当前位置：文档之家 › 北航数据结构与程序设计真题2013年北航991真题及答案

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

  • 格式：doc
  • 大小：33.00 KB
  • 文档页数：15

百度文库 - 让每个人平等地提升自我 1 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．假设用单个字母表示中缀表达式中的一个运算数(或称运算对象)，并利用堆栈产生中缀表达式对应的后缀表达式。对于中缀表达式A+B*(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中没有弧； 百度文库 - 让每个人平等地提升自我 2 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-树的某个结点中插入一个新的关键字值而引起结点产生分裂，则该结点中原有的关键字值的数目是( )。 百度文库 - 让每个人平等地提升自我 3 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(-----); } 百度文库 - 让每个人平等地提升自我 4 } 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++; 百度文库 - 让每个人平等地提升自我 5 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; i *p=*p+(*-----); 百度文库 - 让每个人平等地提升自我 6 *q=*q+(*-----); } } main( ) { int a[N][N], i, j, x, y; for(i=0; i for(j=0; j scanf(“%d”, *(a+i)+j); FUNC3(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;

合集下载

北航《C++程序设计》复习题二答案完整版

北航《C++程序设计》复习题二答案完整版

北航《C++程序设计》复习题二一、单选题（共10题，每题2分，共20分）1、已知x=5，则执行语句x += x -= x*x ；后，x的值为___C___。

A．25B．40C．-40D．202、下面for语句执行时循环次数为___B___。

for （int i=0，j=5；i=j；）{ cout << i << j << endl；i++；j--；}A．0B．5C．10D．无限3、已知int a[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }, *p = a ;则不能表示数组a 中元素的式子是___A___。

A．aB．a[ p-a ]C．*pD．*a4、不能作为重载函数的调用的依据是___C___。

A．参数个数B．参数类型C．函数类型D．函数名称5、当一个派生类保护继承一个基类时，基类中的所有公有成员和保护成员成为派生类的___B___。

A．友员B．protected成员C．private成员D．public 成员6、I/O类库的根基类是___C___。

A．istreamB．ostreamC．iosD．fstream7、关于delete运算符的描述中，错误的是( C )A、它必须用于new返回的指针B、它也适用于空指针C、对于一个指针可以多次使用该运算符D、指针名前只用一对方括号符，不管删除数组的维数8、为了取代C中带参数的宏，在C++中使用（B）A、重载函数B、内联函数C、递归函数D、友元函数9、下面有关重载函数的说法中正确的是（C ）A、重载函数必须具有不同的返回值类型B、重载函数形参个数必须不同C、重载函数必须有不同的形参列表D、重载函数名可以不同10、对于包括（B ）类型数据成员的用户定义类型必须定义其析构函数。

A、staticB、指针类型C、字符串D、字符型二、判断题（共10题，每题1分，共10分）1、对于全局函数int f(void)，与其完全等价的函数原型为const int f( )。

北航网络教育C++程序设计习题1及答案

北航网络教育C++程序设计习题1及答案

《C++程序设计》习题1一、单项选择题1. 下面正确的字符常量是（）。

A、"a"B、'\\''C、'W'D、D、''2. 声明或定义一个内联函数时，必须在函数开始使用保留字（）。

A、StaticB、ConstC、inlineD、extern3. 下列各种函数中，（）不是类的成员函数。

A、构造函数B、析构函数C、友元函数D、拷贝构造函数4. 若用数组名作为函数调用的实参，传递给形参的是（）。

A、数组的首地址B、数组中第一个元素的值C、数组全部元素的值D、数组元素的个数5. 函数重载是指（）。

A、两个或两个以上的函数取相同的函数名，但形参的个数或类型不同B、两个以上的函数取相同的名字和具有相同的参数个数，但形参的类型可以不同C、两个以上的函数名字不同，但形参的个数或类型相同D、两个以上的函数取相同的函数名，并且函数的返回类型相同6. 在下面构造函数的声明中，存在着语法错误的是（）。

A、BC(int a，int)；B、BC(int，int)；C、BC(int，int＝5)；D、D、BC(int x；int y)；7. 在一个类中可以对一个操作符进行（）重载。

A、1种B、2种以下C、3种以下D、D、多种8. strcmp(str1,str2)<0 表示（）。

A、str1的长度小于str2B、str1的长度大于str2C、str1小于str2D、str1的内容小于str2的内容9. 预处理命令在程序中都是以（）符号开头的。

A、*B、#C、&D、@10. 由C++源程序文件编译而成的目标文件的默认扩展名是（）。

A、cppB、objC、exeD、lik11. 每个类（）构造函数。

A、只能有一个B、只可有公有的C、可以有多个D、只可有缺省的12. 在下面构造函数的声明中，存在着语法错误的是（）。

A、BC(int a，int)；B、BC(int，int)；。

北航计算机系考研复试上机真题及答案(06-12年)

北航计算机系考研复试上机真题及答案(06-12年)

0 所在的行，0 的左边和右边必须有 1 0 所在的列，0 的上面和下面必须有 1 所以，解题思路就是，遍历所有的行和列，记录改行或列，最左面和最右面（或 者最上面和最下面）1 的坐标，然后当遇到 0，判断是否处于记录的值的中间， 是，则是内陆，面积加 1，否则不加。 代码：
#include <stdio.h> #include <stdlib.h>
#endif /* JOBDU_H_ */ while(scanf("%d",&N) != EOF){
int i,j; //初始化 memset(data,-1,100*4*sizeof(int)); //读入数据 for(i=0;i<N;i++){
for(j=0;j<N;j++){ scanf("%d",&island[i][j]);
area++;
//printf("i=%d,j=%d\n",i,j); for debug } } } } printf("%d\n",area); } return 0; }
3.【问题描述】
统计关键字出现位置
输入：
一行标准 c 语言代码（字符个数小于 300），统计出该字符串中关键字的 if，while，for 所 在的位置，按照关键字出现的顺序依次输出。注意双引号内的不需要统计。 输入：一行标准 c 语言代码，字符个数小于 300
输入：
第一行输入一个整数 N，表示输入方阵的维数 输入一个 N 维方阵
输出：
小岛面积
样例输入：
6 111111 110001 100010 110111 010100 111111
北航201303学期算法与数据结构答案作业4

北航201303学期算法与数据结构答案作业4

作业4单项选择题第1题假设有对角矩阵a[n][n]，我们可以按行序为主将对角矩阵A的非零元素存入一个一维数组B[K]中。

给出二维数组的任一元素a[i][j]与一维数组B[K]对应的下标m的关系：（）。

A、k = 2*i + jB、k = 2 * j + iC、k = 3* (i + j )D、k = i + j答案：A第2题假设有对称矩阵a[n][n]，我们可以按行序为主将对称矩阵Ａ的下三角中的元素存入一个一维数组Ｂ［Ｋ］（Ｋ＝ｎ（ｎ＋１）／２）中。

给出二维数组的任一元素a[i][j]与一维数组B[K]对应的下标m的关系：（）。

A、(i-1)*(j+1)=kB、(i+1)*(j+1)=kC、(i-1)*j=kD、i*(j+1)=k答案：A第3题假定M行N列的数组a是行优先存贮的，L是元素a[0][0]的存贮地址，每个元素占K个存贮单元，元素a[I][j]的地址是：（）。

A、L + (I –1)* N * K +j*KB、L +( I * N +j)*KC、( I * N * K + (J –1) *KD、L +( I * M +j) * K答案：B第4题对给定的图，Prim方法与Kruskal方法都能给出最小代价生成树，针对最小代价生成树的算法，下面的说法哪一个是正确的：（）。

A、Prim方法与Kruskal方法均不需要进行圈的判断B、Prim方法与Kruskal方法都需要进行圈的判断C、Prim方法需要进行圈的判断，Kruskal方法不需要进行圈的判断D、Prim方法不需要进行圈的判断，Kruskal方法需要进行圈的判断答案：D多项选择题第5题假定以单向链表方式存贮堆栈，栈顶指针变量为p，表示栈空时，下面的说法哪一个是正确的():A、p==-1B、p==0C、p==NULLD、p != NULL答案：B|C第6题下述陈述中哪一项是正确的():A、文件中能唯一标识一个记录的数据项称之为主关键字B、文件中能唯一标识一个记录的数据项组合称之为主关键字C、文件中能标识一个记录的数据项称之为主关键字D、文件中能标识一个记录的数据项组合称之为主关键字答案：A|B第7题常用的线性表存贮结构有():A、顺序存贮结构B、链表存贮结构C、队列存贮结构D、堆栈存贮结构E、顺序存贮与链表存贮混合结构答案：A|B|E第8题常用的堆栈存贮结构有():A、顺序存贮结构B、链表存贮结构C、顺序存贮与链表存贮混合结构D、指针存贮结构答案：A|B判断题第9题空串是打印后不出现任何字符的字符器。