事业单位考试计算机二级线性链表与排序技术真题答案解析
根据最新的事业单位考试计算机二级真题汇总而成，事业单位考试网（http:www.shizheng100.com）提供更多笔试真题、面试原创题等内容。
1、下列叙述中正确的是
A. 线性表链式存储结构的存储空间一般要少于顺序存储结构
B. 线性表链式存储结构与顺序存储结构的存储空间都是连续的
C. 线性表链式存储结构的存储空间可以是连续的，也可以是不连续的
D. 以上说法均错误
答案：C
解析：线性表的顺序存储结构具备如下两个基本特征：（1）线性表中的所有元素所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。用一组任意的存储单元来依次存放线性表的结点，这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此C正确。
2、下列叙述中正确的是( )。
A. 顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的
B. 顺序存储结构只针对线性结构，链式存储结构只针对非线性结构
C. 顺序存储结构能存储有序表，链式存储结构不能存储有序表
D. 链式存储结构比顺序存储结构节省存储空间
答案：A
解析：链式存储结构既可以针对线性结构也可以针对非线性结构，所以B.与C.错误。链式存储结构中每个结点都由数据域与指针域两部分组成，增加了存储空间，所以D)错误。
3、下列叙述中正确的是( )。
A. 线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的
B. 线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构
C. 线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构
D. 线性表的链式存储结构与顺序存储结构在存储空间的需求上没有可比性
答案：B
解析：线性链式存储结构中每个结点都由数据域与指针域两部分组成，增加了存储空间，所以一般要多于顺序存储结构。
4、下列叙述中正确的是( )。
A. 栈是"先进先出"的线性表
B. 队列是"先进后出"的线性表
C. 循环队列是非线性结构
D. 有序线性表既可以采用顺序存储结构，也可以采用链式存储结构
答案：D
解析：栈是先进后出的线性表，所以A.错误；队列是先进先出的线性表，所以B.错误；循环队列是线性结构的线性表，所以C.错误。
5、下列关于线性链表的叙述中，正确的是( )。
A. 各数据节点的存储空间可以不连续，但他们的存储顺序与逻辑顺序必须一致
B. 各数据节点的存储顺序与逻辑顺序可以不一致，但它们的存储空间不需连续
C. 进行插入数据与删除数据时，不需要异动表中的元素
D. 以上说法均不对
答案：C
解析：一般来说，在线性表的链式存储结构中，个数据节点的存储序号时不连续的，并且各节点在存储空间中的位置关系与逻辑关系也不一致。线性链表中数据的插入和删除都不需要移动表中的元素，只需要改变节点的指针域即可。
6、对长度为n的线性表排序，在最坏情况下，比较次数不是n(n－1)/2的排序方法是( )。
A. 快速排序
B. 冒泡排序
C. 直接插入排序
D. 堆排序
答案：D
解析：除了堆排序算法的比较次数是 ，其他的都是n(n－1)/2。
7、下列排序方法中，最坏情况下比较次数最少的是( )。
A. 冒泡排序
B. 简单选择排序
C. 直接插入排序
D. 堆排序
答案：D
解析：冒泡排序与简单插入排序与简单选择排序法在最坏情况下均需要比较n(n－1)/2次，而堆排序在最坏情况下需要比较的次数是 。
8、对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为（）
A. 9
B. 10
C. 45
D. 90
答案：C
解析：冒泡法是在扫描过程中逐次比较相邻两个元素的大小，最坏的情况是每次比较都要将相邻的两个元素互换，需要互换的次数为9+8+7+6+5+4+3+2+1=45，选C。
9、对长度为n的线性表作快速排序，在最坏情况下，比较次数为
A. n
B. n-1
C. n(n-1)
D. n(n-1)/2
答案：D
解析：快速排序最坏情况就是每次选的基准数都和其他数做过比较，共需比较(n-1)+(n-2)+…+1=n(n-1)/2，选D。
