数据结构复习题

1、v1.0 可编辑可修改判断题（下列各题，正确的请在前面的括号内打；错误的打）第1章）（1）数据的逻辑结构与数据元素本身的内容和形式无关。）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。）（3）数据元素是数据的最小单位。）（4）数据项是数据的基本单位。）（5）数据的逻辑结构和数据的存储结构是相同的。）（6）数据的逻辑结构是各数据元素之间的逻辑关系，是用户按使用需要而建立的。）（7）数据的物理结构是指数据在计算机内实际的存储形式。）（8）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。）（9）数据的存储结构是数据的逻辑结构的存储映像。）（10）算法是对解题

2、方法和步骤的描述。第2章）（1）链表的物理存储结构具有同链表一样的顺序。（）（2）链表的每个结点都恰好包含一个指针域。（）（ 3）线性表中的元素可以是各种各样的， 但同一线性表中的数据元素具有相同的特性， 因此属于同一数据对象。（）（ 4）链表的删除算法很简单， 因为当删除链中某个结点后， 计算机会自动地将后续的 各个单元向前移动。）（5）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。）（ 6）数组元素的存储位置是下标 的线性 函数。）（7）在单链表中，元素的存储位置用指针联系，所以可以从头结点开始查找任何一个）（8）顺序存储线性表的插入和删除操作不需要付出很大的代价，因为平均每次移

3、动仅半的元素。（）（9）顺序存储方式的优点是存储密度大，插入、删除效率高。（）（10）在单链表中，要取得某个元素，只要知道该元素的指针即可，因此单链表是随 机存取的存储结构。第3章）（ 1 ）大多数排序算法都有比较关键字大小和改变指向记录的指针或移动记录本身两 种基本操作。）（ 2）快速排序在 任何情况 下都比 其它排 序方法速 度快。）（ 3）快速排序算法在每一趟排序 中都能 找到一个 元素放 在其最 终位置上v1.0 可编辑可修改）（4）如果某种排序算法不稳定，则该排序方法就没有实际应用价值。）（ 5）对 n 个记录的进行快速排序，所需要的平均时间是O（ nlog 2n）。）（6）冒泡排序

4、是不稳定的排序。2）（ 7）冒泡排序的时间复杂度是 O（n2）。 ）（8）堆排序所需的时间与待排序的记录个数无关。）（9）对快速排序来说，初始序列为正序或反序都是最坏情况。）（ 10）对于 n个记录的集合进行归并排序，所需的平均时间为O （nlog 2n）。第4章）（ 1）栈是运算受 限制的线 性表。）（ 2）在栈空的情 况下，不 能作出 栈操作 ，否则产 生下溢 出。 ）（3）栈一定是顺序存储的线性结构。）（ 4）空栈就是所有元素都为 0 的栈。）（5）一个栈的输入序列为： A， B，C，D，可以得到输出序列： C， A，B，D。 ）（6）一个栈的输入序列为： A，B，C，D，通过入出栈操作

5、可以输出序列： A，B，C，D。）（7）在 C 或 C+语言中设顺序栈的长度为 MAXLEN，则 top=MAXLEN时表示队满。）（8）链栈与顺序栈相比，其特点 之一是 通常不会出现栈 满的情 况。）（9）在栈中插入或删除一个元素应遵守的“后进先出”的原则。）（ 10 ）进位制的换 算算法是栈的应用。）（11）队列是限制 在两端进行操作的线性表。）（12）判断顺序队列为空的标准是头指针和尾指针均指向同一个结点。）（13）在链队列做出队操作时，会改变front指针的值。）（14）在循环队列中，若尾指针rear大于头指针 front，其元素个数为rear-）（15）队列是一种“先进先出”的线性表

6、。）（16）在循环链队列中无上溢出现象。）（17）栈和队列都是顺序存储的线性结构。）（18）栈和队列都是属于线性结构。）（19）顺序队和循 环队的队满和队空的判断条件是一样的。）（20）在队列中插 入或删除一个元素应遵守的 ”先 进先出”的原则。第5章）（1）串的长度是指串中不同字符的个数。）（ 2）串是 n 个字母的有限序列。）（3）空串不等于空格串。）（4）如果两个串含有相同的字符，则说明它们相等。）（5）如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。v1.0 可编辑可修改（）（6）串的堆分配存储是一种动态存储结构。（）（ 7）“ DT”是“ DATA”的子串。（）（8

