1、数据结构 应用题1数据结构应用题复习概要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 =
2、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 中，画出该二叉树。数据结构 应用题2b7. 已知一棵树的双
3、亲表示如下，其中各兄弟结点依此排列，试画出该树及对应的孩子兄弟表示的二叉树。1 2 3 4 5 6 7 8 9 10 1112 13 14 15Data A B C D E F G H I J K L M N OParent 0 1 1 1 2 2 3 3 4 4 5 6 6 7 8ABE CDK FLMGNHOIJ8. 有一个完全二叉树按层次顺序存放在一维数组中，如下所示：请指出结点 P 的父结点，左子女，右子女。数据结构 应用题39. 将下列二叉链表改为先序线索链表1 2 3 4 5 6 7 8data A B C D E F G HLTag 0 0 1 0 1 0 0 0lchild 2
4、 4 0 7 0 0 0 0RTag 0 0 0 0 1 0 0 0rchild 3 5 6 8 0 0 0 010. 下表给出用带二个标识的按先序遍历进行顺序存储的二叉树，对于结点 k，规定：ltag(k)=0，k 有左孩子；ltag(k)=1，k 无左孩子；rtag(k)=0 ，k 有右孩子；rtag(k)=1 ，k无右孩子。1 2 3 4 5 6 7 8 9 10ltag 0 0 1 1 1 1 0 1 0 1data A G E I D J H C F Brtag 0 0 0 1 0 1 0 1 1 111. 已知一棵二叉树的后序遍历为 CDBGHFIEA，中序遍历为 CBDAGFHE
5、I。画出此二叉树并写出其先序遍历序列。AB EDCFIGH12. 一棵二叉树的先序序列和中序序列分别如下，画出该二叉树并写出它的后序遍历的序列。先序序列：ABDEHCFIG 中序序列：DBHEAFICG数据结构 应用题4后序遍历为 DHEBIFGCA13. 已知一棵二叉树的中序遍历为 DBHEAFICG，后序遍历为 DHEBIFGCA。画出此二叉树并写出其先序遍历序列。先序遍历：ABDEHCFIG14. 一棵二叉树的先序序列和中序序列分别如下，画出该二叉树的中序线索二叉链表。先序序列：ABCDEFGHIJ 中序序列：CBEDAGHFJI15. 一棵二叉树的先序序列和中序序列分别如下，画出该二叉
6、树的二叉链表。先序序列：ABDFCEG 中序序列：BFDAEGCAB CDFEG16. 一棵二叉树的先序、中序和后序序列分别如下，试求出空格处的内容，并画出该二叉树。先序： 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 数据结构 应用题5中序序列 BDE C AG F H后序序列 E DC B G
7、H F A18. 已知一棵二叉树的层次遍历序列为 ABCDEFGHIJ，中序遍历序列为 DBGEHJACIF，请画出该二叉树。19. 对下面的两棵树，分别画出其顺序存储结构。A B D I J E K C F G A B D E I J C F20. 一棵二叉树的结点数据采用顺序存储结构，存储于下列数组 T 中，画出该二叉数。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21T e a f d g c j l h b21. 用权分别为 2，3，6，7，8 次序的叶子结点构造一棵哈夫曼树（结点标出权值） ，若叶子结点次序改为 8，7，6，3
8、，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=60IAB CD E F GJ KAB CD E FJI数据结构 应用题627116624597
9、DACBE00001A: 001B: 10C: 01D: 000E: 1126. 给定权的集合5，29，7 ，8，14，23，3，11 ，构造相应哈夫曼树。WPL=104+75+92=27127. 画出根据 Prim 算法对下列连通网从顶点 A 出发构造其最小生成树的过程。A B6 23 8 5G 4 E 12 C7 25 15 10F D28. 已知某系统在通信联络中可能出现 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，试设计赫夫曼编码。2018数据结构 应用题729. 设有带权无向图如右图所示(1)
10、 请写出该图的邻接矩阵。(2) 请画出该图的邻接表。(3) 列出从顶点 1 出发深度优先遍历该图所得到的一个顶点序列。(4) 列出从顶点 1 出发广度优先遍历该图所得到的一个顶点序列。(5) 请画出该图的一棵最小生成树。30. 已知图 G 的邻接矩阵如下，分别写出从顶点 A 出发的深度优先和广度优先搜索序列。A B C D EA 0 1 1 1 0B 0 0 1 0 1C 0 0 0 1 0D 0 0 0 0 0E 0 0 0 0 031. 如右图所示有向图 （1）写出邻接矩阵 （2）求出其最小生成树32. 已知图的邻接矩阵如下，图的顶点依此为 V0,V1,V2,V3,V4,V5,V6，分别写
11、出从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 为出发点的广度优先搜索序列和深度优先搜索序列。V1 V2 V3 V4 V5 V6V1 0 1 0 1 1 0 0 C1V2 0 0 1 0 1 0 1 C2V3 0 0 0 0 0 1 2 C31 2 5 5 25 4 数据结构 应用题8V4 0 0 0 0 0 0 3 C
12、4V5 0 0 1 1 0 1 4 C5V6 0 0 0 0 0 0 5 C6 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（如左下图所示） ，从 V
13、6 出发构造最小生成树。37. 已知一有向图 G 的链接表存储结构如右上所示，画出有向图，并写出从结点 V1 出发的深度优先遍历结点序列。38. 求出下图的一棵最小生成树。39. 已知图的邻接矩阵如下， （1）试画出其邻接表；（2）若在它的邻接表存储结构中，每个顶点的邻接点序号是从小到大链接，写出以顶点 V1 为出发点的唯一的深度优先遍历序列。2 51 3 6 84 76754854358536数据结构 应用题9010010654321VV V1V2V3V6V5V440. 画出以顶点 V1 为初始源点遍历下图所得 到的 DFS 和 BFS 生成森林V1V3 V4 V2V5V6 V7 V841.
14、 已知图的邻接矩阵如下所示，画出从顶点 A 出发图的 DFS 和 BFS 生成树。A B C D E F0 1 0 1 0 1 V01 0 1 0 0 00 1 0 1 1 1 V11 0 1 0 0 00 0 1 0 0 1 V21 0 1 0 1 0 V342. 已知图的邻接表如上所示，根据邻接表写出从 V0 出发的深度优先和广度优先遍历序列。43. 画出根据 Prim 算法对下列连通网从顶点 A 出发构造其最小生成树的过程。A B6 23 8 5G 4 E 12 C7 25 15 10F D44. 下图表示一个地区的交通图，顶点表示城市，边表示城市间的公路，边上的数值（权）表示修建公路的代价，要求从顶点 A 出发构造能连通每个城市且总代价最低的 5 条公路。2 1 3 0 2 3 0 1 2 0 2018数据结构 应用题10AEDC BF2346845. 求出下图的最小生成树。46. 请画出左下带权图的一棵最小生成树。47. 如右上有向图中，顶点表示课程，弧表示课程间的先后次序，例如弧表示先学习课程 C1再学习课程 C3，如果某人每次只能学习一门课程则它应该如何安排学习？48. 给出左下图的所有拓扑序列。
