《数据结构》模拟试题15

《数据结构》模拟试题15

一、填空题(每小题2分，共18分)

1、数据的逻辑结构在计算机中的基本存储结构有和0

2、算法的时间复杂度取决于o

3、队列是的线性表，其操作数据的基本原则是o

4、设有一个二维数组A[0…9][0…9],若每个元素占2个基本存储单元，A⑼⑼的地址是200,

若按列优先(以列为主)顺序存储，则A[6][6]的存储地址是_______-

5、在高度为h的二叉树的中只有度为0和度为2的结点，则该类二叉树中所包含的结点数

至少为__________

6、对于一个有n个顶点和e条弧的有向图，若采用正邻接链表存储，则表头向量的大小

为，邻接表中的结点总数为o

7、若采用分块查找，要求线性表块内,块间o

8、对于文件，按其记录的类型可将文件分为文件^文件。

9、外部排序的最基本方法是，其主要时间花费在方面。

二、单项选择题(请将答案写在题目后的括号中。每题2分，共18分)

1、下面程序段的时间复杂度是()0

for(i=l；i<=m；i++)

for(j=l5j<=n；j++)A[i](j]=i+j;

(A)O(m+n)(B)O(m)(C)O(n)(D)O(m*n)

2、判断一个循环队列Q(最多元素个数为m)为满队列的条件是()。

(A)Q.front==Q.rear；(B)Q.front!=Q.rear；

(C)Q.front==(Q.rear+l)%m；(D)Q.front!=(Q.rear+l)%m；

3、设有一个栈顶指针为top的顺序栈S,则将元素p压入栈S中的操作是()。

(A)S[top++]=p；(B)S[++top]=p；

(C)S[top—]=p；(D)S[-top]=p；

4、广义表((a),((b),c),(((d))))的长度是，深度是-()

(A)3,4(B)3,3(C)4,3(D)4,4

5、在二叉树中，指针P所指的结点是叶子结点的条件是()0

(A)P->Lchild!=NULL&&P->Rchild!=NULL；

(B)P->Lchild!=NULL&&P->Rchild==NULL；

(C)P->Lchild==NULL&&P->Rchild!=NULL；

(D)P->Lchild==NULL&&P->Rchild==NULL；

6、■—棵二叉树，其先序遍历序列是abdghcefi,中序遍历序列是bgdhaecfi,则其后序遍历

序列是()0

(A)ghdbiefca(B)ghdbeicfa

(C)ghdbeifca(D)gdheibfca

7、若以｛4,5,6,7,8｝作为叶子的权值构造Huffman树(按左子树根结点的权小于等于右子

树根结点的权的次序构造)，则其带权路径长度WPL为()。

(A)60(B)61(C)73(D)69

8、在无权图G的邻接矩阵中，若(Vi,2)或＜Vi,Vj＞属于G的边集，则对应元素等

于_________^否则等于)

(A)1,1(B)1,0(C)0,1(D)0,0

9、设有一组记录的关键字是(37,28,56,80,60,14,25,50),用快速排序法以第一个

记录为基准得到的一次划分结果是()o

(A)25,28,14,37,60,80,56,50(B)25,28,37,14,60,80,56,50

(C)25,28,14,37,60,56,80,50(D)25,28,37,14,56,80,60,50

三、分析题(每题6分，共30分)

1、设有一棵树如下图，请先将此树转换为二叉树，然后给出该二叉树的前序线

索树和中序线索树。

2、已知某有向图的逆邻接链表如下图所示，请先画出该有向图，然后给出其邻接矩阵和正

邻接链表。

3,将关键字序列(17,19,13,7,15,9,25)依此插入到初态为空的二叉排序树中，请

画出建立二叉排序树T的过程；然后画出删除13之后的二叉排序树TL

4、线性表的关键字集合{21,25,28,19,42,57,15,43,17,36,49,27,65}

，共有13个元素，已知散列函数为：H(k)=kMOD13,采用线性探测法处理冲突，请给出

对应的散列表结构，并计算该表成功查找的平均查找长度。

5、已知数据序列为{35,29,22,16,17,9,38,27,13,45},请给出采用选择排序方法

按非递减要求进行排序的过程。

四、算法填空(每空2分，共20分)

请在下面各算法的空白处填上相应语句以实现算法功能。每个空白只能填一个语句。

1、在以L为头结点的双向链表中删除所有值为key的结点，结点结构定义如下。

typedefstructLnode

