软考-线性结构（上）

1.线性表

设有一个包含n个元素的有序线性表。在等概率情况下删除其中的一个元素，若采用顺序存储结构，则平均需要移动_____个元素；若采用单链表存储，则平均需要移动______个元素。
1.1：A 1 B (n-1)/2 C logn D n/2
1.2：A 0 B 1 C (n-1)/2 D n/2

2.栈与队列

2.1：队列的特点是先进先出，若用循环单链表表示队列，则（ ）
A 入队列和出队列操作都不需要遍历链表
B 入队列和出队列操作都需要遍历链表
C 入队列操作需要遍历链表而出队列操作不需要
D 入队列操作不需要遍历链表而出队列操作需要

2.2：栈的特点是后进先出，若用单链表作为栈的存储结构，并用头指针作为栈顶指针，则______。
A 入栈和出栈操作都不需要遍历链表
B 入栈和出栈操作都需要遍历链表
C 入栈操作需要遍历链表而出栈操作不需要
D 入栈操作不需要遍历链表而出栈操作需要

2.3：已知栈S初始为空，用I表示入栈、O表示出栈，若入栈序列为a1a2a3a4a5，则通过栈S得到出栈的序列a2a4a5a3a1的合法操作序列为______。
A. IIOIIOIOOO
B. IOIOIOIOIO
C. IOOIIOIOIO
D. IIOOIOIOOO

2.4：若元素以a、b、c、d、e的顺序进入一个初始为空的栈中，每个元素进栈、出栈各1次，要求出栈的第一个元素为d，则合法的出栈序列共有______种。
A 4 B 5 C 6 D 24

2.5：输出受限的双端队列是指只有一端可以进行出队操作而从两端都可以进行入职操作的队列，如下图所示。对于输入序列 a b c d，经过一个初始为空且输出受限的双端队列后，不能得到的输出序列为_____。

image.png

A d a b c
B d c b a
C d c a b
D d a c b

3.字符串

3.1：设S中一介长度为n的非空字符串，其中的字符各不相同，则其互异的非平凡子串（非空且不同于S本身）个数为（ ）
A 2n-1
B n^2
C n(n+1)/2
D (n+2)(n-1)/2

3.2：以下关于字符串的叙述中，正确的是（ ）
A 包含任意个空格字符的字符串称为空串
B 字符串不是线性数据结构
C 字符串的长度是指串中所含字符的个数
D 字符串的长度是指串中所含非空格字符的个数