北航数据结构与程序设计真题-2013年北航991真题及答案.doc

            2013年“数据结构与C程序设计”(代码991)试题
一、单项选择题（本题共20分，每小题各2分）
1．对于长度为n的线性表，建立其对应的单链表的时间复杂度为( )。
A．O(1)； B．O(log2n)； ．O(n)； D．O(n2)。
2．一般情况下，在一个双向链表中插入一个新的链结点，( )。
A．需要修改4个指针域内的指针； B．需要修改3个指针域内的指针；
C．需要修改2个指针域内的指针； D．只需要修改1个指针域内的指针。
3．假设用单个字母表示中缀表达式中的一个运算数(或称运算对象)，并利用堆栈产生中缀表达式对应的后缀表达式。对于中缀表达式AB*(C/D-E)，当从左至右扫描到运算数E时，堆栈中的运算符依次是( )。(注：不包含表达式的分界符)
A．+*/-； B．+*(/-； C．+*-； ．+*(-。
4．若某二叉排序树的前序遍历序列为50,20,40,30,80,60,70，则后序遍历序列为( )。
A．30,40,20,50,70,60,80； B．30,40,20,70,60,80,50；
C．70,60,80,50,30,40,20； D．70,60,80,30,40,20,50。
5．分别以6, 3, 8, 12, 5, 7对应叶结点的权值构造的哈夫曼 (Huffman) 树的深度为( )。
A．6； B．5； C．4； D．3。
6．下列关于图的叙述中，错误的是( )。
A．根据图的定义，图中至少有一个顶点；
B．根据图的定义，图中至少有一个顶点和一条边(弧)；
C．具有n个顶点的无向图最多有n(n-1)/2条边；
D．具有n个顶点的有向图最多有n(n-1)条边(弧)。
7．若在有向图G的拓扑序列中，顶点vi在顶点vj之前，则下列4种情形中不可能出现的是( )。
A．G中有弧；
B．G中没有弧；
C．G中有一条从顶点vi到顶点vj的路径；
D．G中有一条从顶点vj到顶点vi的路径。
8．下列关于查找操作的叙述中，错误的是( )。
A．在顺序表中查找元素可以采用顺序查找法，也可以采用折半查找法；
B．在链表中查找结点只能采用顺序查找法，不能采用折半查找法；
C．一般情况下，顺序查找法不如折半查找法的时间效率高；
D．折半查找的过程可以用一棵称之为“判定树”的二叉树来描述。
9．在一棵m阶B-树中，除根结点之外的任何分支结点包含关键字的个数至少是( )。
A．m/2-1； B．m/2； C．m/2-1； D．m/2。
10．若对序列(49, 38, 65, 97, 76, 13, 27, 49’)进行快速排序，则第一趟排序结束(即确定了第1个分界元素的最终位置)时，序列的状态是( )。
A．(13, 27, 49’, 38, 49, 76, 97, 65)；B．(13, 38, 27, 49’, 49, 76, 97, 65)；
C．(13, 38, 49’, 27, 49, 97, 76, 65)；D．(13, 38, 49’, 27, 49, 76, 97, 65)。

二、填空题(本题共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)中元素按值从小到大进行排序，整个排序过程中所进行的元素之间的比较次数为(   )。

三、综合题(本题共20分，每小题各5分)
1．一般情况下，当一个算法中需要建立多个堆栈时可以选用下列三种处理方案之一。问：这三种方案之间相比较各有什么优点和缺点？
（1）多个堆栈共享一个连续的存储空间；
（2）分别建立多个采用顺序存储结构的堆栈；
（3）分别建立多个采用链式存储结构的堆栈。
2．已知二叉树采用二叉链表存储结构，根结点指针为T，链结点类型定义为：
typedef struct node{
     char data;             /* 数据域 */
     struct node *lchild, *rchild;    /* 指向左、右子树的指针域 */
} *BTREE；
下面的算法的功能是输出二叉树中所有叶结点的数据信息。
请在算法的空白处(符号-----处)填入合适内容，使算法完整。
void FUNC(BTREE T)
{   if(T!=NULL){
      if((-----)
        printf(“%c”, T->data);
      FUNC(-----);
      FUNC(-----);
      }
}
3．对给定AOE网(如题三3图所示)，请完成
（1）分别求出各活动ai(i=1, 2, …, 14)的最早开始时间与最晚开始时间；(以表格形式给出结果)
（2）求出所有关键路径。(请以图形方式画出各关键路径)
（说明：由于题三3图在本网站内无法显示，可参见指定教材p280页8-16题）
4．已知要将给定的关键字值序列(42, 51, 16, 26, 50, 25, 37, 68, 64, 33, 18)进行散列存储，并且要求装填因子(也称负载因子)α≈0.61，
（1）请利用除留余数法构造出合适的散列函数；
（2）请画出利用该散列函数依次将序列中各关键字值插入到散列表以后表的状态。设散列表初始为空，并且采用线性探测再散列法处理散列冲突。

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

五、填空题(本题共20分，每小题各2分)
1．已知某等比数列的第一项a1为1，公比为3，下列程序的功能是输出该数列中小于1000的最大项an及其对应的n。
请在程序的空白处(符号-----处)填入合适内容，使程序完整。
main( )
{   int n=1, a=1, q=3;
      while(1){
        a=a*q;
        n++;
        if(a>=1000)
             -----;
      }
      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; iNC3(a, &x, &y); /* x，y中分别存放主对角线与副对角线上的元素之和 */
      printf(“%d, %d\n”, x, y);
}
4．下列程序的功能是先通过键盘输入一正整数，然后调用一递归函数FUNC4，该函数将正整数转换为对应的数字字符组成的字符串显示在屏幕上。例如：若输入的正整数为583，则屏幕上显示的是字符串583。
请在程序的空白处(符号-----处)填入合适内容，使程序完整。
#include
void FUNC4(int n)
{   int i;
      i=n/10;
      if(-----)
          FUNC4(i);
      putchar(-----);
}
main( )
{   int n;
      printf(“请输入一正整数n：”);
      scanf(“%d”, &n);
      printf(“转换后的字符串是：”);
      FUNC4(n);
}
5．下列程序的功能是将小写字母转换成对应的大写字母后的第2个字母，例如，将a转换成C，将b转换成D，其中，y转换成A，z转换成B。
请在程序的空白处(符号-----处)填入合适内容，使程序完整。
#include
main( )
{   char ch;
      while((ch=getchar( ))!=‘\n’)
          if(ch>=‘a’ && ch<=‘z’){
              -----;
              if(ch>‘Z’ && ch<=‘Z’+2)
                   -----;
          }
}
6．下列函数FUNC6的功能是删除字符串s中的所有空白字符，包括Tab字符、回车符以及换行符。
请在函数的空白处(符号-----处)填入合适内容，使函数完整。
#include
#include ng.h>
#include
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
#include
main( )
{   char ch[81], *p=ch, *q;
      gets(p);
      q=p+-----;
      while(-----){
          if(*p==*q){
              p++; q--;
          }
          else
              break;
      }
      if(p      else
          printf(“该字符串是回文！\n”);
}
8．下列程序的功能是：对于字符类型变量ch=108，保留中间两位，而将高、低3位清零。
请在程序的空白处(符号-----处)填入合适内容，使程序完整。
main( )
{   char ch;
      ch=108;
      ch=-----;
      printf(“%d”, ch);
}
9．设file为存放了整型数据的二进制文件。下列程序的功能是从该文件中读入第3个数据输出到屏幕上。
请在程序的空白处(符号-----处)填入合适内容，使程序完整。
#include
main( )
{   FILE *fp;
      int number;
      fp=fopen(“file”,“rb”);
      fseek(fp, -----, SEEK_SET);
      fread(-----, 1, fp);
      printf(“%d”, number);
      fclose(fp);
}
10．下列程序的功能是将一个磁盘中的二进制文件复制到另一个磁盘中。两个文件的文件名随命令行一起输入，输入时原有文件的文件名在前，新复制文件的文件名在后。
请在程序的空白处(符号-----处)填入合适内容，使程序完整。
#include
main(int argc, 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){
        printf(“Cannot open outfile!\n”);
        exit(0);
      }
      while(!feof(old))
        fputc(fgetc(old), new);
      fclose(old);
      fclose(new);
}

六、简答题（本题共20分，每小题各5分）
1．在C语言中，函数调用时数据的传递通常有哪几种方式？
2．在C语言中，指针可以做哪些运算？
3．共用体(union)具有哪些基本特征？
4．使用文件的基本操作步骤是怎样的？

七、程序设计题（本题15分）
请编写一程序，该程序的功能是找出并且删除一维整型数组a[100]中的最小值元素。
要求：1．数组各元素通过键盘输入获得初值；
        2． 所有对数组元素的引用必须通过指针完成。

八、程序设计题（本题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． 给出函数之前请用文字简要叙述函数的基本思想。

2013年“数据结构与C程序设计”(代码991)试题参考答案

一、单项选择题
1．C    2．A    3．D    4．B    5．C    6．B    7．D    8．A    9．C    10．D

二、填空题
1．顺序     2．O(m)     3．log2k+1     4．235     5．261620;(n-1)     6．该有向图中不存在回路     7．2.9     8．m-1     9．插入排序法     10．9

三、综合题
1．答：（1）多个堆栈共享一个连续的存储空间，可以充分利用存储空间，只有在整个存储空间都用完时才能产生溢出，其缺点是当一个堆栈溢出时需要向左、右栈查询有无空闲单元。若有，则需要移动相应元素和修改相关的栈底和栈顶指针的位置。当各个堆栈接近溢出时，查询空闲单元、移动元素和修改栈底栈顶指针位置的操作频繁，计算复杂，并且耗费时间。
（2）每个堆栈仅用一个顺序存储空间时，操作简便。但难以确定初始分配存储空间的大小，空间分配少了，容易产生溢出空间分配多了，容易造成空间浪费；并且各个堆栈不能共享空间。
（3）一般情况下，分别建立多个链接堆栈不考虑堆栈的溢出（仅受用户内存空间限制），缺点是堆栈中各元素要通过指针链接，比顺序存储结构多占用存储空间。
2．(T->lchild==NULL && T->rchild==NULL)
      T->lchild
      T->rchild
3．（由于图表显示限制，此题答案见指定教材(《数据结构教程 第二版》(2012年4月第7次印刷)) 第418页8-16题）
4．
(1)．根据α=散列表中存入的元素数/散列表的长度，得到表的长度为18，因此，合适的散列函数应该为Hk)=k MOD 17。
(2)．（由于图表显示限制，此题答案见指定教材(《数据结构教程 第二版》(2012年4月第7次印刷)) 第428页9-15题）

四、算法设计题
SORT(int A[ ], int n)
{    int ,i, j, min, max, temp;
     i=1;
     while(i<=n/2){
        min=i;
        max=i;
        for(j=i+1;j            if(A[j]>A[max])
                 max=j;
        }    /* 确定某趟排序的最小值元素和最大值元素 */
        if(min!=i){
             temp=A[min]; A[min]=A[i]; A[i]=temp;
        }    /* 交换A[min]与A[i]的位置 */
        if(max!=n-i+1)
             if(max==i){
                 temp=A[min]; A[min]=A[n-i+1]; A[n-i+1]=temp;
             } /* 交换A[min]与A[n-i+1]的位置 */
             else{
                 temp=A[max]; A[max]=A[n-i+1]; A[n-i+1]=temp;
               /* 交换A[max]与A[n-i+1]的位置 */
             }
        i++;
     }
}

五、填空题
1．break a/q     2．a[n-1]>=a[n-2] FUNC2(a, n-1)     3．(*(a+i)+i) a+i)+N-i-1)     4．i!=0 n%10+′0′     5．ch-=30 ch-=26
6．*(s+i) t++     7．strlen(p)-1 p进行下列三种运算：
(1) 指针加/减一个整数。表示以当前指针所指单元的地址为起点的后或前整数个数据的地址。
(2) 指针减指针。表示两个地址之间的数据个数。（指针加指针为非法运算）
(3) 比较。表示同类型的两个指针所指对象在地址位置上的关系。
3．答：共用体具有以下三个特征：
(1) 共用体变量的成员共用一块存储空间，共用体变量所占用的字节数等于最长成员所占用的字节数；
(2) 共用体不能在定义时进行初始化；
(3) 共用体中的成员每次只能有一个起作用，当存入新成员时，原来的成员失效，其值被覆盖。
4．答：使用文件的基本操作一般有下列五个步骤：
(1) 在程序中包含头文件stdio.h
(2) 定义文件指针。例如：FILE *fp;
(3) 打开文件，使文件指针与磁盘中的实际存储的数据文件建立关联。例如：
                     fp=fopen(“test.txt”, “r”);
