升研教育考研频道为23考研、24考研的同学们整理了“中国科学院大学 2020 年招收攻读硕士学位研究生入学统一考试试题：程序设计 ”的相关信息，希望对正在备考的你有所帮助。考研复习效率不高怎么办？自己备考抓不住重点？想报考985/211等热门院校，但是没把握？升研教育推出考研集训营，全日制封闭式面授，10余年授课经验的老师，浓厚的学习氛围助你冲击目标、一战上研！

中国科学院大学 2020 年招收攻读硕士学位研究生入学统一考试试题：程序设计 

 考生须知：

 1．本试卷满分为 150 分，全部考试时间总计 180 分钟。

 2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。

一、单项选择题（共 30 分，每道题 3 分）

 1、请阅读下面的 C 程序，选择程序的输出结果：

2、以下不是 C 程序保留字的是: ______ 

（A）int 

（B）main_ 

（C）if 

（D） sizeof

3、请阅读下面 C 程序，选择程序的输出结果：______

4、请阅读下面 C 程序，选择程序的输出结果：_____

5、请阅读下面 C 程序，选择程序的输出结果：______

6、 二叉树是非线性数据结构，_____________________________________。 

（A）它不能用顺序存储结构存储 

（B）它不能用链式存储结构存储 

（C）它既能用顺序存储结构又能用链式存储结构存储 

（D）它既不能用顺序存储结构也不能用链式存储结构存储

7、 无向图的邻接矩阵一定是______矩阵。 

（A）下三角 

（B）上三角 

（C）稀疏 

（D）对称 

8、下面函数(n>0)的时间复杂度为______。 

void func(int n) {

9、一棵含 18 个结点的二叉树的高度至少为______。 

（A）3 

（B）4 

（C）6 

（D）5 

10、在一棵二叉排序树上，查找关键字为 34 的结点，依次比较的关键字有可能是______。 

（A）28，36，18，46，34 

（B）18，36，28，46，34 

 （C）46，28，18，36，34 

（D）46，36，18，28，34

二、填空题（共 30 分，每道题 3 分）

 1、我们用(a)_b表示 b 进制的 a，请将正确的结果填写到下面的括号中。

2、假定 int 类型变量占用 4 个字节，阅读下面 C 程序，写出程序的输出结果： __________________

3、阅读下列 C 程序，写出程序输出结果：__________________

4、阅读下面 C 程序，请写出程序输出结果：__________________

5、阅读下面 C 程序，请写出程序输出结果：__________________

6、 经过以下栈的操作后，isEmpty(st)的返回值为______________________。

7、 

由 4 个权值构成的哈夫曼树共有________________________个结点。 

由 7 个权值构成的哈夫曼树共有________________________个结点。 

由 n 个权值构成的哈夫曼树共有________________________个结点。 

8、一个高度为 L 的满二叉树有以下性质：第 L 层上的结点都是叶子结点，其余各层上每 个结点都有两棵非空子树。如果从上到下、自左至右，对二叉树中全部结点进行编号（根 结点编号为 1）。

请问编号为 n 的结点的双亲结点（若存在）的编号是________，编号为 n 的结点的右孩子结点（若存在）的编号是__________。

9、用冒泡排序对数组{98，36，-9，0，47，23，1，8，10，7}进行从小到大的排序，前 3 趟冒泡的结果分别为：

 ________________________________________________________________________ 

________________________________________________________________________

10、已知无向图 G 包含 6 个顶点，分别是 v1，…，v6，其邻接矩阵如下表所示：

则从顶点 v1 出发的深度优先遍历序列为________________________________________， 广度优先遍历序列为____________________________________________。（注：顶点扫描 顺序按从小到大进行。）

三、简答题（共 50 分，每道题 10 分） 

1、本文实现了 4 个数据交换函数，具体代码如下：

（1） 请写出程序的输出结果。 

（2） 分析一下为什么有的函数能实现数据交换，而有的却不能，给出原因。

2、请写出下列 C 程序的输出结果：

3、设二叉树 BT 的存储结构如下:

其中 BT 为树根结点的指针，其值为 

6；Lchild、Rchild 分别为结点的左、右孩子指针域， Data 为结点的数据域。请 

（A）画出二叉树 BT 的逻辑结构。 

（B）写出按前序、中序、后序遍历该二叉树所得到的结点序列。 

（C）画出二叉树的后序线索树。

4、请调整序列(40, 55, 49, 73, 12, 27, 98, 81, 64, 36)为小顶堆，并给出调整过程 中序列的变化过程。

5、选取哈希函数为 H(key) = 3*key Mod 

7，采用线性探测再散列法处理冲突。将关键字 序列{7, 8, 30, 11, 18, 9, 14}散列存储到哈希表中，哈希表的存储空间是一个下标从 0 开始的一维数组，要求装填因子为 0.7。请 

（A）画出所构造的哈希表。 

（B）计算等概率情况下，查找成功的平均查找长度。

四、编程（共 40 分，每道题 20 分）要求尽可能清晰地给出算法思想、相关数据结构， 并写出程序 

1、给定一棵二叉链表存储结构表示的二叉树，编写递归算法，计算二叉树中叶子结点的 数目。

二叉链表结点的数据结构定义如下： 

typedef struct binode {

2、给定无向图的邻接表的数据结构如下，求不带权无向连通图 G 中距离顶点 v 最远的顶 点，输出任意一个满足条件的顶点即可。说明：两个顶点的距离是指两个顶点之间的最 短路径的长度。