北航数据结构与程序设计真题-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的拓扑序列是_________。

北京航空航天大学北海学院课程考试试卷答案要点及评分细则课程名称：《数据结构》考试班级：软件与信息工程学院卷别：_A 命题教师签名： 年 月 日1、 单项选择题（本题共15小题，每小题2分，共30分）123456789101112131415C AD B C B D D C A D C A C B2、 判断正误题(本题共10小题，每小题1分，共10分)1.X,2.X,3.√,4.√,5.X,6.X,7.X,8.√,9.X, 10.√3、 填空题(本题共6小题10个空，每空2分，共20分)(1) O(n)(2) O(n)(3) O(1)(4) 求模式串在主串中首次出现的位置的运算，即求主串中左起第一个与模 式串相等的子串的首字符在主串中的位置。

(5) (Q.rear-Q.front+Max)% Max(6) 4(7) n2log n，n3, 2n(8) n→∞时n3/(n2log n)→∞， 2n/(n3)→∞(9) 为空(10) 出队四、简答题：(本题共4小题，1，2小题各4分，3，4小题各6分，共20分)1.1) 确定性指描述无二义性，相同条件下执行的路线和结果都是唯一的。

2) 输入可以有0至多个从算法外部接受的输入。

2. 该缓冲区应该采用队列结构。

其主要特点是先进先出。

3. 顺序表：O(n)，单循环链表：O(n)，顺序栈：O(1)，循环队列：O(1)，链栈：O(1)，链队列：O(1)。

4. 优点：①随机访问，简捷；②只存数据，局部空间利用率高；缺点：①逻辑关系靠地址表达，插入删除造成大量元素移动；②要求连续存储空间，固定长度，不便扩充；③须预先按最大可能分配，但闲置多,按整体看空间利用率低。

五、设计题(本题共3小题，第1小题2分，第2小题8分，第3小题10分，共20 分)1. typedef struct node{datatype data;struct node *next;}node;2.(1). s->next = head->next; head->next = s;(2). s->next = head; head = s;3. 答案1：采用尾指针表示、带头结点的单循环链表。

已今， 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); }。

2013年''数据结构与C程序设计〃（代码991）试题一、单项选择题（本题共20分，每小题各2分）1.对于长度为n的线性表，建立其对应的収链表的时间复朵度为（）。

A.0（1）： B・ O（log2n）：・ O（n）： D・ O（n2）n2.一般情况下，在一个双向链表中插入一个新的链结点，（）。

A.需耍修改4个抬针域内的指针：B・需要修改3个指针域内的抬针：C.需要修改2个抬针域内的抬针：D.只需要修改1个指针域内的抬针。

3.假设用单个字母表示中缀表达式中的一个运算数（或称运算对彖）.并利用堆栈产生中缀表达式对应的后缀表达式。

对于中缀表达式A+B^C/D-E）,十从左至右扫描到运算数E时，堆栈中的运算符依次是（）。

（注：不包含表达式的分界符）A.+*/-：B. +*（/-： C・ +*-：・ +*（-o4.若某二叉排序树的前序遍历序列为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。

&下列关于图的叙述中，错误的是（）0A.根据图的定义，图中至少有一个顶点：B.根据图的定义.图中至少有一个顶点和一条边（弧）：C.具有n个顶点的无向图最多有n&#61620;（n-l）/2条边:D.具有n个顶点的有向图最多有n&#61620;（n-l）条边（弧）。

7.若在有向图G的拓扑序列中.顶点W在顶点vj之前，则下列4种情形中不可能岀现的是（）。

A.G 中有弧vvi,vj＞：B.G 中没有3ft＜vi r vj＞；c. G中有一条从顶点W到顶点vj的路径：D・G中有一条从顶点vj到顶点vi的路径。

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 选C 前三步操作相同，主要看第四步，先分析前三步做了什么，一二的操作是修改p的前后节点，而p是需要插入的节点，所以还要修改的是q和原本q的后面一个节点2 选D，队列为空的情况3 选A，排除带括号的，括号外的为x4 选D，8层的完全二叉树，第7层为2^6个节点，64个节点，非叶节点为54个，第8层为108个节点，前7层为2^7-1个，127个，共127+108=235，一个有几种情况？3种，7层的完全二叉树，一种234，快速方法，不用计算，因为肯定多于70多，又必是奇数5 选B，送分题6 选D，连通可能有回路，一般无向图不讨论拓扑排序7 选A 0 99中进行查找49，24，11，5，2，0算出了六次，一共七次，用满二叉树来计算，一个6层的满二叉树为63个元素，7层的是127个元素8 选C9 选D，插入排序是不是？10 选A，倒数第二个找到之后，最后一个数不需要进行排序二简答题1 见笔记本2 递归调用自身的，堆栈3 初始点，遍历方法，边的顺序4 不细讲，算一下，选择排序是10000 + ···+9991，快速排序差不多为n*Logn，即10000*log10000，堆是log10000三综合题1 ABCFED | ABFCED从A开始，没有指向A的边，把图画出来即可2 先从层序开始，根节点为A，在中序中C为A的左子树序列，DFBE是右子树序列。

再看A的左子树DFBE在层序中B为第一个，所以B为子树的根节点，再回到中序，DF 在B的前面，所以为左子树，E为右子树。

