数据结构-4-8章作业.doc

一、 名词解释1、二叉树：2、哈夫曼树：3、小根堆：4、最小生成树5、最短路径6、关键路径：7、拓扑排序8、二叉搜索树9、出度：10、权11、查找（包括各种主要查找方法的名称，如二分查找等）12、排序（包括各种主要排序方法的名称，如堆排序等）二、填空1、二叉树的度为： 。2、在定义各种数据结构的存储实现时，为增强其数据类型的通用性，应将其定义为 类型。如果是定义树的链接存储结构，除了定义数据类型，还应定义链接孩子结点的 和 。3、图由非空顶点集和 所组成。无向图某个顶点的度是 。4、二叉树的度为2，当深度h=4时，其满二叉树的结点树为： 。5、在选择排序方法时，在最坏或平均情况下元素移动次数越多，则说明该方法的时间复杂性 。 6、在图的概念中路径长度是指该路径上经过的边的 ，而某条边上标有的数值称之为该边的 。7、同一棵树中的数据元素必须是 的。8、对有向图来说，出度是指某个顶点 。9、二叉搜索树是指树上所有 结点均大于 ，同时左右子树又各是一棵二叉搜索树。10、在定义各种数据结构的存储实现时，如果数据元素的数据域是记录类型的使用C+语言进行数据域定义时应使用 命令。11、在计算机中若采用索引查找，索引表中的每个索引项应至少包含 和 两个域。三、选择题1、一个广义表A（B（a, （b, c,（）,d）,C（e ，F（）此广义表的深度为（ ）A3 B. 4 C. 5 D. 62、当用AOE（即边表示活动的网络）时，为求得关键路径，我们根据每项活动的“最早开始时间”和“最迟发生时间”之差定为“开始时间余量”，当此值为（ ）时的活动为关键活动，由关键活动所形成的从源点到汇点的每一条路径称为关键路径。A0 B.最小值 C. 最大值 3、在计算机领域，磁盘上的目录结构就是一棵树，对于这种数据结构，在查找时采用哪种方法较好？（ ）顺序查找 B.二分查找 C. 索引查找 D. 散列查找4、一个广义表形式的二叉树A（B,C（，D）此二叉树的深度为 （ ）A1 B.2 C. 3 D. 45、图的路径长度是指（ ） 。A该路径上经过的边的数目 B 图中所有的边C图中所有的边上权之和 D图中所有的边之和6、如果有一棵完全二叉树上的结点数是9，那么这棵二叉树的最大深度是（ ）A2 B3 C4 D57、对具有n个元素的有序表采用二分查找，则算法的时间复杂度是（ ）。AO(n) BO(n2) CO(1) DO(lbn)8、若根据数据集合23，44，36，48，52，73，64，58建立散列表，采用h(K)=K%7计算散列地址，并采用链接法处理冲突，则元素64的初始散列地址为（ ）。A4 B8 C12 D139、若根据数据集合23，44，36，48，52，73，64，58建立散列表，采用h(K)=K%7计算散列地址，则同义词元素的个数最多为（ ）。A2 B3 C4 D510、在散列查找中，平均查找长度主要与（ ）有关。A散列表程度 B散列元素的个数 C装填因子 D冲突处理方法四、有一棵树，以图形表示法如下：ABCD要求：1、以广义表表示： A（B，C（，D）。2、此树的深度是： 。3、写出中序遍历的结果： 。4、画出链接存储方式。5、如果以C结点为根（不考虑A、B），开始代入求深度的算法，写出递归过程。五、有一个带权无向图G如下0228 11542 16519 5243要求1：写出顶点数组和邻接矩阵。要求2：利用普里姆算法求出图的最小生成树（不要求编写算法），画出对应的图形，填写最小生成树生成过程中顶点集U、最小生成树的边集TE、以及LW的变化过程，画出每一次对应的图形变化过程。根据最小生成树填写边集数组CT的内容。要求3：利用可卢斯卡尔生成最小生成树，并写出生成过程中最小生成树的顶点集、边集的变化过程。答2：(0) 第0次U TE= LW= (1) 第1次U TE= LW= (2) 第2次U TE= LW= (3) 第3次U TE= LW= (4) 第4次U TE= LW= (5) 第5次U TE= LW= CT01234fromvexendvexweight六、有一个带权图如下02711 13 4652176922 3 3要求1：给出顶点数组和邻接表。要求2：利用狄克斯特拉算法求出从0点到其余各顶点的最短路径，画出对应的图形，并给出相应的分析过程中s 、dist 、path 数组值的变化过程。 (1) 初始状态：012345sdistpath(2) 得到 ：012345s1dist0path(3) 得到 ：012345s1dist0path(4) 得到 ：012345sdistpa