广东海洋大学数据结构期末模拟试题两套(含答案,考试必出)

一、判断题（下列各题，你认为正确的，请在前面的括号内打√，错误的打×。每题1分，共10分）

（√）1．数据的存储结构是数据的逻辑结构的存储映像。

（√）2．用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相互关系。

（×）3．非线性结构中，至少存在一个元素不止一个直接前驱或不止一个直接后继。

（√）4．树的最大特点是一对多的层次结构。

（√）5．队列的特点是先进先出。

（×）6．图的最小生成树是惟一的。

（）7．线性表是广义表的特殊形式。

（√）8．由后序遍历序列和中序遍历序列能惟一确定一棵二叉树。

（×）9．散列表是一种链式存储结构。

（×）10．快速排序并非在任何情况下都比其他排序方法速度快。

二、填空题（每空2分，共20分）

1．数据的存储结构的4种形式为链接存储顺序存储、散列存储和索引存储。

2．所有插入和删除都在表的一端进行的线性表称为队列。

3．有n个结点的完全二叉树（空二叉树的深度为0），其深度h=「log2n」+1。

4．对于顺序循环队列Q[M]，下标从0到M-1，头尾指针分别为F 和R，入队时，队尾指针的变化可以表示为R=（R+1）%M。

5．散列法既是一种查找方法，又是一种存储方法。

6．n个顶点的有向完全图具有n*（n-1）条弧。

7．n个元素的顺序查找（检索）的平均查找长度为(n+1)/2。

三、单选题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案填入括号内，多选不给分，每小题3分，共15分）1．若进栈序列为1，2，3，4，则不可能得到的出栈序列是（C）。

A）3，2，1，4B）3，2，4，1

C）4，2，3，1D）2，3，4，1

2．对于图1所示的二叉树，其后序序列为（C）。

A）ABDECFG B）DBEAFCG

C）DEBFGCA D）GFCEBDA

3．对于图2所示的AOV网，不能出现的拓扑序列为（A）。

A）12345B）12435

C）24135D）21435

图1图24．深度为k的完全二叉树所含叶结点的个数最多为（B）。

A）2k B）2k-1C）k D）2k 5．衡量查找算法效率的主要标准是（C）。

A）元素个数B）所需的存储量

C）平均查找长度D）算法难易程度

四、应用题（25分）

1．给定B树如图3所示，画出将14插入到B树后的情形。（3分）

图3

2．对图4进行如下操作：

（1）写出其邻接矩阵。（2分）

（2）按Kruskal算法求其最小生成树，并写出相应的边集数组

图4

|012∞5∞∞|

|1208∞10∞|

|∞80∞∞3|

|5∞∞06∞|

|∞10∞6011|

|∞∞3∞110|

3．请画出后序序列和中序序列相同的二叉树的所有形态。（3分）1：只有左子树

2：一个结点

3:空树

4．散列函数为H(k)=k%7，散列表的地址为0～6，用线性探查法解决冲突，建立散列表ht。给定关键字序列为{32,13,49,55,22,38,21}。

要求：（1）构造散列表（只画出表，不写算法）。（5分）

位置：0123456

关键字：49552238322113

比较次数：1321161

（2）求出平均查找长度。（2分）

WPL=(1+3+2+1+1+6+1)/7=15/7

5．用直接选择排序法对下列关键字进行排序，请写出每一趟排序的结果。（6分）

68452090151050

第一趟：10452090156850

第二趟：10152090456850

第三趟：10152090456850第四趟：10152045906850

第五趟：101520455060

第六趟：101520455060

五、算法设计（在下列算法的横线上填上适当的表达式、语句或运算符。每空3分，共30分）

1．在带头结点的head单链表的结点a之后插入新元素x。

class node

{public:

elemtype data;

node*next;

};

void lkinsert(node*head,elemtype x)

{node*s,*p;

s=_new node；________

s->data=__x；_______;

p=head->next;

while(p!=NULL)&&(p->data!=a)

__p=p-〉next_______;

if(p==NULL)

cout<<"不存在结点a";

else{___s->next=p->next______;

___p->next=s______;

}

}

2．快速排序

void qksort(int R[],int p,int q)//按递<对R[p]～R[q]进行快速排序

