点击查看：2015年计算机二级公共基础知识考点测试题汇总

　　线性表及其顺序存储结构

　　1[单选题]下列叙述中正确的是(　　)。

　　参考答案：A

　　参考解析：顺序存储结构中各数据元素在存储空间中是按逻辑顺序依次连续存放的，在链式存储结构中元素之间的关系通过指针来连接，所以不要求存储空间一定是连续的;顺序存储结构(或链式存储结构)既可以针对线性结构，也可以针对非线性结构，但像栈、队列这样的线性结构一般采用顺序存储结构(但也可以采用链式结构)，树、二叉树这样的非线性结构一般采用链式存储结构(但也可以采用顺序存储结构);链式存储结构既可以存储无序表，也可以存储有序表，注意，链式存储结构存储的即使是有序表，也不能进行二分查找;链式存储结构比顺序存储结构要多使用存储空间，由于链式存储结构中要用额外空间来保存指针。因此本题的正确答案是A。

　　2[单选题]对长度n的线性表排序，在最坏情况下，比较次数不是n(n-1)/2的排序方法是(　　)

　　A.快速排序B.冒泡排序C.直接插入排序D.堆排序

　　参考答案：D

　　参考解析：排序技术有：①交换类排序法(冒泡排序法、快速排序法);②插入类排序法(简单插入排序、希尔排序);③选择类排序法(简单选择排序法、堆排序法)。在最坏情况下，希尔排序需要的比较次数是O(nl.5)、堆排序需要的比较次数是O(nlog2n)、其它排序方法需要的比较次数都是n(n.1)/2。因此本题的正确答案是D。

　　3[单选题]下列叙述中正确的是(　　)

　　A.线性链表是线性表的链式存储结构

　　B.栈与队列是非线性结构

　　C.双向链表是非线性结构

　　D.只有根结点的二叉树是线性结构

　　参考答案：A

　　参考解析：线性表的链式存储结构称为线性链表;栈、队列、双向链表都是线性结构;树、二叉树(不管它有多少个结点)都是非线性结构。因此本题的正确答案是A。

　　4[单选题]一个栈的初始状态为空，现将元素l、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是(　)。【考点3栈】

　　A.12345ABCDEB.EDCBA54321C.ABCDEl2345D.54321EDCBA

　　参考答案：B

　　参考解析：栈是按照“先进后出”或“后进先出”的原则组织数据的，所以出栈顺序是EDCBA54321。

　　5[单选题]下列关于链表结构的叙述正确的是(　　)

　　A.线性链表、带链的栈和带链的队列的结点的结构都是相同的

　　B.双向链表也就是循环链表

　　C.线性链表与带链的栈的结点的结构是不同的

　　D.在循环链表中通过任意一个结点可以找到链表中其他所有的结点，而在双向链表中做不到这一点

　　参考答案：A

　　6[单选题]在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为(　　)

　　A.63B.64C.6D.7

　　参考答案：B

　　参考解析：只要是顺序查找(不管线性表是有序还是无序)，都是从表头到表尾逐个比较，若相同则结束查找，否则-直继续比较下一个表中元素，直到整个表都遍历完。对于长度为64的线性表，平均要进行64/2=32次比较，在最坏情况下要进行64次比较。若采用二分(折半)查找，则最坏情况下需要比较的次数为109264=6次，但要注意采用二分(折半)查找的条件，必须是线性表采用顺序存储结构，而且线性表中的元素要有序，这两个条件缺-不可。若对线性链表进行查找，则不管线性链表中的元素是有序还是无序只能采用顺序查找。因此本题的正确答案是B。

　　7[单选题]下列对于线性链表的描述中正确的是(　　)

　　A.存储空间不-定是连续，且各元素的存储顺序是任意的

　　B.存储空间不-定是连续，且前件元素-定存储在后件元素的前面

　　C.存储空间必须连续，且前件元素-定存储在后件元素的前面

　　D.存储空间必须连续，且各元素的存储顺序是任意的

　　参考答案：A

　　参考解析：线性链表是通过增加一个指针域来把相邻的数据元素链接成一个线性序列。线性链表的这种结构使得它存储数据的空间可以是离散的，并不像顺序表那样-定要求物理上的连续空间。因此选项A正确

　　8[填空题]线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的(　　)存储结构。

　　参考解析：顺序

　　【分析】在实际应用中，队列的顺序存储结构一般采用循环队列的形式。

　　9[单选题]下列叙述中正确的是(　　)。

　　A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的

　　B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构

　　C.顺序存储结构能存储有序表，链式存储结构不能存储有序表

　　D.链式存储结构比顺序存储结构节省存储空间

　　参考答案：A

　　参考解析：顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。而链式存储结构的存储空间不一定是连续的。

　　10[单选题]数据的存储结构是指(　　)

　　A.存储在外存中的数据

　　B.数据所占的存储空间量

　　C.数据在计算机中的顺序存储方式

　　D.数据的逻辑结构在计算机中的表示

　　参考答案：D

