数据结构(C语言版)考研复习题.doc

数据结构（C语言版）考研复习题第一章 绪论1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。1.2 常用的存储表示方法有哪几种? 1.3 算法的时间复杂度仅与问题的规模相关吗?1.4 有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大"O"记号表示。例如，设T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n), T2(n)=2.0nlgn-2n=2.0lgn+O(n), 这两个式子表示，当n足够大时T1(n)优于T2(n)，因为前者的常数因子小于后者。请用此方法表示下列函数，并指出当n足够大时，哪一个较优，哪一个较劣? 函数 大"O"表示优劣  (1) T1(n)=5n2-3n+60lgn 5n2+O(n) (2) T2(n)=3n2+1000n+3lgn 3n2+O(n) (3) T3(n)=8n2+3lgn 8n2+O(lgn) (4) T4(n)=1.5n2+6000nlgn 1.5n2+O(nlgn) 第二章 线性表2.1 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜?2.3 为什么在单循环链表中设置尾指针比设置头指针更好?2.4 下述算法的功能是什么?LinkList Demo(LinkList L) / L 是无头结点单链表ListNode *Q,*P;if(L&&L->next)Q=L;L=L->next;P=L;while (P->next) P=P->next;P->next=Q; Q->next=NULL;return L;/ Demo2.5设线性表的n个结点定义为(a0,a1,.an-1)，重写顺序表上实现的插入和删除算法：InsertList 和DeleteList. 2.6 设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。2.7 写一算法在单链表上实现线性表的ListLength(L)运算。2.8 写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。第三章 栈和队列3.1 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题： (1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)? (2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。 (3)请分析 1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。 3.2 链栈中为何不设置头结点?3.3 循环队列的优点是什么? 如何判别它的空和满? 3.4 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢? 3.5 指出下述程序段的功能是什么? (1) void Demo1(SeqStack *S)int i; arr64 ; n=0 ;while ( StackEmpty(S) arrn+=Pop(S);for (i=0, i< n; i+) Push(S, arri); /Demo1(2) SeqStack S1, S2, tmp;DataType x;./假设栈tmp和S2已做过初始化while ( ! StackEmpty (&S1)x=Pop(&S1) ;Push(&tmp,x);while ( ! StackEmpty (&tmp) )x=Pop( &tmp); Push( &S1,x);Push( &S2, x);(3) void Demo2( SeqStack *S, int m)  / 设DataType 为int 型SeqStack T; int i;InitStack (&T);while (! StackEmpty( S)if( i=Pop(S) !=m) Push( &T,i);while (! StackEmpty( &T)i=Pop(&T); Push(S,i);(4)void Demo3( CirQueue *Q) / 设DataType 为int 型int x; SeqStack S;InitStack( &S);while (! QueueEmpty( Q )x=DeQueue( Q); Push( &S,x);while (! StackEmpty( &s) x=Pop(&S); EnQueue( Q,x );/ Demo3(5) CirQueue Q1, Q2; / 设DataType 为int 型int x, i , n= 0;. / 设Q1已有内容， Q2已初始化过while ( ! QueueEmpty( &Q1) )  x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); n+;for (i=0; i< n; i+)  x=DeQueue(&Q2) ; EnQueue( &Q1, x) ; EnQueue( &Q2, x); 3.6 回文是指正读反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈) 3.7 利用栈的基本操作，写一个将栈S中所有结点均删去的算法void ClearStack( SeqStack *S)，并说明S为何要作为指针参数? 3.8 利用栈的基本操作， 写一个返回S中结点个数的算法 int StackSize( SeqStack S),并说明S为何不作为指针参数? 第四章 串4.1 简述下列每对术语的区别：空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。4.2 假设有如下的串说明：char s130="Stocktom,CA", s230="March 5 1999", s330, *p;(1)在执行如下的每个语句后p的值是什么?p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6');(2)在执行下列语句后，s3的值是什么?strcpy(s3,s1); strcat(s3,","); strcat(s3,s2);(3)调用函数strcmp(s1,s2)的返回值是什么?(4)调用函数strcmp(&s15,"ton")的返回值是什么?(5)调用函数stlen(strcat(s1,s2)的返回值是什么?4.3 设T0.n-1="adaabaabcaabaa",P0.m-1="aab".当用模式串匹配目标串T时，请给出所有的有效位移。算法NaiveStrMatch(T,P)返回的位移是哪一个位移。4.4 利用C的库函数strlen,strcpy和strcat写一算法void StrInsert(char *S, char *T, int i),将串T插入到串S的第i个位置上。若i大于S的长度，则插入不执行。4.5 利用C的库函数strlen 和strcpy(或strncpy)写一算法void StrDelete(char *S,int i, int m)删去串S中从位置i开始的连续m个字符。若istrlen(S),则没有字符被删除；若i+mstrlen(S),则将S中从位置i开始直至末尾的字符均删去。4.6 以HString为存储表示，写一个求子串的算法。4.7 一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为：a b c d e f g h i j k l m n o p q r s t u v w x y z n g z q t c o b m u h e l k p d a w x f y i v r s j 则字符串"encrypt"被加密为"tkzwsdf".试写一算法将输入的文本串进行加密后输出；另写一算法，将输入的已加密的文本串进行解密后输出。4.8 写一算法void StrReplace(char *T, char *P, char *S),将T中首次出现的子串P替换为串S。注意：S和P的长度不一定相等。可以使用已有的串操作。第五章 数组和广义表5.1 当稀疏矩阵A和B均以三元组表作为存储结构时，试写出矩阵相加的算法，其结果存放在三元组表C中。5.2 给出C语言的三维数组地址计算公式。5.3 设有三对角矩阵 An*n，将其三条对角线上的元素逐行地存储到向量B0.3n-3中，使得Bk=aij,求：(1)用i , j 表示k的下标变换公式。(2)用 k 表示 i,j 的下标变换公式。5.4 设二维数组A5*6的每个元素占4个字节，已知Loc(a00)=1000，A共占多少个字节? A的终端结点a45的起始地位为何?按行和按列优先存储时，a25的起始地址分别为何?5.5 特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存取的功能?为什么?5.6 简述广义表和线性表的区别与联系。5.7 画出下列广义表的图形表示：5.8 设广义表L=(),(),试问head(L),tail(L),L的长度，深度各为多少?第六章 树6.1 若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。  (1)已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树。  (2)已知一棵二叉树的在序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树。  (3)已知一棵二叉树的前序序列和后序序列分别为AB和BA，请画出这两棵不同的二叉树。 6.2 一棵度为2的有序树与一棵二叉树有何区别?6.3 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。6.4 已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，.nm个度为m的结点，问该树中有多少片叶子?6.5 一个深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号，问：  (1)各层的结点数目是多少?(2)编号为i的结点的双亲结点(若存在)的编号是多少?(3)编号为i的结点的第j个孩子结点(若存在)的编号是多少?(4)编号为i的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少?6.6 高度为h的完全二叉树至少有多少个结点?至多有多少个结点?6.7 在具有n个结点的k叉树(k>=2)的k叉链表表示中，有多少个空指针?6.8 假设二叉树包含的结点数据为1，3，7，12。(1)画出两棵高度最大的二叉树；(2)画出两棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。第七章 图7.1 在图7.23所示的各无向图中：(1)找出所有的简单环。(2)哪些图是连通图?对非连通图给出其连通分量。(3)哪些图是自由树(或森林)?7.2 在图7.24(下图)所示的有向图中： (1) 该图是强连通的吗? 若不是，则给出其强连通分量。(2) 请给出所有的简单路径及有向环。(3) 请给出每个顶点的度，入度和出度。(4) 请给出其邻接表、邻接矩阵及逆邻接表。7.3 假设图的顶点是A,B.，请根据下述的邻接矩阵画出相应的无向图或有向图。             | 0 1 1 0 0 |  | 0 1 1 1 |   | 0 0 0 1 0 |   | 1 0 1 1 |   | 0 0 0 1 0 |   | 1 1 0 1 |   | 1 0 0 0 1 |   | 1 1 1 0 |   | 0 1 0 1 0 |                      (a)               (b) 7.4 假设一棵完全二叉树包括A,B,C.等七个结点，写出其邻接表和邻接矩阵。7.5 对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题?  (1) 图中有多少条边?  (2)任意两个顶点i和j是否有边相连?  (3) 任意一个顶点的度是多少?7.6 n个顶点的连通图至少有几条边?强连通图呢?7.7 DFS和BFS遍历各采用什么样的数据结构来暂存顶点?当要求连通图的生成树的高度最小，应采用何种遍历?7.8 画出以顶点v1为初始源点遍历图7.25（下图）所示的有向图所得到的DFS 和BFS生成森林。第八章 排序8.1以关键字序列(265，301，751，129，937，863，742，694，076，438)为例，分别写出执行以下排序算法的各趟排序结束时，关键字序列的状态。(1) 直接插入排序 (2)希尔排序 (3)冒泡排序 (4)快速排序(5) 直接选择排序 (6) 堆排序 (7) 归并排序 (8)基数排序上述方法中，哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例。8.2 上题的排序方法中，哪些易于在链表(包括各种单、双、循环链表)上实现? 8.3 当Rlow.high中的关键字均相同时，Partion返回值是什么?此时快速排序的的运行时间是多少?能否修改Partion,使得划分结果是平衡的(即划分后左右区间的长度大致相等)? 8.4 若文件初态是反序的，则直接插入，直接选择和冒泡排序哪一个更好? 8.5 若文件初态是反序的，且要求输入稳定，则在直接插入、直接选择、冒泡和快速排序中就选选哪种方法为宜? 8.6 有序数组是堆吗?8.7 高度为h的堆中，最多有多少个元素?最少有多少个元素?在大根堆中，关键字最小的元素可能存放在堆的哪些地方?  8.8 判别下列序列是否为堆(小根堆或大根堆)，若不是，则将其调整为堆：(1) (100,86,73,35,39,42,57,66,21);(2) (12,70,33,65,24,56,48,92,86,33);(3) (103,97,56,38,66,23,42,12,30,52,06,20);(4) (05,56,20,23,40,38,29,61,35,76,28,100). 第九章 查找9.1对含有n个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较? 9.2 若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度：(1)查找不成功，即表中无关键字等于给定值K的记录；(2)查找成功，即表中有关键字等于给定值K的记录。9.3 画出对长度为18的有序的顺序表进行二分查找的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。9.4 为什么有序的单链表不能进行折半查找?9.5 设有序表为(a,b,c,e,f,g,i,j,k,p,q),请分别画出对给定值b,g和n进行折半查找的过程。 9.6 将(for, case, while, class, protected, virtual, public, private, do, template, const ,if, int)中的关键字依次插入初态为空的二叉排序树中，请画出所得到的树T。然后画出删去for之后的二叉排序树T',若再将for 插入T'中得到的二叉排序树T''是否与T相同?最后给出T"的先序、中序和后序序列。9.7 对给定的关键字集合，以不同的次序插入初始为空的树中，是否有可能得到同一棵二叉排序树?9.8 将二叉排序树T的先序序列中的关键字依次插入一空树中，所得和二叉排序树T'与T否相同?为什么?第十章 文件10.1 常见的文件组织方式有哪几种?各有何特点? 文件上的操作有哪几种? 如何评价文件组织的效率?10.2 索引文件、散列文件和多关键字文件适合存放在磁带上吗?为什么?10.3 设有一个职工文件，其记录格式为(职工号、姓名、性别、职务、年龄、工资)。其中职工号为关键字，并设该文件有如下五个记录： 地址 职工号 姓名 性别 职务 年龄    工资  A 39 张恒珊 男 程序员 25     3270  B 50 王莉 女 分析员 31     5685  C 10 季迎宾 男 程序员     28     3575  D 75 丁达芬 女 操作员     18     1650  E 27 赵军 男 分析员     33     6280  (1)若该记录为顺序文件，请写出文件的存储结构； (2)若该文件为索引顺序文件，请写出索引表； (3)若该文件为倒排序文件，请写出关于性别的倒排表和关于职务的倒排表。10.4 在上题所述的文件中，对下列检索写出检索条件的表达式，并写出结果记录的职工号。(1)男性职工(2)工资超过平均工资的职工；(3)职务为程序员和分析员的职工；(4)年龄超过25岁的男性程序员或分析员；10.5 B+树和B-树的主要差异是什么？模拟试题一一、单项选择(每题1分，共10分)1. 若广义表K满足head(K)=tail(K),则K为 () A.( ) B.( ( ) ) C. ( () ),( () ) D.( (),(),() )2.若要求尽可能快地对实数数组进行稳定的排序，则应选()A.快速排序 B.堆排序 C.归并排序 D.基数排序3. 请指出在顺序表2、5、7、10、14、15、18、23、35、41、52中，用二分法查找关键码12需做多少次关键码比较。（）A.2 B.3 C.4 D.5 4对包含N个元素的散列表进行查找，平均查找长度 （. ）A、为 O(log2N) B、为O(N) C、不直接依赖于N D、上述三者都不是 5.一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？（） A. 1，3，2，4 B. 2，3，4，1C. 4，3，1，2 D. 3，4，2，1     6 下面关于图的存储的叙述中，哪一个是正确的。 （）     A用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关      B用相邻矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关     C用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关     D用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关 7. 首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为()A.前序遍历 B.后序遍历 C.中序遍历 D.层次遍历8.对一棵查找树根结点而言，左子树中所有结点与右子树中所有结点的关键字大小关系是()A、小于 B、大于 C、等于、D、不小于9.下面关于B-树和B+树的叙述中，不正确的是 ()A. B-树和B+树都是平衡的多分树 B. B-树和B+树都是可用于文件的索引结构 C. B-树和B+树都能有效地支持顺序检索 D. B-树和B+树都能有效地支持随机检索 10. 给定下列有向图和初始结点V1,按深度优先遍历的结点序列为()A、V1，V2，V4，V5，V3B、V1，V3，V4，V5，V2C、V1，V2，V5，V3，V4D、V1，V2，V3，V4，V5二、填空题 (每小题2分,共20分) 1.从逻辑结构看，线性表是典型的.，树是典型的. 。 2.设有二维数组A0.9,0.19，其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储，则元素A6,6的存储地址为.，按列优顺序存储，元素A6,6的存储地址为.。 3.若按层次顺序将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么当i为.且小于n时，结点I的右兄弟是结点.，否则结点i没有右兄弟。 4.求具有最小带权外部路径长度的扩充二叉树的算法称为.算法。堆排序中建堆的方法称作.。 5.一个串，除自身之外的所有子串都是该串的.。 6、在图结构中，如果一个从Vp到Vq的路径上除Vp和Vq可以相同外，其它结点都不相同，则称此路径为一.,称为.回路。 7、树形选择排序总的时间开销为.。 8、6阶B-树中，每个结点至多包含.个关键码，除根和叶结点外，每个结点至少包含 .个关键码。 9、散列文件是根据文件中关键字的特点设计一种.函数和.方法将记录散列到存储器上的文件。 10、磁带和磁盘中，.适合随机存储，.适合顺序存储。三、简答题(每小题4分，共16分)1.设有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行多少次探测? 2. 什么是二叉排序树?什么是二叉平衡树?3.一棵树有度为1的结点n1个，度为2的结点n2个,度为m的结点nm个，问它有多少个叶结点?4. 什么是散列表的装填因子?为什么说当装填因子非常接近1时，线性探查类似于顺序查找?为什么说当装填因子比较小(比如=0.7左右)时，散列查找的平均查找时间为O(1)? 四、应用题：(每题5分，共20分)1.把下面的树变成二叉树。2. 在一棵空的二叉查找树中依次插入关键字序列为20、30、8、12、34、5、60、5、1，29，请画出所得到的二叉查找树。3.画出下列网络的最小生成树。 4.假设用于通信的电文仅由A-H八个字母组成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10。试为这八个字母设计哈夫曼编码。图： 五、算法题(共34分)1.试写一算法写出用二叉链表表示给定二叉树的叶结点总数。 (12分)2.下面给出了冒泡排序算法，请填写算法中的空框，使算法正确。(10分)typedef struct int key； datatype info;/设datatype已经定义 node； void BubbleSort ( node R)/R中元素个数为n个 int i,j; Boolean flag； node X； for(i=1;i<=n-1;i+) .(1). for (j=n-1;j>=i;j-).(2). if(.(3).)Rj.key flag =TURE； X=Rj;.(4).;Rj1= X; if(.(5).)return; / 算法结束 3.设一单链表的头指针为head,链表的结点中包含着整数类型的key域，试设计算法将此链表的结点按照key递增次序进行就地排序。 (12分)模拟试题二一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( ) A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构 2.在长度为n的顺序表的第i(1in+1)个位置上插入一个元素，元素的移动次数为( ) A.n-i+1 B.n-i C.i D.i-1 3.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( ) A.顺序表 B.用头指针表示的单循环链表 C.用尾指针表示的单循环链表 D.单链表 4.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为( ) A.4 B.5 C.6 D.7 5.为查找某一特定单词在文本中出现的位置，可应用的串运算是( ) A.插入 B.删除 C.串联接 D.子串定位 6.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=SCIENCESTUDY，则调用函数Scopy(P,Sub(S,1,7)后得到( ) A.P=SCIENCE B.P=STUDY C.S=SCIENCE D.S=STUDY 7.三维数组A456按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A45的存储地址为( ) A.356 B.358 C.360 D.362 8.如右图所示广义表是一种( ) A.线性表 B.纯表 C.结点共享表 D.递归表 9.下列陈述中正确的是( ) A.二叉树是度为2的有序树 B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中必有度为2的结点 D.二叉树中最多只有两棵子树，并且有左右之分 10.n个顶点的有向完全图中含有向边的数目最多为( ) A.n-1 B.n C.n(n-1)/2 D.n(n-1) 11.已知一个有向图如右所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序列为( ) A.a d b e f c B.a d c e f b C.a d c b f e D.a d e f c b  12.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是( ) A.快速排序 B.堆排序 C.归并排序 D.基数排序 13.不可能生成右图所示二叉排序树的关键字序列是( ) A.4 5 3 1 2 B.4 2 5 3 1 C.4 5 2 1 3 D.4 2 3 1 5 14.ALV树是一种平衡的二叉排序树，树中任一结点的( ) A.左、右子树的高度均相同 B.左、右子树高度差的绝对值不超过1 C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度 15.在VSAM文件的控制区间中，记录的存储方式为( ) A.无序顺序 B.有序顺序 C.无序链接 D.有序链接 二、填空题(本大题共10小题，每小题2分， 若有两个空格，每个空格1分，共20分) 16.若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为_。 17.在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是_和_。 18.假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为_。 19.串S=I am a worker的长度是_。 20.假设一个10阶的下三角矩阵A按列优顺序压缩存储在一维数组C中，则C数组的大小应为_。 21.在n个结点的线索二叉链表中，有_个线索指针。 22.若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为_。 23.对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为_。 24.由10000个结点构成的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度的最大值可能达到_。 25.若要找出所有工资低于1500元，职称是副教授，及所有工资低于2000元，职称是教授的记录，则查询条件是_。 三、解答题(本大题共4小题，每小题5分，共20分) 26.已知一个6行5列的稀疏矩阵中非零元的值分别为：-90，41，-76，28，-54，65和-8，它们在矩阵中的列号依次为：1，4，5，1，2，4和5。当以带行表的三元组表作存储结构时，其行表RowTab中的值依次为0，0，2，2，3和5。请写出该稀疏矩阵(注：矩阵元素的行列下标均从1开始)。 27.已知树T的先序遍历序列为ABCDEFGHJKL，后序遍历序列为CBEFDJIKLHGA。请画出树T。 28.对关键字序列(72，87，61，23，94，16，05，58)进行堆排序，使之按关键字递减次序排列。请写出排序过程中得到的初始堆和前三趟的序列状态。 初始堆：_ 第1趟：_ 第2趟：_ 第3趟：_ 29.在关键字序列(07，12，15，18，27，32，41，92)中用二分查找法查找和给定值92相等的关键字，请写出查找过程中依次和给定值“92”比较的关键字。 四、算法阅读题(本大题共4小题，每小题5分，共20分) 30.以下函数中，h是带头结点的双向循环链表的头指针。 (1)说明程序的功能； (2)当链表中结点数分别为1和6(不包括头结点)时，请写出程序中while循环体的执行次数。 int f(DListNode *h) DListNode *p,*q; int j=1; p=h->next; q=h->prior; while(p!=q && p->prior!=q) if(p->data=q->data) p=p->next; q=q->prior; else j=0; return j; 31.设栈S=(1,2,3,4,5,6,7),其中7为栈顶元素。请写出调用algo(&s)后栈S的状态。 void algo(Stack *S) int i=0; Queue Q; Stack T; InitQueue(&Q);InitStack(&T); while (!StackEmpty(S) if(i=!i)!=0)Push(&T,Pop(&S); else EnQueue(&Q,Pop(&S); while(!QueueEmpty(Q) Push(&S,DeQueue(&Q); while(!StackEmpty(T) Push(&S,Pop(&T)； 32.已知带权图的邻接矩阵表示和邻接表表示的形式说明分别如下： #define MaxNum 50/图的最大顶点数 #define INFINITY INT_MAX /INT_MAX为最大整数，表示 typedef struct char vexsMaxNum;/字符类型的顶点表 int edgesMaxNumMaxMum;/权值为整型的邻接矩阵 int n,e;/图中当前的顶点数和边数 MGraph;/邻接矩阵结构描述 typedef struct node int adjvex;/邻接点域 int weight;/边的权值 struct node *next;/链指针域 EdgeNode;/边表结点结构描述 typedef struct char vertex;/顶点域 EdgeNode * firstedge;/边表头指针 VertexNode ;/顶点表结点结构描述 typedef struct VertexNode adjlistMaxNum;/邻接表 int n,e;/图中当前的顶点数和边数 ALGraph;/邻接表结构描述 下列算法是根据一