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

浙江理工大学2013年硕士学位研究生招生入学考试试题考试科目：数据结构代码：991（请考生在答题纸上答题，在此试题纸上答题无效）一、单选题（在每小题的四个备选答案中选出一个正确答案。

每小题2分，共20分。

）1.链表不具备的特点是______。

A. 可随机访问任一结点B. 插入删除不需要移动元素C. 不必事先估计存储空间D. 所需空间与其长度成正比2.设线性表有n个元素，以下算法中，在顺序表上实现比在链表上实现效率更高。

A. 交换第0个元素与第1个元素的值B. 顺序输出这n个元素的值C. 输出第i(0≤i≤n-1)个元素值D. 输出与给定值x相等的元素在线性表中的序号3.设输入序列为a、b、c、d，则借助栈所得到的输出序列不可能是_________。

A. a、b、c、dB. d、c、b、aC. a、c、d、bD. d、a、b、c4.为解决计算机主机与打印机之间的速度不匹配问题，通常设计一个打印数据缓冲区，主机将要输出的数据依次写入到该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是。

A. 栈B. 队列C. 树D. 图5.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有个空指针域。

A. 2mB. 4mC. 2m+1D. 2m -16.二叉树若用顺序存储结构表示，则下列四种运算中最容易实现。

A. 先序遍历二叉树B. 层次遍历二叉树C. 中序遍历二叉树D. 后序遍历二叉树7.以下关于有向图的说法正确的是。

A. 强连通图是任何顶点到其他所有顶点都有边B. 完全有向图一定是强连通图C. 有向图中某顶点的入度等于出度D. 有向图边集的子集和顶点集的子集可构成原有向图的子图8.若一个有向图中的顶点不能排成一个拓扑结构序列，则可断定该有向图____________。

A. 含有多个出度为0的顶点B. 是个强连通图C. 含有多个入度为0的顶点D. 含有顶点数目大于1的强连通分量9.顺序查找法适合于存储结构为的线性表。

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．在二叉排序树中进行查找的平均时间效率主要与下列因素之一有关，该因素是。

北京航空航天大学程序设计与数据结构专业考研真题(2000年)一、选择题(2’x10)1.在非空双向循环链表中q所指的结点前插入一个由p所指的链接点的过程依次为：rlink(p)←q；llink(p)←llink(q)；llink(q)←p；_________。

(A)rlink(q)←p(B)rlink(llink(q))←p(C)rlink(llink(p))←p(D)rlink(rlink(p))←p2.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B(1)1:2n n+⎡⎤⎢⎥⎣⎦中，则在B中确定a ij(i<j)的位置k的关系为_________。

(A)(1)2i ij*-+(B)(1)2j ji*-+(C)(1)2i ij*++(D)(1)2j ji*++3.某堆栈的输入序列为a，b，c，d，下面的四个序列中，_________不可能是它的输出序列。

(A)a，c，b，d(B)b，c，d，a(C)c，d，b，a(D)d，c，a，b4.深度为h的满m叉数的第k层有_________个结点。

(1≤k≤h)(A)m k-1(B)m k-1 (C)m h-1(D)m h-15.具有10个叶结点的二叉树中有_________个度为2的结点。

(A)8 (B)9 (C)10 (D)116.要连通具有n个顶点的有向图，至少需要_________条边。

(A)n-1 (B)n(C)n+1 (D)2n7.已知有向图G=(V，E)，其中V={v1，v2，v3，v4，v5，v6，v7}，E={<v1，v2>，<v1，v3>，<v1，v4>，<v2，v5>，<v3，v5>，<v3，v6>，<v4，v6>，<v5，v7>，<v6，v7>}，G的拓扑序列是_________。

已今， 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函数中计算累加和。

