数据结构例题详解ppt课件

1、数据结构考研辅导 例题详解,浙江大学计算机学院,内容提纲,自测题解答,单项选择题：在每小题给出的四个选项中，请选出一项最符合题目要求的。 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较多少个结点？ n n/2 (n-1)/2 (n+1)/2,自测题解答,某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用什么存储方式最节省运算时间？ 单链表 仅有头指针的单循环链表 双链表 仅有尾指针的单循环链表,自测题解答,设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是？ 5 1 2 3 4 4 5 1 3 2 4 3

2、 1 2 5 3 2 1 5 4,自测题解答,三叉树中，度为1的结点有5个，度为2的结点3个，度为3的结点2个，问该树含有几个叶结点？ 8 10 12 13,N1 = 5; N2 = 3; N3 = 2 N = N0 + 10 N 1 = 5*1 + 3*2 + 2*3,自测题解答,对二叉排序树进行什么遍历可以得到从小到大的排序序列 ？ 前序遍历 中序遍历 后序遍历 层次遍历,自测题解答,12个结点的AVL树的最大深度是？ 3 4 5 6,等价问题：深度为h的AVL树的最少结点数是？,自测题解答,对于一个共有n个结点、k条边的森林，共有几颗树？ n k n k + 1 n k 1 不能确定,每

3、棵有m个结点的树必有m-1条边 n = m k = m t （t是树的个数） t = ?,自测题解答,已知有向图G=(V, E)，其中V = v1, v2, v3, v4, v5, v6，E = , , , , , , , 。G的拓扑序列是? v3, v4, v1, v5, v2, v6 v1, v3, v4, v5, v2, v6 v3, v1, v4, v5, v2, v6 v1, v4, v3, v5, v2, v6,自测题解答,任何一个带权无向连通图的最小生成树 是唯一的 是不唯一的 有可能不唯一 有可能不存在,自测题解答,判定一个有向图是否存在回路，除了拓扑排序，还可以用 图的遍历

4、求最小生成树 最短路径 求关键路径,自测题解答,在图中自a点开始进行深度优先遍历算法可能得到的结果为 a, b, e, c, d, f a, e, d, f, c, b a, c, f, e, b, d a, e, b, c, f, d,自测题解答,以下哪个命题是正确的？ 对于带权无向图G = (V, E)，M是G的最小生成树，则M中任意两点V1到V2的路径一定是它们之间的最短路径。 P是顶点s到t的最短路径，如果该图中的所有路径的权值都加1，P仍然是s到t的最短路径。 深度优先遍历也可用于完成拓扑排序。 以上都不是。,自测题解答,假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散

