中国科学院大学招收攻读硕士学位研究生入学统一考试试题科目名称《程序设计》.docx
《中国科学院大学招收攻读硕士学位研究生入学统一考试试题科目名称《程序设计》.docx》由会员分享，可在线阅读，更多相关《中国科学院大学招收攻读硕士学位研究生入学统一考试试题科目名称《程序设计》.docx（10页珍藏版）》请在冰点文库上搜索。
中国科学院大学招收攻读硕士学位研究生入学统一考试试题科目名称《程序设计》
中国科学院大学
2020年招收攻读硕士学位研究生入学统一考试试题科目名称：
程序设计
考生须知：
1．本试卷满分为150分，全部考试时间总计180分钟。
2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。
一、单项选择题（共30分，每道题3分）
1、请阅读下面的C程序，选择程序的输出结果：
______
#include
intmain（）{
intw[]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
intt=8;
t=（w[t]+w[t+5]）%16;printf（"%d\n",w[t]）;
return0;
}
（A）5（B）6（C）7（D）8
2、以下不是C程序保留字的是:
______
（A）int（B）main_（C）if（D）sizeof
3、请阅读下面C程序，选择程序的输出结果：
______
#includeintx=8;intmain（）{
voidinc（int）;inti;
for（i=0;i<3;i++）{
inc（x）;
}
printf（"%d\n",x）;return0;
}voidinc（intdata）{
++data;
}
（A）8（B）9（C）10（D）11
4、请阅读下面C程序，选择程序的输出结果：
______
#includeintmain（）{
intdata=9;data=~data+1;printf（"%d\n",data）;return0;
}
（A）9（B）-9（C）-10（D）10
5、请阅读下面C程序，选择程序的输出结果：
______
#includetypedefstruct{
intx;inty;
}COORD;intmain（）
{
COORDa[]={{2,4},{3,6}};
COORD*p=&a[1];
--p;
printf（"%d\n",（p[1].x*p[1].y））;
return0;
}
（A）6（B）24（C）8（D）18
6、二叉树是非线性数据结构，_____________________________________。
（A）它不能用顺序存储结构存储
（B）它不能用链式存储结构存储
（C）它既能用顺序存储结构又能用链式存储结构存储
（D）它既不能用顺序存储结构也不能用链式存储结构存储
7、无向图的邻接矩阵一定是______矩阵。
（A）下三角（B）上三角（C）稀疏（D）对称
8、下面函数（n>0）的时间复杂度为______。
voidfunc（intn）{
inti,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#defineL50inta[L]={0,1,2,3,4,5,6,7,8};charb[L]="UCAS";charc[]="WelcometoUCAS!
";intmain（）
{
printf（"%d,%d,%d\n",（int）sizeof（a）,（int）sizeof（b）,（int）sizeof（c））;
return0;
}
3、阅读下列C程序，写出程序输出结果：
__________________
#includeintmain（）{staticinta[][4]={{3,4,5,6},{2,5,7,1},{4,5,6,8},{9,5,1,2}};inti,j,m1=1,m2=0;for（i=0;i<4;i++）for（j=0;j<4;j++）
{if（i==j）m1*=a[i][j];if（i+j==3）m2+=a[i][j];
}printf（"%d,%d\n",m1,m2）;
return0;
}
4、阅读下面C程序，请写出程序输出结果：
__________________
#includeintmain（）{
inta=0,b=2,c=1;switch（a）{
case0:
switch（b）{
case0:
printf（"A"）;case1:
printf（"B"）;case2:
printf（"C"）;
}
case1:
printf（"A"）;
switch（b）{
case0:
printf（"C"）;case1:
printf（"B"）;case2:
printf（"A"）;
}
case2:
printf（"C"）;
switch（c）{
case0:
printf（"C"）;case1:
printf（"B"）;case2:
printf（"A"）;
}
}
return0;
}
5、阅读下面C程序，请写出程序输出结果：
__________________
#includeintmain（）{inti;inta[]={994,995,996,997,998};for（i=0;i<5;i++）a[i]=foo（a[i]）;printf（"%d\n",a[2]+a[3]+1）;
return0;
}intfoo（inty）{
statica=1025;
a--;
return（y+a）>>1;
}
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个数据交换函数，具体代码如下：
#includecharw[]="abcdefgh";
voidswapa（charx,chary）{
chart;t=x;x=y;y=t;
}voidswapb（char*x,char*y）{
chart;
t=*x;*x=*y;*y=t;
}
voidswapc（chara[],charx,chary）{
chart;
t=a[x];a[x]=a[y];a[y]=t;
}voidswapd（charx,chary）{
chart;
t=w[x];w[x]=w[y];w[y]=t;
}intmain（）{swapa（w[0],w[1]）;printf（"%s\n",w）;swapb（&w[2],&w[3]）;printf（"%s\n",w）;swapc（w,4,5）;printf（"%s\n",w）;swapd（6,7）;printf（"%s\n",w）;return0;
}
（1）请写出程序的输出结果。
（2）分析一下为什么有的函数能实现数据交换，而有的却不能，给出原因。
2、请写出下列C程序的输出结果：
#include
#definepower1（x）（x）*（x）#definepower2（x）x*xintfoo（int）;intx=8;
inty=6;inti=1;intmain（）{printf（"%d:
%d\n",i++,power1（y））;
y=foo（x）;printf（"%d:
%d\n",i++,y）;x=power2（x-y）;printf（"%d:
%d\n",i++,x）;y=foo（x）;printf（"%d:
%d\n",i++,y）;return0;
}intfoo（intw）{staticintx=4,y,z;
{
intx=6;y=x--;
printf（"%d:
%d\n",i++,y）;
}
x+=y;z=x+y-w;
printf（"%d:
%d\n",i++,x）;printf（"%d:
%d\n",i++,z）;returnz;
}
3、设二叉树BT的存储结构如下:
12345678910
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*keyMod7，采用线性探测再散列法处理冲突。
将关键字序列{7,8,30,11,18,9,14}散列存储到哈希表中，哈希表的存储空间是一个下标从0开始的一维数组，要求装填因子为0.7。
请
（A）画出所构造的哈希表。
（B）计算等概率情况下，查找成功的平均查找长度。
四、编程（共40分，每道题20分）要求尽可能清晰地给出算法思想、相关数据结构，并写出程序
1、给定一棵二叉链表存储结构表示的二叉树，编写递归算法，计算二叉树中叶子结点的数目。
二叉链表结点的数据结构定义如下：
typedefstructbinode{
ElemTypedata;
structbinode*lchild,*rchild;
}BiNode,*BiTree;
2、给定无向图的邻接表的数据结构如下，求不带权无向连通图G中距离顶点v最远的顶点，输出任意一个满足条件的顶点即可。
说明：
两个顶点的距离是指两个顶点之间的最短路径的长度。
#defineMAX_VERTEX_NUM20
typedefstructArcNode{
intadjvex;//该弧所指向的顶点的位置
structArcNode*nextarc;//指向下一条弧的指针
}ArcNode;typedefstructVNode{
chardata;
//顶点信息
ArcNode*firstarc;
//指向第一条依附该顶点的弧的指针
}VNode;
Typedefstruct{
Nodeadjlist[MAX_VERTEX_NUM];
intvexnum,arcnum;//图的当前顶点数和弧数
}ALGraph;
升级会员 