二级公共基础知识数据结构与算法(三)模拟题

1、 模拟模拟 二级公共基础知识数据结构与算法二级公共基础知识数据结构与算法( (三三) )单项选择题单项选择题第 1 题：算法的空间复杂度是指_。a.算法在执行过程中所需要的计算机存储空间b.算法所处理的数据量c.算法程序中的语句或指令条数d.算法在执行过程中所需要的临时工作单元数参考答案：a一般来说， 一个算法的空间复杂度是指执行该算法所需的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、 输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。第 2 题：下列数据结构中，属于非线性结构的是_。a.循环队列b.带链队列c.二叉树d.带链栈参考答案：c线性结构满足两个条件：有且

2、只有一个根节点；每个节点最多有一个前件，也最多有一个后件。栈、队列都属于线性结构，栈是一种先进后出的线性结构，允许在栈顶进行插入或删除运算；队列则是一种先进先出的线性结构，允许在队尾进行捅入运算，而在队头进行删除运算。二叉树是一种非线性结构，因为除叶子节点，每个节点都有两个后件，不满足线性结构的条件。第 3 题：下列数据结构中，能够按照“先进后出”原则存取数据的是_。a.循环队列b.栈c.队列d.二叉树参考答案：b第 4 题：对于循环队列，下列叙述中正确的是_。a.队头指针是固定不变的b.队头指针一定大于队尾指针c.队头指针一定小于队尾指针d.队头指针可以大于队尾指针，也可以小于队尾指针参考答

3、案：d1第 5 题：下列叙述正确的是_。a.栈是“先进先出”的线性表b.队列是“后进先出”的线性表c.循环队列是非线性结构d.有序线性表既可以采用顺序存储结构，也可以采用链式存储结构参考答案：d栈是“先进后出”的线性表，而队列是“先进先出”的线性表，循环队列自然也是线性结构的， 有序线性表既可以采用顺序存储结构， 也可以采用链式存储结构。第 6 题：下列排序方法中，最坏情况下比较次数最少的是_。a.冒泡排序b.简单选择排序c.直接插入排序d.堆排序参考答案：d本题考查各种排序方法的时间复杂度，冒泡排序、简单选择排序、直接插入排序在最坏的情况下比较次数都是 o(n2)，而堆排序的时间复杂度为 o

4、(nlog2n)，这也是堆排序的最大优点。第 7 题：某二叉树有 5 个度为 2 的节点，则该二叉树中的叶了节点是数是_。a.10b.8c.6d.4参考答案：c由二叉树的性质得知，对于一个非空的二叉树， 叶子节点数等于度为 2 的节点数目1。第 8 题：支持子程序调用的数据结构是_。a.栈b.树c.队列d.二叉树参考答案：d在题目选项中， 栈是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表； 队列是一种只允许在一端进行插入，而在另一端进行删除的线性表，它也是一种操作受限的线性表；线性表是最简单、最常用的一种数据结构，是具有相同数据类型的 n(n0)个数据元素组成的有限序列；二

5、叉树是个有限元2素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。 这里仅有二叉树是支持子程序调用的。第 9 题：在长度为 n 的有序线性表中进行二分查找，最坏情况下需要比较的次数是_。a.o(n)b.o(n2)c.o(log2n)d.o(nlog2n)参考答案：c二分法查找只适用于顺序存储的有序表。二分查找的基本方法是：将被查元素x与线性表的中间项进行比较，若中问项的值等于 x，则说明查到；若小于中间项的值，则在线性表的前半部分以相同的方法进行查找；若大于中间项的值，则在线性表的后半部分以相同的方法进行查找。在最坏情况下，二分查

6、找需要比较log2n 次。第 10 题：下列叙述中正确的是_。a.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的b.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构c.顺序存储结构能存储有序表，链式存储结构不能存储有序表d.链式存储结构比顺序存储结构节省存储空间参考答案：a在顺序存储结构中所有元素所占的存储空间是连续的，而在链式存储结构中，存储数据结构的存储空间可以不连续，因此选项 a 是正确的。 线性表在计算机中的存放可以采用顺序存储结构，也可采用链式存储结构，顺序存储结构和链式存储结构都是既可用于线性结构， 也可以用于非线性结构， 因此选项 b、 c 是错误的

7、。采用链式存储结构，不仅要存储元素的值， 元素间的逻辑关系还需要通过附设的指针字段来表示，因此，链式存储结构需要更多的存储空间。第 11 题：下列叙述中正确的是_。a.循环队列有队头和队尾两个指针，因此，循环队列是非线性结构b.在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况c.在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况d.循环队列中元素的个数是由队头指针和队尾指针共同决定的参考答案：d循环队列是将队列存储空间的最后一个位置绕到第一个位置， 形成逻辑上的环形空间。循环队列仍然是顺序存储结构，是队列常采用的形式，因此选项 a 错误。在循环队列中，用队尾指针 rear

8、 指向队列中的队尾元素，用队头指针 front 指向队列排头元素的前一个位置。循环队列中的元素是动态变化的，每进行一次入队运算，对尾指针就进一；每进行一次出队运算，队头指针就进一。可见，由队3头指针和队尾指针一起反映队列中元素的动态变化情况，因此选项 b、c 是错误的。从队头指针 front 指向的后一个位置直到队尾指针 rear 指向的位置之间所有的元素均为队列中的元素，因此选项 d 是正确的。第 12 题：一个栈的初始状态为空。现将元素 1、2、3、4、5、a、b、c、d、e 依次入栈，然后再依次出栈，则元素出栈的顺序是_。a.12345a2bcdeb.edcba54321c.abcdel

