哈夫曼树构造方法_哈夫曼树只有度为0和度为2

数据结构试题及答案 　　第一篇：数据结构试题及答案 　　数据结构试卷 　　（二）一、选择题(24分)1．下面关于线性表的叙述错误的是（）。 　　(A)线性表采用顺序存储必须占用一片连续的存储空间 　　(B)线性表采用链式存储不必占用一片连续的存储空间(C)线性表采用链式存储便于插入和删除操作的实现(D)线性表采用顺序存储便于插入和删除操作的实现 　　2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。 　　(A)2m-1(B)2m(C)2m+1(D)4m 3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头素的前一位置，尾指针R总是指向队尾素的当前位置，则该循环队列中的素个数为（）。 　　(A)R-F(B)F-R(C)(R-F+M)％M(D)(F-R+M)％M 4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。 　　(A)BADC(B)BCDA(C)CDAB(D)CBDA 5．设某完全无向图中有n个顶点，则该完全无向图中有（）条边。 　　(A)n(n-1)/2(B)n(n-1)(C)n 　　2(D)n2-1 6．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。 　　(A)9(B)10(C)11(D)12 7．设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。 　　(A)n-1(B)n(C)n+1(D)2n-1 8．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（）。 　　(A)2，3，5，8，6(B)3，2，5，8，6(C)3，2，5，6，8(D)2，3，6，5，8 　　二、填空题(24分)1.1.为了能有效地应用HASH查找技术，必须解决的两个问题是____________________和__________________________。 　　2.2.下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。 　　typedef struct {int s[100];int top;} sqstack;void push(sqstack &stack,int x){ if(stack.top==m-1)printf(“overflow”); 　　else {____________________;_________________;} } 3.3.中序遍历二叉排序树所得到的序列是___________序列（填有序或无序）。4.4.快速排序的最坏时间复杂度为___________，平均时间复杂度为__________。5.5.设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数为_________；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_______个空指针域。 　　6.6.设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=_______。 　　7.7.设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立的初始堆为___________________________。 　　v1324v213v31428.8.设某无向图G的邻接表为v413，则从顶点V1开始的深度优先遍历序列为___________；广度优先遍历序列为____________。 　　三、应用题(36分)1． 1． 设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。 　　2． 2． 设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。 　　3． 3． 设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。 　　4． 4． 设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。5． 5． 设有无向图G（如右图所示），要求给出用普里姆算法构造最小生成树所走过的边的集合。 　　6． 6． 设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。 　　数据结构试卷 　　（二）参考答案 　　一、选择题 1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C 　　二、填空题 　　1.1.构造一个好的HASH函数，确定解决冲突的方法 2.2.stack.top++，stack.s[stack.top]=x 3.3.有序 　　4.4.O(n2)，O(nlog2n)5.5.N0-1，2N0+N1 6.6.d/2 7.7.(31，38，54，56，75，80，55，63)8.8.(1，3，4，2)，(1，3，2，4) 　　三、应用题 　　1.1.(22，40，45，48，80，78)，(40，45，48，80，22，78)2.2.q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;3.3.2,ASL=91*1+2*2+3*4+4*2)=25/9 4.4.树的链式存储结构略，二叉树略 　　5.5.E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)} 6.6.略 　　数据结构试卷 　　（三）一、选择题(30分)1．设某数据结构的二组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={，，，，，，，}，则数据结构A是（）。 　　(A)线性结构(B)树型结构(C)物理结构(D)图型结构 2．下面程序的时间复杂为（） 　　for（i=1，s=0； inext；p->data=q->data；p->next=q->next；free(q)；(B)q=p->next；q->data=p->data；p->next=q->next；free(q)； 　　(C)q=p->next；p->next=q->next；free(q)； 　　(D)q=p->next；p->data=q->data；free(q)； 　　4．设有n个待排序的记录关键字，则在堆排序中需要（）个辅助记录单。 　　(A)1(B)n(C)nlog2n(D)n2 　　5．设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为()。(A)10，15，14，18，20，36，40，21(B)10，15，14，18，20，40，36，21(C)10，15，14，20，18，40，36，2l(D)15，10，14，18，20，36，40，21 6．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。(A)O(1)(B)O(log2n)(C)(D)O(n)7．设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）。 　　(A)n，e(B)e，n(C)2n，e(D)n，2e 8.设某强连通图中有n个顶点，则该强连通图中至少有（）条边。 　　(A)n(n-1)(B)n+1(C)n(D)n(n+1)9．设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。 　　(A)快速排序(B)堆排序(C)归并排序(D)插入排序 10.下列四种排序中（）的空间复杂度最大。 　　(A)插入排序(B)冒泡排序(C)堆排序(D)归并排序 　　二、填空殖(48分，其中最后两小题各6分)1.1.数据的物理结构主要包括_____________和______________两种情况。 　　2.2.设一棵完全二叉树中有500个结点，则该二叉树的深度为__________；若用二叉链表作为该完全二叉树的存储结构，则共有___________个空指针域。 　　3.3.设输入序列为1、2、3，则经过栈的作用后可以得到___________种不同的输出序列。 　　4.4.设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有素之和等于顶点i的________，第i列上所有素之和等于顶点i的________。 　　5.5.设哈夫曼树中共有n个结点，则该哈夫曼树中有________个度数为1的结点。6.6.设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为_________。 　　7.7.__________遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。 　　8.8.设查找表中有100个素，如果用二分法查找方法查找数据素X，则最多需要比较________次就可以断定数据素X是否在查找表中。 　　9.9.不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为____________。 　　10.10.设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为____________，右孩子结点的编号为___________。11.11.设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的一趟快速排序结果为___________________________。 　　12.12.设有向图G中有向边的集合E={，，，，}，则该图的一种拓扑序列为____________________。 　　13.13.下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。 　　struct record{int key;int others;};int hashsqsearch(struct record hashtable[ ],int k){ int i,j;j=i=k % p;while(hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____)%m;if(i==j)return(-1);} 　　if(_______________________)return(j);else return(-1);} 14.14.下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。 　　typedef struct node{int key;struct node *lchild;struct node *rchild;}bitree;bitree *bstsearch(bitree *t, int k){ 　　if(t==0)return(0);else while(t!=0)if(t->key==k)_____________;else if(t->key>k)t=t->lchild;else_____________;} 　　数据结构试卷 　　（三）参考答案 　　一、选择题 　　1.B 2.B 3.A 4.A 5.A 6.B 7.D 8.C 9.B 10.D 第3小题分析：首先用指针变量q指向结点A的后继结点B，然后将结点B的值复制到结点A中，最后删除结点B。 　　第9小题分析：9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数，而堆排序只需要在初始堆的基础上再进行10次筛选即可，每次筛选的时间复杂度为O(log2n)。 　　二、填空题 　　1.1.顺序存储结构、链式存储结构 2.2.9，501 3.3.5 4.4.出度，入度 5.5.0 6.6.e=d 7.7.中序 8.8.7 9.9.O(1)10.10.i/2，2i+1 11.11.(5，16，71，23，72，94，73)12.12.(1，4，3，2)13.13.j+1，hashtable[j].key==k 14.14.return(t)，t=t->rchild 第8小题分析：二分查找的过程可以用一棵二叉树来描述，该二叉树称为二叉判定树。在有序表上进行二分查找时的查找长度不超过二叉判定树的高度1+log2n。 　　} 　　数据结构试卷 　　（四）一、选择题(30分)1．设一维数组中有n个数组素，则读取第i个数组素的平均时间复杂度为（）。(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n)2．设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。 　　(A)2k-1(B)2k(C)2k-1(D)2k-1 3．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。 　　(A)n(B)e(C)2n(D)2e 4．在二叉排序树中插入一个结点的时间复杂度为（）。 　　(A)O(1)(B)O(n)(C)O(log2n)(D)O(n2)5．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。 　　(A)n(B)n-1(C)m(D)m-1 6．设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。 　　(A)3(B)4(C)5(D)8 7．设用链表作为栈的存储结构则退栈操作（）。 　　(A)必须判别栈是否为满(B)必须判别栈是否为空 　　(C)判别栈素的类型(D)对栈不作任何判别 8．下列四种排序中（）的空间复杂度最大。 　　(A)快速排序(B)冒泡排序(C)希尔排序(D)堆 　　9．设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（）。 　　(A)N0=N1+1(B)N0=Nl+N2(C)N0=N2+1(D)N0=2N1+l 10.设有序顺序表中有n个数据素，则利用二分查找法查找数据素X的最多比较次数不超过（）。 　　(A)log2n+1(B)log2n-1(C)log2n(D)log2(n+1) 　　二、填空题(42分)1． 1． 设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平均时间复杂度为_________。 　　2． 2． 设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为_________________________________________________________（设结点中的两个指针域分别为llink和rlink）。3． 3． 根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为____________。4． 4． 深度为k的完全二叉树中最少有____________个结点。5． 5． 设初始记录关键字序列为(K1，K2，…，Kn)，则用筛选法思想建堆必须从第______个素开始进行筛选。 　　6． 6． 设哈夫曼树中共有99个结点，则该树中有_________个叶子结点；若采用二叉链表作为存储结构，则该树中有_____个空指针域。 　　7． 7． 设有一个顺序循环队列中有M个存储单，则该循环队列中最多能够存储________个队列素；当前实际存储________________个队列素（设头指针F指向当前队头素的前一个位置，尾指针指向当前队尾素的位置）。 　　8． 8． 设顺序线性表中有n个数据素，则第i个位置上插入一个数据素需要移动表中_______个数据素；删除第i个位置上的数据素需要移动表中_______个素。9． 9． 设一组初始记录关键字序列为(20，18，22，16，30，19)，则以20为中轴的一趟快速排序结果为______________________________。 　　10．10．设一组初始记录关键字序列为(20，18，22，16，30，19)，则根据这些初始关键字序列建成的初始堆为________________________。 　　11．11．设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是______________________。 　　12．12．设无向图对应的邻接矩阵为A，则A中第i上非0素的个数_________第i列上非0素的个数（填等于，大于或小于）。 　　13．13．设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该二叉树的序列为_____________。 　　14．14．设散列函数H(k)=k mod p，解决冲突的方法为链地址法。要求在下列算法划线处填上正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点，成功时返回指向关键字的指针，不成功时返回标志0。 　　typedef struct node {int key;struct node *next;} lklist;void createlkhash(lklist *hashtable[ ]){ int i,k;lklist *s;for(i=0;inext=hashtable[k];_______________________;} } 　　数据结构试卷 　　（四）参考答案 　　一、选择题 　　1．C 2．D 3．D 4．B 5．C 6．A 7．B 8．A 9．C 10．A 　　二、填空题 　　1.1.O(n2)，O(nlog2n)2.2.p>llink->rlink=p->rlink;p->rlink->llink=p->rlink 3.3.3 4.4.2k-1 5.5.n/2 6.6.50，51 7.7.m-1，(R-F+M)%M 8.8.n+1-i，n-i 9.9.(19，18，16，20，30，22)10.10.(16，18，19，20，32，22)11.11.A[i][j]=1 12.12.等于 13.13.BDCA 14.14.hashtable[i]=0，hashtable[k]=s 　　数据结构试卷 　　（五）一、选择题(30分) 　　1．数据的最小单位是（）。 　　(A)数据项(B)数据类型(C)数据素(D)数据变量 　　2．设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（）。 　　(A)40，50，20，95(B)15，40，60，20(C)15，20，40，45(D)45，40，15，20 3．设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。 　　(A)15，25，35，50，20，40，80，85，36，70(B)15，25，35，50，80，20，85，40，70，36(C)15，25，35，50，80，85，20，36，40，70(D)15，25，35，50，80，20，36，40，70，85 4．函数substr(“DATASTRUCTURE”，5，9)的返回值为（）。 　　(A)“STRUCTURE”(B)“DATA” 　　(C)“ASTRUCTUR”(D)“DATASTRUCTURE” 5．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（）。 　　(A)O(log2n)(B)O(1)(C)O(n2)(D)O(n)6．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（）。 　　(A)Nl+N2+……+Nm 　　(B)l+N2+2N3+3N4+……+(m-1)Nm(C)N2+2N3+3N4+……+(m-1)Nm(D)2Nl+3N2+……+(m+1)Nm 　　7．设有序表中有1000个素，则用二分查找查找素X最多需要比较（）次。 　　(A)25(B)10(C)7(D)1 8．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（）。 　　(A)abedfc(B)acfebd(C)aebdfc(D)aedfcb 9．设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个素是n，则输出序列中第i个输出素是（）。 　　(A)n-i(B)n-1-i(C)n+1-i(D)不能确定 设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是（）。 　　(A)40，42，45，55，80，83(B)42，40，45，80，85，88(C)42，40，45，55，80，85(D)42，40，45，85，55，80 　　二、填空题(共30分)1.1.设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是____________________。 　　2.2.在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。 　　3.3.设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的素（包括对角线上素）存放在n(n+1)个连续的存储单中，则A[i][j]与A[0][0]之间有_______个数据素。 　　4.4.栈的插入和删除只能在栈的栈顶进行，后进栈的素必定先出栈，所以又把栈称为__________表；队列的插入和删除运算分别在队列的两端进行，先进队列的素必定先出队列，所以又把队列称为_________表。 　　5.5.设一棵完全二叉树的顺序存储结构中存储数据素为ABCDEF，则该二叉树的前序遍历序列为___________，中序遍历序列为___________，后序遍历序列为___________。 　　6.6.设一棵完全二叉树有128个结点，则该完全二叉树的深度为________，有__________个叶子结点。 　　7.7.设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零素个数之和等于顶点i的________，第i列中所有非零素个数之和等于顶点i的__________。 　　8.8.设一组初始记录关键字序列(k1，k2，……，kn)是堆，则对i=1，2，…，n/2而言满足的条件为_______________________________。 　　9.9.下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。void bubble(int r[n]){ for(i=1;ir[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;} if(exchange==0)return； } } 10.10.下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。struct record{int key;int others;};int bisearch(struct record r[ ], int k){ 　　int low=0,mid,high=n-1; 　　while(lownext==0(C)head->next==head(D)head!=0 4．时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（）。 　　(A)堆排序(B)冒泡排序(C)希尔排序(D)快速排序 　　5．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。 　　(A)空或只有一个结点(B)高度等于其结点数 　　(C)任一结点无左孩子(D)任一结点无右孩子 　　6．一趟排序结束后不一定能够选出一个素放在其最终位置上的是（）。 　　(A)堆排序(B)冒泡排序(C)快速排序(D)希尔排序 7．设某棵三叉树中有40个结点，则该三叉树的最小高度为（）。 　　(A)3(B)4(C)5(D)6 8．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。 　　21/2(A)O(n)(B)O(n)(C)O(n)(D)O(1og2n)9．二路归并排序的时间复杂度为（）。(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)10.深度为k的完全二叉树中最少有（）个结点。 　　(A)2k-1-1(B)2k-1(C)2k-1+1(D)2k-1 11.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。 　　(A)front->next=s；front=s；(B)s->next=rear；rear=s； 　　(C)rear->next=s；rear=s；(D)s->next=front；front=s； 　　12.设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（）。(A)O(n+e)(B)O(n)(C)O(ne)(D)O(n)13.设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。 　　(A)99(B)100(C)101(D)102 14.设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（）。(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)15.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。 　　(A)第i行非0素的个数之和(B)第i列非0素的个数之和 　　(C)第i行0素的个数之和(D)第i列0素的个数之和 　　二、判断题(20分)1．调用一次深度优先遍历可以访问到图中的所有顶点。（） 　　2．分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（）3．冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（）4．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（） 　　5．设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（）6．层次遍历初始堆可以得到一个有序的序列。（） 　　7．设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（）8．线性表的顺序存储结构比链式存储结构更好。（） 　　9．中序遍历二叉排序树可以得到一个有序的序列。（）10.快速排序是排序算法中平均性能最好的一种排序。（） 　　三、填空题(30分)1．for(i=1，t=1，s=0；inext=p->next;p->next=s 3.3.(1，3，2，4，5)4.4.n-1 5.5.129 6.6.F==R 7.7.p->lchild==0&&p->rchild==0 8.8.O(n2)9.9.O(nlog2n)，O(n)10.10.开放定址法，链地址法 　　数据结构试卷 　　（七）一、选择题(30分)1．设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。 　　(A)2n(B)n(C)n/2(D)n(n-1)2．设无向图G中有n个顶点，则该无向图的最小生成树上有（）条边。 　　(A)n(B)n-1(C)2n(D)2n-1 3．设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是（）。 　　(A)40，42，60，55，80，85(B)42，45，55，60，85，80(C)42，40，55，60，80，85(D)42，40，60，85，55，80 4．（）二叉排序树可以得到一个从小到大的有序序列。 　　(A)先序遍历(B)中序遍历(C)后序遍历(D)层次遍历 　　5．设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（）。 　　(A)2i+1(B)2i(C)i/2(D)2i-1 6．程序段s=i=0；do {i=i+1； s=s+i；}while(inext==0(C)head->next==head(D)head!=0 8．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。 　　(A)20(B)256(C)512(D)1024 9．设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（）。 　　(A)1(B)2(C)3(D)4 10.设指针变量top指向当前链式栈的栈顶，则删除栈顶素的操作序列为（）。 　　(A)top=top+1;(B)top=top-1;(C)top->next=top;(D)top=top->next; 　　三、填空题(30分)1.1.设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为_________=p；s->right=p->right；__________=s； p->right->left=s；（设结点中的两个指针域分别为left和right）。2.2.设完全有向图中有n个顶点，则该完全有向图中共有________条有向条；设完全无向图中有n个顶点，则该完全无向图中共有________条无向边。 　　3.3.设关键字序列为(Kl，K2，…，Kn)，则用筛选法建初始堆必须从第______个素开始进行筛选。 　　4.4.解决散列表冲突的两种方法是________________和__________________。 　　5.5.设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为3的结点数有______个。 　　6.6.高度为h的完全二叉树中最少有________个结点，最多有________个结点。7.7.设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟直接插入排序结束后的结果的是__________________________________。 　　8.8.设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟简单选择排序结束后的结果的是__________________________________。 　　9.9.设一棵二叉树的前序序列为ABC，则有______________种不同的二叉树可以得到这种序列。 　　10.10.下面程序段的功能是实现一趟快速排序，请在下划线处填上正确的语句。 　　struct record {int key;datatype others;};void quickpass(struct record r[], int s, int t, int &i){ 　　int j=t;struct record x=r[s];i=s; 　　while(ileft=p，p->right 2.2.n(n-1)，n(n-1)/2 3.3.n/2 4.4.开放定址法，链地址法 5.5.14 6.6.2h-1，2h-1 7.7.(12，24，35，27，18，26)8.8.(12，18，24，27，35，26)9.9.5 10.10.idata=k;t->lchild=t->rchild=0;} else if(t->data>k)bstinsert(t->lchild,k);else__________________________;} 3． 3． 设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列：s->next=p->next;_________________。4． 4． 设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，则指针变量p和指针变量head之间的关系是p=_________和head=__________（设结点中的两个指针域分别为llink和rlink）。 　　5． 5． 设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为__________。 　　6． 6． 完全二叉树中第5层上最少有__________个结点，最多有_________个结点。7． 7． 设有向图中不存在有向边，则其对应的邻接矩阵A中的数组素A[i][j]的值等于____________。 　　8． 8． 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则第4趟直接选择排序结束后的结果为_____________________________。 　　9． 9． 设连通图G中有n个顶点e条边，则对应的最小生成树上有___________条边。10． 10． 设有一组初始记录关键字序列为(50，16，23，68，94，70，73)，则将它们调整成初始堆只需把16与___________相互交换即可。 　　数据结构试卷 　　（八）参考答案 　　一、选择题 1．C 2．C 3．C 4．B 5．B 6．C 7．B 8．C 9．A 10．A 　　三、填空题 　　1.1.(49，13，27，50，76，38，65，97)2.2.t=(bitree *)malloc(sizeof(bitree))，bstinsert(t->rchild,k)3.3.p->next=s 4.4.head->rlink，p->llink 5.5.CABD 6.6.1，16 7.7.0 8.8.(13，27，38，50，76，49，65，97)9.9.n-1 10.10.50 　　第二篇：2013台湾省数据结构试题及答案（推荐） 　　1、串的逻辑结构与（D）的逻辑结构不相同。A）线性表 B）栈 C）队列 D）集合 　　2、广义表head(((a,b),(c,d)))的运算结果为（A）。A）(a,b)B）(c,d)C）空表 D）（（a,b）,(c,d)） 　　3、链式存储的存储结构所占存储空间（A）。 　　A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B）只有一部分，存放结点值 　　C）只有一部分，存储表示结点间关系的指针 　　D）分两部分，一部分存放结点值，另一部分存放结点所占单数 　　4、设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为（A）。 　　A）p->next=p->next->next;B）p=p->next;C）p=p->next->next;D）p->next=p; 　　5、在一个具有n个单的顺序栈中，假定以地址低端（即0单）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（C）。 　　A）top不变 B）top=0 C）top–D）top++ 　　6、数据结构研究的内容是（D）。 　　A）数据的逻辑结构 B）数据的存储结构 　　C）建立在相应逻辑结构和存储结构上的算法 D）包括以上三个方面 　　7、向一个栈顶指针为hs的链栈中插入一个s结点时，应执行（D）。A)hs->next=s; 　　B)s->next=hs->next;hs->next=s;C)s->next=hs;hs=s;D)s->next=hs;hs=hs->next; 　　8、设一数列的顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为（B）。A）3，2，5，6，4，1 B）1，5，4，6，2，3 C）2，4，3，5，1，6 D）4，5，3，6，2，1 　　9、广义表head(((a,b),(c,d)))的运算结果为（A）。A）(a,b)B）(c,d)C）空表 D）（（a,b）,(c,d)） 　　10、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是(B)。A）9 B）11 C）15 D）不能确定 　　11、在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（B）。A)rear=rear->next;B)front=front->next;C)rear=front->next; 　　D)front=rear->next; 　　12、n个顶点的图的最小生成树必定（D），是不正确的描述。A）不唯一 B）权的总和唯一 C）不含回路 D）有n条边 　　13、串的逻辑结构与（D）的逻辑结构不同。A）线性表 B）栈 C）队列 D）树 　　第三篇：数据结构试题及答案10 　　《数据结构》自考复习思考试题 　　一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 　　1.若将数据结构形式定义为二组(K，R)，其中K是数据素的有限集合，则R是K上（） 　　A.操作的有限集合B.映象的有限集合 C.类型的有限集合D.关系的有限集合 　　2.在长度为n的顺序表中删除第i个素(1≤i≤n)时，素移动的次数为（）A.n-i+1 　　B.i C.i+1 　　D.n-i 3.若不带头结点的单链表的头指针为head，则该链表为空的判定条件是（）A.head==NULL 　　B.head->next==NULL C.head!=NULL 　　D.head->next==head 4.引起循环队列队头位置发生变化的操作是（）A.出队 　　B.入队 　　C.取队头素 　　D.取队尾素 　　5.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（）A.2，4，3，1，5，6 　　B.3，2，4，1，6，5 C.4，3，2，1，5，6 　　D.2，3，5，1，6，4 6.字符串通常采用的两种存储方式是（）A.散列存储和索引存储 　　B.索引存储和链式存储 C.顺序存储和链式存储 　　D.散列存储和顺序存储 　　7.设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为（）A.m 　　B.n-m C.n-m+1 　　D.n 8.二维数组A［12］［18］采用列优先的存储方法，若每个素各占3个存储单，且第1个素的地址为150，则素A［9］［7］的地址为（）A.429 　　B.432 C.435 　　D.438 9.对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是（）A.(e,f) 　　B.((e,f))C.(f) 　　D.()10.下列图示的顺序存储结构表示的二叉树是（）11.n个顶点的强连通图中至少含有（）A.n-1条有向边 　　B.n条有向边 C.n(n-1)/2条有向边 　　D.n(n-1)条有向边 　　12.对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为（）A.(19，23，56，34，78，67，88，92) 　　B.(23，56，78，66，88，92，19，34)C.(19，23，34，56，67，78，88，92) 　　D.(19，23，67，56，34，78，92，88)13.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为（） 　　A.4 　　B.5 C.8 　　D.9 14.由同一关键字集合构造的各棵二叉排序树（）A.其形态不一定相同，但平均查找长度相同 　　B.其形态不一定相同，平均查找长度也不一定相同 C.其形态均相同，但平均查找长度不一定相同 D.其形态均相同，平均查找长度也都相同 　　15.ISAM文件和VSAM文件的区别之一是（）A.前者是索引顺序文件，后者是索引非顺序文件 B.前者只能进行顺序存取，后者只能进行随机存取 C.前者建立静态索引结构，后者建立动态索引结构 D.前者的存储介质是磁盘，后者的存储介质不是磁盘 　　二、填空题(本大题共10小题，每空2分，共20分)16.数据的逻辑结构在计算机存储器内的表示，称为数据的____________。17.删除双向循环链表中*p的前驱结点(存在)应执行的语句是____________。18.栈下溢是指在____________时进行出栈操作。 　　19.已知substr(s,i,len)函数的功能是返回串s中第i个字符开始长度为len的子串，strlen(s)函数的功能是返回串s的长度。若s=″ABCDEFGHIJK″,t=″ABCD″,执行运算substr(s,strlen(t), strlen(t))后的返回值为____________。 　　20.去除广义表LS=(a1,a2,a3,„„，an)中第1个素，由其余素构成的广义表称为LS的____________。 　　21.已知完全二叉树T的第5层只有7个结点，则该树共有____________个叶子结点。22.在有向图中，以顶点v为终点的边的数目称为v的____________。 　　23.当关键字的取值范围是实数集合时，无法进行箱排序和____________排序。24.产生冲突现象的两个关键字称为该散列函数的____________。 　　25.假设散列文件中一个桶能存放m个记录，则桶“溢出”的含义是，当需要插入新的记录时，该桶中____________。 　　三、解答题(本大题共4小题，每小题5分，共20分)26.假设以数组seqn［m］存放循环队列的素，设变量rear和quelen分别指示循环队列中队尾素的位置和素的个数。(1)写出队满的条件表达式；(2)写出队空的条件表达式； 　　(3)设m=40,rear=13,quelen=19,求队头素的位置；(4)写出一般情况下队头素位置的表达式。 　　27.已知一棵二叉树的中序序列为ABCDEFG，层序序列为BAFEGCD，请画出该二叉树。28.画出下图所示有向图的所有强连通分量。 　　29.对7个关键字进行快速排序，在最好的情况下仅需进行10次关键字的比较。(1)假设关键字集合为{1,2,3,4,5,6,7}，试举出能达到上述结果的初始关键字序列；(2)对所举序列进行快速排序，写出排序过程。 　　四、算法阅读题(本大题共4小题，每小题5分，共20分)30.阅读下列算法，并回答问题：(1)设顺序表L=(3,7,11,14,20,51)，写出执行f30(&L,15)之后的L；(2)设顺序表L=(4,7,10,14,20,51)，写出执行f30(&L,10)之后的L；(3)简述算法的功能。 　　void f30(SeqList*L, DataType x){ 　　int i =0, j; 　　while(ilength && x>L->data［i］)i++; 　　if(ilength && x==L->data［i］){ 　　for(j=i+1;jlength;j++) 　　L->data［j-1］=L->data［j］; 　　L->length–; 　　} else { 　　for(j=L->length;j>i;j–) 　　L->data［j］=L->data［j-1］; 　　L->data［i］=x; 　　L->length++; 　　} } 31.已知图的邻接表表示的形式说明如下： 　　#define MaxNum 　　//图的最大顶点数 typedef struct node { 　　int 　　adjvex; 　　//邻接点域 　　struct node *next; 　　//链指针域 　　} EdgeNode; 　　//边表结点结构描述 typedef struct { 　　char vertex; 　　//顶点域 　　EdgeNode 　　*firstedge; 　　//边表头指针 } VertexNode; 　　//顶点表结点结构描述 typedef struct { 　　VertexNode adjlist［MaxNum］; 　　//邻接表 　　int n, e; 　　//图中当前的顶点数和边数 } ALGraph; 　　//邻接表结构描述 　　下列算法输出图G的深度优先生成树(或森林)的边。阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。 　　typedef enum {FALSE, TRUE} Boolean;Boolean visited［MaxNum］;void DFSForest(ALGraph *G){ 　　int i; 　　for(i=0;in;i++)visited［i］= 　　(1) 　　; 　　for(i=0;in;i++)if(!visited［i］)DFSTree(G,i);} void DFSTree(ALGraph *G, int i){ 　　EdgeNode *p; 　　visited［i］=TRUE; 　　p=G->adjlist［i］.firstedge; 　　while(p!=NULL){ 　　if(!visited［p->adjvex］){ 　　printf(″″,G->adjlist［i］.vertex，G->adjlist［p->adjvex］.vertex); 　　(2) 　　; 　　} 　　(3) 　　; 　　} } 32.阅读下列算法，并回答问题： 　　(1)假设数组L［8］={3,0,5,1,6,4,2,7}，写出执行函数调用f32(L，8)后的L；(2)写出上述函数调用过程中进行素交换操作的总次数。void f32(int R［］,int n){ 　　int i,t; 　　for(i=0;inext; 　　while(p) 　　{ 　　q=p->next; 　　j=p->key%m; 　　(2) 　　; 　　H［j］=p; 　　(3) 　　; 　　} 　　free(L); 　　} 　　五、算法设计题(本大题10分)34.假设以带双亲指针的二叉链表作为二叉树的存储结构，其结点结构的类型说明如下所示： typedef char DataType;typedef struct node { 　　DataType data; 　　struct node *lchild, *rchild; 　　//左右孩子指针 　　struct node *parent; 　　//指向双亲的指针 } BinTNode;typedef BinTNode *BinTree;若px为指向非空二叉树中某个结点的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继。 　　(1)就后继的不同情况，简要叙述实现求后继操作的方法； 　　(2)编写算法求px所指结点的中序序列后继，并在算法语句中加注注释。数据结构标准答案 　　一、单项选择题 1.(B)2.(D)3.(A)4.(A)5.(D)6.(C)7.(C)8.(A)9.(B)10.(A)11.(B)12.(D)13.(C)14.(B)15.(C) 　　二、填空题(本大题共10小题，每空2分，共20分)16.存储结构 17.q = p->pre;q->pre->next = p;p->pre = q->pre;free(q);18.栈空 　　19.“DEFG” //注意双引号不能少 20.表尾 　　21.２^(I-2)+M/2 叶子结点． 22.入度 23.基数 24.同义词 　　25.已有m个同义词记录 　　三、解答题(本大题共4小题，每小题5分，共20分)26.(1)quelen == m(2)quelen == 0(3)(13quelen + m)% m 27.B 　　/ 　　A F 　　/ 　　E G 　　/ 　　C 　　D 28.3个: a、bce、dfg 29.我们知道，对n个关键自序列进行一趟快速排序，要进行n-1次比较，也就是基准和其他n-1个关键字比较。 　　这里要求10次，而71)= 10，这就要求2趟快速排序后，算法结束。所以，列举出来的序列，要求在做partition的时候，正好将序列平分(1)4 1 3 2 6 5 7 　　或 4 1 3 7 6 5 2 或 4 5 3 7 6 1 2 或 4 1 3 5 6 2 7…….(2)自己列吧 :) 　　四、算法阅读题(本大题共4小题，每小题5分，共20分)30.(1)L=(3,7,11,14,15,20,51)(2)L=(4,7,14,20,51)(3)在顺序表L中查找数x, 找到，则删除x，没找到，则在适当的位置插入x，插入后，L依然有序.31.(1)FALSE //初始化为未访问 　　(2)DSFTree(G, p->adjvex);//从相邻结点往下继续深度搜索(3)p = p->next;//下一个未访问的相邻结点 　　32.(1)L = { 0, 1, 2, 3, 4, 5, 6, 7 };(2)5次 　　33.(1)NULL 　　//初始化 　　(2)p->next = H[ j ] //和下面一句完成头插法(3)p = q; 　　//继续遍历L 　　五、算法设计题(本大题10分)34.1) 　　a)*px 有右孩子，则其右孩子为其中序序列中的后继 　　b)*px 无右孩子，从*px开始回溯其祖先结点，找到第1个身份为左孩子的结点，找到，则该结点的父结点为*px的中序序列中的后继。找不到，则无后继。2)BinTNode * fintNext(BinTNode * px){ if(px-> rchild)return px->rchild;//*px 有右孩子 　　BinTNode *q, *qp; 　　q = px;while(qp = q->parent){ //未回溯到根结点 　　if(qp->lchild == q)return qp;//找到1)b)所述结点 　　q = qp;//往上回溯 } 　　return NULL;//未找到 } 　　第四篇：2012广西壮族自治区JAVA版数据结构试题及答案 　　1、下列序列中，执行第一趟快速排序后得到的序列是（A）。A）[d,a,e,d,b]f[h,g] B)[c,e,a,d]f[h,g,b] C)[g,a,e,c,b]f[d,h] D)[a,b,c,d,]f[e,g,h] 　　2、设给定问题的规模为变量n，解决该问题的算法所需时间为Tn=O(f(n)),Tn表示式中记号O表示（A）。 　　A）一个数量级别 B）一个平均值 C）一个最大值 D）一个均方值 　　3、（C）在进行插入操作时，常产生假溢出现象。A）顺序栈 B）循环队列 C）顺序队列 D）链队列 　　4、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a??11为第一个素，其存储地址为1，每素占1个地址空间，则a85的地址为（B）。A）13 B）33 C）18 D）40 　　5、n个顶点的图的最小生成树必定（D），是不正确的描述。A）不唯一 B）权的总和唯一 　　C）不含回路 D）有n条边 　　6、用一维数组A进行顺序存储时，若起始地址为loc(A1)，素长度为c，则A的第i个数组单在存放地址loc(Ai)，等于（B）。A）loc(A1)+i*c B）loc(A1)+(i-1)*c C）loc(A1)+i*c+1 D）loc(A1)+(i+1)*c 　　7、与无向图相关的术语有（C）。A）强连通图 B）入度 C）路径 D）弧 　　8、链式存储的存储结构所占存储空间（A）。 　　A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B）只有一部分，存放结点值 　　C）只有一部分，存储表示结点间关系的指针 　　D）分两部分，一部分存放结点值，另一部分存放结点所占单数 　　9、若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（D）。A）上三角矩阵 B)稀疏矩阵 C)对角矩阵 D)对称矩阵 　　10、在一个具有n个单的顺序栈中，假定以地址低端（即0单）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（C）。 　　A）top不变 B）top=0 C）top–D）top++ 　　11、栈进行插入和删除操作的特点是（A）。A）LIFO B）FIFO C）FCFS D）HPF 　　12、与无向图相关的术语有（C）。A）强连通图 B）入度 C）路径 D）弧 　　13、n个顶点，e条边的有向图的邻接矩阵中非零素有（C）个。A）n B）2e C）e D）n+e 　　14、已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（C）。 　　A)5，4，3，2，1，6 　　B)2，3，5，6，1，4 C)3，2，5，4，1，6 　　D)1，4，6，5，2，3 　　15、在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（B）。 　　A)rear=rear->next;B)front=front->next;C)rear=front->next; 　　D)front=rear->next; 　　第五篇：全国2012年10月数据结构导论试题及答案 　　全国2012年10月高等教育自学考试 　　数据结构导论试题及答案 　　课程代码：02142 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 　　选择题部分 　　注意事项： 　　1.答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 　　2.每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 　　一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的。错选、多选或未选均无分。1.下面几种算法时间复杂度阶数中，值最大的是 　　D A.O(nlog2n)C.O(n) 　　B.O(n2)D.O(2n)2.即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果，这种算法好坏的评价因素称为 C A.正确性 　　C.健壮性 　　B.易读性 　　D.时空性 　　3.设顺序表的长度为100，则在第40个素之后插入一个素所需移动素的个数为 B A.40 C.61 　　B.60 D.100 4.设带头结点的单循环链表的头指针为head，则判断该链表是否为空的条件是 A A.head->next==head C.head!=NULL 　　B.head->next==NULL D.head==NULL 5.在链栈的运算中，不需要判断栈是否为空的是B ．．．A.出栈 　　C.取栈顶素 　　B.进栈 　　D.求链栈的素个数 　　6.一个队列的输入序列是A，B，C，D，则该队列的输出序列是A A.A，B，C，D C.D，C，B，A 　　B.B，C，D，A D.C，D，B，A 7.以行序为主序的二维数组a［3］［5］中，第一个素a［0］［0］的存储地址是100，每个素占2个存储单，则a［1］［2］的存储地址是C A.100 C.114 　　B.108 D.116 8.对任何一棵二叉树T，若叶结点数为5个，则度为2的结点个数为A A.4 C.6 　　9.m个叶结点的哈夫曼树中，其结点总数为D A.m C.2m 　　B.2m+1 D.2m-1 B.5 D.无法确定 　　10.二叉树的中序遍历序列中，结点P排在结点Q之前的条件是A A.在二叉树中P在Q的左边 　　C.在二叉树中P是Q的祖先 　　11.有10个顶点的无向完全图的边数是B A.11 C.55 　　B.45 D.90 　　B.在二叉树中P在Q的右边 　　D.在二叉树中P是Q的子孙 　　12.在带权有向图中求两个结点之间的最短路径可以采用的算法是A A.迪杰斯特拉（Dijkstra）算法 　　C.普里姆（Prim）算法 　　B.克鲁斯卡尔（Kruskal）算法 D.深度优先搜索（DFS）算法 　　13.二分查找（Binary Search）算法的时间复杂度是D A.O（n2） 　　C.O（n） 　　B.O（nlog2n） 　　D.O（log2n） 　　14.在一棵初始时为空的二叉树中，依次插入键值序列50，72，43，85，75，20，38，45，65，60，构造对应的二叉排序树以后，查找素60要进行的比较次数是C A.2 C.4 　　15.快速排序属于B A.插入排序 　　C.选择排序 　　B.交换排序 　　D.归并排序 B.3 D.5 　　非选择题部分 　　注意事项： 　　用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。 　　二、填空题(本大题共13小题，每小题2分，共26分) 　　16.下面算法程序段的时间复杂度为_ for(i=1;inext=__ ___。 　　19.在带有头结点的单链表head中，首结点的指针为_head->next___。20.在栈结构中，允许插入和删除的一端称为__栈顶___。 　　21.C程序中，将对称矩阵A［n］［n］的下三角素压缩存储到n(n+1)/2个素的一维数组M中，设a［i］［j］（i≥j）存放在数组M［k］中，则k的值（用i,j表示）为__ 22.具有64个结点的完全二叉树的深度为___ 7__。 　　23.某二叉树的先序遍历序列为AJKLMNO，中序遍历序列为JLKANMO，则根结点A的右子树中的结点个数为_3___。01124.三个顶点v1,v2,v3的图的邻接矩阵为101，则该图中顶点v2的出度为__2__。 　　000__。 　　25.除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为__简单回路或简单环____。 　　26.在顺序查找、二分查找、散列查找和索引顺序查找四种查找方法中，平均查找长度与素个数没有关系的查找方法是_散列查找____。 　　27.堆排序算法的时间复杂度为__ 　　____。 　　28.如果要将序列{60，18，28，69，99，75，78}建成堆，则只需把60与__ 18____相互交换。 　　三、应用题(本大题共5小题，每小题6分，共30分)29.如题29图所示，在栈的输入端依次输入素A，B，C，试写出在栈的输出端可以得到的所有输出序列，并给出每个序列的操作过程（用push（A）表示A进栈，pop(A)表示A出栈）。 　　题29图 　　答： 　　30.将题30图所示的一棵树转换为对应的二叉树。 　　题30图 　　答： 　　31.已知含五个顶点A，B，C，D，E的连通带权图的邻接矩阵如题31图所示，试画出它所表示的连通带权图及该连通带权图的最小生成树。 　　题31图 　　答： 　　32.题32图所示二叉排序树的各结点的值为1~10中的数，试标出各结点的数值。 　　题32图 　　33.设散列函数H（key）=key mod 11(mod表示求余运算)，给出键值序列为66,13,41,15,44,6,68,17,26,31,39,46,用链地址法解决冲突，试画出相应的散列表，并计算在等概率情况下查找成功时的平均查找长度。 　　四、算法设计题(本大题共2小题，每小题7分，共14分)34.带头结点的单链表的结点结构如下： 　　typedef struct node { int data;struct node *next;}Node,*LinkList;试编写单链表的删除运算算法void DeleteLinklist(LinkList head，int i) 　　35.写出直接选择排序算法。