《数据结构导论》复习题

数据结构导论摹拟试题

一、考试题型及分值分布：

、单项选择题本大题共小题，每小题分，共分

、填空题本大题共小题，每小题分，共分

、应用题本大题共小题，每小题分，共分

、算法设计题本大题共小题，每小题分，共分

二、单项选择题和填空题样题参考

（一）单项选择题

在二维数组中，每一个数组元素同时处于（）个向量中。

已知单链表长度为，单链表长度为，它们分别由表头指针所指向，若将

整体连接到的末尾，其时间复杂度应为（）。

假定一个链式队列的队头和队尾指针分别为和，则判断队空的条件为

若让元素挨次进栈，则出栈次序不可能浮现种情况。

图的广度优先搜索类似于树的（）遍历。

先根中根后根层次

下面程序段的时间复杂度为。

设有两个串和，求在中首次浮现的位置的运算叫做（）«

求子串模式匹配串替换串联接

利用双向链表作线性表的存储结构的优点是（）。

便于单向进行插入和删除的操作便于双向进行插入和删除的操作

节省空间便于销毁结构释放空间

设链式栈中结点的结构为（）,且是指向栈顶的指针。若想在链式栈

的栈顶插入一个由指针所指的结点，则应执行操作。

一棵具有个结点的彻底二叉树的高度为。假定空树的高度为。

一个有个顶点和条边的无向图一定是的。

.连通.不连通.无回路.有回路

在一个长度为的顺序表的任一位置插入一个新元素的时间复杂度为（）。

已知广义表为,从中取出原子的运算是（）。

1

在一棵树的静态双亲表示中，每一个存储结点包含个域。

有向图中的一个顶点的度数等于该顶点的。

.入度.出度

.入度与出度之和.入度出度2

与邻接矩阵相比，邻接表更适合于存储。

.无向图.连通图.稀疏图.稠密图

较快的数据搜索方法是（）搜索方法。

顺序折半单链散列

在闭散列表中，散列到同一个地址而引起的“堆积”问题是由于（）引起的。

同义词之间发生冲突非同义词之间发生冲突

同义词之偶尔非同义词之间发生冲突散列表“溢出”

根据个元素建立一个有序单链表的时间复杂度为（）»

假定一个顺序存储的循环队列的队头和队尾指针分别为和，则判断队

空的条件为。

假定一棵二叉树的第层上有个结点，则第层上最多有个结点。

对于具有条边的无向图，它的邻接表中共有个边结点。

图的深度优先搜索遍历类似于树的（）次序遍历。

先根中根后根层次

.栈最多能容纳个元素。现有个元素按...............的顺序进栈问下

列哪一个序列是可能的出栈序列

.将一棵有个结点的彻底二叉树从根这一层开始，每一层从左到右挨次对结点进

行编号，根结点编号为，则编号为的结点的左孩子的编号为：

对下列关键字序列用快速排序法进行排序时，速度最快的情形是：

.对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为

顺序表用头指针表示的单循环链表

用尾指针表示的单循环链表单链表

.假设以第一个元素为分界元素，对字符序列（

）进行快速排序，则第一次划分的结果是：

.下面是三个关于有向图运算的叙述:

2

（）求有向图结点的拓扑序列，其结果必然是惟一的

（）求两个指向结点间的最短路径，其结果必然是惟一的

（）求网的关键路径，其结果必然是惟一的

其中哪个（些）是正确的？

惟独（）（）和（）都正确都不正确

.若进栈序列为，则通过入出栈操作可能得到的的不同罗列个数为

以下关于广义表的叙述中正确的是：

广义表是由个或者多个单元素或者子表构成的有限序列

广义表至少有一个元素是子表

广义表不能递归定义

广义表不能为空表

排序时扫描待排序记录序列，按次比较相邻的两个元素的大小，逆序时就交换位置

这是哪种排序方法的基本思想？

堆排序直接插入排序快速排序冒泡排序

.己知一个有向图的邻接矩阵表示，要删除所有从第个结点发出的边，应该:

将邻接矩阵的第行删除将邻接矩阵的第行元素全部置为

将邻接矩阵的第列删除将邻接矩阵的第列元素全部置为

.有一个含头结点的双向循环链表,头指针为则其为空的条件是：

在顺序表中，用折半法查找关键

码值，所需的关键码比较次数为:

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

从队尾插入一个新元素从队列中删除第个元素

