D. 仅有尾指针的单循环链表

3. 有64个结点的完全二叉树的深度为(假设根结点的层次为1。 A. 8 B. 7 C. 6 D. 5

4. 对于键值序列(2,33,21,18,65,38,7,49,24,86,用筛选法建堆,必须从键值为的结点开始。

A. 86 B. 2 C. 65 D. 38

5. 设图 G 用邻接表存储,则求每个顶点入度的算法时间复杂度为。 A. O(n B. O(n+e C. O(n*n D. O(n*e

二、判断题:(每小题2分,共10分

判断下列各题是否正确,若正确,在题后的括号内填“T”,否则填“F”。

1. 在队满情况下不能作入队处理,否则,将产生“上溢”。( 2. 基于插入思想的排序算法都是稳定的。(

3. 一个有向图的邻接表和逆邻接表中的结点个数不一定相等。( 4. 若一棵二叉树的任一非叶子结点度为2,则该二叉树为满二叉树。( 5. 广义表是线性表的推广,因此也可以采用顺序方式进行存储。( 三、填空题:(每小题2分,共10分

1. 在单链表中,删除指针 P 所指结点的后继结点的语句是:。

2. 有向图 G 用邻接矩阵 A[1..n,1..n] 存储表示,其第 i 行的所有元素之和等于顶点 i 的。

3. 基数排序算法的时间复杂度为。

4. 平衡二叉树中每个结点的平衡因子定义为。

5. 利用直接插入排序算法对有 n 个元素的数据表进行排序,在最坏情况下,元素的移动次为。

四、解答下列各题:(每小题10分,共40分

1. 写出采用顺序方式存储的栈的类型描述及相应的入栈、出栈操作的示意图。 2. 已知数据表为(60,20,31,5,44,55,61,30,80,150,4,29,写出采用希尔排序算法进行排序的详细过程和结果(假设增量序列 dlta[] ={6,3,1}。

3. 已知图 G 的邻接表存储结构示意图如下所示,画出它的逻辑关系示意图,以及按深度优先搜索和广度优先搜索进行遍历所得到的顶点序列。

4. 设散列函数为 H(K = K mod 5,散列表的地址空间为 0..6,初始时散列表为空,用线性探测法解决冲突,请写出依次插入23,14,9,6,30, 12,18时散列地址的计算过程及结果,以及最后得到的散列表。

五、算法设计题:(前两题必做,每题15分,共30分;第三题为附加题,选做,10分 1. 设计算法将一个带头结点的单循环链表 A 分解为两个具有相同结构的链表 B、C,其中:B 表中的结点为 A 表中元素的顺序号为奇数的结点,而 C 表中的结点为 A 表中元素的顺序号为偶数的结点。(要求利用原表结点。

2. 已知 S 为顺序栈。写出 S 的存储结构类型描述。试编写算法实现将元素 x 插入栈 S 的入栈操作 Push(S,x 和删除栈顶元素的出栈操作

Pop(S。

3. 已知一棵完全二叉树存于顺序表 sa 中,sa.elem[1..sa.last] 包含各结点值。试编写算法根据此顺序存储结构建立该二叉树的二叉链表 T。