一、 填空题(每空 2 分,共 20 分)
1、数据的逻辑结构主要分为 、 和 三种结构。(答案:集合结构、线性结构、
树状结构)
2、数据的存储结构主要分为 和 两种结构(顺序存储结构和链式存储结构)
3、栈的主要特点是 后进先出 ;队列的主要特点是 先进先出 。
4、使用顺序存储结构线性表对 n个元素进行排序时,快速排序法时间复杂度
最坏的情况是 O(n*n) ,平均情况是 O ( nlog2n ) 。
5、如果单向链表中有 m 个节点,则进行遍历时时间复杂度至少为 O(m^2) 。
二、 选择题(每题 2 分,共 30 分)
1、对于使用顺序表的栈结构来说,设其栈顶指针为 Top,栈空间大小为 n,则
栈满条件为(d)。
A Top== -1 B Top== n-1 C Top==0 D Top==n
2、使用数组存储 n 个数据,如下图所示:
若该数组空间足够大,则在 a
i
处插入一个与 a
i
同类型的数据 x,需要
移动的数据个数是(c)。
A i B n-i C n-i+1 D n-i-1
3、一个顺序表中存储了由小到大顺序排列的 81 个数据,并使用分块查找法
为了使平均查找长度(ASL)最小,则分块的数量为()块最为合理。
A 27 3 快 B 9 9 块 C 3 27 块 D 6 14 块 代入求最小
1/2(n/s+s)+1 n 为元素个数 s 为块数
4、使用数组存储 n 个数据,如下图所示:
若删除 a
i
数据,则需要移动的数据个数是(b)。
A i B n-i C n-i+1 D n-i-1
5、时间复杂度由小到大正确的排列顺序是(d)。
A O(n
1/2
)、O(nlog
2
n)、O(n)、O(n
2
)、O(2
n
)、O(n
n
)
B O(n)、O(n
1/2
)、O(2
n
)、O(n
2
)、O(n
n
)、O(nlog
2
n)
C O(nlog
2
n)、O(n)、O(n
1/2
)、O(n
2
)、O(2
n
)、O(n
n
)
D O(n
1/2
)、O(n)、O(nlog
2
n)、O(n
2
)、O(2
n
)、O(n
n
)
6、某一数组中存储了 4 个数据, 如下图所示:
并且该数组进行排序的每一趟序列如下:
第一趟:2、4、5、2
第二趟:2、2、5、4
第三趟:2、2、4、5
请问,上述排序方法使用的是(a)。
A 冒泡排序 B 选择排序 C 插入排序 D 快速排序
7、数组 Q[n]用来表示一个循环队列,f 指向该队列的队头,r 指向该队列的队尾。