v1v2 （1）该图是强连通的吗？若不是，给出强连通分量。 （2）请给出图的邻接矩阵和邻接表表示。
答案：(1) 是强连通图 (2) 邻接矩阵和邻接表为：
0010100001011000v1v2v3v4v2v3v1v3v4v4v3
??112610??1?89????9、已知图G的邻接矩阵A=?128??2?， 试画出它所表示的图G，并根据Prim算法求出
??69??4????10?24???图的的最小生成树（给出生成过程）。 答案：
(1)图形态： (2)prim算法求最小生成树：
v112102v54v3189v4v118v3v5v22v5v324v4v2v11v2v118v3v2v118v2
10、如下图所示的AOV网，写出其中三种拓扑排序序列。
v0v2v1
v3v4v5
11、已知图G如下，根据克鲁斯卡尔算法求图G的一棵最小生成树。（要求给出构造过程）
v6v7答案：kruskal算法的最小生成树
21
B2B2D3B2D3B2A4D3FFKF3KF3CKHHB2A4D3B25A4D3B25A45D3F3C4KF3C4KF3C4KHEHEHE
第九章 查找
一、选择题
1、已知一个有序表为（11，22，33，44，55，66，77，88，99），则折半查找55需要比较（ A ）次。
A. 1 B. 2 C. 3 D. 4
4、在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为（ ）。
A. n B. log2n C. (h+1)/2 D. h
5、已知表长为25的哈希表，用除留取余法，按公式H(key)=key MOD p 建立哈希表，则p应取（ ）为宜。
A. 23 B. 24 C. 25 D. 26 6、设哈希表长m=14,哈希函数H(key)=key MOD 11。表中已有4个结点：
addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7 其余地址为空，如用二次探测再散列处理冲突，则关键字为49的地址为（ D ）。
A.8 B. 3 C. 5 D. 9 7、在散列查找中，平均查找长度主要与（ C ）有关。
A. 散列表长度 B. 散列元素个数 C. 装填因子 D. 处理冲突方法 10、一个待散列的线性表为k={18,25,63,50,42,32,9}，散列函数为H(k)=k MOD 9，与18发生冲突的元素有（ B ）个。
A. 1 B. 2 C. 3 D. 4 11、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插到集合中，这种方式主要适合于（ B ）。 A. 静态查找表 B. 动态查找表 C. 静态查找表和动态查找表 D. 两种表都不适合 13、在各种查找方法中，平均查找次数与结点个数n无关的查找方法是（ C ）。
A. 顺序查找 B. 折半查找 C. 哈希查找 D. 分块查找 14、下列二叉树中，不平衡的二叉树是（ C ）。 ．
22
15、对一棵二叉排序树按（ B ）遍历，可得到结点值从小到大的排列序列。
A. 先序 B. 中序 C. 后序 D. 层次 16、解决散列法中出现的冲突问题常采用的方法是（ D ）。
A. 数字分析法、除余法、平方取中法 B. 数字分析法、除余法、线性探测法 C. 数字分析法、线性探测法、多重散列法 D. 线性探测法、多重散列法、链地址法
17、对线性表进行折半查找时，要求线性表必须（ C ）。
A. 以顺序方式存储 B. 以链接方式存储
C. 以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序
二、填空题
2、已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半查找90时，需进行 2 次查找可确定成功。
3、具有相同函数值的关键字对哈希函数来说称为 同义词 。
4、在一棵二叉排序树上实施 中序 遍历后，其关键字序列是一个有序表。
三、判断题
（ ×）1、折半查找只适用于有序表，包括有序的顺序表和链表。
（√ ）2、二叉排序树的任意一棵子树中，关键字最小的结点必无左孩子，关键字最大的结点必无右孩子。
（√ ）4、平衡二叉树是指左右子树的高度差的绝对值不大于1的二叉树。 （√ ）5、AVL是一棵二叉树，其树上任一结点的平衡因子的绝对值不大于1。
四、综合题
1、选取哈希函数H（k）=（k）MOD 11。用二次探测再散列处理冲突，试在0-10的散列地址空间中对关键字序列（22,41,53,46,30,13,01,67）造哈希表，并求等概率情况下查找成功时的平均查找长度。
答案：(1)表形态：
022110112461313245673038411953110(2)ASL：ASL(7)=(1*5+2*1+3*1)/7=(5+2+3)/7=10/7
2、设哈希表HT表长m为13，哈希函数为H(k)=k MOD m，给定的关键值序列为{19,14,23,10,68,20,84,27,55,11}。试求出用线性探测法解决冲突时所构造的哈希表，并求
23
出在等概率的情况下查找成功的平均查找长度ASL。 答案：(1)表形态：
0114122723681455256191720188439102311110212112 (2)平均查找长度：ASL(10)=(1*5+2*4+3*1)/10=1.6
3、设散列表容量为7（散列地址空间0..6），给定表（30，36，47，52，34）,散列函数H（K）=K mod 6，采用线性探测法解决冲突，要求： （1）构造散列表；
（2）求查找数34需要比较的次数。 答案：(1)表形态：
0301126223452154716343(2)查找34 的比较次数：3
4、已知下面二叉排序树的各结点的值依次为1－9，请标出各结点的值。
答案：（说明，图中61结点的值应该为 4）
51961627
5、若依次输入序列{62,68,30,61,25,14,53,47,90,84}中的元素，生成一棵二叉排序树。画出生成后的二叉排序树（不需画出生成过程）。
8、根据一组记录（56，42，50，64，48）依次插入结点生成一棵AVL树（画出生成过程）。
6、设有一组关键字{19,1,23,14,55,20,84,27,68,11,10,77},采用哈希函数H(key)=key MOD 13,采用开放地址法的二次探测再散列方法解决冲突，试在0－18的散列空间中对关键字序列构造哈希表，画出哈希表，并求其查找成功时的平均查找长度。
7、已知关键字序列{11,2,13,26,5,18,4,9}，设哈希表表长为16，哈希函数H(key)=key MOD 13，处理冲突的方法为线性探测法，请给出哈希表，并计算在等概率的条件下的平均查找长度。
8、设散列表的长度为m=13，散列函数为H(k)=k MOD m，给定的关键码序列为19，14，23，
24
38
1，68，20，84，27，55，11，13，7，试写出用线性探查法解决冲突时所构造的散列表。 答案：表形态：
01311141212368142745553619172018843973102311111112
9、依次读入给定的整数序列{7,16,4,8,20,9,6,18,5}，构造一棵二叉排序树,并计算在等概率情况下该二叉排序树的平均查找长度ASL。（要求给出构造过程）
10、设有一组关键字（19，1，23，14，55，20，84，27，68，11，10，77），采用哈希函数H(key)=key，采用二次探测再散列的方法解决冲突，试在0-18的散列地址空间中对该关键字序列构造哈希表。 答案：
027311121423551468258436191720189103102311111112771131415161718
11、有一组关键字序列{13,16,6,34,32,98,73,1,27}，哈希表的表长为13，哈希函数为H(key)=key MOD 13,冲突解决的办法为链地址法，请构造哈希表（用图表示）。
第十章 内部排序
一、选择题
1、若需要在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。
A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序 2、下列排序方法中（ ）方法是不稳定的。
A. 冒泡排序 B. 选择排序 C. 堆排序 D. 直接插入排序
3、一个序列中有10000个元素，若只想得到其中前10个最小元素，则最好采用（ ）方法。
A. 快速排序 B. 堆排序 C. 插入排序 D. 归并排序 4、一组待排序序列为（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 5、快速排序方法在（ ）情况下最不利于发挥其长处。
A. 要排序的数据量太大 B. 要排序的数据中有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数
6、排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置，这是（ ）排序的基本思想。
A. 堆排序 B. 直接插入排序 C. 快速排序 D. 冒泡排序 7、在任何情况下，时间复杂度均为O(nlogn)的不稳定的排序方法是（ ）。 A.直接插入 B. 快速排序 C. 堆排序 D. 归并排序 8、如果将所有中国人按照生日来排序，则使用（ ）算法最快。
A. 归并排序 B. 希尔排序 C. 快速排序 D. 基数排序 9、在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。
A. O(log2n) B. O(1) C. O(n) D. O(nlog2n)
10、排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序
25