数据结构(专)-201606-模拟卷2

第1页共2页华东理工大学网络教育学院（全部答在答题纸上，请写清题号，反面可用。试卷与答题纸分开交）数据结构（专）1606模拟卷2一、填空题（共10题,每题1分,共10分）1.在一个单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行的语句为____和p->next=s。（1分）

.2.设广义表L=(

(

)，(

)

)，则Head(L)是____。（1分）

.3.n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为____。（1分）

.4.队列的操作是在____进行删除。（1分）

.5.广义表((a,b),c,d)的表头是________________________，表尾是________________________。（1分）

.6.一棵深度为6的满二叉树有____个叶子结点。（1分）

.7.已知二维数组A[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是________________。（1分）

.8.在n个结点的单链表中要查找某结点*p，其时间复杂度为____。（1分）

.9.若一个算法中的语句频度之和为T（n）＝10n+50nlog2n+9n2，则该算法的时间复杂度为____。（1分）

.10.平衡二叉排序树具有的特点是左子树与右子树的高度差的绝对值____。（1分）

.二、判断题（共10题,每题1分,共10分）1.在常用的排序方法中，一般情况下快速排序的平均查找长度最小。（1分） (

)

.2.平衡二叉排序树的平衡因子为0和1。（1分） (

)

.3.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（1分） (

)

.4.顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。（1分） (

)

.5.二叉排序树的先序遍历序列是递增有序的。（1分） (

)

.6.在顺序表（即顺序存储结构的线性表,表长为n）中删除第i个元素，需要平均移动n-i+1个元素。（1分） (

)

.7.若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用单链表存储方式最节省运算时间。（1分） (

)

.8.设有n个结点的二叉树，采用二叉链表存储，空指针域个数为n-1个。（1分） (

)

.9.有一个有序表{1，3，9，12，32，41，62，75，77，86，95，100}，当二分查找值为86的关键字时，需要比较的关键字有5个。（1分） (

)

.10.将一棵树转换为二叉树表示后,该二叉树的根结点没有右子树。（1分） (

)

.三、单选题（共10题,每题2分,共20分）1.若一个算法中的语句频度之和为T（n）＝10＋8n+12nlog2n+9n2，则该算法的时间复杂度为（）。（2分）

A.O(1)

B.O(n)

C.

O(nlog2n)

D.O(n2)

2.线性表Ｌ在

（）

情况下适用于使用链式结构实现。（2分）

A.

需经常修改Ｌ中的结点值

B.

需不断对Ｌ进行删除插入

C.

Ｌ中含有大量的结点

D.

Ｌ中结点结构复杂

3.已知二维数组A[0..5][0..7]采用行序为主方式存储，每个元素占2个存储单元,并且A[0][0]的存储地址是1024,

则A[4][6]的地址是().（2分）

A.

1048

B.

1080

C.

1120

D.

1100

4.给定二叉树的两种遍历序列，前序遍历序列为abcdef；中序遍历序列为bdcaef，则其后序遍历序列为().（2分）

A.

acbed

B.

decab

C.

deabc

D.

dcbfea

5.设有50000个无序元素，希望用较快速度挑选出其中前10个最大元素，采用（）方法最好。（2分）

A.

直接插入排序

B.

堆排序

C.

快速排序

D.

归并排序

6.若一个栈的输入序列是1，2，3，…..，n，输出序列的第一个元素是n

，则第i个输出元素是()。（2分）

A.n-i

B.

i

C.

n-i+1

D.

n-i-1

7.在一个带头结点的循环双向链表中，若要在指针p所指向的结点之后插入一个q指针所指向的结点，则需要对q->next赋值为（）。（2分）

A.

p->prior

B.

p->next

C.

p->next->next

D.

p->prior->prior

8.下面关于串的叙述中，哪一个是不正确的？（2分）

A.

串是字符的有限序列

B.

空串是由空格构成的串

C.

模式匹配是串的一种重要运算

D.

串既可以采用顺序存储，也可以采用链式存储

9.一个循环队列的头指针为front，尾指针为rear。则判断队列满的条件是（）。（2分）

A.rear=front

B.rear=front+1

C.

front=rear+1

D.front=(rear+1)

%

(整除)

n

10..设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s,

i,

j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,

2,

len(s2)),

subs(s1,

len(s2),

2))的结果串是（）。（2分）

A.BCDEF

B.

BCDEFG

C.

BCPQRST

D.

BCDEFEF

四、问答题（共2题,每题5分,共10分）1.写出下列程序段的输出结果（队列中的元素类型QElem

Type为char）。void

proc

(Queue

*Q){

Stack

S;

int

d;InitStack(&S);

while(!EmptyQueue(*Q)){

DeleteQueue(Q,

&d);Push(

&S,

d);}while(!EmptyStack(S))

{

Pop(&S,

&d);EnterQueue(Q，d)}}2.简述栈和队列的异同点。五、计算题（共3题,每题10分,共30分）1.请将该二叉树还原成其对应的森林。（10分）2.已知一棵二叉树，其中序序列DBCAFGE，后序序列DCBGFEA，试画出该二叉树并写出其先序序列。（10分）

3.输入一个正整数序列{100，50，302，450，66，200，30，260}，建立一棵二叉排序树，要求画出该二叉排序树。（10分）

六、论述题（共2题,每题10分,共20分）1.设计一递归算法，实现在二叉链表为存储结构的二叉树中交换每个结点的左孩子和右孩子。二叉排序树的存储结构如下：

typedef

int

KeyType

typedef

struct

node{

//结点类型

KeyType

key;

//关键字项

Struct

node

*lchild，

*rchild;

//左右孩子指针

}

BSTNode;

typedef

BSTNode

*BSTree;（10分）

2.设A、B是两个单链表，其表中元素递增有序，编写一算法将A、B合并成一个有序的单链表C，要求C也是递增有序的