数据结构总复习1・模式串t='abcaabbcabcaabdab',求该模式串的next数组和nextval数组的值。
2.求模式串P=4abaabcac,的next函数值和nextval函数值序列。
3.已知一•棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,画出该二叉树，并写出后序遍历序列。
4•某二叉树中序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E。
闹岀该二叉树，并写出先序遍历序列。
5.已知一个森林的先序序列和后序序列如下，请构造出该森林。
先序序列：ABCDEFGHIJKLMNO后序序列：CDEBFH1JGAMLONK6.一棵二叉树的先序、中序、后序序列如下，其屮一部分未标出，请构造出该二叉树。
先序序列：__CDE_GHI_K中序序列：CB__FA_JKIG后序序列:_EFDB_JIH_A7.一棵二叉树的先序、中序和后序序列分别如下，其中冇一部分为显示出来。
试求出空格处的内容，并画出该二叉树。
先序序列:_B F ICEH G中序序列：D KFIA EJC后序序列：K FBH J G A8.已知一棵二叉树的先序中序和后序序列如下，其屮空缺了部分，请画出该二叉树。
先序：_BC_EFG_IJK_中序：CBED_GAJ_H_L后序：_E_FD_J_L_HA9.已知含打8个结点的一减二叉树，按先序、屮序、后序进行遍历后，冇些结点序号不清楚如下图示。
要求构造出一棵符合条件的二叉树。
先根序遍历_23_5_78中根序遍历3 _4 1 _ 7 8 6后根序遍历_42__65 110.设冇正文MNOPPPOPMMPOPOPPOPNP,字符集为M, N, O, P,设计一套二进制编码，使得上述正文的编码最短。
11.给定一组数列(15,& 10,21,6,19,3)分别代表字符A,B,C,D,E,F,G出现的频度, 试叙述建立哈夫曼树的算法思想，画岀哈夫曼树，给出各字符的编码值，并说明这种编码的优点。
12.假设用于张信的电文由字符集｛a,b,c,d,e,f,g｝中的字母构成。
它们在电文屮岀现的频度分另IJ 为｛0.31,0.16,0.10,0.0&0.11 ,,0.20,0.04｝,1)为这7个字母设计哈夫曼编码；2)对这7个字母进行等长编码，至少需要几位二进制数？哈夫曼编码比等长编码使电文总长压缩多少？13.试构造一棵二叉树，包含权为1,4,9,16,25,36,49,64,81,100等10个终端结点, 口具有最小的加权路径长度WPLo14.已知无向图如下所示：(1) 给出从VI 开始的广度优先搜索序列; (2) Iffli 岀它的邻接表；(3) 画出从VI 开始深度优先搜索生成树。
15. 已知一个无向图如卜•图所示，要求分别用Prim 和Kruskal 算法生成最小树 (假设以①为起点，试画岀构造过程)。
0 110 0 10 12 0 110 0 3 0 2 0 0 1 0 0 3 1 0 0 0 0 1 117. 已知世界六大城市为：北京(Pe)、纽约(N)、巴黎(Pa)、 伦敦(L)、东京(T)、墨 西哥(M), F 表给定了这六大城市之间的交通里程：枇界六人城市交通里程表(单位:百公里)IT ：N PA L T M PE10982 81 21 124 N 1095855 108 32 PA 82 58397 92 L 81 55 39589 T21 108 97 95113M124329289113(1) .画出这六人城市的交通网络图； (2) .価出该图的邻接表表示法； (3) .画出该图按权值递增的顺序来构造的最小(代价)生成树.18. 试利用Dijkstra 算法求下图中从顶点a 到其他个顶点间的最短路径，写出执行算法过 程屮各步的状态。
16.-带权无向图的邻接矩阵如下图，试画出它的一棵最小生成树O\0 0 0 1 1 0丿19. 已知一图如下图所示：（1） 写出该图的邻接矩阵； （2） 写出全部拓扑排序；（3） 以vl 为源点，以为终点，给岀所有事件允许发生的最早时间和最 晚吋间，并给出关键路径；（4） 求VI 结点到各点的最短距离。
20. 写出下图所有不同的拓扑有序序列。
21・对有五个结点｛ A,B,C,D,E ｝的图的邻接矩阵,100 30 00 10 co 0 oc0000co 60 0 20 ooGO10 OC 0 00 coOC oc 50 0（1）画出逻辑图;(2) 画出图的邻接表、逆邻接表、十字链表存储；(3) 基于邻接矩阵写岀图的深度、广度优先遍历序列； (4) 计算图的关键路径。
22. 对图示的AOE 网络，计算各活动弧的e 佝)和1(缶)的函数值，各事件(顶点) 的ve (Vj)15和vl(Vj)的函数值，列出各条关键路径。
23.设哈希表a、b分别用向量a[0..9], b[0..9]表示,哈希函数均为H (key) =key MOD 7,处理冲突使用开放定址法，在哈希表a中用线性探测再散列法，在哈希表b屮用二次探测再散列法，试将关键字｛19,24, 10,17,15,38,18,40｝分别填入哈希表n,b中，并分别计算出它们的平均查找长度ASLo24•设一组数据为｛1,14,27,29,55,68,10,11,23｝,现采用的哈希函数是H(key)二key MOD 13,即关键字对13取模,冲突用链地址法解决，设哈希表的大小为13(0..12), 试画出插入上述数据后的哈希表。
25・设哈希函数H (k) =3Kmod 11,散列地址空间为0〜10,对关键字序列(32,13,49,24,3&21,4,12)按下述两种解决冲突的方法构造哈希表(1)线性探测再散列(2)链地址法，并求出等概率下查找成功平均查找长度ASL。
26.用序列(46,88,45,39,70,58,101,10,66,34)建立一个排序二叉树，画出该树。
27.依次输入表(30,15,2&20,24,10,12,68,35,50,46,55沖的元素，生成一棵二叉排序树(1)试画出生成之后的二叉排序树；(2)对该二叉排序树作屮序遍历，试写出遍历序列；28.试画出从空树开始，出字符序歹ll(t,d,e,s,u,g,b,j,a,k,i*,i)构成的二叉平衡树，并为每一次的平衡处理指明旋转类型。
29•假定对冇序表：(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找，试回答下列问题：(1)画出描述折半查找过程的判定树；(2)若查找元索54,需依次与那些元索比较？(3)若杳找元素90,需依次与那些元素比较？(4)假定每个元素的查找概率相等，求查找成功时的平均查找长度。
30.设待排序的记录共7个，排序码分别为8, 3, 2, 5, 9, 1, 6。
(1)用直接插入排序。
试以排序码序列的变化描述形式说明排序全过程(动态过程)要求按递减顺序排序。
(2)用直接选择排序。
试以排序码序列的变化描述形式说明排序全过程(动态过程)要求按递减顺序排序。
31・对下面数据表，写出采用SHELL排序算法排序的每一趟的结果，并标出数据移动情况。
(125, 11, 22, 34, 15, 44, 76, 66, 100, 8, 14, 20, 2, 5, 1)。
(增量45,3,2,1)32.对给定文件(28, 07, 39, 10, 65, 14, 61, 17, 50, 21)选择第一个元素28进行划分，写出其快速排序笫一遍的排序过程。
33・设记录的关键字集合K二{23, 9, 39, 5, 68, 12, 62, 48, 33},给定的增量序列D={4, 2, 1},请写出对K按"SHELL方法”排序吋各趟排序结束时的结杲；若每次以表的第一元素为基准(或枢轴)，写出对K按“快速排序方法” 排序时，各趟排序结束时的结果。
34.已知一关键码序列为:3, 87, 12, 61, 70, 97, 26, 45。
试根据堆排序原理，填写完整下示各步骤结果。
建立堆结构：_________________交换与调整：(1) 87 70 26 61 45 12 3 97; (2) ____________________ ;(3)61 45 26 3 12 70 87 97; (4) ____________________ ;(5)26 12 3 45 61 70 87 97; (6) ____________________ ;(7) 3 12 26 45 61 70 87 97;35.根据给定的关键字集合(20, 15, 40, 35, 45, 25, 50, 30, 10)顺序输入①构造一棵完全二叉树；②画出整理好的一棵堆树；③画出一棵输出一个排序记录后的二叉树；④画出重新调整好的堆树。
36.已知待排序的序列为(503, 87, 512, 61, 908, 170, 897, 275, 653, 462), 试完成下列各题。
(1)根据以上序列建立一个堆(画出笫一步和最后堆的结果图)，希望先输出最小值。
(2)输岀最小值后，如何得到次小值。
(并画出相应结果图)37.给出一组关键字:29, 18, 25, 47, 58, 12, 51, 10,分别写出按下列各种排序方法进行排序时的变化过程：(1)归并排序(每归并一次书写一个次序)。
(2)快速排序(每划分一次书写一个次序)。
(3)堆排序(先建成一个堆，然后每从堆顶取下一个元索后，将堆调整一次)。
38.有下表所列软件课程，请画出表示课程之间优先关系的有向图(AOV・网), 并得到该有向图的拓扑有序序列。
(10分)AOV-IM：拓扑有序序列:（CiC2，C3，C4, C5）或（C“ C2，C4, C3，C5）或（Ci，C4，C2，C3，C5）。