2022年全国计算机等级考试二级公共基础知识考题库及答案超强

1、2022 年全国运算机等级考试二级公共基础学问考题库 及答案（超强） 第一章 数据结构 一,选择题 （ 1）以下数据结构中,能用二分法进行查找的是 A）次序储备的有序线性表 B ）线性链表 C）二叉链表 D）有序线性链表 【答案】 A 【解析】二分查找只适用于次序储备的有序表；在此所说的有序表是指线性表 中的元素按值非递减排列 即从小到大 但答应相邻元素值相等 的；选项 A 正确； （ 2）以下关于栈的描述正确选项 A）在栈中只能插入元素而不能删除元素 B）在栈中只能删除元素而不能插入元素 C）栈是特别的线性表,只能在一端插入或删除元素 D）栈是特别的线性表,只能在一端插入元素,而在另一端删除

2、元素 【答案】 C 【解析】栈是一种特别的线性表,其插入与删除运算都只在线性表的一端进行； 由此可见,选项 A,选项 B 和选项 D 错误,正确答案是选 项 C； （ 3）以下表达中正确选项 A ）一个规律数据结构只能有一种储备结构 B ）数据的规律结构属于线性结构,储备结构属于非线性结构 第 1 页,共 151 页C）一个规律数据结构可以有多种储备结构,且各种储备结构不影响数据处理 的效率 D）一个规律数据结构可以有多种储备结构,且各种储备结构影响数据处理的 效率 【答案】 D 【解析】一般来说,一种数据的规律结构依据需要可以表示成多种储备结构, 常用的储备结构有次序,链接,索引等储备结构；

3、而接受不同的储备结构,其 数据处理的效率是不同的；由此可见,选项 D 的说法正 确； 4 算法执行过程中所需要的储备空间称为算法的 A）时间复杂度 B）运算工作量 C）空间复杂度 D）工作空间 【答案】 c 【解析】算法执行时所需要的储备空间,包括算法程序所占的空间,输入的初 始数据 所占的储备空间以及算法执行过程中所需要的额外空间,其中额外 空间仍包括算法程序执行过程的工作单元以及某种数据结构所需要的附加储备 空间；这些储备空间共称为算法的空间复杂度； 5 以下关于队列的表达中正确选项 A）在队列中只能插入数据 B）在队列中只能删除数据 C）队列是先进先出的线性表 D）队列是先进后出的线性表

4、 【答案】 c 【解析】对队列可以进行插入和删除数据的操作,只是插入数据只能在队尾, 删除数据只能在队头；所以队列是先进先出的线性表； 6 设有以下二叉树： A 第 2 页,共 151 页B DE CF 对此二叉树后序遍历的结果为 A） ABCDEF B）BDAECF C） ABDCEF D） DBEFCA 【答案】 D 【解析】二叉树的遍历分为先序,中序,后序三种不同方式；此题要求后序遍 历；其遍历次序应当为：后序遍历左子树一 后序遍历右子树一 拜望根结点； 依据定义,后序遍历序列是 DBEFC,A 故答案为 D； 7 以下表达中正确选项 A 程序执行的效率与数据的储备结构亲热相关 B 程序

5、执行的效率只取决于程序的把握结构 C程序执行的效率只取决于所处理的数据量 D以上三种说法都不对 【答案】 A 【解析】此题考查程序效率；程序效率是指程序运行速度和程序占用的储备空 间；影响程序效率的因素是多方面的,包括程序的设计,使用的算法,数据的 储备结构等；在确定数据规律结构的基础上,选择一种合适的储备结构,可以 使得数据操作所花费的时间少,占用的储备空间少,即提高程序的效率；因此, 此题选项 A 的说法是正确的； 第 3 页,共 151 页8 以下表达中正确选项 A 数据的规律结构与储备结构必定是一一对应的 B 由于运算机储备空间是向量式的储备结构,因此,数据的储备结构确定是线 性结构

6、C程序设计语言中的数组一般是次序储备结构,因此,利用数组只能处理线线 结构 D以上三种说法都不对 【答案】 D 【解析】此题考查数据结构的基本学问； 数据之间的相互关系称为规律结构；通常分为四类基本规律结构,即集合,线 性结构,树型结构,图状结构或网状结构；储备结构是规律结构在储备器中的 映象,它包含数据元素的映象和关系的映象；储备结构在运算机中有两种,即 次序储备结构和链式储备结构；次序储备结构是把数据元素储备在一块连续地 址空间的内存中；链式储备结构是使用指针把相互直接关联的节点链接起来； 因此,这两种储备结构都是线性的；可见,规律结构和储备结构不是一一对应 的；因此,选项 A 和选项 B

7、 的说法都是错误的； 无论数据的规律结构是线性的仍是非线性的,只能选择次序储备结构或链式存 储结构来实现储备；程序设计语言中,数组是内存中一段连续的地址空间,可 看作是次序储备结构；可以用数组来实现树型规律结构的储备,比如二叉树； 因此,选项 c 的说法是错误的 9 冒泡排序在最坏情形下的比较次数是 Ann+1/2 Bnlog 2nCnn-1/2 Dn/2 【答案】 C 第 4 页,共 151 页【解析】冒泡排序的基本思想是：将相邻的两个元素进行比较,假如反序,就 交换；对于一个待排序的序列,经一趟排序后,最大值的元素移动到最终的位 置,其他值较大的元素也向最终位置移动,此过程称为一趟冒泡；对