7、）空 串 与空格串 是相同 的。（）（9）串中任意个字符组成的子序列称为该串的子串。（）（ 10）子串的定位运算称为模式匹配。（）（ 11） n 维的多维数组可以视为 n-1 维数组元素组成的线性结构。（）（12）稀疏矩阵中非零元素的个数远小于矩阵元素的总数。（）（13）若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。（）（14）在稀疏矩阵的三元组表表示法中，每个三元组表示矩阵中数据元素的行号、列 号和值。（）（ 15）上三角矩阵主对角线以上（不包括主对角线中的元素），均为常数 C。（）（16）对称矩阵、三角矩阵、稀疏矩阵都可以进行压缩存储。（

8、）（17）任何矩阵都可以进行压缩存储。（）（18）在稀疏矩阵的三元组表表示法中，每个三元组表示矩阵中非零元素的行号、列 号和值。（）（19）数组元素可以由若干个数据项组成。（ ） （20 ）稀 疏 矩 阵 压 缩 存 储 就 是 为 矩 阵 中 非 零 元 素 分 配 一 个 存 储 空 间 。第6章（）（ 1）树结构中每 个结点最 多只有 一个直 接前驱。（）（ 2）完全二叉树 一定是满 二查树 。 （）（3）由树转换成二叉树，其根结点的右子树一定为空。（）（4）在前序遍历二叉树的序列中， 任何结点的子树的所有结点都是直接跟在该结点之 后。）（5）用一维数组来存储二叉树时，总是以前序遍历存储

9、结点。）（6）已知二叉树的前序遍历和后序遍历并不能唯一确定这棵二叉树，因为不知道根结 点是哪一个。）（7）二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。 ）（8）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。 ）（9）不使用递归，也可以实现二叉树的前序、中序和后序遍历。 ）（10）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。第7章）（1）图可以没有边，但不能没有顶点。v1.0 可编辑可修改（）（2）在无向图中， （ V1， V2）与（ V2，V1）是两条不同的边。 （）（3）邻接表只能用于有向图的存储。（）（ 4）用邻接矩阵法存储一个图时， 在不考虑压

10、缩存储的情况下， 所占用的存储空间大 小只与图中顶点个数有关，而与图的边数无关。（）（5）一个图的邻接矩阵表示是唯一的。（）（ 6）有向图不能进行广度优先遍历。（）（ 7）一个图的最小生成树是该图所有生成树中权最小的生成树。（）（8）存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角） 部分就可以了。（）（9）有向图的邻接矩阵一定是对称的。 （）（10）一个图的深度优先遍历的序列是唯一的。第8章）（1）二分查找法要求待查表的关键字值必须有序。）（2）哈希法是一种将关键字转换为存储地址的存储方法。）（3）在二叉排序树中，根结点的值都小于孩子结点的值。）（4）对有序表而言采用二分

11、查找总比采用顺序查找法速度快。）（5）二叉排序树是一种特殊的线性表。）（6）散列存储法的基本思想是由关键字的值决定数据的存储地址。）（7）哈希法的查找效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。）（8）一般说来用哈希函数得到的地址，冲突不可能避免，只能尽可能减少。）（9）选择好的哈希函数就可以避免冲突的发生。）（10）在二叉排序树上删除一个结点时，不必移动其它结点，只要将该结点的父结点 的相应的指针域置空即可。填空题第1章1数据结构是一门研究非数值计算程序设计中计算机的操作对象以及它们之间的关系和运算的学科。2数据的存储结构形式包括：顺序存储、链式存储、散列存储 、索引存储 。3

12、数据结构按逻辑结构可分为两大类，它们分别是：线性结构和非线性 结构。4一个算法的空间复杂度是指该算法所耗费的存储空间 ，它是该算法求解问题规模 n的函数。5数据结构有逻辑结构和存储结构 两种结构。6数据的存储结构形式包括：顺序存储、链式存储、散列存储、索引存储 。v1.0 可编辑可修改7一个算法的效率可分为 时间效率和空间效率。8数据元素是数据的 基本单位。9数据结构主要研究数据的逻辑结构 、存储结构和算法。11数据的逻辑结构 是独立于计算机的。12数据结构被定义为 （D，R），其中 D 是数据的有限集合， R是 D上的 关系 的有限集 合。13树形结构结构中的元素之间存在一对多 的关系。14

