计算机二级公共基础知识题库及答案分析(4)

C）减少存取时间，降低上溢发生的机率 D）节省存储空间，降低下溢发生的机率

解析： 常常一个程序中要用到多个栈，为了不发生上溢错误，就必须给每个栈分配一个足够大的存储空间。但实际中，很难准确地估计，若每个栈都分配过大的存储空间，势必造成系统空间紧张；若让多个栈共用一个足够大的连续存储空间，则可利用栈的动态特性使他们的存储空间互补。故本题答案应该为选项B）。

（2）设有两个串p和q，求q在p中首次出现位置的运算称作 A）连接 B）模式匹配 C）求子串 D）求串长

解析：B 子串的定位操作通常称作串的模式匹配，是各种串处理系统中最重要的操作之一，算法的基本思想是：从主串的开始字符起和模式的第一个字符比较，若相等则继续比较后续字符，否则从主串的下一个字符起再重新和模式的字符比较，依次类推，直至模式中的每一个字符依次和主串中的一个连续的字符序列相等，称匹配成功，否则称匹配不成功。

（3）下列关于队列的叙述中正确的是______。 A. 在队列中只能插入数据 B. 在队列中只能删除数据 C. 队列是先进先出的线性表 D. 队列是先进后出的线性表 解析：C

队列是先进先出的，栈是先进后出的，2者的区别一定要搞清楚。

(1)算法的空间复杂度是指 A)算法程序的长度 B)算法程序中的指令条数 C)执行算法程序所占的存储空间 D)算法执行过程中所需要的存储空间 【答案】D

【解析】算法的空间复杂度一般是指这个算法执行时所需要的内存空间，其中包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间，其中额外空间还包括算法程序执行过程的工作单元以及某种数据结构所需要的附加存储空间。

（2）线性表的链式存储结构是一种 A)随机结构 B)顺序结构

16 / 90

C)索引结构 D)散列结构 【答案】B

【解析】线性表的链式存储结构中的每一个存储结点不仅含有一个数据元素，还包括指针，每一个指针指向一个与本结点有逻辑关系的结点。此类存储方式属于顺序存储。

（3）设有下列二叉树：对此二叉树先序遍历的结果是 A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA 【答案】C

【解析】二叉树的遍历分为先序、中序、后序三种不同方式。本题要求先序遍历；遍历顺序应该为：访问根结点-＞先序遍历左子树-＞先序遍历右子树。按照定义，先序遍历序列是ABDECF。

（1）算法分析的目的是______。

A）找出数据结构的合理性 B）找出算法中输入和输出之间的关系 C）分析算法的易懂性和可靠性 D）分析算法的效率以求改进 答案：D

评析：算法分析是指对一个算法的运行时间和占用空间做定量的分析，一般计算出相应的数量级，常用时间复杂度和空间复杂度表示。分析算法的目的就是要降低算法的时间复杂度和空间复杂度，提高算法的执行效率。

（3）已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是______。 A）堆排序 C）快速排序 答案：B

评析：当数据表A中每个元素距其最终位置不远，说明数据表A按关键字值基本有序，在待排序序列基本有序的情况下，采用插入排序所用时间最少，故答案为选项B。

（4）用链表表示线性表的优点是______。

A）便于插入和删除操作 B）数据元素的物理顺序与逻辑顺序相同 C）花费的存储空间较顺序存储少 D）便于随机存取 答案：A

评析：链式存储结构克服了顺序存储结构的缺点：它的结点空间可以动态申请和释放；它的数据元素的逻 辑次序靠结点的指针来指示，不需要移动数据元素。故链式存储结构下的线性表便于插入和删除操作。

1. 以下数据结构中不属于线性数据结构的是______。

17 / 90

B）直接插入排序 D）直接选择排序

A、队列 B、线性表 C、二叉树 D、栈

解析:线性表、栈和队列等数据结构所表达和处理的数据以线性结构为组织形式。栈是一种特殊的线性表，这种线性表只能在固定的一端进行插入和删除操作，允许插入和删除的一端称为栈顶，另一端称为栈底。一个新元素只能从栈顶一端进入，删除时，只能删除栈顶的元素，即刚刚被插入的元素。所以栈又称后进先出表（Last In First Out）；队列可看作是插入在一端进行，删除在另一端进行的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。在队列中，只能删除队头元素，队列的最后一个元素一定是最新入队的元素。因此队列又称先进先出表（First In First Out）。 本题答案为C。

5. 下列关于栈的叙述中正确的是______。

A、在栈中只能插入数据 B、在栈中只能删除数据 C、栈是先进先出的线性表 D、栈是先进后出的线性表

