科目名称： 程序设计 第 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;