13、若一个算法中的语句频度之和为T（ n） =125n+3nlog 2n，则算法的时间复杂度为O（ nlog 2n） 。15数据结构主要研究数据的逻辑结构、存储结构 和算法。第2章1顺序表中逻辑上相邻的元素在物理位置上必须 相连。2在单链表中要在已知结点 *P 之前插入一个新结点， 需找到 *P 的直接前趋结点的地址， 其 查找的时间复杂度为 O （n） 。3线性表是 n 个结点的有限 集合。4链表相对于顺序表的优点有插入、删除 方便；缺点是存储密度小。5链表相对于顺序表的优点有插入、删除方便；缺点是存储密度小 。6顺序表相对于链表的优点是：节省存储 和随机存取。7对于一个具有 n 个结点的单链表

14、， 在已知 p 所指结点后插入一个新结点的时间复杂度是 O （ 1） 。8在链表中逻辑上相邻的元素的物理位置不必 相连。9线性表中第一个结点没有直接前趋，称为开始 结点。10在顺序表中访问任意一个结点的时间复杂度均为O （1）。11在 n 个结点的单链表中要删除已知结点 *P，其时间复杂度为 O （1）。12在单链表中需知道头指针 才能遍历整个链表。13在一个单链表中，在指针p 所指向的结点之后插入指针 s 所指向的结点时，应执行s-next=p-next 和 p-next=s 操作。14在一个长度为 n 的顺序表中， 如果要在第 i 个元素前插入一个元素， 要后移 n- i +1 个 元素。

15、15在双向链表中， 每个结点都有两个指针域， 它们一个指向其前趋结点， 另一个指向其 后 继 结点。第3章v1.0 可编辑可修改1根据被处理的数据在计算机中使用不同的存储设备，排序可分为： 内排序和外排序。2评价排序算法优劣的主要标准是时间复杂性 和算法所需的附加空间。3插入排序、堆排序、归并排序中，排序是不稳定的有： 堆排序 。 4在对一组记录（ 54，38，96，23，15， 72，60，45，83）进行直接插入排序时，当把第7 个记录 60 插入到有序表时，为寻找插入位置需比较3 次。5对 n 个关键字进行冒泡排序，其可能的最小比较次数为：n-1 次。6内排序是指整个排序过程，全部在计算

16、机的内存 中进行。7大多数排序算法都有两个基本的操作：比较 和移动。8在插入排序和选择排序中，若初始数据基本正序，则选用插入排序 较好。9在排序前，关键字值相等的不同记录， 排序后相对位置变化的排序方法， 称为 不稳定 的排序方法。10若原始数据接近无序，则选用快速排序 最好。11对于 n个记录的集合进行归并排序，所需要的平均时间为：O （log 2n） 。12在插入排序、归并排序、快速排序中，排序是不稳定的有：快速排序 。13对一组记录（ 54，35，96，21，12，72，60，44，80 ）进行直接选择排序时，第四次选 择和交换后，未排序记录是 54 ， 72，60，96，80 。14对

17、于 n 个记录的集合进行，若对其进行快速排序，在最坏的情况下所需要的时间是 O（n2） 。15在最坏情况下，在第 i 趟直接插入排序中，要进行 i-1 次关键字的比较。第4章1在栈 中存取 数据遵 从的原则 是： 后进先 出 。2在有 n个元素 的栈中 ，进栈操 作的时 间复杂 度为 O （1）。3后进 先出的 线性表 称为 栈 。4在顺 序栈中 ，当 top=MAXLEN-1 时， 表示 栈满 。5. 栈是输入 、输出 受限制的 线性 表 。6在有 n个元素 的栈中 ，出栈操 作的时 间复杂 度为 O （1）。7在栈 结构中 ，允许 插入、删 除的一 端称为 栈顶 。8顺序栈 S存在数组 S

18、-data0.MAXLEN-1中，出栈操作时要执行的语句有： S-top 9在顺 序栈中 ，当栈 顶指针 top=-1 时，表示 栈空 。10 向一个栈顶指针为 top 的链栈插入一个新结点*p 时，应执行 p-next=top ； 和top=p ； 操作。11 同一栈的各元素的类型相同 。v1.0 可编辑可修改12栈只能在 栈顶 插入和删除元素。13已知顺序栈 S，在对 S 进行出栈操作之前首先要判断栈是否空 。14若进栈的次序是 A、 B、C、D、E，执行三次出栈操作以后，栈顶元素为B 。15从一个栈删除元素时，首先取出栈顶元素，然后再移动栈顶指针 。16 在队列中存取数据应遵从的原则是先