一、单项选择题1 选C2 选A3 选D4 选B，通过前序中的50来排除AC，同时这是一个排序树，可以构建出其结构5 选C6 选B7 选D8 选A，不要被顺序表所迷惑，顺序表不一定时有序的9 不在考点里了10选D二、顺序表1 顺序2 O(m)3 log2(k)+1取上界，向上取整，2^(h-2)< k <= 2^(h-1)4 234或2355 2(n+1)6 有向图中不含有回路7 看公式8 B树不考了10 9次4+3+2=9次三、综合题1 多个堆栈可以节约存储空间，可以充分利用全部的存储空间，但是某个堆栈满了之后移动空间麻烦，（2）操作方面，但单个堆栈难以确定分配的空间大小，会出现溢出或存储无法充分利用的情况（3）一般不会出现堆栈溢出的情况，且不需要预先分配空间，但需要用到了指针，需要额外的存储空间2 T->lchild==NULL&&T->rchild==NULL，T->lchild，T->rchild，显然这是个前序遍历，注意题目说明，输出叶结点的数据信息，所以if是判断是否为叶节点，其实还可以改进算法3 虽说不在考点，建议还是看看4 （1）11/0.61=18，除以18（2）四、算法设计题void sort(int A[],int n){int i,j;for(i = 1;i <= n/2; i++){int minIndex=i,maxIndex=i;for(j = i+1; j < n - i + 2; j++)if(A[minIndex] > A[j])minIndex = j;if(A[maxIndex] < A[j])maxIndex = j;}//交换值int temp = A[i];A[i] = A[minIndex];A[minIndex] = temp;temp = A[n-i+1];A[n-i+1] = A[maxIndex];A[maxIndex] = temp;}}五、填空题1 break a/q2 a[1]>=a[0]，FUNC2(a,n-1)，这是一个简单的题目，但算法写的太烂了，可以改进3 a[i][i] a[i][N-1-i]4 i>0 n%10+’0’5 ch=ch-30 ch=ch-267 strlen(p)-1 p<q8 ch&0x189 4 &number10 argv[1]，”rb” argv[2]，”wb”六、简答题1 （1）参数传递（2）return语句（3）全局变量2 与整数进行加减，指针相减，比较3 （1）所有成员共享同一块存储空间，占用空间为占用空间最大的，（2）同一时间只有一个（3）在定义的时候不能初始化4 包含头文件，定义文件指针，打开文件，进行读写操作，关闭文件七、程序设计题#include <stdio.h>int main(int argc,char *argv[]){int n = 100;int a[100];int i;//输入数组for(i = 0; i < n; i++)scanf("%d",a+i);//寻找最小的元素int min = 0;int*p = a;for(i = 0; i < n; i++)if(*(p+min)>*(p+i))min = i;//删除最小的元素for(i = min; i < n - 1; i++)*(p+i) = *(p+i+1);n--;return 0;}八、程序设计题char*maxword(char*s,char*t) {char*p,*q;p = s,q = t;int maxlen = 0;int maxbegin = -1;int i,j,k;int sword[80]={0};int tword[80]={0};int swordlen[80];int twordlen[80];int snum = 0,tnum = 0;for(i = 0; p[i]; i++){if(p[i] == ' '){sword[++snum] = i + 1;swordlen[snum-1] = sword[snum] - sword[snum-1] - 1;}}swordlen[snum] = i - sword[snum];snum++;for(i = 0; q[i]; i++){if(q[i] == ' '){tword[++tnum] = i + 1;twordlen[tnum-1] = tword[tnum] - tword[tnum-1] - 1;}}twordlen[tnum] = i -tword[tnum];tnum++;for(i = 0; i < snum; i++)printf("%d ",swordlen[i]);printf("\n");for(i = 0; i < snum; i++)printf("%d ",sword[i]);for(i = 0;i < snum; i++)for(j = 0; j < tnum; j++){if(swordlen[i] == twordlen[j] && maxlen < swordlen[i]){for(k = 0; k < swordlen[i]; k++){if(p[sword[i]+k] != q[tword[j]+k])break;}if(k == swordlen[i]){maxlen = k;maxbegin = sword[i];}}}printf("begin:%s,%d",(p+maxbegin),maxlen); }。

北京航空航天大学2014年硕士研究生入学考试
“数据结构与C语言程序设计”(科目代码:991)试题
一、单项选择题（本题共20 分，每小题各2 分）
1、在非空线性链表中由p所指的链结点后面插入一个由q所指的链结点的过程是依次执行动作。

A. Link(q) ←p; Link(p) ←q;
B. Link(q) ←Link(p); Link(p) ←q;
C. Link(q) ←Link(p); Link(p) ←q;
D. Link(p) ←q; Link(q) ←p;
2、线性链表中各链结点之间的地址。

A. 必须连续
B.部分地址必须连续
C. 不一定连续
D.连续与否无所谓
3、一个顺序表所占用的存储空间大小与无关。

A. 表的长度
B.元素的存放顺序
C. 元素的类型
D.元素中个字段的类型
4、一般情况下，在一个双向链表中插入一个新的链结点，
A.需要修改3个指针域内的指针
B.只需要修改1个指针域内的指针
C.需要修改4个指针域内的指针
D.需要修改2个指针域内的指针。

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网与关键路径的基本概念与求解过程。

北航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&#61620;(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->rchild3．（由于图表显示限制，此题答案见指定教材(《数据结构教程第二版》(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<n-i+1;j++){ if(A[j]<A[min])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-=266．*(s+i) t++ 7．strlen(p)-1 p<q 8．ch & 24 9．4 &number 10．argv[1],“rb”argv[2], “wb”六、简答题1．答：通常有下列三种方式：(1)参数传递方式：函数调用时根据实参传递给形参内容的不同又分为值传递与地址传递两种。