下载文档原格式
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网与关键路径的基本概念与求解过程。
浙江理工大学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.顺序查找法适合于存储结构为的线性表。
北京航空航天大学程序设计与数据结构专业考研真题(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的拓扑序列是_________。
北京航空航天大学《C语言程序设计》课程考试试卷注意事项： 1、本试卷满分100分；考试时间：90分钟；考试形式：开卷2、请将答案一律写在答题纸上，试卷上作答无效3、考试结束后，考生将试卷及答题纸一并交回4、请将条形码贴在答题纸的指定位置学习中心______________姓名____________学号____________一、单项选择题（本大题共10小题，每小题2分，共20分）1、设有定义语句“char s[]=”123”;”，则表达式“s[3]”的值是______。
（）A．' 1' B．'3'C．'\0' D．存在语法错误2、凡是函数中未指定存储类别的局部变量，其隐含的存储类别为______。
（）A．自动(auto) B．静态(static)C．外部(extern) D．寄存器(register)3、已知：char w; int x; float y; double z;，则表达式w*x+z-y结果的类型是______。
（）A．float B．charC．int D．double4、当声明一个结构变量时，系统分配给它的内存是______。
（）A．各成员所需内存量的总和B．结构中第一个成员所需内存量C．成员中占内存量最大者所需的容量D．结构中最后一个成员所需内存量5、C语言中的简单数据类型包括______。
（）A．整型、实型、逻辑型B．整型、实型、字符型C．整型、字符型、逻辑型D．整型、实型、逻辑型、字符型6、合法的数组说明语句是______。
（）A．int a[]="string"；B．int a[]={0,1,2,3,4,5}；C．char a="string"；D．char a[5]={'0','1','2','3','4','5,}；7、定义int i=1;，执行语句while(i++<5);后，i的值为______。
已今， 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（n-l）/2条边:D.具有n个顶点的有向图最多有n（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的路径。
一．单项选择题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;}八、程序设计题。
一、简答题（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、谓词逻辑中的永假式、可满足式、重言式、永真式之间的关系是什么？3、之间的真值关系是什么？4、如何判断公式中某个变元是约束变元还是自由变元？举例说明一个变元可以既是约束的又是自由的。
北京航空航天大学2012年硕士研究生入学考试试题“数据结构与C语言程序设计”（科目代码：991）一、填空题(本题共20分，每小题各2分)1．从总体上说，“数据结构”课程主要研究三个方面的内容。
2．若对某线性表最常用的操作是在表中插入元素或者删除表中元素，则对于顺序存储结构和链式存储结构这两种存储结构而言，线性表应该采用。
3．在长度为n的非空队列中进行插入或者删除操作的时间复杂度用大O符号表示为。
4．若一棵度为4的树中度为1、2、3和4的结点个数分别为4、2、1和1，则该树中叶结点的个数为。
5．若某二叉树的中序遍历序列为B,A,F,D,G,C,E，按层次遍历序列为A,B,C,D,E,F,G，则该二叉树的后序遍历序列为。
6．将一棵结点总数为n、且具有m个叶结点的树转换为一棵二叉树以后，该二叉树中右子树为空的结点有个。
7．对于图G=(V,E) 与G^=(V^,E^)，若有V^包含于V，E^包含于E，则称G^是G的。
8．在顺序表(6,15,30,37,65,68,70,72,89,99)中采用折半查找法查找元素37，与表中进行过比较的元素依次是。
9．若已知n个关键字值具有相同的散列函数值，并且采用线性探测再散列法处理冲突，那么，将这n个关键字值全部散列到初始为空的地址空间中，发生散列冲突的次数是。
10．若长度为n的序列K=(k1,k2,…,kn)当且仅当满足ki≤k2i并且ki≤k2i+1(1≤i≤n/2)时，则称该序列为一个小顶堆积(Heap)。
根据该定义，序列(26,5,77,1,61,11,59,48,15,19)对应的小顶堆积是。
二、简答题(本题共20分，每小题各5分)1．如果一个具有100个顶点、200条边的有向图采用邻接矩阵存储，该邻接矩阵是否是稀疏矩阵？为什么？（这里我们假设：当矩阵中非零元素的数目小于整个矩阵总元素的数目的5%时认为该矩阵为稀疏矩阵）2．一般情况下，建立散列表时难以避免出现散列冲突，常用处理散列冲突的方法之一是开放定址法，该方法的基本思想是什么？3．若对序列(2,12,16,88,5,10)按值从小到大进行排序，前三趟排序的结果分别为：第1趟排序的结果：(2,12,16,5,10,88)第2趟排序的结果：(2,12,5,10,16,88)第3趟排序的结果：(2,5,10,12,16,88)请问：该结果是采用了选择排序法还是采用了(起)泡排序法得到的？为什么？4．快速排序法的排序过程是递归的。
北京航空航天大学程序设计与数据结构试题(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(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的路径。
2013年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：第1～40小题，每小题2分，共80分。
下列每题给出的四个选项中，只有一个选项最符合试题要求。
1．已知两个长度分别为m 和n 的升序链表，若将它们合并为一个长度为m +n 的降序链表，则最坏情况下的时间复杂度是（ ）。
A ．()O n B ．()O m n ⨯ C ．(min(,))O m n D ．(max(,))O m n 2．一个栈的入栈序列为1,2,3,,n ，其出栈序列是123,,,,n p p p p 。
若23p =，则3p 可能取值的个数是（ ）。
A ．3n -B ．2n -C ．1n -D ．无法确定3．若将关键字1，2，3，4，5，6，7依次插入到初始为空的平衡二叉树T 中，则T 中平衡因子为0的分支结点的个数是（ ）。
A ．0B ．1C ．2D ．34．已知三叉树T 中6个叶结点的权分别是2，3，4，5，6，7，T 的带权（外部）路径长度最小是（ ）。
A ．27B ．46C ．54D ．565．若X 是后序线索二叉树中的叶结点，且X 存在左兄弟结点Y ，则X 的右线索指向的是（ ）。
A ．X 的父结点B ．以Y 为根的子树的最左下结点C ．X 的左兄弟结点YD ．以Y 为根的子树的最右下结点6．在任意一棵非空二叉排序树T 1中，删除某结点v 之后形成二叉排序树T 2，再将v 插入T 2形成二叉排序树T 3。
下列关于T 1与T 3的叙述中，正确的是（ ）。
I ．若v 是T 1的叶结点，则T 1与T 3不同II ． 若v 是T 1的叶结点，则T 1与T 3相同III ．若v 不是T 1的叶结点，则T 1与T 3不同IV ．若v 不是T 1的叶结点，则T 1与T 3相同A ．仅I 、IIIB ．仅I 、IVC ．仅II 、IIID ．仅II 、IV7．设图的邻接矩阵A 如下所示。
各顶点的度依次是（ ）。
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中有弧<vi,vj>；B．G中没有弧<vi,vj>；C．G中有一条从顶点vi到顶点vj的路径；D．G中有一条从顶点vj到顶点vi的路径。
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中有弧<vi,vj>；B．G中没有弧<vi,vj>；C．G中有一条从顶点vi到顶点vj的路径；D．G中有一条从顶点vj到顶点vi的路径。
目 录第一部分 历年考研真题汇编 .......................................................................................................................... 2014年江西师范大学计算机信息工程学院863数据结构与程序设计考研真题.................................................................................................................................................................... 2013年江西师范大学计算机信息工程学院863数据结构与程序设计考研真题.................................................................................................................................................................... 第二部分 兄弟院校真题汇编 .......................................................................................................................... 2013年北京航空航天大学991数据结构与C 语言程序设计考研真题 ........................................... 2012年北京航空航天大学991数据结构与C 语言程序设计考研真题 ........................................... 2011年北京航空航天大学991数据结构与C 语言程序设计考研真题 ........................................... 2010年北京航空航天大学993数据结构与C 语言程序设计考研真题 ...........................................江西师范大学计算机信息工程学院863数据结构与程序设计历年考研真题汇编附答案 最新资料，WORD 格式，可编辑修改！第一部分历年考研真题汇编2014年江西师范大学计算机信息工程学院863数据结构与程序设计考研真题2013年江西师范大学计算机信息工程学院863数据结构与程序设计考研真题第二部分兄弟院校真题汇编2013年北京航空航天大学991数据结构与C语言程序设计考研真题。