8、于有 n 个 数据的序列,共需 n-1 趟排序,第 i 趟对从 l 到 n-i 个数据进行比较,交换； 冒泡排序的最坏情形是待排序序列逆序,第 l趟比较 n-1 次,第 2 趟比较 n-2 次；依此类推,最终趟比较 1 次,一共进行 n-l 趟排序；因此,冒泡排序在最 坏情形下的比较次数是 n-1+n-2+ +l ,结果为 nn-1/2 ；此题的正确答案 是选项 c； 10 一棵二叉树中共有 70 个叶子结点与 80 个度为 1 的结点,就该二叉树中的 总结点数为 A219 B221 C229 D231 【答案】 A 【解析】此题考查数据结构中二叉树的性质；二叉树中意如下一条性质,即： 对任意

9、一棵二叉树,如终端结点 即叶子结点 数为 n0,而其度数为 2 的结点数 为 n2,就 n0= n2+l； 依据这条性质可知, 如二叉树中有 70 个叶子结点,就其度为 2 的结点数为 70-1 , 即 69 个；二叉树的总结点数是度为 2,度为 1 和叶子结点的总和,因此,题目 中的二叉树总结点数为 69+80+70,即 219；因此,此题的正确答案是选项 A； 11 以下表达中正确选项 A算法的效率只与问题的规模有关,而与数据的储备结构无关 B算法的时间复杂度是指执行算法所需要的运算工作量 C数据的规律结构与储备结构是一一对应的 D算法的时间复杂度与空间复杂度确定相关 第 5 页,共 15

10、1 页【答案】 B 【解析】此题考查数据结构中有关算法的基本学问和概念；数据的结构,直接 影响算法的选择和效率；而数据结构包括两方面,即数据的规律结构和数据的 储备结构；因此,数据的规律结构和储备结构都影响算法的效率；选项 A 的说 法是错误的；算法的时间复杂度是指算法在运算机内执行时所需时间的度量； 与时间复杂度类似,空间复杂度是指算法在运算机内执行时所需储备空间的度 量；因此,选项 B 的说法是正确 的； 数据之间的相互关系称为规律结构；通常分为四类基本规律结构,即集合,线 性结构,树型结构,图状结构或网状结构；储备结构是规律结构在储备器中的 映象,它包含数据元素的映象和关系的映象；储备结

11、构在运算机中有两种,即 次序储备结构和链式储备结构；可见,规律结构和储备结构不是一一对应的； 因此,选项 c 的说法是错误的；有时人们为了提高算法的时间复杂度,而以牺 牲空间复杂度为代价；但是,这两者之间没有必定的联系；因此,选项 D 的 说 法是错误的； 12 以下关于算法的时间复杂度陈述正确选项 A） 算法的时间复杂度是指执行算法程序所需要的时间 B） 算法的时间复杂度是指算法程序的长度 C） 算法的时间复杂度是指算法执行过程中所需要的基本运算次数 D） 算法的时间复杂度是指算法程序中的指令条数 【答案】 C 【解析】算法的时间复杂度是指执行算法所需要的运算工作量,也就是算法在 执行过程中

12、所执行的基本运算的次数,而不是指程序运行需要的时间或是程序 的长度； 第 6 页,共 151 页13 以下关于栈的表达中正确选项 A）在栈中只能插入数据 B ）在栈中只能删除数据 C）栈是先进先出的线性表 D）栈是先进后出的线性表 【答案】 D 【解析】对栈可进行插入和删除数据的操作,但必需牢记插入和删除数据都只 能是在栈顶,是一种特别的线性表；所以栈是先进后出的线性表； 14 设有以下二叉树： A B CDE FF F 对此二叉树中序遍历的结果为 A） ABCDEF B ） DAECF C ） BDAECF D ）DBEFCA 【答案】 C 【解析】二叉树的遍历分为先序,中序,后序三种不同方

13、式；此题要求中序遍 历,其遍历次序应当为：中序遍历左子树 - 拜望根结点 - 中序遍历右子树；按 照定义,中序遍历序列是 BDAEC,F 故答案为 B； 15 依据“后进先出”原就组织数据的数据结构是 A）队列 D）二叉树 B ）栈 C）双向链表 【答案】 B 第 7 页,共 151 页【解析】“后进先出”表示最终被插入的元素最先能被删除；选项 A 中,队列是 指答应在一端进行插入,而在另一端进行删除的线性表,在队列这种数据结构 中,最先插入的元素将最先能够被删除,反之,最终插入的元素将最终才能被 删除,队列又称为“先进先出”的线性表,它表达了“先来先服务”的原就： 选项 B 中,栈顶元素总是

14、最终被插入的元素,从而也是最先能被删除的元素, 栈底元素总是最先被插入的元素,从而也是最终才能被删除的元素；队列和栈 都属于线性表,它们具有次序储备的特点,所以才有“先进先出”和“后进先 出”的数据组织方式；双向链表使用链式储备方式二叉树也通常接受链式存 储方式,它们的储备数据的空间可以是不连续的,各个数据结点的储备次序与 数据元素之间的规律关系可以不一样；所以选项 c 和选项 D 错； 16 以下表达中正确选项 A）线性链表是线性表的链式储备结构 B）栈与队列是非线性结构 C）双向链表是非线性结构 D）只有根结点的二叉树是线性结构 【答案】 A 【解析】一个非空的数据结构假如中意以下两个条件

15、： 1 有且只有一个根结 点;2 每一个结点最多有一个前件,也最多有一个后件；就称为线性结构；线 性链表是线性表的链式储备结构,选项 A 的说法是正确的；栈与队列是特别的 线性表,它们也是线性结构,选项 B 的说法是错误的；双向链表是线性表的链 式储备结构,其对应的规律结构也是线性结构,而不是非线性结构,选项 c 的 说法是错误的；二叉树是非线性结构,而不是线性结构,选项 D 的说法是错误 的；因此,此题的正确答案为 A 第 8 页,共 151 页17 对如下二叉树 A DB E F C进行后序遍历的结果为 A） ABCDEF B） DBEAFC C） ABDECF D） DEBFCA 【答案

