v0514258329v1v2v321v4
答：求解过程如下表所示，其中I为循环次数，k为加入集合S的顶点，S为已求得最短路径的顶点集合，shortest为最短路径的长度，path为最短路径。
shortest path
i k S 0 1 2 3 4 0 1 2 3 4
初态
1 1
2 2
3 4
4 3
11. 对如图所示的有向网，试利用狄杰斯特拉算法求出从源点v0到其它各顶点的最短路径，并写出求解过程。
答：求解过程如下表所示，其中i为循环次数，k为加入集合S的顶点，S为已求得最短路径的顶点集合，shortest为最短路径的长度，path为最短路径。
v37243v513357v0241v278v61v410v1
v7 i 0 1 2 3 4 5 6 7
k S shortest path 17
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
12.已知带权有向图如下如示，请用弗洛伊德算法(floyd)算法求出每对顶点之间的最短路径。
4v011362v2v1D 0 1 2 P 0 1 2
D(-1) 0 0 1 P(-1) 1 2 0 2 0 D(0) 1 P(0) 1 2 0 2 0 1 D(1) 2 2 0 0 D(2) 1 P(2) 1 2 2 P(1) 1 第八章 查找
一．判断题
1.顺序查找适用于顺序或链式存储的线性表。（） 2. 二叉排序树和二分法查找的时间性能是一样的。（）
3.AVL树是一棵二叉树，该树上任一结点的平衡因子都不大于1。（） 4.中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（） 5.顺序查找方法只能在顺序存储结构下进行。（） 6.二叉排序树中，新插入的结点总是在最底层。（）
7.平衡二叉排序树中，以每个分支结点为根的子树都是平衡的。（）
8.每个结点的关键字值都大于左子小于右子关键字值，这样的二叉树就是二叉排序树（） 9.哈希冲突是指同一个关键字对应多个不同的哈希地址。（） 10.二叉排序树的查找效率和其高度有关。（） 二．选择题
1.在二叉排序树中，新插入的结点，都是没有 的。 A.孩子 B.关键字 C.平衡因子 D.赋值
2.在数据元素有序，元素个数较多而固定不变的情况下，宜采用 法查找。 A.二叉排序树 B.分块查找 C.二分法 D.顺序查找
3.对有18个元素的有序表作二分查找，则查找A[3]的比较序列下标可能为 。 A.1、2、3 B.9、5、2、3 C.9、5、3 D.9、4、2、3
4.若在线性表中采用二分查找法查找元素，该线性表应该。
A.元素按值有序 B.采用顺序存储结构 C.元素按值有序，且采用顺序存储结构D.元素按值有序，且采用链式存储结构 5.采用顺序检索的方法检索长度为n的线性表，则检索每个元素的平均比较次数为 。 A.n B.n/2 C.(n+1)/2 D.(n-1)/2
6.有一个有序表为{2，3，10，12，32，41，45，62，75，78，83，94，99}，当用二分法查找83时，经过 次比较后查找成功。
18
A.1 B.2 C.4 D.8
7.设Hash表长m=14，Hash函数H(key)=key。表中已有4个结点。addr(15)=4,addr(38)=5,addr(61)=6,addr(81)=7，如用二次探测再Hash处理冲突，关键字为49的结点的地址是 。 A.8 B.9 C.3 D.5
8.分块查找的时间效率 。
A.低于二分查找B.高于顺序查找但低于二分查找C.高于顺序查找D.低于顺序查找但高于二分查找
9.有数据{52,29,36,11,44,23,95}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，则应该选择下面哪个序列插入 。
A.44,23,52,11,36,95,29 B.36,23,11,52,44,95 C.11,23,29,36,44,52,95 D.29,23,11,36,44,96,52. 10.散列表的平均查找长度 。
A.与处理冲突方法有关而与表的长度无关B.与处理冲突方法无关而与表的长度有关C.与处理冲突方法有关且与表的长度有关D.与处理冲突填色关且与表的长度无关 三．填空题
1.衡量查找算法性能好坏的主要标准是 。
2.对二叉排序树进行 遍历，可得到按关键字从小到大排列的序列。 3.在Hash函数H(key)=k%p中，p应取 。
4.对于二叉排序树的查找，若根结点元素的键值大于被查找元素的值，则应该在二叉排序树的 上继续查找。 5.评价Hash函数的标准是 。
6.在各种查找方法中，其平均查找长度与结点个数n无关的查找方法是 。
7.设在有序表A[0..19]中进行二分法查找，比较一次查找成功的结点数是 。比较二次查找成功的结点为数 。比较三次查找成功的结点数为 ，比较四次查找成功的结点数为 。比较五次查找成功的结点数为 。平均查找长度为 。 8.采用二分法查找，应选择 方式的存储结构。
9.在线性表的Hash存储中，处理冲突有 和 两类。当装填因子一定时，采用链地址法解决冲突比采用开放定址处理冲突的平均检索长度要 。
10.二叉排序树的查找效率与树的形态有关。当二叉排序树退化为单支树时，查找算法退化为 查找，其中平均查找长度为 。 四．简答题
1.将整数序列{4，5，7，2，1，3，6}中的数依次插入到一棵空的平衡二叉树中，试构造相应的平衡二叉树，要求用图形给出构造过程，不需编写程序。
2.已知一个有序表{12,17,23,34,46,49,61,82,89,114,133}，写出利用二分法查找89的过程。
3.线性表关键字集合{87,25,310,8,27,132,68,95,187,123,70,63,47}，共13个元素，已知Hash函数为：H(k)=k，采用链地址法处理冲突，设计出链表结构。
4.设关键值集合为{19,7,8,23,16,25,12,26,38,3}，Hash表的长度为13，用线性探测法解决冲突，画出其Hash表。
5.设有一组关键字{19,1,23,14,55,20,84,27,68,11,10,77}，设Hash函数为hash(key)=key mod 13。采用开放定址法的二次探测再hash方法解决冲突，试在0-18的hash地址空间中对该关键字序列构造hash表。 6.编写一算法，实现在带头结点的单链表上顺序查找功能。
7.利用二分查找算法在一个有序表中插入一个元素，并保持表的有序性。 8.编写一递归算法，从大到小输出二叉排序树中所有其值不小于x的关键字。
第九章 习题
一。判断题
1.如果某种排序算法是不稳定的，则该方法无实际价值。（） 2.对n个记录进行冒泡排序，所需的平均时间是O(nlog2n)。（） 3.对n个采用冒泡法排序，最坏情况下所需要的时间为O(n2)。（） 4.{101,88,46,70,34,39,45,58,66,10}是大顶堆。（）
5.在所有排序算法中，快速排序的速度最快，所需的辅助存储空间也最少。（）
19
6.在一个小顶堆中，最大值的结点一定是一个叶子结点。（） 7.若关键字的初始排序杂乱无序，则排序效率低。（）
8.只有在线性表的初始状态为逆序排列的情况下，冒泡排序过程中元素的移动次数才会达到最大值。（） 9.对n个元素进行快速排序，在进行第一次分组时，关键字的比较次数n-1次。（） 10.对一个堆，按二叉树层次进行遍历就可以得到一个有序序列。（） 二．选择题
1.以下排序方法中，某一趟结束后未必能选出一个元素放在其最终位置上的是 。 A.堆排序 B.冒泡排序 C.直接插入排序 D.快速排序
2.依次将待排序序列中的元素和有序子序列合并为一个新的有这辈子子序列的排序方法是 。 A.快速排序 B.插入排序 C.冒泡排序 D.堆排序
3.若表R在排序前已按键值递增顺序排序，则 排序法的比较次数最少。 A.直接插入排序 B.快速排序 C.归并排序 D.选择排序
4.在下列排序中，关键字的比较次数与记录的初始排列次序无关的是 。 A.希尔排序 B.冒泡排序 C.插入排序 D.选择排序 5.快速排序法在 情况下不利于发挥其特点。
A.待排序序列数据量太大 B.待排序序列中含有多个相同值 C.待排序序列基本有序 D.待排序序列数据个数为奇数 6.待排序数据序列中有100个元素，仅要求求出其中最小的十个元素，采用 排序方法最节省时间。 A.堆排序 B.希尔排序C.快速排序 D.直接选择排序
7.若一组记录的排序码为{46,79,56,38,40,84}，则利用堆排序方法排序时建立的初堆为 。 A.79,46,56,38,40,80 B.84,79,56,38,40,46 C.84,79,56,46,40,38 D.84,56,79,40,46,38
8. 若一组记录的排序码为{46,79,56,38,40,84}，要求结果从小到大，则利用快速排序方法排序时第一次划分的结果为 。
A.38,40,46,56,79,84 B.40,38,46,79,56,84 C.40,38,46,56,79,84 D.40,38,46,84,56,79
9.稳定排序方法是指在排序过程中，关键字值相同的不同记录间的前后相对位置 。 A.保持不变 B.变为相反 C.不定 D.无关 10.以下排序方法中， 是不稳定的。
A. 折半插入排序 B.直接插入排序 C.冒泡排序 D.快速排序 11.以下排序方法中， 是稳定的。
A.选择排序 B. 折半插入排序 C. 快速排序 D. 堆排序 12.直接插入法排序的时间复杂度为 。 A.O(log2n) B.O(n) C.O(nlog2n) D.O(n2)
13.待排序记录基本有序的情况下，以下排序方法中，效率最高的是 。 A.插入排序 B.选择排序 C.快速排序 D.归并排序
14.下述几种排序方法中，要求内存量最大的是 。 A.插入排序 B.归并排序 C.选择排序 D.冒泡排序 15.在对n个元素进行快速排序的过程中，第一次划分最多需要移动 次元素（包括开始将基准元素移到临时变量的那一次）。
A.n/2 B.n-1 C.n D.n+1
三．填空题
1.在排序前后，关键字值相等的不同记录间的前后相对位置 的排序方法称之为稳定的排序方法。
2.在堆排序、快速排序和归并排序中，若只从存储空间考虑，则应首先选取 方法，其次选取 方法，最后选取 方法。若只从排序结果的稳定性考虑，则应选取 方法；若只从平均情况下排序最快考虑，则应选择取 方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取 方法。
3.对n个元素进行冒泡排序时，最少的比较次数是 。 4.归并排序的时间复杂度是 。
5.每次从无序表中取出一个元素，把它插入到有序子表中的适应位置，此种排序方法叫做
20
排序；每次从无序子表中挑选一个最小或最大元素，把它交换到有序表的一端， 此种方法叫做排序 。
6.每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种方法做 排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做 排序。
7.在内部排序中，平均比较次数最少的是 ，要求附加存储空间最大的是 ，排序时不稳定的是 、 、 、 。
8. 排序是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。
9.在对一组记录{50,40,95,20,15,70,60,45,80}进行直接选择排序时，第4次交换和选择后，未排序记录（即无序表）为 。
10. 在对一组记录{50,40,95,20,15,70,60,45,80}进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需要比较 次。
11.在堆排序和快速排序中，若原始记录接近正序，则选用 。若原始记录无序，则最好选用 。 12.在直接插入和直接选择排序中，若初始数据基本有序，则选用 ，若初始数据基本反序，则选用 。 四．简答题
1.某整型数组R的10个元素依次为{6,2,9,7,3,8,4,5,0,10}。用下列各排序方法，将R中元素从小到大排序。 （1）取第一个元素6作为划分数据，试写出快速排序第一次划分操作后R中的结果。 （2）用堆排序（大顶堆），试写出将第一个选出的数据交换到R的最后位置上，再将其余元素调整成堆后R中的结果。 2.已知序列{70,83,100,105,10,32,7,9}，请给出采用直接插入排序法对该序列作升序排序时的每一趟结果。 3.已知序列{10,18,4,3,6,12,1,9,15,8},请给出采用希尔排序法对该序列做升序排序的每一趟结果。 4. 已知序列{10,18,4,3,6,12,1,9,15,8},请给出采用归并排序法对该序列做升序排序的每一趟结果。 5.判断下列序列是否为堆（小根或大根堆），若不是，则将其调整为堆： （1）（100,86,73,66,39,42,57,35,21） （2）（12,70,33,65,24,56,48,92,86,33）
6.已知序列{57,40,38,11,13,34,48,75,6,19,9,7}，采用堆排序法对该序列做降序排序时的每一趟过程。 7.设计一个直接选择排序算法，将数组中的元素按降序排列。 8.设计一个算法，在n个元素的堆中增加一个元素且调整为堆。
21