再分析子树DF，DF在层序中D为第一个，所以D为根节点，而中序中F在D的右边所以F为D的右孩子3 17填在位置5，27填在位置04 求数组的最大值，可以写得详细点四、算法设计题利用堆栈结构，我写是四不像，没有先后顺序，可以进行修改，改成前序typedef int ElementType;//多余的一行，但能使程序可以编译typedef struct BinaryNode{struct BinaryNode*lchild;ElementType data;struct BinaryNode*rchild;}Node,*BinaryTree;Node*searchBroNode(BinaryTree T,Node*q) {Node*Stack[100];int top = -1;Stack[++top] = T;while(top != -1){Node*current = Stack[top--];if(current->lchild == q)return current->rchild;elseif(current->lchild)Stack[++top] = current->lchild;if(current->rchild != q)return current->lchild;elseif(current->rchild)Stack[++top] = current->rchild;}return NULL;}五、单项选择题1.选B2 选C，由于i会导致全部都变为double3 选A4 选C，A必须有输入项，B规定位数没用，输入项必须是变量，或者说地址5 选D，可以这么想，循环继续进行下去的条件是s不等于100且k小于3，则结束条件就是s等于100或者k大于等于36 选A，j++是先执行完这条语句然后再j++，所以循环结束j大于等于4，j++就是57 选B，D还有什么反例？return8 选B9 选D10 选C，“123456”可以看成const char *11 选C，A是比较地址，B是判断两个是否相等12 选B，第一个都是参数的数量，与参数名无关，第二个参数是字符串数组，标准形式是char*argv[ ]，等同于char**13 选A，所有变量都是传递值，但是传地址是传什么？传地址也是传地址的值，所以说传地址实际上也是传值14 选D15 选C，这是一个指针数组，数组存放的是int类型的指针，需要区别的是D，D是数组指针，所以选C，原因在于[ ]的优先级高于*16 选D，a三个元素分别的值是{1001，20}，{1002，19}，{1003，21}，只有第2个结构体的age是1002，所以是B，D，B是1001，D是正确答案17 选C，强制类型转换需要带括号18 选D，了解宏定义是什么，宏定义再预处理阶段做处理19 选A，C最完善，但正常不需要这样20 选B，指向结尾所以是a，同时是可读写所以是a+六、填空题1 1，1跟结合性有关，b=1，a=0，运算顺序，b--，重点a+b其中b已经减1了，然后是<=，!=，最后是||2 5 来看一下f是在，干什么，大致跟长度有关，最后s指向字符串开头，p指向’\0’，用一个字符串长度为1的字符串作例子，则返回1，所以返回字符串长度3 11 7 i=（2*M）=>> i=(2*N+1) =>> i=(2*5+1)，所以i=11，j=(1+1*M) =>> j=(1+1*5+1) =>> j=74 123456 这道题的疑问就是有没有空格七、程序设计题#include <stdio.h>int main(int argc,char *argv[]){int a,n;scanf("%d %d",&a,&n);int sum = 0;int temp = 0;int i;for(i = 0;i < n;i++){temp = temp * 10 + a;sum += temp;}printf("%d\n",sum);return 0;}八、程序设计题。

北京航空航天大学程序设计与数据结构试题(2002年)一、简答题1. “数据结构”课程是计算机专业的基础课还是专业课，或者专业基础课？(2’)2. 学习“数据结构”课程需要哪些课程作为它的基础(举例两门课程)？若没有这些知识，对学习“数据结构”课程可能会产生哪些影响？请举例说明(不超过100字)。

(4’)3. “数据结构”课程将为那些课程学习奠定必要的基础？请举例说明哪些课程(举例两门课程)用到了“数据结构”课程的哪些知识(不超过100字)。

(4’)二、(5’)请推导出结论：具有n0个叶结点的哈夫曼树(Huffman)的分支总数为2(n0-1)。

三、单项选择题(2’x15)1. 线性链表中各链接点之间的地址__________。

A)必须连续B)部分地址必须连续C)不一定连续D)连续与否无所谓2. 在非空线性链表中由p所指的链接点后面插入一个由q所致的链接点的过程是依次执行动作__________。

A) link(q)←p; link(p)←q; B) link(q)←link(p); link(p)←q;C) link(q)←link(p); p←q; D) link(p)←q; link(q)←p;3. 在非空双向循环链表中由q所指的那个链接点前插入一个p指的链接点的动作对应的语句依次为rlink(p)←q, llink(p)←llink(q), llink(q)←p, __________。

(空白处为一条赋值语句)A) rlink(q)←p B) rlink(llink(q))←pC) rlink(llink(p))←p D) rlink(rlink(p))←p4. 在初始为空的堆栈中依次插入元素f，e，d，c，b，a以后，连续进行了三次删除操作，此时栈顶元素是__________。

A) c B) d C) b D) e5. 若某堆栈的输入序列为1，2，3，……，n，输出序列的第1个元素为n，则第i个输出元素为__________。

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&#61620;(n-1)/2条边；D．具有n个顶点的有向图最多有n&#61620;(n-1)条边(弧)。

7．若在有向图G的拓扑序列中，顶点vi在顶点vj之前，则下列4种情形中不可能出现的是( )。

A．G中有弧<vi,vj>；B．G中没有弧<vi,vj>；C．G中有一条从顶点vi到顶点vj的路径；D．G中有一条从顶点vj到顶点vi的路径。

991“数据结构与C语言程序设计”考试大纲（2019版）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)的计算，包括查找过程对应的“判定树”的构造；3．散列(Hash)表的构造、散列函数的构造，散列冲突的基本概念、处理散列冲突的基本方法以及散列表的查找和平均查找长度的计算。

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&#61620;(n-1)/2条边；D．具有n个顶点的有向图最多有n&#61620;(n-1)条边(弧)。

7．若在有向图G的拓扑序列中，顶点vi在顶点vj之前，则下列4种情形中不可能出现的是( )。

A．G中有弧<vi,vj>；B．G中没有弧<vi,vj>；C．G中有一条从顶点vi到顶点vj的路径；D．G中有一条从顶点vj到顶点vi的路径。