北京航空航天大学 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'=(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)对应的小顶堆积是( )。

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;
并且 $n$ 个顶点结点构成一个数组结构 $G[0..n-1]$.请写一个算法,该算法判断给定的顶点序列 $V[0..n-1]=(v_1,v_2,v_3,...,v_n)$ 是否是该有向图的一个拓扑序列,若是该有向图的一个拓扑序列,算法返回 1,否则,算法返回 0.

5. 五、单项选择题

   (本题共 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);
}
A. defdef $\qquad$ B. abcdef $\qquad$ C. abc d $\qquad$ D. d d

   8.当说明一个结构体变量时系统分配给它的内存是( )
A.结构中最后一个成员所需的内存量
B.结构中第一个成员所需的内存量
C.成员中占内存是最大者所需的容量
D.各成员所需内存量的总和

   9.下列程序的输出结果为( ).

#define ABC(x) x*x
main( )
{
    int a,k=3;
    a=++ABC(k+1);
    print("%d",a);
}
A.8 $\qquad$ B.9 $\qquad$ C.14 $\qquad$ D.17

   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.下列函数的功能是根据公式

\begin{equation} s=1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+...+\frac{1}{2n+1}~ \end{equation}
计算 $s$ 的值,其中,$n$ 通过形参传入($n\geqslant0$),计算结果通过形参指针传回。
请在函数的空白处(方框内)填入合适的内容,使函数完整。
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);
}


致读者: 小时百科一直以来坚持所有内容免费无广告,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元,我们一周就能脱离亏损, 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利