贵州大学计算机840考研模拟试题A831试题及答案Word下载.docx
- 文档编号:6644965
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:39
- 大小:1.34MB
贵州大学计算机840考研模拟试题A831试题及答案Word下载.docx
《贵州大学计算机840考研模拟试题A831试题及答案Word下载.docx》由会员分享,可在线阅读,更多相关《贵州大学计算机840考研模拟试题A831试题及答案Word下载.docx(39页珍藏版)》请在冰点文库上搜索。
,a[6-i]);
B.for(i=0;
7;
i++)printf("
C.for(i=0;
i<
D.for(i=0;
7、已知i=1,sum=0,执行以下程序段后sum的值为___。
while(i++<
100)
sum+=i;
A.5050B.5049C.5051D.5005
8、以下能对二维数组y进行初始化的语句是___。
A.inty[2][]={{1,0,1},{5,2,3}};
B.inty[][3]={{1,2,3},{4,5,6}};
C.inty[2][4]={{1,2,3},{4,5},{6}};
D.inty[][3]={{1,0,1,0},{},{1,1}};
9、若有以下宏定义:
#defineN2
#defineY(n)(N+1)*n
则执行语句intz;
z=2*(N+Y(5));
后z的值是___。
A、50 B、34 C、19 D、无定值
10、以下正确的函数说明是___。
A、doublefun()B、floatfun(inta;
intb)
C、intfun(inta,b)D、intfun(chara[][])
11、对于intx=7,*p=&
x,*q;
,表达式q=p,*q+=3的值是:
______。
A.7B.9C.10D.机器数
12、若有定义floata=1.2,*p=&
a;
且p的值为65496。
若执行p+=2;
则p的值等于____。
A.65496B.65498C.65500D.65504
13、若有以下的说明和语句,则在执行for语句后,*(*(pt+l)+2)表示的数组元素是____。
intt[3][3],*pt[3],k;
for(k=0;
k<
3;
k++)pt[k]=&
t[k][0];
A.t[2][0]B.t[2][2]C.t[l][2]D.t[2][l]
14、在一个C源文件中,若要定义一个只允许本源文件所有函数使用的全局变量,其他文件中不允许使用,则该变量需要使用的存储类别是_______。
A.autoB.registerC.externD.static
15、定义以下结构体类型,假设不采用字节对齐。
structs
{
charb;
floatf;
};
则语句printf("
%d"
sizeof(structs))的输出结果为________。
A.3B.5C.6D.4
16、下面列说法错误的是()
(1)算法原地工作的含义是指不需要任何额外的辅助空间。
(2)在相同的规模n下,复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法。
(3)所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界。
(4)同一个算法,实现语言的级别越高,执行效率就越低。
A.
(1)B.
(1),
(2)C.
(1),(4)D.(3)
17、设矩阵A是一对称矩阵(a(i,j)=a(j,i),1<
=i,j<
=8),若每个矩阵元素占3个单元,将其上三角部分(包括对角线)按行序为主序存放在数组B中,B的首地址为1000,则矩阵元素a(6,7)的地址为( )
A.1031 B.1093 C.1096 D.1032
18、线性表采用链式存储时,结点的存储地址()
A.必须是不连续的B.连续与否均可
C.必须是连续的D.和头结点的存储地址相连续
19、设数组data[m]作为循环队列SQ的存储空间,front为头指针,rear为尾指针,则执行出队操作后其头指针的值为()
A.front=front+1B.front=(front+1)%(m-1)
C.front=(front-1)%mD.front=(front+1)%m
20、在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为()
A.4B.5C.6D.7
21、一棵含18个结点的树的高度至少为()
A.2B.3C.4D.5
22、在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为()
A.eB.2eC.n^2-eD.n^2-2e
23、在索引顺序表中查找一个元素,可用的且最快的方法是()
A.用顺序查找法确定元素所在块,再用顺序查找法在相应块中查找
B.用顺序查找法确定元素所在块,再用二分查找法在相应块中查找
C.用二分查找法确定元素所在块,再用顺序查找法在相应块中查找
D.用二分查找法确定元素所在块,再用二分查找法在相应块中查找
24、用某种排序方法对关键字序列(25,84,21,47,15,27,68,35,20)进行排序时,序列的变化情况如下:
20,15,21,25,47,27,68,35,84
15,20,21,25,35,27,47,68,84
15,20,21,25,27,35,47,68,84
则所采用的排序方法是()
A.选择排序B.希尔排序C.归并排序D.快速排序
25、在下列排序方法中,平均时间性能为O(nologn)且空间性能最好的是()
A.快速排序B.堆排序C.归并排序D.基数排序
二、程序阅读题(4小题,每小题5分,共20分)
1、下列程序的输出结果为?
#include<
stdio.h>
intmain(){
intx=2,y;
switch(x)
{
case1:
y=x;
break;
case2:
y=-x;
case3:
y=x*3;
}
printf("
y=%d.\n"
y);
return0;
}
输出__________________
2、下列程序的输出结果是?
intmain(){
inta[5]={1,3,5,7,9};
intb,*q=&
a[1];
b=(*--q)++;
b=%d,"
b);
a[0]=%d\n"
a[0]);
输出___________________
3、下列程序的输出结果是?
intfun(chara[][2]);
inta[4][4]={{1,2,3,4},{5,6,7,8},{11,12,13,14},{15,16,17,18}};
inti=0,j=0,s=0;
while(i++<
4)
if(i==2||i==4)continue;
j=0;
do{
s+=a[i][j];
j++;
}while(j<
4);
}
s);
输出_______________
4、以下程序的输出结果是?
intfun(intx,inty)
{
staticintm=0,i=2;
i+=m+1;
m=i+x+y;
returnm;
intj=4,m=1,k;
k=fun(j,m);
%d,"
k);
输出__________
三、简答题(6小题,每小题5分,共30分)
1、对于下图所示的二叉树,写出该二叉树的前序中序和后续遍历序列。
答案:
2、已知一个无向图的顶点集为{a,b,c,d,e},其邻接矩阵如下所示,请回答:
(1)画出该图的图形,并回答除了用邻接矩阵外,无向图得存储还有哪些方式?
(2)根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历,写出相应的遍历序列。
3、一个散列表如下图所示:
回答下列问题:
(1)对表中关键字35,20,33,和48进行查找时,所需进行的比较次数各为多少?
(2)该散列表在等概率查找时查找成功的平均查找长度为多少?
4、假设通信电文使用的字符集为{a,b,c,d,e,f},各字符的在电文中出现的频度分别为:
34,5,12,23,8,18,试为这6个字符设计哈夫曼编码。
请先画出你所构造的哈夫曼树(要求树中左孩子结点的权值小于右孩子结点的权值),再分别写出每个字符对应的编码。
5、简要回答数据结构所研究的内容,并说明算法与数据结构的关系。
四、应用题(5小题,每小题10分,共50分)
1、编程求出分数序列2/1,3/2,5/3,8/5,13/8,……的前20项之和。
2、设有一带头结点的单链表L,结点结构为[data,next]。
(1)试画出链表L结点个数等于3时的结构图;
(2)编写一个函数,参数为L,判断该单链表L中的元素是否成等差关系,即:
设各元素值次为a1,a2,a3,…,an,判断ai+1-ai=ai-ai-1是否成立。
3、请用两个栈实现队列操作,给出数据结构定义并描述算法思想,至少写出入队、出队操作的代码。
4、机器人走迷宫。
地上有一个m行和n列的方格,一个机器人从坐标(0,0)的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。
例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7=18。
但是,它不能进入方格(35,38),因为3+5+3+8=19。
问该机器人能够达到多少个格子?
要求:
1)先给出算法说明,关键处给出注释;
2)基于intmovingCount(intk,intm,intn);
函数声明实现,其中k,m,n的含义已在题目中给出。
5、输入两棵二叉树A,B,判断B是不是A的子结构。
(ps:
我们约定空树不是任意一个树的子结构)。
请先给出算法说明再实现算法,函数定义为:
boolisSubtree(TreeNode*A,TreeNode*B);
//返回true代表B树是A树的子结构,返回false代表B树不是A树的子结构。
二叉树采用二叉链表存储。
提示:
子结构如图所示,右树是左树的子结构。
贵州大学2021年硕士研究生入学考试模拟卷(A)-参考答案
题号
1
2
3
4
5
6
7
8
9
10
答案
D
C
B
A
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
详细解析:
1、D。
关于main函数相关的考点,注意有以下说法需要掌握:
C语言中main函数称之为主函数,一个C程序总是从main函数开始执行的,main函数是由操作系统调用的,操作系统总是将main函数作为应用程序的开始,操作系统将main函数的返回值作为程序的退出状态。
程序执行时操作系统也可以向main函数传递参数。
main函数可以放在其他函数之前,也可以放在其他函数之后。
构成C程序的基本单位是函数;
函数可以嵌套调用,但不可以嵌套定义。
被调用函数可以在调用之后定义,但需要在调用前声明。
2、C。
1/2得到是0,因为1和2都是整数,值为取整。
3、B。
考察数学表达式与C语言表达式的对应。
4、B。
A项不是语句,因为没有分号。
C项4*y不是变量。
D项错误的语法。
5、C。
这题考察运算符的优先级和短路原则,对于运算符优先级,记住最高级是()和[],最低的运算级是逗号,倒数第二低的是赋值和复合赋值。
在这个题目中c>
x先判断,值为0,因此a的值为0,整个赋值表达式的值也为0,则&
之后的表达式不再执行,故b的值还是6。
上述语句执行完之后,a、b、c的值分别为:
0,6,0.
6、D。
考察for循环,A项第二次循环会导致i为最小的负数,B项循环体不执行,C项当i=7时访问下标出错。
7、B。
2+3+4+...+100=100*(100+1)/2–1=5049
8、A。
注意第二维不能省略。
9、B。
宏定义只是替换,z=2*(N+Y(5))=2*(2+(N+1)*5)=2*(2+(N+1)*5)=2*(2+15)=34.
10、对于D项,第二维不能省略。
这样就对了。
11、C。
考察一级指针,q指向x,*q+=3等价于x+=3,表达式是一个逗号表达式,逗号表达式的值为最后一个表达式的值,因此最终的答案为10.
12、D。
p代表地址,p+=2代表地址单元加了2个,一个float占4位,因此p的值此时为65496+8=65504.
13、C。
考察二级指针与数组的对应关系。
14、D。
考察C语言中几个变量定义相关的关键字。
C语言中,动态存储区域中存放的变量在使用时才分配内存空间。
auto变量的存储单元是分配在内存的动态存储区中,每当进入函数体时自动分配存储单元。
register变量也是auto类变量。
static说明的变量为静态变量,静态变量在内存的静态存储中占据着永久的存储单元,直至程序运行结束。
extern说明的变量为外部变量,属于全局变量,全局变量在整个程序运行期间都占用内存空间。
对于register,register修饰符暗示编译程序相应的变量将被频繁地使用,如果可能的话,应将其保存在CPU的寄存器中,以加快其存储速度。
因为register变量可能不存放在内存中,所以不能用“&
”来获取register变量的地址。
只有局部自动变量和形式参数可以作为寄存器变量,其它(如全局变量)不行。
局部静态变量不能定义为寄存器变量。
不能写成:
registerstaticinta,b,c;
15、B。
结构体所占的内存空间,等于各单元占用内存空间的和。
此题已说明不采用字节对齐,如果在对齐的方式下将输出8。
16、C。
算法原地工作含义是需要O
(1)常量级的辅助空间。
算法执行效率的高低与语言实现没有绝对关系,一般来讲由于汇编语言更偏向于硬件,可以写出更佳高效的代码,但不代表低级语言写出的算法实现一定优于高级语言。
17、B。
按题意要求,将对称矩阵A的上三角部分按行优先进行存放数组了B中,那么B[k]与aij的对应关系为:
当i<
=j时,k=(i-1)/2*(2*n-i+2)+j-i+1
因此有:
k=(6-1)/2*(2*8-6+2)+7-6+1=32
18、B。
19、D
将顺序队列想象成一个环。
注意rear是指向的队尾,没有对应元素,入队即将存在这个地方。
初始时:
Q.front=Q.rear=0
队首指针进1,入队:
Q.front=(Q.front+1)%MaxSize
队尾指针进1,出队:
Q.rear=(Q.rear+1)%MaxSize
队列长度:
(Q.rear+MaxSize−Q.front)%MaxSize
循环队列判空的条件:
Q.front==Q.rear;
判断循环队列满的条件:
(Q.rear+1)%MaxSize==Q.front
20、C。
树中结点总数为:
n0+n1+n2+n3,树中所有边的数量为0*n0+1*n1+2*n2+3*n3,考察树的性质,结点数=边数+1。
将题目中的值代入,n0+n1+1+2=n1+2+6+1,解得:
n0=6.
21、A。
注意考察得是树,不是二叉树,高度至少为2,17个叶子结点。
22、D。
23、C。
24、D。
快速排序每趟已一个元素为基准将待排序列分成左右两部分,左边均小于基准,右边均大于基准,此题以第一个元素作为基准,第一趟下来,25左边:
20,15,21均小于25,右边:
47,27,68,35,84均大于25。
第二趟左右两遍同样执行相同的操作。
因此可以看出所采用的是快速排序。
25、B。
由下图可以看出,仅堆排序辅助空间为O
(1).
1、y=6.
2、b=1,a[0]=2
3、92
4、8,17
1、
前序-+a*b-cd/ef
中序a+b*c-d-e/f
后序abcd-*+ef/-
2、
(1)对应的图如下:
除了邻接矩阵存储无向图之外,还可以用邻接表、逆邻接表、十字链表、邻接多重表来存储,每种存储方式都有其适用的场景。
(2)深度优先遍历序列为:
abdce
广度优先遍历序列为:
abedc
3、
(1)对关键字35、20、33和48进行查找的比较次数为3、2、1、1。
解析:
35的分析过程,35首先进行一次hash得到的哈希码为:
9,9这个位置存了48不等于35,发生冲突,需要用双重散列解决,此时h(key)=9,m=13,hl(key)=3。
故h1=(9+1*3)%13=12。
12这个位置存了59,还是发生冲突,继续散列。
h2=(9+2*3)%13=2,2这个位置存了35,故查找35的比较次数为3次。
20,33,48一样的分析思路。
(2)59关键字的比较次数为2,基于第一问。
平均查找长度=(3+2+1+1+2)/5=1.8。
4、构造的哈夫曼树如下:
编码:
a:
0c:
100b:
1010f:
1011f:
110d:
111
5、
数据结构是带有结构特性的数据元素的集合,它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系,并对这种结构定义相适应的运算,设计出相应的算法,并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。
换句话说,数据结构是相互之间存在一种或多种特定关系的数据元素的集合,即带“结构”的数据元素的集合。
“结构”就是指数据元素之间存在的关系,分为逻辑结构和存储结构。
数据结构研究的内容:
就是如何按一定的逻辑结构,把数据组织起来,并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。
算法研究的目的是为了更有效的处理数据,提高数据运算效率。
数据的运算是定义在数据的逻辑结构上,但运算的具体实现要在存储结构上进行。
说明:
采用for循环的方式依次累加。
编程实现如下:
解法1-直接递推:
//定义变量及初始化
floatx=2.0,s=0.0;
//循环求和
for(inti=0;
i<
20;
i++){
x=1+1/x;
s+=x;
s=%f"
解法2-分子分母分别递推
floata=2.0,b=1.0,s=0.0;
for(inti=0;
20;
i++){
s+=a/b;
a=a+b;
b=a-b;
(1)结点个数为3时的结构图:
(2)说明:
先算前两个结点的的差值取到等差diff,再循环遍历各个结点计算相邻的差,如果差值不等于diff,则说明不满足等差关系。
程序实现如下:
intisRise(LINKL){
Node*t=L->
next;
if(t==NULL)return0;
Node*p=t->
next;
if(p==NULL)return0;
//以上,合法性校验
ElemTypediff=p->
data-t->
data;
//先计算差值
while(p->
next!
=NULL)
{
Node*q=p->
if(q->
data-p->
data!
=diff)
return0;
else
p=q;
return1;
3、请用两个栈实现队列操作,给出数据结构定义并描述算法思想,至少写出入队、出队的代码。
算法思想:
入队时只往栈1中入,出队时,判断栈2是否为空,如果为空则把栈1中的元素全部入栈到栈2,然后栈2的栈顶元素
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 贵州 大学计算机 840 考研 模拟 试题 A831 答案