《数据结构》――应用题复习概要2022年4月1.写出执行下列程序段时，语句S的执行次数。
for (i=1; i<n; i++)for (j=n; j>=i; j--)S;2.假设n为2的乘幂，并且n>2，试求下列算法的时间复杂度及变量count的值（以n的函数形式表示）int Time(int n){ int count:=0; x:=2;while (x<n/2){ x:=2*x; count:=count +1 };return (count);}3.已知双向链表、指针P、Q所指的结点和结点的结构（数据域DATA、指针域LL及RL），分别画出经过下述算法后的双向链表。
(1)Q->RL = 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）。
XSXXSXXSSSXXSS6.一棵二叉树的结点数采用顺序存储结构，存于下列数组T中，画出该二叉树。
b7.已知一棵树的双亲表示如下，其中各兄弟结点依此排列，试画出该树及对应的孩子兄弟表示的二叉树。
1 2 3 4 5 6 7 8 9 10 11 12 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 FLMGN HOIJ8.有一个完全二叉树按层次顺序存放在一维数组中，如下所示：请指出结点P的父结点，左子女，右子女。
9.将下列二叉链表改为先序线索链表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 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，中序遍历为CBDAGFHEI。
画出此二叉树并写出其先序遍历序列。
AB EC F IDG H12.一棵二叉树的先序序列和中序序列分别如下，画出该二叉树并写出它的后序遍历的序列。
先序序列：ABDEHCFIG 中序序列：DBHEAFICG后序遍历为DHEBIFGCA13.已知一棵二叉树的中序遍历为DBHEAFICG，后序遍历为DHEBIFGCA。
画出此二叉树并写出其先序遍历序列。
先序遍历：ABDEHCFIG14.一棵二叉树的先序序列和中序序列分别如下，画出该二叉树的中序线索二叉链表。
先序序列：ABCDEFGHIJ 中序序列：CBEDAGHFJI15.一棵二叉树的先序序列和中序序列分别如下，画出该二叉树的二叉链表。
先序序列：ABDFCEG 中序序列：BFDAEGCAF16.一棵二叉树的先序、中序和后序序列分别如下，试求出空格处的内容，并画出该二叉树。
先序：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.对下面的两棵树，分别画出其顺序存储结构。
A B D I J E K C F G A B D E I J C F20.一棵二叉树的结点数据采用顺序存储结构，存储于下列数组T中，画出该二叉数。
T e a f d g c j l h b21.用权分别为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=60IAB CD E F GJ KAB CD E FJI271116624597D A C B E1111A: 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，试设计赫夫曼编码。
201829.设有带权无向图如右图所示(1)请写出该图的邻接矩阵。
(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，分别写出从V0，V5出发的深度优先和广度优先的遍历序列。
深度：0 1 3 4 2 5 65 3 0 16 2 4广度：0 1 2 3 4 6 55 3 46 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 ^2 4 ^V4 0 00 0 0 0 3 C4V5 0 0 1 1 0 1 4 C5V6 0 0 0 0 0 0 5 C6^34.有向图G的邻接表如右上所示，若在图中增加弧<C1,C6>和<C6,C1>，该邻接表需做何种修改？（可直接在给出的邻接表上修改）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.求出下图的一棵最小生成树。
39.已知图的邻接矩阵如下，（1）试画出其邻接表；（2）若在它的邻接表存储结构中，每个顶点的邻接点序号是从小到大链接，写出以顶点V1为出发点的唯一的深度优先遍历序列。
2 51 3 6 84 76754854358536⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡010000000100100000100000011100001110654321V V V V V VV1V2V3V6V5V440. 画出以顶点V1为初始源点遍历下图所得到的DFS 和BFS 生成森林V1V3 V4 V2 V5 V6 V7 V841. A B C D E F V00 1 0 1 0 1 1 0 1 0 0 0 V1 0 1 0 1 1 1 1 0 1 0 0 0 V2 0 0 1 0 0 1 1 0 1 0 1 0 V342. 已知图的邻接表如上所示，根据邻接表写出从V 0出发的深度优先和广度优先遍历序列。
43. 画出根据Prim 算法对下列连通网从顶点A 出发构造其最小生成树的过程。
A B6 23 8 5 G 4 E 12 C7 25 15 10 F D44. 下图表示一个地区的交通图，顶点表示城市，边表示城市间的公路，边上的数值（权）表示修建公路的代价，要求从顶点A 出发构造能连通每个城市且总代价最低的5条公路。
2 13 ^0 2 ^ 3 0 1 ^20 ^2018AEDC BF2346845.求出下图的最小生成树。
46.请画出左下带权图的一棵最小生成树。
47.如右上有向图中，顶点表示课程，弧表示课程间的先后次序，例如弧<C1,C3>表示先学习课程C1再学习课程C3，如果某人每次只能学习一门课程则它应该如何安排学习？48.给出左下图的所有拓扑序列。
49. 请写出右上图所有可能的拓扑序列。
50. 设有向图G ＝（V ，E ），V ＝{1，2，3，4，5，6}，E ＝{<1，2>，<1，3>，<2，5>，<3，6>，<6，5>，<5，4>，<6，4>}。
