数据结构自考题

《数据结构自考题》由会员分享，可在线阅读，更多相关《数据结构自考题（19页珍藏版）》请在装配图网上搜索。

1、14. 下面程序段的时间复杂度是O（mn）。for （int i=1;i=n;i+）for （int j=1;jnext=NULL）。43. 在一个单链表中，若删除（*p）结点的后继结点，则执行（p-next=p-next-next）。49. 若频繁地对线性表进行插入和删除操作，该线性表应该采用的存储结构是（链式）。53. 若要在0（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分 别指向（各自的尾结点）o77. 若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，需要移动表中元素的 个数是（n-i+1）。95. 若要在0 （1）的时间复杂度上

2、实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分 别指向（ 各自的尾结点）。102.将长度为m的单链表连接在长度为n的单链表之后的算法的时间复杂度为（0（n）。107. 单链表中，增加头结点的目的是为了（方便运算的实现）。121.在顺序表（n足够大）中进行顺序查找，其查找不成功的平均长度是（n+1 ）o22222222222222222222222222222222222224. 在 循环 链表中，从任何一结点出发都能访问到表中的所有结点。44. 每个结点只有 一个 链接域的链表叫做单链表。333333333333333333333333333333333333333333333

3、3333311. 线性表有两种存储结构：一是顺序表，二是链表。试问：如果有n个线性表同时并存，并且在处理过 程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？ 答：选链式存储结构。它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间 复杂度为0 （1）o12. 试述顺序存储和链式存储的区别及各自的优缺点。答：数组占用连续的内存空间，链表不要求结点的空间连续。1）插入与删除操作：由于数组在插入与删除数据时需移动大量的数据元素，而链表只需要改变一些指 针的链接，因此，链表比数组易于实现数据的插入和删除操作。2）内存空间的占用情况：因链

4、表多了一个指针域，故较浪费空间，因此，在空间占用方面，数组优于 链表。3）数据的存取操作：访问链表中的结点必须从表头开始，是顺序的存取方式，而数组元素的访问是通 过数组下标来实现的，是随机存取方式，因此，在数据存取方面，数组优于链表。数据的合并与分离：链表优于数组，因为只需要改变指针的指向44444444444444444444444444444444444444444444444444444444四1. 写出计算单链表head（head为单链表的表头）中数据域data值为m的结点个数的算法。int count （Node *head）计算单链表head中数据域data值为m的结点个数 Nod

5、e *p=head-next;int n=0;while (p!=NULL)if (p-data=m)n+；p=p-next;return n;/ count2. 巳知非空单链表head，试设计一个算法，交换p所指结点与其后继结点在链表中的位置。解答：int revers(listnode *head, listnode *p)/*交换p所指结点与其后继结点在链表中的位置*/ if (p-next=NULL) return 0 ;listnode *q=head;while (q-next!=p) q=q-next;r=p-next； q-next=r;p-next =r-next ; r-n

6、ext=p;return 1;/ revers3. 线性表用带头结点的单向链表示，试写出删除表中所有data域为零的元素的算法。解答：解：int DeleteItem(Node * head) Node *p=head;声明指针p，并令其指向链表头结点while (p-next!=NULL)if(p-nex-data=0)p-next=p-next-next.else p=p-next; /指针下移4. 试设计一算法，计算带头结点的单链表head(head指向表头)的结点个数。解答：int Length()计算带表头结点的单链表head的长度Node *p=head-next;int coun

7、t=0;while (p!=NULL)p=p-next; count +; return count;5. 判断单链表head(head指向表头)是否是递增的。解答【编者注：链表无头结点】int order(Node *head)Node *p=head;while(p-next!=NULL)if(p-datanext-data)p=p-next;elsebreak;if(p-next=NULL)return 1;elsereturn 0;6. 设计一个算法，在一个单链表head中找出值最小的元素。解答【编者注：链表无头结点】int Min(Node * head )在单链表head中找出值最

