公共基础练习题库

《公共基础练习题库》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第一章数据结构一、选择题（1）卞列数据结构中，能用二分法进行查找的是A）顺序存储的有序线性表B）线性链表C）二叉链表D）有序线性链表【答案】A【解析】二分杏找只适用于顺序存储的有序表。在此所说的有序表是指线性表屮的元素按值非递减排列（即从小到大.但允许相邻元素值相等）的。选项A正确。（2）下列关于栈的描述正确的是A）在栈中只能插入元素而不能删除元素B）在栈中只能删除元素而不能插入元素C）栈是特殊的线性表，只能在一端插入或删除元素D）栈是特殊的线性表，只能在一端插入元索，而在另一端删除元索【答案】C【解析】栈是一种

2、特殊的线性表，具插入与删除运算都只在线性表的一端进行。由此可见,选项A、选项B和选项D错误，正确答案是选项C。（3）下列叙述中正确的是A）一个逻辑数据结构只能冇一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D）一•个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率【答案】D【解析】一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，

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

4、D）队列是先进后出的线性表【答案】c【解析】対队列可以进行插入和删除数据的操作，只是插入数据只能在队尾，删除数据只能在队头。所以队列是先进先出的线性表。（6）设有下列二叉树:对此二叉树后序遍历的结果为A）ABCDEFB）BDAECFC）ABDCEFD）DBEFCA【答案】D【解析】二叉树的遍历分为先序、中序、后序三种不同方式。本题要求后序遍历。英遍历顺序应该为：后序遍历左子树一〉后序遍历右子树一〉访问根结点。按照定义，后序遍历序列是DBEFCA,故答案为D。（7）下列叙述中正确的是（）A）程序执行的效率■数据的存

5、储结构密切相关3/119B）程序执行的效率只取决于程序的控制结构C）程序执行的效率只取决于所处理的数据量D）以上三种说法都不对【答案】A【解析】木题考查程序效率。程序效率是指程序运行速度和程序占用的存储空间。影响程序效率的因素是多方面的，包括程序的设计、使用的算法、数据的存储结构等。在确定数据逻辑结构的基础上，选择一种合适的存储结构，可以使得数据操作所花费的时间少，占用的存储空间少，即提高程序的效率。因此，木题选项A的说法是正确的。(8)下列叙述中正确的是()A)数据的逻辑结构•存储结构必定是一一对应的B)山于计

6、算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构C)程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线线结构D)以上三种说法都不对【答案】D【解析】本题考查数据结构的基本知识。数据Z间的相互关系称为逻辑结构。通常分为四类基本逻辑结构，即集合、线性结构、树型结构、图状结构或网状结构。存储结构是逻辑结构在存储器中的映彖，它包含数据元素的映象和关系的映象。存储结构在计算机屮有两种，即顺序存储结构和链式存储结构。顺序存储结构是把数据元素存储在一•块连续地址空间的内存中；链式存储结构是使用指

7、针把相互直接关联的节点链接起来。因此，这两种存储结构都是线性的。可见，逻辑结构和存储结构不是一一对应的。因此，选项A和选项B的说法都是错误的。无论数据的逻辑结构是线性的还是非线性的，只能选择顺序存储结构或链式存储结构來实现存储。程序设计语言中，数组是内存中一段连续的地址空间，可看作是顺序存储结构。可以用数组来实现树型逻辑结构的存储，比如二叉树。因此，选项c的说法是错课的⑼冒泡排序在最坏情况下的比较次数是()A)n(n+l)/2B)nlog2nC)n(n-l)/2D)n/2【答案】C【解析】冒泡排序的基本思想是：将

8、和邻的两个元素进行比较，如果反序，则交换；对于一个待排序的序列，经一趟排序后，最大值的元素移动到最后的位置，其他值较大的元素也向最终位置移动，此过程称为一趟冒泡。对于有n个数据的序列，共需n・l趟排序，第i趟对从1到mi个数据进行比较、交换。冒泡排序的最坏情况是待排序序列逆序，第1趟比较ml次，第2趟比较m2次。依此类推，最后趟比较1次，一共进行ml趟排序。因此，冒泡排序