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

贡献者： xzllxls

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

1. 一、单项选择题

　　 （本题 20 分，每小题各 2 分）

　　 1. 对于 K 度为 n 的线性表，建立其对应的单链表的时问复杂度为（）。
A. $O(1)$ $\quad$ B $O(log_2n)$ $\quad$ C. $O(n)$ $\quad$ D. $O(n^2)$

　　 2. 一般情况下。在一个双向链表中插一个新的链结点，（）。
A.需要器改 4 个指针域内的指针 $\quad$ B.需要修改 3 个指针域内的指针
C.需要修改 2 个指针域内的指针 $\quad$ D.只需要修改 1 个指针域内的指针

　　 3. 假设用单个字母表示中缀表达式中的一个运算数（或称运算对象）。井利用堆栈产生中缀表达式对应的后辍表达式。对于中辍表达式 $A+B*(C/D-E)$，当从左至右扫描到运算数 $E$ 时，堆栈中的运算符依次是（）。（注：不包含表达式的分界符）
A. $+*/-$ $\quad$ B. $+*(/-$ $\quad$ C. $+*-$ $\quad$ D. $+*(-$

　　 4. 若某二叉排序树的前序遍历序列为 50，20，40，30，80，60，70。则后序遍历序列（）。
A.30.40 20.50.70.60.80 $\quad$ B.30.40.20.W.60.80.50.
C.70.60.80.50.30.40.20 $\quad$ D.70.60.90.30.40.20.50.

　　 5. 分别以 6、3、8、12、5、7 对应叶结点的权值构造的哈夫曼（Huffman）树的深度（）。
A.6 $\quad$ B.5 $\quad$ C.4 $\quad$ D.3

　　 6. 下列关于图的叙述中，错误的是
A. 根据图的定义，图中至少有一个顶点
B. 根据图的定义，图中至少有一个个顶点和一条边（弧）
c. 具有 $n$ 个顶点的无向图最多有 $n\times(n-1)/2$ 条边
D. 具有 $n$ 个顶点的有向图最多有 $n\times(n-1)$ 条边（弧）

　　 7. 若在有向图 $O$ 的拓扑序列中，顶点 $v_i$，在顶点 $v_j$ 之前，则下列 $4$ 种情形中不可出现的是（）。
A. $G$ 中有弧 $< v_i,v_j>$
B. $G$ 中没有弧 $< v_i,v_j>$
C. $G$ 中有一条从顶点 $v_i$ 到顶点 $v_j$ 的路径
D. $G$ 中有一条从顶点 $v_j$ 到顶点 $v_i$ 的路径。

　　 8. 下列关于查找操作的叙述中，错误的是（）
A. 在顺序表中查找元素可以采用顺序查找法，也可以采用折半查找法
B. 在链表中查找结点只能采用顺序查找法，不能采用折半查找法
C. 一般情况下，顺序查找法不如折半查找法的时间效率高
D. 折半查找的过程可以用一棵称之为 “判定树” 的二叉树来描述

　　 9. 在一棵 $m$ 阶 $B$-树中。除根结点之外的任何分支结点包含关键字的个数至少是（）。
A. $m/2-1$ $\quad$ B. $m/2$ $\quad$ C. $\lceil m/2-1 \rceil $ $\quad$ D. $\lceil m/2 \rceil $

　　 9. 在一棵 $m$ 阶 $B$-树中，除根结点之外的任何分支结点包含关键字的个数至少是（）。
A. $m/2-1$ $\quad$ B. $m/2$ $\quad$ C. $\lceil m/2 \rceil-1$ $\quad$ D. $\lceil m/2 \rceil$.

　　 10. 若对序列（49. 38，65，97，76，13. 27，49'）进行快速捧序，则第一趟排序结束（即确定了第 1 个分界元素的最终位置)时，序列的状态是（）。
A. (13. 27, 49', 38, 49, 76, 97, 65) $\quad$ B.(13. 38. 27. 49'. 49. 76. 97. 65).
C. (13. 38. 49'. 27. 49. 97. 76. 65) $\quad$ D.(13. 38. 49'. 27. 49. 76. 97. 65)

2. 二、填空题

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

　　 1.非空线性表在采用（ ）存储结构的情况下，删除表的一个数据元素平均需要移动表中近一半元素的位置。

　　 2.将个长度为 $n$ 的单链表链接到一个长度为 $m$ 的单链表后面，该算法的时间复杂度用大 $O$ 符号表示为（ ）.

　　 3.若完全二叉树的叶结点的数目为 $k$，且最下面一层的结点数大干 $1$，则该完全二叉树的深度为（ ）。

　　 4.若深度为 8 的完全二叉树的第 7 层有 10 个叶结点，则该二叉树的结点总数为（ ）。

　　 5.在具有 n 个顶点的有向图中，每个顶点的度最大可以达到（ ）。

　　 6.若对有向图进行拓扑排序，则能够得到拓扑序列的条件是（ ）。

　　 7.已知长度为 10 的顺序表中数据元素接值从小到大排列。若在该表中进行折半查找，则平均查找长度（ASL）是（ ）。

　　 8.若在棵 m 阶 B-树的某十结点中插一个新的关键宇值而引起结点产生分裂， 则该结点中原有的关键字值的数目是（ ）。

　　 9.有一种排序方法可能台出现这种情况：最后一趟排序开始之前，序列中所有的元素都不在其最终应该在的位置上，这种排序方法是（ ）。

　　 10.若按照冒泡排序法的思想将序列（2，12，16，5 10)中元襄按值从小到大进行排序，整个排序过程所进行的元素之间的比较次数为（ ）。

3. 三、综合题

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

　　 1.一般情况下，当一个计算法中需要建立多个堆栈时可以选用下列三种处理方案之一。
问：这三种方案之间相比较晷有什么优点和缺点？
(l)多十堆栈麸享-个连续的存储空间
(2)井别建立多个采用顺序存储结构的堆栈
(3)分别建立多个采用硅式存储结构的堆栈

　　 2.已知二叉树采用二叉链表存储结构，根结点指针 T，链结点类型定义为：

typedef strucr node {
    char data;                      /* 数据域 */
    struct node *lchild, *rchild;   /* 指向左、右子树的指针域 */
} *BTREE;

void FUNC(BTREE T)
{
    if(T!=NULL) {
       printf("%c", T->data);
    FUNC(_____);
    FUNC(_____);
    }
}

　　 3.对给定 AOE 网（如题三 3 图所示），请完成
(1)分别求出各活动 $a_i$($i$=1，2, ...，14)的最早开始时间与最晚开始时间；（请以表格形式给出结果）
(2)求出所有关键路径。（请以图形方式画出各关键路径）

　　 4.已知要将给定的关键字值序列（42，51，16，26，50，25 37，68,64，33，18）进行散列存储-并且要求装填因子（也称负载因子）$\alpha\approx061$,
(1)请利用除留余数法构造出合适的教列函数;
(2)请画出利用该散列函数依次将序列中各关键字值插入到散列表以后表的状态。设散列表初始为空，并且采用线性探测再散列法处理散列冲突。

4. 四、算法设计题

　　 本题 15 分

　　 假设长度为 $n$ 的顺序表 $A[1..n]$ 中每个数据元素为一整数，请写出按照下列思想将表中数据元素按值从小到大进行排序的算法：第 l 趟排序将最小值元素放在 $A[1]$ 中，最大值元素放在 $A[n]$ 中；第 $2$ 趟排序将次小元素放在 $A[2]$ 中，次大值元素放在 $A[n-1]$ 中；……，依此下去，直至排序结束。

5. 五、填空题

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

　　 1.已知某等比数列的第一项 $a_i$ 为 $1$，公比为 $3$。下列程序的功能是输出该数列中小于 1000 的最大项 $a_n$ 及其对应的 $n$.
请在程序的空白处（下划线上）填入合适内容，使程序完整。

mam()
{
    int n=1,a=1,q=3;
    while(1){
        a=a*q;
        n++;
        if(a>=l000)
            ______;
    }
    printf("n=%d,a=%d\n",n-1,______);
}

　　 2.下列递归函数 FUNC2 的功能是判断整型数组 $a[n]$ 是否为递增数组，即判断数组的元素是否按值从小到大排列。若是一个递增数组，则函数返回 true，否则，函数返回 false.
请在函数的空白处（下划线上）填写合适内容，使函数完整。

bool FUNC2(int a[], int n)
{
    if(n==1)
        return true;
    if(n==2)
        return ______;
    return _____&&(a[n-1]>=a[n-2]);
}

　　 3. 下列程序的功能是主函数调用 FUNC3 函数求方阵 $a$ 中两条对角线上元紊之和。
请在程序的空白处（下划线上）填入合适内容，使程序完整。

#define N 10
void FUNC3(int a[N[N], int *p, int *q)
{
    int i;
    *p=0;
    *q=0;
    for(i=0; i<N; i++) {
        *p=*p+(*______);
        *q=*q+(*______);
    }
}

main()
{
    int a[N][N],i,j,x,y;
    for(i=0; i<N; i++)
        for(j=0，j<N; j++)
            scanf("%d", *(a+i)+j);
    FUNC3(a,&x,&y);  /* x,y中分别存放主对角线与副对角线上的元素之和 */
    printf("%d,%d\n",x,y);
}

　　 4.下列程序的功能是先通过键盘输入一正整数，然后调用一递归函数 FUNC4.该函数将正整数转换为对应的数字字符组成的字符串显示在屏幕上。例如：若输入的正整数为 583，则屏幕上显示的是字符串 583。
请在程序的空白处（下划线上）填入合适内容，使程序完整。

#include <stdio.h>
void FUNC4(int n)
{
    int i;
    i=n/10;
    if(____)
        FUNC4(i);
    putchar(_____);
}

mam()
{
    int n;
    printf("请输入一正整数n:");
    scanf("%d",&n);
    printf("转换后的字符串是：");
    FUNC4(n);
}

　　 5.下列程序的功能是将小写字母转换成对应的大写字母后的第 2 个字母，例如：将 a 转换成 C，将 b 转换成 D.其中，y 转换成 A，z 转换成 B。
请在程序的空白处（下划线上）填入合适内容，使程序完整。

#include <stdio.h>
main()
{
    char ch;
    while((ch=getchar())!='\n'）
        if(ch='a'&&ch<='z') {
            _______;
            if(ch>'Z'&&ch<='Z'+2)
                _______;
        }
}

　　 6.下列函数 FUNC6 的功能是删除字符串 s 中的所有空自字符，包括 Tab 字符、回车符以及换行符。
请在函数的空白处（下划线上）填入合适内容，使函数完整。

#include<stdio.h>
#include<string.h>
#include<ctype.h>
FUNC6(char *s)
{
    int i,t;
    char c[80];
    for(i=0,t=0;s[i];i++)
    {
        if(!isspace(______))
            c[_____]=s[i];
    }
    c[t]='\0';
    strcpy(s，c);
}

　　 7. 下列程序的功能是判断输入的字符串是否是 “回文”，(注：按顺序读与按逆序读都一样的字符串被称为 “回文”，例如：abcdcba)。
请在程序的空自处（下划线上）填入合适内容，使程序完整。

#include <stdio.h>
#include <string.h>

main()
{
    char ch[81],*p=ch,*q;
    gets(p);
    q=p+_________;
    while(_____){
        if(*p==*q) {
            p++;
            q--;
        }
        else
            break;
    }
    if(p<q)
        printf("该字符串不是回文！'\n");
    else
        printf("该字符串是回文！\n");

　　 8.下列程序的功能是：对于字符类型变量 ch=108，保留中间两位，而将高、低 3 位清零。
请在程序的空白处（下划线上）填入合适内容，使程序完整。

main()
{
    char ch;
    ch=108;
    ch=_____;
    printf("%d",ch);
}

　　 9.设 file 为存放了整型数据的二进制文件。下列程序的功能是从该文件中读取第 3 个数据输出到屏幕上。
请在程序的空自处（下划线上）填入合适内容，使程序完整。

#include <stdio.h>
main()
{
    FILE *fp;
    int number;
    fp=fopen("file","rb");
    fseek(fp，______,SEEK_SET);
    fread(____,2,1,fp);
    printf("%d",number);
    fclose(fp);
}

　　 10.下列程序的功能是将一个磁盘中的二进制文件复制到另一个磁盘中。两个文件的文件名随命令行一起输入，输入时原有文件的文件名在前，新复制文件的立件名在后。
请在程序的空自处（下划线上）填入合适内容，使程序完整。

#include <stdio.h>
main(int arge, char *argv[])
{
    FILE *old, *new;
    if(argc!=3){
        printf("You forgot to enter a filename!\n");
        exit(0);
    }
    if(old=fopen(_____)==NULL){
        printf("Cannot open infile!\n");
        exit(0);
    }
    if(new=fopen(_____)==NULL) {
        pnntf("Cannot open outfile!\n").
        exit(0);
    }
    while(!feof{old)
        fputc(fgetc(old),new);
        fclose(old);
        fclose(new};
    }

6. 六、简答题

　　 （本题共 20 分，每小题各 5 分）

　　 1.在 c 语言中，函数调用时数据的传递通常青哪儿种方式？
2.在 C 语言中，指针可以做哪些运算？
3.共用体（union）具有哪些基本特征？ 4.使用文件的基本操作步骤是怎样的？

7. 七、程序设计题

　　 （本题 15 分）

　　 请编写程序，该程序的功能是找出并且删除一维整型数组 a[100]中的最小值元素。
要求：(1) 数组各元素通过键盘精 ^ 获得树值； (2) 所有对数组元素的引用必须通过指针完成。

8. 八、程序设计题目

　　 （本题 20 分）

　　 请仅编写出 $C$ 语言函数 char *maxword(char *s, char *t),该函数的功能是求出字符 $s$ 与字符 $t$ 的最长公共单词（这里，假设两个字符串均由英文字母和空格字符组成）;若找到这样的公共单词，函数返回该单词，否则，函数返回 $NULL$.
例如：若 s="This is C programming text", t="This is a text for C programming",则函数返回 "programming"。
要求：(1) 函数中不得设置保存单词的存储空间；
(2) 给出函数之前请用文字简要叙述函数的基本思想。