北京航空航天大学2012年硕士研究生入学考试试题
“数据结构与C语言程序设计”（科目代码：991）
一、填空题(本题共20分，每小题各2分)
1．从总体上说，“数据结构”课程主要研究三个方面的内容。
2．若对某线性表最常用的操作是在表中插入元素或者删除表中元素，则对于顺序存储结
构 和链式存储结构这两种存储结构而言，线性表应该采用 。
3．在长度为n的非空队列中进行插入或者删除操作的时间复杂度用大O符号表示
为 。
4．若一棵度为4的树中度为1、2、3和4的结点个数分别为4、2、1和1，则该树中叶
结点的个数为 。
5．若某二叉树的中序遍历序列为B,A,F,D,G,C,E，按层次遍历序列为A,B,C,D,E,F,G，则
该二叉树的后序遍历序列为 。
6．将一棵结点总数为n、且具有m个叶结点的树转换为一棵二叉树以后，该二叉树中右
子树为空的结点有 个。
7．对于图G=(V,E) 与 G´=(V´,E´)，若有V´ÍV，
E´ÍE，则称G´是G的
8．在顺序表(6,15,30,37,65,68,70,72,89,99)中采用折半查找法查找元素37，与表中进行过
比较的元素依次是 。
9．若已知n个关键字值具有相同的散列函数值，并且采用线性探测再散列法处理冲突，
那 么，将这n个关键字值全部散列到初始为空的地址空间中，发生散列冲突的次数
是 。
10．若长度为n的序列K=(k1,k2,…,kn)当且仅当满足ki≤k2i并且ki≤k2i+1(1≤i≤n/2)时，则
称该序列为一个小顶堆积(Heap)。根据该定义，序列(26,5,77,1,61,11,59,48,15,19)对应的小
顶堆积是 。
二、简答题(本题共20分，每小题各5分)
1．如果一个具有100个顶点、200条边的有向图采用邻接矩阵存储，该邻接矩阵是否是
稀疏矩阵？为什么？（这里我们假设：当矩阵中非零元素的数目小于整个矩阵总元素的数
目的5%时认为该矩阵为稀疏矩阵）
2．一般情况下，建立散列表时难以避免出现散列冲突，常用处理散列冲突的方法之一是
开放定址法，该方法的基本思想是什么？
3．若对序列(2,12,16,88,5,10)按值从小到大进行排序，前三趟排序的结果分别为：
第1趟排序的结果：(2,12,16,5,10,88)
第2趟排序的结果：(2,12,5,10,16,88)
第3趟排序的结果：(2,5,10,12,16,88)
请问：该结果是采用了选择排序法还是采用了(起)泡排序法得到的？为什么？
4．快速排序法的排序过程是递归的。若待排序序列的长度为n，则快速排序的最小递归
深度与最大递归深度分别是多少？
三、综合题(本题共20分，每小题各5分)
1．若非空双向循环链表中链结点结构为 blink data rink，则依次执行下列4条语句的目 的是在该链表中由q指的结点后面插入一个由p指的结点，其中1条语句有错误，请找出
该语句，并写出正确的语句。
p->llink=q; /* 第1条语句 */ p->rlink=q>rlink; /* 第2条语句 */
q->rlink=p; /* 第3条语句 */ q->rlink->llink=p; /* 第4条语句 */
2．已知某完全二叉树的第7层有10个叶结点，请求出该完全二叉树的结点总数的最大值。（要求写出结论的求解过程）
3．证明：具有n个顶点的无向图最多有n(n-1)/2条边。
4．请分别写出对数据元素序列(80,30,50,10,90,20) 按值从大到小进行选择排序时每一趟的 排序结果。
四、算法设计题（本题15分）
已知某具有n个顶点的有向图采用邻接表方法存储，其中，用以存储有向边信息的边结点类型为
typedef struct edge{
int adjvex; /* 某有向边的终止顶点在顶点结点中的位置 */
struct edge *next; /* 指向下一个边结点 */
}ELink;
用以存储顶点信息的顶点结点类型为
typedef struct ver{
int indegree; /* 某顶点的入度 */
vertype vertex; /* 某顶点的数据信息 */
ELink *link; / * 指向以该顶点为出发点的第一个边结点 */
}VLink;
并且n个顶点结点构成一个数组结构G[0..n-1]。请写一个算法，该算法判断给定的顶点序列V[0..n-1]={v1,v2,v3,…,vn}是否是该有向图的一个拓扑序列，若是该有向图的一个拓扑序列，算法返回1，否则，算法返回0。
五、单项选择题（本题共20分，每小题各2分）
1．在C语言中，标识符只能由字母、数字和下划线三种字符组成，并且第一个字符 。
A．必须是字母 B．必须是下划线
C．必须是字母或者下划线 D．可以是字母、数字和下划线之一
2．若整型变量x的初值为6，则计算表达式“x+=x-=x*x”之后，x的值是 。
A．50 B．60 C．-50 D．-60
3．下列4个程序段中，不是无限循环的是 。
A．for(b=0,a=1; a>++b; a=k++) k=a; B．for( ; ; a++=k) ;
C．while(1) { a++; } D．for(k=10; ; k--) total+=k;
4．说明“double (*ptr)[N];”中的标识符ptr是 。
A．N个指向double类型变量的指针
B．指向N个double类型变量的函数指针
C．一个指向由N个double类型元素组成的一维数组的指针
D．具有N个指针元素的一维指针数组，其每一个元素都只能指向double类型变量
5．下列4个叙述中，正确的是 。
A．char *r=“china”;等价于char *r; *r=“china”;
B．char *ptr=“china”;等价于char *ptr; ptr=“china”;
C．char string[10]={“china”};等价于char string[10]; string[ ]={“china”};
D．char str[4]=“abc”,temp[4]=“abc”;等价于char str[4]=temp[4]=“abc”;
6．在C程序中，语句“char *func(int x,int y);”表示 。
A．对函数func的定义 B．对函数func的调用
C．对函数func返回值类型的说明 D．对函数func的原型说明
7．对于下列程序，若从键盘上输入：abc def<回车>，则输出结果是 。
#include <stdio.h>
#include <malloc.h>
main( )
{ char *p,*q;
p=(char *)malloc(sizeof(char)*20);
q=p;
scanf(“%s%s”,p,q);
printf(“%s%s\n”,p,q);
}
A．defdef B．abcdef C．abc d D．d d
8．当说明一个结构体变量时系统分配给它的内存是 。
A．结构中最后一个成员所需的内存量
B．结构中第一个成员所需的内存量
C．成员中占内存量最大者所需的容量
D．各成员所需内存量的总和
9．下列程序的输出结果为 。
#define ABC(x) x*x
main( )
{ int a, k=3;
a=++ABC(k+1);
printf(“%d”,a);
}
A．8 B．9 C．14 D．17
10．若要以a+方式打开一个已经存在的文件，则下列叙述中，正确的是 。
A．文件被打开时，原有的文件内容不被删除，位置指针移动到文件的末尾，可进 行添加和读操作
B．文件被打开时，原有的文件内容不被删除，位置指针移动到文件的开头，可进 行重写和读操作
C．文件被打开时，原有的文件内容被删除，只能进行写操作
D．以上三种说法都不正确
六、简答题（本题共20分，每小题各5分）
1．在C语言中，头文件的作用是什么?
2．在C语言中，#include “filename.h”和#include <filename.h>的区别是什么?
3．在C语言中，全局变量和局部变量的主要区别是什么？
4．字符指针、浮点数指针、以及函数指针这三种类型的变量哪个占用的内存最大？为什么？
七、填空题（本题共20分，每小题各2分）
(说明：由于一些符号无法在本网站显示，本大题中的填空处用(i)表示第i个空 ----- “答疑”)
1．下列代码的功能包括：定义一个x数组，说明一个结构体，同时对变量t进行初始化，使得t的a成员的值为50，b成员的值为x数组的首地址。
请在空白处(方框内)填入合适的内容，以完成上述功能。
int x[5]={1,2,3,4,5};
struct{ int a,
int *b‟
}t{ (1), (2) };
2．下列函数的功能是根据公式s=1-1/3+1/5-1/7+ … + 1/(2n+1)计算s的值，其中，n通过形参传入(n≥0)，计算结果通过形参指针传回。请在函数的空白处填入合适的内容，使函数完整。
void fun(float *sn,int n)
{ float s=0,w,f=-1;
int i;
for(i=0;i<=n;i++){
f= (1);
w=f/(2);
s+=w;
}
*sn=s;
}
3．下列程序实现将输入的一个小写字母循环后移5个位置后输出。例如，若输入字母„a‟，则输出字母„f‟，若输入字母„w‟，则输出字母„b‟。请在程序的空白处填入合适的内容，使程序完整。
#include <stdio.h>
main( )
{ char c;
c=getchar( );
if(c>=„a‟&& c<=„u‟)
(1);
else if(c>=„v‟&& c<=„z‟)
(2);
putchar(c);
}
4．下列自定义函数的功能是实现两个字符串的比较。请在函数的空白处填入合适的内容，使函数完整。
int sstrcmp(char *s,char *t)
{
while(*s && *t && *s== (1) ){
s++; t++; }
return ( (2) );
}
5．下列程序的功能是将已经按升序排好序的两个字符串str1和str2中的字符再按升序归并到字符串str3中。请在程序的空白处填入合适的内容，使程序完整。
#include <stdio.h>
main( )
{ char str1[ ]=“acegikm”;
char str2[ ]=“bdfhjlnpq”;
char str3[ ],*p;
int i=0,j=0,k=0;
while(str1[i]!=„\0‟&& str2[j]!=„\0‟){
if(str1[i]<str2[j]) str3[k]=str1[i++];
else (1) ;
k++; }
str3[k]=„\0‟;
if( (2) ) p=str2+j;
else p=str1+i;
strcat(str3,p);
puts(str3);
}
6．对于下列main函数，经过编译、连接后得到的可执行文件名为file.exe，并且已知在系统的命令状态下输入命令行“file Beijing Shanghai<回车>”后得到的输出结果是 Beijing
Shanghai
请在函数的空白处填入合适的内容，使函数完整。
main(int argc,char *argv[ ])
{ while( (1) ){
++argv;
printf(“%s\n”, (2) );
--argc; }
}
7．下列程序的功能是打开两个已存在的文件file1和file2，并将file2拼接到file1的后面。请在程序的空白处填入合适的内容，使程序完整。
#include <stdio.h>
int main( )
{ FILE *fp1,*fp2;
if((fp1=fopen(“file1”,“ (1) ”))==NULL){
printf(“Cannot open file1!\n”);
return 0; }
if((fp2=fopen(“file2”,“ (2) ”))==NULL){
printf(“Cannot open file2!\n”);
return 0; }
while(!feof( (3) ))
fputc( (4) ,fp1);
fclose(fp1);
fclose(fp2);
}
8．设n>0。下列函数的功能是 。
int fun(int n)
{ int count=0;
while(n){ count++; n=n/10; }
return count;
}
9．下列程序的功能是 。
#include <stdio.h>
#include <string.h>
main( )
{ char str[81],*ptr1,*ptr2;
int n;
gets(str);
n=strlen(str);
ptr1=str;
ptr2=str+n-1;