《[2017年整理]数据结构复习模拟题5》由会员分享，可在线阅读，更多相关《[2017年整理]数据结构复习模拟题5（3页珍藏版）》请在金锄头文库上搜索。
1、第六章 树1. 对于图 6.29 给出的树，指出树中的根结点、叶结点和分支结点。并指出各个结点的度数和层数。2. 对图 6.29 所示的树，采用先根次序、后根次序和中根次序遍历。问得到怎样的结点序列？3. 对图 6.29 所示的树，分别采用先根次序的父指针表示法、长子-兄弟表示法，试画出各种方法的图示。4. 用三个结点 A，B，C 可以构成多少种不同的二叉树？请把它们画出来。5. 将图 6.29 所示的树转换成对应的二叉树是什么样子？请把它画出来。6. 请按先根、后根和对称序遍历图 6.30 所示的二叉树，列出遍历所得的结点序列。7 请将图 6.30 所示的二叉树转换成对应的树林，并按先根次序
2、和后根次序遍历树林。8. 对于给定的一组权值w1，4，9，16，25，36，49，64，81，100 ，构造具有 Huffman 树。并求出它的带权路径长度。9 给出(a) 所示树的双亲链表表示、孩子链表表示、双亲孩子链表表示及孩子兄弟链表表示等四种存储结构，并指出哪些存储结构易于求指定结点的祖先，哪些易于求指定结点的后代？10画出下图所示的各二叉树所对应的森林。11假设用于通信的电文由字符集a,b,c,d,e,f,g,h中的字母构成，这 8 个字母在电文中出现的概率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。1) 为这 8 个字母设计 Huffman
3、 编码。26 构造连通网最小生成树的两个典型算法是_。27求图的最小生成树有两种算法，_算法适合于求稀疏图的最小生成树。28. Prim（普里姆）算法适用于求_的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求_的网的最小生成树。29克鲁斯卡尔算法的时间复杂度为_,它对_图较为适合。30对于含 N 个顶点 E 条边的无向连通图，利用 Prim 算法生成最小代价生成树其时间复杂度为_，利用Kruskal 算法生成最小代价生成树其时间复杂度为_。31 考虑下图：(1)从顶点 A 出发，求它的深度优先生成树(2)从顶点 E 出发，求它的广度优先生成树（3）根据普利姆(Prim) 算法，求它的
4、最小生成树32 已知一个无向图如下图所示，要求分别用 Prim 和 Kruskal 算法生成最小树（假设以为起点，试画出构造过程） 。33 已知图的邻接矩阵为：V1 V2 V3 V4 V5 V6 V7 V8 V9 V10V1 0 1 1 1 0 0 0 0 0 0V2 0 0 0 1 1 0 0 0 0 0V3 0 0 0 1 0 1 0 0 0 0V4 0 0 0 0 0 1 1 0 1 0V5 0 0 0 0 0 0 1 0 0 0V6 0 0 0 0 0 0 0 1 1 0V7 0 0 0 0 0 0 0 0 1 0V8 0 0 0 0 0 0 0 0 0 1V9 0 0 0 0 0 0
5、 0 0 0 1V10 0 0 0 0 0 0 0 0 0 01 4 9 10 7 6 8 3 2 51 4 3 2 9 7 6 5 10 81 4 3 2 9 7 6 5 10 8当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出：（1） 以顶点 V1 为出发点的唯一的深度优先遍历；（2） 以顶点 V1 为出发点的唯一的广度优先遍历；（3） 该图唯一的拓扑有序序列。 【同济大学 1998 一 (12 分 )】45已知一图如下图所示：（1） 写出该图的邻接矩阵；（2） 写出全部拓扑排序；（3） 以 v1 为源点,以 v8 为终点，给出所有事件允许发生的最早时间和最晚时间，并给出
6、关键路径；（4） 求 V1 结点到各点的最短距离。 【北京邮电大学 2000 五 （15 分） 】1 构造连通网最小生成树的两个典型算法是_2求图的最小生成树有两种算法，_算法适合于求稀疏图的最小生成树3 Prim（普里姆）算法适用于求_的网的最小生成树；kruskal （克鲁斯卡尔）算法适用于求_的网的最小生成树。4 克鲁斯卡尔算法的时间复杂度为_,它对_图较为适5 对于含 N 个顶点 E 条边的无向连通图，利用 Prim 算法生成最小代价生成树其时间复杂度为_，利用Kruskal 算法生成最小代价生成树其时间复杂度为_ 。6 考虑右图：(1)从顶点 A 出发，求它的深度优先生成树(2)从顶
7、点 E 出发，求它的广度优先生成树(3)根据普利姆(Prim) 算法，求它的最小生成树8 已知一个无向图如下图所示，要求分别用 Prim 和 Kruskal 算法生成最小树（假设以为起点，试画出构造过程） 。9 题9 已知连通图如下：（1） 给出本图的邻接表；（2） 若从顶点 B 出发对该图进行遍历，在（1）的基础上分别给出本图的按深度优先搜索和按广度优先搜索的顶点序列；（3） 写出按深度优先搜索的递归程序。1、什么叫串？串和字符在存储方法上有什么不同？可以用几种存储方法存储串？分别写出串的静态数组存储结构和串的动态数组存储结构的结构体定义。2、串是由字符组成的，长度为 1 的串和字符是否相同
8、。为什么？3、串是不定长的，表示串的长度有几种方法？C 语言中的串采用哪种方法？4、可以说串是数据类型固定为字符类型的线性表，但是串操作和线性表操作的主要不同之处在哪里？5、简述下列每对术语的区别：空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串。6、两个字符串 S1 和 S2 的长度分别为 m 和 n。求这两个字符串最大共同子串算法的时间复杂度为 T(m,n)。估算最优的 T(m,n)，并简要说明理由。7、设 S1 =“Data Structure Course”，S2 =“Structure”，S3 =“Base”，求：（1）Length(S1)； （2）Compare(S2, S3)；（3）Insert(S1, 5, S3)； （4）Delete(S1, 5, 9)；（5）SubString(S1, 5, 9, T)； （6）Search(S1, 0, S2)；（7）Replace(S1, 0, S2, S3)8 试利用 KMP 算法和改进算法分别求 p1=abcabaa和 p2=aabbaab的 NEXT 函数和 NEXTVAL 函数。
