北京航空航天大学 2012 年数据结构与 C 语言程序设计

贡献者： xzllxls

　　 考生注意：所有答题务必书写在考场提供的答题纸上，写在本试题单上 的答题一律无效（本题单不参与阅卷）。

1. 一、填空题

　　 (本题共 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^{\prime }=(V^{\prime }E)$，若有 $V^{\prime }\subseteq V$,$E^{\prime }\subseteq E$,则称 $G^{\prime }$ 是 $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⩽k_{2i}$，并且 $k_i⩽k_{2i+1}(1⩽i⩽\lfloor n/2\rfloor )$ 时，则称该序列为一个小顶堆积（Heap）。根据该定义，序列（26,5,77,1,61,11,59,48,15,19）对应的小顶堆积是（ ）。

2. 二、简答题

　　 (本题共 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,则快速排序的最小 递归深度与最大递归深度分别是多少？

3. 三、综合题

　　 (本题共 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$）按值从大到小进行选择排序时每一趟的排序结果。

4. 四、算法设计题

　　 （本题 15 分）

　　 已知某具有 $n$ 个顶点的有向图采用邻接表方法存储，其中，用以存储有向边信息的边结点类型为

typedef struct edge{
    int adjvex;           /*某有向边的终止顶点在顶点结点中的位置*/
    struct edge *next;    /*指向下，个边结点*/
} ELink;

typedef struct ver{
    int indegree;    /*某顶点的入度*/
    vertype vertex;  /*某顶点的数据信息*/
    ELink *link;     /*指向以该顶点为出发点的第一个边结点*/
}VLink;

5. 五、单项选择题

　　 (本题共 20 分，每小题各 2 分)

　　 1.在 $C$ 语言中，标识符只能由字母、数字和卜划线三种字符组成，并且第一个字符（ ）。
A.必须是字母 $$ B.必须是下划线
C.必须是字母或者下划线 $$ D.可以是字母、数字和下划线之一

　　 2.若整型变量 $x$ 的初值为 $6$,则计算表达式 $"x+=x-=x\ast 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[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.以上三种说法都不正确

6. 六、简答题

　　 (本题共 20 分，每小题各 5 分)

　　 1.在 C 语言中，头文件的作用是什么？
2.在 C 语言中，#include "flename.h"和#include <filename.h> 的区别是什么？

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

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

7. 七、填空题

　　 (本题共 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);
}