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

                     

贡献者: 待更新

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:第四 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>的形式表示.

图
图 2:第七题图

8. 八,编程题(本题 24 分,每小题 12 分)

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


致读者: 小时百科一直以来坚持所有内容免费,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 10 元,我们一个星期内就能脱离亏损, 并保证在接下来的一整年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利