国家二级VF机试（数据结构与算法）模拟试卷4
选择题
1.算法的有穷性是指(A)
A. 算法程序的运行时间是有限的
B. 算法程序所处理的数据量是有限的
C. 算法程序的长度是有限的
D. 算法只能被有限的用户使用
解析：算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。
2.算法的空间复杂度是指(A)
A. 算法在执行过程中所需要的计算机存储空间
B. 算法所处理的数据量
C. 算法程序中的语句或指令条数
D. 算法在执行过程中所需要的临时工作单元数
解析：算法的空间复杂度是指执行这个算法所需要的内存空间。这个内存空间包括算法程序所占的空间，输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。
3.下列叙述中正确的是(B)
A. 算法的效率只与问题的规模有关，而与数据的存储结构无关
B. 算法的时间复杂度是指执行算法所需要的计算工作量
C. 数据的逻辑结构与存储结构是一一对应的
D. 算法的时间复杂度与空间复杂度一定相关
解析：算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算的次数来度量，而算法所执行的基本运算次数是问题规模的函数；算法的空间复杂度一般是指执行这个算法所需要的内存空间。算法的时间复杂度与空间复杂度并不相关。数据的逻辑结构就是数据元素之间的逻辑关系，它是从逻辑上描述数据元素之间的关系，是独立于计算机的；数据的存储结构是研究数据元素和数据元素之间的关系如何在计算机中表示，它们并非一一对应。算法的执行效率不仅与问题的规模有关，还与数据的存储结构有关。
4.数据的存储结构是指(D)
A. 存储在外存中的数据
B. 数据所占的存储空间量
C. 数据在计算机中的顺序存储方式
D. 数据的逻辑结构在计算机中的表示
解析：在对数据进行处理时，各数据元素在计算机中的存储关系，即为数据的存储结构。
5.下列描述中正确的是(D)
A. 数据的逻辑结构与存储结构必定是一一对应的
B. 由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构
C. 程序设计语言中的数据一般是顺序存储结构，因此，利用数组只能处理线性结构
D. 以上三种说法都不对
解析：数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)。一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等。
6.下列数据结构中，属于非线性结构的是(C)
A. 循环队列
B. 带链队列
C. 二叉树
D. 带链栈
解析：根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类：线性结构和非线性结构。循环队列、带链队列和带链栈都是线性结构，而二叉树是非线性结构。
7.下面叙述中正确的是(A)
A. 线性表是线性结构
B. 栈与队列是非线性结构
C. 线性链表是非线性结构
D. 二叉树是线性结构
解析：线性表是最简单的、最常用的一种线性结构。所谓线性链表指的是采用链式存储结构的线性表。栈和队列其实是一种特殊的线性表。树是一种简单的非线性结构，二叉树是树的一种。
8.支持子程序调用的数据结构是(A)
A. 栈
B. 树
C. 队列
D. 二叉树
解析：栈是一种限定在一端进行插入与删除的线性表。在主函数调用子函数时，要首先保存主函数当前韵状态，然后转去执行子函数，把子函数的运行结果返回到主函数调用子函数时的位置，主函数再接着往下执行，这种过程符合栈的特点。所以一般采用栈式存储方式。
9.下列关于栈叙述正确的是(A)
A. 栈顶元素最先能被删除
B. 栈顶元素最后才能被删除
C. 栈底元素永远不能被删除
D. 以上三种说法都不对
解析：栈是先进后出的线性表，栈顶的元素最先被删除，栈底的元素最后被删除。
10.下列叙述中正确的是(C)
A. 在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化
B. 在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化
C. 在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化
D. 上述三种说法都不对
解析：在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。栈跟队列不同，元素只能在栈顶压入或弹出，栈底指针不变，栈中元素随栈顶指针的变化而动态变化，遵循后进先出的规则。
11.一个栈的初始状态为空。现将元素1，2，3，A，B，C依次入栈，然后再依次出栈，则元素出栈的顺序是(C)
A. 1，2，3，A，B，C
B. C，B，A，1，2，3
C. C，B，A，3，2，1
D. 1，2，3，C，B，A
解析：栈是按照“先进后出”或“后进先出”的原则组织数据的。所以出栈顺序是CBA321。
12.按照“后进先出”原则组织数据的数据结构是(B)
A. 队列
B. 栈
C. 双向链表
D. 二叉树
解析：栈是限定在一端进行插入与删除的线性表。在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素，也是最先被删除的元素；栈底元素总是最先被插入的元素，也是最后才能被删除的元素。即栈是按照“后进先出”(Last In First Out，简称LIFO)或“先进后出”(First In Last Out，简称FILO)的原则组织数据的。因此，栈也称为“后进先出表”或“先进后出”表。
13.下列叙述中正确的是(D)
A. 栈是一种先进先出的线性表
B. 队列是一种后进先出的线性表
C. 栈与队列都是非线性结构
D. 以上三种说法都不对
解析：栈是先进后出的线性表，队列是先进先出的线性表，二者均为线性结构。
14.下列关于栈的描述中正确的是(C)
A. 在栈中只能插入元素而不能删除元素
B. 在栈中只能删除元素而不能插入元素
C. 栈是特殊的线性表，只能在一端插入或删除元素
D. 栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素
解析：栈是限定在一端进行插入与删除的线性表，在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。
15.对于循环队列，下列叙述中正确的是(D)
A. 队头指针是固定不变的
B. 队头指针一定大于队尾指针
C. 队头指针一定小于队尾指针
D. 队头指针可以大于队尾指针，也可以小于队尾指针
解析：所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列中，用队尾指针rear指向队列中的队尾元素，用队头指针front指向队头元素的前一个位置。循环队列的主要操作是：入队运算和退队运算。每进行一次入队运算，队尾指针就进一。每进行一次退队运算，队头指针就进一。当rear或front等于队列的长度加1时，就把rear或front值置为1。所以在循环队列中，队头指针可以大于队尾指针，也可以小于队尾指针。
16.设循环队列的存储空间为Q(1：35)，初始状态为fro
本文档预览：3600字符，共8428字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
