贡献者： xzllxls
考生注意：所有答题务必书写在考场提供的答题纸上，写在本试题单上 的答题一律无效（本题单不参与阅卷）。
(本题共 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'\subseteq V$,$E'\subseteq E$,则称 $G'$ 是 $G$ 的（ ）.
8. 在顺序表（6,15,30,37,65,68,70,72,89,99）中采用折半查找法看找元素 37,与表中进行过比较的元素依次是（ ）.
9. 若已知 $n$ 个关键字值具有相同的散列函数值，并且采用线性探测再散列法处理冲突，那么，将这 $n$ 个关键字值全部散列到初始为空的地址空间中，发生散列冲突的次数是（ ）。
10. 若长度为 $n$ 的序列 $K=(k_1,k_2,...,k_n)$ 当且仅当满足 $k_i\leqslant k_{2i}$，并且 $k_i\leqslant k_{2i+1} (1\leqslant i\leqslant \lfloor n/2 \rfloor)$ 时，则称该序列为一个小顶堆积（Heap）。根据该定义，序列（26,5,77,1,61,11,59,48,15,19）对应的小顶堆积是（ ）。
(本题共 20 分，每小题各 5 分)
1. 如果一个具有 100 个顶点、200 条边的有向图采用邻接矩阵存储，该邻接矩阵是 否是稀疏矩阵？为什么？(这里我们假设：当矩阵中非零元索的数门小「整个知阵总元 素的数目的 5%时认为该如阵为稀疏矩阵)
2. 一般情况 F,建立散列表时难以避免出现散列冲突，常用处理散列冲突的方法之 是开放定址法，该方法的基木思想是什么？
3. 若对序列（2,12,列，88510）按值从小到大进行排序，前三趟排序的结果分别为：
第一趟排序的结果：(2J 2.16.5.10.88)
第二趟排序的结果：(2.12,5,10,16,88)
笫三趟排序的结果：(2,5,10」2,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\times(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;
(本题共 20 分，每小题各 2 分)
1.在 $C$ 语言中，标识符只能由字母、数字和卜划线三种字符组成，并且第一个字符（ ）。
A.必须是字母 $\qquad$ B.必须是下划线
C.必须是字母或者下划线 $\qquad$ D.可以是字母、数字和下划线之一
2.若整型变量 $x$ 的初值为 $6$,则计算表达式 $"x+=x-=x*x"$ 之后，$x$ 的值是。
A. 50 $\qquad$ B. 60 $\qquad$ C. -50 $\qquad$ 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[lO];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.对于下列程序，若从键盘上输入：abcdef<回车>，则输出结果是（ ）
#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);
}
8.当说明一个结构体变量时系统分配给它的内存是（ ）
A.结构中最后一个成员所需的内存量
B.结构中第一个成员所需的内存量
C.成员中占内存是最大者所需的容量
D.各成员所需内存量的总和
9.下列程序的输出结果为（ ）.
#define ABC(x) x*x
main( )
{
int a,k=3;
a=++ABC(k+1);
print("%d",a);
}
10.若要以 a+方式打开一个已经存在的文件，则下列叙述中，正确的是（ ）
A.文件被打开时，原有的文件内容不被删除，位置指针移动到文件的末尾，可进行添加和读操作
B.文件被打开时，原有的文件内容不被删除，位置指针移动到文件的开头，可进行重写和读操作
C.文件被打开时，原有的文件内容被删除，只能进行写操作
D.以上三种说法都不正确
(本题共 20 分，每小题各 5 分)
1.在 C 语言中，头文件的作用是什么？
2.在 C 语言中，#include "flename.h"和#include <filename.h> 的区别是什么？
3.在 C 语言中，全局变量和局部变量的主要区别是什么？
4.字符指针、浮点数指针、以及函数指针这三种类型的变量哪个占用的内存最大？为什么？
(本题共 20 分，每小题各 2 分)
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.下列函数的功能是根据公式
void fun(float *sn,int n)
{
float s=0,w,f=-l;
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 sstrmp(char *s,char *t)
{
while(*s&&*t&&*s=( (1) )){
s++;
t++;
}
return( (2) };
}
5.下列程序的功能是将已经按升序排好序的两个字符串 strl 和 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'&&st2[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;
print("%s\n",( (2) ));
--argc;
}
}
7.下列程序的功能是打开两个已存在的文件 filel 和 file2,并将 file2 拼接到 filel 的后面。
请在程序的空白处（方框内）填入合适的内容，使程序完整。
#include <stdio.h>
int main()
{
FILE *fp1,*fp2;
if(fp1=fopen("file1!"," (1) "])==NULL){
printf("Cannot open file!\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],*ptrl,*ptr2;
int n;
gets(str);
n=strlen(str);
ptr1=str;
ptr2=str+n-1;
while(ptr1<ptr2){
if(*ptr1!=* ptr2)
break;
else{
ptr1++;
ptr2--;
}
}
if(ptr1<ptr2)
printf("No!\!n");
else
printf("Yes!\n");
}
10.下列程序的功能是
(注：fill(*FlLE)返回 long 类型的文件指针位置)
#include <stdio.h>
void main()
{
FILE *fp;
long position;
fp=fopen("file.tex","a");
fprintf(fp,"data");
position=fell(fp);
print("position=%ld\n",position);
fclose(fp);
}