2020年中国科学院大学程序设计考研真题.docx

中国科学院大学 2020 年招收攻读硕士学位研究生入学统一考试试题科目名称：程序设计 考生须知： 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=(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 科 目 名 称 ： 程 序 设 计 第 13 页 共 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 程序，选择程序的输出结果： #include int main() int data=9; data=data+1; printf(%dn,data); return 0; （A）9 （B）-9 （C）-10 （D）10 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） 它不能用顺序存储结构存储 （B） 它不能用链式存储结构存储 （C） 它既能用顺序存储结构又能用链式存储结构存储 （D） 它既不能用顺序存储结构也不能用链式存储结构存储 7、 无向图的邻接矩阵一定是 矩阵。 （A）下三角（B）上三角（C）稀疏（D）对称 8、下面函数(n0)的时间复杂度为 。 void func(int n) 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、在一棵二叉排序树上，查找关键字为 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=UCAS; char c=Welcome to UCAS!; int main() 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; printf(%d,%dn,m1,m2); return 0; 4、阅读下面 C 程序，请写出程序输出结果： #include int main() int a=0,b=2,c=1; switch (a) case 0: switch (b) 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 ); 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 的满二叉树有以下性质：第 L 层上的结点都是叶子结点，其余各层上每个结点都有两棵非空子树。如果从上到下、自左至右，对二叉树中全部结点进行编号（根结点编号为 1）。请问编号为 n 的结点的双亲结点（若存在）的编号是 ，编号为 n 的结点的右孩子结点（若存在）的编号是 。 9、用冒泡排序对数组98，36，-9，0，47，23，1，8，10，7进行从小到大的排序，前3 趟冒泡的结果分别为： 10、已知无向图 G 包含 6 个顶点，分别是 v1，v6，其邻接矩阵如下表所示： V1 V2 V3 V4 V5 V6 V1 0 1 1 0 0 0 V2 1 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; 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 程序的输出结果： #include #define power1(x) (x)*(x) #define power2(x) x*x int foo(int); int x=8; 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-; printf(%d:%dn,i+,y); x+=y; z=x+y-w; printf(%d:%dn,i+,x); printf(%d:%dn,i+,z); return z; 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） 画出二叉树 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 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;