1、 科目名称：程序设计 第 1 页 共 12 页 中国科学院大学中国科学院大学 20202020 年年招收攻读硕士学位研究生入学统一考试试题招收攻读硕士学位研究生入学统一考试试题 科目名称：科目名称：程序设计程序设计 考生须知：考生须知：1本试卷满分为 150 分，全部考试时间总计 180 分钟。2所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。一、单项选择题（共 30 分，每道题 3 分）1、请阅读下面的 C 程序，选择程序的输出结果：_#include int main()int w=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15;int t=8;t=(
2、wt+wt+5)%16;printf(%dn,wt);return 0;（A）5 （B）6 （C）7 （D）8 2、以下不是 C 程序保留字的是:_ （A）int （B）main_（C）if（D）sizeof 科目名称：程序设计 第 2 页 共 12 页 3、请阅读下面 C 程序，选择程序的输出结果：_#include int x=8;int main()void inc(int);int i;for(i=0;i3;i+)inc(x);printf(%dn,x);return 0;void inc(int data)+data;（A）8（B）9（C）10（D）11 4、请阅读下面 C 程序，选
3、择程序的输出结果：_#include int main()int data=9;data=data+1;printf(%dn,data);return 0;（A）9（B）-9（C）-10（D）10 科目名称：程序设计 第 3 页 共 12 页 5、请阅读下面 C 程序，选择程序的输出结果：_#include typedef struct int x;int y;COORD;int main()COORD a=2,4,3,6;COORD*p=&a1;-p;printf(%dn,(p1.x*p1.y);return 0;（A）6（B）24（C）8（D）18 6、二叉树是非线性数据结构，_。（A）它
4、不能用顺序存储结构存储（B）它不能用链式存储结构存储 （C）它既能用顺序存储结构又能用链式存储结构存储 （D）它既不能用顺序存储结构也不能用链式存储结构存储 7、无向图的邻接矩阵一定是_矩阵。（A）下三角 （B）上三角 （C）稀疏 （D）对称 8、下面函数(n0)的时间复杂度为_。void func(int n)科目名称：程序设计 第 4 页 共 12 页 int i,j;for(i=1,j=0;j=n;j=j+i+);（A）O()（B）O(n)（C）O()（D）O()9、一棵含 18 个结点的二叉树的高度至少为_。（A）3 （B）4 （C）6 （D）5 10、在一棵二叉排序树上，查找关键字为
5、 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，请将正确的结果填写到下面的括号中。(7)8+(3)8=()8(a)16+(b)16=()16(154)10-(22)16=()8 2、假定 int 类型变量占用 4 个字节，阅读下面 C 程序，写出程序的输出结果：_#include#define L 50 int aL=0,1,2,3,4,5,6,7,8;char bL=UCA
6、S;char c=Welcome to UCAS!;int main()科目名称：程序设计 第 5 页 共 12 页 printf(%d,%d,%dn,(int)sizeof(a),(int)sizeof(b),(int)sizeof(c);return 0;3、阅读下列 C 程序，写出程序输出结果：_#include int main()static int a4=3,4,5,6,2,5,7,1,4,5,6,8,9,5,1,2;int i,j,m1=1,m2=0;for(i=0;i4;i+)for(j=0;j4;j+)if(i=j)m1*=aij;if(i+j=3)m2+=aij;print
7、f(%d,%dn,m1,m2);return 0;4、阅读下面 C 程序，请写出程序输出结果：_#include int main()int a=0,b=2,c=1;switch(a)case 0:switch(b)科目名称：程序设计 第 6 页 共 12 页 case 0:printf(A);case 1:printf(B);case 2:printf(C);case 1:printf(A);switch(b)case 0:printf(C);case 1:printf(B);case 2:printf(A);case 2:printf(C);switch(c)case 0:printf(C
8、);case 1:printf(B);case 2:printf(A);return 0;5、阅读下面 C 程序，请写出程序输出结果：_#include int main()int i;int a=994,995,996,997,998;for(i=0;i1;6、经过以下栈的操作后，isEmpty(st)的返回值为_。iniStack(st);push(st,a);push(st,b);push(st,c);pop(st,x);pop(st,y);7、由 4 个权值构成的哈夫曼树共有_个结点。由 7 个权值构成的哈夫曼树共有_个结点。由 n 个权值构成的哈夫曼树共有_个结点。8、一个高度为 L
9、 的满二叉树有以下性质：第 L 层上的结点都是叶子结点，其余各层上每个结点都有两棵非空子树。如果从上到下、自左至右，对二叉树中全部结点进行编号（根结点编号为 1）。请问编号为 n 的结点的双亲结点（若存在）的编号是_，编号为n 的结点的右孩子结点（若存在）的编号是_。9、用冒泡排序对数组98，36，-9，0，47，23，1，8，10，7进行从小到大的排序，前3 趟冒泡的结果分别为：_ _ 科目名称：程序设计 第 8 页 共 12 页 _ 10、已知无向图 G 包含 6 个顶点，分别是 v1，v6，其邻接矩阵如下表所示：V1 V2 V3 V4 V5 V6 V1 0 1 1 0 0 0 V2 1
10、0 0 1 0 1 V3 1 0 0 0 0 1 V4 0 1 0 0 1 0 V5 0 0 0 1 0 1 V6 0 1 1 0 1 0 则从顶点 v1 出发的深度优先遍历序列为_，广度优先遍历序列为_。（注：顶点扫描顺序按从小到大进行。）三、简答题（共 50 分，每道题 10 分）1、本文实现了 4 个数据交换函数，具体代码如下：#include char w=abcdefgh;void swapa(char x,char y)char t;t=x;x=y;y=t;void swapb(char*x,char*y)char t;t=*x;*x=*y;*y=t;科目名称：程序设计 第 9 页
11、 共 12 页 void swapc(char a,char x,char y)char t;t=ax;ax=ay;ay=t;void swapd(char x,char y)char t;t=wx;wx=wy;wy=t;int main()swapa(w0,w1);printf(%sn,w);swapb(&w2,&w3);printf(%sn,w);swapc(w,4,5);printf(%sn,w);swapd(6,7);printf(%sn,w);return 0;（1）请写出程序的输出结果。（2）分析一下为什么有的函数能实现数据交换，而有的却不能，给出原因。2、请写出下列 C 程序的输
12、出结果：#include#define power1(x)(x)*(x)#define power2(x)x*x int foo(int);int x=8;科目名称：程序设计 第 10 页 共 12 页 int y=6;int i=1;int main()printf(%d:%dn,i+,power1(y);y=foo(x);printf(%d:%dn,i+,y);x=power2(x-y);printf(%d:%dn,i+,x);y=foo(x);printf(%d:%dn,i+,y);return 0;int foo(int w)static int x=4,y,z;int x=6;y=x
13、-;printf(%d:%dn,i+,y);x+=y;z=x+y-w;printf(%d:%dn,i+,x);printf(%d:%dn,i+,z);return z;科目名称：程序设计 第 11 页 共 12 页 3、设二叉树 BT 的存储结构如下:1 2 3 4 5 6 7 8 9 10 Lchild 0 0 2 3 7 5 8 0 10 1 Data J H F D B A C E G I Rchild 0 0 0 9 4 0 0 0 0 0 其中 BT 为树根结点的指针，其值为 6；Lchild、Rchild 分别为结点的左、右孩子指针域，Data 为结点的数据域。请（A）画出二叉树
14、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 分）要求尽可能清晰地给出算法思想、相
15、关数据结构，并写出程序 1、给定一棵二叉链表存储结构表示的二叉树，编写递归算法，计算二叉树中叶子结点的数目。二叉链表结点的数据结构定义如下：typedef struct binode 科目名称：程序设计 第 12 页 共 12 页 ElemType data;struct binode*lchild,*rchild;BiNode,*BiTree;2、给定无向图的邻接表的数据结构如下，求不带权无向连通图 G 中距离顶点 v 最远的顶点，输出任意一个满足条件的顶点即可。说明：两个顶点的距离是指两个顶点之间的最短路径的长度。#define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex;/该弧所指向的顶点的位置 struct ArcNode*nextarc;/指向下一条弧的指针 ArcNode;typedef struct VNode char data;/顶点信息 ArcNode*firstarc;/指向第一条依附该顶点的弧的指针 VNode;Typedef struct Node adjlistMAX_VERTEX_NUM;int vexnum,arcnum;/图的当前顶点数和弧数 ALGraph;
