2018年_2018数据结构专科复习资料

1、数据结构课程复习资料一、填空题：1. 设需要对5个不同的记录关键字进行排序，则至少需要比较J次，至多需要比较10次。2. 设二叉排序树的高度为h,则在该树中查找关键字key最多需要比较n次。3. 设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有工个，比较两次查找成功有结点数有2个。4. 数据结构从虱辑上划分为三种基本类型：线性结构、树型结构和图型结构。5. 在一个具有n个顶点的无向完全图中，包含有n(n-1)/2条边，在一个具有n个顶点的有向完全图中，包含有n(n-1)条边。6. 向一棵B列插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度增加。7. 在堆排序的过

2、程中，对任一分支结点进行筛运算的时间复杂度为O(log2n),整个堆排序过程的时间复杂度为O(nlog2n)。8. 在快速排序、堆排序、归并排序中，归并排序是稳定的。9. 在有n个叶子结点的哈夫曼树中，总结点数是n-1。10. 一棵树T采用二叉链表存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定左,右子树空。11. 已知数组A1010为对称矩阵，其中每个元素占5个单元。现将其下三角部分按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A5,6对应的地址是1225。12. 在有n个结点的无向图中，其边数最多为n(n-1)/2。13. 取出广义表A=(x,(a,b,

3、c,d)中原子x的函数是head(A)。14. 对矩阵采用压缩存储是为了节省空间。15. 带头结点的双循环链表L为空表的条件是L->next=L->prior或L->next=L。16. 设线性表中元素的类型是实型，其首地址为1024,则线性表中第6个元素的存储位置是1044。17. 对于顺序存储的栈，因为栈的空间是有限的，在进行入栈(插入)运算时，可能发生栈的上溢,在进行出栈(删除)运算时,可能发生栈的下溢。18. 在双向链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。19. 折半查找的存储结构仅限于顺

4、序存储结构，且是有序白对于一个顺序存储的线性表，在表头插入元素的时间复杂度为On),在表尾插入元素的时间复杂度为O(1)Q在稀疏距阵所对应的三元组线形表中，每个三元组元素按行号为主序,列号为辅序的次序排列。20. 中缀表达示3+X*(2.4/5-6)所对应的后缀表达示为3x2.45/6*+。21. 在一棵高度为h的3叉树中，最多含有(3h-1)/2结点。22. 分析下面算法(程序段)，给出最大语句频度愁，该算法的时间复杂度是O(n3)。for(i=0;i<n;i+)for(j=0;j<n;j+)Aij=0；23. 空串是零个字符的串，其长度等于零。_一个图的邻接矩阵表示法是唯一的,

5、而邻接表表示法是不唯一的。24. 在一个单链表中p所指结点之前插入一个s(值为e)所指结点时，可执行如下操作：25. q=head;while(q->next!=p)q=q->next;s=newNode;s->data=e;q->next=sj/填空s->next=p;/填空在一个单链表中删除p所指结点的后继结点时，应执行以下操作：26. q=p->next;p->next=q->next;/填空deleteq;/填空两个串相等的充分必要条件是两个串的长度相等且对应位置的字符相同。27. 二维数组A1020采用列序为主方式存储，每个元素占一个存

6、储单元并且A00的存储地址是200,则A612的地址是200+(6*20+12)=326。28. 二维数组A10.205.10采用行序为主方式存储，每个元素占4个存储单元，并且A105的存储地址是1000,则A189的地址是1000+(18-10)*6+(9-5)*4=1208。29. 求下列广义表操作的结果：30. GetTailGetHead(a,b),(c,d);(b)GetTailGetHeadGetTail(a,b),(c,d)(d)已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是求矩阵第i列非零元素之和。31. 已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法

