2018-2019-1 数据结构期末试卷¶

2017级

科目：数据结构与算法主讲教师：胡卉芪出卷人：胡卉芪

题目1 (8分)-C++基本概念¶

（1）关于C++与C语言关系的描述中，（）是错误的。

A. C语言是C++语言的一个子集

B. C语言与C++语言是兼容的

C. C++语言对C语言进行了一些改进

D. C++语言和C语言都是面向对象的

（2）已知：int m=10; 则在下列表示引用的方法中，（）是正确的。

A. int &x=m;

B. int &y=10;

C. int &z;

D. float &t=&m;

（3）（）不是构造函数的特征

A. 构造函数的函数名与类名相同

B. 构造函数可以重载

C. 构造函数可以设置缺省参数

D. 构造函数必须指定函数返回类型说明

（4）如没有使用关键字定义类的数据成员，则默认为（）类型。

A. private

B. public

C. protected

D. friend

题目2 (6分)-代码阅读¶

请阅读下述程序，按照print或cout函数，依次写出程序所有的输出。

举例：对下述a+b的程序

#include<stdio.h>
int main(){
    int a, b;
    a=b=5;
    print(“a=%d, b=%d;\n”);
    print(“a+b=%d;\n”);
    return 0;
}

上例输出程序将包含两行:

a=5, b=5;

a+b=10;

阅读程序如下：

#include <iostream>
using namespace std;
int fun(int n, int*m)
{
  if(n%3 ==0)
    *m=n++/3;
  else if (n%5==0)
    *m=n++/5;
}
int rec(int x,int y)
{ 
   cout<<x<<" "<<y<<endl;
   return (x+y);  
}
int main()
{
    int m =6, p=10;
fun(m,&p); 
cout << m <<" "<< p << endl;
int a=2,b=5,c=8;
cout<<rec(rec(a+c,b),a-c);
    return 0;
}

请依次写出程序所有的输出：

题目3(9分)-代码改错¶

请指出下述C++代码中三处语法错误，语法错误是指导致程序无法编译通过的错误，每个指出的错误简述可能的解决方案, 并填入下述表格的错误1-3中(表格中错误0为举例，每个错误3分，多写不加分)。

该程序功能是倒序输出各给定的字符串。

1.  #include <iostream>
2.  class Base
3.  {
4.    public:
5.       Base() {
6.         x = 0; 
7.       }
8.       ~Base() {}
9.       void display() { 
10.           cout<<”x=”<<x<<endl;
11.      }
12.   private:
13.      int x;
14. };
15. class A : private Base
16. {
17.   public: 
18.       A(){
19.        m = 5; 
20.       }
21.       ~A() {}
22.       void display_a() {
23.             cout<<”x=”<<x<<endl;
24.             cout<<”m=”<<m<<endl;
25.       }
26.   private:
27.      int m;
28. };
29. int main()
30. {
31.   A a;
32.   a.A();
33.   a.display();
34.   a.display_a();
35.   a.m =18;
36.   return 0;
37. }

错误	类型	错误描述	改正方法
错误0	编译错误	未使用using namespace std; 导致10、23、24行cout与endl符号无法识别	在行1-2间添加代码using namespace std;
错误1
错误2
错误3

题目4 (9分)-栈和队列¶

设有编号为1，2，3，4的四辆列车，依次进入一个栈式结构的车站A。现允许先进站的列车在后续列车进站前离开车站。比如当1号车在入站后，且先于2、3、4号车进站前出站，而2, 3, 4号车依次入站后出站，那么列车最终出站的顺序为1, 4, 3, 2。

(1) 请问以下两种列车最终的出站顺序是否分别存在。如若存在，请写出一种具体列车的进站与出站顺序。比如当出站顺序为1,4,3,2 时。那么列车具体的进站顺序为 “1进站A，1 出站 A， 2 进站 A， 3进站 A， 4进站 A， 4出站 A，3 出站 A，2出站 A”。(6分)