16、】 D 【解析】二叉树后序遍历的简洁描述如下：如二叉树为空,就终止返回；否就 （ 1 后序遍历左子树； 2 后序遍历右子树； 3 拜望根结点；也就是说,后序 遍历是指在拜望根结点,遍历左子树与遍历右子树这三者中,第一遍历左子树, 然后遍历右子树,最终拜望根结点,并且,在遍历左,右子树时,仍然先遍历 左子树,然后遍历右子树,最终拜望根结点；依据后序遍历的算法,后序遍历 的结果为 DEBFC；A 18 以下对队列的表达正确选项 A队列属于非线性表 B队列按“先进后出”原就组织数据 C队列在队尾删除数据 第 9 页,共 151 页D队列按“先进先出”原就组织数据 【答案】 D 【解析】此题考查数据结

17、构中队列的基本学问；队列是一种限定性的线性表, 它只答应在表的一端插入元素,而在另一端删除元素,所以队列具有先进先出 的特性；在队列中,答应插入元素的一端叫做队尾,答应删除的一端就称为队 头；这与日常生活中的排队是一样的,最早进入队列的人最早离开,新来的人 总是加入到队尾；因此,此题中只有选项 D 的说法是正确 的； 19 对以下二叉树进行前序遍历的结果为 A DYBEAFCZX B YDEBFZXCA C ABDYECFXZ D ABCDEFXYZ 【答案】 C 【解析】此题考查数据结构中二叉树的遍历；依据对二叉树根的拜望先后次序 不同,分别称为前序遍历,中序遍历和后序遍历；这三种遍历都是递

18、归定义的, 即在其子树中也依据同样的规律进行遍历；下面就是前序遍历方法的递归定义； 当二叉树的根不为空时,依次执行如下 3 个操作： 1 拜望根结点 2 按先序遍历左子树 3 按先序遍历右子树 依据如上前序遍历规章,来遍历此题中的二叉树；第一拜望根结点,即 A,然 后遍历 A 的左子树；遍历左子树同样依据相同的规章第一拜望根结点 B,然后 遍历 B 的左子树； 遍历 B 的左子树, 第一拜望 D,然后拜望 D 的左子树, D 的 左 第 10 页,共 151 页子树为空 , 接下来拜望 D 的右子树,即 Y；遍历完 B 的左子树后,再遍历 B 的右 子树,即 E；到此遍历完 A 的左子树,接下

19、来遍历 A 的右子树；依据同样的规 就,第一拜望 C,然后遍历 c 的左子树；即 F； c 的左子树遍历完,接着遍历 c 的右子树；第一拜望右子树的根结点 X,然后拜望 X 的左子树, X 的左子树, 即 Z,接下来拜望 X 的右子树, 右子树为空；到此,把题目的二叉树进行了一次前 序遍历；遍历的结果为 ABDYECFX,Z故此题的正确答案为选 项 C； 20 某二叉树中有 n 个度为 2 的结点,就该二叉树中的叶子结点数为 A n+1 B n-1 C 2n D n/2 【答案】 A 【解析】此题考查数据结构中二叉树的性质； 二叉树中意如下一条性质,即： 对任意一棵二叉树,如终端结点 即叶子结

20、点 数为 no,而其度数为 2 的结点数 为 n2,就 n0=n2+l； 依据这条性质可知,如二叉树中有 n 个度为 2 的结点,就该二叉树中的叶子结 点数为 n+l ；因此,此题的正确答案是选项 A； 21 在深度为 7 的满二叉树中,叶子结点的个数为 A） 32 B）31 C）64 D） 63 【答案】 C k-1 【解析】在二叉树的第 k 层上,最多有 2 k 1 个结点；对于满二叉树来说, 每一层上的结点数都达到最大值, 即在满二叉树的第 k 层上有 2 个结点；因此, k-1 7-1 在深度为 7 的满二叉树中, 全部叶子结点在第 7 层上即其结点数为 2 =2 =64 因此此题的正

21、确答案为 c； 22 以下表达中正确选项 A）一个算法的空间复杂度大,就其时间复杂度也必定大 第 11 页,共 151 页B）一个算法的空间复杂度大,就期时间复杂度必定小 C）一个算法的时间复杂度大,就其空间复杂度必定小 D）上述三种说法都不对 【答案】 D 【解析】时间复杂度是指一个算法执行时间的相对度量；空间复杂度是指算法 在运行过程中临时占用所需储备空间大小的度量；人们都期望选择一个既省存 储空间,又省执行时间的算法；然而,有时为了加快算法的运行速度,不得不 增加空间开销；有时为了能有效地储备算法和数据,又不得不牺牲运行时间； 时间和空间的效率往往是一对冲突,很难做到两全；但是,这不适用

22、于全部的 情形,也就是说时间复杂度和空间复杂度之间虽然经常冲突；但是二者不存在 必定的联系；因此,选项 A,B,c 的说法都是错误的；故此题的正确答案是 D； 23 在长度为 64 的有序线性表中进行次序查找,最坏情形下需要比较的次数为 A） 63 B ）64 C）6 D）7 【答案】 B 【解析】在长度为 64 的有序线性表中,其中的 64 个数据元素是依据从大到小 或从小到大的次序排列有序的；在这样的线性表中进行次序查找,最坏的情形 就是查找的数据元素不在线性表中或位于线性表的最终；依据线性表的次序查 找算法,第一用被查找的数据和线性表的第一个数据元素进行比较；如相等, 就查找胜利,否就,