19、进先出 。17 设长度为 n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为O （ n ）。18 在队列中，允许插入的一端称为队尾 。19 设长度为 n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为0 （ 1） 。20 设循环队列的头指针front 指向队头元素，尾指针 rear 指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，则队空的标志为front=rear 。21 队列在进行出队操作时，首先要判断队列是否为空 。22 设循环队列的头指针front 指向队头元素，尾指针 rear 指向队尾元素后的一个空闲元素 ，队列的最大空间为 MAXLEN，

20、 则队满标志为front=（rear+1）%MAXLEN 。23 在一个链队列中，若队头指针为front ，队尾指针为 rear ，则判断该队列只有一个结点的条件为： front=rear & front NULL 。24 队列结构的元素个数是可变的 。25 设长度为 n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复杂度为0 （ 1） 。26 设长度为 n的链队列用单循环链表表示，若只设尾指针，则入队操作的时间复杂度为0 （ 1）。27 链队列为空时， LQ-front-next= NULL 。28 设循环队列的头指针front 指向队头元素，尾指针 rear 指向队尾元素后的一个

21、空 闲 元 素 ， 队 列 的 最 大 空 间 为 MAXLEN， 当 rearfront 时 ， 队 列 长 度 是 MAXLEN-front 。29 向一个循环队列中插入元素时，首先要移动队尾指针，然后再向指针所指位置写入 新的元素。30队列 Q经过 InitQueue （Q） ； InQueue （Q ，a）； InQueue （Q ， b） ； GetHead （Q ，x）后，v1.0 可编辑可修改x 的值是 a1长 度为零的 字符串称为 空串 。2在 串的运算 中， EqualStr(aaa ， aabb) 的值为 0。3串 的顺序存 储结构简称为 顺序串 。4串 的链式存 储结构简

22、称为 链式串 。5 求 子 串 函 数SubStr(Today is 30 July,2005,13,4) 的结 果是：July 。6设 S=A:/document/ ，则 len(s)= _ 20 。7由 零个或多 个字符组成的 有限序列 称为 字符串 (或 串)。8字符串按存储方式可以分为：顺序存储、链接存储和 堆分配存储 。9设 S=“ A:/mydocument/ ”，则 strlen(S)= 23。10在空串和空格串中，长度不为 0 的是 空格串 。11串 顺序存储紧凑格式的优点是：空间利用率高 , 对串的字符处理效率低。12 两个串相等是指两个串相长度等，且对应位置的 字符都相同

23、。13串 顺序 存储紧凑格式 的缺点是 对串的字符处理效率 低 。14 模式匹配成功的起始位置称为： 有效位移。15 所有模式匹配不成功的起始位置称为：无效位移 。16. 多 维数组的 顺序存储方式 有行优先 顺序存储和 列优先 顺序存储 两 种。17. 同 一数组中 各元素的长度 相等 。18. 在 多维数 组中，数 据元素的存放 地址可 以直 接 通过地 址计算公 式算 出 ，所以 多维数组是 一种 随机 存取结构。19. 在 n维数组中的每一个元素最多可以有n 个直接前驱。20. 输 出 二 维 数 组 Amn 中 所 有 元 素 值 的 时 间 复 杂 度 为O(m*n) 。数组元素a

24、0.20.3的实 际地址上 2000 ，元素长 度是4，则Loc1,2=2024 。21. 数 组的三元 组存储是对 稀疏矩阵 的压 缩存储22. 稀 疏矩阵的 三元组 有3 列。23. 稀 疏矩阵的 三元组中第1列存储 的是数 组中非 零元素所 在的 行数 。 阶对称矩阵，如果只存储下三角元素，只需要 n (n-1 )/2个存储单元。25. 稀 疏矩阵A如下 图所示 ，其非零 元素存 于三元 组表中， 三元组(4，1，5)按 行优先顺序 存储在 三元组 表的第6 项 。v1.0 可编辑可修改8 0 0 00 0A=0 11 0 00 00 0 0 60 00 3 0 07 0稀疏矩阵 A26

