2022年数据结构图,查找,内排序的练习及答案参照 .pdf

《2022年数据结构图,查找,内排序的练习及答案参照 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构图,查找,内排序的练习及答案参照 .pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课后练习习题要求：此次练习不要求上交，只是帮助大家掌握知识点，便于复习。第八章图一单项选择题（20 分）1.带权有向图G 用邻接矩阵A 存储，则 Vi 的入度等于A 中_D_A. 第 i 行非的元素只和B. 第 i 列非的元素之和C. 第 i 行非且非0 的元素之和D. 第 i 列非且非0 的元素个数2.无向图的邻接矩阵是一个_A_A. 对称矩阵B. 零矩阵C. 上三角阵D. 对角矩阵3.在一个无向图中，所有顶点的度之和等于边数的_C_倍A. 1/2 B. 1 C. 2 D. 4 4.一个有 n 个顶点的无向图最多有_C_条边。A. n B. n(n-1) C. n(n-1)/2 D.

2、2n 5.对于一个具有n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵大小是_D_A. n B. 2)1(-nC. n-1 D. 2n6.一个有向图G 的邻接表存储如右图所示，现按深度优先搜索遍历，从V1 出发，所得到的顶点序列是 _B_。 A. 1 ，2，3，4，5 B. 1，2，3，5，4 C. 1，2，4，5，3 D. 1，2，5，3，4 7.对右图所示的无向图，从顶点V1 开始进行深度优先遍历，可得到顶点访问序列_A_ （提示：可先画出邻居表图再遍历）A. 1 2 4 3 5 7 6 B. 1 2 4 3 5 6 7 C. 1 2 4 5 6 3 7 D. 1 2 3 4 5 6 7

3、8.如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是_B_ A. 完全图B. 连通图C.有回路D. 一棵树9.任何一个无向连通图_B_最小生成树 （提示：注意最小生成树的定义，此题易错）A. 只有一棵B. 一棵或多棵C. 一定有多棵D.可能不存在11. 若图的邻接矩阵中主对角线上的元素全是0，其余元素全是1，则可以断定该图一定是_D_。A. 无向图B. 不是带权图C. 有向图D. 完全图二填空题1. 有 n 个结点的无向图最多有_n(n-1)/2_ 条边。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - -

4、 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - 2. 有 n 个顶点的强连通有向图G 至少有 _n-1_条弧。3. 对于一个具有n 个顶点和 e条边的无向图， 若采用邻接表表示， 则表头数组的大小为_n_，所有邻接表中的结点总数是_2e_。4. 对于 n 个顶点的无向图，采用邻接矩阵表示，求图中边数的方法是_邻接矩阵中1 的个数除以 2_,判断任意两个顶点i 和 j 是否有边相连的方法是_Aij 是否为 1_，求任意一个顶点的度的方法是_计算该行或该列中1 的个数 _。5. 对于 n 个顶点的有向图，采用邻接矩阵表示，求图中边数的方法是_

5、邻接矩阵中1 的个数_,判断任意两个顶点i 和 j 是否有边相连的方法是_Aij 是否为 1_，求任意一个顶点的度的方法是_出度为该行中1 的个数，入度为该列中1 的个数，顶点的度等于出度和入的之和 _。6. 对于 n 个顶点的无向图，采用邻接表表示，求图中边数的方法是_邻接表中结点的个数（除头结点外） 除以 2_,判断任意两个顶点i 和 j 是否有边相连的方法是_从 i 表头结点开头的链表中是否包含j 结点 _，求任意一个顶点的度的方法是_以 i 表头结点开头的链表中结点个数 _。7. 连通分量是无向图中的_极大 _连通子图。8. 一个连通图的 _生成树 _是一个极小连通子图。四. 分析题有

6、一个带权图，其邻接矩阵的数组表示如右图：试完成下列要求：（1）写出该图上从顶点1 触发进行深度优先遍历的顶点序列，并据此判断该图是否为连通图。（2）画出该图的带权邻接表（3）画出按 Kruskal 算法构造最小生成树（森林）的示意图。解答：（1）从顶点1 出发的一个深度优先遍历的顶点序列为： 1，2，3，8，7，4，5，6。据此判断该图不是连通图。（2）该图的带权邻接表如下图所示（特别注意：带权图要将权值放到结点中）（3）按 Kruskal 算法构造的生成森林为： （特别注意：下面的答案没有给过程，考试时应写过程，如果过程正确将按步骤给分，如果没有过程，结果错误扣全部分数！ ！ ）名师资料总结

7、 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - 第九章查找1. 只能在顺序存储结构上才能实现的查找方法是_B_（特别重要！ ！ ） A. 顺序查找B. 二分查找C. 树型查找D. 散列查找2. 在数据元素有序，元素个数较多而且固定不变的情况下，宜采用_A_A. 二分查找B. 分块查找C. 二叉排序树查找D. 顺序查找3. 有一个长度为12 的有序表， 按二分查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数为_B_。

8、 （提示：可借助二分查找判定树）A. 35/12 B. 37/12 C.39/ 12 D. 43/12 4. 有一个有序表R113=1,3,9,12,32,41,45,62,75,77,82,95,100 ，当采用二分查找法查找值为 82 的结点时，经 _C_次比较后查找成功（提示：二分查找判定树）。A. 1 B. 2 C. 4 D.8 5. 如右图所示的一棵二叉排序树，其查找 不成功 的平均查找长度是_A_. （提示：加方框结点表示不成功） A. 12/7 B. 28/7 C. 15/6 D. 21/6 6. 采用分块查找时，若线性表有625 个元素，查找每个元素的概率相同，假设采用顺序查找

9、来确定结点所在的块，则每块分为_B_个结点最佳。A. 9 B. 25 C. 6 D. 625 7. 设有 n 个关键字，散列查找法的平均查找长度是_A_。A. O(1) B. O(n) C. O(n2log) D. O(2n) 三. 分析题1.教材 P272的 9.2 解答：请参考相关课件2.对于关键字序列30,15,21,40,25,26,36,37, 若装填因子为0.8，采用线性探查法解决散列冲突，完成以下各题： （提示：表长=关键字个数 /装填因子）（1）设计散列函数（2）画出散列表（3）计算查找成功和查找失败的平均查找长度解答：（1）由于装填因子为0.8，关键字个数n=8，所以表长m=

10、8/0.8=10 。用除留余数法，由于表长为10，则 p=7，散列函数为H(key)=key mod 7 （2） （！ ！ ！此处给出最后结果，中间过程必须计算，否则不给全分！ ！ ）（3）(写出完整的算式给全分，只有结果的只给1/3 分数 ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - 查找成功的平均查找长度ASLsucc= （1+1+1+3+1+1+2+6 ）/8=16/8=2 查找失败的平均查找长度ASLunsucc=

11、 （9+8+7+6+5+4+3+2+1+1 ）/10=46/10=4.6 第十章内排序以关键字序列 256，301，751，129，937，863，742，694，076，438为例，分别写出执行以下排序算法的各趟排序结束时，关键字序列的状态：（1）直接插入排序（2）希尔排序（3）冒泡排序（4）快速排序（5）直接选择排序（6）堆排序（7）归并排序（8）基数排序比较各种排序算法的时间复杂度（平均情况、最坏情况、最好情况）和空间复杂度。（提示：教材 P296）例如：解答：（1）直接插入排序名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -

12、- 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - （2）希尔排序（3）冒泡排序（4）快速排序（见示例）（5）直接选择排序（6）堆排序（大根堆）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - （7）归并排序（8）基数排序名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -