数据结构试题-试卷四-含答案VIP

模拟试题四模拟试题四

一、选择题（20分）

1.由两个栈共享一个存储空间的好处是(

)。

A)减少存取时间，降低下溢发生的几率

B)节省存储空间，降低上溢发生的几率

C)减少存取时间，降低上溢发生的几率

D)节省存储空间，降低下溢发生的几率

2.设有两个串p和q，求q在p中首次出现位置的运算称做(

)。

A)连接

B）模式匹配

C）求子串

D）求串长

3.n个顶点的连通图中边的条数至少为(

)。

A)0

B)l

C)n-l

D）n

4.对一个具有n个元素的线性表，建立其有序单链表的时间复杂度为(

)。

A)O(n)

B)O(1)

C)O(n2)

D)O(log2n)

5.在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是(

)。

A)p->next=s;s->prior=n;p->next->prior=s;s->next:p->next.

B)s->priOFp;s->next-p->next;p->next=s;p->next->priOFS。

C)p->next=s;p->next->priOFS;s->prior=p;s->next=p->next.

D)s->prior=p;s->next=p->next;p->next->priOFS;p->next=S。

6，串的长度是(

)。

A)串中不同字符的个数

B）串中不同字母的个数

C)串中所含字符的个数n(n>0)

D)串中所含字符的个数n(n≥0)

7.若有一个钱的输入序列是l，2，…，n，输出序列的第一个元素是n，则第i个输出元素是(

)。

A)n-i

B)n-i-l

C）n-i+l

D）不确定

8.设有一个栈，元素的进栈次序为A，B，C，D，E，下列(

)是不可能的出栈序列。

A)A,B,C,D,E

B)B,C,D,E,A

C)E,A,B,C,D

D)E,D,C,B,A

9.在一棵度为3的树中，度为3的结点数有2个，度为2的结点数有1个，度为l的结点数有2个，那么度为0的结点数有(

)个。

A)4

B)5

C)6

D)7

10.在一个具有n个结点的无向完全图中，包含有(

)条边。

A)n(n-l)/2

B)n(n-l)

C)n(n+l)/2

D)nn

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

1.数据逻辑结构包含__________三种类型，树型结构和图形结构合称__________。

2.某算法在求解一个10阶方程组时，运算次数是500，求解二个30阶方程组时，运算次数是4500，则该算法的时间复杂度为__________。

3.在一个长度为n的顺序表个插入一个元素，最少需要移动__________个元素，最多需要移动__________个元素。

4.如果某有向图的所有顶点可以构成一个拓扑排序序列，则说明该有向图__________。

5.在双向循环链表中，在指针p所指的结点之后插入指针f所指的结点，其操作为__________。

6.一数组的长度为20，用于存放一个循环队列，则队列最多只能有__________个元素。

7.无向图用邻接矩阵存储，其所有元素之和表示无向图的__________。

8.一个具有n个结点的线性表采用堆排序，在建堆之后还要进行__________次堆调整。

9.《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和__________。

10.若频繁地对线性表进行插入与删除操作，该线性表应采用__________存储结构。

三、简答题(36分)

1.已知一个长度为12的表(Jan，Feb，Mar，Apr，May，June，July,Aug,Sep,Oct,Nov，Dec)。

1)试按表中元素的次序依次插入一棵初始为空的二叉排序树，字符之间以字典顺序比较大小，并画出对应的二叉排序树，且求出在等概率情况下查找成功的平均查找长度。（4分）

2)根据该二叉排序树，查找元素July，需要比较那几个数？（4分）

2.已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，画出这棵二叉树。（4分）

3.已知题图4是一个有向图。

(1)画出该有向图的邻接链表。（4分）

(2)基于(1)给出的邻接链表，求从顶点F出发的广度优先遍历。（4分）

4.用Prim算法（一个顶点一个顶点加入生成树）求题图5的最小生成树。

(l)从顶点D开始，写出各顶点加入生成树的次序。（4分）

(2)画出最终的最小生成树。（4分）

5.已知题图6是一棵二叉排序树。

(1)计算平均查找长度。（4分）

(2)画出删除值为46的结点后的二叉排序树。（4分）

四、程序填空题（10分）

