数据结构考试复习题

一、填空题

1、数据结构被形式地定义为（D, R），其中D是 的有限集合，R是D上的 有限集合。

2、一个算法的效率可分为 复杂性和 复杂性。

3、向一个长度为n的线性表的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 ___ _____个元素。

4、在一个循环队列中，队首指针指向队首元素的 位置。

5、在具有n个单元的循环队列中，队满时共有 个元素。

6、向栈中压入元素的操作是先 ，后 。 7、 称为空串； 称为空格串。 8、假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 ；末尾元素A57的第一个字节地址为 ；若按行存储时，元素A14的第一个字节地址为 ；若按列存储时，元素A47的第一个字节地址为 。

9、设一棵完全二叉树具有1000个结点，则此完全二叉树有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。 10、线性有序表（a1，a2，a3，?，a256）是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 次。设有100个结点，用二分法查找时，最大比较次数是 。

11、散列法存储的基本思想是由 决定数据的存储地址。 12、在线性结构、树结构和图结构中，前驱和后继结点之间分别存在着 、 和 的联系。

13、在线性表的单链表存储中，若一个元素所在结点的地址为p，则其后继结点的地址为 ，若假定p为一个数组a中的下标，则其后继结点的下标的 。 14、在初始化一个稀疏矩阵的函数定义中，矩阵形参应说明为 参数。 15、栈又称为 表，队列又称为 表。 16、后缀表达式“4 5+3*2 4+ *”的值为 。

17、一棵深度为5的满二叉树中的结点数为 个，一棵深度为3的满四叉树中的结点数为 个。

18、对关键字序列(50，34，92，19，11，68，56，41，79)进行直接插入排序，当将第7个关键字56插入到当前的有序子表中时，为寻找插入位置需进行 ___ ______次关键字之间的比较。

19、从一棵二叉排序树中查找一个元素时， 若元素的值等于根结点的值，则表明 ，若元素的值小于根结点的值，则继续向 查找，若元素的大于根结点的值，则向 查找。

第1页/共15页

20、当向一个小顶堆插入一个具有最小值的元素时，该元素需要逐层 调整，直到被调整到 位置为止。

21、对于一个具有n个顶点的图，若采用邻接炬阵表示，则矩阵大小为 。

22、对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为 和 。

23、从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为 和 。

24、每次从无序中表示顺序取出一个元素，把插入到有序表中的适当位置，此种排序方法叫做___ _______排序，每次从无序中表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做____ _______排序。

25、若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为 。 26、在一棵二叉排序树中,每个分支点的左子树上所有结点的值一定___ ___该结点的值,右子树上所有结点的值一定___ __________该结点的值。

27、在归并排序中，进行每趟归并的时间复杂度为 ，整个排序过程的时间复杂度为 ，空间复杂度为 。

28、在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是___ ___和________ __________。

29、在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度(考虑等概率 )为______。

30、已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是______。

31、如果入栈序列是1，3，5，?，97，99，且出栈序列的第一个元素为99，则出栈序列中第30个元素为______。

32、假设以行优先顺序存储三维数组A[5][6][7]，其中元素A[0][0][0]的地址为1100，且每个元素占2个存储单元，则A[4][5][6]的地址是______。

第2页/共15页

33、已知一棵二叉树的先序序列为ABCD，中序序列为BCAD，则它的后序序列为______。 34、在含n个顶点的连通图中，任意两个不同顶点之间的一条简单路径最多包含______条边。 35、对关键字序列(50，34，92，19，11，68，56，41，79)进行直接插入排序，当将第7个关键字56插入到当前的有序子表中时，为寻找插入位置需进行______次关键字之间的比较。

36、对有序表进行二分查找的过程可用判定树来描述，其判定树的形态只取决于______。 37、 若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为_______。

二、判断题

（ ）1. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

（ ）2.满二叉树中所有结点个数是2-1，其中k是树的深度。 （ ）3. 栈和队列的存储方式既可是顺序方式，也可是链接方式。

