内容发布更新时间 : 2024/11/15 23:05:32星期一 下面是文章的全部内容请认真阅读。
北京航空航天大学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．若非空双向循环链表中链结点结构为 llink data rlink，则依次执行下列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
{ 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
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
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
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] } 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 { 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)