上海海事大学 2011 年数据结构

贡献者： xzllxls

1. 一。判断题（本题 20 分，每小题 2 分）

　　 1.为了很方便地插入和删除数据，可以使用双向链表存放数据。

　　 2.两个栈共享一片连续内存空间时，为了提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。

　　 3.数组是同类型值的集合。

　　 4.在查找树（二叉排序树）中插入一个新结点，总是插入到叶子结点的下面。

　　 5.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中顶点的个数有关，而与图的边数无关。

　　 6.顺序存储方式只能用于存储线性结构，不能用于存储二叉树。

　　 7.在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。

　　 8.数据的逻辑结构被分为集合结构、线性结构、树型结构、图结构四种，

　　 9.将一棵树转换成二叉树后，根结点没有左子树。

　　 10.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

2. 二。填空题（本题 30 分，每空 2 分）

　　 1.分析下列程序段，其时间复杂度分别为：（(1)），（(2)）.

i=1;
while(i<=n)
    i=i*3;

void test(int m) {
    int i=0, s=0;
    while (s<n) {
        i++;
        s=s+i;
    }
}

　　 2.堆栈的插入和删除操作都是在栈顶位置进行，而队列的（(3) )操作在队尾进行，( (4) )操作在队头进行。

　　 3.对具有 n 个结点的二叉树采用二叉链表存储结构，则该链表中有（(5) )个指针域，其中有（(6) )个指针域用于链接孩子结点，( (7) )个 指针域空闲存放着 NULL.

　　 4.对线性表采用折半查找方法，该线性表必须采用（(8) )存储结构，并且数据元素按值（(9) ).

　　 5.除了顺序存储结构与链式存储结构之外，数据的存储结构通常还有（(10) )结构和（(11) )结构。

　　 6.已知具有 4 行 6 列的矩阵 A 采用行序为主序方式存储，每个元素占用 4 个存储单元，并且 a[3][4]的存储地址为 1234，元素 a[1][1]的存储地址是（(12) ).

　　 7.对于长度为 n 的线性表，采用顺序存储结构存储，插入或删除一个元素的时间复杂度为（(13) ).

　　 8.若对线性表进行的操作主要不是插入和删除，则该线性表宜采用（(14) )存储结构，若频繁地对线性表进行插入和删除操作，则该线性表宜采用（(09) )存储结构。

3. 三、选择题（本题 20 分，每空 2 分）

　　 1.权值为{1.2.6.8}的四个结点构成的哈夫曼树的带权路径长度是（）。
A) 18 $\qquad$ B) 28 $\qquad$ C) 19 $\qquad$ D)29

　　 2.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。
A)1/2 $\qquad$ B) 1 $\qquad$ C)2 $\qquad$ D)4

　　 3.无向图 G=(V,E)，其中：V={a,b,c.d.e.f). E={ab)(a,)(a.c)(b.c).(c.f), (f.d).(e.d)}, 对该图进行深度优先遍历，得到的顶点序列正确的是（）。
A) a,b,e,c.d,f $\qquad$ B) a,c,f,e,b.d $\qquad$ C) a,e,b,c,fd $\qquad$ D) a,e.d.f.c,b

　　 4.有 8 个结点的无向连通图最少有（）条边。
A)5 $\qquad$ B) 6 $\qquad$ C) 7 $\qquad$ D) 8

　　 5.在一棵度为了的树中，度为 3 的节点个数为 2，度为 2 的节点个数为 1,则度为 0 的节点个数为（）。
A)4 $\qquad$ B)5 $\qquad$ C)6 $\qquad$ D)7

　　 6.对广义表 L(a,b),(c,d.),(e,f)执行操作 tail(tail(L))的结果是（）。
A)(e,f) $\qquad$ B) ((e,f)) $\qquad$ C)(f) $\qquad$ D)()

　　 7.引起循环队列队头位置发生变化的操作是（）.
A)出队 $\qquad$ B)入队 $\qquad$ C)取队头元素 $\qquad$ D)取队尾元素

　　 8.一个栈的入栈序列是 a.b.c.d.e.则栈的不可能的输出序列是（）。
A) edcba $\qquad$ B) decba $\qquad$ C) dceab $\qquad$ D) abcde

　　 9.下列排序算法中，不稳定的排序是（）。
A)直接插入排序 $\qquad$ B)冒泡排序 $\qquad$ C)堆排序 $\qquad$ D)选择排序

　　 10.顺序栈 S 中 top 为栈顶指针，指向栈顶元素所在的位置，elem 为存放栈的数组，则元素 e 进栈操作的主要语句为（）
A)s.elem [ top] =e; s.top-s.top+1; $\qquad$ B)s.elem [ top+1] =e; s.top=s.top+1;
C) s.top-s.top+1; s.elem [ top+1 ] =e; $\qquad$ D) s.top=s.top+I; s.elem [ top ]=e;

4. 四。(本题 20 分，每小题 10 分)

　　 1.某二叉树的结点数据采用顺序存储结构如下：

　　 试解答下列问题：
1)画出该二叉树;
2)画出把此二叉树还原成森林的图;

　　 2.已知一棵二叉树的中序序列和后序序列分别为，
中序序列：CDBAFGEKHL
后序序列：DCBGFKLHEA
请根据画出该树的结构并写出其先序序列。

5. 五，(本题 12 分)

　　 设散列表为 HT[0..12]，即表的长度为 13.散列函数为：H(key)=key%13.采用线性探测再散列法解决冲突，若插入的关键码序列为（25, 9, 36, 43, 15, 28, 51, 67, 94）.
1.试画出插入这 9 个关键码后的做列表。
2.计算在等概率情况下查找成功的平均查找长度 ASL.

6. 六，(本题 12 分，每小题 6 分)

　　 已知待排序记录的关键字序列为{435，183，506, 289，318, 705，76，632, 826, 245)，需要按关键字值递增的次序进行排序，请分别写出用下列两种排序方法进行第一趟扫描的过程和结果。
1.以第一个元素为基准的快速排序
2.冒泡排序

7. 七，(本题 12 分)

　　 右图是一个无向图，试用 Prim 算法从顶点 2 开始求该图的最小生成树，并给出依次产生的边，边用<i, j>的形式表示。

8. 八，编程题（本题 24 分，每小题 12 分）

　　 1.已知 A, B 为两个递增有序的线性表，试编写函数实现对 A 表的如下操作：删去其中那些在 B 表中出现的元素。
2.已知 T 为一棵二叉排序树，设计算法按递减次序打印各节点的值。