25、. 稀 疏疏矩阵 的压缩 存储方 法通常有 三元组表和 十字链 表 两 种。27 n 阶下 三角 矩阵，因 为对角 线的上 方是同一 个常数 ，需要 n （ n-1 ）/2+1 个 存储单元。28稀疏矩 阵中有 n 个非 零元素 ，则三元 组有n 行。29. 稀 疏矩阵的 三元组 中第 2 列存储的 是数组 中非零 元素所在 的 列 数 。30. 稀 疏矩阵的 三元组 中，第 3列存 储的是 稀疏数 组中的非零元素 。第6章1在树中，一个结点所拥有的子树数称为该结点的度 。2一棵含有 n 个结点的完全二叉树，它的高度是| log2n |+1。 （下取整）3度为零的结点为叶子结点（或叶结点） 。

26、4一棵深度为 h 的完全二叉树上的结点总数最少为 2 h-1 个。5树内各结点度的最大值称为 树的度 。6一棵深度为 h 的完全二叉树上的结点总数最多为 2 h-1个。7树中结点的最大层次称为树的 深度（或高度） 。8三个结点可以组成 2 种不同形态的树。9由树转换成二叉树时，其根结点没有 右子树 。10有 20个结点的完全二叉树，编号为10 的结点的左儿子结点的编号是 20 。11在树中，一个结点的直接子结点的个数称为该结点的度 。12由二叉树的后序和中序 遍历序列，可以唯一确定一棵二叉树。13给定如下图所示的二叉树，其前序遍历序列为：ABEFHCG 。v1.0 可编辑可修改14给定如下图所

27、示的二叉树，其层次遍历序列为：ABCEFGH2*i+1 。i 的结点， 该结点右孩子的编号为：第7章1图有： _ 邻接矩阵 _ 和邻接表等存储结构。2n个顶点 e 条边的图若采用邻接矩阵存储， 深度优先遍历算法的时间复杂度为：O（n2）3图的遍历有：深度优先搜和_ 广度优先搜 _ 等方法。4n 个顶点 e条边的图若采用邻接矩阵存储，则空间复杂度为：_ O （n2）_。5图有：邻接矩阵和邻接表 等存储结构。6若图 G中每条边都 _ 无 方向，则 G 为无向图。7在具有 n 个顶点的图的生成树中，含有n-1 条边。8有向图的边也称为 _ 弧 _ 。9图的邻接矩阵表示法是表示_ 顶点 之间相邻关系的

28、矩阵。10有向图 G用邻接矩阵存储，其第 i 行的所有元素之和等于顶点 i 的 _ 出度 。11图的深度优先遍历序列 _ 不是 唯一的。12设有一稀疏图 G，则 G采用 _ 邻接表 存储比较节省空间。13从图中某一顶点出发，访遍图中其余顶点，且使每一顶点仅被访问一次，称这一过程为 图的遍历（或遍历） 。14遍历图的两种基本方法是：深度优先遍历 和广度优先遍历。15有向图的邻接表表示适于求顶点的出度第8章1顺序查找法，表中元素可以任意 存放。2 散列表 查找法的平均查找长度与元素个数 n 无关。3快速排序是对冒泡 排序的一种改进。4在哈希函数 H（key）=key % P 中， P一般应取质数

29、10v1.0 可编辑可修改5二分查找的存储结构仅适用于顺序存储 结构，而且关键字有序的。6在分块查找方法中，首先查找索引 ，然后再查找相应的块。7二分查找法，表中元素必须按关键字有序 存放。8在分块查找方法中，表中元素每块内的元素可以任意存放 ，块与块之间必须有序存放。9顺序查找、二分查找、分块查找都属于静态 查找。10顺序查找法，其平均查找长度为：（n+1）/2 。11理想情况下，在散列表中查找一个元素的时间复杂度为：O （1） 。12散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突 的方法。13二叉排序树是一种动态 查找表。14处理冲突的两类主要方法是开放定址法和拉链法 （或

