上海海事大学 2012 年数据结构
贡献者： xzllxls
1. 一.判断题(本题 20 分，每小题 2 分)
1.线性的数据结构可以顺序存储，也可以链接存储;非线性的数据结构只能链接存储。
2. B+树中所有叶子结点都处在同一层次上,且每个叶子结点中关键字个数都是相等的。
3.单链表从任何一个结点出发，都能访问到所有结点。
4.排序的目的就是要将一组无序的记录序列按从小到大的顺序调整。
5.存储在顺序存储器上的顺序文件不能进行折半查找。
6.网络的最小代价生成树是唯一的。
7.磁带是顺序存取的外存储设备。
8.将一棵树转换成二叉树后，二叉树的根结点一定没有右子树。
9.所有叶子结点都处于同一层的二叉树一定是完全二叉树。
10.在 AOE 网中，任何一个关键活动提前完成，都将使整个工程提前完成。
2. 二、填空题(本题 30 分，每空 2 分) .
1.分析下列程序段，其时间复杂度分别为:_ (1) ._ (2)_
i=1;
while(i<=n*n)
i=i*2;
int i=0, s=0;
while (s<n*n){
i++;
s=s+i;
}
2.顺序表.栈和队列都是（(3)）结构，顺序表可以在其（(4)）位置插入和删除元素;对于栈只能在（(5)）插入和删除元素; 对于队列只能在（(6)）插入元素和另一端删除元素。
3.广义表 A=(a,b,(c ,d),(e,(f, g)))的长度是（(7) )。深度是（(8)），取表头和表尾函数分别为 head()和 ail(),则 head (head (tail (tail (A))))=（(9)），而从表中取出原子项 d 的运算为（(10））。
4.有一个二维数组 A[1..6][0..7].每个数组元素占用 6 个存储单元，并且 a[3][4]的存储地址为 1280,若按行序为主序方式存储，数组元素 A[2][3]的存储地址是（(11)）;若按列序为主序方式存储，数组元素 A[2][3]的存储地址是（(12)）.
5.在堆排序、快速排序和归并排序三种算法中，若仅从存储空间考虑，则应首先选取（(13)）方法:若只从平均情况下排序最快考虑。则应选取（(14））方法;若只从排序结果的稳定性考虑，则应选取（（15））方法。
3. 三、选择题(本题 20 分，每空 2 分)
1. 算法分析的两个主要方面是( )。
A)时间复杂度和空间复杂度 $\qquad$ B)正确性和简单性
C)可读性和健壮性 $\qquad$ D)数据复杂性和程序复杂性
2.线性表若采用顺序存储结构时，要求内存中可用存储单元的地址( )。
A)必须是连续的 $\qquad$ B)部分地址必须是连续的
C)一定是不连续的 $\qquad$ D)连续不连续都可以
3.在一个单链表中，已知 q 所指结点是 p 所指结点的前驱结点，若在 q 和 p 之间插入 S 点，则执行( )。
A) p->next=S; S->nexl=q $\qquad$ B) S->next=p->next ; p->next=S
C) q->next=S; S->next=p $\qquad$ D) q->next=S->*next ; S->next=p
4.如果一个栈的进栈序列是 ABCD(即，A 先进栈，然后 B、C 和 D 依次进栈),，允许在进栈过程中可以退栈，且规定每个元素进栈和退栈各一次，那么不可能得到的退栈序列是( )
A) DCBA $\qquad$ B) ACBD $\qquad$ C) CDBA $\qquad$ D) DBAC
5. 如果 G 是一个具有 n(n>1)个顶点的连通无向图，T 是 G 的一棵生成树，那么 T 有(、)条边。 A) n $\qquad$ B) n-1 $\qquad$ C) n+1 $\qquad$ D) n+2
6. 在对顺序表进行折半查找时，要求该表必须( )。
A)以顺序方式存储
B)以链接方式存储
C)以顺序方式存储，且结点按关键字有序排序
D)以链接方式存储，且结点按关键字有序排序
7.一个有 n 个顶点的有向图最多有( )条边。
A) n $\qquad$ B) n(n-1) $\qquad$ C) n(n-1)/2 $\qquad$ D) 2n
8. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用( ) 存储方式最节省运行时间。
A)单链表 $\qquad$ B)仅有头指针的单循环链表
C)双向链表 $\qquad$ D)有尾指针的单循环链表
9.用一维数细 Q[0..n-1]来存储一个循环队列，每个数组单元存放一 个队列元素，记 f 为队头指针，为队尾指针，都为数组下标，若空队列的初始状态 f=τ=0,则计算队列中元素个数的公式(式中 mod 为取余)为( )。
A) r-f $\qquad$ B) (n+r-f) mod n $\qquad$ C) n-1 $\qquad$ D) n
10.若二叉树的叶子结点个数为 n0.度数为 2 的结点个数为 2，则 n0=（)。
A) n2-1 $\qquad$ B) n2 $\qquad$ C) n2+1 $\qquad$ D) 2*n2
4. 四，(本题 20 分，每小题 10 分)
1.已知某系统在通信联络中可能出现八个字符: s. H、M. T. U. C.1. E.它们出现频率分别为: 0.09. 0.07. 0.16. 0.23. 0.12. 0.06. 0.08. 0.19，试利用它们作为叶子结点构造一棵 Huffman 树(哈夫曼树)，并设计这八个字符的哈夫曼编码。
2. 已知一棵二叉树的先序序列和中序序列分别为，
先序序列: ABDGEHCFKL
中序序列: DGBHEACKFL
请画出该树的结构并写出其后序序列。
5. 五，(本题 12 分)
设散列表为 HT0..16]，即表的长度为 17.散列函数为: H(key)=key%17,采用二次(平方)探测再散列法解决冲突，若插入的关键码序列为{125, 119, 136, 143, 115, 218,151, 167, 194, 83, 171, 186, 253, 95, 200}.
1.试画出插入这 15 个关键码后的散列表。
2.计算在等概率情况下查找成功的平均查找长度 ASL.
6. 七. (本题 12 分)
右图是一个无向图，试用 Kruskal 算法求该图的最小生成树，并给出依次产生的边，连接顶点 i 和 j 的边用<i, j>的形式表示。
7. 八。编程题(本题 24 分，每小题 12 分)
1.没有一个表头为 fist 的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点按逆序链接。
2.具有 n 个结点的完全二叉树存放在一维数组 A[1..n]中，试据此建立一棵用二又链表表示的二叉树，根由 tree 指向。二叉树的二叉链表存储结构统一表示如下:
typedef struct BiNode {
ElemType data;
struct BiNode *lchild, * rchild;
}BiNode,* BiTree;
BiTree Create(ElemType AD, int i)
{
……
}