计算机数据结构习题2附答案.

1、第六章图1、填空题一个有n个结点的无向图中，所有顶点的度数之和等于所有边数之和的 _2_ 倍。一个有n个结点的强连通图，最多有_n（n-1_/2条边，最少有_n-1_条边。在一个无向图中，所有顶点的度数之和等于所有边数之和的 _2咅。2、判断题1无向图的邻接矩阵一定是对称矩阵。（V2有向图的邻接矩阵一定是对称矩阵。（X3图的深度优先搜索路径是唯一的。（X4图的广度优先搜索路径不是唯一的。（V5一个图可能存在多棵最小生成树。（V6无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的。（V7图的关键路径是指从源点到汇点的最短路径。（X8用邻接矩阵法存储图，占用的存储空间数量只与图中边数有关

2、，与结点个数无 关。（X9对一个图分别进行深度优先搜索和广度优先搜索，得到的结点序列一定是相同 的。（X10图的关键路径是指从源点到汇点的最长路径。（V3、选择题1一个无向连通图的生成树是含有该连通图的全部顶点的A、极小连通子图B、极小子图C、极大连通子图D、极大子图2具有e条 边的有向图，它的邻接表中有_D_个弧结点。A、e-1 B、2e C、2(e-1 D、e3如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是_D_A、无向图B、完全图C、强连通图D、有向无环图4顶点个数为n的有向图最多有_D_条弧。A、n-1 B、n(n-1/2 C、n(n+1/2 D、n(n-1应用题：1.请给

3、出图1的所有最小生成树。(10分图1共两棵第一棵为：(5分错一条边扣1分第二棵为:（5分错一条边扣1分2.请给出图2的所有拓扑排序序列。（16第一个:abcdefgh （错一个字符扣1分第二个:abcdegfh （错一个字符扣1分3、对于有向无环图（如图3,写出它的所有不同的拓扑有序序列。（共16分ACJD-序列为：1、3、2、4、5、6、7、84. 已知某图采取如图2所示的邻接矩阵表示法，请回答下列问题。（共12分ACDEBclPT图4（1请画出该图。（6分（2对其从顶点A开始进行深度优先遍历，写出遍历序列。（6分（1请画出该 图。（6分错一个结点扣1分。（2对其从顶点A开始进行深度优先遍历

4、，写出遍历序列。（6分,错一个字符扣1分序列为:ABDECF 5、（本题总计7分构造该图的最小生成树。4E?Disi2jV12Vp v4V, J v2Vp v4, V:, V37图的最小生成树如下-母条边1分，共7分Disi2712V" VV|t v4t v:Vr v4, Vp v3|76用迪杰斯特拉（Djkstra算法求从顶点V 1到其它各顶点间的最短路径，要求写出求解过程7、V4V, v4, v2Dist2|Dis<31Dist4129v48V, Vz®v4t V：t V.185第七章内部排序平均時向型臬度辅助空IB直接抽入排序0( n2)0(1)稳足的希尔排序O

5、(nL3)ou)不稳定的r按选抒拮序O(n2)0(1)不稳定的堆排序O(nlcg2n)0(1)不稳定的冒泡排序O(n2)0(1)稳宦的快速排序OfnlogJn)0( log2n>彳;憶定的归井排序O(nlog2n)0( n)稳定的1、填空题1快速排序和堆排序的平均时间复杂度分别为 和。2假定一组数据的关键字为46,79,56,38,40,84,则以第一个记录为基准点，对其进行第一趟快速排序的结果为 40,46,38,56,79,842、选择题1下面给出的四种排序法中（排序法是不稳定性排序法。A 插入B 冒泡C二路归并D 堆排序2从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比

6、较，然后将其放在已排序序列的合适位置，该排序方法称为_A_排序法。（A插入（B选择（C希尔（D二路归并3设一组初始记录关键字序列（5, 2, 6, 3, 8, 10, 11以d=3进行一趟shell排序的 结果为（A oA、 3, 2, 6, 5, 8,10,11 B、 3, 5, 11,2, 8, 6, 10C、2, 3, 5, 6, 8, 10, 11 D、 6, 3, 11, 10, 5, 2, 84若对n个元素进行直接插入排序，在进行第i趟（2 < i排序时,为寻找插入位 置最多需要进行_C次元素的比较。A、i+1 B、i-1 C、i D、13、判断题1从平均性能而言，快速排序最

7、佳，其所需时间最省。（x2快速排序属于交换排序，待排序序列越乱，快速排序效率越高，但它是不稳定 的。（V4、应用题1. 对于关键字序列49, 38, 65, 97, 76, 13，回答下述问题。（共6分（1写出一趟冒泡排序的结果。（3分（2写出一趟快速排序的结果。（3分参考答案如下：（1写出一趟冒泡排序的结果。（6分38,49,65,76,13,97 （2）写出一趟快速排序的结果。（6分）13,38,49,76,97,65第八章查找1、填空题1）对一个有100个元素的顺序表，进行折半查找法 时，在查找成功的情况下，最大比 较次数是_7_ o 2）对线性表进行折半查找 时，要求线性表必须 顺序存

8、储有序o 2、判断题1）同一组关键字，输入的序 列顺序不同，不影响其产生二叉排序树的形态。（ 2 ）对一棵二叉排序树进行中序遍历能得到从小到大的有序序列。（V） 2、选择题1.若在线性表中采用二分查找法查找元素，该线性表应该（C o A元素按值有序B采用顺序存储结构 C.元素按值有序，且采用顺序存储结构 D元素按值有序，且采用链式存储结构2. 对二叉排序树进行_B历，可以得到该二叉树所有结点构成的有序序列。（A前序（B中序（C后序（D按层次3.利用逐点插入法建立序列（51, 71, 43，81， 74, 20，34, 45, 64, 30对应的二叉排序树 以后，查找元素34要进行（A元素间 的

9、比较。A. 4次B . 5次C. 7次D . 10 4.散列函数有一个共同性质，即函数值应 按（D取其值域的每一个值。A.最大概率B.最小概率C.同等概率D.平均概率5.一个哈希函数被认为是好的”，如果它满足条件A o （A哈希地址分布均匀（B保证不产生冲突（C所有哈希地址在表长范围内（D满足（B和（C 6.平均查找长度最 短的查找方法是 c o （A）折半查找（B）顺序查找（C）哈希查找（4）其他7、以下二叉树中不属于平衡二叉树的是 _A_o A、二叉排序树B、完全二 叉树C、满二叉树D、堆3、判断题1）哈希表是一种根据哈希函数来计算存储地 址的查找表，因此不能存在函数值相同的关键字。（X）

10、 2）对于折半查找，其前提条件是待查找序列只要是有序的即可。（X 3）对线性表进行折半查找时，要求线性表必须是有序的顺序表或链表。（X 3、应用题1、若一棵排序二叉树的关键字输入序列为80, 6, 10, 7, 8, 25, 100, 90，请画出 该二叉树。解： 二叉排序树为：（16分，每个结点2分）80 6 100 10 90 7 25 8 2 已知一组关键字为1,14,27,29,55,68,10,11,23,则按哈希函数H（key=key MOD 13和链地址法处理冲突来构造哈希表。（1）画出所构造的哈希表。（2）在记录的查找概率相等的前提下，计算该表查找成功时的平均查 找长度。（1）画出所构造的哈希表。0 1 2 3 4 5 6 7 8 9 10 11 12A A A A A AA 10 11 A 23 A A 29 55 68 A A 1 14 27 A 9 个结点，每个 1 分（2 ）在记 录的查找概率相等的前提下，该表查找成功时的平均查找长度，ASL =（1+2+3+1+2+3+1+2+1） /9=16/9 2 分 3、一个线性表为 B= （12，23，45，57, 20，3，78, 31，15, 36），设散列表为 H0.12