1.以下是采用冒泡排序法对数组a进行排序。完成程序。

bsort(inta[]，intn)

{

int

n,i,j，tmp;

for（i=__________;i>=l;i--）{

for(j=1，j<=i;j++)

{

if(__________)

{tmp=a[j];a[j]=a[j+1];a[j+1]=tmp;)

}

}

}

2.在单链表(表首指针为head)的元素中找出最后一个值为e的元素，返回其指针;如果找不到，返回NULL。完成以下程序。

typedef

struct

LinkNode{

intdata;

structLinkNode

*next;

}

Node;

Node

*search一link(Node*head,inte)

{

Node*p，*q;

q=__________;

for(p=head;____;p=p->next)

if(p->data==e)__________;

returnq;

}

3.下列算法是输出一棵二叉树第i层的所有结点的值，假设根结点是第1层。

Typedef

struct

LinkNode{

intdata;

Struct

LinkNode

*lchild,

*rchild;

}

Node;

void

outi(Node*tree,inti)

{

if(tree==NULL)

return;

if(i==1)

{printf("%d\n",tree->data);return;）

outi(__________);

outi（__________）;

}

4.下面一段算法描述的是对题图7所示火车调度站的n节硬席或软席车厢（分别以H和S表示）进行调度的运算（入栈或出栈运算）序列，调度后所有的软席车厢都被调整到硬席车厢之前。

typedefcharElemType;

int

attemper(STACK

*p,STACK

*q)

{/*将p栈道的车厢，经调度之后入q栈道，使软席车厢调整到硬席车厢之前*/

STACK*temp;

ElemTypee;

InitStack(temp);

while(!Empty(p)){

Pop(p，＆e);

if(e=='S')__________;

else__________;

}

while(!Empty(temp))

{__________;Push(q,e);}

}

五、编程题(14分)

1.两个字符数组s，t中各放有一个串，编写算法，将所有t中有而s中没有的字符加到s中（逐个加到s的后面）。

2.已知顺序表的数据结构如下，编写算法，删除顺序表前面的10个元素。如果顺序表中的元素少于10个，则删完为止。

typedefstruct

{int

elem[100];

intlength;

}

SQ;模拟试题四答案

模拟试题四参考答案

一、选择题

1.B

2.B

3.C

4.C

5.C

6.D

7.D

8.C

9.C

10.C

二、填空题

1.线性、树形和图形，非线性。

2.O(n2)

3.0，n。

4.无环路5.（1）f->next=p->next;

(2)p->next->prior=f;

（3）f->prior=p;

(4)p->next=f;6.19。

7.所有顶点度之和。8.n-2

9.对数据的操作

10.链表

三、简答题

（1）插入一棵初始为空的二叉排序树平均查找长度=（1+2x2+3x3+4x3+5x2+6x1）/12=12

(2)需要比较的元素：Jan，Mar，June

2.根据中序序列BDCEAFHG和后序序列DECBHGFA，画出二叉树如下：

3.(1)题图4—1的邻接链表如下：(2)从顶点F出发的广度优先遍历序列：FCBADE

4.(1)题图4.2从顶点D开始，各顶点加入生成树的次序：DECAGBF

(2)最小生成树为：

5.(1)题图4-3的平均查找长度：ASL=(1十2×2十3×3十4×2十5×1)/9=3

(2)删除值为46的结点后的二叉排序树如下：

四、程序填空题

1.(1)n-l

(2)a[j]>a[j+l]

2.(1)NULL

(2)p!=NULL或者！p

(3)q=p

3.(1)tree->lchild,

i-l

(2)tree->rchild,

i-l

（注：1，2答案顺序可以调换）

4.(1)Push(q,e)

(2)Push(temp,e)

(3)Pop(temp,&e)

五、编程题

1.在字符数组中将所有t中有而s中没有的字符加到s中的算法如下：

typedefstruct

{

char

data[100];

intlength;

)

List;

voidAddTos(LIST

*s,

LIST*t)

{

inti，j;

for(i=0;i<t->length;i++)

{

for(j=0;j<s->length＆&s->data[j]!=t->data[i];j++)

if(j==s->length＆＆s->length<sizeof(s->data)-1)

/*找不到相同的值，并且有空间*/

{

s->data