{ElemTypedata;/*数据域，保存结点的值*/

structLnode*prior;/*指针域，指向直接后继*/

structLnode*next;/*指针域，指向直接前趋*/

JDULNode;/*结点的类型*/

VoidDel_Node(DULNode*L,intkey)

{DULNode*q,*p=L->next;

while(p!=NULL)

{if(p->data==key)

{q=p->next;

if(p->next!=NULL)

{p->next->prior=p->prior;

elsep->prior->next=NULL;

)

2、设T是指向二叉树根结点的指针变量，用非递归方法统计树中叶子结点的数

目。

#defineMax_Node_Num50

TypedefstructBTNode

{ElemTypedata;/*数据域，保存结点的值*/

structBTNode*Lchild,*Rchild;/*指针域*/

JBTNode;/*结点的类型*/

Voidcount_leaf_node(BTNode*T)

{BTNode*Stack[Max_Node_Num],*p=T,*q;

inttop=0,leaf_num=0;/*leaf_num保存叶子结点的数目*/

if(T==NULL)printf(uTheBinaryTreeisEmpty!\n");

else{do

{if(p->Lchild==NULL&&p->Rchi1d==NULL);

q=p->Rchild;

if(q!=NULL);

p=p->Lchild;

)

while();

primf（“叶子结点的数目是：%d\n",leaf_num）;

)

3、用正邻接链表保存有向图，各结点的结构形式如下，所有的顶点结点放在数

组adjlist口中，统计图中顶点的入度。

链表结点顶点结点

adjvexinfonextarcdataindegreefirstarc

Voidcount_indegree(ALGraph*G)

{intk;LinkNode*p;

for(k=0;k<G->vexnum;k++)

G->adjlist[k].indegree=O;

for(k=0;k<G->vexnum;k++)

{；

while(p!=NULL)

{G->adjlist[p->adjvex].indegree++;

4、H->R[s...m]中记录关键字除H->R[s].key均满足堆定义，调整H->R[s]的位置

使之成为小根堆。

VoidHeap_adjust(Sqlist*H,ints,intm)

{intj=s,k=2*j;/*计算H->R[j]的左孩子的位置*/

H->R[0]=H->R[j];/*临时保存H->R[j]*/

for(k=2*j;k<=m;k=2*k)

{if((k<m)&&(H->R[k].key>H->R[k+l].key)

k++;/*选择左、右孩子中关键字的最小者*/

if(H->R[O].key>H->R[k].key)

{H->R[j]=H->R[k];j=k;

；)

elsebreak;

五,编写算法(要求给出相应的数据结构说明，14分)

设Hash函数为H(key)=keyMOD13,用链地址法解决冲突，请写出进行散

列查找的算法。

《数据结构》模拟试题15参考答案

一、填空题（每小题2分，共18分）

1、顺序（存储）结构链式（存储）结构

2、问题的规模

3、操作受限后进先出（先进后出）

4、232

5、2h-l

6、ne

7、顺序存储块间有序

8、操作系统数据库

9、归并内、外存之间的数据交换

二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）

题号123456789

答案DCBADCDBA

三、分析题（每题6分，共30分）

1、解：转换后得到的二叉树如图（a）,前序线索树如图（b）,中序线索树如图（c）。

2、J图（a）转换后的二叉树在邻接图（b）前序线索树邻接链表力图⑹中序线索树

图(a)有向图

图(b)有向图

roo9oooo8

cooooo4oo

56oo4oo

oooooooooo

00J

co210oo

(c)邻接矩阵

3、解：将关键字序列(17,19,13,7,15,9,25)依此插入到初态为空的二叉排序树

中所得到的二叉排序树T如图(a)所示；删除13之后的二叉排序树T1如图(b)所示。

图(a)生成的二叉排序树T的过程

图(b)删除13的二叉排序树TI

4、解：根据所给定的散列函数和处理冲突方法，其地址计算过程如下：

H(31)=21MOD13=8H(25)=25MOD13=12H(28)=18MOD13=2

H(19)=19MOD13=6H(42)=42MOD13=3H(57)=57MOD13=5

H(15)=15MOD13=2冲突H(15)=(2+1)MOD13=3冲突

H(15)=(3+l)MOD13=4

H(43)=43MOD13=4冲突H(43)=(4+l)MOD13=5冲突

H(43)=(5+l)MOD13=6冲突H(43)=(6+l)MOD13=7

H(22)=22MOD13=9H(36)=36MOD13=10

H(49)=49MOD13=10冲突H(49)=(10+1)MOD13=11

H(27)=27MOD13=1H(65)=65MOD13=0

得到的散列表结构如下：

散列地址0123456789101112

关键字65272842155719433122364925

成功查找的平均查找长度：ASL=(1X9+2X2+2X3)/13=19/13

5、解：采用选择排序号方法做非递减排序的过程如下:

初始关键字：3529221617938271345

第一趟排序：9292216173538271345

第二趟排序：9132216173538272945

第三趟排序：9131622173538272945

第四趟排序：9131617223538272945

第五趟排序：91316172227383529