判断一个队列是否为空读取队头元素的值

.对包含个元素的哈希表进行查找，平均查找长度为：

不直接依赖于

.将一棵有个结点的彻底二叉树从根这一层开始，每一层从左到右挨次对结点进

行编号，根结点编号为，则编号最大的非叶结点的编号为：

.某二叉树结点的中序序列为、,后序序列为、

,则其左子树中结点数目为：

.下面是顺序存储结构的优点。

存储密度大插入运算方便

查找方便适合各种逻辑结构的存储表示

.下面关于串的叙述中，是不正确的。

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

模式匹配是串的一种重要运算串既可以采用顺序存储，也可以采用链式

存储

.的邻接矩阵是对称矩阵。

有向图无向图网网

.用链式方式存储的队列，在进行删除运算时，。

仅修改头指针仅修改尾指针

头、尾指针都要修改头、尾指针可能都要修改

3

.二叉树的先序遍历和中序遍历如下，则该二叉树右子树的树根是=

先序序列：中序序列：

.下面方法可以判断出一个有向图中是否有环。

深度优先遍历拓朴排序求最短路径求关键路径

.从未排序序列中挨次取出一个元素与己排序序列中的元素挨次进行比较，然后将其

放在已排序序列的合适位置，该排序方法称为排序法。

插入选择冒泡都不是

.一个栈的入栈序列是，则栈的不可能的输出序列是。

.个节点的彻底二叉树，编号为的节点是叶子结点的条件是•

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

个元素。

.在一个单链表中，若要在指针所指结点的后面插入一个由指针所指向的结

点，则执行O

.对一个满二叉树，个树叶，个结点，深度为，则有

.在所有排序方法中，关键字比较的次数与记录的初始罗列次序无关的是O

选择排序冒泡排序插入排序希尔排序

.用链式方式存储的队列，在进行插入运算时，。

仅修改头指针仅修改尾指针

头、尾指针都要修改头、尾指针可能都要修改

.在一个长度为的顺序存储的线性表中，向第个元素（＜W）插入一个新

元素时，需要从后向前挨次后移个元素。

.一个栈的入栈序列是，则栈的不可能的输出序列是。

.个顶点的有向图最多有条弧。

.假定一个链队的队首和队尾指针分别为和，则判断队空的条件

为。

.若某线性表中最常用的操作是提取第个元素及找第个元素的前驱元素，则采用

（）存储方式最省时间。

单链表双链表单向循环链表顺序表

.将含有个结点的彻底二叉树从根开始自上向下，每层从左到右挨次编号，且设

根结点的编号为，则编号的结点的双亲的编号为（）。

无法确定

单循环链表的主要优点是（）。

4

再也不需要头指针了

已知某结点的位置后，很容易找到其前驱

在进行插入、删除运算时，能更好地保证链表不断开

从表中任一结点出发都能扫描到整个链表

一个栈的入栈顺序是................则此栈不可能的输出顺序为（）。

串是一种特殊的线性表，其特殊性表现在（）。

可以顺序存储数据元素是一个字符

可以链式存储数据元素是多个字符

个顶点的无向图中最多有（）条边。

个顶点的无向图中，至少有（）条边才干保证是一个连通图。

.若某线性表中最常用的操作是删除第个元素，则不宜采用（）存储方式。

单链表双链表单向循环链表顺序表

.在一棵彻底二叉树的顺序存储方式中，若编号的结点有右孩子，则其右孩子的编

号为（）。

按照二叉树的定义，具有个结点的二叉树有（）种不同形态。

在长为的顺序表中，删除第个元素WW需要向前挪移（）个元

素。

一个队的入队顺序是、、、、，则此队的出队顺序为（）o

栈是一种特殊的线性表，其特殊性表现在（）。

可以顺序存储只能从端点进行插入和删除

可以链式存储可以在任何位置进行插入和删除

一棵二叉树中，第层上最多有（）个结点。

一棵有个结点的二叉树，其高度最小为（）层。

有向图中，所有顶点入度和是所有顶点出度和的（）倍。

（二）填空题

数据元素之间存在的相互关系称为,0

数据结构从逻辑上分为，结构和结构。

线性表的顺序存储结构称为。

所有插入在表的一端进行，而所有删除在表的另一端进行的线性表称为.

深度为的二叉树至少有个结点。

折半查找要求待查表为表。

个记录按其关键字大小递增或者递减的次序罗列起来的过程称为