　　参考解析：数据的逻辑结构是指数据元素之间的逻辑关系的数据结构。数据的存储结构则是数据的逻辑结构在计算机中的物理实现，有时也称作数据的物理结构。两者的区别是数据的逻辑结构只涉及到数据之间抽象的数学关系。存储结构则涉及到如何在计算机中通过对数据的物理存储进行组织来表达数据元素之间的逻辑关系。比如在线性表的顺序存储中是利用物理存储空间上的连续性来表达线性表中数据的前后件关系;在线性表的链式存储中是通过指针域构成的逻辑链条来表达数据的前后件关系。-般的，-种数据的逻辑结构对应的物理实现，即数据的存储结构不止-种。因此选项D正确。

　　11[单选题]下列叙述中正确的是(　　)

　　A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不-定是连续的

　　B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构

　　C.顺序存储结构能存储有序表，链式存储结构不能存储有序表

　　D.链式存储结构比顺序存储结构节省存储空间

　　参考答案：A

　　参考解析：顺序存储结构中各数据元素在存储空间中是按逻辑顺序依次连续存放的，在链式存储结构中元素之间的关系通过指针来连接，所以不要求存储空间-定是连续的;顺序存储结构(或链式存储结构)既可以针对线性结构，也可以针对非线性结构，但像栈、队列这样的线性结构-般采用顺序存储结构(但也可以采用链式结构)，树、二叉树这样的非线性结构-般采用链式存储结构(但也可以采用顺序存储结构);链式存储结构既可以存储无序表，也可以存储有序表，注意，链式存储结构存储的即使是有序表，也不能进行二分查找;链式存储结构比顺序存储结构要多使用存储空间，由于链式存储结构中要用额外空间来保存指针。因此本题的正确答案是A。

　　12[单选题]支持子程序调用的数据结构是(　　)。【考点3栈】

　　A.栈B.树C.队列D.二叉树

　　参考答案：A

　　参考解析：栈是一种限定在一端进行插入与删除的线性表。主函数调用子函数时，首先会保存主函数当前的状态，然后转去执行子函数，并把子函数的运行结果返回到主函数调用子函数时的位置，主函数再接着往下执行，这种过程符合栈的特点。所以一般采用栈式存储方式。

　　13[填空题]在长度为n的顺序存储结构的线性表中，插入(或删除)一个元素，在平均情况下需要移动表中的________个元素，在最坏情况下需要移动表中的________个元素。

　　参考解析：

　　n/2 n

　　14[单选题]下列诜项中不属于结构化稗序设计方法的是

　　A.自顶向下B.逐步求精C.模块化D.可复用

　　参考答案：D

　　参考解析：结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、模块化、限制使用GOTO语句。可复用不是结构化程序设计方法的主要原则。因此本题的正确答案是D。

　　15[单选题]长度为10的顺序表的首地址是从l023开始的，顺序表中每个元素的长度为2，在第4个元素前面插入一个元素和删除第7个元素后，顺序表的总长度还是不变。问在执行插入和删除操作前，顺序表中第5个元素在执行插入和删除操作后在顺序表中的存储地址是(　　)。

　　参考答案：D

　　参考解析：

　　16[填空题]重复结构对应两类循环语句，对先判断后执行循环体的称为________型循环结构，对先执行循环体后判断的称为________型循环结构。

　　参考解析：当【7】直到【分析】本题考查两类循环结构，希望考生还能够识记并辨别它们的流程图。

　　17[填空题]数据结构分为线性结构和非线性结构，带链的队列属于(　　)。

　　参考解析：线性

　　18[填空题]对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为(　　)。

　　参考解析：45

　　【分析】假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要比较的次数为n(n一1)/2。因此本题的正确答案是10x(10—1)÷2=45。

　　19[填空题]数据结构分为逻辑结构和存储结构，循环队列属于(　　)结构。

　　参考解析：存储结构

　　20[填空题]在长度为n的顺序存储结构的线性表中，要在第i(1≦i≦n)个元素之前插入一个新元素，则需要移动表中的(　　)个元素，表的长度变为(　　);若删除表中的第i(1≦i≦n)个元素，则需要移动表中的(　　)个元素，表的长度变为(　　)。

　　参考解析：n一i+1 、n+1 、n—i 、n一1

　　21[填空题]在长度为n的顺序存储结构的线性表中，插入(或删除)一个元素，在平均情况下需要移动表中的(　　)个元素，在最坏情况下需要移动表中的(　　)个元素。

　　参考解析：n/2、n

　　22[填空题]已知线性表的每个元素占2个字节，它的第5个元素在内存中的存储地址是1005，那么它的第2个元素在内存中的存储地址是(　　)。

　　参考解析：999

　　23[填空题]数据独立性分为逻辑独立性与物理独立性。当数据的存储结构改变时，其逻辑结构可以不变，因此，基于逻辑结构的应用程序不必修改，称为(　　)。

　　参考解析：物理独立性性

　　【分析】数据独立性一般分为物理独立性性和逻辑独立性。物理独立性一般是指数据的物理结构(包括存储结构、存取方式等)的改变，如存储设备的更换、物理存储的更换、存取方式改变等都不影响数据库的逻辑结构，从而不致引起应用程序的改变。逻辑独立性是指数据库总体逻辑结构的改变，如修改数据模式、增加新的数据类型、改变数据间联系等，不需要相应修改应用程序。

　　相关推荐：

　　2015计算机二级公共基础知识考前冲刺练试题汇总

　　2015计算机二级公共基础知识精选选择题专项练习

　　2015计算机二级《公共基础知识》精选选择题90道