③存储无向图的相邻矩阵是对称的，因此只要存储相邻矩阵的下（或上）三角部分就可以了 ③用相邻矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查A的第 i行第j列的元素是否为0即可。 16．以下说法正确的是 （ ） ①连通分量是无向图中的极小连通子图。 ②强连通分量是有向图中的极大强连通子图。
③在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。
④对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。 四、简答及应用
1． 简述图的邻接矩阵表示的类型定义 2． 简述图的邻接表的类型定义。
3． 给出无向图简答题3中g1的邻接矩阵和邻接表。
4．分别给出图简答题3中g2的邻接矩阵、邻接表和逆邻接表。
5．分别给出图简答题3中g3从v5出发按深度优先搜索和广度优先搜索算法遍历得到的顶点序列。 6．求出图简答题6-1的连通分量。
7．求出带权图简答题7-1的最小生成树 8．写出有向图简答题8-1的拓扑排序序列。 9．给出网图简答题9-1的邻接矩阵表示。
10．已知连通网的邻接矩阵如下，试画出它所表示的连通网及该连通网的最小生成树。
11．对于图简答题11-1从其邻接表中回答下列问题： （1） 图中有多少条弧？
（2） 图中是否存在从i到j的弧？ （3） 如何求顶点i的出度？
16
12．图简答题11-1所示为一有向图，请给出该图的下述要求： （1） 每个顶点的入/出度。 （2） 邻接矩阵。 （3） 邻接表。 （4） 逆邻接表。
13．拓扑排序的结果不是唯一的，对图简答题13-1进行拓扑排序，试写出其中任意5个不同的拓扑排序列。 14．对m个顶点的无向图G，采用邻接矩阵，如何判别下列有关问题： （1） 图中有多少条边？
（2） 任意两个顶点i和j是否有边相连？ （3） 任意一个顶点的度是多少？
15.已知图G的邻接表如图简答题15-1所试，顶点V1为出发点，完成要求： （1） 深度优先搜索的顶点序列； （2） 广度优先搜索的顶点序列；
（3） 由深度优先搜索得到的一棵生成树； （4） 由广度优先搜索得到的一棵生成树。 Vertex fi
16.设有一无向图G=(V,E),其中V={1,2,3,4,5,6},E={(1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5),(3,5)}。 （1） 按上述顺序输入后，画出其相应的邻接表；
（2） 在该邻接表上，从顶点4开始，写出DFS序列和BFS序列。
17．图简答题17-1所示为一无向连通网络，先要求根据prim算法构造出它的最小生成树。
第九章 查找表
二、填空题
1.对任何集合A而言，A的每一个成员a称为A的一个________，记为________。 17
2.空集是________的集合，记为________。
3.在集合这种逻辑结构中，任何结点之间都不存在________关系，这是集合这种逻辑结构的基本特点。 4.集合中没有相同的________。作为一个数学概念，集合的元素没有________。 5.数据元素之间的逻辑关系反映的是________。
6.对于集合这逻辑结构来说，其中的数据元素之间也可以有各种各样的非逻辑关系，但任何一对数据元素之间没有________关系，即没有________关系。
7.查找表按其所包括的运算的不同分为________查找表和________查找表。 8.查找表中主关键字指的是________，次关键字指的是________。 9.静态查找表包括________、________、________三种基本运算。
10.动态查找表包括________、________、________、________、________五种基本运算。
11.假定key为主关键字，若顺序表中第n个元素的键值为K，则顺序查找算法的查找长度为1；若第1个元素的键值为K，则查找长度为________；若表中无键值等于K的元素，则查找长度为________。
12.以下算法在有序表R中用二分查找法查找键值等于K的元素，请分析程序，并在________上填充合适的语句。 int binsearch(sqtable R,keytype K)
{low=1;hig=R.n;/*置查找区间初值。low,hig分别标记查找区间的下、上界*/ while(low<=hig)
{mid=（low+hig)/2; switch
{case K==R.item[mid].key:return(mid);/*找到，返回位置mid*/ case K
return(0);/*若区间长度已为0但仍不成功，则返回0，表示查找不成功*/ }
13.二分查找在查找成功时的查找长度不超过________，其平均查找长度为________，当n较大时约等于________。
14.一个________表由一个顺序表和一个索引表两部分组成。其中的顺序表在组织形式与普通的________表完全相同；而索引表本身在组织形式上也是一个________表。
15.索引顺序表的特点表现为以下两个方面：a.顺序表中的数据元素\；b.索引表反映了这些\的有关特性。
16.在索引顺序表上，对于顺序表中的每一块，索引表中有相应的一个\索引项\。每个索引项有两个域：块内最大________值和块________位置。
17.索引顺序表上的查找分两个阶段：一、________；二、________。该查找方法称为________查找。
18.静态查找表的三种不同实现各有优缺点。其中，________查找效率最低但限制最少。________查找效率最高但限制最强。而________查找则介于上述二者之间。 19.二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值________于其左孩子（及其子孙）的键值且________于其右孩子（及其子孙）的键值。
20.在表示一棵二叉排序树的二叉链表上，要找键值比某结点X的键值________的结点，只需通过结点X的左指针到它的左子树中去找。 21.中根遍历一棵二叉排序树所得的结点访问序列是键值的________序列。 22.对于一个无序序列，可以通过构造一棵________而使其成为一个有序序列。
23.以下算法在指针T所指的二叉排序树上查找键值等于K的结点。成功时回送指向该结点的指针；否则回送空指针。请分析程序，并在________填充合适的语句。
bitreptr search_bst(bitreptr T,keytype K) {if(T==NULL)return(NULL); else swith
{case T->key==K:________;
case________: rerutn(search_bst(T->lchild,K)); case________: rerutn(search_bst(T->rchild,K)); } }
24.二叉排序树上的查找长度不仅与________有关，也与二叉排序树的________有关。
25.在随机情况下，含有n个结点的二叉排序树的平均查找长度为________，其时间效率很高。 26.二叉排序的查找效率与树的形态有关。当二叉排序树退化为一条单支时，查找算法退化为________查找，平均查找长度上升为________。 27.有n个结点的AVL树的深度与________是同数量级的，因而在它上面进行查找的平均查找长度也与________同数量级。 28.平衡二叉排序树上任一结点的平衡因子只可能是________、________或________。 29.采用散列技术时需要考虑的两个主要问题是：一、________？二、________？ 30.按组织形式的不同，通常有________与________两类散列表。
31.以下算法在开散列表HP中查找键值等于K的结点，成功时返回指向该结点的指针，不成功时返回空指针。请分析程序，并在________上填充合适的语句。
pointer research_openhash(keytype K,openhash HP) {i=H(K); /*计算K的散列地址*/
p=HP[i]; /*i的同义词子表表头指针传给p*/
while(________)p=p->next;/*未达表尾且未找到时，继续扫描*/ ________; }
32以下算法实现若开散列表HP中无键值为K结点，则插入一个这样的结点。请分析程序并在________上填充合适的语句。 void insert_openhash(keytype K,openhash HP) {if(research_openhash(K,HP)==NULL) {i=H(K);
q=malloc(size);q->key=________; /*生成新结点*/
________=HP[i];HP[i]=________; /*前插法链入新结点*/ } }
33.以下算法实现若开散列表HP中存在键值为K结点，则将其删除。请分析程序并在________上填充合适的语句。 void delete_openhash(keytype K,openhash HP) {i=H(K); 18
if(HP[i]==NULL)return;/*空表则退出*/ p=HP[i];
if(p->key==K){_______=p->next;free(p);return;} /*表首结为待点时的删除*/ while(p->next!=NULL) /*其他情况下的删除*/ {q=p;p=p=->next;
if(p->key==K){________=p->next;delete(p);return;} } }
34.对闭散列表来说，________的方法就是处理冲突的方法。
35.常见的构造后继散列地址序列的方法有________、________、________、________四种。
36.以下算法假定以线性探测法解决冲突，在闭散列表HL中查找键值为K的结点，成功时回送该位置；不成功时回送标志-1。请分析程序，并在________上填充合适的语句。
int search_cloxehash(keytype K,closehash HL) {d=H(K); /*计算散列地址*/ i=d;
while(HL[i].key!=K&&(i!=d-1)i=______;/*未成功且未查遍整个HL时继续扫描*/ if(________)reurn(i); /*查找成功*/ else return(-1); /*查找失败*/ }
37.________查找法的平均查找长度与元个数n个数无关。
38.在分块查找法中，首先查找________，然后再查找找相应的________。
39.在具有24个元素的有序表上进行二分查找，则比较一次查找成功的结点数为________，比较二次查找成功的结点数为________，比较五次查找成功的结点数为________。总的平均查找长度为________。 40.在散列存储中，装填因子x的值越大，则________。
41.________是散列表的一个重要参数，它反映出散列表的装满程度。
42.当所有结点的权值都相等时，用这些结点构造的二叉排序树上只有________。
43.在二叉排序树上插入新结点时，不必移动其它结点，仅需使某结点的指针域由________变为________即可。 44．二分查找方法仅适用于这样的表：表中的记录必须________，其存储结构必须是________。
45.设线性表(a1,a2,?,a500)元素的值由小到大排列。对一个给定的k值，用二分法检索查找表中与k相等的元素，在检索不成功的情况下至多较________次。
46.设线性表L=（a1,a2,?,an)(n>2),表中元素按值的递增顺序排列。对一个给定的值k，分别用顺序检索和二分法检索查找与k相等的元素，比较次数分别为s和b ，若检索不成功，则s和b的数量关系是________。
47.设有两个散列函数H1(k)=k mod 13 和H2(k)=k mod 11+1，散列表为T[0?12]，用双重散解决冲突。函数H1用来计算散列地址，当发生冲突时，H2作为计算下一个探测地址的地址增量，假定在某一时刻T的状态为：
T: 0 1 2 3 4 5 6 7 8 9 10 11 12 80 85 34 下一个被插入的关键码是42，其插入的位置是:______________。 48.设有一个已按各元素的值排好序的线性表，长度为125，对给定的k值，用二分法查找与k相等的元素，若查找成功，则至少需要比较________次，至多需比较________次。 三、单项选择题
1． 以下说法错误的是 （ ） ①数字分析法对健值的各位进行分析，选择分布较均匀的若干位组成散列地址。 ②除余法选择一个适当的正整数p,以p除健值以所得的余数作为散列地址。 ③平方取中法以健值平方的中间几位作为散列地址。
④基数转换法将健值看成另一种进制的数再转换成原来进制的数，然后选择其中几位作为散列地址。 ⑤随机数法选择一个随机函数random,以健值在该函数下的值作为散列地址。
2． 以下所法正确的是 （ ）
①数字分析法需事先知道所有可能出现的健值及所有健值的每一位上各数字的分布情况，并且健值的位数比散列地址的位数多。 ②除余法要求事先知道全部健值。
③平方取中法需要事先掌握健值的分布情况。 ④随机数法适用于健值不相等的场合。
3． 除余法选择一正整数p，以健值除以p所得的余数作为散列地址。通常选p为（ ） ①小于或等于散列表长的素数。
②接近表长的且不与组成关键字的字符基数直接相关的质数。 ③大于或等于散列表长的素数。 ④接近表长的质数。
4．顺序查找法适合于（ ）存储结构的查找表。
①压缩 ② 散列 ③索引 ④顺序或链式
5．对采用二分查找法进行查找运算的查找表，要求按（ ）方式进行存储。 ①顺序存储 ② 链式存储
③顺序存储且结点按关键字有序 ④ 链式存储且结点按关键字有序
6．设顺序表的长为n,则其每个元素的平均查找长度是 （ ） ①n ② (n-1)/2 ③ n/2 ④ (n+1)/2
7.设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84的结点时，经（ ）次比较后查找成功。
①2 ② 3 ③ 4 ④ 12
8．静态查找表与动态查找表两者的根本差别在于 （ ） ①逻辑结构不同 ② 存储实现不同
③施加的操作不同 ④ 数据元素的类型不同
9．长度为12的按关键字有序的查找表采用顺序组织方式。若采用二分查找方法，则在等概率情况下，查找失败时的ASL值是 （ ）
①37/12 ② 62/13 ③ 39/12 ④49/13
10.在表长为n的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数为（ ） ①n ②1 ③ n+1 ④n-1
11.二分查找法适用于存储结构为（ ）的，且按关键字排序的线性表。 （ ） 19
①顺序存储 ② 链接存储 ③ 顺序存储或链接存储 ④索引存储 12．用顺序查找法对具有n个结点的线性表查找的时间复杂性量级为
2
①O（n） ② O(nlog2n) ③ O（n） ④ O(log2n)
13．用二分查找法对具有n个结点的线性表查找的时间复杂性量级为 （ ）
2
①O(n) ② O(nlog2n) ③ O(n) ④O(log2n)
14．二叉排序树的查找和折半查找的时间性能相同。这种说法 （ ） ①正确 ② 错误
15．与其他查找方法相比，散列查找法的特点是 （ ） ①通过关键字比较进行查找
②通过关键字计算记录存储地址进行查找
③通过关键字计算记录存储地址，并进行一定的比较进行查找
16．在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的健值 （ ）
①一定都是同义词 ② 一定都不是同义词
③都相同 ④ 健值不一定有序的顺序表
18．设散列函数为H(k)= k mod 7,一组关键码为23，14，9，6，30，12和18，散列表T的地址空间为0..6,用线性探测法解决冲突，依次将这组关键码插入T中，得到的散列表为 （ ） ①0 1 2 3 4 5 6 14 6 23 9 18 30 12 ② 0 1 2 3 4 5 6 14 18 23 9 30 12 6 ③0 1 2 3 4 5 6 14 12 9 23 30 18 6 ④0 1 2 3 4 5 6 6 23 30 14 18 12 9 19．设有一个用线性探测法解决冲突得到的散列表：
T:0 1 2 3 4 5 6 7 8 9 10 13 25 80 16 17 6 14 散列函数为H(k)=k mod 11,若要查找元素14，探测的次数是 （ ） ① 18 ② 9 ③3 ④6
20．在散列函数H(k)=k MOD m 中，一般来讲，m应取 （ ） ①奇数 ②偶数 ③ 素数 ④ 充分大的数
21，分块查找的时间性能 （ ） ①低于二分查找 ② 高于顺序查找而低于二分查找 ③高于顺序查找 ④ 低于顺序查找而高二分查找
22．以下说法正确的是 （ ） ①顺序查找效率最低但限制最强。 ②二分查找效率最高但限制最少。
③分块查找效率介于顺序查找和二分查找之间。
23．以下说法正确的是 （ ） ①查找表中数据元素的任何数据项都可以作为关键字。
②采用二分查找法对有序表进行查找总比采用顺序查找法对其进行查找要快。 ③二叉排序树的查找和二分查找时间的性能相同。 ④最佳二叉排序树一定是平衡二叉树
⑤“顺序查找法”是指在顺序表上进行查找的方法。 24．．以下说法错误的是 （ ） ①散列法存储的基本思想是由关键码的值决定数据的存储地址。 ②散列表的结点中只包含数据元素自身的信息，不包含任何指针。 ③装填因子是散列法的一个重要参数，它反映散列表的装填程度。
④散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法。
25．以下说法错误的是 （ ） ①当所有的结点的权之都相等时，用这些结点构造的二叉排序树的特点是只有右子树 ②中序遍历二叉排序树的结点就可以得到排好序的结点序列。
③任一二叉排序树的平均检查时间都小于用顺序查找法查找同样结点的线性表的平均查找时间。
④对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的。 ⑤采用分块查找方法，既能实现线性表所希望的较快的查找速度，又能适应动态变化的需要。 26．以下说法正确的是 （ ） ①平衡树一定是丰满树。
②虽然信息项的序列的顺序不一样，但依次生成的二叉排序树确是一样的。
③在二叉排序树上插入新的结点时，不必移动其他结点，只需改动某个结点的指针，由空变为非空即可。 ④在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应的指针域置空即可。
27．长度为12的有序表：Apr,Aug,Dec,Feb,Jan,Jul,Jun,Mar,May,Nov,Oct,Sep,按折半查找法对该表进行查找。在表内各元素等概率情况下查找成功所需的平均比较次数为（ ）。
① 35/12 ②37/12 ③39/12 ④43/12
28．已知一采用开放地址法解决Hash表冲突，要从此Hash表中删除一个记录，正确的做法是 （ ）
①将该元素所在的存储单元清空。 ②将该元素用一个特殊的元素代替
③将与该元素有相同Hash地址的后继元素顺次前移一个位置。 ④用与该元素有相同Hash地址的最后插入表中的元素替代。 四、简答及应用
1． 对长度为20的有序表进行二分查找，试画出它的一棵判定树，并求等概率情况下的平均查找长度。
2． 给定有序表D={006,087,155,188,220,465,505,508,511,586,656,670,700,766,897,908}，用二分查找法在D中查找586，试用图示
20