30、链地址法） 。15设有 100 个元素，用二分查找时，最少的比较次数是1 次。三选择题第1章1数据结构通常是研究数据的（）及它们之间的相互联系。2A. 存储结构和逻辑结构执行下列语句的时间复杂度为：B.存储和抽象C.联系和抽象 D.联系与逻辑B ）。s=0;for (i=1;i=n; i+)s=s+i;3A. O ( 1)B. On）C. O2n2)D. On3)数据结构中，在逻辑上可以把数据结构分成：）。A. 动态结构和静态结构B.紧凑结构和非紧凑结构C. 线性结构和非线性结构D.内部结构和外部结构4某程序的时间复杂度为（ 3n+log 2n+n2+15）其数量级表示为（ B ）A. O(

31、n)B. O2n2 )C. Olog 2n) D. Onlog 2n)5非线性结构的数据元素之间存在（B ）。A. 一对多关系 B. 多对多关系 6下列时间复杂度中最坏的是（D ）A. O （1）B. O （ n ）7以下任何两个结点之间都没有逻辑关系的是（A. 图型结构 B. 线性结构C.多对一关系D.一对一关系C. O( log 2n)D. O（n2）D）C.树型结构D.集合11v1.0 可编辑可修改8链接存储的存储结构所占存储空间（A ）。A 分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针B 只有一部分，存放结点值C 只有一部分，存储表示结点间关系的指针D 分两部分，一部

32、分存放结点值，另一部分存放结点所占单元素9一个存储结点存放一个（B）A. 数据项 B.数据元素C.数据结构D. 数据类型10下列时间复杂度中最好的是（A ）A. O （ 1）B. O（ n）C. O（ log 2n）D. O（ n2）11每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（B ）存储方式A. 顺序 B.链式C.索引 D.散列12下列算法的实际复杂度是（D ）for （i=0;in;i+）for （j=0;in;j+）cij=i+j;A. O （ 1）B. O（ n ） C.O（ log 2n） D. O（n2）13数据元素是数据的基本单位，其内（ B）数据项。A.

33、 只能包括一个 B.可以包括多个C.不包括 D.可以包括也可以不包括14数据结构中，与所使用的计算机无关的是数据的（C ）结构；A. 存储 B.物理 C.逻辑 D.物理和存储15数据的逻辑结构是（ A）关系的整体A. 数据元素之间逻辑B.数据项之间逻辑C. 数据类型之间D.存储结构之间第2章1用单链表方式存储的线性表，存储每个结点需要两个域， 一个数据域，另一个是B ）。2312A 当前结点所在地址域在具有 n 个结点的单链表中，A遍历链表和求链表的第C删除开始结点B 指针域C 空指针域D空闲域实现（i 个结点设 a， b， c 为三个结点， p， 10， 20，a 10A ）的操作，其算法的

34、时间复杂度都是O（n）。B在地址为 P 的结点之后插入一个结点D删除地址为 P 的结点的后继结点代表地址，则如下存储结构称为（ B ）。b 20v1.0 可编辑可修改A 循环链表B 单链表C 双向循环链表 D 双向链表4已知一个顺序存储的线性表，设每个结点需占m 个存储单元，若第一个结点的地址B，则第 i 个结点的地址为A ）。A B+(i-1)*mBB+i*mC B-i*m B+(i+1)*m5单链表的存储密度（C ）。A 大于 1等于 1C 小于 1不能确定6在 n 个结点的顺序表中，算法的时间复杂度是）。A访问第 i 个结点 （1=i-n） 和求第i 个结点的直接前驱 （2=i=n）B在

35、第 i 个结点之后插入一个新结点(1=i=n)C删除第 i 个结点 （1=inext= = P P-next= = NULL D P-next=9一维数组和线性表的区别是（A）。A 前者长度固定，后者长度可变 后者长度固定，前者长度可变C 两者长度都固定两者长度都可变10指针 P 所指的元素是双循环链表L 的尾元素的条件是（ D ）。AP= = LB P-prori= = LC P= = NULLDP-next=L11一个向量第一个元素的存储地址是100，每个元素的长度为 2，则第5 个元素的地址是A11010810012012两个指针 P 和 Q，分别指向单链表的两个元素，P 所指元素是 Q

36、所指元素前驱的条件是）。A P-next= =Q-next P-next= = QC Q-next= = PP= = Q13向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动B ）个元素。A 8B 63.5C14用链表存储的线性表，其优点是（C ）。A 便于随机存取B63 D 7花费的存储空间比顺序表少13v1.0 可编辑可修改C 便于插入和删除D 数据元素的物理顺序与逻辑顺序相同15单链表的示意图如下：LD指向链表 Q 结点的后继的指针是（ D ）ALB P C Q DR1每次从无序表中取出一个元素，把它插入到有序表中的适当位置，这种排序方法叫 （ C ）。A 选

