长沙理工大学数据结构期末考试试卷(2)

7．若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )

A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3

8．在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择（ ）排序，如果从节省存储空间的角度来考虑则最好选择（ ）排序。

9．设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是（ ）。

A 40，42，45，55，80，83 B 42，40，45，80，85，88 C 42，40，45，55，80，85 D 42，40，45，85，55，80

10．下列叙述正确的是（ ） A．算法的执行效率与数据的存储结构无关 B．算法的空间复杂度是指算法程序中指令（或语句）的条数 C．算法的有穷性是指算法必须能在执行有限个步骤之后终止 D．算法的时间复杂度是指执行算法程序所需要的时间

四、算法设计题(4小题,共32分)

1．设计判断单链表中元素是否是递增的算法。

2．一个循环队列Queue，只有头指针front，不设尾指针，另设一个含有元素个数的记数器cont，试写出相应的入队算法和出队算法。 3．设计一个在链式存储结构上统计二叉树中结点个数的算法。 4．设计算法，计算图中出度为零的顶点个数。

五、填空题(6小题,共12分)

1．当循环队列为空时，不能进行出队运算，这种情况称为（ ）。 2．已知顺序栈S，在对S进行进栈操作之前首先要判断（ ），在对S进行出栈操作之前首先要判断（ ）。

3．设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复杂度为( )。

4．完全二叉树中第5层上最少有（ ）个结点，最多有（ ）个结点。

5．表示一个有100个顶点，1000条边的有向图的邻接矩阵有（ ）个非零矩阵元素。 6．若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为（ ） 六、简答题(2小题,共10分)

1．设一数列的输入顺序为123456，若采用堆栈结构，并以A和D分别表示入栈和出栈操作，试问通过入出栈操作的合法序列， 能否得到输出顺序为154623的序列。 2．

设有无向图G（如下图所示），要求给出用普里姆算法构造最小生成树所走过的边的集合。

七、名词解释(1小题,共4分) 1．什么是AOE网?