23、连续进行比较,即和线性表的其次个数据元素进行比较； 同样,如相等,就查找胜利,否就,连续进行比较；依次类推,直到在线性表 中查找到该数据或查找到线性表的最终一个元素,算法才终止；因此,在长度 为 64 的有序线性表中进行次序查找,最坏的情形下需要比较 64 次；因此,本 题的正确答案为 B； 第 12 页,共 151 页24 对以下二叉树 进行中序遍历的结果是 A） ACBDFEG B）ACBDFGE C） ABDCGEF D）FCADBEG F A CDE G B 【答案】 A 【解析】二叉树的中序遍历递归算法为：假如根不空,就 1 按中序次序拜望左 子树； 2 拜望根结点： 3 按中序次序

24、拜望右子树；否就返回；此题中,依据 中序遍历算法应第一依据中序次序拜望以 c 为根结点的左子树,然后再拜望 根结点 F,最终才拜望以 E 为根结点的右子树； 遍历以 c 为根结点的左子树同样 要遵循中序遍历算法,因此中序遍历结果为 ACBD；然后遍历根结点 F；遍历以 E 为根结点的右子树,同样要遵循中序遍历算法,因此中序遍历结果为 EG；最终 把这三部分的遍历结果按次序连接起来,中序遍历结果为 ACBDFE；G因此,此题 的正确答案是 A； （ 25）数据的储备结构是指； A）储备在外存中的数据 B）数据所占的储备空间量 C）数据在运算机中的次序储备方式 D）数据的规律结构在运算机中的表示

25、【答案】 D 【解析】数据的规律结构在运算机储备空间中的存放形式称为数据的储备结构, 第 13 页,共 151 页也称数据的物理结构；所以选项 D 正 确； （ 26）以下关于栈的描述中错误选项 ； A） 栈是先进后出的线性表 B） 栈只能次序储备 C） 栈具有记忆作用 D） 对栈的插入与删除操作中,不需要转变栈底指针 【答案】 B 【解析】此题考核栈的基本概念,我们可以通过排除法来确定此题的答案；栈 是限定在一端进行插入与删除的线性表,栈顶元素总是最终被插入的元素,从 而也是最先能被删除的元素；栈底元素总是最先被插入的元素,从而也是最终 才能被删除的元素,即栈是依据“先进后出”或“后进先出”

26、的原就组织数据 的,这便是栈的记忆作用,所以选项 A 和选项 C 正确；对栈进行插入和删除操 作时,栈顶位置是动态变化的,栈底指针不变,选项 D 正确；由此可见,选B 项 的描述错误； （ 27）对于长度为 n 的线性表,在最坏情形下,以下各排序法所对应的比较次 数 中正确选项； B）冒泡排序为 n A）冒泡排序为 n/2 C）快速排序为 n【答案】 D D）快速排序为 nn-1/2 【解析】假设线性表的长度为 n,在最坏情形下,冒泡排序和快速排序需要的比 较次数为 nn 1 2；由此可见,选项 D正 确； （ 28）对长度为 n 的线性表进行次序查找,在最坏情形下所需要的比较次数 为 ； 第

27、 14 页,共 151 页n A） log2 B）n/2 C） n D）n+1 【答案】 C 【解析】在长度为 n 的线性表中进行次序查找,最坏情形下需要比较 n 次；选 项 C 正 确； （ 29）以下对于线性链表的描述中正确选项 ； A） 储备空间不愿定是连续,且各元素的储备次序是任意的 B） 储备空间不愿定是连续,且前件元素确定储备在后件元素的前面 C） 储备空间必需连续,且前件元素确定储备在后件元素的前面 D） 储备空间必需连续,且各元素的储备次序是任意的 【答案】 A 【解析】在链式储备结构中,储备数据的储备空间可以不连续,各数据结点的 储备次序与数据元素之间的规律关系可以不一样,数

28、据元素之间的规律关系, 是由指针域来确定的；由此可见,选项 A 的描述正确； （ 30）某二叉树中度为 2 的结点有 18 个,就该二叉树中有 个叶子结点； 【答案】 19 【解析】二叉树具有如下性质：在任意一棵二叉树中,度为 O 的结点 即叶子 结 点 总是比度为 2 的结点多一个；依据题意,度为 2 的节点为 18 个,那么, 叶子结点就应当是 19 个； （ 1）线性表如接受链式储备结构时,要求内存中可用储备单元的地址 A）必需是连续的 B）部分地址必需是连续的 C）确定是不连续的 第 15 页,共 151 页D）连续不连续都可以 解析： 在链式储备结构中,储备数据结构的储备空间可以是连

29、续的,也可以是 不连续的,各数据结点的储备次序与数据元素之间的规律关系可以不一样；故 此题答案应当为选项 D） （ 2）在待排序的元素序列基本有序的前提下,效率最高的排序方法是 A）冒泡排序 B）选择排序 C）快速排序 D）归并排序 解析： 从平均时间性能而言,快速排序正确,其所需时间最少,但快速排序在 最坏情形下的时间性能不如堆排序和归并排序；当序列中的记录基本有序或元 素个数较少时,冒泡排序和简洁选择排序为正确排序方法,故此题答案应当为 选项 A）； （ 3）以下表达中,错误选项 A）数据的储备结构与数据处理的效率亲热相关 B）数据的储备结构与数据处理的效率无关 C）数据的储备结构在运算机

30、中所占的空间不愿定是连续的 D）一种数据的规律结构可以有多种储备结构 解析： 一般来说,一种数据结构依据需要可以表示成多种储备结构；常用的存 储结构有次序,链接,索引等,而接受不同的储备结构,其数据处理的效率是 不同的；一个数据结构中的各数据元素在运算机储备空间中的位置关系与规律 关系是有可能不同的；故此题答案应当为选项 B）； （ 4）希尔排序属于 第 16 页,共 151 页A）交换排序 B）归并排序 C）选择排序 D）插入排序 解析： 希尔排序的基本思想是把记录按下标的确定增量分组,对每组记录使用 插入排序,随增量的逐步减小,所分成的组包含的记录越来越多,到增量 的值减小到 1 时,整个

