数据结构复习资料题目和参考答案.docx

1、数据结构复习资料题目和参考答案数据结构复习题及参考答案（抽考其中50%）一、单选题(每小题1分)1下列程序段的时间复杂度为（A）。for(i=0； im； i+) for(j=0； jt； j+) cij=0；for(i=0； im； i+) for(j=0； jt； j+) for(k=0； kn； k+) cij=cij+aik*bkj；(A) O(m*n*t) (B) O(m+n+t) (C) O(m+n*t) (D) O(m*t+n)2下列程序段的时间复杂度为（A）。i=0，s=0； while (snext=p-next；p-next=-s； (B) q-next=s； s-next

2、=p；(C) p-next=s-next；s-next=p； (D) p-next=s；s-next=q；7利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（C）。(A) (B) (C) (D) 8设输入序列为1,2,3,4,5,6，则通过栈的作用后可以得到的输出序列为（B）。(A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1(C) 3，1，2，5，4，6 (D) 1，5，4，6，2，39设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（D）。(A) p-right=s； s-left=p； p-right-left=s

3、； s-right=p-right；(B) s-left=p；s-right=p-right；p-right=s； p-right-left=s；(C) p-right=s； p-right-left=s； s-left=p； s-right=p-right；(D) s-left=p；s-right=p-right；p-right-left=s； p-right=s；10设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A54地址与A00的地址之差为（B）。(A) 10 (B) 19 (C) 28 (D)

4、5511下列各种排序算法中平均时间复杂度为是（D）。(A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 冒泡排序12设一棵m叉树中有个度数为1的结点，个度数为2的结点，个度数为m的结点，则该树中共有（D）个叶子结点。(A) (B) (C) (D)13设输入序列1、2、3、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（C）。(A) n-i (B) n-1-i (C) n+l-i (D) 不能确定14. 二叉排序树中左子树上所有结点的值均（A）根结点的值。(A) (C) = (D) =15设散列表中有m个存储单元，散列函数H(key)= key % p，则p最

5、好选择（B）。(A) 小于等于m的最大奇数 (B) 小于等于m的最大素数(C) 小于等于m的最大偶数 (D) 小于等于m的最大合数16. 设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（D）。(A) 129 (B) 219 (C) 189 (D) 22917设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（C）个。(A) 4 (B) 5 (C) 6 (D) 718. 设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到H

6、ASH表中需要做（D）次线性探测。 (A) n (B) n(n+1) (C) n(n+1)/2 (D) n(n-1)/219.设完全无向图中有n个顶点，则该完全无向图中有（A）条边。(A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) (n-1)/220.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（C）个结点。(A) 2n (B) n+l (C) 2n-1 (D) 2n+l21.设顺序表的长度为n，则顺序查找的平均比较次数为（C）。(A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/222.设一组初始记录关

7、键字的长度为8，则最多经过（B）趟插入排序可以得到有序序列。(A) 6 (B) 7 (C) 8 (D) 923.设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（C）次比较。(A) 1 (B) 2 (C) 3 (D) 424.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（A）。(A) F，H，C，D，P，A，M，Q，R，S，Y，X(B) P，A，C，S，Q，D，F，X，R，H，M，Y(C) A，D，C，R，F，Q，M，S，Y，P，H，X(D) H，C，Q，P，

8、A，M，S，R，D，F，X，Y25.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找(二分法定块，块内顺序查找)，则其平均查找长度为（D）。(A) 6 (B) 11 (C) 5 (D) 6.526.设有向无环图G中的有向边集合E=，则下列属于该有向图G的一种拓扑排序序列的是（A）。(A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，327.设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（A）。(A) 4 (B) 5 (C) 6 (D) 7二、填空题(每小题2分)1 设

9、指针p指向单链表中结点，指针s指向待插入的结点。若在p所指向的结点之前插入s所指结点，则操作序列为：1) s-next=_；2) p-next=s；3) t=p-data；4) p-data=_；5) s-data=t；2. 设需要对5个不同的记录关键字进行排序，则至少需要比较_次，至多需要比较_次。3 设某棵完全二叉树中有100个结点，则该二叉树中有_个叶子结点。4. 快速排序算法的平均时间复杂度为_，直接插入排序算法的平均时间复杂度为_。5 设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储_队列元素。6. 设二

10、叉排序树的高度为h，则在该树中查找关键字key最多需要比较_次。7 对一组初始关键字序列（40，50，95，20，15，70，60，45，10）进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为_，在整个排序过程中最多需要进行_趟排序才可以完成。8. 设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有_个，比较两次查找成功有结点数有_个。9 在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择_排序，如果从节省存储空间的角度来考虑则最好选择_排序。10. 设一棵m叉树的结点数为n，用多重链表表示其存储结构，则该树中有_个空指针域。11 设一组初始记录关键

