南邮通达数据结构B期末试卷及答案

《 数据结构B 》期末试卷（A）

本试卷共 4 页； 考试时间 110 分钟； 专业

班级 学号 姓名

一、填空题（20分，共10题）

1. 数据结构主要研究数据的______结构，数据的存储结构以及在数据上执行的运算。

自觉 2. 设顺序表长度为100，若下标从0开始计，则删除元素a10需要移动______个元素。 3. 一棵二叉树中，若叶结点的个数为2011，则度为2的结点个数为______。 4. 有向图进行拓扑排序时，没有输出图中所有顶点，说明图中存在______。 5. 线性表采用二分搜索必须满足两个条件：线性表关键字必须是______；存储结构

必须采用顺序存储结构。

6. 二叉搜索树的______序遍历序列是一个按关键字递增排列的有序序列。

7. 设有一组记录的关键字为{19, 14, 1, 69, 20, 27, 55, 79}，散列函数为h(key) =

key%11，散列函数值为3的有______个。

8. 快速排序算法平均情况下的渐近时间复杂度为O(______)。 9. 采用二次探查法解决冲突可能产生_______聚集。 10. 图常见的两种存储结构有邻接矩阵和_______。

遵装 守考订试线规则内，诚不信考要试，答绝不题作弊 二、选择题（20分，共10题）

1. 一个算法必须在执行有穷步之后结束。这是算法的_______。

A. 有穷性 B. 正确性 C. 确定性 D. 可行性 2. 在指针p所指示的结点之后插入新结点s的操作是_______。

A. s->link=p;p->link=s; B. s->link=p->link;p->link=s; C. s->link=p->link;p=s; D. p->link=s;s->link=p; 3. 栈和队列的共同点是_______。

A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点 4. 后缀表达式：5 3 2 * 3 + 3 / +的值为_______。

A. 18 B. 7 C. 9 D. 8

授课：XXX

5. 6. 7. 8.

9.

高度为5的二叉树至多有_______个结点。 A. 5 B. 10 C. 31 D. 32

采用对半查找方法查找长度为n的线性表时，时间复杂度为_______。 A. O(n2) B. O(nlog2n) C. O(n) D. O(log2n) n个顶点的无向图采用邻接矩阵表示，则该矩阵的大小是_______。 A. n B. (n - 1)2 C. n2 D. n – 1 一个无向连通图的生成树是一个_______连通子图。 A. 极大 B. 极小 C. 有时极大 D. 有时候极小 下列排序方法中，排序过程中的比较次数与排序方法无关的是_______。 A. 简单选择排序法 B. 直接插入排序法 C. 快速排序法 D. 冒泡排序法

散列表的长度为11，下标范围是[0，10]，散列函数为h(key) = key % 11。采用线性探查法解决冲突，依次将关键字7，38，5，16插入空的散列表中。则关键字16在散列表中存放的下标是_______。 A. 5 B. 6 C. 7 D. 8

三、简答题（30分，共5题）

1． 有二叉树如图1所示，写出该二叉树的前序遍历序列和中序遍历序列。

ABACDE

图1

EBDC

图2

2． 写出图2所有可能的拓扑排序。

3． 设有向图的邻接表表示如图3所示，请给出每个顶点的入度。

0∧1234534450∧0121∧∧∧

0∧

图3

授课：XXX

4． 空二叉搜索树中依次插入33，44，99，22，11，55，画出最终所构建二叉搜索树。 5． 设W={5, 6, 7, 8, 9}，

（1）画出由权值集合W构造的哈夫曼树。 （2）计算加权路径长度。

四、判断题（10分，共5题）

1． 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。 2． 简单选择排序是稳定的排序算法。

3． 散列函数越复杂越好，因为这样随机性好，冲突概率小。 4． 完全二叉树一定存在度为1的结点。

5． 在一非空二叉树的中序遍历中，根结点的右边是其右子树上的所有结点。

五、程序填空题（10分，共1题）

1. 以下程序是对半搜索的迭代实现，请填写完整。 BOOL BSearch2(List lst, KeyType k, T *x) { int mid, low=(1)_________, high = lst.Size－1; while ( (2)__________) { mid=(low+high)/2; if (k授课：XXX

六、编程题（10分，共1题）

1. 用二叉链表方式存储二叉树。试编写函数Count1，求一棵二叉树的结点总数。并编写Count接口函数，让其调用Count1函数。 typedef int K; typedef struct btnode{ K Element; struct btnode* LChild, *RChild; }BTNode; typedef struct btree{ struct btnode* Root; }BTree; 自觉 《 数据结构B 》期末试卷（A）答案 遵装 守考订试线规则内，诚不信考要试，答绝不题作弊 一、 填空题（20分，共10题） 1 逻辑 2 3 2010 4 有向回路 5 有序 6 中 7 2 8 nlog2n 9 二次 10 邻接表 二、选择题（20分，共10题） 1 A 2 B 3 C 4 D 5 C 6 D 7 C 8 B 9 A 10 D 三、简答题（30分，共5题） 1． 前序遍历序列：BADCE （3分）授课：XXX

中序遍历序列：ABCDE （3分） 2．每个1分，全对再加2分 BACDE BACED BCADE BCAED 3．每个1分 顶点 0 1 2 3 4 5 4．

33221199入度 3 2 1 1 2 1

5．

35157520116（4分）

WPL = (5+6) * 3 + (7+8+9)*2 = 33 + 48 = 81 （2分）

四、判断题（10分，每题2分）

1 ×

2 × 3 × 4 × 5 √ 五、程序填空题（10分，每空2分）

(1) 0

(2) low <= high

授课：XXX

(3) mid－1

(4) k>lst.Elements[mid].Key (5) return FALSE;

六、编程题（10分，共1题）

1．

int Count(BTree Bt){ return Count 1(Bt.Root); }

int Count 1(BTNode* p){ if(!p) return 0; else return Count1(p->LChild)+ Count1(p->RChild) + 1; }

（注：可编辑下载，若有不当之处，请指正，谢谢!）

授课：XXX