北航数据结构和程序设计真题2014北航991真题和答案解析
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中没有弧
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; i *p=*p+(*-----); *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; 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 #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 printf(“该字符串不是回文！\n”); 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 outfi 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分） 请编写一程序，该程序的功能是找出并且删除一维整型数组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．2(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，因此，合适的散列函数应该为H(k)=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] min=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．答：通常有下列三种方式： (1)参数传递方式：函数调用时根据实参传递给形参内容的不同又分为值传递与地址传递两种。 (2) 通过return语句传递数据：被调用函数可以通过return语句将函数值传递给调用函数。 (3)利用全局变量传递数据。 2．答：指针可以进行下列三种运算： (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; /* 找到最长公共单词，返回该单词 */ } } 北航考研详解与指导 一.飞行器设计 对于本校的学生来说，每年复试的内容可能会不太一样，所以具体的准备还是以到时学校通知为主，这里主要介绍去年的复试，仅供参考。2012年飞行器设计专业复试分为笔试和面试，笔试又分为专业课和专业英语。专业课考的是航天器动力学基础，给了一本参考书是肖叶伦教授的《航天器建模**》之类的，具体名字不太记得了，北航本校本专业的学生可以直接用赵育善老师航天器飞行动力学课的教材，内容基本是一样的。把这本书好好的看一遍就可以了，一个星期绝对没有问题，因为考试考的也都是比较基础的东西，看懂概念，轨道六要素，欧拉角、奇点问题，摄动，航空航天器的分类,还有几个坐标系转换，基本都是概念，动力学方程以及复杂的公式都不会考，四元数的计算也不会考。有条件的同学想办法找一下赵育善老师那门课往年的期末考试题，可以作为参考。跨专业的、以前没接触过航天课程的同学，如果看不懂书可以去找一下你联系的导师，让他安排个学生给你稍微指点一下。专业英语的话考的是翻译，给了几段中文和英文，汉译英以及英译汉，每一段都不长，都是跟航天知识有一些关系的，准备的话上网搜索一些航天相关词汇背一背就好，当然也不用找特别专业的词汇，毕竟考试中的那些单词还都是平时读文献会比较常用到的。 面试的话也不用很紧张，基本都是先简单的介绍一下自己（只有中文，没有英文介绍），问问你跟的导师是谁，四六级考了多少分，如实回答就可以。北航的同学会很快，老师问什么你答什么就行了。外校的同学老师会再问一下你本科参加竞赛的情况，或者是毕业设计的内容，在本科期间参加的重要活动什么的。总之面试其实是个很简单的事，完全不必担心，放松心态正常交流就行了。 最后提一下，其实复试并没有那么难，大家能够通过初试，都是从成千上万同龄人中脱颖而出的佼佼者，应付这么一个小考试完全没有问题。而且我留意了一下，复试名单是按照初试成绩的名次排列的，经过复试之后，前面二三十个人的名次是完全没有变化的，复试的目的只是为了从后几名中筛选一下，所以初试成绩比较高的同学只要稍加准备正常发挥就行了，不用担心的太多。 二.航天导航制导与控制 首先简单介绍一下去年复试的情况，去年是王新龙老师管招生，复试有专业英语翻译和专业笔试，笔试上的内容都是本科传感器那门课的课件里的，去年进入复试的录取率大概在百分之八十多，录取了20人，其中专业硕士和学术硕士的比例是1:1，今年未知，估计是王可东、宋佳、杨博等老师，估计只有面试，没有笔试，面试需要有一个5分钟的英文自我介绍，之后对于本校的来说，一般不会问专业性问题，都是聊聊本科时候的表现，问问你研究生打算之类的，一般都是你的导师主要问，其他老师偶尔插一句，对于外校的来说，也是先英文自我介绍，然后如果导师定下来的话，也是导师主要问问题，可能会问一些专业性的问题，但大部分都是很开放的，比如王新龙老师会问惯性导航平台和捷联的区别联系，材料力学和理论力学哪个更基础，也会有老师问一些其他无关的问题，比如为什么要来GNC等等。王新龙老师建议大家准备复试的时候重点花在对英语自我介绍的完善以及导航制导控制转业的理解上。 2015年考研复试在即，面对又一轮的考研挑战，同学们不仅要面对像初试时所要准备的专业 2017版北京航空航天大学《911材料综合》全套考研资料 我们是布丁考研网北航考研团队，是在读学长。我们亲身经历过北航考研，录取后把自己当年考研时用过的资料重新整理，从本校的研招办拿到了最新的真题，同时新添加很多高参考价值的内部复习资料，保证资料的真实性，希望能帮助大家成功考入北航。此外，我们还提供学长一对一个性化辅导服务，适合二战、在职、基础或本科不好的同学，可在短时间内快速把握重点和考点。有任何考北航相关的疑问，也可以咨询我们，学长会提供免费的解答。更多信息，请关注布丁考研网。 以下为本科目的资料清单（有实物图及预览，货真价实）： 北京航空航天大学《材料综合》全套考研资料 一、北京航空航天大学《材料综合》历年考研真题及答案解析 2015年北京航空航天大学《材料综合》考研真题（含答案解析） 2015年北京航空航天大学《材料综合》考研真题（含答案解析） 2014年北京航空航天大学《材料综合》考研真题（含答案解析） 2013年北京航空航天大学《材料综合》考研真题（含答案解析） 2012年北京航空航天大学《材料综合》考研真题（含答案解析） 2011年北京航空航天大学《材料综合》考研真题（含答案解析） 2010年北京航空航天大学《材料综合》考研真题（含答案解析） 2009年北京航空航天大学《材料综合》考研真题（含答案解析） 2008年北京航空航天大学《材料综合》考研真题（含答案解析） 2007年北京航空航天大学《材料综合》考研真题（含答案解析） 2006年北京航空航天大学《材料综合》考研真题（含答案解析） 2005年北京航空航天大学《材料综合》考研真题（含答案解析） 2004年北京航空航天大学《材料综合》考研真题（含答案解析） 2003年北京航空航天大学《材料综合》考研真题（含答案解析） 2002年北京航空航天大学《材料综合》考研真题（含答案解析） 2000年北京航空航天大学《材料综合》考研真题（含答案解析） 1999年北京航空航天大学《材料综合》考研真题（含答案解析） 二、材料分析重点总结 三、金属学原理重点总结 四、金属学原理名称解析总结 五、物理化学复习总结 六、无机非金属材料复习总结 七、高分子物理复习总结 八、高分子化学复习总结 以下为截图及预览： 2015真题及答案 南阳理工学院2013-2014学年第2学期试卷（A卷） 课程：《数据结构》课程号：1504108130 考核方式：（闭卷）课程性质：专业必修课适用对象：12级软件工程专业 题号一二三四五总分复核人 满分20 20 10 30 20 100 得分 评卷人得分 一、选择题：（每题2 分，共20 分） 1.设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06， 07，08，09}，R={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03， 07>，<03，08>，<03，09>}，则数据结构A是（）。 A.线性结构 B.树型结构 C.物理结构 D.图型结构 2.栈和队列的共同特点是（）。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 3.在头指针为head的循环链表中，判断指针变量P指向尾结点的条件是（）。 A.p->next->next==head B.p->next==head C.p->next->next==NULL D.p->next==NULL 4.在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（）。 A.s->next=p+1; p->next=s; B.(*p).next=s; (*s).next=(*p).next; C.s->next=p->next; p->next=s->next; D.s->next=p->next; p->next=s; 5.数组Q[n]用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾 元素的位置，假定队列中元素的个数小于n，计算队列中元素个数的公式为 （）。 A.r-f B.(n+f-r)%n C.n+r-f D.（n+r-f)%n 6.设有数组A[0..7][0..9]，数组的每个元素长度为2字节，数组从内存首地址 1000开始顺序存放，当用以行为主存放时，元素A[5][8]的存储首地址为（）。 A.1116 B.1094 C.1138 D.1120 7.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上 所有元素)依次存放于一维数组B[1..n(n+1)/2]中，则在B中确定a ij（i 991数据结构与C语言程序设计考试大纲（2013版）2013年《数据结构与C语言程序设计》考试内容包括“数据结构”与“C语言程序设计”两 门课程的内容，各占比例50%，试卷满分为150分。 《数据结构》部分 指定参考书：《数据结构教程（第二版）》唐发根编著北京航空航天大学出版社 一、概述 1．数据的逻辑结构与存储结构的基本概念； 2．算法的定义、基本性质以及算法分析的基本概念，包括采用大 形式表示时间复杂度和空间复杂度。 二、线性表 1．线性关系、线性表的定义，线性表的基本操作； 2．线性表的顺序存储结构与链式存储结构(包括单(向)链表、循环链表和双向链表)的构造原理； 3．在以上两种存储结构的基础上对线性表实施的基本操作，包括顺序表的插入与删除、链表的建立、插入与删除、查找等操作对应的算法设计(含递归算法的设计)。 三、堆栈与队列 1．堆栈与队列的基本概念与基本操作； 2．堆栈与队列的顺序存储结构与链式存储结构的构造原理； 3．在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作的算法设计； 4．堆栈和队列在解决实际问题中应用。 四、树与二叉树 1．树与二叉树的基本概念，基本特征、名词术语； 2．完全二叉树与满二叉树的基本概念，二叉树的基本性质； 3．二叉树与树、树林之间的转换； 4．二叉树的顺序存储结构与二叉链表存储结构； 5．二叉树的前序遍历、中序遍历、后序遍历和按层次遍历，以及在二叉链表基础上各种遍历算法(重点为非递归算法)的设计与应用； 6．二叉排序树的基本概念、建立(插入)、查找与平均查找长度ASL的计算； 7．哈夫曼(Huffman)树的基本概念，哈夫曼树的构造与带权路径长度(WPL)的计算。 五、图 1．图的基本概念、名词术语； 2．图的邻接矩阵存储方法和邻接表(含逆邻接表)存储方法的构造原理及特点； 3．图的深度优先搜索与广度优先搜索； 4．最小(代价)生成树、最短路径、AOV网与拓扑排序以及AOE网与关键路径的基本概念与求解过程。 六、文件及查找 1．顺序查找法以及平均查找长度(ASL)的计算； 2．折半查找法以及平均查找长度(ASL)的计算，包括查找过程对应的“判定树”的构造； 3．B-树和B+树的基本概念，B-树的插入与查找； 4．散列(Hash)表的构造、散列函数的构造，散列冲突的基本概念、处理散列冲突的基本方法以 2019北航软件学院软件工程考研专业课991考试大纲 2019年“数据结构与C语言程序设计”考试内容包括“数据结构”与“C 语言程序设计”两门课程的内容，各占比例50%。试卷满分为150分。 “数据结构”部分 一、概述 1．数据的逻辑结构与存储结构的基本概念； 2．算法的定义、基本性质以及算法分析的基本概念，包括采用大 形式表示时间复杂度和空间复杂度。 二、线性表 1．线性关系、线性表的定义，线性表的基本操作； 2．线性表的顺序存储结构与链式存储结构(包括单(向)链表、循环链表和双向链表)的构造原理； 3．在以上两种存储结构的基础上对线性表实施的基本操作，包括顺序表的插入与删除、链表的建立、插入与删除、查找等操作对应的算法设计(含递归算法的设计)。 三、数组 1．一维数组和二维数组的存储； 2．矩阵的压缩存储的基本概念； 3．对称矩阵、对角矩阵以及三角矩阵的压缩存储。 四、堆栈与队列 1．堆栈与队列的基本概念与基本操作； 2．堆栈与队列的顺序存储结构与链式存储结构的构造原理； 3．在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作的算法设计； 4．堆栈和队列在解决实际问题中应用。 五、树与二叉树 1．树与二叉树的基本概念，基本特征、名词术语； 2．完全二叉树与满二叉树的基本概念，二叉树的基本性质及其应用； 3．二叉树的顺序存储结构与二叉链表存储结的基本原理； 4．二叉树的前序遍历、中序遍历、后序遍历和按层次遍历，重点是二叉树在以二叉链表作为存储结构基础上各种遍历算法(包括非递归算法)的设计与应 用； 5．二叉排序树的基本概念、建立(插入)、查找以及平均查找长度ASL的计算。 六、图 1．图的基本概念、名词术语； 2．图的邻接矩阵存储方法和邻接表(含逆邻接表)存储方法的构造原理及特点； 3．图的深度优先搜索与广度优先搜索； 4．最小(代价)生成树、最短路径、AOV网与拓扑排序的基本概念。 七、文件及查找 1．顺序查找法以及平均查找长度(ASL)的计算； 2．折半查找法以及平均查找长度(ASL)的计算，包括查找过程对应的“判定树” 的构造； 2013年''数据结构与C程序设计〃（代码991）试题 一、单项选择题（本题共20分，每小题各2分） 1.对于长度为n的线性表.建立其对应的做链表的时间复杂度为（）。 A.0（1）： B. O（log2n）：? O（n）： D? O（n2）。 2.一般情况下，在一个双向链表中插入一个新的链结点，（）o A.需要修改4个抬针域内的指针： B.需要修改3个指针域内的指针： C.需要修改2个指针域内的抬针：D?只需要修改1个指针域内的指针。 3.假设用单?个字母表示中缀表达式中的一个运算数（或称运算对&）?并利用堆栈产生中缀表达式对应的后缀表达式。对于中缀表达式A+B*（C/D-E）,十从左至右扫描到运算数E时，堆栈中的运算符依次是（）。（注：不包含表达式的分界符） A.+*/-： B. +*（/-： C? +*-：? +*（-o 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, 5Z 7对应叶结点的权值构造的哈夫曼（Huffman）树的深度为（）。 A. 6： B. 5： C? 4： D? 3。 &下列关于图的叙述中，错误的是（）0 A.根据图的定义，图中至少有一个顶点： B.根据图的定义.图中至少有一个顶点和一条边（弧）： C.具有n个顶点的无向图最女有n（n-l）/2条边； D.具有n个顶点的有向图最多有n（n-l）条边（弧）。 7.若在有向图G的拓扑序列中，顶点vi在顶点vj之前，则下列4种情形中不可能出现的是（）》 A.G中有弧 B.G中没有弧vvi,vj＞： 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-l： D? m/2° 10.若对序列（49, 38, 65, 97, 76, 13, 27f 49J进行快速排序，则第一趙排序结束（即确定了第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；27t 49z 76, 97, 65）。 二、填空题（本题共20分，每小题各2分） 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中有弧 一、填空题 1 逻辑结构、存储结构、算法 2 链式存储结构 3 O(1) 4 8 4+4+3+4条边，一共16个结点，叶节点为8，也可以画图试试 5 BFGDECA 先找根节点到A，A的左子树B，右子树FDGCE，右子树的根节点C，C的左子树FDG,右子树E，左子树的根节点D，D的左子树F，右子树G 6 n-m+1，对于任何一个有子节点的结点而言，其子节点有且只有一个子节点右子树为空，再加上根结点也是没有右子树的 7 子图 8 4次依次比较65，15，30，37 9 n(n-1)/2 0+1+……+n-1 10 1，5，11，15，19，77，59，48，26，61 二、简答题 1. 矩阵总元素数量是100x100=10000，非零元素数量为200，200/10000=0.02<5%，所以是稀疏矩阵 2. 书上的概念，没啥好说的 3. 起泡排序法，因为选择排序每趟排序只会交换两个元素，第二趟交换了三个元素的位置，而泡排序每趟排序将最大值像泡一样交换到数组最右边，同时每趟排序过程中，如果相邻元素不符合要求的顺序，会交换两个相邻元素，符合所给结果 4最大递归深度是n，最小递归深度是log2(n+1)取上界 三、综合题 1. 第四句，p->rlink->llink = p做过类似的题目，修改四个指针，前两句做的是修改p 的左右指针，没什么问题，后两句做的是修改q的右指针和原q的右结点的左指针，但第四句错了，因为q的右结点已经修改了 2. 又是一道似曾相识的题目，有两种大的情况，第7层只有叶节点，还有一种情况是第7层还有分支结点。10+2^6-1=73，(2^6=64,64-10=54,2^7-1=127 127+108(107)=235(234) 3. 从度的角度更好一点，将顶点编号为1，2……n，第1个顶点可以跟其他顶点有n 条边，除去顶点1，第2个顶点可以跟其他顶点有n-1条边，而第n-1个顶点可以跟第n个顶点有一条边，归纳总结为n+(n-1)+……+1=(n-1)xn/2 4. 90，30，50，10，80，20 || 90，80，50，10，30，20 || 90，80，50，10，30， 20 || 90，80，50，30，10，20 || 90，80，50，30，20，10 四、算法设计题 判断一个序列是否是有向图的拓扑序列，简单 typedef int vertype;//防止无法编译用，实际做题删除 typedef struct edge { int adjvex; struct edge*next; }ELink; 一填空题 1．已知一Ｎ＊Ｎ三角矩阵按行序为主序存放，下标从１开始,每个元素占l字节，则a[i][j]地址为当i≥j时，地址为i(i+1)/2+j-1；当i 北京航空航天大学2015年 硕士研究生入学考试试题科目代码：961 计算机综合 (共8页) 考生注意：所有答题务必书写在考场提供的答题纸上，写在本试题单上的答题一律无效（本题单不参与评卷） 一、 单项选择（15道小题，每题2分，共30分） 1、常见的几种总线仲裁方式中，对电路最为敏感的方式为（） A、链式查询 B、计数器查询方式 C、独立请求 D、中断查询 2、在常用的I/O控制方式中，要求主存与I/O设备之间有直接数据通路的方式为（） A、程序查询 B、程序中断 C、I/O通道 D、DMA 3、某机器字长为64位，内存容量为256MB，若按字编址，则其寻址空间为（） A、0～8M-1 B、0～16M-1 C、0～32M-1 D、0～64M-1 4、某机器字长为16位，内存按字编址，PC当前值为2000H,当读取一条双字长指令后PC的值为（） A、2000H B、2004H C、2008H D、200AH 5、某程序运行于一个由L1、L2两级cache以及主存组成的存储系统，L1 cache和L2 cache的命中率分别为50%和80%，则整个存储系统cache的命中率为（） A、65% B、80% C、90% D、95% 6、段式存储管理的逻辑地址空间为（） A、一维线性的 B、二维的 C、三维的 D、由操作系统决定的 7、下列选项中，操作系统提供给用户的接口为（） A、库函数 B、中断 C、系统调用 D、驱动程序 8、设某进程的页面走向为：5、4、3、2、4、3、1、4、3、2、1、5，系统中 有3页物理内存，请问采用LRU和FIFO淘汰算法的缺页次数分别为（） A、9和10 B、5和7 C、6和6 D、8和10 9、进程可以使用的最大地址空间受限于（） I.地址位数；II.物理内存大小；III.辅存大小 A、I B、I和II C、II和III D、I，II，III 10、有5个记录A,B,C,D,E存放在某磁盘的某磁道上，假定这个磁道划分为5块，每块存放一个记录，若磁盘旋转一周需要20ms，处理程序每读出一个记录后需要花费6ms进行处理，程序处理这些数据时磁盘照常旋转，按照（）顺序存放这5个记录可以使其按照A,B,C,D,E顺序处理这些记录的时间最少。 A、“A,B,C,E,D” B、“A,C,E,B,D” C、“A,D,E,C,B” D、“A,E,B,C,D” 11、以太网交换机按照自学算法建立转发表，它通过（）进行地址学习 A、ARP协议 B、帧中的源MAC地址和目的MAC地址 C、帧中的目的MAC地址 D、帧中的源MAC地址 12、以太网内某主机甲的IP地址为：211.71.136.23，子网掩码为：255.255.240.0，网关地址为：211.71.136.1，若主机甲向主机乙【IP地址为：211.71.130.25】发送一个IP分组，则（） A、该分组封装成帧后直接发送给乙，帧中目的MAC地址为网关MAC地址 B、该分组封装成帧后直接发送给乙，帧中目的MAC地址为主机乙的MAC 地址 C、该分组封装成帧后交由网关转发，帧中目的MAC地址为网关的MAC地址 D、该分组封装成帧后交由网关转发，帧中目的MAC地址为主机乙的MAC 地址 13、Internet中所有末端系统和路由器都必须实现（）协议以确定网络的连通。 A、IP B、UDP C、TCP D、OSPF 14、主机甲向主机乙发送一个（SYN=1，seq=1000）的TCP段，期望与主机乙 绝密★考试结束前 全国2014年4月高等教育自学考试 数据结构试题 课程代码：02331 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1.答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2.每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸” 的相应代码涂黑。错涂、多涂或未涂均无分。 1.与数据存储结构无关 ．．的概念是 A.栈 B.链表 C.顺序表 D.二叉链表 2.顺序表中有10个数据元素，若第一个元素的存储地址是1000，则最后一个元素地址是1036，第5个元素的地址是 A．1010 B.1016 C.1018 D.1019 3.设栈的初始状态为空，元素1、2、3、4、5、6依次入栈，得到的出栈序列是（2,4,3,6,5,1）,则栈的容量至少是 A.2 B.3 C.4 D..6 4.下列关于队列的叙述中,错误 ．．的是 A.队列是一种先进先出的线性表 B.队列是一种后进后出的线性表 C.循环队列中进行出队操作时要判断队列是否为空 1 D.在链队列中进行入队操作时要判断队列是否为满 5.对稀疏矩阵进行压缩存储的目的是 A.便于运算 B.节省存储空间 C.便于输入输出 D.降低时间复杂度 6.一棵二叉树的第7层上最多含有的结点数为 A.14 B.64 C.127 D.128 7.下列选项为完全二叉树的是 8.用邻接表表示n个顶点e条边的无向图,其边表结点的总数是 A. n×e B. e C. 2e D. n+e 9.无向图中所有顶点的度数之和与所有边数之比是 A.1/2 B.1 C.2 D.4 10.采用邻接矩阵存储图时,广度优先搜索遍历算法的时间复杂度为 A. O（n） B. O（n+e） C. O（n2） D. O（n3） 11.对序列（15,9,7,8,20,-1,4）进行排序,若一趟排序后的结果为（-1,15,9,7,8,20,4）,则采用的排序方法是 A.归并排序 B.快速排序 C.直接选择排序 D.冒泡排序 12.比较次数与待排序列初始状态无关的排序方法是 A.快速排序 B.冒泡排序 C.直接插入排序 D.直接选择排序 13.查找较快,且插入和删除操作也比较方便的查找方法是 A.分块查找 B.二分查找 C.顺序查找 D.折半查找 14.下列关于m阶B树的叙述中,错误 ．．的是 2 2008年北京航空航天大学961计算机专业综合考研试题 一、简答题（4’×5） 1、写出影响算法执行的时间效率的主要因素，并指出哪些因素与算法的时间效率直接相关。 2、已知元素的入栈顺序为A,B,C,D,E，在所有可能的出栈顺序中，写出第一个出栈的元素为C且第二个出栈的元素为D的所有组合。 3、根据单词（Nov, Jul, Sept, Feb, Oct, Mar, May, Jun, Jan, Dec, Aug, Apr）的第一个字母在字母表中的顺序建立二叉排序树，当每个元素的查找概率相等时，求查找成功时的平均查找长度ASL。 4、证明：具有n个顶点的无向图最多有n(n-1)/2条边。 5、有人说，折半查找的时间效率一定比顺序查找的时间效率高，你怎么看待这种说法？为什么？ 二、算法设计题（10’） 已知一非空完全二叉树存放于数组BT[0..n-1]中，请写出中序遍历该二叉树的非递归算法。 三、算法设计题（10’） 写出不带头结点的双向链表的插入排序算法。 四、简答题（4’×5） 1、数据传输控制方式有哪些？ 2、引入线程的目的是什么？ 3、P, V操作是如何实现互斥的的？ 4、什么是死锁？产生死锁的原因是什么？ 5、什么是文件系统？ 五、判断题（1’×10） 略。（基本上来自于历年真题） 六、解答题（10’） 某机器字长为16位，采用段页式存储管理算法，页内偏移为12位，段表和页表内容如下，给出4个虚拟地址（二进制形式），问哪个地址产生缺段中断，哪个地址产生缺页中断，哪些地址可以转换为物理地址，并求转换后的物理地址。（地址格式中段号占1位，段内页号占3位，页内偏移为12位，另外，在给出的页表中，物理块号占6位，最后又问该机器的最大物理内存是多少（答案：256 KB）。） 七、简答题（4’×4） 1、利用等值演算的方法，写出求命题逻辑公式的主范式的方法。 2、谓词逻辑中的永假式、可满足式、重言式、永真式之间的关系是什 北航2015年考研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．2(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，因此，合适的散列函数应该为H(k)=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 《数据结构》试卷（C卷） 一、单项选择题 1. 空串与空格字符组成的串的区别在于（B ）。 A.没有区别 B.两串的长度不相等 C.两串的长度相等 D.两串包含的字符不相同 2. 一个子串在包含它的主串中的位置是指（ D ）。 A.子串的最后那个字符在主串中的位置 B.子串的最后那个字符在主串中首次出现的位置 C.子串的第一个字符在主串中的位置 D.子串的第一个字符在主串中首次出现的位置 3. 下面的说法中，只有（ C ）是正确的。 A.字符串的长度是指串中包含的字母的个数 B.字符串的长度是指串中包含的不同字符的个数 C.若T包含在S中，则T一定是S的一个子串 D.一个字符串不能说是其自身的一个子串 4. 两个字符串相等的条件是（ D ）。 A.两串的长度相等 B.两串包含的字符相同 C.两串的长度相等，并且两串包含的字符相同 D.两串的长度相等，并且对应位置上的字符相同 5. 若SUBSTR（S，i，k）表示求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（ B ）。 A. “ijing” B. “jing＆” C. “ingNa” D. “ing＆N” 6. 若INDEX（S，T）表示求T在S中的位置的操作，则对于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（ C ）。 A.2 B.3 C.4 D.5 7. 若REPLACE（S，S1，S2）表示用字符串S2替换字符串S中的子串S1的操作，则对于 S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（ D ）。 A. “Nanjing＆Shanghai” B. “Nanjing＆Nanjing” C. “ShanghaiNanjing” D. “Shanghai＆Nanjing” 8. 在长度为n的字符串S的第i个位置插入另外一个字符串，i的合法值应该是（ C ）。 A.i＞0 B. i≤n C.1≤i≤n D.1≤i≤n+1 9. 字符串采用结点大小为1的链表作为其存储结构，是指（D ）。 A.链表的长度为1 B.链表中只存放1个字符 C.链表的每个链结点的数据域中不仅只存放了一个字符 D.链表的每个链结点的数据域中只存放了一个字符 10. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（C ）个。 A. 4 B. 5 C. 6 D. 7 11. 假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（ B ）个。 A. 15 B. 16 C. 17 D. 47 12. 假定一棵三叉树的结点数为50，则它的最小高度为（ C ）。 A. 3 B. 4 C. 5 D. 6 13. 在一棵二叉树上第4层的结点数最多为（ D ）。 A. 2 B. 4 C. 6 D. 8 14. 用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]若有左孩子，其左孩子的编号为结点（B ）。 A. R[2i+1] B. R[2i] C. R[i/2] D. R[2i-1] 15. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ D ）。 A. 24 B. 48 C. 72 D. 53 16. 线索二叉树是一种（ C ）结构。 A. 逻辑 B. 逻辑和存储 C. 物理 D. 线性 17. 线索二叉树中，结点p没有左子树的充要条件是（ B ）。 复习题集 一判断题 （）1. 在决定选取何种存储结构时，一般不考虑各结点的值如何。 （）2. 抽象数据类型与计算机内部表示和实现无关。 （）3. 线性表采用链式存储结构时，结点和结点内部的存储空间可以是不连续的。 （）4. 链表的每个结点中都恰好包含一个指针。 （）5.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（）6. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （）7. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （）8. 线性表在物理存储空间中也一定是连续的。 （）9. 顺序存储方式只能用于存储线性结构。 （）10.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （）11.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 （）12.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （）13.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （）14.二叉树的度为2。 （）15.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （）16.二叉树中每个结点的两棵子树的高度差等于1。 （）17.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （）18.具有12个结点的完全二叉树有5个度为2的结点。 （）19.二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。 （）20.在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。 （）21.计算机处理的对象可以分为数据和非数据两大类。 （）22.数据的逻辑结构与各数据元素在计算机中如何存储有关。 （）23.算法必须用程序语言来书写。 （）24.判断某个算法是否容易阅读是算法分析的任务之一。 （）25.顺序表是一种有序的线性表。 （）26.分配给顺序表的内存单元地址必须是连续的。 （）27.栈和队列具有相同的逻辑特性。 （）28.树形结构中每个结点至多有一个前驱。 （）29.在树形结构中，处于同一层上的各结点之间都存在兄弟关系。 （）30.如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。 （）31.如果表示图的邻接矩阵是对称矩阵，则该图一定是有向图。 （）32.顺序查找方法只能在顺序存储结构上进行。 数字电子技术基础(A卷)（无答案） 一．解答下列问题（共40分，每小题5分） 1.十进制数 X = 117，其ASCII码表示为：。 在8位机器中，[X]补 = ，[-X]补 = 。 2.已知逻辑函数：() F A C BC A B CD =+++，直接用反演规则写出其反函数和对偶函数。 3.用卡诺图化简逻辑函数∑∑ + =) 15 , 1013 ,8,2,1( ) 14 , 12 ,7,6,0(4 4d m F 4.用OC 门驱动发光二极管电路如图，若V F=2V，I F=20mA，试完善电路并计算电阻R=? 5.画出图示电路的输出波形 A B C Y A B & E n 6. 主-从JK 触发器，已知CP 、J 、K 信号波形如图示，画出输出波形（初始状态为0）。 7. 分析函数 F AB ABC =+ 所组成的电路存在何种险象。 8. 图示电路中触发器： 建立时间 t su = 20ns ， 保持时间 t h = 5ns ， 传输迟延时间t pdcp-Q,/Q = 30ns， 门G迟延t pd G= 10ns， 时钟脉冲F max = ? 二．逻辑函数(,,) =++（本题共14分，每小题7分） F A B C ABC BC AC 1.用3-8译码器及适当门电路实现。 2.用“四选一”数据选择器及适当门电路实现。 三．分析下列电路所实现的逻辑功能（本题共16分，每小题8分）Array 1.由2-5-10进制异步计数器构成的电路。 2. 由74LS163构成计数器电路。 四． 某同步时序系统的原始状态表如图示（本题15分） 1. 用隐含表法化简； 2. 自然序编码； 3. 用JK 触发器及适当门设计电路； 4. 检查是否可以自启动。 数字电子技术基础（A 卷）2015年北京航空航天大学飞行器设计历年真题,心得分享,考研大纲,考研笔记,复试真题
1999-2016年北京航空航天大学911材料综合考研真题及答案解析 汇编
2014(1)数据结构-A-试题
北航考研991考试大纲
2019北航软件学院软件工程考研专业课991考试大纲
北航数据结构与程序设计真题-2013北航991真题与答案
北航数据结构与程序设计真题 2013年北航991真题及答案
北航991真题2012年答案
2014年数据结构补考试题
北航2015年961真题
全国2014年4月自考数据结构真题
北京航空航天大学961计算机专业综合考研试题(历年)
北航2015年考研991科目的答案
2014《数据结构》试卷( C 卷)
武汉理工大学数据结构2014复习题
北航数电2015试题及答案
相关文档
- 2021年北京航空航天大学991数据结构与C语言程序设计考研精品资料之历年真题汇编及考研大纲
- 2015-2016北航计算机系考研真题(961)
- 2019北航软件学院软件工程考研专业课991考试大纲
- 北航数据结构与程序设计真题2013年北航991真题及答案
- 2017-2018年北航软件学院软件工程991数据结构与C语言程序设计考研大纲重难点
- 北航数据结构程序设计真题 2013年北航991真题及答案
- 北航数据结构与程序设计真题-2013年北航991真题及答案
- 2019北航991软件工程初试经验
- 北航991真题2012年答案
- 2014年北航921真题(清晰扫描版)
- 北航计算机学院2019考研961真题
- 北航数据结构和程序设计真题2014北航991真题和答案解析
- 北航考研991考试大纲
- 北航物理实验绪论考试真题4套题含答案(供参考)
- 北航数据结构与程序设计真题2013年北航991真题及答案
- 北航线性系统理论真题及答案
- 北航考研真题汇总 资料查询汇总
- 北航数据结构与程序设计真题-2013年北航991真题及答案
- 北航数据结构与程序设计真题 2013年北航991真题及答案
- 北航软院2012年数据结构与C语言程序设计试题(原版)