5

存储数据时不仅要存储数据元素的还要存储元素之间的相互

.将一棵有个结点的彻底二叉树按层编号，则编号为的结点，其双亲（）

的编号为。

、一个字符串相等的充要条件是_______和,

、在有向图的邻接表和逆邻接表表示中，每一个顶点的边链表中分别链接着该顶点的

所有和结点。

、在一个长度为的顺序表中向第个元素（W）之前插入一个新元素时，需

要向后挪移________个元素。

、是只允许在表的一端进行插入，而在另一端进行删除的线性表。

、设主串="”模式串="”则第次匹配成功。

、在一棵二叉树中，第层上的结点数最多为________o（根的层次为）

、假设一个阶的上三角矩阵按列优先顺序压缩存储在一维数组中，其中［］存储

矩阵中第个元素，则中存放的元素是________。

、有个结点的二叉链表中，其中空的指针域为，指向孩子的指针个数为

、二叉树后序遍历的顺序是,则该二叉树的根结点是=

、对于一个具有个顶点和条边的无向图，若采用邻接表表示，则整个邻接表中的结

点总数是.

、在单链表上难以实现的排序方法有_______和。

查找法的平均查找长度与元素个数无关。

、在有个元素的顺序表的任意位置插入一个元素所需挪移结点的平均次数为

、是插入和删除元素都在表的同一端进行的线性表。

、广义表=（）则其长度为o

、在树中，除跟结点外，其他结点都有且惟独一个结点。

、在串““中，以为首字符的子串有个。

、广度优先搜索遍历类似于树的按，遍历的过程。

、已知一棵彻底二叉树中共有个结点为，则该树中共有个叶子结点。

、在有序表（）中二分查找关键字时所需进行的关键字比较次

数为

、两个长度分别和（）的排好序的表归并成一个排好序的表，至少要进行次

键值比较。通常从四个方面评价算法的质量:和

一个算法的时间复杂度为，其数量级表示为。

若用链表存储一棵二叉树时，每一个结点除数据域外，还有指向左孩子和右孩子的两个

针。在这种存储结构中，个结点的二叉树共有个指针域，其中有个指针

域是存放了地址，有个指

、对于一个具有个顶点和条边的有向区q和无向图，在其对应的邻接表中，所含边结点

分别有个和个。

、在一个具有个顶点的无向彻底图中，包含有条边，在一个具有个顶点的有

向彻底图中，包含有条边。

35、在快速排序、堆排序、归并排序中,，排序是稳定的。

36、37.中序遍历二叉排序树所得到的序列是____________序列。

快速排序的最坏时间复杂度为,平均时间复杂度为。

设一组初始记录关键字序列为，，,,,,,,则利用筛选法建立

的初始堆为

.数据的物理结构主要包括和两种情况。

6

设一棵彻底二叉树中有个结点，则该二叉树的深度为；若用二叉链表作

为该彻底二叉树的存储结构，则共有个空指针域。

、设输入序列为、、，则经过栈的作用后可以得到种不同的输出序列。

、设有向图用邻接矩阵作为存储结构，则该邻接矩阵中第行上所有元素之和

等于顶点的，第列上所有元素之和等于顶点的。设哈夫曼树中共有个结点，

则该哈夫曼树中有个度数为的结点。

设有向图中有个顶点条有向边，所有的顶点入度数之和为，则和的关系为

遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或者

后序）。

设查找表中有个元素，如果用二分法查找方法查找数据元素，则最多需要比较

次就可以断定数据元素是否在查找表中。

不管是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为

设有个结点的彻底二叉树，如果按照从自上到下、从左到右从开始顺序编号，则第

个结点的双亲结点编号为，右孩子结点的编号为。

设一组初始记录关键字为，，，，，，，则以记录关键字为基准的

一趟快速排序结果为。

设有向图中有向边的集合.........................................则该图

的一种拓扑序列为。

下列算法实现在顺序散列表中查找值为的关键字，请在下划线处填上正确的语句。

下列算法实现在二叉排序树上查找关键值，请在下划线处填上正确的语句。

设有个无序的记录关键字，则直接插入排序的时间复杂度为，快速排序的平

均时间复杂度为

设指针变量指向双向循环链表中的结点，则删除结点需要执行的语句序列为

（设结点中的两个指针域

7

分别为和）«根据初始关键字序列,,,,建立的二叉排序树的

高度为