(4) 对文件进行读写操作。例如：fread(f, 4, 2, fp);
(5)文件使用完毕后，关闭文件。例如：fclose(fp);

七、程序设计题
#include
main( )
{   int a[100], i, *p, k=0;
    p=a;
    for(i=0; i<100; i++)
        scanf(“%d”, p+i); /* 对数组进行数据输入 */
    for(i=1; i<100; i++) /* 找出最小值元素，并记录其位置 */
        if(*(p+k)>*(p+i))
            k=i;
    for(i=k; i<99; i++)         /* 删除最小值元素 */
        *(p+i)=*(p+i+1);
    for(i=0; i<99; i++)       /* 输出处理后数组各元素 */
        printf(“%d”, *(p+i));
    printf(“\n”);
}

八、程序设计题
函数的基本思想：
从左至右顺序扫描字符串s，逐个找出单词，并记录单词的开始位置与单词的长度；若该单词的长度比已找到的单词更长，则从左至右顺序扫描字符串t；当在字符串t中找到与在s中找到的当前最长单词相匹配的单词时，记录单词的开始位置与单词的长度，并回到字符串s，在其中找出下一个更长的单词。如此下去，只至字符串s扫描结束，最后返回相应结果。
#include
#include
char *maxword(char *s, char *t)
{   char res, *temp, chs, cht;
    int i, j, found, maxlen=0;
    while(*s!=‘\0’){
        while(*s==‘ ’)
            s++; /* 过滤s中的空格 */
        for(i=0; s[i]!=‘ ’&&s[i]!=‘\0’; i++) /* 确定s中单词 */
            if(i>maxlen){
               chs=s[i];
               s[i]=‘\0’;
               temp=t;
               found=0;
               while(*temp!=‘\0’&&!found){
                    while(*temp==‘ ’)
                        temp++; /* 过滤t中的空格 */
                    for(j=0;temp[j]!=‘ ’&&temp[j]!=‘\0’;j++) /* 确定t中单词 */
                        if(j==i){
                            cht=temp[j];
                            temp[j]=‘\0’;
                            if(strcmp(s, temp)==0){
                                 maxlen=i;
                                 res=s;
                                 found=1
                            }
temp=cht;
                        }
                        temp=&temp[j];    /* 回到字符串t的某一位置*/
                    }
                    s[i]=chs;
            }
            s=&s[i]; /* 回到字符串s的某一位置*/
        }
        if(maxlen==0)
            return NULL; /* 未找到最长公共单词，返回NULL */
        else{
            res[maxlen+1]=‘\0’;
   return res;    /* 找到最长公共单词，返回该单词 */
        }
}