9、2345d.54321edcba参考答案：b栈是按照“先进后出”的原则组织数据的，入栈的顺序为12345abcde，1 为栈底元素最后出栈，e 为栈顶元素最先出栈，因此出栈的顺序为 edcba54321。第 13 题：算法的时间复杂度取决于_。a.问题的规模b.待处理的数据的初始状态c.问题的困难度d.a 和 b参考答案：d第 14 题：计算机算法指的是_。a.计算方法b.调度方法c.排序方法d.解决某一问题的有限运算序列参考答案：d第 15 题：下列叙述中正确的是_。a.一个逻辑数据结构只能有一种存储结构b.数据的逻辑结构属于线性结构，存储结构属于非线性结构c.一个逻辑数据结构可以有多种存储

10、结构，且各种存储结构不影响数据处理的效率d.一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率参考答案：d第 16 题：数据的存储结构是指_。a.存储在外存中的数据b.数据所占的存储空间量4c.数据在计算机中的顺序存储方式d.数据的逻辑结构在计算机中的表示参考答案：d第 17 题：数据在计算机内存中的表示是指_。a.数据的存储结构b.数据结构c.数据的逻辑结构d.数据元素之问的关系参考答案：a第 18 题：数据的_包括集合、线性结构、树型结构和图形结构 4 种基本类型。a.算法描述b.基本运算c.逻辑结构d.存储结构参考答案：c第 19 题：下列关于栈的描述正确的是_。a.在

11、栈中只能捅入元素而不能删除元素b.在栈中只能删除元素而不能捅入元素c.栈是特殊的线性表，只能在一端捅入或删除元素d.栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素参考答案：c第 20 题：下列关于栈的描述中错误的是_。a.栈是先进后出的线性表b.栈只顺序存储c.栈具有记忆作用d.对栈的插入与删除操作中，不需要改变栈底指针参考答案：b第 21 题：假定利用数组 am 顺序存储一个栈，利用 top 表示栈顶指针，用 topn1 表示栈空，该数组所能存储的栈的最大长度为 n，则表示栈满的条件是_。a.top-1b.top0c.top1d.top1参考答案：d5第 22 题：在一个顺序存储的

12、循环队列中，队头指针指向队头元素的_。a.当前位置b.任意位置c.前一个位置d.后一个位置参考答案：c第 23 题：在单链表中，头指针的作用是_。a.方便运算的实现b.用于标识单链表c.使单链表中至少有一个节点d.用于标识首节点位置参考答案：b第 24 题：树最适合于表示_。a.有序数据元素b.元素之间无联系的数据c.无序数据元素d.元素之间具有分支层次关系的数据参考答案：d第 25 题：在用二叉链表表示的有 n 个节点的二叉树中，值为非空的链域的个数为_。a.n-1b.n+1c.2n-1d.2n+1参考答案：a第 26 题：下列数据结构中，能用二分法进行查找的是_。a.顺序存储的有序线性表b

13、.线性链表c.二叉链表d.有序线性链表参考答案：a第 27 题：对于长度为 n 的线性表进行顺序查找，在最坏情况下所需要的比较次数为6_。a.log2nb.n/2c.nd.n+1参考答案：c第 28 题：对于长度为 n 的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是_。a.冒泡排序为 n/2b.冒泡排序为 nc.快速排序为 nd.快速排序为 n(n-1)/2参考答案：d填空题第 29 题：描述算法的常用方法有_。参考答案：传统流程图、n-s 结构化流程图和伪码描述语言第 30 题：一个算法的时间复杂度是_的函数。参考答案：算法输入规模第 31 题：算法复杂度主要包括时间复杂度和

14、_复杂度。参考答案：空间第 32 题：对问题处理方案的正确而完整的描述称为_。参考答案：算法第 33 题：一个数据结构在计算机中的表示(映像)称为_。参考答案：数据的存储结构第 34 题：数据结构分为逻辑结构和存储结构，循环队列属于_结构。参考答案：逻辑第 35 题：在一个长度为 n 的顺序表中的删除第 i 个元素(0in-1)，需要向前移动_元素。7参考答案：n-i第 36 题：栈和队列的区别在于_。参考答案：删除运算不同第 37 题：从一个循环队列中删除一个元素，通常的操作是_。参考答案：先取出元素，后移动队头指针第 38 题：一棵二叉树第 6 层(根节点为第一层)的节点数最多为_个。参考答案：32第 39 题：某二叉树中度为 2 的节点有 18 个，则该二叉树中有_个叶子节点。参考答案：19第 40 题：设一棵 n 个节点的完全二叉树从根节点这一层开始，每一层上的节点按从左到右的顺序存储在数组 a1n中，设某个节点在数组中的位置为 i(1in)，则其父节点的位置是_。参考答案：i/2第 41 题：对 n 个记录的有序表进行二分查找法查找时，最大的比较次数是_。参考答案：log2n第 42 题：二分查找法的存储结构仅限于_，且是有序的。参考答案：顺序存储结构第 43 题：在插入排序和选择排序中，若原始记录基本正序，则选择_，若原始记录基本反序，则选择_。参