（ ）4.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （ ）5.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2－1个结点。

（ ）6. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。

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

（ ）8. 具有12个结点的完全二叉树有5个度为2的结点。

（ ）9. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 （ ）10. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

i

k-1

三、单项选择题

1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为： （A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构 2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是

（A）110 （B）108 （C）100 （D）120 3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：

（A） 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） （B） 在第i个结点后插入一个新结点（1≤i≤n） （C） 删除第i个结点（1≤i≤n） （D） 将n个结点从小到大排序

4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 个元素

（A）8 （B）63.5 （C）63 （D）7

5. 判定一个队列QU（最多元素为m0）为空队列的条件是

第3页/共15页

Ａ．QU->rear － QU->front = = m0 Ｂ．QU->rear － QU->front －1= = m0 Ｃ．QU->front = = QU->rear Ｄ．QU->front = = QU->rear+1 6. 链表是一种采用 存储结构存储的线性表；

（A）顺序 （B）链式 （C）星式 （D）网状 7. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:

（A）必须是连续的 （B）部分地址必须是连续的

（C）一定是不连续的 （D）连续或不连续都可以

8． 线性表Ｌ在 情况下适用于使用链式结构实现。

（Ａ）需经常修改Ｌ中的结点值 （Ｂ）需不断对Ｌ进行删除插入 （Ｃ）Ｌ中含有大量的结点 （Ｄ）Ｌ中结点结构复杂 9. 若已知一个栈的入栈序列是1，2，3，?，n，其输出序列为p1，p2，p3，?，pn，若

p1=n，则pi为

Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定

10、在一个长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n）时，需要从前向后依次前移动 个元素。 A n-i B n-i+1 C n-i-1 C i

11、由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为_________

A、24 B、48 C、72 D、53

12、假定一个顺序队列的队首和队尾指针分别为f和r，则判断队空的条件为 。 A f+1= =r B r+1= =f C f= =0 D f= =r

13、从堆中删除一个元素的时间复杂度为 。 A O（1） B O（n）

C O（1og2n） D O（nlog2n）

14、若需要利用形参直接访问实参，则应把形参变量说明为 参数。

A．指针 B．引用 C．值

15.数据元素及其关系在计算机存储器内的表示，称为数据的( ) A.逻辑结构 B.存储结构 C.线性结构 D.非线性结构

16.某带头结点的单链表的头指针为head，判定该链表为非空的条件是( )

第4页/共15页

A.head==NULL B.head->next==NULL C.head!=NULL D.head->next!=NULL 17.导致栈上溢的操作是( )

A.栈满时执行的出栈 B.栈满时执行的入栈 C.栈空时执行的出栈 D.栈空时执行的入栈

18.设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q为空队列的条件是( )

A.(rear-front)%m= =1 B.front= =rear

C.(rear-front)%m= =m-1 D.front= =(rear+1)%m

19.假设S=″I AM A STUDENT″，则运算substr(S,4,8)的结果为( ) A.″M A S″ B.″M A STUD″ C.″A STUDEN″ D.″STUD″

20.假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在( ) A.BT[i/2] B.BT[2*i-1] C.BT[2*i] D.BT[2*i+1] 21.连通图是指图中任意两个顶点之间( ) A.都连通的无向图 B.都不连通的无向图 C.都连通的有向图 D.都不连通的有向图

22.对记录序列(314，298，508，123，486，145)依次按个位和十位进行两趟基数排序之后所得结果为( )

A.123，145，298，314，486，508 B.508，314，123，145，486，298 C.486，314，123，145，508，298 D.298，123，508，486，145，314 23.在待排关键字序列基本有序的前提下，效率最高的排序方法是( ) A.直接插入排序 B.快速排序 C.直接选择排序 D.归并排序

24．下列排序算法中，（）算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。

A、堆排序 B、冒泡排序 C、快速排序 D、SHELL排序

25．已知一个有向图如右所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序

第5页/共15页

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