a) 出站顺序 2, 1, 4, 3

b) 出站顺序 2, 4, 1, 3

(2) 现在增加另一个栈式结构的车站B，但不再允许先进站的列车在后续列车进站前离开车站，也就是只有所有车都进入到A站或者B站之后，才允许车离开。允许的操作是A站和B站之间， A站的车可以出站并进站到B站，同样 B站的车可以出站并进站到A站。那么当1， 2， 3， 4车依次入站时，请在下面第一步操作 “1 进站 A” 后补充完整的操作流程，能使 1, 2, 3, 4 车依次离开A与B站。 (3分)

1进站 A,

题目5(7分)-哈希表¶

给定一个关键字序列：{38，25，74，63，52，48，11}。假设哈希表的长度为7，哈希函数为H(k) = k%7 。

(1) 用链地址法解决哈希冲突，试画出相应的哈希表。(4分)

(2) 在第(1)题构建的哈希表的基础上，给出一个查找的key为60，问能否在哈希表中查找成功，计算出其在哈希表中查找的比较次数(假定计算哈希值并访问相应的链表也是一次比较，即比较的次数至少是1)。(3分)

题目6 -堆（9分）¶

现有一颗完全二叉树 A，我们知道完全二叉树可以用数组存储。A的数组存储为 [15, 13, 8, 12, 16, 3, 5, 7, 5’, 14, 11] (数组中有两个5，一个为5，另一个表示为5’)。

(a) 请根据该存储的数组画出对应的完全二叉树。(3分)

(b) 该完全二叉树A是一个最大堆么？如若不是，通过堆的调整操作对A进行调整，使其变成一个最大堆, 请画出调整后最大堆的属性结构。(3分)

(c) 我们知道利用堆可以进行排序。现在用堆排序的方法对A的数组进行排序，在排序前我们观察到两个相同的元素 5 是出现在 5’ 之前的。请问利用堆排序后产生的序列中 5 与5’ 次序谁会在前？(3分)

题目7-排序 (7分)¶

给定一个长度为8的整型数组Ａ：{16，32，149，27，38，54，25，6}，要求对其中的元素进行从小到大排序。请根据以下排序方法和规定写出相应的中间排序结果。注意，对于下列题目中描述的第k趟排序的结果，这里的k都是从1开始，而非从0开始。

(1) 采用快速排序法，取第一个元素16作为基准值，写出第1趟排序后的临时结果（即以16作为分隔值分隔完成后的结果）。(3分)

(2) 写出低位基数排序法第2趟排序后的临时结果。(4分)

题目8 -B树（10分）¶

给出下述的4颗B树，分别画出下述插入/删除完成之后的B树。其中删除操作中，B树将借调左右兄弟节点，优先借调右兄弟的节点。注：每个插入/删除操作均为分开的对下面给出的B树直接进行操作，并不是4个连续操作。给出的B树及操作如下，每颗树中每个节点的键值个数不超过4。

（1）插入42 (2 分)

（2）插入53 (2分)

(3) 插入 26 (3分)

（4）删除 28 (3分)

题目9 (10分)-图¶

给定一个有向无环图：

(1) 试画出该图的邻接表。这里要求每个顶点对应的邻接点的访问顺序按照值从小到大排序，例如3的邻接点5，8，7的访问顺序应是5，7，8。(3分)

(2) 在第(1)题的基础上，以顶点1为起始点，写出相应的广度优先搜索序列。(3分)

(3) 给出该图的一种拓扑排序序列。(4分)

题目10 -数据结构应用题（7分）¶