31、数据合成一组,构成一组有序记录,故其属于插入 排序方法；故此题答案应当为选项 D）； （ 1）栈和队列的共同特点是 A）都是先进先出 B）都是先进后出 C）只答应在端点处插入和删除元素 D）没有共同点 解析：栈和队列都是一种特别的操作受限的线性表,只答应在端点处进行插入 和删除； 二者的区分是： 栈只答应在表的一端进行插入或删除操作, 是一种“后 进先出”的线性表；而队列只答应在表的一端进行插入操作,在另一端进行删 除操作,是一种“先进先出”的线性表；故此题答案应当为选项 C）； （ 2）已知二叉树后序遍历序列是 历序列是 A） acbed B） decab C） deabc D） cedba

32、 dabec,中序遍历序列是 debac,它的前序遍 第 17 页,共 151 页解析： 依据后序遍历序列可确定根结点为 c；再依据中序遍历序列可知其左子 树由 deba 构成,右子树为空；又由左子树的后序遍历序列可知其根结点为 e, 由中序遍历序列可知其左子树为 d,右子树由 ba 构成,如下图所示；求得该二 叉树的前序遍历序列为选项 D）； （ 3）链表不具有的特点是 A）不必事先估量储备空间 B）可随机拜望任一元素 C）插入删除不需要移动元素 D）所需空间与线性表长度成正比 解析： 链表接受的是链式储备结构,它克服了次序储备结构的缺点：它的结点 空间可以动态申请和释放；它的数据元素的规律

33、次序靠结点的指针来指示, 不需要移动数据元素；但是链式储备结构也有不足之处： 每个结点中的 指针域需额外占用储备空间； 此题答案应当为选项 D）； （ 6）算法的时间复杂度是指 A）执行算法程序所需要的时间 B）算法程序的长度 链式储备结构是一种非随机储备结构；故 C）算法执行过程中所需要的基本运算次数 D）算法程序中的指令条数 第 18 页,共 151 页解析： 算法的复杂度主要包括算法的时间复杂度和算法的空间复杂度；所谓算 法的时间复杂度是指执行算法所需要的运算工作量；算法的空间复杂度一 般是指执行这个算法所需要的内存空间；故此题答案应当为选项 A）； （ 1）已知一棵二叉树前序遍历和中序

34、遍历分别为 二叉树的后序遍历为 A） GEDHFBCA B） DGEBHFCA C） ABCDEFGH D） ACBFEDHG ABDEGCF和H DBGEACH,F就 该 解析： 利用前序和中序遍历的方法可以确定二叉树的结构,详细步骤如下： 前序遍历的第一个结点 A 为树的根结点； 中序遍历中 A 的左边的结点 为 A 的 左子树, A 右边的结点为 A 的右子树； 再分别对 A 的左右子树进行上述两步 处理,直到每个结点都找到正确的位置；故此题答案应当为选项 B）； （ 2）树是结点的集合,它的根结点数目是 A）有且只有 1 B） 1 或多于 1 C） 0 或 1 D）至少 2 解析： 树

35、是一个或多个结点组成的有限集合,其中一个特定的结点称为根,其 余结点分为如干个不相交的集合；每个集合同时又是一棵树；树有且只有 1 个 根结点；故此题答案应当为选项 A）； （ 3）假如进栈序列为 e1,e2,e3,e4 ,就可能的出栈序列是 A） e3,e1,e4,e2 第 19 页,共 151 页B） e2,e4,e3,e1 C） e3,e4,e1,e2 D）任意次序 解析： 由栈 后进先出 的特点可知： A）中 e1 不行能比 e2 先出, C）中 e3 不 可能比 e4 先出,且 e1 不行能比 e2 先出, D）中栈是先进后出的,所以不行能 是任意次序； B）中出栈过程如以下图： 故

36、此题答案应当为选项 B）； （ 4）在设计程序时,应接受的原就之一是 A）不限制 goto 语句的使用 B）削减或取消注解行 C）程序越短越好 D）程序结构应有助于读者懂得 解析：滥用 goto 语句将使程序流程无规律,可读性差,因此 A）不选；注解行 有利于对程序的懂得,不应削减或取消, B）也不选；程序的长短要依照实际情 况而论,而不是越短越好, C）也不选；故此题答案应当为选项 D）； （ 5）程序设计语言的基本成分是数据成分,运算成分,把握成分和 A）对象成分 B）变量成分 C）语句成分 第 20 页,共 151 页D）传输成分 解析： 程序设计语言是用于书写运算机程序的语言,其基本成

37、分有以下 4 种, 数据成分：用来描述程序中的数据；运算成分：描述程序中所需的运算； 把握成分：用来构造程序的规律把握结构；传输成分：定义数据传输成分, 如输入输出语言；故此题答案应当为选项 D）； （ 1）循环链表的主要优点是 A）不再需要头指针了 B）从表中任一结点动身都能拜望到整个链表 C）在进行插入,删除运算时,能更好的保证链表不断开 D）已知某个结点的位置后,能够简洁的找到它的直接前件 解析： 循环链表就是将单向链表中最终一个结点的指针指向头结点,使整个链 表构成一个环形,这样的结构使得从表中的任一结点动身都能拜望到整个链表； 故此题答案应当为选项 B）； （ 2）栈底至栈顶依次存放

