数据结构与算法(习题)

第六章图

若一个有向图的邻接距阵中，主对角线以下的元素均为零，则该图的拓扑有序序列（）。

A. 存在
B. 不存在
下面关于求关键路径的说法不正确的是（）。

A. 求关键路径是以拓扑排序为基础的
B. 一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C. 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D. 关键活动一定位于关键路径上
图中有关路径的定义是（）。

A. 由顶点和相邻顶点序偶构成的边所形成的序列
B. 由不同顶点所形成的序列
C. 由不同边所形成的序列
D. 上述定义都不是
下列说法不正确的是（）。

A. 图的遍历是从给定的源点出发每一个顶点仅被访问一次
B. 遍历的基本算法有两种:深度遍历和广度遍历
C. 图的深度遍历不适用于有向图
D. 图的深度遍历是一个递归过程
设无向图的顶点个数为 n，则该图最多有（）条边。

A. n-1
B. n(n-1)/2
C. n(n+1)/2
D. 0
E. n2
(判断题) 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（）
有向图中顶点 V 的度等于其邻接矩阵中第 V 行中的 1 的个数。（）
需要借助于一个队列来实现 DFS 算法。（）
广度遍历生成树描述了从起点到各顶点的最短路径。（）
最小生成树问题是构造连通网的最小代价生成树。（）
连通图上各边权值均不相同，则该图的最小生成树是唯一的。（）
不同的求最小生成树的方法最后得到的生成树是相同的。（）
拓扑排序算法把一个无向图中的顶点排成一个有序序列。（）
在表示某工程的 AOE 网中，加速其关键路径上的任意关键活动均可缩短整个工程的完成时间。（）
在 AOE 图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。（）
（简答题）根据邻接表写遍历序列
按照Prim方法，从顶点1 出发，求该网的最小生成树的产生过程
按照Kruskal方法，求该网的最小生成树的产生过程
根据 AOE 网，求关键路径
Dijkstra算法

第七章查找

（简答题）已知键值序列为{38，47，59，4，40，25，20，22}。按照给定的顺序输入构造一棵平衡二叉排序树，画出所建的平衡二叉排序树。
已知键值序列为{38，47，59，4，40，25，20，22}。（1）按照给定的顺序输入构造一棵二叉排序树，画出所建的二叉排序树；并计算在等概率的情况下查找成功的平均查找长度；（2）画出在所建的二叉排序树中删除47后的二叉排序树.
设键值集合为{32，50，26，88，49，89，55，60，75}，散列函数为h(x) = x % 13,表长为13。采用链地址法解决冲突时，请画出相应的散列表；查找55、75各要比较多少次
设键值集合为{32，50，26，88，49，89，55，60，75}，散列函数为h(x) = x % 13,表长为13。采用平方探测再散列法解决冲突，请画出相应的散列表；查找55、75各要比较多少次？计算在等概率的条件下查找成功的平均检索长度？
设有一组关键字{6，13，16，18，19，25，26，30，45，58，67，74，88，91，118，124，137}，采用二分查找，（1）画出折半查找的二分查找判定树；并计算在等概率情况下查找成功的平均查找长度ASL；（2）查找失败最多需要比较几次？

1. 常见的平均查找长度总结
2. 链地址法和线性探测法求查找成功与不成功的平均查找长度ASL
3. 详细图解什么叫平方探查法即二次探测再散列和线性探测再散列(数据结构哈希函数哈希冲突)
4. 关于ASL(平均查找长度)的简单总结

第八章排序

下列排序方法中,哪一个是稳定的排序方法?( )

A. 直接选择排序
B. 二分法插入排序
C. 希尔排序
D. 快速排序
比较次数与排序的初始状态无关的排序方法是( )。

A. 直接插入排序
B. 气泡排序
C. 快速排序
D. 简单选择排序
数据序列(2,1,4,9,8,10,6,20)只能是下列排序算法中的( )的两趟排序后的结果。

A. 快速排序
B. 冒泡排序
C. 选择排序
D. 插入排序
下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。

A. 选择
B. 冒泡
C. 归并
D. 堆
下列排序算法中,占用辅助空间最多的是:( )

A. 归并排序
B. 快速排序
C. 希尔排序
D. 堆排序
就排序算法所用的辅助空间而言,堆排序,快速排序,归并排序的关系是 ( )

A. 堆排序〈快速排序〈归并排序
B. 堆排序〈归并排序〈快速排序
C. 堆排序〉归并排序〉快速排序
D. 堆排序 > 快速排序 > 归并排序
若需在 O(nlog2n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是( )。

A. 快速排序
B. 堆排序
C. 归并排序
D. 直接插入排序
下列排序算法中,在每一趟都能选出一个元素放到其最终位置上,并且其时间性能受数据初始特性影
响的是:( )。

A. 直接插入排序
B. 快速排序
C. 直接选择排序
D. 堆排序
对 n 个记录的文件进行堆排序,最坏情况下的执行时间是多少?( )

A. O(log2n)
B. O(n)
C. O(nlog2n)
D. O(n*n)
下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。

A. 快速排序
B. shell 排序
C. 堆排序
D. 冒泡排序
(简答题)
已知待排序序列为{38,125,474,368,16,30,590,372}，
（1）给出每一趟归并排序的结果。
（2）画出初建的大顶堆，并给出第一趟、第二趟堆排序的结果。
（3）采用基数排序，给出第一趟、第二趟基数排序的结果。
（4）归并排序、堆排序和基数排序中是否存在不稳定的排序方法？给出其中的不稳定排序方法，并证明其不稳定性。