有K 个从大到小的有序数组记为 $A_1，A_2 , … A_K$ , 每个包含n个元素（n>>K）。一共具有K*n个元素，现要求出这个`K*n个元素中最大的K个元素。比如K=3, n=4 时，假定3个数组 A_1=[10，8，7，5]， A_2=[9，7，4，2], A_3=[7，6，5，4]，那么最大的3个元素为10, 9, 8。

请写出相应的算法思路。并分析给出方法的复杂度。注：思路可以是伪代码，也可通过文字描述大致流程，但需要清晰且没有歧义。请直接阅读 (1)(2)两个小题后再选择作答。

(1) 请写出任意的一种求得最大K个元素的方法，并分析复杂度。(4分)

(2) 现要求用一个复杂度为 $O(k* log k) $的方法求出最大的K个元素。如果（1）中的方法已经做到，可以直接标注 “同上”。(3分)

题目11-程序设计题(一) (9 分)¶

给定一棵二叉树：

树中的一个节点node包含三个属性value, left和right。假设p是指向某一个节点的指针，我们可以通过p->value, p->left 和 p->right来分别访问该节点的值，左孩子和右孩子。如果某个节点不存在，则指针值可以设为NULL。用于打印某个值，可以使用print(打印内容) 或者cout<<打印内容这两个接口。假设该二叉树已经构建好，root是指向根节点的指针，请按照下列给出的接口和输入输出用伪代码的实现相应功能。允许增加函数或者改变函数接口，也允许使用任意其他数据结构，但请做详尽解释。

(1) 输出二叉树的中序遍历序列。接口：InOrderTraverse(root)；输入：一个指向二叉树根节点的指针 root；输出：返回值为空，打印中序遍历序列。(3分)

(2) 计算二叉树的叶子节点个数。接口：LeafCount( root, count) 输入: 一个指向二叉树根节点的指针root 及一个计算用于统计叶子节点个数的变量count，count已初始化为0；输出：返回叶子节点个数count。 (3分)

(3) 判断二叉树是否是二分查找树。接口：isBST(root)；输入：一个指向二叉树根节点的指针root；输出：返回一个bool类型的值，如果是二分查找树返回true,不是就返回false。(3分)

题目12-程序设计题(二) (9分)¶

给定一个二叉树, 该二叉树所有节点的值都是唯一的，树中的一个节点node包含三个属性value, left和right。假设p是指向某一个节点的指针，我们可以通过p->value, p->left 和 p->right来分别访问该节点的值，左孩子和右孩子。如果某个节点不存在，则指针值可以设为NULL。用于打印某个值，可以使用print(打印内容) 或者cout<<打印内容这两个接口如果某个孩子节点不存在，则相应属性值为NULL。root是指向根节点的指针，请按照下列给出的接口和输入输出用伪代码的实现相应功能。允许增加函数或者改变函数接口，也允许使用任意其他数据结构，但请做详尽解释。

(1) 现在要找到从该树根节点到一个指定节点的路径。接口：GetPath(root, x, stack)；输入：一个指向树根的指针root、一个指定节点的值x和一个用来存储路径的栈stack；输出：GetPath返回一个bool类型的值，若该树中存在节点x，则将该树根节点到节点x路径上的所有节点从底到顶依次存放到输入的栈结构stack中，并且GetPath返回true；若该树中不存在节点x，则GetPath返回false。栈的相关操作可以直接使用STL中函数，例如入栈、出栈分别表示为stack.push()、stack.pop(); (4分)

(2) 接下来需要找到该树中两个指定节点的最近公共祖先。

接口：LowestCommonAncestor(root, p, q)；输入：一个指向树根的指针root和两个指定的节点指针p、q（p、q 为不同节点且均存在于给定的二叉树中）；输出：LowestCommonAncestor返回一个指向p、q最近公共祖先节点的指针。

最近公共祖先的定义：对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。

例如：给定二叉树如下：

如果输入p = 7, q = 0, 则LowestCommonAncestor输出为3；

如果输入p = 5, q = 4, 则LowestCommonAncestor输出为5，因为根据定义最近公共祖先节点可以为节点本身。(5分)

提示：如有需要，可以直接调用上题实现的GetPath函数。第(1) 小题的正确性并不影响第(2)小题的给分。

2018-2019-1 数据结构 期末试卷¶