数据结构模拟试题三及答案 .pdfVIP

数据结构模拟试题三

一．判断题（每小题1分，共10分）

1.逻辑结构不同的数据，要采用不同的存储方法来存储。

2.单链表中的结点只有后继，没有前驱。

3.栈和队列具有相同的逻辑特性。

4.二叉树中结点之间的相互关系不能用二元组来表示。

5.关键路径是由权值最大的边构成的。

6.在表示矩阵的三元组顺序表中，各元素的排列顺序与矩阵元素值的大小无关。

7.在广义表中，每个原子必须是单个字符。

8.在平衡二叉排序树中，每个结点的平衡因子值是相等的。

9.只有在线性表的初始状态为逆序排列的情况下，起泡排序过程中，元素的移动次数才会

达到最大值。

10.在B+树上可以进行顺序查找。

二．填空题（每空1分，共10分）

1.若用不带表头结点的单链表来表示链接队列，则只有在________情况下，插入操作既要

修改队尾指针的值，也要修改队头指针的值;只有在________情况下，删除操作仅需修改

队首指针的值，不需修改队尾指针的值。

2.无向图中边的数目等于邻接矩阵中___________。

3.在各元素查找概率相等的情况下，在含有12个元素的二叉排序树上查找其中一个元素，

元素间的平均比较次数至少是____次，至多是____次。

4.对12个元素进行快速排序，排序码的比较次数最多是___次。

5.对B+树来说，若某个非根分支结点中有6个关键字，则在它的某个孩子结点中至少有

_____个关键字，至多有_____个关键字。

6.如果在根结点中要查到要找的关键字，则对于B-树来说，下一步应该_________，而对

于B+树来说，下一步应该_________。

三．单选题（每题2分，共20分）

1.线性结构采用链式存储，________。

A．对插入、删除结点的操作较为有利B．不利于进行顺序访问

C．逻辑上相邻的结点在存储器中也相邻D．可以用一些不连续的存储区域来存放一个结点

n

2.某算法的时间复杂度为O（2），表明该算法的________。

nn

A．执行时间与2成正比B．执行时间等于2

nn

C．问题规模是2D．问题规模与2成正比

3.在长度为n的_________上，删除最后一个元素，其算法的时间复杂度是O(n)。

A．只有表头指针的循环双向链表B．只有表头指针的非循环双向链表

C．只有表尾指针的非循环双向链表D.只有表尾指针的循环双向链表

4.在4个元素的进栈序列给定以后，由这4个元素构成的可能出栈序列共有________种。

A．14B.16C.17D.24

5.在任何一棵二叉树中，如果结点a有左孩子b、右孩子c，则在结点的前序序列、中序序

列、后序序列中，_____________。

A．结点b一定在a的前面B．结点a一定在结点c的前面C．结点b一定在结点c的前

面D．结点a一定在结点b的前面

6.若二叉树中结点的中序序列是abcdef，则结点的前序序列不可能是_____________。

A．dbacefB.acbedfC.efbacdD.bafdce

7.对稀疏矩阵采用压缩存储，其优点之一是可以_____________。

A．减少非零元素的存储空间B．不减少访问非零元素所需时间

C．减少矩阵的存储空间D．降低非零元素间逻辑关系的复杂程度

8.设待查找元素关键字的值是47，且已存入变量k中，如果在查找过程中，和k进行比较

的关键字值依次是82,72,36,84,47，则所采用的查找方法可能是____________。

A．顺序查找B．分块查找C．折半查找D．平衡二叉排序树查找

9．在线性表中元素很多且各元素逆序排列的情况下，执行_______排序，元素的移动次数最

少。

A．直接插入B．起泡C．简单选择D．折半插入

10.8阶方阵，每个元素