37、择 B 交换 C 插入 D 归并 2快速排序方法在（ C ）情况下最不利于发挥其长处。A 要排序的数据量太大 B 要排序的数据中含有多个相同值C. 要排序的数据已基本有序D.要排序的数据个数为奇数3排序方法中，从无序序列中选择关键字最小的记录，将其与无序区（初始为空）的第一 个记录交换的排序方法，称为 : （ D ） 。A希尔排序B归并排序C插入排序D. 选择排序4在待排序的元素序列基本有序的前提下，效率最高的排序方法是：（A ）。A直接插入B冒泡排序C希尔排序D选择排序5每次把待排序方的区间划分为左、右两个区间，其中左区间中元素的值不大于基准元素 的值，右区间中元素的值不小于基准元素的值，此

38、种排序方法叫做（ C ）。A冒泡排序B 堆排序 C 快速排序 D. 归并排序6排序是根据（ A ）的大小重新安排各元素的顺序。A 关键字 B 数组 C 元素件 D 结点 7堆的形状是一棵（ D ）。A二叉排序树B 满二叉树C 不是二叉树 D. 完全二叉树8稳定的排序方法是指在排序前后， 关键字值相等的不同记录间的前后相对位置 （ B ）。A 保持相反 B 保持不变 C 不定 D 无关 9下述几种排序方法中，要求内存量最大的是：（D ）。A 插入排序 B 选择排序 C 快速排序 D. 归并排序 14v1.0 可编辑可修改10直接插入排序的方法是（B ）的排序方法。A不稳定B稳定C 外部D选择11

39、直接插入排序的方法要求被排序的数据（B ）存储。A必须链表B必须顺序C 顺序或链表D可以任意12设有 1000 个无序元素，希望用最快的速度挑选出其中前10 个最大的元素，最好选用（ B ）排序法。A冒泡排序B堆排序C 快速排序D.归并排序13用快速排序法对n 个元素进行排序时，最坏情况下的执行时间为（A )AO（n2）B O(log 2n)C O( nlog 2n )D.O （ n）14一个数据序列的关键字为：（ 46，79，56，38，40， 84），采用快速排序，并以第一个 数为基准得到第一次划分的结果为：（ C ）A （38，40，46，56，79，84）B （ 40， 38，46，7

40、9，56，84）C （40，38，46，56，79，84）D （40，38，46，56，79，84）15用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下： 20 ，15， 21，25， 47，27，68，35，8415，20， 21，25， 35，27，47，68，8415，20， 21，25， 27，35，47，68，84则所采用的排序方法是（ D ）。A 选择排序 B 希尔排序 C 归并排序 D. 快速排序第4章1顺序 栈判空的条件是（ C ）A top=0Btop=1C top=-1D top=m2设有编号为1， 2，3，4

