下载文档原格式
北京航空航天大学2011-2012学年第一学期期末<<微机原理及应用>>考试B卷班级______________ 学号______________姓名______________ 成绩______________2012年月日<<微机原理及应用>> 试卷B班级____________姓名____________学号____________成绩____________一、填空题（30分，每空1分）1.典型的微型计算机硬件主要由四部分组成，它们是___________、_________、___________和_____________。
2.8086/8088 CPU从功能上可分为两部分，即执行单元EU和总线接口单元BIU，EU 的功能是负责______________________________， BIU的功能是负责______________________________。
由于____________________的存在，使EU 和BIU 可以并行工作，因而提高了CPU的利用率。
3.微型计算机硬件各部分之间的信息都是通过总线传送，总线信号分为三组，分别为____________, ___________和___________。
4.8086的数据总线有_________位,地址总线有_________位,其中____________为地址/数据复用总线。
5.8086的标志寄存器中控制标志有_____、_____、_____。
6.8086CPU的I/O指令采用间接寻址时，使用的间接寄存器是__________。
7.在串操作中，一般假定源串在__________中，而目的串在__________中，用__________作指针对源串寻址，用__________作指针对目的串寻址。
8.半导体存储器包括__________和__________两大类。
第一章概论一、选择题1、研究数据结构就是研究（D ）。
A. 数据的逻辑结构B。
数据的存储结构C. 数据的逻辑结构和存储结构D。
数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是（ A ）。
A。
空间复杂度和时间复杂度 B. 正确性和简单性C。
可读性和文档性D。
数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ）。
A。
图B。
树C。
广义表D。
栈4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、( B )等5个特性。
A. 可执行性、可移植性和可扩充性B。
可执行性、有穷性和确定性C。
确定性、有穷性和稳定性 D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是（ C )。
for(i=0；i<m;i++）for(j=0;j〈n；j++）a[i］[j]=i＊j；A. O(m2) B。
O（n2) C。
O（m*n) D. O（m+n)6、算法是（D ）。
A。
计算机程序 B. 解决问题的计算方法C。
排序算法 D. 解决问题的有限运算序列7、某算法的语句执行频度为（3n+nlog2n+n2+8），其时间复杂度表示( C ）。
A。
O（n） B. O（nlog2n) C。
O（n2） D. O （log2n)8、下面程序段的时间复杂度为（ C ）.i=1；while(i<=n）i=i*3；A. O(n）B。
O(3n) C。
O(log3n) D. O(n3）9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。
A. 结构B。
关系C。
运算D。
算法10、下面程序段的时间复杂度是（A ）。
i=s=0；while（s<n)｛i++；s+=i;}A. O(n) B。
O（n2）C。
O（log2n）D。
O(n3)11、抽象数据类型的三个组成部分分别为（A）。
A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D. 数据元素、数据结构和数据类型12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量，以下解释错误的是（)。
20XX年“数据结构与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中有弧<vi,vj>；B．G中没有弧<vi,vj>；C．G中有一条从顶点vi到顶点vj的路径；D．G中有一条从顶点vj到顶点vi的路径。
已今， f ., 北京航空航天大学2017年硕士研究生招生考试初试试题科目代码：991 数据结构与C 语言程序设计（共7页）考生注意：所有答题务必书写在考场提供的答题纸上，写在本试题单上的答题一律无效（本题单不参与阅卷）。
一、单项选择题（本题共20分，每小题各2分）1."数据结构”课程研究的内容主要包括＿——°A.数据的逻辑结构与存储结构；B.数据的逻辑结构与对数据进行的操作（即算法）；C.数据的存储结构与对数据进行的操作（即算法）；D.数据的逻辑结构、存储结构以及对数据进行的操作（即算法）。
2. 与单向链表相比，双向链表的优点之一是＿＿＿。
A.可以进行随机访问；B.可以访问链表中的相邻结点；C.链表的插入和删除操作更加简便；D . 可以节省头结点指针。
3.通常情况下，将递归算法转换为等价的非递归算法需要使用一种数据结构来保存中间结果，这种数据结构是A .堆栈； B.队列； c.二叉树； D.图。
4.深度为h的完全二叉树的结点总数不会超过一。
A.2气B.2h 一1;C .2h : D.2h +l 。
5.若某二叉树的前序遍历序列为a,b, e, f, c, d, g, 中序遍历序列为b,f, e, a , d, g, c, 则后序遍历序列为———°A.f, e, b, g, d, c, a;C.b, f , e, a, d , g, c;B.f, g, e , d, b , c, a ;D.f, e, b, a, g, d, c 。
t夕＿＿，一． 6.对千一个具有n 个顶点的有向图，其边数最多为＿＿＿。
A.nX(n -1)/2条；B. n-1条；C.nX(n-1)条；D.n 2条。
第991—1页k'/后计算表达式"1a+28+3吽…+n a"的结果。
需要注意的是，当a或者n小千等千0时，该函数返回0。
提示：可以先编写一个求解旷的辅助函数，再在psum函数中计算累加和。
北京航空航天大学2010－2011学年第二学期期末《C语言程序设计》考试A 卷班级______________学号 _________姓名______________成绩 _________2011年6月15日班号学号姓名成绩《C语言程序设计》期末考试卷注意事项：1、请将所有的答案和程序写在答题纸上，写在试卷纸上不得分！2、考试时间120分钟一、选择题(每题2分，共40分)1、以下叙述正确的是______。
A) 在C 程序中，main 函数必须位于程序的最前面B) C 程序的每行中只能写一条语句C) C 语言本身没有输入输出语句D) 在对一个C 程序进行编译的过程中，可发现注释中的拼写错误2、以下正确的描述是______。
A) continue语句的作用是结束整个循环的执行B) 只能在循环体内和switch语句体内使用break语句C) 在循环体内使用break语句或continue语句的作用相同D) 从多层循环嵌套中退出时，只能使用goto语句3有以下程序void main(){ double d=3.2;int x,y;x=1.2;y=(x+3.8)/5.0;printf("%d\n",d*y);}程序的输出结果是____A) 3 B) 3.2 C) 0 D) 3.074、若变量已正确说明为float类型，要通过语句scanf("%f %f %f ",&a,&b,&c);给a赋值10.0，给b赋值22.0，给c赋值33.0，不正确的输入形式是______。
A) 10<enter> 22<enter>33<enter>B) 10.0,22.0,33.0<enter>C) 10.0<enter> 22.0 33.0<enter>D) 10 22<enter>33<enter>5、main(){ int a=0,b=0,c=0,d=0;if(a=1) b=1;c=2;else d=3;printf("%d,%d,%d,%d\n",a,b,c,d);}程序输出是____A) 0,1,2,0 B) 0,0,0,3 C) 1,1,2,0 D) 编译有错6、能正确表示“当x的取值在[1,10]和[200,210]范围内为真，否则为假的表达式是______。
北航算法与数据结构复习题北航《算法与数据结构》复习题单选题（每小题2分，总分10分）1、线性表若采用链表存储结构时，要求内存中可用存储单元的地址（D ）A、必需是联系的B、部分地址必须是连续的C、一定是不连续的D、连续不连续都可以2、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以什么为标准操作（B）A、条件判断B、结点移动C、算术表达式D、赋值语句3、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（B ）A、p->next=s;s->next=p->next;B、s->next=p->next;p->next=s;C、p->next=s;p->next=s->next;D、p->next=s->next;p->next=s;4、对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（C ）A、(2,5,12,16)26(60,32,72)B、(5,16,2,12)28(60,32,72)C、(2,16,12,5)28(60,32,72)D、(5,16,2,12)28(32,60,72)5、稀疏矩阵的压缩存储方法是只存储（A ）A、非零元素B、三元组（i,j, aij）C、aijD、i,j1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（A）排序法。
A、插入B、选择C、希尔D、二路归并2、用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（D ）A、一定都是同义词B、一定都不是同义词C、都相同D、不一定都是同义词3、将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为（D ）A、42B、40C、21D、204、一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（B ）A、不确定B、n-i+1C、ID、n-i5、设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数最少（C）个A、k+1B、2kC、2k-1D、2k+1判断题（每小题1分，总分10分）(A==对，B==错)6、在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的结果。
2011 年硕士研究生入学考试“数据结构与C语言程序设计”(科目代码:991)试题与答案一、单项选择题(本题共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．front->link=p; rear=p;3．下列关于二叉树的叙述中，正确的是。
A．二叉树的度可以小于2 B．二叉树的度等于2C．二叉树中至少有一个结点的度为2 D．二叉树中每一个结点的度都为24．若某二叉树有40个叶结点，则该二叉树的结点总数最少是。
A．78 B．79 C．80 D．815．若采用邻接矩阵存储一个有向图，且邻接矩阵主对角线以下元素均为0，则该有向图的拓扑序列。
A．存在且惟一B．存在但可能不惟一C．不存在D．无法确定6．下面关于AOE 网的叙述中，正确的是。
A．AOE 网是一个带权的连通图B．AOE 网是一个带权的强连通图C．AOE 网是一个带权的无回路的连通图D．AOE 网是一个带权且无回路的有向图7．下列关于线性表查找方法的叙述中，错误的是。
A．顺序查找法适合于采用顺序存储结构和链式存储结构的线性表的查找B．对于相同元素，顺序查找法一定能够查找到表中首次出现的元素C．对于相同元素，折半查找法一定能够查找到表中首次出现的元素D．对于相同元素，折半查找法不一定能够查找到表中首次出现的元素8．在二叉排序树中进行查找的平均时间效率主要与下列因素之一有关，该因素是。
A．二叉排序树的深度B．二叉排序树中结点的个数的多少C．被查找结点的度D．二叉排序树的存储结构9．下列4 种排序方法中，每一趟排序结束时不一定能够确定一个元素排序最终位置的是。
A．插入排序B．快速排序C．堆积(Heap)排序D．二路归并排序210．下列4 种排序方法中，当待排序的序列中元素初始时已经按值有序，排序所花费的时间反而有可能最多的是。
A．泡排序B．谢尔(Shell)排序C．快速排序D．堆积(Heap)排序二、简答题(本题共20分，每小题各5 分)1．等概率情况下，在长度为n 的顺序表中插入和删除一个数据元素分别需要平均移动多少个元素？移动的元素个数主要取决于哪几个因素？2．在采用循环单链表作为某队列的存储结构时，可以只设置一个队头指针，也可以只设置一个队尾指针。
请问：从操作的时间效率考虑，采用哪种方案更合适？为什么？3．对于具有n 个顶点、e 条边的稀疏图和稠密图，就空间性能而言，采用邻接矩阵存储方法和邻接表存储方法哪一种更合适？为什么？4．什么是小顶堆积(Heap)？在小顶堆积中，值最大的元素可能处在什么位置？（可以借助一棵二叉树描述）三、综合题(本题共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 图给定的树转换为一棵二叉树。
（只须画出转换后的二叉树）题三2 图3．已知某3阶B-树如题三3图所示，请画出在该B-树中插入关键字20 以后得到的B-树。
题三3 图6030 50 7015 25 35 45 55 65 75AB C DE F G H I J34．请分别写出对数据元素序列(49,38,65,97,76,13,27,49 )按从小到大进行谢尔(Shell）排序时每一趟的结果。
设排序的间隔数(也称为增量)依次为4,2,1。
四、算法设计题(本题15 分)已知某哈夫曼树采用二叉链表存储，结点构造为lchild data rchild ，其中，叶结点的data 域中已经存放了该叶结点对应的权值。
请写一非递归算法，该算法的功能是计算根结点指针为T的哈夫曼树的带权路径长度(WPL)。
要求：1．用文字简要给出算法的基本思想；（5 分）2．根据算法的基本思想写出相应算法。
（10 分）五、程序阅读题(本题共20分，每小题各2分)1．下列程序的输出结果是。
main( ){char ch=‘A’;printf(“ch(1)=%d,ch(2)=%c\n”,ch,ch+1);}2．下列程序段的输出结果是。
k=1; t=3;do{t+=k++;if(t%7==0)continue;else++k;}while(t<15);printf(“%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++)printf(“%d”,a[i]);printf(“\n”);}4．下列程序的输出结果是。
#include <string.h>main( ){ char str1[15]= “good”,str2[10]= “morning”;printf(“%d\n”,strlen(strcat(str1,str2)));}5．下列程序的输出结果是。
main( )4{ 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(“file1.txt”,“w”))!=NULL)while(*str1!=‘.’)fputc(*str1++,in);fclose(in);if(((in=fopen(“file1.txt”,“r”))!=NULL)&&((out=fopen(“file2.txt”,“w”)!=NULL)){while(!eof(in)){fgetc(in);5fputc(*str2++,out);}}fclose(in);fclose(out);}六、填空题(本题共20分，每小题各4 分)1．对于下列程序，为了使输出结果为t=4，输入量x和y应该满足的条件是。
main( ){ int x,y,s=1,t=1;scanf(“%d,%d”,&x,&y);if(x>0)s=s+1;if(x>y)t=s+t;else if(x==y)t=5;elset=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;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:”);6scanf(“%d%d%d”,a,b,c);printf(“%d,%d,%d\n”,*a,*b,*c);num=*a;if(*a>*b)①;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:”);scanf(“%s”,fname);if((fp=fopen( ①))==NULL){printf(“Can not open file %s !\n”,fname);exit(0);}printf(“Input a string:\n”);while((ch=getchar( ))!=‘#’)fputc( ②);printf(“Enter date:\n”);scanf(“%s”,date);fclose(fp);}七、程序设计题(本题15 分)请编写一C语言程序，该程序的功能是先通过键盘输入一个整数n，然后调用一个递归函数fun(int n)计算1+2+3+…+n，最后输出计算结果。
