上 海 海 事 大 学 试 卷
2010 — 2011 学年第二学期期终考试
《 数 据 结 构 》（A卷）
班级 学号 姓名 总分
题 目
得 分
阅卷人
填空题（本题 15 分， 每空1 分）
1. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p所指结点之间插入s所指结点，则执行（1） , （2） 。
2．具有n个节点的满二叉树的叶子节点的个数是（3） 。
3．已知一棵二叉树的先序序列是 abdfjgcehi，中序序列是bjfdgachei，则它的后序序列是： （4） 。
4. 在下面的程序段中，s=s+p语句的执行次数为（5） ，p*=j语句的执行次数为（6） ，该程序段的时间复杂度为（7） 。
int i=0, s=0;
while (++i<=n){
int p=1;
for (int j=1; j<=i; j++)
p*=j;
s=s+p;
}
5．若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出的是 （8） 。
6．设s1='Shanghai Maritime University'，则SubString(s1, 10, 8) = （9） 。
7．数据结构可以形式地定义为是一个两元组（D，S）。其中，D是数据元素的有限集，S是 （10） 上关系的有限集。
8．哈希表中常用的地址冲突处理方法有 （11） 、 （12） 、 （13） 和公共溢出区法。
9．在有序表{2,5,7,10,15,18,23,35,41,52,56}中，用折半查找法检索出关键字2和关键字18的比较次数分别是 （14） 、 （15） 。
选择题（本题 20 分， 每小题2分）
1．若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是_________。
A. 二叉排序树 B. 哈夫曼树 C. 线索二叉树 D. 堆
2. 计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出和________等5个特性。
A．可执行性、可移植性、可扩充性
B．可执行性、有穷性、确定性
C．确定性、有穷性、稳定性
D．易读性、稳定性、确定性
3. 如图所示，若从顶点a出发按深度优先搜索法进行遍历，则可能得到的一种顶点序列为_________。
A. a, b, e, c, d, f B. a, c, f, e, b, d C. a, e, b, c, f, d D. a, e, f, d, c, b
4．具有65个结点的完全二叉树其深度为 （根的层次值为1）。
A. 8 B. 7 C. 6 D. 5
5． 在待排序的元素序列基本有序的前提下，效率最高的排序方法是________。
A．选择排序 B. 快速排序 C. 插入排序 D. 合并排序
6．判定一个循环队列Q（最多有m个元素，采用“少用一个元素空间”来判别队空、队满）为满的条件是__________。
A. Q->front==Q->rear B. Q-> front! =Q->rear
C. Q->front==(Q->rear + 1)%m D. Q->front!=(Q->rear + 1)%m
7．一组记录的关键字为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为_______。
A．38，40，46，56，79，84
B．40，38，46，79，56，84
C．40，38，46，56，79，84
D．40，38，46，84，56，79
8．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用_____存储方式最节省运行时间。
A. 单链表 B. 仅有头指针的单循环链表
C. 双向链表 D. 有尾指针的单循环链表
9．空串的长度是 。
A. 0 B. 1 C. 2 D. 不确定
10．栈的操作原则是 。
A. 先进先出 B. 后进先出
C. 只能在一端进行插入 D. 只能一端进行删除
应用题（本题 35 分，每小题5分）
1．对于下图所示二叉树，试给出：
（1）它的顺序存储结构示意图。
（2）它的二叉链表存储结构示意图。
（3）它的三叉链表存储结构示意图。
2．假设用于通讯的电文由8个字母（a、b、c、d、e、f、g、h）组成，字母出现的频率为0.05，0.23，0.03，0.08，0.10，0.13，0.34，0.04。试为这8个字母构造赫夫曼树并设计赫夫曼编码。
3．对于给定关键字序列{41，62，13，84，35，96，57，39}使用冒泡排序方法进行排序（结果为非递减），请写出每一趟排序结果。
4．给出下图所示有向图的拓扑序列及得到该拓扑序列的详细过程。
5．已知关键字序列{19，14，23，01，68，20，84，27，55，11，10，79}。
（1）要求将此序列散列到长度为16的表中，哈希函数为 H (key) = key %13，并用二次探测再散列法解决地址冲突；
(2)在等概率情况下，求查找成功时的平均查找长度。
6．对于下图所示的无向图，按普里姆(prim)算法从顶点A出发求其最小生成树，要求写出求解的顺序步骤。
7. 设查找的关键字序列为{45，37， 86，99，76，43，19}，请画出该序列生成的二叉排序树及其构造过程。
算法填空题（本题10分，每空2分）
以下是顺序表的顺序查找算法，请补充缺失语句。
int Search_Seq(SSTable ST, KeyType key){
ST.elem[0].key = (1) ;
for(i=ST.length; !EQ( (2) );--i);
return i;
}
折半查找。
int Search_Bin(SSTable ST,keyType key)
{
low=1; high=ST.length;
while( (3) )
{
mid= (4) ;
if (key==ST.elem[mid].key) return mid;
else if(key<ST.elem[mid].key) high=mid+1;
else low= (5) ;
}
return 0;
}
编程题（本大题共20分）
1．假设有两个按元素值递增有序排列的线性表A和B，均以单链表做存储结构，请编写算法将A表和B表归并成一个按元素值非递减有序（允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表。（10分）
编写算法,对n个关键字取整数值的记录序列进行整理,以使所有关键字为负值的记录排在所有关键字为非负值的记录之前,要求：采用顺序存储结构,至多使用一个记录的辅助存储空间。（10分）
|
