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

1、 2013 年“ 数据结构与 C 程序设计”( 代码 991)试题一、单项选择题（本题共 20 分，每小题各 2 分）1对于长度为 n 的线性表，建立其对应的单链表的时间复杂度为( )。AO(1)； B O(log2n)； O(n)； DO(n2)。2一般情况下，在一个双向链表中插入一个新的链结点，( )。A需要修改 4 个指针域内的指针； B需要修改 3 个指针域内的指针；C需要修改 2 个指针域内的指针； D只需要修改 1 个指针域内的指针。3假设用单个字母表示中缀表达式中的一个运算数(或称运算对象 )，并利用堆栈产生中缀表达式对应的后缀表达式。对于中缀表达式 A+B*(C/D-E)，当从

2、左至右扫描到运算数 E 时，堆栈中的运算符依次是( )。(注：不包含表达式的分界符)A+*/- ； B+*(/-； C+*- ； +*(- 。4若某二叉排序树的前序遍历序列为 50,20,40,30,80,60,70，则后序遍历序列为( )。A30,40,20,50,70,60,80； B30,40,20,70,60,80,50 ；C70,60,80,50,30,40,20 ； D70,60,80,30,40,20,50 。5分别以 6, 3, 8, 12, 5, 7 对应叶结点的权值构造的哈夫曼 (Huffman) 树的深度为( )。A6； B5； C4； D3。6下列关于图的叙述中，错误的

3、是( )。A根据图的定义，图中至少有一个顶点；B根据图的定义，图中至少有一个顶点和一条边(弧) ；C具有 n 个顶点的无向图最多有 n(n-1)/2 条边；D具有 n 个顶点的有向图最多有 n(n-1)条边(弧) 。7若在有向图 G 的拓扑序列中，顶点 vi 在顶点 vj 之前，则下列 4 种情形中不可能出现的是( )。AG 中有弧；BG 中没有弧 ；CG 中有一条从顶点 vi 到顶点 vj 的路径； D G 中有一条从顶点 vj 到顶点 vi 的路径。8下列关于查找操作的叙述中，错误的是( )。A在顺序表中查找元素可以采用顺序查找法，也可以采用折半查找法；B在链表中查找结点只能采用顺序查找法

4、，不能采用折半查找法；C一般情况下，顺序查找法不如折半查找法的时间效率高；D折半查找的过程可以用一棵称之为“判定树” 的二叉树来描述。9在一棵 m 阶 B-树中，除根结点之外的任何分支结点包含关键字的个数至少是( )。Am/2-1 ； Bm/2 ； Cm/2-1 ； Dm/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, 3

5、8, 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、的度最大可以达到 ( )。6若对有向图进行拓扑排序，则能够得到拓扑序列的条件是( )。7已知长度为 10 的顺序表中数据元素按值从小到大排列。若在该表中进行折半查找，则平均查找长度(ASL)是( )。8若在一棵 m 阶 B-树的某个结点中插入一个新的关键字值而引起结点产生分裂，则该结点中原有的关键字值的数目是( )。9有一种排序方法可能会出现这种情况：最后一趟排序开始之前，序列中所有的元素都不在其最终应该在的位置上，这种排序方法是( )。10若按照泡排序法的思想将序列(2, 12, 16, 5, 10)中元素按值从小到大进行排序，整个排序过程中所进行的元素之间的比较次数为( )。三、综合题(本

7、题共 20 分，每小题各 5 分)1一般情况下，当一个算法中需要建立多个堆栈时可以选用下列三种处理方案之一。问：这三种方案之间相比较各有什么优点和缺点？（1）多个堆栈共享一个连续的存储空间；（2）分别建立多个采用顺序存储结构的堆栈；（3）分别建立多个采用链式存储结构的堆栈。2已知二叉树采用二叉链表存储结构，根结点指针为 T，链结点类型定义为：typedef struct nodechar data; /* 数据域 */struct node *lchild, *rchild; /* 指向左、右子树的指针域 */ *BTREE；下面的算法的功能是输出二叉树中所有叶结点的数据信息。请在算法的空白处

8、(符号- 处)填入合适内容，使算法完整。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, 1

9、8)进行散列存储，并且要求装填因子( 也称负载因子 )0.61，（1）请利用除留余数法构造出合适的散列函数；（2）请画出利用该散列函数依次将序列中各关键字值插入到散列表以后表的状态。设散列表初始为空，并且采用线性探测再散列法处理散列冲突。四、算法设计题（本题 15 分）假设长度为 n 的顺序表 A1.n中每个数据元素为一整数，请写出按照下列思想将表中数据元素按值从小到大进行排序的算法：第 1 趟排序将最小值元素放在 A1中，最大值元素放在 An中；第 2 趟排序将次小值元素放在 A2中，次大值元素放在 An-1中；，依此下去，直至排序结束。五、填空题(本题共 20 分，每小题各 2 分)1已知

10、某等比数列的第一项 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=%dn”, n-1, -);2下列递归函数 FUNC2 的功能是判断整型数组 an是否为递增数组，即判断数组的元素是否按值从小到大排列。若是一个递增数组，则函数返回 true，否则，函数返回 false。请在函数的空白处(符号- 处)填入合适内容，使函数完整。bool FUNC2(i

11、nt a , int n) if(n=1)return true;if(n=2)return -;return - 3下列程序的功能是主函数调用 FUNC3 函数求方阵 a 中两条对角线上元素之和。请在程序的空白处(符号- 处)填入合适内容，使程序完整。#define N 10void FUNC3(int aNN, int *p, int *q) int i;*p=0;*q=0;for(i=0; ivoid FUNC4(int n) int i;i=n/10;if(-)FUNC4(i);putchar(-);main( ) int n;printf(“请输入一正整数 n： ”);scanf(“