7、是将矩阵第i行全部置为零。32. 在利用快速排序方法对一组记录(54,38,96,23,15,72,60,45,83)进行快速排序时，递归调用而使用的栈所能达到的最大深度为2,共需递归调用的次数为4,其中第二次递归调用是对(23,38,15)组记录进行快速排序。33. 在堆排序，快速排序和归并排序中，若只从存储空间考虑，则应首先选取堆排序方法，其次选取快速排序方法,最后选取归并排序方法;若只从排序结果的稳定性考虑，则应选取归并排序方法；若只从石情况下排序最快考虑，则应选取快速排序方法;若只从最坏情况下排序最快并且要节省内存考虑,则应选取堆排序方法。34. 称算法的时间复杂度为O(f(n)，其含

8、义是指算法的执行时间和f(n)的数量级相同。35. 在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为O(n)。36. 假设为循环队列分配的向量空间为Q20,若队列的长度和队头指针值分别为13和17,则当前尾指针的值为0。37. 对于栈只能在栈顶插入和删除元素。38. 设有一个顺序栈S,元素sl,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s2,s3,s4,s6,s5,sl,贝U顺序栈的容量至少应为3_。39. 数据结构一般包括三个方面内容：数据的逻辑结构,数据的存储结构及数据的运算。n/2个结点。44. 在包含n个结点的顺序表上做等概率插入运算，平均要移动4

9、5. 队列的特性是先进先出。46. 已知二叉树中叶子数为30,仅有一个孩子的结点数为20,则总结点数为47. 虫序遍历二叉排序树中的结点可以得到一个递增的关键字序列(选填“先序”48. n个节点的连通图至少有49. 在堆排序和快速排序中，50. 带有一个头结点的单链表51. 设一组初始关键字序列为10,13,27,76,65,97,3879o、“中序”或“后序”)n-1条边。如果从平均情况下排序的速度最快的角度来考虑，head为空的条件是(假设指针域的名称为next)head->next=NULL。(38,65,97,76,13,27,10),则第3趟简单选择排序后的结果为应最好选择快速

10、排序排序。52. 在拓扑排序中，拓扑序列的第一个顶点必定是53. 数据的逻辑结构分为两大类，它们是线性结构和54. 在单链表中(假设结点指针域名称为入度为零的顶点。非线性结构。next),删除指针P所指结点的后继结点的语句是p->next=p->next->next。55. 已知循环队列用数组datan存储元素值，用front,rear分别作为头尾指针，则当前元素个数为(rear-front+n)%n。56. 若n为主串长，m为子串长，则串的朴素匹配算法最坏的情况下需要比较字符的总次数(n-m+1)xm广义表(a),(b),j,(d)的表尾是(b),j,(d)。57. 已知二

11、叉树有61个叶子节点，且仅有一个孩子的节点数为45,贝U总节点数为166。59.解决计算机与打印机之间速度不匹配问题，须要设置一个数据缓冲区，应是一个队列结构。、单项选择题:队列的特点是A.先进后出B.先进先出有n个记录的文件，如关键字位数为A.nB.dC.rC.d,基数为D.n-d3. 在二叉树结点的先序序列、中序序列和后序序列中，A.都不相同B.C.先序和中序相同，而与后序不同4. 设有198个初始归并段，如采用A.12B.13C.14B任意位置进出D.r,则基数排序共要进行(前面都不正确)遍分配与收集。D.所有叶子结点的先后顺序完全相同中序和后序相同，而与先序不同K-路平衡归并三遍完成排

12、序，则K值最大为D.15下面关于广义表的叙述中，不正确的是A.广义表可以是一个多层次的结构C.广义表可以被其他广义表所共享B.D.6. 设二叉树根结点的层次为0,一棵深度(高度)c个结点，下列关系式不正确的是A.f>=cB.c>fC.f=2从L=(apple,pear),(orange,banana)A.head(tail(L)C.tail(head(tail(L)7. 下列文件的物理结构中，A.顺序结构B.B广义表至少有一个元素广义表可以是一个递归表为k的满二叉树和同样深度完全二叉树各有Bk+1-aD.c>s中，取出banana元素的表达式为B.head(head(tail

13、(L)D.head(tail(head(tail(L)不利于文件长度动态增长的文件物理结构是链接结构C.索引结构Ck-1D个结点和D.HashD.A结构9. 在数据结构中，数据元素可由A.实体B.域C.数据项对于有n个顶点的有向图，由弗洛伊德(FloyD算法求每一对顶之间的最短路径的时间复杂度是A.O(1)B.O(n)C.O(n)D.O(n对n个记录的文件进行快速排序，所需要的辅助存储空间为A.O(1)B.O哈夫曼树中一定不存在A.度为0的结点B.度为1的结点下述哪一条是顺序存储方式的优点？A.存储密度大B.C.获取符合某种条件的元素方便D.(log2n)C.OC.(n)B度为2的结点D.OD

14、.A插入和删除运算方便查找运算速度快字段3)B(n2)带权的结点14. 有一个二维数组Amn，假设A00存放位置在600(10),A33存放位置在678(10)占一个空间，问A23(10)存放在什么位置？(脚注(10)表示用10进制表示，m>315. A.658B.648C.633D.653下列关于二叉树遍历的叙述中，正确的是AA. 若一个叶子是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点若一个结点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点每个元素D若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点

15、若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点第K层二叉树的结点总数最多为A.2k-1B.2k+1C.2K-1线性表进行二分法查找，其前提条件是A.线性表以链接方式存储，并且按关键码值排好序AD.2k-1B. 线性表以顺序方式存储，并且按关键码值的检索频率排好序线性表以顺序方式存储，并且按关键码值排好序线性表以链接方式存储，并且按关键码值的检索频率排好序18.n个记录进行堆排序，所需要的辅助存储空间为B.O(n)C.O(1)34,77,25,64,49,20,14)0的元素有()个。19. B.2C.3A.O(1og2n)线性表(7,20. 散列地址为A.1D.

16、4D.O(n进行散列存储时，若选用DC2)H(Q=K%7作为散列函数，则下列关于数据结构的叙述中，正确的是21. A.数组是不同类型值的集合C.树是一种线性结构以下数据结构中哪一个是线性结构？A.有向图B.队列D.B.22. B线索二叉树D.B在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由语句序列。D23. A.p=q;p->next=q;B.p->next=q;q->next=p;C.p->next=q->next;p=q;D.q->next=p->next;p->next=q;()不是队列的基本运算。A.在队列第i个元素之后插

17、入一个元素C.判断一个队列是否为空D.24. 若已知一个栈的入栈序列是1,2,3,，为A.i栈的特点是A.先进先出设有两个串A.连接C.D.)<B.n,递归算法的程序结构比迭代算法的程序结构更为精炼用一维数组存储一棵完全二叉树是有效的存储方法27. 树q指向的结点，则执行如下()A从队头删除一个元素读取队头元素的值p1,p2,其输出序列为Cp3,，pn,若p1=n，贝UpiB.n=iC.n-i+1(B),队列的特点是(AB.先进后出p和q,求q在p中首次出现的位置的运算称作B.模式匹配C.求子串的长度为3个字节，行下标二维数组A中，每个元素Aij28. 址SA开始连续存放在存储器内，该数

18、组按列存放时，元素A.SA+141B.SA+180C.SA+222某二叉树的前序遍历结点访问顺序是abdgcefh29. 的结点访问顺序是A.bdgcefhaB.gdbecfha在一非空二叉树的中序遍历序列中，30. A.只有右子树上的所有结点C.只有左子树上的部分结点具有6个顶点的无向图至少应有(A.5B.6C.7二分查找和二叉排序树的时间性能A.相同B.不相同采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)在待排序的兀素序列基本有序的前提下，效率最高的排序方法是A.插入排序B.选择排序C.31. 下述几种排

19、序方法中，要求内存量最大的是A.插入排序B.选择排序C.C.bdgaechf根结点的右边B.D.)条边才能确保TED.8不确定B求串长D.i从0到7,列下标jA47的起始地址为D.SA+225,中序遍历的结点访问顺序是DD.gdbehfca只有右子树上的部分结点只有左子树上的所有结点旦一个连通图。快速排序快速排序D.DD.从0到9,从首地Bdgbaechf,则其后序遍历A归并排序归并排序35. 设有两个串p和q,求q在p中首次出现的位置的运算称作BA.连接B.模式匹配C.求子串D.求串长二维数组A中，每个元素Aij的长度为3个字节，行下标i从0到7,列下标j从0到9,从首地36. 址SA开始连

20、续存放在存储器内，该数组按列存放时，元素A47的起始地址为BA.SA+141B.SA+180C.SA+222某二叉树的前序遍历结点访问顺序是abdgcefh37. 的结点访问顺序是A.bdgcefhaB.gdbecfha在一非空二叉树的中序遍历序列中，38. A.只有右子树上的所有结点C.只有左子树上的部分结点具有6个顶点的无向图至少应有(A.5B.6C.7二分查找和二叉排序树的时间性能A.相同B.不相同C.bdgaechf根结点的右边B.D.D.SA+225,中序遍历的结点访问顺序是DD.gdbehfcadgbaechf,则其后序遍历A只有右子树上的部分结点只有左子树上的所有结点)条边才能确

21、保是一个连通图。D.8C.采用二分查找方法查找长度为n的线性表时，A.O(n2)B.O(nlog2n)C.O(n)B可能相同D.每个元素的平均查找长度为42. D.O(log2n)在待排序的兀素序列基本有序的前提下，效率最高的排序方法是A.插入排序B.选择排序C.快速排序下面的序列中(43. A.1,2,8,5,3,9,10,4C.9,8,7,6,4,8,2,1对一个算法的评价，A.健壮性和可读性在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，44. A.p->next=HL->next;HL->next=pB.p->next=HL;HL=pC.p-&g

22、t;next=HL;p=HLD.HL=p;p->next=HL对线性表，在下列哪种情况下应当采用链表表示？A.经常需要随机地存取元素B.45. C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变一个栈的输入序列为123,则下列序列中不可能是栈的输出序列的是A.231B.321C.312D.123每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是A.冒泡排序B.简单选择排序C.希尔排序D.46. 采用开放定址法处理散列表的冲突时，其平均查找长度A.低于链接法处理冲突C.与链接法处理冲突相同若需要利用形参直接访问实参时，A.值B.函数在稀疏矩阵的带行指针向量的链接存储中

23、，A.行号B.列号快速排序在最坏情况下的时间复杂度为A.O(log2n)B.O(nlog2n)B.选择排序)是大顶堆。B.1,5,10,6,7,8,9,2D.9,8,7,6,5,4,3,1不包括如下()方面的内容。B.并行性C.正确性D.D.不确定BA归并排序B时空复杂度则执行B经常需要进行插入和删除操作B.高于链接法处理冲突D.高于二分查找应将形参变量说明为()参数。C.指针D.每个单链表中的结点都具有相同的C.元素值D.DB:直接插入排序BD引用A非零元素个数C.O(n)从二叉搜索树中查找一个元素时，其时间复杂度大致为A.O(n)B.O(1)设一个有序的单链表中有D.O(n2n)D.O(n

24、C2)C.O(logn个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为DA.O(log2n)B.O(1)C.O(n2)D.O(n)55.设一棵m叉树中度数为0的结点数为Nd,度数为1的结点数为N,，度数为m的结点数为Nm则Nd=A.Ni+N2+NmB.l+N2+2N+3N4+(m-1)NmC.N2+2N3+3N+(m-1)NmD.2Nl+3N2+(m+1)Nm二维数组A中，每个元素A的长度为3个字节，行下标i从0到7,列下标j从0到开始连续存放在存储器内，该数组按行存放时，数组元素A74的起始地址为A.SA+141B.SA+144C.SA+222D.SA+225如果

25、某二叉树的前根次序遍历结果为stuwv,中序遍历为uwtvs,那么该二叉树的后序为C.wuvtsD.wutsv)个结点。C.31D.109,从首地址CSAA.uwvtsB.vwuts深度为5的二叉树至多有(A.16B.32在一个无向图中，所有顶点的度数之和等于所有边数的(A.1/2B.1采用顺序查找方法查找长度为A.nB.n/2采用二分查找方法查找长度为A.O(n2)B.O(nlog)倍。62. C.2D.4n的线性表时，每个元素的平均查找长度为C.(n+1)/2D.(n-1)/2n的线性表时，每个元素的平均查找长度为D.O(log2n)C.O(n)下述几种排序方法中，要求内存量最大的是A.插

26、入排序B.选择排序C.排序方法中，从未排序序列中依次取出元素与已排序序列称为快速排序(初始时为空)2n)64. 入已排序序列的正确位置上的方法，A.希尔排序对于长度为值除以9。A.20D.中的元素进行比较，将其放D.归并排序B.起泡排序C.9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为(插入排序选择排序B.18C.25D.22在有向图中每个顶点的度等于该顶点的A.入度B.出度在基于排序码比较的排序算法中，(A.起泡排序B.希尔排序C入度与出度之和D.C.算法的最坏情况下的时间复杂度不高于C.入度与出度之差O(n10g2n)。快速排序B不清楚归并排序D.)的查找速度。相同

27、D.67. 当a的值较小时，散列存储通常比其他存储方式具有(A.较慢设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5,则散列表项应能够至少容纳(68. (设搜索成功的平均搜索长度为A.400B.526堆是一个键值序列(k1,k2,.k69. A.ki<k2i<k2i+1C.kiVk2i且kivk2i+1(2i+1<n)若将数据结构形式定义为二元组A.操作的有限集合B.B.较快C.)个表项。a)/2,其中a为装填因子)D.6761=1,2,.|_n/2_|,满足Snl=(1+l/(1C.624n,对B.kD.kR),其中

28、(K,映象的有限集合71.下列图示的顺序存储结构表示的二叉树是i<k2i+1<k2ii<k2i或ki<k2i+1(2i+1<n)K是数据元素的有限集合，则R是K上C.类型的有限集合D.关系的有限集合C12345678101112A.ABEDC.ED72.由同一关键字集合构造的各棵二叉排序树A.其形态不一定相同，但平均查找长度相同C.其形态均相同，但平均查找长度不一定相同73.ISAM文件和VSA吸件的区别之一是A. 前者是索引顺序文件，后者是索引非顺序文件B. 前者只能进行顺序存取，74. 前者建立静态索引结构，前者的存储介质是磁盘，下列描述中正确的是A. 线性表

29、的逻辑顺序与存储顺序总是一致的B. 每种数据结构都具备三个基本运算：插入、删除和查找75. 数据结构实质上包括逻辑结构和存储结构两方面的内容选择合适的数据结构是解决应用问题的关键步骤下面程序段的时间复杂度是I=s=0While(s<n)(I+；s+=I;A.O(1)如果只想得到A.起泡排序B.D.后者只能进行随机存取后者建立动态索引结构后者的存储介质不是磁盘B.O(n)C.O(log2n)1024个元素组成的序列中的前B.快速排序C.77. 算法分析的目的是A.辨别数据结构的合理性C.研究算法中输入与输出的关系B.D.其形态不一定相同，平均查找长度也不一定相同其形态均相同，平均查找长度也

30、都相同CD.O(nA2)5个最小元素，堆排序B那么用(D.方法最快。A直接选择排序评价算法的效率鉴别算法的可读性78. 在线性表的下列运算中，不改变数据元素之间结构关系的运算是A.插入B.删除C.定位若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行，A.3,C.1,设串C排序2,2,sl=6,1,4,5B.55,3,4,6D.3"DataStructureswithJava",s2=D.则可能出现的出栈序列为2,3,1,6,it,6,4,4,2,则子串定位函数index(s1,s2)的值为A81. A.15B.16C.17D.18一个顺序存储的线性表的第一个元素

31、的存储地址是址是A.108从一个具有个结点。A.n100,每个元素的长度为4,则第4个元素的存储地BB.112C.116D.120n个结点的单链表中查找其值等于x的结点，在查找成功的情况下，平均需要比较（CD.（n-1）/2各叶子之间的相对次序关系C.B.n/2C.(n+1)/2在任意一棵二叉树的前序序列和后序序列中，A.不一定相同B.互为逆序高度为5的二叉树至多有结点数为A.63B.32C.24都不相同D.85. AD都相同D.64若用邻接矩阵表示一个有向图，则其中每一列包含的A.图中每个顶点的出度B.C.图中弧的条数D.86. 图的邻接矩阵表示法一般不太适用于表示A.无向图B.有向图C.8

32、7. 循环队列是空队列的条件是A.Q->rear=Q->frontC.Q->rear=0设有一广义表E=（a,b,（c,d）A.2B.3某二叉树的前序遍历序列为1的个数为图中每个顶点的入度图中连通分量的数目AD.稀疏图稠密图BB.(Q->rear+1)%maxsize=Q->frontD.Q->front=0)，其长度为C.4D.590. ABDEFC中序遍历序列为DBEFAC则后序遍历序列为A.DFEBCAB.DBECFAC.BDAECFD.DBEFCA下列（）不是利用查找表中数据元素的关系进行查找的方法。91. A.有序表的查找B.二叉排序树的查找C.平

33、衡二叉树下述几种排序方法中，要求内存量最大的是A.插入排序B.快速排序C.归并排序在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（A.1/2B.1C.2D.4在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行92. A.p->next=HL->next;HL->next=pB.p->next=HL;HL=pC.p->next=HL;p=HLD.HL=p;p->next=HL对线性表，在下列哪种情况下应当采用链表表示？B93. A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中

34、元素的个数不变一个栈的输入序列为123,则下列序列中不可能是栈的输出序列的是A.231B.321C.312D.123每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是A.冒泡排序B.简单选择排序C.希尔排序采用开放定址法处理散列表的冲突时，其平均查找长度94. A.低于链接法处理冲突C.与链接法处理冲突相同若需要利用形参直接访问实参时，A.值B.函数D.BD.D.B.高于链接法处理冲突D.高于二分查找应将形参变量说明为（）参数。C.指针D.99. 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的A.行号B.列号C.元素值D.C散列查找选择排序）倍。B直接插入排序

35、BD引用A非零元素个数100. 快速排序在最坏情况下的时间复杂度为A.O(log2n)B.O(nlog2n)C.O(n)从二叉搜索树中查找一个元素时，其时间复杂度大致为A.O(n)B.O(1)设一个有序的单链表中有时间复杂度为A.O(log2n)B.O(1)设一棵m叉树中度数为D.O(n2n)CD.O(n2)2)C.O(logn个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的DC.O(n2)D.O(n)0的结点数为N0,度数为1的结点数为Nl,，度数为m的结点数为Nm则N0=104. A.Ni+N2+NmB.l+N2+2N+3N+(m-1)NmC.N2+2N3+3M+(m-1)

36、NmD.2Nl+3N2+(m+1)Nm设有序表中有1000个元素，则用二分查找查找元素X最多需要比较()次。BA.25B.10C.7D.1设连通图G中的边集E=(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c),则从顶点a出发可以得到一种深度优先遍历的顶点序列为BA.abedfcB.acfebdC.aebdfcD.aedfcb拓扑排序运算只能用于CA.带权有向图B.连通无向图C.有向无环图D.无向图在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是BA.O(1)B.O(n)C.O(n2)D.O(nlogn)三、计算与算法应用题：1. 已知

37、一个图的顶点集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. 一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。先序序列：_BFICEHG_中序序列：d_kfiaEJC_后序序列：KFBHJGA3. 画出下列树对应的二叉树，并写出其先根遍历序列:4.将关键字序列为54,29,

38、37,86,71,91,8,31,44,26进行归并排序，写出各趟详细过程。5. 试列出如下图中全部可能的拓扑排序序列。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,hE=<a,b>,<a,c

39、>,<b,f>,<c,d>,<c,e>,<d,a>,<d,f>,<d,g>,<e,g>,<f,h>假定该图采用邻接矩阵表示，则分别写出从顶点a出发进行深度优先搜索遍历和广度优先搜索遍历得到的顶点序列。9. 设散列表的长度为13,散列函数为H(h)=k%13,给定的关键码序列为19,14,23,01,68,20,84,27。试画出用线性探查法解决冲突时所构成的散列表。012345678910111210. 对7个关键字进行快速排序，在最好的情况下仅需进行10次关键字的比较。(1) 假设关键字集合

40、为1,2,3,4,5,6,7，试举出能达到上述结果的初始关键字序列;(2) 对所举序列进行快速排序，写出排序过程。3,1,4,6,9,8,5,7时每一插入后AVL树的形态。若做了某种11. 如图所示二叉树，回答下列问题。12. <1)其申序髯历序列(2>(3>其后序AVL树中删去根结点后的结果。,40,80,95,24),写出对其进行快画出在一个初始为空的AVL树中依次插入旋转，说明旋转的类型。然后，给出在这棵插入后得到的已知一组记录的排序码为(46,79,56,38速排序的每一次划分结果。14. 一个线性表为B=(12,23,45,57,20HT0.12，散列函数为H(ke

41、y)=key%13算等概率情况下查找成功的平均查找长度。,03,78,31,15,36),设散列表为并用线性探查法解决冲突，请画出散列表，"丁15. 已知一棵二叉树的前序遍历的结果序列是ABECDFGHIJ，中序遍历的结果是EBCDAFHIGJ,试写出这棵二叉树的后序遍历结果。16. 假定对线性表(38,25,74,52,48,65,36)进行散列存储，采用H(K)=K%9作为散列函数，若分别采用线性探查法和链接法处理冲突，则计算对应的平均查找长度。17. 已知哈希表地址空间为0.8，哈希函数为H(key)=key%7,采用线性探测再散列处理冲突，将数据序列100,20,21,35,

42、3,78,99,45依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查找长度。18. 试画出下面带权无向图的一棵最小生成树。19. 已知关键字序列为：03,87,12,61,98,70,61*,97,27,53,42,56,77,请采用希尔(Shell)排序法对该序列作非递减排序.按5,3,1分组，写出下列标明的趟的结果。初始03,87,12,61,98,70,97,27,53,42,56,77第一趟第二趟每三趟四、阅读下列算法，分析它的作用：1.intAA(LNode*HL,ElemTypex)intn=0;LNode*p=HL;while(p!=NULL)if(p->

43、data=x)n+;p=p->next;returnn;对于结点类型为LNode的单链表，以上算法的功能为：2.intAA(LNode*HL,ElemTypex)intn=0;LNode*p=HL;while(p!=NULL)(if(p->data=x)n+;p=p->next;returnn;对于结点类型为LNode的单链表，以上算法的功能为:-1,请写出输出结果。假定从键盘上输入一批整数，依次为：786345309134include<iostream.h>include<stdlib.h>constintstackmaxsize=30;typed

44、efintelemtype;structstack(elemtypestackstackmaxsize;inttop;#include"stack.h”voidmain【】(stacka;initstack(a);intx;cin>>x;while(x!=-1)(push(a,x);cin>>x;while(!stackempty(a)cout<<pop(a)<<”;cout<<end1;该算法的输出结果为：。3. 读下述算法，说明本算法完成什么功能。template<calsstype>voidBinTree&

45、lt;Type>unknown(BinTreeNode<Type>*t)(BinTreeNode<Type>*p=t,*temp;if(p!=NULL)(temp=prleftchild;prleftchild=prrightchild;prightchild=temp;unknown(pleftchild);undnown(prightchild);该算法的功能是:5.阅读下列算法，说明该算法的作用。voidSqstack:push(ElemTypex)(if(top=MAX-1)cout<<"n满！"；else(top+;ele

46、mtop=x;/pushI/类定义1constintMAX=20;ItypedefcharElemType;IclassSqstack1(private:-ElemTypeelemMAX;iinttop;1public:ISqstack()top=0;IElemTypepop();1voidpush(ElemTypex);i1;6.有如下图所示单链表，经过图示。voidLink:output()p=Head->next;while(p!=NULL)cout<<"np=p->next;/outputoutput）算法处理后，单链表发生了什么变化？画出处理后的单链

47、表data="<<p->data;7.读下述算法，说明本算法完成什么功能。voidBtree:inordern(bnode*p,int&n)if(p!=NULL)inordern(p->lch,n);if(p->lch=NULL&&p->rch=NULL)n+;inordern(p->rch,n);/inordern1structSnode/II构ichardata;；Snode*next;:;IclassLink/I,.iprivate:iSnode*Head;1public:ILink()Head=NULL;ivo

48、idcreat();1voidoutput();I:/结点结链表类8.voidAD(Lnode*&HL)Insert(HL,30);Insert(HL,50);Delete(HL,26);Delete(HL,55);10.阅读下列算法，说明该算法的作用。ElemTtypeSqstack:pop【(ElemTypex;if(top=0)x=-999;else(x=elemtop;top-;returnx;/pop单链表发生了什么变化？画出处理后的单链表图示。IstructSnode/结点结1构Ichardata;!ISnode*next;1:;'IclassLink/链表类！I1

49、private:(；Snode*Head;ipublic:1_Link()Head=NULL;I"1e一A_|voidcreat();ivoidreverse();11voidoutput();5,针对下图所示二叉树列算法，一输出是什么U假定调用该算法时以HL为表头指针的单链表中的内容为(15,26,48,55),则调用返回后该单链表中的内容为：voidAI(adjmatrrixGA,inti,intn)(cout<<i<<''vistedi=true;for(intj=0;j<n;j+)if(GaIj!=0&&GAij!

50、=MaxValue&&!visitedj)AI(GA,j,n);该算法的功能为：。I/类定义IconstintMAX=20;1typedefcharElemType;iclassSqstacki(private:；ElemTypeelemMAX;Iinttop;ipublic:11. -Sqstack()top=0;IElemTypepop();Ivoidpush(ElemTypex);:/.;|;有如下图所示单链表，经过reverse算法处理后，voidLink:reverse()Snode*p,*q;p=Head->next;Head->next=NULL;wh

51、ile(p!=NULL)q=p->next;p->next=Head->next;Head>next=p;p=q;/reverseead-IEc二3J下列函数是二叉排序树的什么算法？如果K值为比较几次得到结果？VoidBstree:Search(KeyTypeK)(intflag=0;BstNode*q=root,*p=NULL;while(q!=NULL)&&(flag=0)(if(q->key=K)flag=1;elseif(K<q->key)p=q;q=q->lch;elsep=q;q=q->rch;if(flag=0

52、)cout<<"n查找失败，无此结点！n”;elsecout<<"n查找成功，找到："<<q->key<<endl;voidAA(LNode*HL,constElemType&item)LNode*newptr=newLnode;newptr->data=item;LNode*p=HL;while(p->next!=HL)p=p->next;newptr->next=HL;p->next=newptr;对于结点类型为LNode的单链表，以上算法的功能为：voidBB(Lis

53、t&L)inti=0;while(i<L.size)intj=i+1;while(j<L.size)if(L.listj=L.list)for(intk=j+1;k<L.size;k+)L.listk-1=L.listk;L.size-;elsej+;i+;以上算法的功能为：voidCC(BTreeNode*&BST)ElemTypea6=45,23,78,35,77,25;BST=NULLfor(inti=0,i<6;i+)Insert(BST,ai);调用该算法后，生成的二叉搜索数的中序序列为：voidDD()ElemTypeA=1,3,5,7,9,

54、2,4,6,8,10,B10;TwoMerge(A,B,0,4,9);for(inti=0;i<10;i+)cout<<Bi<<”"cout<<endl;调用该算法后，输出结果为：template<classType>intSeqList<Type>:Insert(Type&x,inti)if(i<0|i>last+1|last=MaxSize-1)return0;elseLast+;for(intj=last;j<i;j-)dataj=dataj-1;datai=x;return1;对于结点

55、类型为SeqList的顺序表，以上算法的功能为：四、算法设计题：1. 编写复制一棵二叉树的非递归算法。2. 假设二叉树中每个结点所含数据元素均为单字母，以二叉链表为存储结构，试编写算法按如下图所示的树状显示二叉树。3. 试用递归法编写输出从n个数中挑选k个进行排列所得序列的算法。4. 编写一个算法，交换单链表中p所指向的结点和其后续结点的两个结点，Head指向该链表的表头，P指向链表中的某一结点。Head5. 试写一递归算法，从大到小输出二叉排序树中所有的关键字值小于key的元素值。6. 已知带头结点的单链表是一个递增有序表，试写一算法，删除表中值大于min且小于max的结点（若表中有这样的结

56、点)，同时释放被删除结点的空间，这里min和max是两个给定的参数。7.已知深度为h的二叉树以一维数组BT(1:2h-1)作为其存储结构。请写一算法，求该二叉树中叶结点的个数。8. 编写在以BST为树根指针的二叉搜索树上进行查找值为item的结点的非递归算法，若查找item带回整个结点的值并返回true，否则返回false。9. boolFind(BtreeNode*BST,ElemType&item)设A=(a1,.,am)和B=(b1,.,bn)均为顺序表，A'和B'分别为A和B中除去最大共同前缀后的子表。若A'=B'=空表，则A=B若A'=空表，而B'乒空表，或者两者均不为空表，且A'的首元小于B'的首元，则A<B;否则A>B试写一个比较A,B大小的算法。10. 已知单链表a和b的元素按值递增有序排列，编写算法归并a和b得到新的单链表c,c的元素按值递减有序。11. 编写递归算法，对于二叉树中每一个元素值为x的