数据结构(专)1412模拟卷2

数据结构

华东理工大学网络教育学院

数据结构（专）1412模拟卷2

一、填空题 （共10题,每题1分,共10分）

1. 图的深度优先遍历类似于树的________遍历。

2. 图的广度优先遍历类似于树的________遍历。

3. 若一组记录的关键字码值为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为____。

4. 设s=’YOU ARE JUDG IT RIGHT OR WRONG’，执行操作：SubString(sub1,s,5,8)；则最后sub1的值为：____。

5. 具有6个顶点的有向图至少应有____条边才能确保是强连通图。

6. 一个算法必须在执行有穷步之后结束，这是算法特点的____。

7. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。

8. 设一棵完全二叉树具有600个结点，则此完全二叉树有____个叶子结点，有 1个结点只有非空左子树，有 0 个结点只有非空右子树。

9. 栈是一种特殊的线性表，允许插入和删除运算的一端称为____。不允许插入和删除运算的一端称为栈底。

10. n个顶点e条边的图，若采用邻接表存储，则时间复杂度为________________________。

二、判断题 （共10题,每题1分,共10分）

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

2. 在一个图中，所有顶点的度数之和等于图的边数的2倍。 ( )

3. 关键路径是从源点到收点的最长的一条路径，或者全部由关键活动构成的路径。 ( )

4. 一个有n个叶子结点的哈夫曼树中，其结点总数为2n。 ( )

5. 设一棵完全二叉树有500个结点，则共有250个叶子结点。 ( )

6. 二叉排序树或是一棵空树，或是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值；若它的右子树非空，则根结点的值大于其右孩子的

7. 若查找表的长度为n，则顺序查找法的平均查找长度为（n+1）/2。 ( )

8. 用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 ( )

9. 平衡二叉排序树具有的特点是左子树与右子树的高度差的绝对值不大于1。 ( )

10. 一棵具有257个结点的完全二叉树，它的深度为9。 ( )

值。 ( )

三、单选题 （共15题,每题2分,共30分）

1. 以下哪一个不是队列的基本运算？

A. 从队尾插入一个新元素

B. 从队列中删除第i个元素

C. 判断一个队列是否为空

D. 读取队头元素的值

数据结构

2. 栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈, 问下列哪一个序列是可能的出栈序列?

A. E、D、C、B、A、F

B. B、C、E、F、A、D

C. C、B、E、D、A、F

D. A、D、F、E、B、C

3. 循环双链表中在p所指结点之后插入结点s的操作是 。

A.p->next=s; s->prior=p; p->next->prior=s; s->next=p->next

B.p->next=s; p->next->prior=s; s->prior=p; s->next=p->next

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

D.s->prior=p; p->next=s; s->next=p->next ;p->next->prior=s

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

A.p->left B.p->right

C.p->right->right D.p->left->left

5. 二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存储时()元素的起始地址相同.

A.M[2][4]

B. M[3][4]

C.M[3][5]

D. M[4][4]

6. 一维数组与线性表的特征是

A.前者长度固定，后者长度可变

B.两者长度均固定

C.后者长度固定，前者长度可变

D.两者长度均可变

7. GetHead【GetTail【((a,b),(c,d))】】=== ().

A. c

B. (c)

C. (c,d)

D. d

8. 在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是

A.访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）

B.在第i个结点后插入一个新结点（1≤i≤n）

C.删除第i个结点（1≤i≤n）

D.将n个结点从小到大排序

9. 若一个栈的输入序列是1，2，3，…..，n，输出序列的第一个元素是n ，则第i个输出元素是 ().

A. n-i

数据结构

B. i

C. n-i+1

D. n-i-1

10. 在一个单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行的语句为().

A. s->next=p; p->next=s

B.s->next=p->next; p->next=s;

C. s->next=p->next; p=s;

D.p->next=s; s->next=p

11. 在n个结点的带头结点的单链表中，要在已知结点*p之后插入一个新结点，则其操作的时间复杂度为

A.O（1） B.O(n)

C.O (n+1) D.O(n2

12. 在n个结点的单链表中，算法的时间复杂度是O(n)的操作是

A.求链表的第i个结点

B.在地址为p的结点之后插入一个结点

C.删除开始结点

D.删除地址为p的结点的后继结点

13. 在n个结点的带头结点的单链表中，要在已知结点*p之前插入一个新结点，则其操作的时间复杂度为

A.O（1） B.O(n)

C.O (n+1) D.O(n2

14. 向 …… 此处隐藏：1486字，全部文档内容请下载后查看。喜欢就下载吧 ……