41、的四辆列车，顺序进入一个栈式结构的站台，下列不可能的出站顺序为 （ D ）A 1234B 1243C1324D14233插入 和删除只能 在 一端进行 的线性表，称为 ( C ) 。A 队列B循 环队列C栈D 循环栈4链栈 与顺序栈相比 ，有一个 比较明显的优点是（ B ）。A插入 操作根 加方便B通常 不会出现栈满的情况。C不会 出现栈 空的情 况D删 除操作根 加方便5在栈 中，出栈操作 的时间复 杂度为( A）。A O(1)B O(log 2n)C0(n)DO(n2)15v1.0 可编辑可修改6带头 结点的 链栈 LS 的示意图 如下， 栈顶元 素是( A )LSHACA AB BCCD

42、D7元素 A,B,C,D 依次进栈以后，栈顶元 素是( D )A ABBCCD D8顺序 栈存储 空间的实现使用( B )存 储栈元素A 链表 B数组C循 环链表D变量9在 C或 C+ 语 言中，一个顺序栈一 旦 被声明 ，其占用空间的 大小( A )。A已固定 B 不固定C 可以改变D 动态 变化10当栈中的元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为(C ) 。An-1B n+1CnDn/211栈与 一般线 性表的区别在于( B ) 。A 数据元 素的类 型不同 B 运算是否 受限制C 数据元 素的个 数不同D 逻辑结构 不同12 设有 一个顺 序栈 S，元素 A,B,C,D,

43、E,F, 依次 进栈，如 果六个 元素出 栈的顺序 是 B， D，C，F， E，A，则 栈的容量 至少应 是 ( A ) 。A3B 4C5D 613在栈 顶一端 可进行 ( D ) 操作。A 插入B删除C 进栈D插 入和删除14从一个栈顶指针为top 的链栈中删除一个结 点时，用x保存被删除 的结点，应 执行下列 ( D ) 命令。A x=top;top=top-next;B top=top-next;x=top-data;C x=top-data;D x=top-data;top=top-next;15在一 个栈顶指针为HS的链栈中，将 一个S指针所指的结点入栈，应执行下列 ( B ) 命令

44、。A HS-next=S; B S-next=HS-next;HS-next=S;C S-next=HS-next;HS=S;D S-next=HS;HS=HS-next;16在队 列中存 取数据 应遵循的 原则是 ( A ) 。A 先进 先出B 后进先出C先 进后出D随 意进 出17设长 度为 n的链队 列 用单循环 链表表 示，若 只设头指 针，则 人队操 作的时间 复 杂度为 ( C ) 。16v1.0 可编辑可修改2D O(n 2)A 已固 定 B 可以变 动C 不能固定D 动态 变化19 当利用大小为n的数组顺序存储一个队列时，该队列的最后一个元素的下标为B ）。A n-2B n-1

45、C n D n+1A O(1) B O(log 2n)C O(n) 18 一个 循环队 列一旦 说明，其 占用空 间的大 小（ A ）。针，则 出队操 作的时间 复B ）。20设长 度为 n的链队 列 用单循环 链表表 示，若 只设尾指A 队头 指针减 1B 取出队头 指针所 指的元 素C 队头 指针加 1D 取出队尾 指针所 指的元 素24. 在一个顺序存储的循环队列中，队头指针指向队头元素的（A ）位置。C 后面D 当前25 四个元素按：A，B， C， D顺序连续进队元素是（ B）。A AB BA 前一 个B后一个Q，执行一次 OutQueue（Q） 操作后，队头C CD DA O(1)B

46、 O (log 2n)C O(n)D O(n21队列 是限定 在（D ）进行 操作的 线性 表。A中间B队头C 队尾D端 点22若进队的序列为：A，B， C， D，则出队的序列是（C）。A B， C， D， AB A，C，B，DC A， B， C， DD C，B，D，A杂度为 （ A ） 。23从一个顺序循环队列删除一个元素时，首先需要做的操作是（； top=sA 5和 1B4和229以下属于队列的操作有 （ D ）A 在队 首插入 元素C 按元 素的大 小排 序C 2 和 4D 1 和 5B 删除值 最小的 元素D 判断是 否还有 元素1726队列 中的元 素个数是（B) 。A不变 的B可变

47、的C任意 的27设链栈中结点的结构：data为数据域，next 为指针域，且想在链栈的栈顶插入一个由指针s 所指的结点，则应执行下列（A s-next=top-next；top-next=sB top-next=sD 0 top 是栈顶指针。若 A ）操作。C s-next=top ； top=top-nextD s-next=top28 若用一个大小为 6的数组来实现循环队列，且当前 front 和rear 的值分别为 3和 0，当从 队列中删 除一个 元素， 再加入两 个元素 后， front 和 rear 的值分别为 （ B ）v1.0 可编辑可修改30. 带头结点的 链队列 LQ示意图

48、如 下， LQ为空时 （ A ）LQ-frontLQ-rearA LQ-front= LQ-rearB LQ-rear=NULLC LQ-front!= LQ-rearD LQ-front=null第5章1串 是一种特 殊的线性表， 其特殊性 体现在（ B ）。A.可以顺 序存储B数据 元素是一 个字符C.可以链 接存储D数据 元素可以 是多个字符2设目标 串T=AABBCCDDEEFF ，P=CCD ，则该模式 匹配的有效位移 为 （ C ） 。A 2B 3C 4D. 5 3设 有两个串 p和 q，求q在p中首次出 现的位置的运 算称作（ B ）。A.连接C.求子串B模式匹配D 求 串 长4. S1=sdudent， S2=SDUDENT ， 执 行 串 比 较 函 数 EqualStr(S1,S2)后的结果为 (