5、列表中，至少要进行多少次探测？ k-1 k k+1 k(k+1)/2,自测题解答,就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是 堆排序 归并排序 快速排序 堆排序 快速排序 归并排序,自测题解答,下面四种排序算法中，稳定的算法是 快速排序 归并排序 堆排序 希尔排序,自测题解答,综合应用题 树中任意两结点之间都存在一条路径，两结点的距离即定义为路径的长度。距离最远的两个结点的距离定义为树的“直径”。给定一棵用二叉链表存储的二叉树，其结点构造为如图。指针Root指向根结点。请设计时间复杂度为O(n)的算法（n为树中结点的个数）求二叉树的直径。,直径 = max( 左树深度 +

6、 右树深度 ),自测题解答,int BinaryTreeHeight( tree T, int ,自测题解答,考研大纲中例题（15分） 已知一棵二叉树采用二叉链表存储。现定义二叉树中结点X0的根路径为从根结点到X0的一条路径，请编写算法输出该二叉树中最长的根路径（多条最长根路径中只输出一条即可。算法可用C或C+或JAVA语言实现）。 参考答案： 计算树的深度，同时记住最深的结点p。 然后用非递归先序遍历找到p，此时路径上的结点都在堆栈中。,自测题解答,下图中每个顶点表示一个岛，每条边表示岛屿间建桥的成本，找到一个算法计算正确的造桥方法，使得所有的岛屿都能连通，并且总的造价最小，给出这个算法的名

7、字，并给出求解过程。,求最小生成树： 普里姆(Prim)算法 或克鲁斯卡尔(Kruskal)算法。,自测题解答,假设有n个值不同数据元素存储在顺序表中，要求不经过完全排序就从中选出自小到大顺序的前m(mn)个元素，试问要如何进行才能使最坏情况下的元素间所作的比较次数最少？,改造堆排序，建立最小堆。,23,分类测试,线性表、堆栈、队列、数组 树与图 查找与排序,自测题 令P代表入栈，O代表出栈。则将一个字符串3 * a +b/c变为3 a * b c / +的堆栈操作序列是哪个？（例如将ABC变成BCA的操作序列是PPOPOO。） PPPOOOPPOPPOOO POPOPOPPOPPOOO PO

8、PPOOPPOPPOOO POPPOOPPOPOOPO,线性表、堆栈、队列、数组,自测题 从一个栈顶指针为ST的链栈中删除一个结点时，用x保存被删结点的值，则执行： x= ST; ST = ST-next; x= ST-data; ST = ST-next; x= ST-data; x= ST-data; ST = ST-next;,线性表、堆栈、队列、数组,自测题 线性表在什么情况下适用于使用链式结构实现? 需经常修改中的结点值 需不断对进行删除插入 中含有大量的结点 中结点结构复杂,线性表、堆栈、队列、数组,自测题 若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn

9、。若p1=n，则pi为： i n i n i + 1 不确定,线性表、堆栈、队列、数组,自测题 链表不具有的特点是： 插入、删除不需要移动元素 可随机访问任一元素 不必事先估计存储空间 所需空间与线性长度成正比,线性表、堆栈、队列、数组,自测题 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用哪种存储方式最节省运算时间？ 单链表 双链表 单循环链表 带头结点的双循环链表,线性表、堆栈、队列、数组,自测题 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用哪种存储方式最节省时间？ 顺序表 双链表 单循环链表 带头结点的双循环链表,线性表、

10、堆栈、队列、数组,自测题 数组A1.5,1.6每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A5,5的地址为 1140 1145 1120 1125,线性表、堆栈、队列、数组,1000 + (29 1)*5,自测题 设高为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为_，最多为_？ 2h-1 + 1, 2h 1 2h, 2h 1 2h 1, 2h 1 2h 1, 2h-1 1,树与图,自测题 设每个d叉树的结点有d个指针指向子树，有n个结点的d叉树有多少空链域？ n(d-1) n(d-1)+1 nd 以上都不是,树与图,n个结点有nd个指针

11、除了根，每个结点被1个指针所指 nd (n 1),自测题 哪种树，树中任何结点到根结点路径上的各结点值是有序的？ 堆 二叉排序树 完全二叉树 以上都不是,树与图,自测题 某二叉树的中序序列和后序序列正好相反，则该二叉树一定是 空或只有一个结点 高度等于其结点数 任一结点无左孩子 任一结点无右孩子,树与图,自测题 下面是某二叉树三种遍历的部分结果，请画出相应的二叉树。 前序: _B_F_ICEH_G 中序: D_KFIA_EJC_ 后序: _K_FBHJ_G_A,树与图,A,B,D,K,D,I,H,J,G,E,C,自测题 请设计算法求二叉树中叶结点的个数。,树与图,void countLeaf

12、(Tree T, int ,自测题 一棵二叉排序树结构如下,各结点的值从小到大依次为1-8，请标出各结点的值。,树与图,1,2,3,4,5,6,7,8,自测题 给定一个整数x，以及一个可能的查找的关键字序列 K0, , KN-1 ，请设计算法判别一个序列是否是一个可能的二叉排序树上进行的查找序列。（例如：1, 4, 2, 3 就是查找3的序列，对应二叉排序树如图。而2, 4, 1, 3就不可能是。）要求算法时间复杂度为O(N)。,树与图,答案1：先构造树，再判断是否二叉排序树,树与图,bool Is_BST_sequence( int K , int N ) if (Nkey key) Par

13、ent-rightchild = node ; else Parent-leftchild = node ; Parent = node ; return IS_BST(root, ,可以用简单的后序遍历吗？,树与图,bool IS_BST( Tree T, int* min, int* max ) if ( !T-leftchild ,树与图,答案2： bool Is_BST_sequence( int K , int N ) if(NK1) max=K0; min=MIN_ELEMENT; else max=MAX_ELEMENT ; min=K0; for( i=1; i= max |

14、Ki+1 = max | Ki+1 Ki+1 ) max = Ki; else min = Ki; if(KN-1=KN-2) return FALSE; return TRUE; ,自测题 递归地从大到小输出二叉排序树T中所有关键字不小于x的元素。,树与图,SortBST( tree T, int x ) if ( T-RightChild ) SortBST( T-RightChild, x ); if ( T-data data ); if ( T-LeftChild ) SortBST( T-LeftChild, x ); ,自测题 在有N个结点且为完全二叉树的二叉排序树中查找一个键值

15、，其平均比较次数的数量级为（）。 O(logN) O(N) O(NlogN) O(N2),树与图,自测题 给定链表表示的二叉树，判断其是否为完全二叉树。 答案1：使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。,树与图,树与图,bool JudgeComplete(BiTree T) if (!T) return true; QueueIn(Q,T); /初始化队列，根结点指针入队 while (!QueueEmpty(Q) T=QueueOut(Q); /出队 if (T-lchild ,自测题 森林的二叉树用T表示。已知T的前序和中序遍历结果，请画出对应的

16、森林 前序：A B C D E F G H I J K L 中序：C B E F D G A J I K L H,树与图,A,A,H,自测题 设一段文本中包含字符a, b, c, d, e，其出现频率相应为3, 2, 5, 1, 1。则经过哈夫曼编码后，文本所占字节数为 40 36 25 12,树与图,自测题 给定字符出现频率以及哈夫曼编码的正确长度，现对于任一套输入的编码，判断其是否哈夫曼编码。,树与图,树与图,核心部分： while (codeij != 0) if (codeij = 0) if ( !tmp-left_child ) tmp-left_child = new_node(

17、); else if (tmp-left_child-data 0) ok = false; tmp = tmp-left_child; if (codeij = 1) if ( !tmp-right_child ) tmp-right_child = new_node(); else if (tmp-right_child-data 0) ok = false; tmp = tmp-right_child; j+; if (!tmp-left_child /计算编码长度,自测题 在AOE网中，什么是关键路径？ 最短回路 从第一个事件到最后一个事件的最短路径 最长回路 从第一个事件到最后一个事

18、件的最长路径,树与图,自测题 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是？ 逆拓扑有序 拓扑有序 无序的 以上都不对,树与图,DFS: 4, 3, 2, 1,自测题 某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。要解决这个问题，问： (1) 可用什么数据结构表示城镇和道路？ (2) 请描述效率最高的算法。,树与图,答案：最小生成树；Prim,自测题 某省调查城镇交通状况，得到现有城镇道

19、路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可），并要求增设的道路条数为最少。要解决这个问题，问： (1) 可用什么数据结构表示城镇和道路？ (2) 请用伪码描述效率最高的解法。,树与图,答案：DSF数连通集个数 1,自测题 给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?,树与图,答案： 先用Floyd求任意2点间

20、最短路； 对每个村庄，求它到其他村庄的最短路中最长的； 找所有n条最长路中最短的，那个村庄就建医院。,自测题 给定现有城镇道路统计表，表中列出了每条道路直接连通的城镇以及距离。现有一镇受灾，指定另一镇救援，要求设计算法使得救援队以最快速度到达。另外，救援队每经过一镇，可以得到一个单位的救援物资。要求在最快到达的同时带去最多的救援物资。,树与图,树与图,修改 Dijkstra： if( Tv.Dist + Cvw Tw.Count ) ) Tw.Count = Tv.Count + 1; Tw.Path = v; /* DO NOT forget this */ ,自测题 设有100个元素的有序序列，如果用折半插入排序再插入一个元素，则最大比较次数是（） 25 50 10 7,查找与排序,自测题 对线性表进行二分查找时，要求线性表必须（） 以顺序方式存储 以顺序方式存储,且数据元素有序 以链接方式存储 以链接方式存储,且数据元素有序,查找与排序,自测题 散列表的地址区间为0-16,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，