{int i=p,j=q;

R[0]=R[i];//R[0]作临时单元

while(__i{

while(j>i)&&(R[j]_=>___R[0])j--;

if(j>i)

{R[i]=R[j];i++;}

while(iif(i};

R[i]=___R[0]______;

i++;j--;

if(j>p)qksort(R,p,j);

if(i}

模拟试题三

一、判断题（下列各题，你认为正确的，请在前面的括号内打√，错误的打×。每题1分，共10分）

（）1．数据是计算机加工处理的对象。

（）2．数据结构的概念包括数据的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面。

（）3．线性表是由n≥0个相同类型元素组成的有限序列。

（）4．栈是一种后进先出的线性表。

（）5．从循环链表的某一结点出发，只能找到它的后继结点，不能找到它的前驱结点。

（）6．单链表设置头结点的目的是为了简化运算。

（）7．深度为h（空二叉树的深度为0）的二叉树，最多有2h-1个结点。

（）8．图G由两个集合V(G)和E(G)所组成，其中顶点集V(G)可以为空集，而边集E(G)不能为空。

（）9．散列法是一种对关键字进行运算的查找方法和存储方法。

（）10．快速排序在任何情况下都是速度最快的一种排序方法。

二、填空题（每空2分，共20分）

1．数据元素之间存在的相互关系称为。

2．数据结构从逻辑上分为结构和结构。

3．线性表的顺序存储结构称为。

4．所有插入在表的一端进行，而所有删除在表的另一端进行的线性表称为。

5．深度为h（空二叉树的深度为0）的二叉树，最少有个结点。

6．折半查找要求待查表为表。

7．n个记录按其关键字大小递增或递减的次序排列起来的过程称为。

8．用链表存储数据时，不仅要存储数据元素的，还要存储元素之间的相互。

三、单选题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案填入括号内，多选不给分，每小题3分，共15分）1．与线性表的链接存储相符的特性是（）。

A）插入和删除操作灵活B）需要连续存储空间

C）便于随机访问D）存储密度大

2．若进队序列为1，2，3，4，则出队序列是（）。

A）4，3，2，1B）1，2，3，4

C）1，3，2，4D）3，2，4，1 3．已知广义表A=((a,b),(c,d))，则head(A)等于（）。

A）（a,b）B）((a,b))C）a,b D）a4．n个结点的二叉树，若用二叉链表作为存储结构，则非空闲的左、右孩子链域为（）。

A）n B）2n C）n-1D）n+1 5．6个顶点的连通图的深度优先生成树，其边数为（）。

A）6B）5C）7D）4

四、应用题（共25分）

1．给定B树如下，画出将19插入到B树后的情形。（4分）

2．对于给定的5个实数W={8,5,13,2,6}，试构造Huffman树，并求出该树的最小带权路径长度。（7分）

3．对于下面所给的图，进行如下操作：

（1）画出其邻接表。（4分）

（2）写出从V1出发的深度优先搜索序列。（3分）

4．给定有序表D={15,17,18,22,35,51,60,88,93}，用折半查找法在D中查找18。现要求：

（1）试用图示法表示查找过程。（4分）

（2）求出其成功的平均查找长度ASL。（3分）

五、算法设计（在下列算法的横线上填上适当的语句或表达式。每空3分，共30分）

1．直接选择排序

void selectsort(int R[],int n)

//按递增序对R[0]～R[n-1]进行直接选择排序

{int i,j,k,temp;

for(i=0;i<=;i++)

{k=i;

for(j=;j<=n-1;j++)

if(R[j]R[k])

k=j;

if()

{temp=R[i];R[i]=;R[k]=temp;} }

}

2．中序遍历二叉树。设二叉树用二叉链表表示，以t为根指针，二叉链表结点的类型为node；栈s的元素类型为指向node的指针类型，栈容量m足够大。中序遍历的非递归算法如下：

struct node

{char data;

node*lc,*rc;

};

void preorder(node*t){node*s[m]，*p=t;

int top=-1;//置栈空

do

{while(p!=NULL)

{s[++top]=;

;

}

if(top!=-1)

｛p=s[top--];

;

;

}

}while(()||(p!=NULL));

}