暨南大学信息科学技术学院830数据结构历年考研真题汇编

下载地址:http://free.100xuexi.com/Ebook/140615.html
目录                                                                                        封面
内容简介
目录
2015年暨南大学信息科学技术学院830数据结构考研真题
2014年暨南大学信息科学技术学院830数据结构考研真题
2013年暨南大学信息科学技术学院830数据结构考研真题
2012年暨南大学信息科学技术学院830数据结构考研真题
2011年暨南大学信息科学技术学院830数据结构考研真题
2010年暨南大学信息科学技术学院830数据结构考研真题
                                                                                                                                    本书更多内容>>
                                                                                                                                                                                                                    使用说明                                                                                                   
                                                                                    

内容预览
2015年暨南大学信息科学技术学院830数据结构考研真题
2015年全国硕士研究生统一入学考试自命题试题（B卷）
学科、专业名称：计算机科学与技术、软件工程
研究方向：计算机系统结构081201，计算机软件与理论081202，计算机应用技术081203，软件工程083500，计算机技术（专业学位） 085211，软件工程（专业学位） 085212
考试科目名称及代码：数据结构830
考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。
一、单项选择题（每题2分，共30分）
1．线性表采用链式存储时，其地址（　　）。
A．必须是连续的
B．部分地址必须是连续的
C．一定是不连续的
D．连续与否均可以
2．若有一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（　　）。
A．n-i
B．n-i-1
C．n-i+1
D．不确定
3．已知单链表上一结点的指针为p，则删除该结点后继的正确操作语句是（　　）。
A．s= p->next;p=p->next; free（s）;
B．p=p->next; free（p）;
C．s= p->next;p->next=s->next; free（s）;
D．p=p->next; free（p->next）;
4．若使用邻接矩阵表示某有向图，则矩阵中非零元素的个数等于（　　）。
A．图中顶点的数目
B．图中边的数目
C．图中边的数目的两倍
D．无法确定
5．下列哪种排序需要的附加存储开销最大（　　）。
A．快速排序
B．堆排序
C．归并排序
D．插入排序
6．下面哪一方法可以判断出一个有向图是否有环（即回路）（　　）。
A．拓扑排序
B．求最短路径
C．求最小生成树
D．广度优先遍历
7．具有n个顶点的无向图至少应有（　　）条边才能确保是一个连通图.
A．n-1
B．n
C．n+1
D．2n
8．对线性表进行折半查找时，要求线性表必须（　　）。
A．以顺序方式存储
B．以顺序方式存储，且结点按关键字有序排序
C．以链接方式存储
D．以链接方式存储，且结点按关键字有序排序
9．若使用二叉链表作为树的存储结构，在有n个结点的二叉链表中非空的链域的个数为（　　） 。
A．n-1
B．2n-1
C．n+1
D．2n+1
10．在内部排序中，排序时不稳定的有（　　）。
A．插入排序
B．冒泡排序
C．快速排序
D．归并排序
11．一个具有500 个结点的完全二叉树具有一个孩子的结点个数最多为（　）。
A．1
B．250
C．0
D．249
12．从未排序序列中取出一个元素，并将其依次插入已排序序列的方法，称为 （　　）。
A．希尔排序
B．归并排序
C．插入排序
D．选择排序
13．如果希望对二叉排序树遍历的结果是升序的，应采用（　 ）遍历方法。
A．先序
B．中序
C．后序
D．层次
14．队列操作的原则是（　　）
A．先进先出
B．后进先出
C．只能进行插入
D．只能进行删除
15．在用邻接表表示有向图的情况下，假设n为图的顶点数目， e为图的边数目，建立图的算法的时间复杂度为（　　）。
A．O（n+e）
B．O（n2）
C．O（n×e）
D．O（n3）
二．填空题（每空2分，共20分）
1．循环链表的主要优点是。
2．根据数据元素之间关系的不同特性，基本逻辑结构分为 、 线性结构 、 树形结构和 四种。
3．对一棵完全二叉树中按照从上到下、从左到右的顺序从1开始顺序编号，则编号为11双亲结点的编号为 ，编号为10的结点的左孩子结点（若存在）的编号为 　。
4．下面程序段的时间复杂度是 　　。
S=0;
for（ i=0;ilchild;
}
else{
pop（&S， P）; 　printf（P->data）;
P=P->rchild;
}
}
}
2．假设表中关键字序列为（7，6，9，10，14，8），将关键字依次插入一棵初始为空的二叉排序树。画出二叉排序树的生成过程。（10 分）
3．关键字序列 T=（63，55，48，37，20，90，84，32），对其从小到大排序，以第一个关键字为枢轴（支点），写出快速排序具体实现过程（10分）。
4．一个有六个顶点{v1，v2，v3，v4，v5，v6}的网的邻接矩阵如图1所示，解答下列问题：
（1）画出该网（2分）
（2）能否写出一种拓扑排序序列，若可以，写出一种拓扑排序序列（2分）
（3）求出从顶点v1到其他各顶点之间的最短路径，并写出计算过程。（8）

图1.
5．设用于通信的电文由字符集{a， b，c，d，e，f，g}中的字母构成，它们在电文中出现的频度分别为{0.34，0.12，0.10，0.08，0.13，0.20，0.03}，如何为这7个字母设计二进制前缀编码使得电文总长最短，写出编码过程。（7分）
五．算法填空（每空2分，共20分）
1．以下算法功能是:插入元素e到队列Q中，完成算法的空格部分。
typedef struct Qnode
{ QElemType data;
struct Qnode *next;
}Qnode， *QueuePtr;
typedef struct
{ QueuePtr front; //队头
QueuePtr rear; //队尾
} LinkQueue;
status EnQueue（LinkQueue &Q，QElemType e）
{ P= （QueuePtr）malloc（sizeof（Qnode））;
if （ ①　） 　exit（OVERFLOW）;
P->data= 　②
P->next=　 ③
④　=P;
Q.rear= 　⑤ ;
Return OK;
}
2．以下程序为图的深度优先遍历算法，完成算法的空格部分。
Booleanvisited[Max];　 //访问标志数组
Status（*VisitFunc）（int v）; //访问函数变量
voidDFStraverse（ GraphG ， Status（*visit）（int v）） {
vistFunc=visit;
for （v=0;v<G.vexnum;++v） visited[v]=False;
for （v=0; ⑥ 　； ++v）
if （ ⑦　）　 DFS（G， v）; }
voidDFS（Graph G， int v） {
visited[v]=⑧; VisitFunc（V）;
for （w=FirstAdjvex（G，v）; 　⑨ ; w= NextAdjVex（G，v，w） ）
if （!visited[w]） 　⑩　　;
}
六．编写算法（25分）
1．已知线性表中的元素按值递增有序排列，并以带头结点的单链表作存储结构。试编写算法 ，删除表中所有值大于x且小于y的元素（若表中存在这样的元素）， 同时释放被删除结点空间。（10分）
2．设计一个算法，求不带权无向连通图G中距离顶点v的最远顶点。（15分）

下载地址:http://free.100xuexi.com/Ebook/140615.html