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)}。
41
（1） 按上述顺序输入后，画出其相应的邻接表；
（2） 在该邻接表上，从顶点4开始，写出DFS序列和BFS序列。
17．图简答题17-1所示为一无向连通网络，先要求根据prim算法构造出它的最小生成树。
第九章 查找表
二、填空题
1.对任何集合A而言，A的每一个成员a称为A的一个________，记为________。 2.空集是________的集合，记为________。
3.在集合这种逻辑结构中，任何结点之间都不存在________关系，这是集合这种逻辑结构的基本特点。
4.集合中没有相同的________。作为一个数学概念，集合的元素没有________。 5.数据元素之间的逻辑关系反映的是________。
6.对于集合这逻辑结构来说，其中的数据元素之间也可以有各种各样的非逻辑关系，但任何一对数据元素之间没有________关系，即没有________关系。
7.查找表按其所包括的运算的不同分为________查找表和________查找表。 8.查找表中主关键字指的是________，次关键字指的是________。 9.静态查找表包括________、________、________三种基本运算。
42
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.索引表反映了这些\的有关特性。
43
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个结点的二叉排序树的平均查找长度为________，其时间效率
44
很高。
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]=________; /*前插法链入新结点*/ }
45
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库DS复习资料1(11)在线全文阅读。
相关推荐：