11、字序列为(20，12，42，31，18，14，28)，则根据这些记录关键字构造的二叉排序树的平均查找长度是_。12. 设指针变量p指向单链表中结点A，则删除结点A的语句序列为：q=p-next；p-data=q-data；p-next=_；delete q；13 设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉树的前序序列为_。14. 数据结构从逻辑上划分四种基本类型：集合、线性表、_和_。15设通信用电文仅有8个字母，频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为_。16. 设无向图G中有n个顶点e条边，则用

12、邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为_；用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为_。17 设一组记录关键字序列为(80，70，33，65，24，56，48)，则用筛选法建成的初始（小根）堆为_。18. 设散列表的长度为8，散列函数H(k)=k % 7，用线性探测法解决冲突，则根据一组初始关键字序列(8，15，16，22，30，32)构造出的散列表的平均查找长度是_。19赋权无向图的最小生成树最终使_达到了最小。20. 设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟冒泡排序结束后的结果为_。21. 设一组初始关键

13、字序列为(38，65，97，76，13，27，10)，则第3趟简单选择排序后的结果为_。22. 设有向图G的有向边的集合E=，则该图的一个拓扑序列为_。三、判断题(每小题1分)1 有向图的邻接表和逆邻接表中表结点的个数不一定相等。( )2 对链表进行插入和删除操作时不必移动链表中结点。( )3 子串“ABC”在主串“AABCABCD”中的位置为2。( )4 若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。( )5 希尔排序算法的时间复杂度为O(n)。( )6 用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关

14、。( )7 中序遍历一棵二叉排序树可以得到一个有序的序列。( )8 入栈操作和入队列操作在链式存储结构上实现不需要考虑溢出的情况。( )9 顺序表查找指的是在顺序存储结构上进行查找。（ ）10堆是完全二叉树，完全二叉树不一定是堆。（ ）11所谓数据的逻辑结构指的是数据之间的逻辑关系。（ ）12O(nlogn)O(n) ( )13设p，q是指针，若p=q，则*p=*q。（ ）14有n个元素依次进栈，则出栈序列有(n-1)/2种。（ ）15在循环队列中，front指向队头元素的前一个位置，rear指向队尾元素的位置，则队满的条件是front=rear。（ ）16使用三元组表存储稀疏矩阵的元素，有时

15、并不能节省存储空间。（ ）17二叉树是度为2的树。（ ）18对任一满二叉树，其分枝数B2(n0-1) ，其中，n0为终端结点数。（ ）19对任意一个图，从某顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点。（ ）20在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条从顶点a到顶点b的弧。（ ）四、算法阅读填空题（每空2分） 1.请在下面对整数排序的快速排序算法中填上正确的语句。void QuickSort(int r , int s, int t) int j=t; int x=rs; i=s; while(ij) while (i & x) j=j-1; if (ij)

16、 ri=rj;i=i+1; while (_) i=i+1; if (ich;if( ch=#) _;else bt=new bitree; bt-data=ch; _;CreateBiTree(bt-rchild);3. 下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。typedef struct node int data; struct node *next; *lklist;void LinkListCreate( _ ,&head ) for (i=1;inext=0;cinp-data;if(i=1) head=q=p;else q-next=p

17、; _; 五、计算题和应用题（共2834分）1设权值集W=1,4,5,16,6,7。按算法构造哈夫曼树（左小右大合并树）,并计算带权路径长度。 （5分） 2、对数据：4,5,3,1,7,按此进入的次序,建立一棵二叉排序树。（5分）3. 给定键值：3,14,8,4,13。构造表长为6，散列函数H(k)=k mod 5，用拉链法解决冲突的散列表，并计算查找成功的平均查找长度。（6分）4计算下列模式串的每一位字符的失效函数值。（4 分）a b a b b a a b 5. 用Dijkstra算法求从源点a到其余各个顶点的最短路径及长度。（6分）6.求出下列图中一个拓扑序列。（2分）7.用PRIM或K

18、ruskal法，求下列图中一个最小生成树。（5分）8.计算下列模式串的每一位字符的失效函数值（最小值为-1）。（5 分）9.顺次扫描数据：7,4,6,12,8,建立一棵二叉排序树。（5分） 10.采用线性探测法解决冲突，用初始关键字：25，32，8，15，12，40 建立长度=8、散列函数为H(k)=k mod 7的散列表，并计算平均查找长度(含成功和不成功查找两种)。(6分) 11.列表用Dijkstra算法计算从源点A到其余各顶点的最短路径及长度。（5分）12.用Prim法或KRUSKAL法，求上小题的图变成无向图（即将边全改为无向边，其他不变）后的一个最小生成树。（5分）13.设权值集W

19、=4，3，8，1，5, 7，按算法路线建立唯一一棵哈夫曼树（而不是从逻辑上满足条件的任意一个,即始终要按左小右大的方案来合并两棵最小树）、树叶所对应符号的哈夫曼编码、整棵树的带权路径长度（8分）六、算法设计题(共15分左右，每小题5分)1 设计计算二叉树中所有结点值之和的算法。（5小分）2 设计将所有奇数移到所有偶数之前的算法。（5小分）3 设计判断单链表中元素是否是递增的算法。（5小分）4 设计在链式存储结构上合并排序的算法。（5小分）5 设计在二叉排序树上查找结点X的算法。（5小分）6 设关键字序列(k1，k2，kn-1)是堆，设计算法将关键字序列(k1，k2，kn-1，x)调整为堆。提示

20、: 设r1n存放关键字序列数据,r1n-1已是大根堆。（5小分）总参考答案一、选择题（每小题1分)）1A 2A 3A 4D 5A 6B 7C 8B 9D 10B 11D 12.D 13C 14A 15B 16D 17C 18D 19A 20C 21C 22B 23C 24. A 25D 26A 27A 二、填空题（每小题2分)1. p-next，s-data2. 4，103. 504. O(nlog2n)，O(n2)5. m-16. h7. 6，88. 1，29. 快速，堆10. n(m-1)+111. 19/712. q-next13. CBDA14.树；图15. 616. O(n2)， O