38、元素 A,B,C,D,在第五个元素 E 入栈前,栈中元素 可以出栈,就出栈序列可能是 A） ABCED B） DCBEA C） DBCEA D） CDABE 解析： 栈操作原就上“后进先出” ,栈底至栈顶依次存放元素 A, B,C,D,就 说明这 4 个元素中 D 是最终进栈, B,C 处于中间, A 最早进栈；所以出栈时一 定是先出 D,再出 C,最终出 A；故此题答案应当为选项 B）； （ 3）对长度为 N 的线性表进行次序查找,在最坏情形下所需要的比较次数为 第 21 页,共 151 页； A N+1 B N C N+1/2 D N/2 解析： 答案 B ,很简洁,我们的二级程序设计语言

39、书中都有此算法,另外仍要 把握二分法查找,这也是我们二级中常考的；那么二分法最坏的情形为多 少次呢？ log2 n的最小整数值；比如 n 为 4,最坏的情形要比较 3 次； n 为 18,最坏的情形要比较 5 次； （ 1）以下表达中正确选项 A）线性表是线性结构 B）栈与队列是非线性结构 C）线性链表是非线性结构 D）二叉树是线性结构 解析： 线性表是一种线性结构,数据元素在线性表中的位置只取决于它们自己 的序号,即数据元素之间的相对位置是线性的；栈,队列,线性链表实际上也 是线性表,故也是线性结构；树是一种简洁的非线性结构；故此题答案应当为 选项 A）； （ 2）非空的循环单链表 head

40、 的尾结点（由 p 所指向）,中意 A） p-next=NULL B） p=NULL C） p-next=head D） p=head 第 22 页,共 151 页解析： 循环链表就是将链表的最终一个结点指向链表头结点（或第一个结点） , 即 p-next=head ；故此题答案应当为选项 C）； （ 3）已知数据表 A 中每个元素距其最终位置不远,为节省时间,应接受的算法 是 A）堆排序 B）直接插入排序 C）快速排序 D）直接选择排序 解析： 当数据表 A 中每个元素距其最终位置不远,说明数据表 A 按关键字值 基 本有序,在待排序序列基本有序的情形下,接受插入排序所用时间最少,故答 案为

41、选项 B）； （ 1）假设线性表的长度为 n,就在最坏情形下,冒泡排序需要的比较次数为 nA） log2 B） n C） O（） D） n（n-1 ）/2 解析： 假设线性表的长度为 n,就在最坏情形下,冒泡排序要经过 n/2 遍的从 前往后的扫描和 n/2 遍的从后往前的扫描,需要的比较次数为 n（ n-1 ）/2 ；故 此题答案应当为选项 D）； （ 2）算法分析的目的是 A）找出数据结构的合理性 B）找出算法中输入和输出之间的关系 C）分析算法的易懂性和牢靠性 第 23 页,共 151 页D）分析算法的效率以求改进 解析： 算法分析是指对一个算法的运行时间和占用空间做定量的分析,一般计

42、算出相应的数量级,常用时间复杂度和空间复杂度表示；分析算法的目的就是 要降低算法的时间复杂度和空间复杂度,提高算法的执行效率；故此题答案应 该为选项 D）； （ 3）线性表 L=（a1,a2,a3, ai , an）,以下说法正确选项 A）每个元素都有一个直接前件和直接后件 B）线性表中至少要有一个元素 C）表中诸元素的排列次序必需是由小到大或由大到小 D）除第一个元素和最终一个元素外,其余每个元素都有一个且只有一个直接前 件和直接后件 解析： 线性表可以为空表；第一个元素没有直接前件,最终一个元素没有直接 后件；线性表的定义中,元素的排列并没有规定大小次序；故此题答案应当为 选项 D）； （

43、 4）在单链表中,增加头结点的目的是 A）便利运算的实现 B）使单链表至少有一个结点 C）标识表结点中首结点的位置 D）说明单链表是线性表的链式储备实现 解析： 头结点不仅标识了表中首结点的位置,而且依据单链表（包含头结点） 的结构,只要把握了表头,就能够拜望整个链表,因此增加头结点目的是为了 便于运算的实现；故此题答案应当为选项 A）； （ 1）算法的空间复杂度是指 第 24 页,共 151 页A）算法程序的长度 B）算法程序中的指令条数 C）算法程序所占的储备空间 D）执行过程中所需要的储备空间 解析： 算法的复杂度主要包括算法的时间复杂度和算法的空间复杂度；所谓算 法的时间复杂度是指执行

44、算法所需要的运算工作量；算法的空间复杂度一般是 指执行这个算法所需要的内存空间；故此题答案应当为选项 D）； （ 2）用链表表示线性表的优点是 A）便于随机存取 B）花费的储备空间较次序储备少 C）便于插入和删除操作 D）数据元素的物理次序与规律次序相同 解析： 链式储备结构克服了次序储备结构的缺点：它的结点空间可以动态申请 和释放；它的数据元素的规律次序靠结点的指针来指示,不需要移动数据元素； 故链式储备结构下的线性表便于插入和删除操作；故此题答案应当为选项 C）； （ 3）数据结构中,与所使用的运算机无关的是数据的 A）储备结构 B）物理结构 C）规律结构 D）物理和储备结构 解析： 数据

45、结构概念一般包括 3 个方面的内容,数据的规律结构,储备结构及 数据上的运算集合；数据的规律结构只抽象的反映数据元素之间的规律关 系,而不管它在运算机中的储备表示形式；故此题答案应当为选项 C）； 第 25 页,共 151 页（ 1）由两个栈共享一个储备空间的好处是 A）削减存取时间,降低下溢发生的机率 B）节省储备空间,降低上溢发生的机率 C）削减存取时间,降低上溢发生的机率 D）节省储备空间,降低下溢发生的机率 解析： 经常一个程序中要用到多个栈,为了不发生上溢错误,就必需给每个栈 支配一个足够大的储备空间；但实际中,很难精确地估量,如每个栈都支配过 大的储备空间,势必造成系统空间紧急；如

