青岛大学2017年硕士研究生入学考试试题科目代码：910科目名称：数据结构（共5页）
请考生写明题号，将答案全部答在答题纸上，答在试卷上无效
一、单项选择题（本大题共10道小题，每小题2分，共20分）
1．计算机算法指的是（）。
A．计算方法B.排序方法C.解决问题的步骤序列D.存储结构
2．链表不具有的特点是（）。
A．插入、删除不需要移动元素B．可随机访问任一元素
C．不必事先估计存储空间D．所需空间与线性长度成正比
3．连续存储设计时，存储单元的地址（）。
A．一定连续B．一定不连续
C．不一定连续D．部分连续，部分不连续二叉树中序遍历非递归算法
4．一个递归算法必须包括（）。
A.递归部分
B.终止条件和递归部分
C.迭代部分
D.终止条件和迭代部分
5．栈和队列的共同点是（）。
A.都是先进先出
B.都是先进后出
C.只允许在端点处插入和删除元素
D.没有共同点
6．任何一棵二叉树的叶子结点在先序、中序和后序遍历中的相对次序（）。
A．不发生改变B．发生改变C．不能确定D．以上都不对
7．由带权为{8，2，5，7}的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（）。
A．23B．37C．46D43
8．若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（）图。
A．非连通B．连通C．强连通D．有向
9．适用于折半查的表的存储方式及元素排列要求为（）。
A．链接方式存储，元素无序B．链接方式存储，元素有序
C．顺序方式存储，元素无序D．顺序方式存储，元素有序
10．对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（）。
A．O(n)B．O(n2)C．O(nlog2n)D．O(n3)
二、简答题（本大题共6道小题，每题5分，共30分）
1．如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？2．有5个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？3．简述树与二叉树的转化方法。试举一个例子说明。
4．简要说明图的各种遍历方法。
5．简述顺序查和折半查的优缺点。
6．简要说明归并排序的基本思想。
三、综合应用题（本大题共4道小题，每题12分，共48分）
1．已知一棵二叉树的中序遍历序列为BCAFEC，后序遍历序列为CBECFA，试画出该二叉树，并给出该二叉树的先序序列。
2．对于下图所示的有向图，试给出：
(1)邻接表；
(2)从顶点v1出发的深度优先遍历序列；
(3)从顶点v3出发的广度优先遍历序到。
3．设将关键字集合Keys=｛2,6,7,5,4,3,1｝中的元素依次插入到一个空的平衡二叉排序树中，画出所得的平衡二叉排序树。假设查每一个元素的概率相同，查此平衡二叉树排序中任一结点的平均查长度为多少？
4．某设待排序的关键字集合为{12，2，16，30，28，10，16*，20，6，18}，试分别回答下面的问题。
①给出希尔排序（增量选取5，3，1）的结果；
②写出快速排序第一趟之后的状态；
③把关键字集合调整成堆顶元素取最大值的堆。
四、算法分析题（本大题共3道小题，每题10分，共30分）
1．下面的算法是在带头结点的单链表L中，删除第i个元素，并由e返回其值，请在空白处填入正确的语句。
Status ListDelete(LinkList&L,int i,ElemType&e)
{
LinkList p,q;
p=_____①_____;
int j=0;
while(p->next&&______②_____){
p=p->next;
++j;
}
if(!(______③______)||j>i-1)
return ERROR;
q=p->next;
p->next=_____④______;
e=q->data;
_______⑤_______;
return OK;
}
2．阅读下面的代码，试说明算法的功能。
int Unknown(BiTNode*T,BiTNode*s)
{//s为指向二叉排序树中某个结点的指针
int k=0;
BiTNode*p=T;
if(T!=NULL){
k++;
while(p->data!=s->data){
if(p->data<s->data)
p=p->rchild;
else
p=p->lchild;
k++;
}
}
return k;
}
3．下面代码是中序遍历二叉树T的非递归算法。请在空白处填入正确的语句。Status InOrderTraverse(BiTree T)
{
SqStack S;
BiTree p;
_____①_______;
Push(S,T);
while(!_______②________)
{
while(GetTop(S,p)&&_____③_______)
Push(S,p->lchild);
Pop(S,p);
if(!StackEmpty(S))
{
_______④________;
printf("%c",T->data);
_______⑤______;
}
}
return OK;
}
五、算法设计题（本大题共2道小题，每题11分，共22分）
1．已知L1、L2分别为两个循环单链表（带头结点）的指针，m,n分别为L1、L2表中数据元素个数。试设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。
LinkList Union(LinkList&L1,LinkList&L2,int m,int n) {……}
2．试编写算法，统计一棵二叉树中所有非叶子结点的数目。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。