8、已知如下所示的有向图，试列出图中的全部可能的拓扑有序序列。
1 2 3
5 6 4
9、已知一个图的顶点集V和边集G分别为： V={0，1，2，3，4，5，6，7，8}
E={<0，1>，<0，2>，<1，3>，<1，4>，<2，4>，<2，5>，<3，6>，<3，7>，<4，7>，<4，8>，<5，7>，<6，7>，<7，8>} 若采用邻接表存储，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，则按照教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列（答案是惟一的）。 10、已知一个图如下：
1）分别写出从顶点1开始的DFS和BFS遍历序列； 2）找出一棵生成树；
3）求顶点4到各点的最短路径；
11、A,B是图G的两个顶点。写一个算法，判断他们是否连通。
Int AlinkB(Graph G, VertexType A, VertexType B) 12、写一个算法，求图G的连通分支数。
Int num(Graph G)
21
第九章 查找
班级： 学号： 姓名：
一、选择题
1、对线性表进行二分查找时，要求线性表必须（ ）。
A)以顺序方式存储；B)以顺序方式存储，且结点按关键字值有序排列； C)以链接方式存储；D)以链接方式存储，且结点按关键字值有序排列。
2、用二分查找法查找具有n个结点的线性表时，查找每个元素的平均比较次数是（ ）。
A)O（n2）； B)O（n*log2 n）； C)O（n）； D)O（log2 n）。
3、利用逐个插入结点的方法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉树排序以后，查找元素35时，需要进行（ ）次元素比较。
A)4； B)5； C)7； D)10。
4、设哈希表的长度为m=14，哈希函数H（key）= key MOD 11，表中已有4个结点，其地址分别是：addr（15）= 4；addr（38）= 5；addr（61）= 6；addr（84）= 7；其余地址空。如果采用二次探测再散列处理冲突，则关键字49的结点的地址是（ ）。
A)8； B)3； C)5； D)9。
5、一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该平衡二叉树共有（ ）结点。
A)2 k-1-1； B)2 k-1+1； C)2 k -1； D)2 k +1。
6、有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素查找概率相等的情况下，查找成功所需的平均比较次数为（ ）。
A)35/12； B)37/12； C)39/12； D)43/12。
7、若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( ) A)顺序存储结构 B)链式存储结构 C)索引存储结构 D)散列存储结构 8、具有5层结点的平衡二叉树至少有（ ）个结点。
A)10； B)12； C)15； D)17。
二、填空题
１、己知一个有序表为(1,8,12,25,29,32,40,62,98),当二分查找值为29和98的元素时,分别需要( )次和( )次比较才能查找成功；若采用顺序查找时,分别需要( )次和( )次比较才能查找成功。
２、采用散列（Hash）技术进行查找，需要解决的两个问题是（ ）、（ ）。
３、在各种查找方法中，平均查找长度与结点个数n无关的是（ ）。
４、在分块查找法中，用二分查找法查找记录所在的块，在块内用顺序查找法，则平均查找
22
长度是（ ）。对哈希表查找，若用链表处理冲突，则平均查找长度是（ ）。 ５、在分块查找中，对256个元素组成的线性表分成（ ）块最好，每块最佳长度是（ ）。若每块的长度是8，则平均查找长度是（ ）。
６、假设有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少需要进行（ ）次探测
７、设有一个长度为10的已排好序的表，用二分查找进行查找，若查找不成功，至少与关键字比较（ ）次。 8、二分查找的递归算法。
int Binsch(ElemTye A[ ] , int low , int high ,KeyType K)
{
if ( ){ int mid = (low + high) / 2;
if ( )return mid; //查找成功，返回元素的下标 else if (K < A[mid].key)
return Binsch(A , low , mid –1 , K ); //在左子表上继续查找
else return ; //在右子表上继续查找 }
else ; //查找失败，返回 -1 }
三、问答题与算法题 1、画出对长度为10的有序线性表进行折半查找的一棵判定树，并求其在等概率时查找成功的平均查找长度。
2、在等概率条件下,求查找成功和失败时平均查找长度 ASL成功＝（ ）,ASL失败＝（ ）.
⑥ ⑤ ⑨ ② ⑦ ⑩
① ④
3、用序列（46，88，45，39，70，58，101，10，66，34）建立一棵二叉排序树，画出此树，并求在等概率情况下查找成功时的平均查找长度。
4、给定的一组关键字K={4，5，2，3，6，1}，试按二叉排序树生成规则画出这棵二叉树，并说明用这组关键字以不同的次序输入后建立起来的二叉排序树的形态是否相同？当以中序遍历这些二叉排序树时，其遍历结果是否相同？为什么？
5、设有二叉排序树，画出依次插入8，3后的情形。
⑥ ⑤ ⑨
23
② ⑦ ⑩
① ④
6、设上题（插入前）所示的二叉排序树，画出依次删除5，6后的情形。
7、构造以{4,5,7,2,1,3,6}为关键字的平衡二叉树,并注明用了何种旋转．(写出步骤) 8、设有3阶B-树（图5），画出依次插入18，33，97后的B-树。
43
26 55 60
16 35 41 48 57 66 88
图5
9、在上一题的B-树上（图5），分别画出删除66，16，43后的B-树（都从图5出发）。 10、设散列表的地址范围是[ 0..9 ]，散列函数为H（key）= （key 2 +2）MOD 9,并采用链表处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。 11、已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探查法处理，试： （1）计算出每一个元素的散列地址并在下图中填写出散列表：
` 0 1 2 3 4 5 6 （2）求出在查找每一个元素概率相等情况下的平均查找长度。
12、有字集合K= {15，22，50，13，20，36，28，48，31，41，18}，散列表地址空间为HT [ 0..15 ]，散列函数H（K）= K MOD 13，采用二次探测再散列的开放地址法解决冲突，试将K值填入HT中，并把查找每个关键字所需的比较次数m填入下表中，然后计算出查找成功时的平均查找长度。 I K M 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 13、编写在以BT为树根指针的二叉搜索树上进行查找值为key的结点的非递归算法。 BiTree search(BiTree BT , keytype key)
24
第十章 内部排序
班级： 学号： 姓名：
一、选择题
1、在下列排序算法中，稳定的是（ ），平均速度最快的是（ ），所需辅助存储空间最多的是（ ）。
A．希尔排序； B．快速排序； C．堆排序； D．归并排序。
2、若要在O（n.log 2 n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法应该是（ ）。
A．快速排序； B．堆排序； C．归并排序； D．希尔排序。 3、一组纪录的关键码序列是（46，79，56，38，40，84），则用堆排序方法建立的初始堆是（ ）。
A．79，46，56，38，40，84； B．84，79，56，38，40，46； C．84，79，56，46，40，38； D．84，56，79，40，46，38。 4、一组纪录的关键码序列是（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。
5、一组纪录的关键码序列是（25，48，16，35，79，82，23，40，36，72），用二路归并排序方法进行排序，则第二趟归并的结果是（ ）。
A．16，25，35，48，23，40，79，82，36，72； B．16，25，35，48，79，82，23，36，40，72； C．16，25，35，46，23，36，40，79，82，72； D．16，25，35，48，79，23，36，40，72，82。
6、在以下排序方法中，关键字比较的次数与记录的初始排列次序无关的是（ ）。
A．希尔排序； B．起泡排序； C．插入排序； D．选择排序。 7、下列排序算法中，（）算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。 A、堆排序 B、冒泡排序 C、快速排序 D、SHELL排序 8、直接插入排序在最好的情况下，其时间复杂度为（ ）。
A. O（log n）； B．O（n）； C．O（n 2）； D．O（n*log n）。
二、填空题
１、设有字符序列（Q,H,C,Y,P,A,M,S,E,D,F,X），则用初始步长为4的希尔排序方法将其按
字符升序排序，第一趟扫描的结果是（ ）。 ２、快速排序的最大递归深度是（ ），最小递归深度是（ ）。
３、在对n个元素的序列利用起泡法排序时，最好情况的最少比较次数是（ ）。
４、在插入序排、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均
25
比较次数最少的是（ ），需要辅助内存空间最大的是（ ）。 ５、在插入序排、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序算法不稳定的有（ ）。
６、在插入排序和选择排序两种算法中，若待排序的序列已基本正序，则选用（ ）较好，若待排序的序列已基本反序，则选用（ ）较好。
７、在堆排序和快速排序两种算法中，若待排序的序列已基本有序，则选用（ ）较好，若待排序的序列完全无序，则选用（ ）较好
三、问答题与算法题
1、已知序列（10，18，4，3，6，12，1，9，18，8）请用希尔排序(增量d1=3,d2=1),写出每一趟排序的结果。
2、已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。 3、已知序列（10，18，4，3，12，9，18，8）请用堆排序写出每一趟（建好初始堆，L.r[1]与 L.r[n]互换后为第一趟）排序的结果。
26