一、单选：1、为便于判别有向图中是否存在回路,可借助于 A.广度优先搜索算 B.最小生成树算法 C.最短路径算 D.拓扑排序算法2、数据结构在逻辑上可以分为3、下述编码中（）不是前缀码。4、下列陈述正确的是：对于哈希函数H（key）=key%17,被称为同义词的关键字。5、若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素，查找成功的情况6有一个链队列中，front和rear分别为头指针和尾指针，则将一个p指针所指的结点插入队列应执行算法分析的目的是计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入，输出在一个n个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为二、填空：1、在对一组记录（13 25 3 9 38 17 46 29 6 31 ）进行希尔（shell）排序时，取d=3，则一趟希尔排序后记录：2、已知有向图的邻接表如下图所示：则该图中从结点1出发的广度优先遍历序列是（），深度优先遍历序列是（）3、在具有m个单元的循环队列中，队头指针为front，队尾指针为fear，则队满的条件是。4、设有向无环图G中的有向边集合E=ab ac db de，请写出该有向图G的一种拓扑排序序列。5、已知二叉树的前序遍历序列为ABDCEF，中序遍历序列为DBAEFC，则它的后序遍历序列为6、若用一个大小为8的数组来实现循环队列，且当rear和front的值分别为0.5.当从中删除一个元素，再加入两个元素后7、在一个长度为n的顺序表中,删除第i(1in)个元素时，需要向前移动（）个元素8、一个采用了顺序存储结构的线性表，其长度为20，若在第5个元素前插入一个元素，需要移动（）个元素，若接着又将元素删除，那么需要移动（）个元素。9、在对一组记录（53 41 96 22 16 75 61 46 88）进入堆排序时，根据初始记录构成初始堆（大栈堆）后，这10、假定一个有向图的顶点集为a b c d e f 边集为ac ae cf dc ed则出度为0的顶点个数为（），入度为1的顶点个数为（）三、简答题：已知一表为（43 21 67 9 40 78 2 41 70 90 ）按表中顺序依次插入初始为空的二叉排序树，要求（1）用括号法表示建立的二叉排序树（用#表示空树）（2）求出在等概率情况下查找成功的平均查找长度2、若一个无向连通图以邻接表作为存储结构，请设计一个函数，功能是删除图中的一条边（I j）,已知类型edgnd包含，类型AdjList表示顶点数组类型，每个数组元素包含first（指针成员）3、已知图G的邻接表如下图所示：请写出从顶点0出发，该图的深度优先遍历序列和广度优先遍历序列4、已知有n个顶点的有向图邻接表，编写一个函数求出该图中指定顶点的出度。已知边类型edgenode,包含next(指出下一条边)，和adjvex(序号)成员。类型adjlist表示顶点数组类型，每个数组元素包含link（指向第一条边）和vex成员。5、已知数据序列 13 3 17 31 29 11 18 21 7 19写出希尔排序每一趟排序的结果，（设d=5 2 1 ）