21、(n+e)17. (24，65，33，80，70，56，48)18. 8/319. 820. (38，13，27，10，65，76，97)21. (10，13，27，76，65，97，38)22. 1,2,4,6,5,3三、判断题（每小题1分)1错 2对 3对 4对 5错 6错 7对 8对 9错 10对11错 12错 13错 14错 15错 16对 17错 18对 19错 20错四、算法阅读填空题（每空2分） 1.请在下面对整数排序的快速排序算法中填上正确的语句。=ij&ri lchild)3. lklist，q=p五、计算题（共2834分）1设权值集W=1,4,5,16,6,7。按算法构造哈

22、夫曼树（左小右大合并树）,并计算带权路径长度。 （5分）带权路径长度WPL=(1+4)*4+(5+6+7)*3+(16)*1=902、对数据：4,5,3,1,7,按此进入的次序,建立一棵二叉排序树。（5分）解：构造过程如下：3. 给定键值：3,14,8,4,13。构造表长为6，散列函数H(k)=k mod 5，用拉链法解决冲突的散列表，并计算查找成功的平均查找长度。（6分）3813144 012345ASLsucc= (2*1+2*2+1*3)/5=9/5 4计算下列模式串的每一位字符的失效函数值(最小值为-1)。（4 分）a b a b b a a b -1 0 0 1 2 0 1 15.

23、用Dijkstra算法求从源点a到其余各个顶点的最短路径及长度。（6分）f2e83312a1 gd1248c16bbcdefg8185,adb3,adc2,adf3,adg5,adb3,adc4,adfe3,adg4,adcb4,adfe3,adg4,adcb4,adfe4,adfe最短路径及长度： a-b: 4,adcba-c: 3,adca-d:1,ada-e: 4,adfea-f: 2,adfa-g: 3,adg6.求出下列图中的一个拓扑序列。（2分）v0,v5,v3,v2,v1,v6,v47.用PRIM或Kruskal法，求下列图中一个最小生成树。（5分）8.计算下列模式串的每一位字符

24、的失效函数值（最小值为-1）。（5 分）1 0 0 1 1 0 0 1 0 0失效函数值: -1 0 0 0 1 1 2 3 4 0 9.顺次扫描数据：7,4,6,12,8,建立一棵二叉排序树。（5分） 7 4 12 6 810.采用线性探测法解决冲突，用初始关键字：25，32，8，15，12，40 建立长度=8、散列函数为H(k)=k mod 7的散列表，并计算平均查找长度(含成功和不成功查找两种)。(6分) 0123456781525321240要查找成功时比较次数 1 2 1 2 2 3 ASLsucc=(1+2+1+2+2+3)/6=11/6 ASLunsucc=(2+1+4+3+2+1)/8=13/811.列表用Dijkstra算法计算从源点A到其余各顶点的最短路径及长度。（5分）BBCDEF5294,ACB8,ACD3,ACE6,ACF4,ACB6,ACED5,ACEF6,ACED5,ACEF6,ACEDA-B:4,ACB;A-C:2,AC;A-D:6,ACED