解析:栈是限定在一端进行插入与删除的线性表。

栈是按照\先进后出\的或后进先出的原则组织数据的，因此，栈也被称为\先进后出\表或\后进先出\表。

本题答案是D。

7. 对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为______。

A、N+1 B、N C、(N+1)/2 D、N/2

解析:在进行顺序查找过程中，如果线性表中被查的元素是线性表中的最后一个，或者被查元素根本不在线性表中，则为了查找这个元素需要与线性表中所有元素进行比较，这是顺序查找最坏的情况。 本题答案为B。

1. 在一棵二叉树上第5层的结点数最多是______。 A、8 B、16 C、32 D、15

解析:根据二叉树的性质：二叉树第i（i≥1）层上至多有2i-1个结点。得到第5层的结点数最多是16。 本题答案为B。

3. 下列叙述中正确的是______。 A、线性表是线性结构 B、栈与队列是非线性结构 C、线性链表是非线性结构 D、二叉树是线性结构

18 / 90

解析:根据数据结构中各数据元素之间前后间关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。

如果一个非空的数据结构满足下列两个条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构，又称线性表。 所以线性表、栈与队列、线性链表都是线性结构，而二叉树是非线性结构。 本题答案是A。

7. 在下列选项中，哪个不是一个算法一般应该具有的基本特征______。 A、确定性 B、可行性 C、无穷性 D、拥有足够的情报

解析:作为一个算法，一般应具有以下几个基本特征。 1)可行性 2)确定性 3)有穷性 4)拥有足够的情报 本题答案为C。

5. 在计算机中，算法是指______。 A、查询方法 B、加工方法

C、解题方案的准确而完整的描述 D、排序方法

解析:计算机算法是指解题方案的准确而完整的描述，它有以下几个基本特征：可行性、确定性、有穷性和拥有足够的情报。 本题答案为C。

7. 在单链表中，增加头结点的目的是______。 A、方便运算的实现 B、使单链表至少有一个结点 C、标识表结点中首结点的位置 D、说明单链表是线性表的链式存储实现

解析:头结点不仅标识了表中首结点的位置，而且根据单链表（包含头结点）的结构，只要掌握了表头，就能够访问整个链表，因此增加头结点目的是为了便于运算的实现。 本题答案为A。

1. 数据的存储结构是指______。 A、存储在外存中的数据 B、数据所占的存储空间量 C、数据在计算机中的顺序存储方式

19 / 90

D、数据的逻辑结构在计算机中的表示 解析:本题考查的是数据结构的基本概念。

数据的逻辑结构在计算机存储空间中的存放形式形式称为数据的存储结构（也称数据的物理结构）。 故本题答案为D。

2. 下列关于栈的描述中错误的是______。 A、栈是先进后出的线性表 B、栈只能顺序存储 C、栈具有记忆作用

D、对栈的插入与删除操作中，不需要改变栈底指针 解析:本题考查的是栈和队列。

栈是一种特殊的线性表，这种线性表只能在固定的一端进行插入和删除操作，允许插入和删除的一端称为栈顶，另一端称为栈底。一个新元素只能从栈顶一端进入，删除时，只能删除栈顶的元素，即刚刚被插入的元素。所以栈又称先进后出表（FILO-First In Last Out）。线性表可以顺序存储，也可以链式存储，而栈是一种线性表，也可以采用链式存储结构。 故本题答案为B。

3. 对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是______。 A、冒泡排序为n/2 B、冒泡排序为n C、快速排序为n D、快速排序为n(n-1)/2

解析:本题考查的是基本排序算法。

假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后扫描和n/2遍的从后往前扫描，需要比较次数为n(n-1)/2。快速排序法的最坏情况比较次数也是n(n-1)/2。 故本题答案为D。

4. 对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为______。 A、log2n B、n/2 C、n D、n+1

解析:本题考查的是顺序查找。

在进行顺序查找过程中，如果线性表中的第一个元素就是被查找元素，则只需做一次比较就查找成功，查找效率最高；但如果被查找的元素是线性表中的最后一个元素，或者被查找的元素根本就不在线性表中，则为了查找这个元素需要与线性表中所有的元素进行比较，这是顺序查找的最坏情况。所以对长度为n的线性表进行顺序查找，在最坏情况下需要比较n次。 故本题答案为C。

5. 下列对于线性链表的描述中正确的是______。 A、存储空间不一定是连续，且各元素的存储顺序是任意的

20 / 90

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库计算机二级公共基础知识题库及答案分析(4)在线全文阅读。