12、%d”, printf(“转换后的字符串是：”);FUNC4(n);5下列程序的功能是将小写字母转换成对应的大写字母后的第 2 个字母，例如，将 a 转换成 C，将 b 转换成 D，其中， y 转换成 A，z 转换成 B。请在程序的空白处(符号- 处)填入合适内容，使程序完整。#include main( ) char ch;while(ch=getchar( )!=n)if(ch=a char c80;for(i=0,t=0; si; i+)if(!isspace(-)c-=si;ct=0;strcpy(s, c); 7下列程序的功能是判断输入的字符串是否是“回文”。(注：按顺序读与按逆序读

13、都一样的字符串被称为“回文” ，例如：abcdcba)。请在程序的空白处(符号- 处)填入合适内容，使程序完整。#include #include main( ) char ch81, *p=ch, *q;gets(p);q=p+-;while(-)if(*p=*q)p+; q-;elsebreak;if(pmain( ) FILE *fp;int number;fp=fopen(“file”,“rb”);fseek(fp, -, SEEK_SET);fread(-, 1, fp);printf(“%d”, number);fclose(fp);10下列程序的功能是将一个磁盘中的二进制文件复制

14、到另一个磁盘中。两个文件的文件名随命令行一起输入，输入时原有文件的文件名在前，新复制文件的文件名在后。请在程序的空白处(符号- 处)填入合适内容，使程序完整。#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 outfi

15、le!n”);exit(0);while(!feof(old)fputc(fgetc(old), new);fclose(old);fclose(new);六、简答题（本题共 20 分，每小题各 5 分）1在 C 语言中，函数调用时数据的传递通常有哪几种方式？2在 C 语言中，指针可以做哪些运算？3共用体(union)具有哪些基本特征？4使用文件的基本操作步骤是怎样的？七、程序设计题（本题 15 分）请编写一程序，该程序的功能是找出并且删除一维整型数组 a100中的最小值元素。要求：1数组各元素通过键盘输入获得初值；2 所有对数组元素的引用必须通过指针完成。八、程序设计题（本题 20 分）请仅

16、编写出一 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)试题

17、参考答案一、单项选择题1C 2A 3D 4B 5C 6B 7D 8A 9C 10D二、填空题1顺序 2O(m) 3log2k+1 4235 52(n-1) 6该有向图中不存在回路 72.9 8m-1 9插入排序法 109三、综合题1答：（1）多个堆栈共享一个连续的存储空间，可以充分利用存储空间，只有在整个存储空间都用完时才能产生溢出，其缺点是当一个堆栈溢出时需要向左、右栈查询有无空闲单元。若有，则需要移动相应元素和修改相关的栈底和栈顶指针的位置。当各个堆栈接近溢出时，查询空闲单元、移动元素和修改栈底栈顶指针位置的操作频繁，计算复杂，并且耗费时间。（2）每个堆栈仅用一个顺序存储空间时，操作简便。

18、但难以确定初始分配存储空间的大小，空间分配少了，容易产生溢出，空间分配多了，容易造成空间浪费；并且各个堆栈不能共享空间。（3）一般情况下，分别建立多个链接堆栈不考虑堆栈的溢出（仅受用户内存空间限制） ，缺点是堆栈中各元素要通过指针链接，比顺序存储结构多占用存储空间。2(T-lchild=NULL i=1;while(iAmax)max=j; /* 确定某趟排序的最小值元素和最大值元素 */if(min!=i) temp=Amin; Amin=Ai; Ai=temp; /* 交换 Amin与 Ai的位置 */if(max!=n-i+1)if(max=i)temp=Amin; Amin=An-i+

19、1; An-i+1=temp; /* 交换 Amin与 An-i+1的位置 */else temp=Amax; Amax=An-i+1; An-i+1=temp;/* 交换 Amax与 An-i+1的位置 */i+;五、填空题1break a/q 2an-1=an-2 FUNC2(a, n-1) 3(*(a+i)+i) (*(a+i)+N-i-1)4i!=0 n%10+0 5ch-=30 ch-=266*(s+i) t+ 7strlen(p)-1 pmain( ) int a100, i, *p, k=0;p=a;for(i=0; i*(p+i)k=i;for(i=k; i#include c

20、har *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; si!= i+) /* 确定 s 中单词 */if(imaxlen)chs=si;si=0;temp=t;found=0;while(*temp!=0 /* 过滤 t 中的空格 */for(j=0;tempj!= j+) /* 确定 t 中单词 */if(j=i)cht=tempj;tempj=0;if(strcmp(s, temp)=0)maxlen=i;res=s;found=1temp=cht;temp= /* 回到字符串 t 的某一位置*/si=chs;s= /* 回到字符串 s 的某一位置*/if(maxlen=0)return NULL; /* 未找到最长公共单词，返回 NULL */elseresmaxlen+1=0;return res; /* 找到最长公共单词，返回该单词 */