山西省2017年专升本选拔考试（C程序设计数据结构）历年真题详解
说明:本试题分C程序设计和数据结构(C语言版)两部分，各占100分，满分200分，考试时间150分钟。
第一部分C程序设计
一、单项选择题( 本大题共10小题，共小题3分，共计30分，在每小题的四个备选答案中，只有一个答案是正确的，请将代表正确答案的字母填入下列表格内)
1. C程序 (B)
A.可立即执行
B.是一种源程序
C.经过编译即可执行
D.是一种目标程序
2. C语言中用于结构化程序设计的三种基本结构是(A)
A.顺序结构、选择结构、循环结构
B.if、switch、break
C.for、while、do-while
D.if、for、continue
3.以下定义语句中正确的是(C)
A. char a='A' b='B';
B. float a=b=10.0;
C. int a=10,*b=&a;
D. float *a,b=&a;
4．下面不属于C语言的数据类型是(C)
A.整型
B.实型
C.逻辑型
D.双精度实型
5.变量的指针,其含义是指该变量的(B)
A.值
B.地址
C.名
D.一个标志
6. 以下叙述中，正确的是(C)
A. continue 和break语句只能用于循环体内
B. continue 和break语句只能用于分支语句中
C. continue 语句只能用于循环体内
D. continue 语句只能用于分支语句中
7. C语言规定，简单变量作为实参时它和对应形参之间的数据传递方式是( A )
A.单向值传递
B.地址传递
C.相互传递
D.由用户指定方式
8. 下列运算符中，要求运算对象必须是整数的是(C)
A. /
B.”
C. %
D.！
9.下面合法的赋值语句是(D)
A.x+y=2002;
B. ch= "green";
C.x=(a+b)++;
D. x=y=0316;
10.若有定义:int x;则语句x=(2 *3)+6%5;运行后，x的值是(B)
A.8
B.7
C.6
D.5
二、填空题(本大题共6小题，每空2分，共计12分)
1.函数是具有相对独立功能的（程序段）。
2.假设所有变量均为整型,则表达式(a=2,b=5,a++,b++,a+b)
的值为（9）。
3.若有说明:int a[ ][3]={1,2,3,4,5,6}，则数组a第一维
大小是（ 2）。
4. C语言可以定义结构体类型，其关键字为（struct）。
5.没有说明语句int k,i=5,j=10;则表达式k=( ++i)*(j--)
的值是（60）。
6.一个变量的地址称为该变量的（指针）。
三、改错题
(本大题共2小题，每小题12分，共计24分)
说明如下:参改程序。每题3个错误,找出每对"/* * *found* * /../* **found***/"之间存在的错误,并把正确答索填写在横线上。
1.程序功能是:程序实现从10个数中找出最大值和最小值。
# include
# include
int max,min;
void find_max_min(int *p,int n)
{int *q:
*******found********/
max=min=p;
/********found********/
for(*q=p;q
if(*q>max) max=*q;
/********found********/
else if(min
/********found********/
void main()
int i,num[10];
printf(“input 10 numbers;”);
for(i=0;j
/********found********/
scanf(“%d”,num [i]);
/********found********/
find_max_min(num,10);
print(“max=%d,min=%d\n”,max,min);
}
（1）、错误：max=min=p;
正确：max=min=*p;
（2）、错误：else if(min
正确：else if(min>*q)min=*q;
（3）、错误：scanf(“%d”,num [i]);
正确：scanf(“%d”,&num [i]);
2.程序功能是，从键盘上输入两个整数，及一个运算符（+、-、*、/），进行相应的运算后输出运算的结果。
如输入：1+2 将输出：1+2=3
#include
#include
void main()
int m，n，result,flag=0;
/********foiund********/
char ch，
/********found********/
clrscr();
printf(“input an expression:”);
scanf(“%d%c%d”,&m,&ch,&n);
/********found********/
switch ch
/********found********/
case’+’:result=m+n;break;
case’-’:result=m-n;birak;
case’*’;result=m*n;break;
case’/’:result= m/n;break;
default: {print(" Error! \n" ):flag=1;}
/********found********/
if( flag)
/********found********
print("%d%c%d= %d\n",m,ch,n,result);}
（1）、正确：char ch，
错误：char ch;
（2）、正确：switch ch
错误：switch (ch)
（3）、正确：if( flag)
错误：if( ！flag)或if( flag==0)
四、程序填空题(本大题共2小题，每空4分，共计20分。)
说明如下:在每对“/**/...../**/”之间填入程序内容，使之实现相应的功能。
1.程序功能是:便其实现输人若干整数，统计其中大于零和小于零的个数，输入零结束。
#include
void main()
{
int n,a,b;
/**/（a=b=0） /**/；
scanf("%d" ,&n);
while(/**/（n!=0） /**/)
{
if(n>0)a++;
else/* */(b++)/**/
scanf("%d"，&n);
}
2.程序功能是：输人一个大于3的整数n,判定它是否为素数(prime ,
又称质数)。
# include
void main()
{
int n,i;
printf(”please enter a integer number,n=?");
scanf("%d",&n);
for(i=2:i
if(/**/n%i==0/**/) break;
if(i
else pintf(/* */”%d is a prime number.\n”,n/**/;
return 0;
}
五、编程题(本大题共2小题，共计24分)
1.输入一个字符，判别它是否为小写字母，如果是，将它转换成大写字母，如果不是，不转换，然而输出最后得到的字母。（9分）
# include
int main
{
char ch;
scanf(" %c",&ch);
ch=(ch>= "a"&&ch
print("%c\n" ,ch);
return 0;
}
2.有一个3*4的矩阵a，求出其中值最小的那个元素的值，以及其所在的行号和列号。
1 2 3 4
a= 9 8 7 6
-10 10 -5 -2
#include
int main()
{
int i,j,row =0, colum=0 , min;
int a[3][4]={{1,2,3,4},1{9,8,7,6},{-10,10.-3,2}}
min=a[0][0];
for (i=0;i
for(j=0;j
if(a[i][j]
{min=a[i][j];
row=i;
colum=j;
}
printf(”min %d\nrow= %d\ ncolum = %d\n" ,min，row, colum) ;
return 0;
}
第二部分数据结构
六、单项选择题(本大题共10小题，每小题2分，共计20分)
1.线性表是（A）
A.一个有限序列，可以为空
B.一个有限序列，不可以为空
C.一个无限序列，可以为空
D.一个无限序列，不可以为空
2在一个长度为n的顺序表中删除第1个元索(0
A.n-i
B.n-i+1
C.n-i-1
D.i
3.从一个具有n个结点的单链表中查找其值等于X的结点时，在查找成功的情况下，需平均比较(C)个元素结点。
A.n/2
B.n
C. (n+1)/2
D. (n-1)/2
4.在等概率情况下，顺序表的插人操作要移动(B) 结点。
A.全部
B.一半
C.三分之一
D.四分之一
5.数据结构中，与所使用的计算机无关的是数据的(C)结构。
A.存储
B.物理
C.逻辑
D.物理和存储
6.算法分析的两个主要方面是(A)
A.空间复杂性和时间复杂性
B.正确性和简明性
C.可读性和文档性
D.数据复杂性和程序复杂性
7.计算机算法指的是(C)
A.计算方法
B.排序方法
C.解决问题的有限运算序列
D.调度方法
8.栈中元素的进出原则是(B)
A.先进先出
B.后进先出
C.栈空则进
D.栈满则出
9. 与单链表相比，双链表的优点之一是(D)
A.插入、删除操作更简单
B.可以进行随机访问
C.可以省略表头指针或表尾指针
D.顺序访问相邻结点更灵活
10. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着(B)
A.数据元素具有同一特点
B.不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要-致
C.每个数据元素都-样
D.数据元素所包含的数据项的个数要相等
七、填空题(本大题共7小题，每小空2分，共计20分)
1.根据数据元素之间关系的不同特性，通常有集合结构、（线性结构）、（树形结构）和图形结构四类基本结构。
2.算法的5个重要特性是有穷性、（确定性）、可行性、（输入）和输出。
3.在单链表上插入、删除一个节点，必须知道其（前驱）节点。
4.链式存储结构是通过（指针）表示元素之间的关系的。
5.深度为5的二叉树至多有（31）个节点
6.数据机构的形式定义为{D,R}，其中D是数据元素的有限集合，R 是D上的（关系）有限集合。
7.常见的图的存储结构有邻接矩阵、（邻接表）和（边集数组）这三
种方法。
八、名词解释(本大题共4小题，每小题6分，共计24分)
1.队列：是一种先进先出的线性表，它只允许在表的一端进行插入，而另一端删除元素。
2.数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
3.排序：是计算机程序设计中的一种重要操作，它的功能是将一个数据元素的任意序列，重新排列成一个关键字的有序序列。
4.关键字：是数据元素中某个数据项的值，用它可以识别一个数据元素。
九、解答题(本大题共4小题，共计21分)
1.写出图1中二叉树的先序、中序、后序遍历的结点序列。
先序: -+a*b-cd/ef （2分）
中序: a+b*c-d-e/f（2分）
后序: abcd-*+ef/-（2分）
2.简述深度优先搜索的遍历方法。
假设初始状态是些中所有顶点均未被访问过，（1分）则深度优先搜索可从某个顶点V出发，首先访问此顶点(称此顶点为初始点)，（1分）然后依次从V的任意一个未被访问的邻接点出发进行深度优先控索遍历，（1分）直到图中所有与V有路径相通的顶点都被访问到，（1分）若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作为初始点，重复上述过程，直到图中所有顶点都被访问到为止。（1分）
3.简述邻接矩阵表示法的特点。
(1) 无向图的邻接矩阵是对称的，而有向图的邻接矩阵不一定对
称。（1分）
(2)对于无向图，顶点V1的度是邻接矩阵中第i行(或第i列)的非零元素的个数。（1分）
(3)对于有向图，顶点V1的度是邻接矩阵中第i行和第i列的非零元素的个数之和。（1分）
(4)用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连，但要确定图中的边数，则必须按行、按列对每个元素进行检查，所花费的时间代价很大。（1分）
4.某二叉树的中序序列为DBFEGAC，后序序列为DFGEBCA.。画出该二叉树；并写出先序序列。
如图所示，先序序列为ABDEFGC
十、论述题
试述顺序查找法、折半查找法和分块查找法的基本思路，并比较他们的平均查找长度和优缺点。
基本思路:
颠序查找法:从表的一端开始，用所给定的关键字依次与顺序表中各记录的关键字逐个比较，若找到相同的，查找成功否则查找失败。（3分）
折半查找法:将给定值与有序表中间位置的记录的关键字进行比较，有三种情况:
(1)两者相等，说明查找成功，返回该记录的位；否则，从该中间位置将有序表分为前后两个子表。(2) 若给定值小于该记录的关键字，则说明待查找记录若在表中，定排在该记录之前，继续在前一子表中查找记录。(3)若给定值大于该记录的关键字，是说明待查找记录若在表中，一定排在该记录之后，继续在后一子表中查找记录。（3分）
分块查找法:它是顺序查找和折半查找相结合的一种查找方法。
在这种在查找方法中，存储结构采用按索引存储方式构造的索引顺序表。（3分）
平均查找长度:
顺序查找法：ASL=3(n+1)4（1分）
折半查找法：ASL=log2(n+1)-1（1分） 分块查找法：ASL=12(n s +1)+s 2（1分）
优缺点:
三种查找方法各有优缺点。顺序查找法效率最低，但限制最少，对查找表中的数据元素没有要求。折半查找法效率最高，但限制也最强，要求查找表中的数据元素必须是按关键字有序。分块查找则介于二者之间。在实际应用中应根据具体情况进行选择。（3分）