46、让多个栈共用一个足够大的连续存 储空间,就可利用栈的动态特性使他们的储备空间互补；故此题答案应当为选 项 B）； （ 2）设有两个串 p 和 q,求 q 在 p 中首次显现位置的运算称作 A）连接 B）模式匹配 C）求子串 D）求串长 解析： 子串的定位操作通常称作串的模式匹配,是各种串处理系统中最重要的 操作之一,算法的基本思想是：从主串的开头字符起和模式的第一个字符比较, 如相等就连续比较后续字符,否就从主串的下一个字符起再重新和模式的字符 比较,依次类推,直至模式中的每一个字符依次和主串中的一个连续的字符序 列相等,称匹配胜利,否就称匹配不胜利； （ 3）以下关于队列的表达中正确选项 ；

47、 A. 在队列中只能插入数据 B. 在队列中只能删除数据 第 26 页,共 151 页C. 队列是先进先出的线性表 D. 队列是先进后出的线性表 解析： C 队列是先进先出的,栈是先进后出的, 2 者的区分确定要搞清楚； 1 算法的空间复杂度是指 A 算法程序的长度 B 算法程序中的指令条数 C执行算法程序所占的储备空间 D算法执行过程中所需要的储备空间 【答案】 D 【解析】算法的空间复杂度一般是指这个算法执行时所需要的内存空间,其中 包括算法程序所占的空间,输入的初始数据所占的储备空间以及算法执行过程 中所需要的额外空间,其中额外空间仍包括算法程序执行过程的工作单元以及 某种数据结构所需要

48、的附加储备空间； （ 2）线性表的链式储备结构是一种 A 随机结构 B 次序结构 C索引结构 D散列结构 【答案】 B 【解析】线性表的链式储备结构中的每一个储备结点不仅含有一个数据元素, 仍包括指针,每一个指针指向一个与本结点有规律关系的结点；此类储备方式 属于次序储备； 第 27 页,共 151 页（ 3）设有以下二叉树：对此二叉树先序遍历的结果是 AABCDEF BDBEAFC CABDECF DDEBFCA 【答案】 C 【解析】二叉树的遍历分为先序,中序,后序三种不同方式；此题要求先序遍 历；遍历次序应当为：拜望根结点 - 先序遍历左子树 - 先序遍历右子树；按 照定义,先序遍历序列

49、是 ABDEC；F （ 1）算法分析的目的是 ； A）找出数据结构的合理性 B ）找出算法中输入和输出之间的关系 C）分析算法的易懂性和牢靠性 答案： D D）分析算法的效率以求改进 评析：算法分析是指对一个算法的运行时间和占用空间做定量的分析,一般计 算出相应的数量级,常用时间复杂度和空间复杂度表示；分析算法的目的就是 要降低算法的时间复杂度和空间复杂度,提高算法的执行效率； （ 3）已知数据表 A 中每个元素距其最终位置不远,为节省时间,应接受的算法 是； B）直接插入排序 D）直接选择排序 A）堆排序 C）快速排序 答案： B 评析：当数据表 A 中每个元素距其最终位置不远,说明数据表

50、A 按关键字值基 本有序,在待排序序列基本有序的情形下,接受插入排序所用时间最少,故答 第 28 页,共 151 页案为选项 B； （ 4）用链表表示线性表的优点是 ； A）便于插入和删除操作 B）数据元素的物理次序与规律次序相同 C）花费的储备空间较次序储备少 答案： A D）便于随机存取 评析：链式储备结构克服了次序储备结构的缺点：它的结点空间可以动态申请 和释放；它的数据元素的规律次序靠结点的指针来指示,不需要移动数据元素； 故链式储备结构下的线性表便于插入和删除操作； 1. 以下数据结构中不属于线性数据结构的是 ； A ,队列 B ,线性表 C ,二叉树 D ,栈 解析 : 线性表,栈

51、和队列等数据结构所表达和处理的数据以线性结构为组织形 式；栈是一种特别的线性表,这种线性表只能在固定的一端进行插入和删除操 作,答应插入和删除的一端称为栈顶,另一端称为栈底；一个新元素只能从栈 顶一端进入,删除时,只能删除栈顶的元素,即刚刚被插入的元素；所以栈又 称后进先出表（ Last In First Out ）；队列可看作是插入在一端进行,删除在 另一端进行的线性表,答应插入的一端称为队尾,答应删除的一端称为队头； 在队列中,只能删除队头元素,队列的最终一个元素确定是最新入队的元素； 因此队列又称先进先出表（ First In First Out ）； 此题答案为 C； 5. 以下关于栈

52、的表达中正确选项 ； A,在栈中只能插入数据 B,在栈中只能删除数据 C,栈是先进先出的线性表 D,栈是先进后出的线性表 解析 : 栈是限定在一端进行插入与删除的线性表； 栈是依据 先进后出 的或后进先出的原就组织数据的,因此,栈也被称为 先进后出 表或 后进先出 表； 此题答案是 D； 7. 对长度为 N 的线性表进行次序查找,在最坏情形下所需要的比较次数为 第 29 页,共 151 页； A,N+1 B,NC,N+1/2 D,N/2 解析 : 在进行次序查找过程中,假如线性表中被查的元素是线性表中的最终一 个,或者被查元素根本不在线性表中,就为了查找这个元素需要与线性表中所 有元素进行比较

53、,这是次序查找最坏的情形； 此题答案为 B； 1. 在一棵二叉树上第 5 层的结点数最多是； A, 8 B, 16 C, 32 D, 15 解析 : 依据二叉树的性质：二叉树第 i （ i 1）层上至多有 2 个结点；得到第 5层的结点数最多是 16； 此题答案为 B； 3. 以下表达中正确选项 ； A,线性表是线性结构 B,栈与队列是非线性结构 C,线性链表是非线性结构 D,二叉树是线性结构 解析 : 依据数据结构中各数据元素之间前后间关系的复杂程度,一般将数据结构 分为两大类型：线性结构与非线性结构； 假如一个非空的数据结构中意以下两个条件：（ 1）有且只有一个根结点； （ 2）每一个结点

