1、数据结构练习试卷 1及答案与解析 1 数据结构主要研究数据的 _。 （ A）逻辑结构 （ B）存储结构 （ C）逻辑结构和存储结构 （ D）逻辑结构和存储结构及其运算的实现 2 在数据结构中，结点 (数据元素 )及结点间的相互关系组成数据的逻辑结构。按逻辑结构的不同，数据结构通常可分为 _两类。 （ A）线性结构和非线性结构 （ B）紧凑结构和稀疏结构 （ C）动态结构和静态结构 （ D）内部结构和外部结构 3 下面叙述不正确的是 _。 （ A）算法的执行效率与数据的存储结构有 关 （ B）算法的空间复杂度是指执行这个算法所需要的内存空间 （ C）算法的有穷性是指算法必须能在执行有限个步骤之后
2、终止 （ D）算法的时间复杂度是指执行这个算法所需要的时间 4 数据的存储结构是指 _。 （ A）数据所占的存储空间量 （ B）数据的逻辑结构在计算机中的表示 （ C）数据在计算机中的顺序存储方式 （ D）存储在外存中的数据 5 下列对于线性链表的描述中正确的是 _。 （ A）存储空间不一定连续，且各元素的存储顺序是任意的 （ B）存储空间不一定连续，且前件元素一定存储 在后件元素的前面 （ C）存储空间必须连续，且前件元素一定存储在后件元素的前面 （ D）存储空间必须连续，且各元素的存储顺序是任意的 6 下列叙述中正确的是 _。 （ A）数据的逻辑结构与存储结构必定是一一对应的 （ B）由于
3、计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构 （ C）程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构 （ D）以上三种说法都不对 7 以下关于字符串的判定语句中正确的是 _。 （ A）字符串是一种特殊的线性表 （ B）串的长度必须大于零 （ C）字符串不属于线性表的一种 （ D）空格字符组成的串就是空串 8 字符串 computer中长度为 3的子串有 _个。 （ A） 4 （ B） 5 （ C） 6 （ D） 7 9 PUSH和 POP命令常用于 _操作。 （ A）队列 （ B）数组 （ C）栈 （ D）记录 10 n个元素依次全部进入栈后，再
4、陆续出栈并经过一个队列输出。那么，_。 （ A）元素的出队次序与进栈次序相同 （ B）元素的出队次序与进栈次序相反 （ C）元素的进栈次序与进队次序相 同 （ D）元素的出栈次序与出队次序相反 11 若一个栈以向量 V1n)存储，且空栈的栈顶指针 top为 n+1，则将元素 x入栈的正确操作是 _。 （ A） top=top+1； Vtop=x； （ B） Vtop=x； top=top+1； （ C） top=top-1； Vtop=x； （ D） Vtop=x； top=top-1； 12 设初始栈为空， s表示入栈操作， x表示出栈操作，则 _是合法的操作序列。 （ A） sxxsssx
5、xx （ B） xxssxxss （ C） sxsxssxx （ D） xssssxxx 13 若 push、 pop分别表示入栈、出栈操作，初始栈为空且元素 1、 2、 3依次进栈，则经过操作序列 push、 push、 pop、 pop、 push、 pop之后，得到的出栈序列为_。 （ A） 321 （ B） 213 （ C） 231 （ D） 123 14 设栈 S初始状态为空。元素 a、 b、 c、 d、 e、 f依次通过栈 S，若出栈的顺序为c、 f、 e、 d、 b、 a，则栈 S的容量至少应该为 _。 （ A） 6 （ B） 5 （ C） 4 （ D） 3 15 一个栈的输入
6、序列为 123n ，若输出序列的第一个元素是 n，输出第 i(1in)个元素是 _。 （ A）不确定 （ B） n-i+l （ C） i （ D） n-i 16 以下数据结构中属于线性数据结构的是 _。 （ A）集合 （ B）线性表 （ C）二叉树 （ D）图 17 设栈 S和队列 Q的初始状态为空，元素 e1、 e2、 e3、 e4、 e5和 e6依次通过栈S，一个元素出栈后即进入队列 Q，若 6个元素出队的序列是 e2、 e4、 e3、 e6、e5、 e1，则栈 S的容量至少应该是 _。 （ A） 6 （ B） 4 （ C） 3 （ D） 2 18 某循环队列的容量为 M，队头指针指向队头
7、元素，队尾指针指向队尾元素之后，如图 8-8所示 (M=8)，则队列中的元素数目为 _(MOD表示整除取余运算 )。 （ A） rear-front （ B） front-rear （ C） (rear-front+M)MODM （ D） (front-rear+M)MODM 19 栈和队列的共同点是 _。 （ A）都是先进先出 （ B）都是先进后出 （ C）只允许在端点处插入和删除元素 （ D）没有共同点 20 _是线性结构的数据结构。 （ A）列表 （ B）高维数组 （ C）双端队列 （ D）二叉树 21 链表不具备的特点是 _。 （ A）可随机访问任何一个元素 （ B）插入、删除操作不需
8、要移动元素 （ C）无需事先估计存储空间大小 （ D）所需存储空间与线性表长度成正比 22 与单向链表相比，双向链表 _。 （ A）需要较少的存储空间 （ B）遍历元素需要的时间较长 （ C）较易于访问相邻结点 （ D）较易于插入和删除元素 23 若 in、 out分别表示入、出队操作，初始队列为空且元 素 a、 b、 c依次入队，则经过操作序列 in、 in、 out、 out、 in、 out之后，得到的出队序列为 _。 （ A） cba （ B） bac （ C） bca （ D） abe 24 在链表结构中，采用 _可以用最少的空间代价和最高的时间效率实现队列结构。 （ A）仅设置尾指
9、针的单向循环链表 （ B）仅设置头指针的单向循环链表 （ C）仅设置尾指针的双向链表 （ D）仅设置头指针的双向链表 25 判断 “链式队列为空 ”的条件是 _(front为头指针， rear为尾指针 )。 （ A） front=NULL （ B） rear=NULL （ C） front=rear （ D） front!=rear 26 可以用栈来检查算术表达式中的括号是否匹配。分析算术表达式时，初始栈为空，从左到右扫描字符，遇到字符 “(”就将其入栈，遇到 “)”就执行出栈操作。对算术表达式 “(a+b*(a+b)/c)+(a+b)”，检查时， (1)；对算术表达式 “(a+b/(a+b)
10、-c/a)/b”，检查时， (2)。这两种情况都表明所检查的算术表达式括号不匹配。（ A）栈为空却要进行出栈操作 （ B）栈已满却要进行 入栈操作 （ C）表达式处理已结束，栈中仍留下有字符 “(” （ D）表达式处理已结束，栈中仍留下有字符 “)” （ A）栈为空却要进行出栈操作 （ B）栈已满却要进行入栈操作 （ C）表达式处理已结束，栈中仍留下有字符 “(” （ D）表达式处理已结束，栈中仍留下有字符 “)” 数据结构练习试卷 1答案与解析 1 【正确答案】 D 【试题解析】 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构一般包括三方面的内容： 数据之间的逻辑关系。从
11、逻辑关系上描述数据，与数据的存储无关。 数据的存 储结构。存储结构分为顺序结构和链式结构，是逻辑结构在计算机存储器中的表示，它包括数据元素的表示和关系的表示。 数据的运算。也就是在数据上所施加的一系列操作。只考虑操作的功能是怎样的，暂不考虑如何实现。综上所述，本题的正确答案为选项 D。 【知识模块】 数据结构 2 【正确答案】 A 【试题解析】 在数据结构中，结点 (数据元素 )及结点间的相互关系组成数据的逻辑结构。按逻辑结构的不同，数据结构通常可分为线性结构和非线性结构两类。本题正确答案为选项 A。 【知识模块】 数据结构 3 【正确答 案】 D 【试题解析】 算法的时间复杂度是指执行算法所
12、需要的计算工作量，故 D选项不正确。 【知识模块】 数据结构 4 【正确答案】 B 【试题解析】 数据的存储结构是数据元素在计算机存储器内的表示。数据的存储结构是逻辑结构用计算机语言的实现，即建立数据的机内表示。本题正确答案为选项 B。 【知识模块】 数据结构 5 【正确答案】 A 【试题解析】 在链式存储结构中，存储数据的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，数据元素之间的逻辑关系 ，是由指针域来确定的。由此可见，选项 A的描述正确。 【知识模块】 数据结构 6 【正确答案】 D 【试题解析】 数据之间的相互关系称为逻辑结构。存储结构是逻辑结构在存储器中
13、的映像，它包含数据元素的映像和关系的映像。存储结构在计算机中有两种，即顺序存储结构和链式存储结构。 顺序存储结构是把数据元素存储在一块连续地址空间的内存中。 链式存储结构是使用指针把相互直接关联的结点链接起来。因此，这两种存储结构都是线性的。可见，逻辑结构和存储结构不是一一对应的。因此，选项 A和选项 B的说法都是错误的。无论 数据的逻辑结构是线性的还是非线性的，只能选择顺序存储结构或链式存储结构来实现存储。程序设计语言中，数组是内存中一段连续的地址空间，可看作是顺序存储结构。可以用数组来实现树型逻辑结构的存储，比如二叉树。因此，选项 C的说法是错误的。 【知识模块】 数据结构 7 【正确答案
14、】 A 【试题解析】 字符集中的字符所组成的有限字符序列，就是字符串，它是特殊的线性表，选项 A说法正确。选项 C错误。字符串不包含任何字符时，为空串，长度为 0，所以，选项 B和选项 D的说法错误。 【知识模块】 数据结构 8 【正确答案】 B 【试题解析】 子串是字符串中任意长度的连续字符构成的序列。对于字符串computer，长度为 3的子串有： com、 omp、 mpu、 put、 ute、 ter。共有 6个。选项 B为本题正确答案。 【知识模块】 数据结构 9 【正确答案】 C 【试题解析】 栈是先进后出的线性表。其基本运算是入栈和出栈操作，也就是PUSH和 POP。本题的正确答
15、案为选项 C。 【知识模块】 数据结构 10 【正确答案】 B 【试题解析】 栈的特点是先进后出，出栈后，元素逆序。队 列的特点是先进先出，元素经过队列，不会更改其顺序，也就是说，出队顺序与入队顺序相同，与出栈顺序相同，与入栈顺序相反。所以，选项 B的说法正确，为本题正确答案，其他选项的说法错误。 【知识模块】 数据结构 11 【正确答案】 C 【试题解析】 栈是运算受限的线性表，只允许在栈顶进行插入和删除操作。栈顶指针为 n+1，说明该数组将栈顶放在了下标大的一端，所以，在进行入栈操作时， top指针应该进行减 1操作。通常元素进栈的操作为：先移动栈顶指针，后存入元素。移动栈顶指针的操作是
16、“top=top-1； ”， 存入元素的操作是“Vtop=x； ”。本题正确答案为选项 C。 【知识模块】 数据结构 12 【正确答案】 C 【试题解析】 栈是操作受限的线性表，其特点是后进先出。应用中可将栈看作一个桶状的容器，当栈中有元素时，栈顶元素先出栈，栈为空时进行出栈操作是不正确的。因此，对于一个关于初始为空的栈的操作序列，要求序列中任何一个操作之前，入栈操作的次数要大于等于出栈操作的次数。题目选项中仅操作序列sxsxssxx满足该要求。本题正确答案为选项 C。 【知识模块】 数据结构 13 【正确答案】 B 【试题解析】 栈的运算特点是先进后出。对于元素 1、 2、 3，经过操作序列
17、push、 push、 pop、 pop、 push、 pop的过程如图 8-3(a g)所示。通过图可以看出，出栈序列为 213。本题正确答案为选项 B。 【知识模块】 数据结构 14 【正确答案】 B 【试题解析】 根据题中给定的条件，可做如下模拟操作： 元素 a、 b、 c进栈，栈中有 3个元素，分别为 a、 b、 c； 元素 c出栈后，元素 d、 e、 f进栈，栈中有 5个元素，分别为 a、 b、 d、 e、f； 元素 f、 e、 d、 a、 b出栈，栈为空。可以看出，进栈的顺序为 a、 b、 c、 d、e、 f，出栈的顺序为 c、 f、 e、 d、 b、 a，满足题中所提出的要求。
18、在每一次进栈操作后，栈中最多有 3个元素，因此，为了顺利完成这些操作，栈的容量应至少为 5。本题答案为 B。 【知识模块】 数据结构 15 【正确答案】 B 【试题解析】 栈的特点是先进后出，若输入序列为 123n ，输出的第一个元素是 n，则表明，所有元素都已入栈，则出栈顺序为：第 1个元素为 n，第 2个元素为 n-1，第 3个元素为 n-2， ，第 i个元素是 n-i+1。 【知识模块】 数据结构 16 【正确答案】 B 【试题解析】 所谓的线性结构是指：如果一个非空的数据结构满足下列两个条件，即： 有且只有一个根结点。 每一个结点最多有一个前件，也最多有一个后件。同时满足两个条件的只有
19、线性表，而其他三种数据结构的结点可能存在多个前件或后件，所以不是线性结构。故本题正确答案为 B。 【知识模块】 数据结构 17 【正确答案】 C 【试题解析】 栈的特点是先进后出，队列的特点是先进先出。所以，如果一个元素序列先进入栈，再进入队列，那么，出队的序列，与入 栈序列是逆序。队列不影响元素顺序。 所以，下面使用图来模拟输入和输出顺序，只给出栈的变化。 根据题意，元素 e1、 e2、 e3、 e4、 e5和 e6依次通过栈 S，一个元素出栈后即进入队列 Q，若 6个元素出队的序列是 e2、 e4、 e3、 e6、 e5、 e1，那么，通过出队次序可以看出，首先是 e2，说明 e1、 e2
20、顺序入栈。后来 e2出栈， e1还在栈中。 如图 8-4所示。 第 2个输出元素是 e4，那么，说明此时在栈中，还有 e1、 e3。如图 8-5所示。 第 3个输出元素是 e3，直接出栈即可。如图 8-6所示。 第 4个输出元素 是 e6，说明在 e3出栈后，e5、 e6顺序入栈。 e6出栈后，栈中剩下 e5和 e1。顺序出栈即可。如图 8-7所示。 根据前面对入栈、出栈过程的模拟，可以看出，栈 s的容量至少为 3。选项 C为正确答案。 【知识模块】 数据结构 18 【正确答案】 C 【试题解析】 队列是仅在表头删除元素、在表尾插入元素的操作受限的线性表，其特点是先入先出。队列采用顺序存储结构
21、 (一维数组，顺序队列 )时，为了降低运算的复杂度，元素入队时，只需修改队尾指针 rear(rear+1rear) ；元素出队时，只需修改队头指针 front(front+1front) 。由于顺序队列的存储空间是提前设定的，所以队尾指针会有一个上限值，当队尾指针达到其上限时，就不能只通过修改队尾指针来实现新元素的入队操作了。此时，可将顺序队列假想成一个环状结构，称为循环队列。队列容量为 M时，队头指针 front和队尾指针 rear的值循环地在 0 M-1之间变化，当 rear front时，队列中元素数目为 rear-front；当 rear front时，队列中元素数目为 rear-fr
22、ont+M。综上，队列中元素数目为 (rear-front+M)MODM。本题正确 答案为选项 C。 【知识模块】 数据结构 19 【正确答案】 C 【试题解析】 栈和队列都是运算受限的线性表，只允许在表端点处进行操作。本题正确答案为选项 C。 【知识模块】 数据结构 20 【正确答案】 A 【试题解析】 列表是树形结构，高维数组和二叉树为非线性结构。双端队列是线性结构。本题正确答案为选项 C。 【知识模块】 数据结构 21 【正确答案】 A 【试题解析】 链表是线性表的链式存储，是用结点来存储数据元素。线性表采用链表作为存储结构时，不能进行数据元 素的随机访问，其优点是插入和删除操作不需要移
23、动元素。所以，本题应该选择 A。 【知识模块】 数据结构 22 【正确答案】 D 【试题解析】 在单向链表中，只能沿着一个方向访问结点。在双向链表中，可以向前访问结点，也可以向后访问结点。所以，双向链表的插入和删除操作更为容易。选项 D为正确答案。 【知识模块】 数据结构 23 【正确答案】 D 【试题解析】 队列的运算特点是先进先出。初始队列为空且元素 a、 b、 c依次入队，则经过操作序列 in、 in、 out、 out、 in、 out的过程，如图 8-9的 (a) (g)所示。 通过图可知，出队序列为 abc，所以，本题正确答案为选项 D。 【知识模块】 数据结构 24 【正确答案】
24、 A 【试题解析】 从空间的角度考虑，采用链表作为存储结构，应当使用单链表，没有必要采用双向链表从两个方向遍历元素。所以排除选项 C和选项 D。队列的特点是，先进先出。从时间效率的角度考虑，同时具有头指针和尾指针的话，入队和出队操作最为简单。但题目中仅仅给出了只有头指针或者只有尾指针的情况。那么： 如果仅仅设置头指针，那么，删除元素时，只要修改第一个元素的指向即可。 如果要插入元素，则需要遍历整个链表，才能到达尾指针的位置。 如果仅仅设置尾指针，那么，如果要实现删除操作，可以取尾指针域的值，直接获得头指针。如果要执行插入操作，那么，修改两个尾指针的指针域以及新插入结点的指针域即可。通过比较，仅
25、仅设置尾指针，更节省时间。选项 A是正确答案。 【知识模块】 数据结构 25 【正确答案】 C 【试题解析】 队列的链式存储也称为链队列。为了便于操作，链队列有一个头结点，并令头指针指向头结点。因此，队列为空的判定条件是：头指针和尾指针的值相同，且均为指向头结点。所以 ，本题应该选择 C。 【知识模块】 数据结构 26 【正确答案】 A 【知识模块】 数据结构 27 【正确答案】 C 【试题解析】 栈是先进后出的线性表。 对算术表达式 “(a/b*(a+b)/c)+(a+b)”进行括号检查时，操作顺序为： 遇到第 1个左括号，进行入栈操作。栈中有 1个左括号。 遇到第 2个左括号，进行入栈操作
26、。栈中有 2个左括号。 遇到第 1个右括号，进行出栈操作。栈中有 1个左括号。 遇到第 2个右括号，进行出栈操作。栈中没有左括号。 遇到第 3个右括号，进行出栈操作。但此时为空栈，无法进行出栈操作。 表达式检查结束。第 1空的正确答案为选项 A。 对算术表达式 “(a+b/(a+b)-c/a)几 ”进行括号检查时，操作顺序为： 遇到第 1个左括号，进行入栈操作。栈中有 1个左括号。 遇到第 2个左括号，进行入栈操作。栈中有 2个左括号。 遇到第 3个左括号，进行入栈操作。栈中有 3个左括号。 遇到第 1个右括号，进行出栈操作。栈中有 2个左括号。 遇到第 2个右括号，进行出栈操作。栈中有 1个左括号。 表达式检查结束。栈中依然还有左括号，表示表达式不匹配，第 2空的正确答案为选项 C。 【知识模块】 数据结构
