数据结构第三次作业(12.6)

1、精选文档难度系数及复杂系数说明：难度系数从易到难分别为：N1、N2、N3、N4、N5复杂系数从简到繁分别为：F1、F2、F3、F4、F5数据结构第三阶段作业第6章 树和二叉树6.1 单项选择题1. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法_B_。（N2F1）A. 正确 B. 错误2. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 B 个。 （N2F1） A15 B16 C17 D473. 按照二叉树的定义，具有3个结点的不同形状的二叉树有_C_种。（N2F1）A. 3 B. 4 C. 5 D. 64. 按照二叉树的定义，具有3个不同数

2、据结点的不同的二叉树有_C_种。（N3F1）A. 5 B. 6 C. 30 D. 325. 深度为5的二叉树至多有_C_个结点。（N2F1）A. 16 B. 32 C. 31 D. 106. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_ _A_。（N3F1）A. 2h B. 2h-1 C. 2h+1 D. h+17. 对一个满二叉树，m个树叶，n个结点，深度为h，则_D_ 。（N3F1）A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h-18. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序_A_。（N3F1）A.不发生

3、改变 B.发生改变 C.不能确定 D.以上都不对9. 如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为_C_。（N3F1） A. uwvts B. vwuts C. wuvts D. wutsv6.2 简答题1. 根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分别画出。（N2F3）2. 假设一棵 二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。（N3F2）请画出该树。3. 以数据集4，5，6，7，10，12，18为结点权值，画出构造Huffman树的每一步图示，计算其带权路径长度。（N3F3）4. 一棵含有N个

4、结点的k叉树,可能达到的最大深度和最小深度各为多少? （N3F2）最大深度：h=N-k+1,最小深度：logkN+1第7章 图7.1 单项选择题1在一个图中，所有顶点的度数之和等于所有边数的_C_倍。（N3F1）A. 1/2 B. 1 C. 2 D. 4 2任何一个无向连通图的最小生成树 B 。（N3F1）A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在3在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_B_倍。（N3F1）A. 1/2 B. 1 C. 2 D. 44一个有n个顶点的无向图最多有_C_条边。（N2F1）A. n B. n(n-1) C. n(n-1)/2 D.

5、 2n5具有4个顶点的无向完全图有_A_条边。（N2F1）A. 6 B. 12 C. 16 D. 206具有6个顶点的无向图至少应有_A_条边才能确保是一个连通图。（N3F1）A. 5 B. 6 C. 7 D. 87在一个具有n个顶点的无向图中，要连通全部顶点至少需要_C_条边。（N3F1）A. n B. n+1 C. n-1 D. n/28对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是_A_。（N3F1）A. n B. (n-1)2 C. n-1 D. n29对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_A_；所有邻接表中的接点总数是_C_。

6、（N3F1） A. n B. n+1 C. n-1 D. n+e A. e/2 B. e C.2e D. n+e 10已知一个图如图7.1所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为D_B_；按宽度搜索法进行遍历，则可能得到的一种顶点序列为_。（N3F1） A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,bbaecdf图 7.1 一个无向图7.2 综合题badcef1611151515

7、16131412211请用克鲁斯卡尔和普里姆两种算法分别为图7.6、图7.7构造最小生成树： （N3F3）（1） 图7.661213212495201516106154372（2）图7.72请用图示说明图7.9从顶点a到其余各顶点之间的最短路径。（N3F3）543223356abdfce图7.93已知AOE网有9个结点：V1，V2，V3，V4，V5，V6，V7，V8，V9，其邻接矩阵如下：(1)请画出该AOE图。(2)计算完成整个计划需要的时间。(3)求出该AOE网的关键路径。（N4F4）64511297424答：(1)该AOE图为：(2)完成整个计划需要18天。(3)关键路径为：（V1，V2

8、，V5，V7，V9）和（V1，V2，V5，V8，V9，）第8章 查找8.1 单项选择题1.顺序查找法适合于存储结构为_B_的线性表。（N2F1）A. 散列存储 B. 顺序存储或链接存储C. 压缩存储 D. 索引存储2.对线性表进行二分查找时，要求线性表必须_C_。（N2F1）A. 以顺序方式存储 B. 以链接方式存储C. 以顺序方式存储，且结点按关键字有序排序D. 以链接方式存储，且结点按关键字有序排序3.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为_C_.（N3F1）A. n B. n/2 C. (n+1)/2 D. (n-1)/24.采用二分查找方法查找长度为n的线性表

9、时，每个元素的平均查找长度为_D_。（N3F1）AO（n2） B. O(nlog2n) C. O(n) D. O(log2n)5.二分查找和二叉排序树的时间性能_B_。（N2F1）A. 相同 B. 不相同6.有一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当二分查找值82为的结点时，_C_次比较后查找成功。（N3F1）A. 1 B. 2 C. 4 D. 87.设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：（N3F1）addr (15)=4; addr (38)=5; addr (61)=6; addr (84)=7如用二次探测

10、再散列处理冲突，关键字为49的结点的地址是_D_。A. 8 B. 3 C. 5 D. 98.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为_B_。（N3F1）A. 35/12 B. 37/12 C. 39/12 D. 43/129对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为 C 。（N2F1）A.从第0个元素往后查找该数据元素B.从第1个元素往后查找该数据元素C.从第n个元素往开始前查找该数据元素D.与查找顺序无关10解决散列法中出现的冲突问题常采用的方法是 D 。（N2F1）A.数字分析法、除余法、平方取中法B.数字

11、分析法、除余法、线性探测法C.数字分析法、线性探测法、多重散列法D.线性探测法、多重散列法、链地址法第9章 排序9.1 单项选择题1. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是_D_。（N2F1）A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序2. 设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用_C_排序法。（N2F1）A. 起泡排序 B. 快速排序 C. 堆排序 D. 基数排序3. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是_A_。（N2F1）A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序4.

12、 一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为_B_。（N3F1）A. 79，46，56，38，40，80 B. 38，46, 56，79， 40，84，C. 84，79，56，46，40，38 D. 84，56，79，40，46，385. 一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为_C_。（N3F1）A. 38，40，46，56，79，84 B. 40，38，46，79，56，84C. 40，38，46，56，79，84 D. 40，38，46，84，56，796. 一组记录的排序码为（25，48，16，35，79，82，23，40，36，72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为_A_。（N3F1）A. 16，25，35，48，23，40，79，82，36，72 B. 16，25，35，48，79，82，23，36，40，72C. 16，25，48，35，79，82，23，36，40，72D. 16，25，35，48，79，23，36，40，72