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

贡献者： xzllxls

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

1. 一、单项选择题

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

　　 1.下列关于线性表的存储结构的叙述中，错误的是（）。
A.线性表的顺序存储结构中隐式地存储了数据元素之间的逻辑关系
B.线性表的顺序存储结构-定需要占用一片地址连续的存储空间
C.线性表的链式存储结构通过指针来反映数据元素之间的逻辑关系
D.线性表的链式存储结构占用的存储空间一定不连续

　　 2.若 front 和 rear 分别表示链接队列的队头指针与队尾指针，则向队列中插入一个由 p 指的新元素的过程是依次执行
A. rear=p; front=p;
B. front=p; rear-p;
C. rear->link=p; rear=p;
D. font->link=p; rear=p;

　　 3.下列关于二叉树的叙述中，正确的是（）
A.二叉树的度可以小于 2
B.二叉树的度等于 2
C.二叉树中至少有一一个结点的度为 2
D.二叉树中每一个结点的度都为 2

　　 4.若某二叉树有 40 个叶结点，则该二叉树的结点总数最少是（）
A.78 $\qquad$ B.79 $\qquad$ C. 80 $\qquad$ D.81

　　 5.若采用邻接矩阵存储-个有向图，且邻接矩阵主对角线以下元素均为 0,则该有向图的拓扑序列（）。
A.存在且惟一 $\qquad$ B.存在但可能不惟一
C.不存在 $\qquad$ D.无法确定

　　 6.下面关于 AOE 网的叙述中，正确的是（）。
A. AOE 网是一个带权的连通图
B. AOE 网是一个带权的强连通图
C. AOE 网是一个带权的无回路的连通图
D. AOE 网是一个带权且无回路的有向图

　　 7.下列关于线性表查找方法的叙述中，错误的是（）.
A.顺序查找法适合于采用顺序存储结构和链式存储结构的线性表的查找
B.对于相同元素，顺序查找法一定能够查找到表中首次出现的元素
C.对于相同元素，折半查找法一定能够查找到表中首次出现的元素
D.对于相同元素，折半查找法不一定能够查找到表中首次出现的元素

　　 8.在二叉排序树中进行查找的平均时间效率主要与下列因素之一有关，该因素是（）
A.二叉排序树的深度 $\qquad$ B.二叉排序树中结点的个数的多少
C.被查找结点的度 $\qquad$ D.二叉排序树的存储结构

　　 9.下列 4 种排序方法中，每一趟排序结束时不一定能够确定一个元素排序的最终位置的是（）
A.插入排序 $\qquad$ B.快速排序
C.堆积（Heap）排序 $\qquad$ D.二路归并排序。

　　 10.下列 4 种排序方法中，当待排序的序列中元素初始时已经按值有序，排序所花费的时间反而有可能最多的是（）
A.泡排序 $\qquad$ B.谢尔（Shel1）排序
C.快速排序 $\qquad$ D.堆积（Heap）排序

2. 二、简答题

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

　　 1.等概率情况下，在长度为 n 的顺序表中插入和删除一个数据元素分别需要平均移动多少个元素？移动的元素个数主要取决于哪几个因素？

　　 2.在采用循环单链表作为某队列的存储结构时，可以只设置一个队头指针，也可以只设置一个队尾指针。请问：从操作的时间效率考虑，采用哪种方案更合适？为什么？

　　 3.对于具有 n 个顶点、e 条边的稀疏图和稠密图，就空间性能而言，采用邻接矩阵存储方法和邻接表存储方法哪一种更合适？为什么？

　　 4.什么是小顶堆积（Heap）？在小顶堆积中，值最大的元素可能处在什么位置？(可以借助一棵二叉树描述)

3. 三、综合题

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

　　 1.下列算法的功能是删除长度为 n 的顺序表 A 中重复出现的多余元素，即对于重复出现的元素，表中只保留一个。请在算法的空白处填上必要的内容，使算法完整。

