数据结构模拟题二

数据结构模拟题二

一、选择题（本大题共20小题，每题2分，共40分。）

1．抽象数据类型的三个组成部分分别为（ A ）

A．数据对象、数据关系和基本操作 B．数据元素、逻辑结构和存储结构 C．数据项、数据元素和数据类型 D．数据元素、数据结构和数据类型

2．以下数据结构中，哪一个是线性结构（ D ）？

A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串

3．线性表是具有 n个（ C ）的有限序列（n>0）。

A．表元素 B．字符 C．数据元素 D．数据项 E．信息项

4．若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为（ B ）

A．无头结点的双向链表

B．带尾指针的循环链表

C．无头结点的单链表 D．带头指针的循环链表

5．将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为（ B ） A．O(1) B．O(m) C．O(n) D．O(m+n)

6．上溢现象通常出现在（ A ） A．顺序栈的入栈操作过程中

B．顺序栈的出栈操作过程中

C．链栈的入栈操作过程中 D．链栈的出栈操作过程中

7. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p 1,p2,p3，…，pN,若p N是n，则p i是( D )。

A. i B. n-i C. n-i+1 D. 不确定

8. 用单链表表示的链式队列，队头在链表的（ A ）位置。 A．链头 B．链尾 C．链中

9. 若用一个大小为6的数组来实现循环队列，且当前 rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和 front的值分别为多少？( B ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1

10．下面关于串的的叙述中，哪一个是不正确的？（ B ）

A．串是字符的有限序列 B．空串是由空格构成的串

C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 11．若串str=”Software”，其子串的数目是（ D ） A．8 B．9 C．36 D．37

12. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（ B ）

A. 808 B. 818 C. 1010 D. 1020

13．设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，all为第一个元素，其存储地址为1000，每个元素占一个地址单元，则a85的地址为（ C ） A．1012 B．1017 C．1032 D．1039

14．若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是( B ) A.树中没有度为2的结点 C.树中非叶结点均只有左子树

B.树中只有一个根结点 D.树中非叶结点均只有右子树

15．有n个叶子的哈夫曼树的结点总数为（ D ）。

A．不确定 B．2n C．2n+1 D．2n-1

16．在下图中，从顶点1出发进行深度优先遍历可得到的序列是( B ) A.1 2 3 4 5 6 7 B.1 4 2 6 3 7 5 C.1 4 2 5 3 6 7 D.1 2 4 6 5 3 7

17．在图G中求两个结点之间的最短路径可以采用的算法是( A ) A.迪杰斯特拉（Dijkstra）算法

B.递归算法

C.普里姆(Prim)算法 D.广度优先遍历(BFS)算法

18．对下面有向图给出了四种可能的拓扑序列，其中错误的．．是（ C ）

A．1，5，2，6，3，4 3，4

C．5，1，6，3，4，2 4，3

B．1，5，6，2，D．5，1，2，6，

19．下列序列中，不构成堆的是（ D ） ．

A．（1，2，5，3，4，6，7，8，9，10） B．（10，5，8，4，2，6，7，1，3） C．（10，9，8，7，3，5，4，6，2） D．（1，2，3，4，10，9，8，7，6，5）

20．已知二叉树结点关键字类型为字符，下列二叉树中符合二叉排序树性质的是( D )

二、填空题（本大题共10小题，每题2分，共20分。）

1．下面程序段的时间复杂度为________。(n>1) sum=1；

for (i=0; sum

sum+=1;

2．使用一个100个元素的数组存储循环队列，如果采取少用一个元素空间的方法来区别循环队列的队空和队满，约定队头指针front等于队尾指针rear时表示队空。若为front=8，rear=7，则队列中的元素个数为___________。

3．3个结点可以组成___________种不同树型的二叉树。

4．用5个权值{3, 2，4，5，1}构造的哈夫曼(Huffman)树的带权路径长度是___________。

5．若无向图G中有n个顶点m条边，采用邻接矩阵存储，则该矩阵中非0元素的个数为___________。

6．已知有向图如下所示，其中顶点A到顶点C的最短路径长度是____。

7．在含有n个顶点的连通图中，任意两个不同顶点之间的简单路径的最大长度为_______。

8．影响排序效率的两个因素是关键字的 次数和记录的移动次数。

9．用_______排序方法对关键字序列（20，25，12，47，15，83，30，76）进行排序时，前三趟排序的结果为：

20，12，25，15，47，30，76，83 12，20，15，25，30，47，76，83

12，15，20，25，30，47，76，83

10．一个有序表为(1，3，9，12，32，41，45，62，75，77，82，95，100)，当采用折半查找方法查找值32时，查找成功需要的比较次数是

三、简答题（本大题共5小题，每题6分，共30分。）

1．已知二叉树如下，请画出该二叉树对应的森林。

2．已知带权图G如下图所示，使用普里姆算法，从点A开始，按步骤画出图G的一棵最小生成树。

3．如下AOE图所示，求出完成此工程的关键路径，以及完成此工程所需的最少天数。

4．设输入的关键字序列为：22,41,53,33,46,30,13,01,67，要求使用快速排序实现元素递增有序，写出每趟排序过程。

5．已知散列表的地址空间为A[0..12]，散列函数H（k）=k mod 11，采用线性探测法处理冲突。请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并计算出在等概率情况下查找成功时的平均查找长度。

四、算法题（本大题共2小题，每题5分，共10分。）

1．算法阅读题

设有单链表类型定义如下： typedef struct node {

int data;

struct node *next; } *LinkList;

阅读下列算法，并回答问题：

void f33(LinkList head, int A, int B) {

LinkList p=NULL;

While (head !=NULL) {

if (head->data>A&&head->data

p=head; head=head->next; }

if (p !=NULL)

printf(\

}

(1)已知链表h如下图所示，给出执行f33(h，5，8)之后的输出结果（2分）；

结果为7

(2)简述算法f33的功能（3分）。

若存在，则输出链表中最后一个大于A小于B的值。

2．算法设计题

设计算法将一个带头结点的单链表 A分解为两个具有相同结构的链表B、C，其中 B表的结点为 A表中值小于零的结点，而 C表的结点为 A表中值大于零的结点（链表 A的元素类型为整型，要求B、C表利用 A表的结点）。

本文来源：https://www.bwwdw.com/article/vudt.html