8、小的元素 Node *p=head;int min=p-data;while (p-next!=NULL) if(p-next-datanext-data;p=p-next;return min;7设有两个单链表L和L1,其结点结构为(data,next),试编写算法判断链表L1中的各元素是否都是单链表 L中的元素。解答：int SubLnk(Node *L, Node *L1)Node *p1=L1;while(p1!=NULL)Node *p=L;while(p!=NULL)&(p1-data!=p-data)p=p-next;if (p=NULL) return 0; /【编者注：L1中

9、元素未在L中】else p1=p1-next;return 1;9. 设有一个正整数序列组成带头结点的单链表head，试编写算法确定在序列中比正整数x大的数有几个。(8分)解答：int count (Node * head， int x)在带头结点的单链表head中，确定序列中比正整数x大的数有几个Node *p=head-next;int count=0;while (p!=NULL) if (p-datax) count +;p=p-next;return count; 算法count结束五33333333333333333333333333333333333333333333333333

10、333333333333333一5. 对于栈操作数据的原则是(后进先出)。13. 对于栈操作数据的原则是(后进先出)14. 设输入序列为A,B,C,D,借助一个栈不可以得到的输出序列是(D,A,B,C )。19. 因此在初始为空的队列中插入元素a,b,c,d以后，紧接着作了两次删除操作，此时的队尾元素是(d).20. 一般情况下，将递归算法转换成等价的非递归算法应该设置(堆栈)。25. 设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作，则下面得不到的序列为(cabdef)。37. 因此在初始为空的队列中插入元素 a,b,c,d 以后，紧接着作了两次删除操作，此时的队尾元素是 (d

11、)。41. 栈和队列的主要区别在于(插入删除运算的限定不一样)48. 链栈和顺序栈相比，有一个较明显的优点是(通常不会出现栈满的情况)。50. 设一个栈的输入序列是1，2, 3, 4, 5，则下列序列中，是栈的合法输出序列的是(3 2 1 5 4)。72.单链表表示的链式队列的队头在链表的什么位置(链头 )。101.链栈和顺序栈相比，有一个较明显的优点是(通常不会出现栈满的情况)。110. 设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为(O(n)。113.设有三个元素X, Y, Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是（ZXY ）。123. 栈的插入

12、和删除操作进行的位置在（栈顶）。125. 链栈和顺序栈相比，有一个较明显的优点是（通常不会出现栈满的情况）。222222222222222222222222222222222222222222226循环队列的引入，目的是为了克服 假溢出 。49. 队列中允许进行插入的一端称为队尾。29. 栈和队列的共同特点是插入和删除均在端点处进行。34.队列中允许进行插入的一端称为 队尾。39. 一个栈的输入序列是：1, 2, 3则不可能的栈输出序列是3 1 2。40. 设有一个顺序栈S,元素S1, S2, S3, S4, S5, S6依次进栈，如果6个元素的出栈顺序为S2, S3, S4,S6, S5,

13、S1,则顺序栈的容量至少应为3。33333333333333333333333333333333331. 对于一个队列，如果输入项序列由1,2,3,4所组成，试给出全部可能的输出序列。答：1,2,3,4。4.将算术表达式a+b* （c+d/e）转为后缀表达式。答： B. abcde/+*+13. 将表达式（a+b）-c*（d+e）-f）*（g+h）改写成后缀表达式。答：后缀表达式为：ab+cde+*-f-gh+*14. 将算术表达式a*（b+c）-d转为后缀表达式。答： abc+*d-19. 写出中缀表达式A-（B+C/D）*E的后缀形式。答：中缀表达式A-（B+C/D）*E的后缀形式是：AB

14、CD/+E*-。3333333333333333333333333333333333333333333333333333333333316. 一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的起始地址为100,则该数组的 首地址是（70）。59. 稀疏矩阵一般采用的压缩存储方法为（三元组表）【编者注：三元组表和十字链表】81.设有数组Ai,j,数组的每个元素长度为3字节，i的值为1到8 , j的值为1到10，数组从内存 首地址BA开始顺序存放，当用以列为主存放时，元素A5, 8的存储首地址为（BA+180 ）。126. 对稀疏矩阵进行压缩存储是为了（节省存储空间）。91.二维数组A

15、56的每个元素占5个单元，将其按行优先顺序存储在起始地址为3000的连续的内存单 元中，则元素A45的存储地址为（3145）。四五由由由由由由由由由由由由 串串串串串串串串串串串串2. 串是（任意有限个字符构成的序列）。12.串是（任意有限个字符构成的序列）。70. 串是（任意有限个字符构成的序列）。104.若字符串“1234567”采用链式存储，假设每个字符占用1个字节，每个指针占用2个字节，则该字 符串的存储密度为（33.3%）。四五=树树树树树树树树树=1. 具有n个结点的二叉树采用链接结构存储，链表中存放NULL指针域的个数为（n+1）。3. 在一棵二叉树的二叉链表中，空指针域数等于非

16、空指针域数加（2）。4. 某二叉树的前序和后序序列正好相反，则该二叉树一定是什么二叉树（高度等于其结点数）。7. 在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该（只有左子树上的所有结点）。9. 若一棵二叉树具有45个度为2的结点，6个度为1的结点，则度为0的结点个数是（46 ）。10. 某二叉树的前序和后序序列正好相同，则该二叉树一定是什么样的二叉树（空或只有一个结点）。15. 结点前序为xyz的不同二叉树，所具有的不同形态为（5 ）。17. 在一棵高度为假定树根结点的层号为0）的完全二叉树中，所含结点个数不小于（2h ）。21. 对于一棵满二叉树，m个树叶，n个结点，深度为h,则（n

17、=2h+1-1 ）。27. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（2 ）。30. 如果T2是由有序树T转换而来的二叉树，那么T中结点的先根序列就是T2中结点的（先根序列）。31. 对于一棵满二叉树，m个树叶，n个结点，深度为h,则（n=2h+1-1 ）。38. 深度为h且有多少个结点的二叉树称为满二叉树（2h+1-1）。39. 某二叉树的前序和后序序列正好相反，则该二叉树一定是的二叉树为（高度等于其结点数）【编者注： 只有一个叶子结点】42. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（2h-1 ）【编者注：根结点高度为1】44. 在一棵

18、具有n个结点的二叉树中，所有结点的空子树个数等于（n+1）45. 若一棵二叉树有11个度为2的结点，则该二叉树的叶结点的个数是（12 ）。51. 设森林F中有三棵树，第一、第二和第三棵的结点个数分别为m1,m2和m3,则森林F对应的二叉树根结 点上的右子树上结点个数是（m2+m3 ）。54. 二叉树的第I层上最多含有结点数为（2i ）【编者注：根结点高度为0】55. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（2h-1 ）。56. 如果T2是由有序树T转换而来的二叉树，那么T中结点的先根序列就是T2中结点的（先根序列 九58.有n个叶子的哈夫曼树的结点总数

19、为（2n-1）。60. 若二叉树中度为2的结点有15个，度为1的结点有10个，则叶子结点的个数为（16）。61. 若某完全二叉树的深度为h，则该完全二叉树中具有的结点数至少是（2h-1 ）【编者注：根结点高度 为1】62. 任何一棵二叉树的叶结点在其先根、中根、后根遍历序列中的相对位置（肯定不发生变化）。74. 对于一棵满二叉树，m个树叶，n个结点，深度为h,则（n=2h+1-1）【编者注：根结点高度为0】75. 某二叉树的前序和后序序列正好相同，则该二叉树一定是什么样的二叉树（空或只有一个结点）。76. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（n+1 ）。78. 树中所有结点

20、的度等于所有结点数加（-1）。79. 设二叉树根结点的层次为0, 一棵高度为h的满二叉树中的结点个数是（2h+1-1）。80. 将一棵有50个结点的完全二叉树按层编号，则对编号为25的结点x，该结点（有左孩子，无右孩子）。83.设森林F中有三棵树，第一、第二和第三棵的结点个数分别为m1,m2和m3，则森林F对应的二叉树根 结点上的右子树上结点个数是（m2+m3 ）。87.用孩子兄弟链表表示一棵树，若要找到结点x的第5个孩子，只要先找到x的第一个孩子，然后（从兄 弟域指针连续扫描4个结点即可）。90.深度为h的满二叉树具有的结点个数为（2h+1-1）【编者注：根结点高度为0】96. 在一棵高度为

21、h（假定树根结点的层号为0）的完全二叉树中，所含结点个数不小于（2h ）。98.有n个叶子的哈夫曼树的结点总数为（2n-1 ）。106.若在一棵非空树中，某结点A有3个兄弟结点（包括A自身），B是A的双亲结点，则B的度为（3）。108. 深度为h的满二叉树所具有的结点个数是（2h+1-1 ）。109. 按照二叉树的定义，具有3个结点的二叉树有多少种（5 ）。111. 树中所有结点的度等于所有结点数加（-1 九112. 树中所有结点的度等于所有结点数加（-1）117.树形结构的特点是：一个结点可以有（多个直接后继）。119.按照二叉树的定义，具有3个结点的二叉树具有的种类为（5 ）。127. 结

22、点前序为xyz的不同二叉树，所具有的不同形态为（5 ）。128. 若一棵二叉树具有20个度为2的结点，6个度为1的结点，则度为0的结点个数是（21 ）。129. 一棵线索二叉树的线索个数比链接个数多（2 ）个。124. 某二叉树的前序和后序序列正好相同，则该二叉树一定是的二叉树为（空或只有一个结点）。122.设树T的度为4,其中度为1，2, 3和4的结点个数分别为4, 2, 1，1则T中的叶子数为（8）。【编者注：公式为n0 = 1 + (i - 1)ni i=122222222222222222222222222222222222222222222222222222222I. 若一棵二叉树有

23、10个叶结点，则该二叉树中度为2的结点个数为9。3.对于一棵二叉树，设叶子结点数为n0，次数为2的结点数为n2，则n0和n2的关系是n0= n2 + 1。6. 深度为h且有2h-1个结点的二叉树称为满二叉树。（设根结点处在第1层）。8. 哈夫曼树是带权路径长度最小的二叉树。9. 二叉树的存储结构有顺序存储结构和链式存储结构。10. 哈夫曼树是带权路径长度最小的二叉树。II. 一般树的存储结构有双亲表示法、孩子兄弟表示法和孩子链表表示法。18. 由一棵二叉树的后序序列和中序序列可唯一确定这棵二叉树。20. 若二叉树的一个叶子结点是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历中的

24、第一个结点。22. 具有100个结点的完全二叉树的叶子结点数为50。25.将一棵树转换成一棵二叉树后，二叉树根结点没有右子树。30.二叉树的遍历方式有三种：先序遍历、中序遍历、后序遍历。33.若一棵二叉树有15个叶结点，则该二叉树中度为2的结的点个数为14。37.则高度为k的二叉树具有的结点数目，最少为k，最多为2k-1【编者注：根结点高度为1】41. 对于一棵二叉树，设叶子结点数为n0,次数为2的结点数为n2,则n0和n2的关系是 n0= n2 + 142. 设某二叉树的后序遍历序列为ABKCBPM，则可知该二叉树的根为M。48. 由一棵二叉树的后序序列和中序序列 可唯一确定这棵二叉树。33

25、333333333333333333333333333333333333333333333333332. 巳知一棵二叉树的中序和前序序列如下，求该二叉树的后序序列。中序序列：c， b， d， e，a，g， i，h， j， f前序序列：a， b， c，d， e，f， g，h， i， j答：该二叉树的后序序列为：c,e,d,b,i,j,h,g,f,a3. 为什么说树是一种非线性结构？答：树中的每个结点除了根结点外，其余每个结点有一个直接前驱，但有多个直接后继，所以说树是一种 非线性结构。5. 找出所有这样的二叉树形，其结点在先根次序遍历和中根次序遍历下的排列是一样的。答：为空树，或为任一结点至多只

26、有右子树的二叉树。10. 完全二叉树用什么数据结构实现最合适，为什么？答：完全二叉树用一维数组实现最合适。因为完全二叉树保存在一维数组中时，数组内没有空洞，不存在 空间浪费问题；另外，顺序存储方式下，父子结点之间的关系可用公式描述，即巳知父（或子）结点寻找 子（或父）结点只需计算一个公式，访问结点方便。但采用链表存储时就存在空间浪费问题，因为每个结 点要另外保存两个链接域，并且寻找结点也不容易。20.为什么用二叉树表示一般树？答：树的最直观表示是为树中结点设置指向子结点的指针域，对k叉树而言，每个结点除data域外，还有 k个链接域。这样，对一个有n个结点的k叉树来说，共有n*k个指针域，其中

27、n-1个不空，另外n（k-1）+1 个指针域为空，因此，空链接域的比例约为（k-1） /k，于是导致大量的空间浪费。然而，如果采用二叉 树表示一棵n个结点的树，则树中共有2n个链接域，其中未用到的有n+1个，占所有指针域的比例约为 1/2,空间浪费少很多。另外，因为任何树型结构都可以转换成二叉树，因此，通常用二叉树表示树型结构。22. 试找出前序序列和中序序列相同的所有二叉树。解答：空树或缺左子树的单支树。23. 完全二叉树用什么数据结构实现最合适，为什么？答：完全二叉树用一维数组实现最合适。因为完全二叉树保存在一维数组中时，数组内没有空洞，不存在 空间浪费问题；另外，顺序存储方式下，父子结点

28、之间的关系可用公式描述，即巳知父（或子）结点寻找 子（或父）结点只需计算一个公式，访问结点方便。但采用链表存储时就存在空间浪费问题，因为每个结 点要另外保存两个链接域，并且寻找结点也不容易。26. 我们巳经知道，树的先根序列与其对应的二叉树的先根序列相同，树的后根序列与其对应的二叉树的 中根序列相同。那么利用树的先根遍历次序与后根遍历次序，能否唯一确定一棵树？请说明理由。答：能。因为树的先根序列与其对应的二叉树的先根序列相同，树的后根序列与其对应的二叉树的中根序 列相同，而二叉树的先根序列与二叉树的中根序列能唯一确定一棵二叉树，所以利用树的先根遍历次序与 后根遍历次序，能唯一确定一棵树。28.

29、 巳知一棵二叉树的中序和前序序列如下，求该二叉树的后序序列。中序序列：c，b， d， e，a，g， i，h， j， f前序序列：a， b， c，d， e，f， g，h， i， j答：该二叉树的后序序列为：c,e,d,b,i,j,h,g,f,a39.巳知一棵二叉树的前序和中序序列，求该二叉树的后序序列。前序序列：A, B,C,D,E,F,G,H,I,J中序序列：C, B,A,F,E,D,I,H,J,G答：后序序列为：C,B,F,E,I,J,H,G,D, A4444444444444444444444444444444444444444444444444四8.设一棵二叉树以二叉链表为存储结构，设计

30、一个算法交换二叉树中每个结点的左子女和右子女。(12分) 解答：void exchange(BinTreeNode * t)if (t!=NULL)BinTreeNode * temp;if(t-lchild!=NULL)|(t-rchild!=NULL)temp= t-lchild;t-lchild= t-rchild;t-rchild= temp;exchange(t-lchild);exchange(t-rchild);10. 设一棵二叉树以二叉链表为存储结构，试设计一个算法计算二叉树中叶子结点的个数。(12 分)解答：void countleaf(BinTreeNode * t,int

31、 &count) if(t!=NULL)if(t-lchild= =NULL)&(t-rchild= =NULL)count+; (2 分)countleaf(t-lchild,count);countleaf(t-rchild ,count);11. 设一棵二叉树以二叉链表为存储结构，试写一算法求该二叉树上度为2的结点个数。(12 分)解答：void count2(bitreptr t，int count)if (t!=NULL)if (t-lchild != NULL) & (t-rchild != NULL)count+;count2(t-lchild,count)；count2(t-r

32、child,count)；/ count212. 设一棵二叉树以二叉链表为存储结构，试写一算法求该二叉树中最大值(元)。(12分)解答：void maxnode(bitreptr t，int max)if(t!=NULL) (2 分)if(t- datamax) max=t-data; (4 分)max= maxnode(t-lchild,max) ； (2 分)max= maxnode(t-rchild,max) ； (2 分)return max; （2 分）/ maxnode555555555555555555555555555555555555555555555555555555555

33、5555555五6. 由二叉树的前序和后序遍历序列能否唯一确定一棵二叉树。若不能请举出反例。 答：不能唯一确定一棵二叉树。如下图。12318.画出下图中二叉树的顺序存储结构示意图。答：二叉树的顺序存储结构示意图为:25.对于下图所示的二叉树，试分别写出先根遍历、中根遍历和后根遍历该树所得到的先根序列、中根序13715A0A2A6A14列和后根序列。解答：先根遍历的结点序列：ABCEIFJDGHKL中遍历的结点序列：EICFJBGDKHLA后根遍历的结点序列：IEJFCGKLHDBA32. 答：把下列森林转化为一棵二叉树。答：森林转化成的二叉树如下图。33. 试找出前序序列和后序序列相同的所有二

34、叉树。答：空树或只有根结点的二叉树。40. 把下图中的二叉树转化成森林。42.将下图中的二叉树，转换成相应的森林。43. 知二叉树按中根遍历所得到的结点序列为DCBGEAHFIJK ,按后根遍历所得到的结点序列为 DCEGBFHKJIA，画出该树形结构，并按中根遍历序列进行线索化。44. 对于下图所示的二叉树，试分别写出先根遍历、中根遍历该树所得到的先根序列、中根序列。中遍历的结点序列：EICFJBGDKHLA答：先根遍历的结点序列：ABCEIFJDGHKL，46.把下图中的二叉树转化成森林。49.有一棵二叉树如下图所示，分别指出其前序、中序遍历的结点序列。答：它的前序序列为：ABCDEFGH

35、IJ，它的中序序列为：CDBAFGEIHJ。52.有二叉树先序序列为：ABCDEF,中序序列为：CBAEDF,试画出该二叉树。 答：二叉树如下图。53.根据下图给出的二叉树，求出中序和后序遍历的结点序列。答：先序遍历为：abdcef中序遍历为：dbaefc后序遍历为：dbfeca55555555555555555555555555图图图图图图图图图图图图11. 在一个有向图中，所有顶点的入度之和等于所有边数（1 ）倍【编者改了答案】18.在一个无向图中，所有顶点的度数之和等于所有边数（2 ）倍。23.用邻接表表示图进行深度优先遍历时，通常用来实现算法的辅助结构是（栈）。32. 具有n个顶点的有

36、向图最多可包含的有向边的条数是（n（n-1）。34. 任何一个无向连通图的最小生成树（有一棵或多棵）。47. 有向图中，以顶点v为终点的边的数目，称为顶点的（入度）。66在一个有向图中，所有顶点的出度之和等于所有边数的倍数是（1）。67.有n个顶点的图采用邻接矩阵表示，则该矩阵的大小为（n*n ）。68.6个顶点的无向图成为一个连通图至少应有边的条数是（5 ）。71.无向图中，所有顶点的度数之和等于所有边数（2）倍。【编者改了答案】82.在一个具有n个顶点的完全无向图的边数为（n（n-1）/2 ）。85.在图形结构中，每个结点的前驱结点数和后续结点数可以有（任意多个）。92. 一个具有n个顶点

37、e条边的无向图中，采用邻接表表示，则所有顶点的邻接表的结点总数为（2e）。93. 一个具有n个顶点的图采用邻接矩阵表示，则该矩阵的大小为（n*n）。94. 一个具有n个顶点e条边的无向图中，采用邻接表表示，则所有顶点的邻接表的结点总数为（2e）。114.用邻接表表示图进行深度优先遍历时，通常采用的辅助存储结构是（栈）。116.在含n个顶点e条边的无向图的邻接矩阵中，零元素的个数为（n2-2e）o118.使具有30个顶点的无向图成为一个连通图至少应有边的条数是（29）。120.使具有9个顶点的无向图成为一个连通图至少应有边的条数是（8 ）。5.普里姆（Prim）算法适用于边稠密图。7. 图的深度

38、优先搜索方法类似于二叉树的先序遍历13.图的深度优先遍历序列不是唯一的。16. 图的遍历是指从图中某一顶点出发访问图中全部顶点且使每一顶点仅被访问一次。17. 在一个图中，所有顶点的度数之和等于所有边的数目的2倍。23.普里姆（Prim）算法适用于边稠密图。27.若连通网络上各边的权值均不相同，则该图的最小生成树有1棵。31. 若连通图的顶点个数为n，则该图的生成树的边数为n-1。32. 图的存储结构最常用的有邻接矩阵和邻接表。35. 拓扑排序输出的顶点数小于有向图的顶点数，则该图一定存在环。38.若连通网络上各边的权值均不相同，则该图的最小生成树有1棵。47.图的存储结构最常用的有邻接表和邻

39、接矩阵。45. 设无向图G的顶点数为n，则要使G连通最少有n-1条边。8. 有n个顶点的无向连通图至少有多少条边？有n个顶点的有向连通图至少有多少条边? 答：有n个顶点的无向连通图至少有n-1条边，有n个顶点的有向连通图至少有n条边。5555555555555555555555555555555555555555555555五答：有向图的邻接矩阵为:012340278q1808882880583888084V8840 j15.求出下图所示有向图的邻接表。答：有向图的邻接表为:16.求出下图所示无向图的邻接表。答：无向图的邻接表为:Head17.用邻接矩阵存储一个包含1000个顶点和1000条边

40、的图，则该图的邻接矩阵中有多少元素？有多少非零 元素？ 答：该图的邻接矩阵中有1000*1000个元素。该图的邻接矩阵中有2000个非零元素27.请给出如下图所示的权图的邻接矩阵。答：00123412327811808884880588L 38888048036. 巳知一个图如下所示，若从顶点0出发求出其广度优先搜索序列。解答：广度优先搜索序列：01234567 =排序排序排序排序排序排序排序排序= 8.排序方法中，从未排序序列中依次取出元素与巳排序序列中的元素进行比较，将其放入已排序序列的正 确位置上的方法，称为（插入排序）。29. 一组记录的关键字为45, 80, 55, 40, 42,

41、85，则利用堆排序的方法建立的初始堆为（85, 80, 55,40, 42, 45 ）。33. 设有6000个无序的元素，希望用最快的速度挑选出其中前5个最大的元素，最好选用（堆排序）法。35. 排序方法中，从未排序序列中挑选元素，将其放入巳排序序列的一端的方法，称为（选择排序）。57.用分划交换排序方法对包含有n个关键的序列进行排序，最坏情况下执行的时间杂度为（O（n2）。63. 初始序列巳经按键值有序时，用直接插入算法进行排序，需要比较的次数为(n-1)。65用冒泡排序法对序列18,16,14,12,10,8从小到大进行排序，需要进行的比较次数是(15 )。73. 一组记录的关键字为45,

42、 80, 55, 40, 42, 85，则利用堆排序的方法建立的初始堆为(85, 80, 55,40, 42, 45)。84.对于键值序列72,73,71,23,94,16,5,68,76,103用筛选法建堆，开始结点的键值必须为(94 )。97.若待排序对象序列在排序前巳按其排序码递增顺序排序，则采用比较次数最少的方法是(直接插入排 序)。(n)100.在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂性为()o103.若待排序对象序列在排序前巳按其排序码递增顺序排序，则采用(直接插入排序)方法比较次数最少。105.用分划交换排序方法对包含有n个关键的序列进行排序，最坏情况下执行的时间杂

43、度为(O(n2 )。21.在直接插入排序、直接选择排序、分划交换排序、堆排序中稳定的排序方法有直接插入排序。33333333333333333333333333333333333333333333333333333333333333339. 下面列举的是常用的排序方法：直接插入排序，起泡排序，快速排序，直接选择排序，堆排序，归并排 序。试问，哪些排序方法是稳定的？答：起泡排序，直接插入排序，归并排序是稳定的。21.巳知数据序列为12,5,9,20,6,31,24，对该数据序列进行排序，试写出冒泡排序每趟的结果。答：初始键值序列12 5920 631 24第一趟排序599126612202024

44、243131第二趟排序5第三趟排序56912202431【编者改了答案】第四趟排序5691220243131.巳知数据序列为12,5,9,20,6,31,24，对该数据序列进行排序，试写出归并排序每趟的结果。解答：初始键值序列12592063124第一趟排序 5129206 31 24第二趟排序 59122062431第三趟排序56912202431 ()37. 一组记录的关键字为(52,56,26,12,69, 85, 33, 48, 70)，给出快速排序的过程解答：【编者：本书对快速排序与其它书不一样】解：52,56,26,12,69,85, 33, 48, 70 错误第一趟排序 33,4

45、8,26,12,52,85,69, 56, 70第二趟排序 26,12,33,48,52,69,56, 70, 85第三趟排序 12,26,33,48,52,56,70, 69, 85第四趟排序 12,26,33,48,52,56,70, 69, 85第五趟排序 12,26,33,48,52,56,70, 69, 8538.下面列举的是常用的排序方法：直接插入排序，起泡排序，快速排序，直接选择排序，堆排序，归并 排序。试问，哪些排序方法是稳定的？起泡排序，直接插入排序，归并排序是稳定的。48. 设记录的关键字集合key=51,28,38,86,70,90,7,30,40,25，试写出对key进

46、行渐减增量排序(增量d = 5,3, 1)时，各趟排序结束后的结果。解答：各趟排序结束后的结果。初始状态：51 283886 70907304025第一趟排序(d=5):517304025902838 86 70第二趟排序(d=3):287304025865138 90 70第三趟排序(d=1):725 283038405170 86 90)四5555555555555555555555555555555555555555555555555555555五34. 一组记录的关键字为（50, 79, 8, 56, 32, 41, 85）,给出利用重建堆方法建立的初始堆（堆顶最大）,并给出堆排序的过

47、程。答：1）建立的初始堆为：85, 79, 50, 56, 32, 41, 82）堆排序的过程如下：（g）第6次交换47. 一组记录的关键字为（52, 56, 26, 12, 69, 85, 33, 48, 70），给出快速排序的过程。解答：【编者：本书对快速排序与其它书不一样】解：52,56,26,12,69,85,33,48,70错误第一趟排序33,48,26,12,52,85,69,56, 70第二趟排序26,12,33,48,52,69,56,70, 85第三趟排序12,26,33,48,52,56,70,69, 85第四趟排序12, 26,33,48,52,56,70,69, 85第

48、五趟排序12, 26,33,48,52,56,70,69, 8550.巳知8个记录，对应的关键词为：25,84,21,47,15,27,68,35,20写出快速排序的第一趟排序过程图示。答：初始键值序列2584 21 4715 27683520第一次交换2584214715 27683520第二次交换251 1-220 21471 15 276835* J-9 84扫描交叉25 2021 15j f47 27代683584Rm与Rj互换R25 20f m21 15jf47 27683584分划表15 2021 2547 2768358488888888888888888888888888888

49、8查找查找查找查找查找出查找24.堆的形状是一棵(完全二叉树)。36. 对有14个数据元素的有序表R14进行折半搜索，搜索到R3的关键码等于给定值，此时元素比较顺 序依次为(R6，R2，R4，R3)【编者注：下标从0开始】46.对有n个记录的表按记录键值有序建立二叉查找树，在这种情况下，其平均查找长度的量级为 (O(n)。52. 有数据53，30，37，12，45，24，96，从空二叉树开始逐个插入数据来形成二叉查找树，若希望高 度最小，则应选择下面输入序列是(37,24,12,30,53,45,96)。64. 对有n个记录的有序表采用二分查找，其平均查找长度的量级为(O(logn)。69.对

50、有14个数据元素的有序表R14进行折半搜索，搜索到R3的关键码等于给定值，此时元素比较顺 序依次为(R6，R4，R2，R3)。86.对有n个记录的有序表采用二分查找，其平均查找长度的量级为(O(logn)。2 .115.对有18个元素的有序表作二分(折半)查找，则查找A 3的比较序列的下标为(9、4、2、3)【编 者注：下标从1开始】88. 有一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当二分查找值为 82 的结点 时，查找成功的比较次数是(4 )。.89. 当初始序列巳经按键值有序时，用直接插入算法进行排序，需要比较的次数为(n-1 )。99.二分查

51、找法要求查找表中各元素的键值必须是(递增或递减)。222222222222222222222222222222222222222222222222222222222222.在有序表(12,24,36,48,60,72,84)中二分查找关键字72时所需进行的关键字比较次数为2。12.将数据元素2,4,6,8,10,12,14,16,18,20依次存于一个一维数组中，然后采用折半查找元素12,被比 较过的数组元素的下标依次为5, 8, 6【编者注：下标从1开始，答案巳改】19.24.在有序表(12,24,36,48,60,72,84)中二分查找关键字72时所需进行的关键字比较次数为2。在n个结点的

52、顺序表中插入一个结点需平均移动n/2个结点。28.29.答：30.答：在有序表(12,24,36,48,60,72,84)中二分查找关键字72时所需进行的关键字比较次数为2。对半查找是否适合于以链接结构组织的表？对半查找不适合于以链接结构组织的表。请指出中序遍历二叉查找树的结点可以得到什么样的结点序列。中序遍历二叉查找树的结点就可以得到从小到大排序的结点序列。36.在有序表(15,23,24,45,48,62,85)中二分查找关键词23时所需进行的关键词比较次数为2。四五 24.给定表(40,36,55,6,64,77,9,41)，按数据元素在表中的次序构造一棵二叉查找树，并求其平均查找 长度

53、。答：构造的二叉查找树如下图，其平均查找长度为11/4。41.给定表(43,36,56,6,64,32,8,41),按数据元素在表中的次序构造一棵二叉查找树，并求其平均查找长 度。解答：根据给定表(43,36,56,6,64,32,8,41)，构造的二叉查找树如下图；其平均查找长度为：23/8。51.给定表(45,36,56,6,64,32,8,41)，按数据元素在表中的次序构造一棵二叉查找树。解答：按数据元素在表中的次序构造一棵二叉查找树为：53. 序表(5, 12, 17, 19, 23, 25, 30, 36, 45, 49, 58)中，用二分法查找关键词36，进行多少次比 较后查找成功

54、？写出查找过程。解答：经过4次比较查找成功。查找过程如下：5, 12, 17, 19, 23, 25, 30, 36, 45, 49, 58! t ti=1m=6j=11(a )第1次与25进行比较5, 12, 17, 19, 23, 25, 30, 36, 45, 49, 58t ti=7j=8I18 / 18m=75, 12, 17, 19, 23, 25, 30, 36, 45, 49, 58j t I i=7m=9 j=11(b)第2次与45进行比较5, 12, 17, 19, 23, 25, 30, 36, 45, 49, 58i=8 Hj=8tm=8(c)第3次与30进行比较(d )第4次与36进行比较