2020年中国科学院大学硕士研究生考试真题之程序设计.pdf
科目名称: 程序设计 第 1页 共 12页 中国科学院大学 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 科目名称: 程序设计 第 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程序,选择程序的 输出结果 : _ #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= -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) 科目名称: 程序设计 第 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、 在一棵二叉排序树上,查找关键字为 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() 科目名称: 程序设计 第 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; 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) 科目名称: 程序设计 第 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 ); 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趟 冒泡的 结果分别为: _ _ 科目名称: 程序设计 第 8页 共 12页 _ 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; 科目名称: 程序设计 第 9页 共 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( 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; 科目名称: 程序设计 第 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-; 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) 画出二叉树 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 科目名称: 程序设计 第 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;