void PURGE(ElemType A[ ], int &n)
{
    int i=0, j, k;
    while(i<n) {
        j=i+1;    /*从第i+1个元素开始逐个与第i个元素比较*/
        while(j<n)
            if(A[j]]==A[i) {    /*若A[j]与A[i]相同，删除A[j] */
                for( ① )
                    A[k-1]=A[k];
                n--;    /*修改表的长度*/
            } else
                ②
        ③
}

　　 2.请将由题三 2 图给定的树转换为一棵二叉树。(只须画出转换后的二叉树)

　　 3.已知某 3 阶 B 树如题三 3 图所示，请画出在该 B 树中插入关键字 20 以后得到的 B 树。

　　 4.请分别写出对数据元素序列（49,38,65,97,76,13,27,49'）按从小到大进行谢尔（Shel）排序时每一趟的结果。设排序的间隔数（也称为增量）依次为 4,2,1。

4. 四、算法设计题

　　 (本题 15 分)

　　 已知某哈夫曼树采用二叉链表存储，结点构造为 lchild，data，rchild 其中，叶结点的 data 域中已经存放了该叶结点对应的权值。请写一非递归算法，该算法的功能是计算根结点指针为 T 的哈夫曼树的带权路径长度（WPL）。
要求：
1.用文字简要给出算法的基本思想;
2.根据算法的基本思想写出相应算法。

5. 五、程序阅读题

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

　　 1.下列程序的输出结果是（）

main()
{
    char ch='A';
    printf("ch(1)=%d,ch(2)=%c\n",ch,ch+1);
}

　　 2.下列程序段的输出结果是（）

k=l; t=3;
do{
    t+=k++;
    if(t%7==0)
        continue;
    else
        ++k;
}while(t<15);
print("%d",k);

　　 3.下列程序的输出结果是（）。

#include< stdio.h>
main( )
{
    int s[12]={1,2,3,4.4,3,2,1,1,1,2,3},a[5]={0},i;
    for(i=0;i<12;i++)
        a[s[i]]++;
    for(i=1;i<5;i++)
        prit("%d",a[i]);
    prinf("\n");

　　 4.下列程序的输出结果是（）。

#include <string.h>
main()
{
    char str1[15]=“ood",str2[10]=“morning";
    prinf("%d\n",strlen(strcat(str1,st2)));
}

　　 5.下列程序的输出结果是（）.

main()
{
    int a[5]={1,2,3,4,5},*p;
    p=a;
    printf(*%d\n",*(++p));
}

　　 6.下列程序的输出结果是（）。

main()
{
    char *s="13579";
    s++;
    printf("%c%c%c",*s,*(s+1),*s+1);
}

　　 7.下列程序的输出结果是（）

#define MAX(A,B) (A)>(B)?(A);(B)
#define PRINT(Y) printf("Y=%d\t",Y)
main()
{
    int a=1,b=2,c=3,d=4,temp;
    temp=MAX(a+b,c+d);
    PRINT(temp);
}

　　 8.下列程序的输出结果是（）

int fun(int x,int y)
{ return(x+y); }

main()
{
    int a=2,b=5,c=8;
    printf("%d\n",fun(fun(a+c,b),a-c));
}

　　 9.下列程序的输出结果是（）。

#include <stdio.h>
main()
{
    struct date{
        int year,month,day;
    }today;
    printf("%d\n","sizeof(struct date));
}

　　 10.执行下列程序后，文件 file2.txt 中的内容是（）。

#include <stdio.h>
main()
{
    FILE *in,*out;
    char *str1=“YOU PLAN TO FAIL.";
    char *str2=“IF YOU FAIL TO PLAN";
    if(in=fopen("filt.cxt","))!=NULL)
        while(*str1!='')
            fputc(*str1++,in);
    fclose(in);
    if((in=fopen("“filel t.,"))!=NULL)&&((out-foen("fle2.txt'",")!=NULL){
        while(!eof(in)){
            fgetc(in);
            fputc(*str2++ ,out);
        }
    }
    fclose(in);
    fclose(out);
}

6. 六、填空题

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

　　 1.对于下列程序，为了使输出结果为 t=4, 输入量 x 和 y 应该满足的条件是（）

main()
{
    int x,y,s=1,t=l;
    scanf("%d,%d",&x,&y);
    if(x>0)
        s=s+1;
    if(x>y)
        t=s+t;
    else if(x==y)
        t=5;
    else
        t=2*s;
    printf("t=%d",t);
}

　　 2.若已有下列定义，则表达式 $p->b/n.a$ 的值是（①）,表达式 $p->b/n.a*++p->b$ 的值是（②），表达式 $(*p).a+p->c$ 的值是（③）。

struct num{
    int a;
    int b;
    float C;
}n={1,3,5.0};
struct num *p=&n;

　　 3.下列程序段的功能是计算 1000! 的末尾含有多少个零。请在程序段的空白处填上必要的内容，使程序段完整。(提示：只要计算出 1000!中含有因数 5 的个数即可)

for(k=0,i=5;i<=1000;i+=5){
    m=i;
    while(___){
        k++;
        m=m/5;
    }
}

　　 4.下列程序的功能是通过指针操作，找出并输出三个整数中的最小者。请在程序的空白处填上必要的内容，使程序完整。

#include <stdlib.h>
main()
{
    int *a,*b,*c,num,x,y,z;
    a=&x;
    b=&y;
    c=&z;
    printf("Input a,b,c:");
    scanf("%d%d%d",a,b,c);
    printf("%d,%d,%d\n",*a,*b,*c);
    num=*a;
    if(*a>*b)
        ( (1) );
    if(num>*c)
        ( ② );
    printf("The minimun=%d\n",num);
}

　　 5.下列程序的功能是先由用户通过键盘输入一个文件名，然后向此文件输入一串字符（假设输入以字符 “#” 结束），最后再将当前日期写到文件的尾部。请在程序的空白处填上必要的内容，使程序完整。

#include <stdio.h>
main()
{
    char ch,date[20],fname[30];
    FILE *fp;
    printf("Input the file name:");
    sanf("%s",fmame);
    if(fp=fopen( ① ))==NUL){
        print("Can not open file %s !\n", fname); 
        exit(0);
    }
    printf("Input a string:\n");
    while(ch=getchar( )!='#')
        fpute( ② ));
    printf("Enter date:\n");
    scanf("%s",date);
    fprint( (3) );
    fclose(fp);
}

7. 七、程序设计题

　　 (本题 15 分)

　　 请编写一 C 语言程序，该程序的功能是先通过键盘输入一个整数 n，然后调用一个递归函数fun(int n)计算 1+2+3+...+n,最后输出计算结果。

8. 八、程序设计题

　　 (本题 20 分)

　　 请设计一 C 语言函数（注：只须写出函数，不必写出完整程序），该函数的功能是用尽可能高的时间效率与空间效率将-一个 int 类型的数组 A[0..n- 1]的所有元素依次循环右移 k 个位置。
例如，对于某数组，当 k=3 时（即把数组所有元素循环右移 3 个位置），是将 10,20,30,40,50,60,70 转换为 50,60,70,10,20,30,40