54、最多有一个前件,也最多有一个后件；就称该数据结构为线性 结构,又称线性表； 所以线性表,栈与队列,线性链表都是线性结构,而二叉树是非线性结构； 此题答案是 A； 7. 在以下选项中,哪个不是一个算法一般应当具有的基本特点 ； A,确定性 B,可行性 第 30 页,共 151 页C,无穷性 D,拥有足够的情报 解析 : 作为一个算法,一般应具有以下几个基本特点； 1 可行性 2 确定性 3 有穷性 4 拥有足够的情报 此题答案为 C； 5. 在运算机中,算法是指 ； A,查询方法 B,加工方法 C,解题方案的精确而完整的描述 D,排序方法 解析 : 运算机算法是指解题方案的精确而完整的描述,它有

55、以下几个基本特点： 可行性,确定性,有穷性和拥有足够的情报； 此题答案为 C； 7. 在单链表中,增加头结点的目的是 ； A,便利运算的实现 B,使单链表至少有一个结点 C,标识表结点中首结点的位置 D,说明单链表是线性表的链式储备实现 解析 : 头结点不仅标识了表中首结点的位置,而且依据单链表（包含头结点）的 结构,只要把握了表头,就能够拜望整个链表,因此增加头结点目的是为了便 于运算的实现； 此题答案为 A； 1. 数据的储备结构是指 ； A,储备在外存中的数据 B,数据所占的储备空间量 C,数据在运算机中的次序储备方式 D,数 据的规律结构在运算机中的表示 解析 : 此题考查的是数据结构

56、的基本概念； 数据的规律结构在运算机储备空间中的存放形式形式称为数据的储备结构 第 31 页,共 151 页（也称数据的物理结构）； 故此题答案为 D； 2. 以下关于栈的描述中错误选项 ； A,栈是先进后出的线性表 B,栈只能次序储备 C,栈具有记忆作用 D,对栈的插入与删除操作中,不需要转变栈底指针 解析 : 此题考查的是栈和队列； 栈是一种特别的线性表,这种线性表只能在固 定的一端进行插入和删除操 作,答应插入和删除的一端称为栈顶,另一端称为栈底；一个新元素只能从栈 顶一端进入,删除时,只能删除栈顶的元素,即刚刚被插入的元素；所以栈又 称先进后出表（ FILO-First In Last

57、 Out ）；线性表可以次序储备,也可以链 式储备,而栈是一种线性表,也可以接受链式储备结构； 故此题答案为 B； 3. 对于长度为 n 的线性表,在最坏情形下,以下各排序法所对应的比较次数中 正确选项； A,冒泡排序为 n/2 B,冒泡排序为 nC,快速排序为 n D,快速排序为 nn-1/2 解析 : 此题考查的是基本排序算法； 假设线性表的长度为 n,就在最坏情形下, 冒泡排序需要经过 n/2 遍的从前 往后扫描和 n/2 遍的从后往前扫描,需要比较次数为 最坏情形比较次数也是 nn-1/2 ； 故此题答案为 D； nn-1/2 ；快速排序法的 4. 对长度为 n 的线性表进行次序查找,

58、在最坏情形下所需要的比较次数为 ； A, log2n B, n/2 C, n D, n+1 第 32 页,共 151 页解析 : 此题考查的是次序查找； 在进行次序查找过程中,假如线性表中的第一个元素就是被查找元素,就 只需做一次比较就查找胜利,查找效率最高；但假如被查找的元素是线性表中 的最终一个元素,或者被查找的元素根本就不在线性表中,就为了查找这个元 素需要与线性表中全部的元素进行比较,这是次序查找的最坏情形；所以对长 度为 n 的线性表进行次序查找,在最坏情形下需要比较 n 次； 故此题答案为 C； 5. 以下对于线性链表的描述中正确选项 ； A,储备空间不愿定是连续,且各元素的储备次

59、序是任意的 B,储备空间不愿定是连续,且前件元素确定储备在后件元素的前面 C,储备空间必需连续,且前件元素确定储备在后件元素的前面 D,储备空间必需连续,且各元素的储备次序是任意的 解析 : 此题考查的是线性单链表,双向链表与循环链表的结构及其基本运算； 在链式储备结构中,储备数据结构的储备空间可以不连续,各数据结点的 储备次序与数据元素之间的规律关系可以不一样,而数据元素之间的规律关系 是由指针域来确定的； 故此题答案为 A； 1. 算法的时间复杂度是指 ； A,执行算法程序所需要的时间 B,算法程序的长度 C,算法执行过程中所 需要的基本运算次数 D,算法程序中的指令条数 解析 : 所谓算

60、法的时间复杂度,是指执行算法所需要的运算工作量； 为了能够比较客观地反映出一个算法的效率,在度量一个算法的工作量时, 不仅应当与所使用的运算机,程序设计语言以及程序编制者无关,而且仍应当 与算法实现过程中的许多细节无关；为此,可以用算法在执行过程中所需基本 运算的执行次数来度量算法的工作量； 此题答案是 C； 2. 以下表达中正确选项 ； A,线性表是线性结构 B,栈与队列是非线性结构 C,线性链表是非线性结构 第 33 页,共 151 页D,二叉树是线性结构 解析 : 依据数据结构中各数据元素之间前后间关系的复杂程度,一般将数据结构 分为两大类型：线性结构与非线性结构； 假如一个非空的数据结