北京大学数据结构与算法2014期末考试题考试试题(答案)+B树

1

北京大学信息科学技术学院考试试卷 考试科目： 数据结构与算法A 姓名： 学号： 考试时间： 2014 年 1 月 1 日 任课教师:

以下以下为答题纸，共 页

以下为试题和答题纸，试题共 5 页。

北京大学考场纪律 1、考生进入考场后，按照监考人员安排隔位就座，将学生证放在桌面上。无学生证者不能参加考试；迟到超过15分钟不得入场。在考试开始30分钟后方可交卷出场。 2、除必要的文具外，其它所有物品（包括空白纸张、手机、或有存储、编程、查询功能的电子用品等）不得带入座位，已经带入考场的必须放在监考人员指定的位置。 3、考试使用的试题、答卷、草稿纸由监考人员统一发放，考试结束时收回，一律不准带出考场。若有试题印制问题请向监考教师提出，不得向其他考生询问。提前答完试卷，应举手示意请监考人员收卷后方可离开；交卷后不得

在考场内逗留或在附近高声交谈。未交卷擅自离开考场，不得重新进入考场答卷。考试结束时间到，考生立即停止答卷，在座位上等待监考人员收卷清点后，方可离场。

4、考生要严格遵守考场规则，在规定时间内独立完成答卷。不准交头接耳，不准偷看、夹带、抄袭或者有意让他人抄袭答题内容，不准接传答案或者试卷等。凡有违纪作弊者，一经发现，当场取消其考试资格，并根据《北京大学本科考试工作与学术规范条例》及相关规定严肃处理。

5、考生须确认自己填写的个人信息真实、准确，并承担信息填写错误带

来的一切责任与后果。 学校倡议所有考生以北京大学学生的荣誉与诚信答卷，共同维护北京大学的学术声誉。

装

订

线

内

不

要

答

题

一、填空（27分）

1.（2分）当各边上的权值A 时，BFS算法可用来解决单源最短路径问题。

A．均相等B．均互不相等C．不一定相等

2.（4分）有向图G如下图所示：

（1）写出所有可能的拓扑序列：1234, 1324, 2134。

（2）添加一条弧v2v1，或者v3v2之后, 则仅有惟一的拓扑序列。

3.（2分）设有如下所示无向图G，用Prim算法构造最小生成树所走过的边

的集合E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)} （用边（2，3）代替（1，2）也可以）。

4.（2分）如果只想得到1000个元素组成的序列中第5个最小元素之前的部

分排序的序列，用 C 方法最快。

A．起泡排序B．快速排列C．堆排序D．简单选择排序

5.（2分）若要求尽可能快地对序列进行稳定的排序，则应选 B

A．快速排序B．归并排序C．冒泡排序 D.归并排序

2

6.（2分）在文件局部有序或文件长度较小的情况下，最佳的排序方法是A 。

A.直接插入排序

B. 冒泡排序

C. 直接选择排序

D.归并排序

7.（2分）设输入的关键字满足K1>K2> … >K n，缓冲区大小为m ，用置换

选择排序方法可产生n/m+1 个初始归并段。

8.（2分）设有13个初始归并段，其长度分别为28，16，37，42，5，9，13，

14，20，17，30，12，18。试计算最佳4路归并树的带权路径长度WPL= 480 。

9.（3分）设有序顺序表中的元素依次为017, 094, 154, 170, 275, 503, 509, 512,

553, 612, 677, 765, 897, 908，则对其进行折半查找时，等概率下搜索成功的平均查找长度和不成功的平均查找长度分别为45/14 和59/15 。

10.（2分）设散列表长度为14（地址下标为0…13），哈希函数为H(key)=key%11，

表中已有数据的关键字为15,38,61,84共四个，现要将关键字为49的结点将加入表中，用二次探查法解决冲突，则放入的位置是 D 。

A．8 B．3 C．5 D．9

11.（2分）在一棵含有1023个关键字的4阶B树中进行查找（不读取数据主

文件），至多读盘 C 次。

A.7

B. 8

C. 10

D. 9

12.（2分）在一棵阶为k 的红黑树中，内部结点最少有2k-1 个；从根到叶的

简单路径长度的范围为[k,2k]。

二、辨析与简答（30分）

1.（8分）将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。

散列表是一个下标从0开始的一维数组，散列函数为：H(key) = (key * 3) MOD 7，处理冲突采用线性探测法，要求装填（载）因子为0.7。

(1) 请画出所构造的散列表。

3

