发布时间 : 星期三 文章数据结构复习题及参考答案更新完毕开始阅读07758f7bc850ad02df804100
52.快速排序在最坏情况下的时间复杂度为【 】。
2
A.O(log2n) B.O(nlog2n) C.O(n) D.O(n) 53.从二叉搜索树中查找一个元素时，其时间复杂度大致为【 】。
2
A.O(n) B.O(1) C.O(log2n) D.O(n)
54.设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为【 】。
2
A.O(log2n) B.O(1) C.O(n) D.O(n)
55.设一棵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
56.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为【 】。 A. SA+141 B. SA+144 C. SA+222 D. SA+225
57.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为【 】。 A.uwvts B.vwuts C.wuvts D.wutsv 58.深度为5的二叉树至多有【 】个结点。
A. 16 B. 32 C. 31 D. 10 59.在一个无向图中，所有顶点的度数之和等于所有边数的【 】倍。
A. 1/2 B. 1 C. 2 D. 4
60.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为【 】。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 61.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为【 】。
2
A．O（n） B. O(nlog2n) C. O(n) D. O(log2n) 62.下述几种排序方法中，要求内存量最大的是【 】。
A.插入排序 B.选择排序 C.快速排序 D.归并排序
63.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为【 】。
A.希尔排序 B.起泡排序 C.插入排序 D.选择排序
64.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为【 】的值除以9。
A. 20 B. 18 C. 25 D. 22 65.在有向图中每个顶点的度等于该顶点的【 】。
A.入度 B.出度 C.入度与出度之和 D.入度与出度之差 66.在基于排序码比较的排序算法中，【 】算法的最坏情况下的时间复杂度不高于O(n10g2n)。 A.起泡排序 B.希尔排序 C.归并排序 D.快速排序 67.当α的值较小时，散列存储通常比其他存储方式具有【 】的查找速度。 A.较慢 B.较快 C.相同 D.不清楚
68.设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列表项应能够至少容纳【 】个表项。
(设搜索成功的平均搜索长度为Snl＝{1+l／(1一α)}／2，其中α为装填因子) A. 400 B. 526 C. 624 D. 676 69.堆是一个键值序列{k1,k2,?..kn},对I=1,2,?.|_n/2_|,满足【 】 A. ki≤k2i≤k2i+1 B. ki C. ki≤k2i且ki≤k2i+1(2i+1≤n) D. ki≤k2i 或ki≤k2i+1(2i+1≤n) 70.若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上【 】 A.操作的有限集合 B.映象的有限集合 C.类型的有限集合 D.关系的有限集合 71.下列图示的顺序存储结构表示的二叉树是【 】 第5页共22页 72.由同一关键字集合构造的各棵二叉排序树【 】 A.其形态不一定相同，但平均查找长度相同 B.其形态不一定相同，平均查找长度也不一定相同 C.其形态均相同，但平均查找长度不一定相同 D.其形态均相同，平均查找长度也都相同 73.ISAM文件和VSAM文件的区别之一是【 】 A.前者是索引顺序文件，后者是索引非顺序文件 B.前者只能进行顺序存取，后者只能进行随机存取 C.前者建立静态索引结构，后者建立动态索引结构 D.前者的存储介质是磁盘，后者的存储介质不是磁盘 74.下列描述中正确的是【 】 A.线性表的逻辑顺序与存储顺序总是一致的 B.每种数据结构都具备三个基本运算：插入、删除和查找 C.数据结构实质上包括逻辑结构和存储结构两方面的内容 D.选择合适的数据结构是解决应用问题的关键步骤 75.下面程序段的时间复杂度是【 】 I=s=0 While(s A.O(1) B.O(n) C.O(log2n) D.O(n^2) 三、计算与算法应用题： 1.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 按照普里姆算法从顶点1出发得到最小生成树，试写出在最小生成树中依次得到的各条边。 2.一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。 先序序列： B F ICEH G 中序序列：D KFIA EJC 后序序列： K FBHJ G A 第6页共22页 3.画出下列树对应的二叉树，并写出其先根遍历序列： A B C D F E G 4.将关键字序列为{54，29，37，86，71，91，8，31，44，26}进行归并排序，写出各趟详细过程。 5.试列出如下图中全部可能的拓扑排序序列。 123456 6.设某通信系统使用A，B ，C，D，E，F，G，H八个字符，他们出现的概率w={5，29，7，8，14，23，3，11}，试构造对应的哈夫曼树（请按左子树根结点的权小于右子树树根结点的权的次序构造）。 7.给定表（119，14，22，1，66，21，83，27，56，13，10）,请按表中元素的顺序构造一棵平衡二叉树，并求其在等概率情况下查找成功的平均长度。 8.已知一个有向图的顶点集V和边集G分别为：V={a,b,c,d,e,f,g,h} E={ 假定该图采用邻接矩阵表示，则分别写出从顶点a出发进行深度优先搜索遍历和广度优先搜索遍历得到的顶点序列。 9.设散列表的长度为13，散列函数为H（h）= k，给定的关键码序列为19，14，23，01，68，20，84，27。试画出用线性探查法解决冲突时所构成的散列表。 0 1 2 3 4 5 6 7 8 9 10 11 12 10.对7个关键字进行快速排序，在最好的情况下仅需进行10次关键字的比较。 (1)假设关键字集合为{1,2,3,4,5,6,7}，试举出能达到上述结果的初始关键字序列； (2)对所举序列进行快速排序，写出排序过程。 11.如图所示二叉树，回答下列问题。 12.画出在一个初始为空的AVL树中依次插入3,1,4,6,9,8,5,7时每一插入后AVL树的形态。若做了某种旋转，说明旋转的类型。然后，给出在这棵插入后得到的AVL树中删去根结点后的结果。 13.已知一组记录的排序码为（ 46 ， 79 ， 56 ， 38 ， 40 ， 80 ， 95 ， 24 ），写出对其进行快速排序的每一次划分结果。 14.一个线性表为 B= （ 12 ， 23 ， 45 ， 57 ， 20 ， 03 ， 78 ， 31 ， 15 ， 36 ），设散列表为 HT[0..12] ，散列函数为 H （ key ） = key % 13 并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。 15.已知一棵二叉树的前序遍历的结果序列是 ABECDFGHIJ ，中序遍历的结果是 EBCDAFHIGJ ，试写出这 第7页共22页 棵二叉树的后序遍历结果。 16.假定对线性表(38，25，74，52，48，65，36)进行散列存储，采用H(K)=K％9作为散列函数，若分别采用线性探查法和链接法处理冲突，则计算对应的平均查找长度。 四、阅读下列算法，分析它的作用： 1.int AA(LNode *HL , ElemType x) { int n=0; LNode *p=HL; while (p!=NULL) { if (p->data= =x) n++; p=p->next; } return n; } 对于结点类型为LNode的单链表，以上算法的功能为： 2.int AA(LNode *HL , ElemType x) { int n=0; LNode *p=HL; while (p!=NULL) { if (p->data= =x) n++; p=p->next; } return n; } 对于结点类型为LNode的单链表，以上算法的功能为： 3.假定从键盘上输入一批整数，依次为：78 63 45 30 91 34 # include < iostream.h> # include < stdlib.h > const int stackmaxsize = 30; typedef int elemtype; struct stack { elemtype stack [stackmaxsize]; int top; }; # include “stack.h” void main 【 】 { stack a; initstack(a); int x; cin >>x; while (x! = -1) { push (a, x ); cin >>x; 第8页共22页 –1，请写出输出结果。