要求:所有的题目的解答均写在答题纸上,需写清楚题目的序号。每张答题纸都要写
上姓名和学号。
一、单项选择题(每小题
2
分,共
20
小题,共计
40
分)
1、设n是描述问题规模的非负整数,下面程序片段的时间复杂度为( )。
x=1;
while (x<=n)
x=5*x;
A. O(log
5
n) B.O(n) C.O(nlog
5
n) D.O(n
5
)
2、顺序表和链表相比存储密度较大,这是因为( )。
A.顺序表的存储空间是预先分配的
B.顺序表不需要增加指针来表示元素之间的逻辑关系
C.链表中所有节点的地址是连续的
D.顺序表中所有元素的存储地址是不连续的
3、在长度为 n(n≥1)的循环双链表 L 中,在尾节点之后插入一个新节点的时间复杂
度为( )。
A. O(n
2
) B.O(n) C. O(1) D.O(nlog
2
n)
4、设栈的输入序列是 1、2、3、4,则( )不可能是其出栈序列。
A.1,2,4,3 B.2,1,3,4 C.1,4,3,2 D.4,3,1,2
5、当用一个数组 data[0..n-1]存放栈中元素时,栈底最好( )。
A. 设置在 data[0]或 data[n-1]处 B.设置在 data[n-1]处
C. 设置在 data[0]处 D.设置在 data 数组的任何位置
6、在数据处理过程中常需要保存一些中间数据,如果先保存的数据先处理,则使用
( )来保存这些数据。
A.线性表 B. 队列 C. 栈 D.单链表
7、在环形队列中,元素的排列顺序( )。
A.与队头和队尾指针的取值有关 B.与元素值的大小有关
C.由元素进队的先后顺序确定 D.与存放队中元素的数组大小有关
8、将 10 阶对称矩阵压缩存储到一维数组 A 中,则数组 A 的长度最少为( )。
A.100 B.40 C.80 D.55
9、设目标串为 s,模式串为是 t,在 KMP 模式匹配中,next[4]=2 的含义是( )。
A.表示t
4
字符前面最多有2个字符和开头的2个字符相同
B.表示s
4
字符前面最多有2个字符和开头的2个字符相同
C.表示目标串匹配失败的位置是i=4
D.表示模式串匹配失败的位置是j=2
10、由权值分别为 9、2、7、5 的四个叶子节点构造一棵哈夫曼树,该树的带权路径长