(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。

2.（6分）设有如下一棵3阶B树，请画出在其中插入关键码19后的B树，并给出

插入过程中的访外（读写）次数；在此基础上再删除关键码48，请画出删除后的B树及删除过程中的访外（读写）次数。

4

5

答案：

插入19后结点持续分裂到根，整个树高增1，

读盘3

次，写盘

7次，共读写10次。结果为：

删除48时需先与后继50交换，后删除，删除后各结点依然满足阶的要求，故不再调整，删除过程中写盘2次，若假设之前操作读进的页块不再读的话，读盘2次，或者从根开始重新读盘则4次，结果如下：

3. （6分）将下列字符序列 E A S Y Q U E S T I O N 依次插入到初始为空的红黑

6

树（RB-tree ）中，请画出最终得到的红黑树。（用圆圈表示红色结点，方框表示黑色结点，外部空叶结点可省略不画）。 4. （4分）利用广义表的Head 和Ｔail 运算，把原子d 分别从下列广义表中分离出来，L1＝(((((a),b),d),e))；L2＝（a,(b,((d)),e ））。

答案：head(tail(head(tail(LS))))

5. （6分）将关键码1，2，3，...，（2k-1）依次插入到一棵初始为空的AVL 树中，试证明结果是一棵高度为k 的完全满二叉树。

答案：答案：

采用数学归纳法。

1. 当1=k 时，命题现任成立（只有一个点的情况）

2. 假设，当n k =时命题成立（即依次插入121--n 个关键码递增的结点构成一棵

高度为n 的完全满二叉树），下面讨论1+=n k 的情况。

由于关键码的插入顺序单调递增，因此每次插入的新结点的初始位置一定是最右链的叶子的右儿子。

按照插入顺序，当插入到关键码121--n 时，构成一棵高度为n 的完全满二叉O

E S

A I Q U

T Y N

7

树（归纳假设）。接着，考虑从关键码12

-n 到12221++--n n （共22-n 个关键码），它们和根结点的右子树构成了12

1--n 个连续递增的关键码，根据归纳假设，插入关键码12221++--n n 后，根结点的右子树成为一棵高度为n 的完全满二叉树。然

后，下一个关键码22221++--n n 破坏了根结点的平衡（右子树比左子树深度大2），

根据AVL 树的旋转要求，树将以n 2为根（之后根结点不再参与旋转，因此这就是

最终的根结点），左子树是一棵高度为n 的完全满二叉树；而右子树几乎是一棵高度为1-n 的完全满二叉树，唯一差别在于它的最右边还挂着222

21++--n n 这个结点。最后，关键码32221++--n n 到12-n 插入到树中，根据归纳假设，它们将把右子树构造成一棵高度为n 的完全满二叉树。此时，整棵树便是一棵高度为1+n 的完全满二叉树。

综上，结论成立。

三、算法填空 （18分）

阅读和完成下面的代码（每空可不限一条语句）。

1. （10分）以单向链表为存储结构，实现选择排序算法（得到非递减序列）。

struct node {

int key;

node *next;

};

node* sort_linked_list(node* head) {

i = head;

while (i!=NULL) {

填空1 node *j = i->next ;

while (j!=NULL) {

if ( 填空2 i->key>j->key ) 填空3 swap(i->key,j->key) ;

填空4 j = j->next ;

}

填空5 i = i->next ;

}

return head;

}

2.（8分）下面是败者树在内部结点从右分支向上比赛的成员函数实现，请将空

缺部分补充完整。

template

void LoserTree::Play(int p, int lc, int rc, int(*winner)(T A[], int b, int c), int(*loser)(T A[], int b, int c)) {

B[p] = loser(L, lc, rc);

int temp1, temp2;

（1）temp1 = winner(L, lc, rc);

while (p>1 && （2）p%2 ) {

temp2 = winner(L, temp1, B[p/2]);

（3）B[p/2] = loser(L, temp1, B[p/2]);

temp1 = temp2;

p/=2;

}

（4）B[p/2] = temp1;

}

3.（8分）下述算法实现在图G中计算从顶点i到顶点j之间长度为len的简单路

径条数。图的ADT如下：

Class Graph {

public:

int VerticesNum();

int EdgesNum();

8

Edge FirstEdge(int oneVertex);

Edge NextEdge(Edge preEdge);

bool IsEdge(Edge onEdge);

int FromVertex(Edge oneEdge);

int ToVertex(Edge oneEdge);

};

int visited[MAXSIZE]; // 初始化为0

int GetPathNum_Len(Graph& G, int i, int j, int len) {

if (填空1 i == j && len == 0) return 1;

sum = 0; // sum表示通过本结点的路径数

visited[i] = 1;

for (Edge e = G.FirstEdge(i); G.IsEdge(e); e = G.NextEdge(e)) {

int v = G.ToVertex(e);

if (!visited[v])

填空2 sum += GetPathNum_Len(G, v, j, len - 1)

}// for

visited[i] = 0; //本题允许曾经被访问过的结点出现在另一条路径中return sum;

} // GetPathNum_Len

四、算法设计与分析（25分）

请尽量按照试题中的要求来写高效率的可读算法。应该申明算法思想，在代码

种加以恰当的注释。

1.伸展树是一种自平衡的BST树，它可以通过旋转来实现树结构的动态调整。

伸展树结点的数据结构定义如下：

struct TreeNode{

int data;

TreeNode * father,* left,* right;

9

};

其成员函数包括：

1）Delete zig(TreeNode* x); 其功能是删除以x结点为根的子树；

2）Splay(TreeNode* x , TreeNode* f)；其功能是将x旋转为f的子结点（f 是x的祖先）。特殊的，把x旋转到根结点即Splay(x, NULL)。

请运用上述给定的成员函数，实现删除树rt中所有大于u小于v的结点（假设u, v是Splay树中的结点，且树种所有的节点值不重复）。

函数原型为：void DeleteSubTree(TreeNode* rt, TreeNode* u, TreeNode* v )

解答：把u结点旋转到根；把v旋转为u的右儿子；删除v结点的左子树前面几句各3分，最后一句1分。如果思路、注释各1分，不写则扣。

void DeleteUV(TreeNode* rt, TreeNode* u, TreeNode* v ) {

Splay(u, NULL);

Splay(v, u);

Delete(v->lchild);

v->lchild = NULL;

}

10

本文来源：https://www.bwwdw.com/article/c6zq.html