数据结构课堂测试

1.‍已知循环队列的存储空间为A[1...21]，front指向对头元素的前一个位置，rear指向
队尾元素，假设当前front和rear的值分别为8和3，则该队列的长度为（）
‍A.17			B.5			C.16		D.6
正确答案：C
2最适合做链队列存储的链表是（）
A.只有头指针的循环单链表
B.只有头指针的单链表
C.带队头指针和队尾指针的单链表
D.带队头指针和队尾指针的循环单链表
正确答案：C
3（2018统考真题）现有队列Q和栈S，初始时Q中的元素依次是1、2、3、4、5、6（1在队头），
S为空，若仅允许下列三种操作：（1）出队并输出出队元素；
（2）出队并将出队元素进栈；（3）出栈并输出出栈元素。
则不能得到的输出序列是（）
A.3、4、5、6、1、2		B.2、3、4、5、6、1
C.6、5、4、3、2、1		D.1、2、5、6、4、3
正确答案：A
4.设二维数组A[1..m，1..n]（即m行n列）按行存储在数组B[1..m*n]中，
则二维数组元素A[i,j]在一维数组B中的下标为（）。
A.(i-1)*n+j			B.(i-1)*n+j-1
C.j*m+i-1			D.i*(j-1)
正确答案：A
5.广义表A=(a,b,(c,d),(e,(f,g)))，
则Head(Tail(Head(Tail(Tail(A)))))的值为（）。
A.(g)		B.d		C.c		D.(d)
正确答案：B
6.设广义表L=((a,b,c))，则L的长度和深度分别为（）。
A.1和2		B.1和3		C.2和3		D.1和1
正确答案：A
7.顺序表中第一个元素的存储地址是100，每个元素的长度为2，
则第5个元素的地址是（）。
A.110		B.104		C.105		D.108
正确答案：D
8.在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。
A.访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B.删除第i个结点（1≤i≤n）
C.将n个结点从小到大排序。
D.在第i个结点后插入一个新结点（1≤i≤n）
正确答案：A
9.向一个有150个元素的顺序表中插入一个新元素并保持原来顺序不变，
平均要移动元素的次数为（）。
A.75		B.150		C.0		D.149
正确答案：A
10.单链表的存储密度（）。
A.小于1		B.等于1		C.不能确定		D.大于1
正确答案：A
11.创建一个包括n个结点的有序单链表的时间复杂度是（）。
A.O(nlog2n)		B.O(1)		C.O(n)		D.O(n^2)
正确答案：D
12.栈在（  ）中有所应用。
A.表达式求值				B.函数调用
C.前三个选项都有			D.递归调用
正确答案：C
13.在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，
以top作为栈顶指针，则当作进栈处理时，top的变化为（）
A.top--		B.top=0		C.top不变		D.top++
正确答案：A
14有一个n*n的对称矩阵A，将其下三角部分按行优先存放在
一维数组顺序表B中，A[0][0]存放在B[0]中，则第i行
对角线元素存放在B中的下标位置是（）
‍A.(2*n-i+1)*i/2
B.(i+1)*i/2
C.(2*n-i-1)*i/2
D.(i+3)*i/2
正确答案：D
15.(2016年统考真题)有一个100阶的三对角矩阵M，其元素m(i,j)(1<=i，j<=100)，
按行优先依次压缩存储到下标从0开始的顺序表（一维物理数组）N中，
元素m(30,30)在N中的存储下标是（）
‍A.88		B.87		C.89		D.86
正确答案：B
16.2017年统考真题）适用于压缩存储稀疏矩阵的两种存储结构为（）
A.三元组表和邻接矩阵			B.十字链表和二叉链表
C.三元组表和十字链表			D.邻接矩阵和十字链表
正确答案：C
17.2018年统考真题）设有一个12*12的对称矩阵M，将其上三角部分元素m(i,j)(1<=i,j<=12)
按行优先存入C语言的一维数组N中，元素m(6,6)在N中的存储下标是（）
A.66		B.51		C.50		D.55
正确答案：C
18.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于
一维数组B[1..(n(n+1))/2]中，则在B中确定aij（i<j且1<=i,j<=n）的位置k的关系为（）。
‍A.i*(i+1)/2+j			B.j*(j+1)/2+i
C.i*(i-1)/2+j			D.j*(j-1)/2+i
正确答案：D
19.循环队列存储在数组A[0..m]中，则入队时的操作是：
A.rear=(rear+1)%m				B.rear=(rear+1)%(m-1)
C.rear=(rear+1)%(m+1)			D.rear=rear+1
正确答案：C
20.在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（）。
A.s->next=p->next;p->next=s->next;
B.s->next=p+1;p->next=s;
C.s->next=p->next;p->next=s;
D.(*p).next=s;(*s).next=(*p).next;
正确答案：C
21.使用KMP算法进行模式匹配，模式串'aabaabaabaac'的next数组为（ ）。
‍A.012123456789
B.012323456743
C.012123451234
D.012213434756
正确答案：A