北航软院数据结构与C语言程序设计试题原版.doc

北航软院数据结构与C语言程序设计试题原版.doc

《北航软院数据结构与C语言程序设计试题原版.doc》由会员分享，可在线阅读，更多相关《北航软院数据结构与C语言程序设计试题原版.doc（6页珍藏版）》请在冰点文库上搜索。

北京航空航天大学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．若非空双向循环链表中链结点结构为llinkdatarlink，则依次执行下列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个顶点的有向图采用邻接表方法存储，其中，用以存储有向边信息的边结点类型为

typedefstructedge{

intadjvex;/*某有向边的终止顶点在顶点结点中的位置*/

structedge*next;/*指向下一个边结点*/

}ELink;

用以存储顶点信息的顶点结点类型为

typedefstructver{

intindegree;/*某顶点的入度*/

vertypevertex;/*某顶点的数据信息*/

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．60C．-50D．-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．charstring[10]={“china”};等价于charstring[10];string[]={“china”};

D．charstr[4]=“abc”,temp[4]=“abc”;等价于charstr[4]=temp[4]=“abc”;

6．在C程序中，语句“char*func（intx,inty）;”表示。

A．对函数func的定义B．对函数func的调用

C．对函数func返回值类型的说明D．对函数func的原型说明

7．对于下列程序，若从键盘上输入：

abcdef<回车>，则输出结果是。

#include

#include

main（）

{char*p,*q;

p=（char*）malloc（sizeof（char）*20）;

q=p;

scanf（“%s%s”,p,q）;

printf（“%s%s\n”,p,q）;

}

A．defdefB．abcdefC．abcdD．dd

8．当说明一个结构体变量时系统分配给它的内存是。

A．结构中最后一个成员所需的内存量

B．结构中第一个成员所需的内存量

C．成员中占内存量最大者所需的容量

D．各成员所需内存量的总和

9．下列程序的输出结果为。

#defineABC（x）x*x

main（）

{inta,k=3;

a=++ABC（k+1）;

printf（“%d”,a）;

}

A．8B．9C．14D．17

10．若要以a+方式打开一个已经存在的文件，则下列叙述中，正确的是。

A．文件被打开时，原有的文件内容不被删除，位置指针移动到文件的末尾，可进

行添加和读操作

B．文件被打开时，原有的文件内容不被删除，位置指针移动到文件的开头，可进

行重写和读操作

C．文件被打开时，原有的文件内容被删除，只能进行写操作

D．以上三种说法都不正确

六、简答题（本题共20分，每小题各5分）

1．在C语言中，头文件的作用是什么?

2．在C语言中，#include“filename.h”和#include的区别是什么?

3．在C语言中，全局变量和局部变量的主要区别是什么？

4．字符指针、浮点数指针、以及函数指针这三种类型的变量哪个占用的内存最大？

为什么？

七、填空题（本题共20分，每小题各2分）

（说明：

由于一些符号无法在本网站显示，本大题中的填空处用（i）表示第i个空-----“答疑”）

1．下列代码的功能包括：

定义一个x数组，说明一个结构体，同时对变量t进行初始化，使得t的a成员的值为50，b成员的值为x数组的首地址。

请在空白处（方框内）填入合适的内容，以完成上述功能。

intx[5]={1,2,3,4,5};

struct{inta,

int*b’

}t{

（1）,

（2）};

2．下列函数的功能是根据公式s=1-1/3+1/5-1/7+…+1/（2n+1）计算s的值，其中，n通过形参传入（n≥0），计算结果通过形参指针传回。

请在函数的空白处填入合适的内容，使函数完整。

voidfun（float*sn,intn）

{floats=0,w,f=-1;

inti;

for（i=0;i<=n;i++）{

f=

（1）;

w=f/

（2）;

s+=w;

}

*sn=s;

}

3．下列程序实现将输入的一个小写字母循环后移5个位置后输出。

例如，若输入字母‘a’，则输出字母‘f’，若输入字母‘w’，则输出字母‘b’。

请在程序的空白处填入合适的内容，使程序完整。

#include

main（）

{charc;

c=getchar（）;

if（c>=‘a’&&c<=‘u’）

（1）;

elseif（c>=‘v’&&c<=‘z’）

（2）;

putchar（c）;

}

4．下列自定义函数的功能是实现两个字符串的比较。

请在函数的空白处填入合适的内容，使函数完整。

intsstrcmp（char*s,char*t）

{

while（*s&&*t&&*s==

（1））{

s++;t++;}

return（

（2））;

}

5．下列程序的功能是将已经按升序排好序的两个字符串str1和str2中的字符再按升序归并到字符串str3中。

请在程序的空白处填入合适的内容，使程序完整。

#include

main（）

{charstr1[]=“acegikm”;

charstr2[]=“bdfhjlnpq”;

charstr3[],*p;

inti=0,j=0,k=0;

while（str1[i]!

=‘\0’&&str2[j]!

=‘\0’）{

if（str1[i]

else

（1）;

k++;}

str3[k]=‘\0’;

if（

（2））p=str2+j;

elsep=str1+i;

strcat（str3,p）;

puts（str3）;

}

6．对于下列main函数，经过编译、连接后得到的可执行文件名为file.exe，并且已知在系统的命令状态下输入命令行“fileBeijingShanghai<回车>”后得到的输出结果是

Beijing

Shanghai

请在函数的空白处填入合适的内容，使函数完整。

main（intargc,char*argv[]）

{while（

（1））{

++argv;

printf（“%s\n”,

（2））;

--argc;}

}

7．下列程序的功能是打开两个已存在的文件file1和file2，并将file2拼接到file1的后面。

请在程序的空白处填入合适的内容，使程序完整。

#include

intmain（）

{FILE*fp1,*fp2;

if（（fp1=fopen（“file1”,“

（1）”））==NULL）{

printf（“Cannotopenfile1!

\n”）;

return0;}

if（（fp2=fopen（“file2”,“

（2）”））==NULL）{

printf（“Cannotopenfile2!

\n”）;

return0;}

while（!

feof（（3）））

fputc（（4）,fp1）;

fclose（fp1）;

fclose（fp2）;

}

8．设n>0。

下列函数的功能是。

intfun（intn）

{intcount=0;

while（n）{count++;n=n/10;}

returncount;

}

9．下列程序的功能是。

#include

#include

main（）

{charstr[81],*ptr1,*ptr2;

intn;

gets（str）;

n=strlen（str）;

ptr1=str;

ptr2=str+n-1;

while（ptr1

if（*ptr1!

=*ptr2）

break;

else{ptr1++;

ptr2--;}

}

if（ptr1

\n”）;

elseprintf（“Yes!

\n”）;

}

10．下列程序的功能是。

（提示：

ftell（*FILE）返回long类型的文件指针位置）

#include

voidmain（）

{FILE*fp;

longposition;

fp=fopen（“file.tex”,“a”）;

fprintf（fp,“data”）;

position=ftell（fp）;

printf（“position=%ld\n”,position）;

fclose（fp）;

}

八、程序设计题（本题15分）

请编写一C语言程序，该程序的功能是确定字符串中首次出现的某字符在串中的位置（即该字符是字符串中的第几个字符），然后从字符串中删除该字符。

要求：

（1）如果未找到该字符，程序给出相应信息，否则，输出该字符在字符串中首次出现的位置，删除该字符（注：

不考虑非首次出现的该字符的删除），并且显示删除前后的字符串。

（2）通过键盘输入字符串以及被确定的字符。