数据结构题库应用题上海杉达学院期末总复习题

数据结构 应用题数据结构应用题复习概要2018年10月1. 写出执行下列程序段时，语句S的执行次数。for (i=1; i=i; j-) S;2. 假设n为2的乘幂，并且n2，试求下列算法的时间复杂度及变量count的值（以n的函数形式表示）int Time(int n) int count:=0; x:=2; while (xRL = P-RL; P-RL = Q; Q-RL-LL = Q; Q-LL = P;(2) Q-RL = P; P-LL-RL = Q; Q-LL = P-LL; P-LL = Q;(3) P-LL-RL = P-RL; P-RL-LL = P-LL;4. 设栈S的初始状态为空，元素a, b, c, d, e和f依次通过栈S，试分析下列各组出栈次序，每组所用的最大容量。（1）a,b,c,d,e,f；（2）f,e,d,c,b,a；（3）b,d,c,f,e,a5. 有字符串A+B*C-D，试写出利用栈操作将该字符串序列改为ABC*+D-的操作步骤，这里用X和S分别表示字符的进栈和出栈操作（例如把字符ABCD改为ACBD的操作步骤为XSXXSSXS）。XSXXSXXSSSXXSS 6. 一棵二叉树的结点数采用顺序存储结构，存于下列数组T中，画出该二叉树。7. 已知一棵树的双亲表示如下，其中各兄弟结点依此排列，试画出该树及对应的孩子兄弟表示的二叉树。123456789101112131415DataABCDEFGHIJKLMNOParent0111223344566788. 有一个完全二叉树按层次顺序存放在一维数组中，如下所示：请指出结点P的父结点，左子女，右子女。9. 将下列二叉链表改为先序线索链表12345678dataABCDEFGHLTag00101000lchild24070000RTag00001000rchild3568000010. 下表给出用带二个标识的按先序遍历进行顺序存储的二叉树，对于结点k，规定：ltag(k)=0，k有左孩子；ltag(k)=1，k无左孩子；rtag(k)=0，k有右孩子；rtag(k)=1，k无右孩子。12345678910ltag0011110101dataAGEIDJHCFBrtag000101011111. 已知一棵二叉树的后序遍历为CDBGHFIEA，中序遍历为CBDAGFHEI。画出此二叉树并写出其先序遍历序列。12. 一棵二叉树的先序序列和中序序列分别如下，画出该二叉树并写出它的后序遍历的序列。先序序列：ABDEHCFIG中序序列：DBHEAFICG后序遍历为DHEBIFGCA13. 已知一棵二叉树的中序遍历为DBHEAFICG，后序遍历为DHEBIFGCA。画出此二叉树并写出其先序遍历序列。先序遍历：ABDEHCFIG14. 一棵二叉树的先序序列和中序序列分别如下，画出该二叉树的中序线索二叉链表。先序序列：ABCDEFGHIJ中序序列：CBEDAGHFJI15. 一棵二叉树的先序序列和中序序列分别如下，画出该二叉树的二叉链表。先序序列：ABDFCEG中序序列：BFDAEGC16. 一棵二叉树的先序、中序和后序序列分别如下，试求出空格处的内容，并画出该二叉树。先序： A B D F K I C E H J G中序：D B K F I A H E J C G 后序： D K I F B H J E G C A先序：ABDFKICEHJG中序：DBKFIAHEJCG后序：DKIFBHJEGCA17. 二叉树的先序、中序和后序序列分别如下，试求出空格处的内容，并构造出该二叉树 先序序列 A BC D EF G H 中序序列BDE C AG F H后序序列 E DC B GH F A18. 已知一棵二叉树的层次遍历序列为ABCDEFGHIJ，中序遍历序列为DBGEHJACIF，请画出该二叉树。19. 对下面的两棵树，分别画出其顺序存储结构。IABCDEFGJKABCDEFJIABDIJEKCFGABDEIJCF20. 一棵二叉树的结点数据采用顺序存储结构，存储于下列数组T中，画出该二叉数。123456789101112131415161718192021Teafdgcjlhb21. 用权分别为2，3，6，7，8次序的叶子结点构造一棵哈夫曼树（结点标出权值），若叶子结点次序改为8，7，6，3，2，所构造的哈夫曼树是否相同？22. 以数据集3，4，5，8，12，18，20，30为叶子结点的权值，（1）构造一棵哈夫曼树；（2）计算其带权路径长度。 23. 按照给定的权值10，12，14，5，30，40，构造相应的赫夫曼树。24. 以数据集15，3，14，2，6，9，16，17为叶子结点的权值，（1）构造一棵哈夫曼树；（2）计算其带权路径长度。25. 有一电文中使用5各字符A,B,C,D,E，他们出现的频率依次为4，7，5，2，9，试为每个字符设计哈夫曼编码。WPL=60A: 001B: 10C: 01D: 000E: 1126. 给定权的集合5，29，7，8，14，23，3，11，构造相应哈夫曼树。WPL=104+75+92=27127. 画出根据Prim算法对下列连通网从顶点A出发构造其最小生成树的过程。2018AB 623 85G 4E 12C 7251510FD28. 已知某系统在通信联络中可能出现8种字符，A,B,C,D,V,W,X,Y，其概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计赫夫曼编码。29. 设有带权无向图如右图所示(1) 请写出该图的邻接矩阵。(2) 请画出该图的邻接表。(3) 列出从顶点1出发深度优先遍历该图所得到的一个顶点序列。(4) 列出从顶点1出发广度优先遍历该图所得到的一个顶点序列。(5) 请画出该图的一棵最小生成树。30. 已知图G的邻接矩阵如下，分别写出从顶点A出发的深度优先和广度优先搜索序列。ABCDEA01110B00101C00010D00000E0000031. 如右图所示有向图 （1）写出邻接矩阵 （2）求出其最小生成树32. 已知图的邻接矩阵如下，图的顶点依此为V0,V1,V2,V3,V4,V5,V6，分别写出从V0，V5出发的深度优先和广度优先的遍历序列。深度： 0 1 3 4 2 5 65 3 0 1 6 2 4广度： 0 1 2 3 4 6 55 3 4 6 0 1 233. 已知图的邻接矩阵如左下方所示：（1）画出其邻接表；（2）若在它的邻接表存储结构中，每个顶点邻接序号是从小到大链接时，写出它根据邻接表以顶点V1为出发点的广度优先搜索序列和深度优先搜索序列。V1V2V3V4V5V61 2 5 5 25 4 V10101100C1V20010101C2V30000012C3V40000003C4V50011014C5V60000005C6 34. 有向图G的邻接表如右上所示，若在图中增加弧和，该邻接表需做何种修改？（可直接在给出的邻接表上修改）35. 假定无向图G有6个结点和9条边，并依次输入这9条边为（0，1），（0，2），（0，4），（0，5），（1，2），（2，3），（2，4），（3，4），（4，5）。试从顶点0出发分别写出按深度优先搜索和广度优先搜索进行遍历得到的遍历结点序列。深度：0 1 2 3 4 5广度：0 1 2 4 5 336. 对于带权的连通图G（如左下图所示），从V6出发构造最小生成树。 37. 已知一有向图G的链接表存储结构如右上所示，画出有向图，并写出从结点V1出发的深度优先遍历结点序列。38. 求出下图的一棵最小生成树。25136847675485435853639. 已知图的邻接矩阵如下，（1）试画出其邻接表；（2）若在它的邻接表存储结构中，每个顶点的邻接点序号是从小到大链接，写出以顶点V1为出发点的唯一的深度优先遍历序列。 V1V2V3V6V5V440. 画出以顶点V1为初始源点遍历下图所得到的DFS和BFS生成森林V1V3V4V2V5V6V7V841. 已知图的邻接矩阵如下所示，画出从顶点A出发图的DFS和BFS生成树。ABCDEFV0213 0 2 301 2 0 010101101000V1010111101000V2001001101010V342. 已知图的邻接表如上所示，根据邻接表写出从V0出发的深度优先和广度优先遍历序列。43. 画出根据Prim算法对下列连通网从顶点A出发构造其最小生成树的过程。2018AB 623 85G 4E 12C 7251510FD44. 下图表示一个地区的交通图，顶点表示城市，边表示城市间的公路，边上的数值（权）表示修建公路的代价，要求从顶点A出发构造能连通每个城市且总代价最低的5条公路。 45. 求出下图的最小生成树。 46. 请画出左下带权图的一棵最小生成树。 47. 如右上有向图中，顶点表示课程，弧表示课程间的先后次序，例如弧表示先学习课程C1再学习课程C3，如果某人每次只能学习一门课程则它应该如何安排学习？48. 给出左下图的所有拓扑序列。49. 请写出右上图所有可能的拓扑序列。50. 设有向图G（V，E），V1，2，3，4，5，6，E，。请写出图G中顶点的所有拓扑序列。0 1 2 5 4 30 2 1 5 4 30 2 5 1 4 3V0V1V2V3V4V5 4 2 3 5 1 4 5 0 3 0 4 2 5 0 2 0 3 5 4 3 1 0 51. 已知某图邻接表如下图所示，分别写出从V0，V3出发的深度优先和广度优先遍历序列。52. 求出左下图的所有拓扑序列。31654253. 一项工程P有6个子工程组成，这些子工程间的优先关系用下列的有向无环图表示，使给出工程P的4种可能的施工顺序。P1P2P4P3P5P6P1P2P4P5P3P6P1P4P2P3P5P6P1P4P2P5P3P6P1P4P3P2P5P6P1P4P3P5P2P6P1P4P5P2P3P6P1P4P5P3P2P6P4P1P2P3P5P6P4P1P2P5P3P6P4P1P3P2P5P6P4P1P3P5P2P6P4P1P5P2P3P6P4P1P5P3P2P654. 按下列邻接矩阵分别画出自顶点1出发进行遍历所得的深度优先和广度优先遍历生成树。55. 已知图的邻接矩阵如下，若在它的邻接表存储结构中，每个顶点的邻接点序号是从小到大链接时，写出其拓扑有序序列。1 2 3 4 6 5 7 856. 简答下列各题：（1）什么叫二叉排序树？（2）按给定的输入序列：45，24，53，12，42，90构成一棵二叉排序树；（3）由n个结点组成的二叉排序树是唯一的吗？如不唯一，请举例说明；（4）如何用二叉排序树方法对关键字序列：45，24，53，12，42，90进行排序。57. 从一棵空的二叉排序树开始，将以下关键码值依次插入：25,13,15,31,7,20,37，请画出插入全部完成后的二叉排序树。58. 对于给定结点的数据集合D=55,13, 20,15,31,7, 18（1）依次取出D中各数据，构成一棵二叉排序树BT。（2）求等概率情况下的平均查找长度ASL。（3）画出在二叉排序树BT中删除“13”后的树的结构。 ASL=(1+2+3*2+4*2+5)/7=22/7or (参考：中序遍历序列为准则)59. 分别建立结点值（关键字值）为12，24，30，37，45，53，96及37，24，12，30，53，45，96的二叉排序树，并说明在查找等概率情况下的平均查找长度。60. 对给定的关键字序列7，16，4，8，20，9，6，18，5，画出对应的二叉排序树，并再画出删除关键字为16的结点后的二叉排序树。61. 一棵二叉排序树结构如右图所示，各结点的值从小到大依次为18，请标出各结点的值。62. 设有一个长为10的有序表S1 . 10，画出对其进行折半查找的判定树，并求出等概率情况下查找成功的平均查找长度。63. 画出长度为18的有序顺序表进行二分法查找的判定树，并指出在等概率时查找成功的平均查找长度ASL以及查找失败时所需的最多的关键字比较次数。64. 设二叉排序树中关键字有1到1000的整数构成，现要查找关键字为363的结点，下述关键字序列中哪一个不可能是在二叉排序树上查到的序列？（1）2，252，401，398，330，344，397，363；（2）924，220，911，244，898，258，362，363；（3）925，202，911，240，912，245，363；（4）2，399，387，219，266，382，384，278，36365. 有一组关键值序列（38，19，65，97，49，41，95，1，73），采用冒泡排序方法由小到大进行排序，请写出每趟的结果。19,38,65,49,41,95,1,73,9719,38,49,41,65,1,73,9519,38,41,49,1,65,7319,38,41,1,49,6519,38,1,41,4919,1,38,41,1,19,38Or1, 38, 19, 65, 97, 48, 41, 95, 731, 19, 38, 41, 65, 97, 48, 73, 951, 19, 38, 41, 48, 65, 97, 73, 951, 19, 38, 41, 48, 65, 73, 97, 951, 19, 38, 41, 48, 65, 73, 95, 9766. 设有序列38，27，54，86，65，2，16，38，写出用快速排序法对该序列进行升序排序的每一趟结果。16，27，2，38，65，86，54，382，16，27，38，38，54，65，8667. 对下列数据表，写出采用快速排序算法排序的每一趟的结果，并标明第一趟排序过程中的数据移动情况。（60，20，31，1，5，44，55，61，200，30，80，150，4，29）68. 设待排序文件的关键码为（512,275,908,677,503,765,612,897,154,170）以第一元素为分界元素进行快速排序（按关键码值递增顺序），请给出第一趟扫描后的结果。69. 对下列数据表，写出采用快速排序算法排序的每一趟的结果。（100，12，20，31，1，5，44，66，61，200，30，80，150，4，8）70. 已知待排序文件各记录的排序码顺序如下: 72,73,71,23,94,16,05,68，请列出快速排序过程中每一趟的排序结果。71. 初始输入序列的关键值如下：（72，73，71，23，94，16，05，68，48，19，26）试采用二路归并排序法进行从小到大的排序，写出该序列在每遍扫描时的合并过程。72，73，23，71，16，94，05，68，19，48，2623，71，72，73，05，16，68，94，19，26，4805，16，23，68，71，72，73，94，19，26，4805，16，19，23，26，48，68，71，72，73，9472. 利用堆排序的“筛选”方法将序列36，27，41，10，13，21，19，25调整为“小顶堆”。73. 将下面数据建成一个“大顶堆”（70，12，20，31，1，5，44，66，61，200，30，80，150，4，28）74. 有一个数据序列：25,50,70,100,43,7,12。现采用堆排序算法进行排序，写出每趟的结果。 75. 设有哈希函数为：H(key) = key MOD 11，哈希表的长度为11，解决冲突的方法为线性探测再散列法，关键字的输入序列为：（18，34，58，26，75，67，48，93，81），试构造此哈希表，并求出在等概率情况下查找成功和不成功时的平均查找长度。012345678910346758264893188175成功121122151不成功110987654321ASL成功=（1+2+1+1+2+2+1+5+1）/9=16/9ASL不成功=（1+10+9+8+7+6+5+4+3+2+1）/11=56/1176. 设哈希表容量为7，给定表30，36，47，52，34，散列函数H(k)=k mod 6，采用线性探测再散列法解决冲突，求（1）构造此哈希表；（2）求查找数34需要进行比较的次数77. 设有一哈希表如图所示，该哈希表用二次探测再散列法解决冲突，其哈希函数为：H(K) = K mod 13, 从该哈希表中检索出关键码35需几次比较？请写出比较顺序。01234567891011123533214810251. 35 mod 13 = 92. (9+1) mod 13 = 103. (9-1) mod 13 = 84. (9+4) mod 13 = 0 (OK)7