V10 0 0 0 0 0 0 0 0 0 0
当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出： （1）．以顶点V1为出发点的唯一的深度优先遍历； （2）．以顶点V1为出发点的唯一的广度优先遍历； （3）．该图唯一的拓扑有序序列。
7、已知一数据集合的逻辑结构为：B = (K, R), 其中，K = {k1, k2, ?, k8}，R={
K2 K3 K7 K1 K4 K5 K6 K8 （2）拓扑序列K1，K2，K3，K4，K8，K5，K6，K7
五、算法设计题
1、编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。
解：Status Build_AdjList(ALGraph &G) //输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表 { InitALGraph(G); scanf(\
if(v<0) return ERROR; //顶点数不能为负 G.vexnum=v; scanf(\、;
if(a<0) return ERROR; //边数不能为负 G.arcnum=a; for(m=0;m G.vertices[m].data=getchar(); //输入各顶点的符号 for(m=1;m<=a;m++) 31 { t=getchar();h=getchar(); //t为弧尾,h为弧头 if((i=LocateVex(G,t))<0) return ERROR; if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到 p=(ArcNode*)malloc(sizeof(ArcNode)); if(!G.vertices.[i].firstarC、 G.vertices[i].firstarc=p; else { for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarC、; q->nextarc=p; } p->adjvex=j;p->nextarc=NULL; }//while return OK; }//Build_AdjList 2.试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w) ，即删除一条边的操作。（如果要删除所有从第i个顶点出发的边呢？ 提示： 将邻接矩阵的第i行全部置0 ） 解：//本题中的图G均为有向无权图。 Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w) { if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(G.arcs[i][j].adj) { G.arcs[i][j].adj=0; G.arcnum--; } return OK; }//Delete_Arc 3.试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。 32 int visited[MAXSIZE]; //指示顶点是否在当前路径上 int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j 是否有路径,是则返回1,否则返回0 { if(i==j) return 1; //i就是j else { visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarC、 { k=p->adjvex; if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径 }//for }//else }//exist_path_DFS 第九章 查找 一、填空题 1、在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。 2、线性有序表（a1，a2，a3，?，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。 3、假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。 4、折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它 将依次与表中元素 28，6，12，20 比较大小。 5、在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 散列查找 。 6、散列法存储的基本思想是由 关键字的值 决定数据的存储地址。 7、有一个表长为m的散列表，初始状态为空，现将n（n 8、设一哈希表表长M为100 ，用除留余数法构造哈希函数，即H（K）=K MOD P（P<=M）, 为使函数具有较好性能，P应选（ 97 ） 9、在各种查找方法中，平均查找长度与结点个数无关的是哈希查找法 33 10、对线性表进行二分查找时，要求线性表必须以 顺序方式存储，且结点按关键字有序排列。 11、在分块查找方法中，首先查找索引，然后再查找相应的 块。 12、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为_n__次；当使用监视哨时，若查找失败，则比较关键字的次数为_ n+1。 13、在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为_____6,9,11,12 _____。 14、在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__5 15、已知二叉排序树的左右子树均不为空，则左子树_上所有结点的值均小于它的根结点值，_右子树_上所有结点的值均大于它的根结点的值。 二、单项选择题 1、在表长为ｎ的链表中进行线性查找，它的平均查找长度为（ B ）。 A、ＡＳＬ＝ｎ; B、ＡＳＬ＝（ｎ＋１）／２; C、ＡＳＬ＝n＋１; D、ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１ 2、折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（ A 比较大小，查找结果是失败。 A、20，70，30，50 B、30，88，70，50 C、20，50 D、30，88，50 3、对22个记录的有序表作折半查找，当查找失败时，至少需要比较（ C ）次关键字。 A、3 B、4 C、5 D、 6 4、链表适用于（ A ）查找。 A、顺序 B、二分法 C、顺序，也能二分法 D、随机 5、折半搜索与二叉搜索树的时间性能（ C ）。 A、相同 B、完全不同 C、有时不相同 D、数量级都是O（log2n） 6、散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。元素59存放在散列表中的地址是（ D ）。 A、 8 B. 9 C、 10 D、11 7、当采用分快查找时，数据的组织方式为 ( B )。 A、数据分成若干块，每块内数据有序 B、数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D、数据分成若干块，每块（除最后一块外）中数据个数需相同 34 8、散列函数有一个共同的性质，即函数值应当以( D )取其值域的每个值。 A、最大概率 B、最小概率 C、平均概率 D、同等概率 9、假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( D )。 A、k-1次 B. k次 C、 k+1次 D、k（k+1）/2次 10、哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行( )次探测。 A、k B、k+1 C、k(k+1)/2 D、1+k(k+1)/2 11、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( C ) 型调整以使其平衡。 A、LL B、LR C、RL D、RR 12、二叉查找树的查找效率与二叉树的( C )、有关, 在 (B )时其查找效率最低。 (1): A、高度 B、结点的多少 C、树型 D、结点的位置 (2): A、结点太多 B、完全二叉树 C、呈单枝树 D、结点太复杂。 13、在顺序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找关键码值11，所需的关键码比较次数为（ C ）。 A、 2 B) 3 C、 4 D、 5 14、对包含n个元素的哈希表进行查找，平均查找长度为（ D ）。 A、 O(log2n) B、 O(n) C、 O(nlog2n) D、不直接依赖于n 15、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( C )。 A、(n-1)/2 B、n/2 C、 (n+1)/2 D、n 16、下面关于二分查找的叙述正确的是 ( D )。 A、表必须有序，表可以顺序方式存储，也可以链表方式存储 B、表必须有序，而且只能从小到大排列 C、表必须有序且表中数据必须是整型，实型或字符型 D、表必须有序，且表只能以顺序方式存储 17. 对线性表进行二分查找时，要求线性表必须（ B ）。 A、以顺序方式存储 B、以顺序方式存储,且数据元素有序 C、以链接方式存储 D、以链接方式存储,且数据元素有序 18、适用于折半查找的表的存储方式及元素排列要求为( D )。 A、链接方式存储，元素无序 B、链接方式存储，元素有序 C、顺序方式存储，元素无序 D、顺序方式存储，元素有序 19、用二分（对半）查找表的元素的速度比用顺序法( D )。 35