数据结构与算法上机作业
第二章 线性表

一、选择题
1、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新的元素算法的时间复杂度为    C        。
    A. O(log2n)        B. O(1)        C. O(n)        D. O(n2)
2、以下关于线性表的说法中，不正确的是    C    。
    A. 线性表中的数据元素可以是数字、字符、结构等不同类型
    B. 线性表中包含的数据元素个数不是任意的
    C. 线性表中的每一个结点都有且只有一个直接前驱和直接后继
    D. 存在这样的线性表：表中各结点都没有直接前驱和直接后继
3、在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为    B    。
    A. O(1)        B. O(n)        C. O(n2)        D. O(log2n)
4、等概率情况下，在有n个结点的顺序表上做插入结点操作，需平均移动的结点数目为 
  C    。提示：插入的位置有n+1个，移动总数为：1+2+3+……+n
    A. n        B. (n-1)/2        C. n/2        D. (n+1)/2
5、在一个长度为n的顺序存储的线性表中查值为x的元素时，平均查长度(及x同元素的平均比较次数，假定查每个元素的概率都相等)为    C    。
    A. n        B. n/2        C. (n+1)/2    D. (n-1)/2
6、在顺序表中，只要知道    D    ，就可以求出任一结点的存储地址。
    A. 基地址        B. 结点大小        C. 向量大小        D. 基地址和结点大小
7、将两个各有n个元素的有序表归并为一个有序表，其最少的比较次数是    A  。
    A. n        B. 2n-1        C. 2n        D. n-1
8、线性表采用链表存储时其存储地址要求    D      。
    A. 必须是连续的            B. 部分地址必须是连续的
    C. 必须是不连续的            D. 连续的和不连续的都可以
9、下面关于线性表的描述中，错误的是    B    。
A. 线性表采用顺序存储，必须占用一片连续的存储单元
B. 线性表采用顺序存储，便于进行插入和删除操作
C. 线性表采用链式存储，不必占用一片连续的存储单元
merge函数D. 线性表采用链式存储，便于插入和删除操作
10、向具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是  B   
    A. O(1)        B. O(n)        C. O(n2)        D. O(log2n)
11、在一个带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行的语句是  D    。
    A. HL=p; p->next=HL;            B. p->next=HL; HL=p;
    C. p->next=HL; p=HL;            D. p->next=HL->next; HL->next=p;
12、在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行的语句是 C 。
    A. p=q->next; p->next=q->next;
    B. p=q->next; q->next=p;
    C. p=q->next; q->next=p->next;
    D. q->next=q->next->next; q->next=q;
13、设有编号为1, 2, 3, 4的4辆列车，顺序进入一个栈结构的站台，下列不可能的出栈顺序
为    D    。
    A. 1234        B. 1243        C. 1324        D. 1423
14、4个元素按A, B, C, D顺序进入S栈，执行两次Pop(S, x)运算后，栈顶元素的值是 B  。
    A. A        B. B        C. C        D. D
15、从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列
  A      命令。
    A. x=top; top=top->next;        B. top=top->next; x=top->data;
    C. x=top->data;                D. x=top->data; top=top->next;
16、向顺序栈中输入元素时  B    。
    A. 先存入元素，后移动栈顶指针        B. 先移动栈顶指针，后存入元素
    C. 谁先谁后无关紧要                    D. 同时进行
17、设有一个顺序栈，元素A, B, C, D, E, F依次进栈，如果6个元素出栈的顺序是B, D, C, F, E, A，则栈的容量至少为    A    。
    A. 3        B. 4        C. 5        6. 6
18、设已将元素A, B, C依次入栈，元素D正等待进栈。那么下列4个序列中不可能出现的出栈顺序为  A    。
    A. CADB        B. CBDA        C. CDBA        D. DCBA
19、栈和队列的相同之处是    C    。
    A.元素的进出满足先进后出             B.元素的进出满足后进先出
C.只允许在端点进行插入和删除操作     D.无共同点
20、设栈S 和队列Q 的初始状态为空,元素e1，e2，e3，e4，e5 和e6 依次通过栈，一个元素出栈后即进入队列Q,若6 个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S 的容量至少应该是    C    。
A. 6     B. 4     C. 3     D. 2
21、队列通常采用的两种存储结构是     A    。
A. 顺序存储结构和链式存储结构     B.散列方式和索引方式
C. 链表存储结构和线性存储结构     D.线性存储结构和非线性存储结构
22、循环队列SQ队满的条件是      D      。
    A. SQ->rear==SQ->front            B. (SQ->rear+1)%MAXLEN==SQ->front
    C. SQ->rear+2 == SQL->front        D. (SQ->rear+2)%MAXLEN==SQL->front
23、若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为    B    。
    A. 5和1        B. 4和2        C. 2和4        D. 1和5
24、链栈与顺序栈相比，有一个较为明显的优点是  A    。
    A. 通常不会出现满栈的情况        B. 通常不会出现栈空的情况
    C. 插入操作更加方便                D. 删除操作更加方便
25、设用一个大小为M=60的顺序表A[M]表示一个循环队列，如果当前的尾指针rear=32，头指针front=15，则当前循环队列的元素的个数为  C    。
    A. 42        B. 17        C. 18        D. 41
26、串是一种特殊的线性表，其特殊性体现在    B      。
    A. 可以顺序存储            B. 数据元素是一个字符
    C. 可以链式存储            D. 数据元素可以是多个字符
27、设主串的长度为n，模式串的长度为m，则串匹配的KMP算法的时间复杂度为  C  。
    A. O(m)        B. O(n)        C. O(m+n)        D. O(m×n)
28、已知串S=“abab”，其Next数组值为    C    。
    A. 0123        B. 0121        C. 0112        D. 0122
29、若字符串“ABCDEFG”采用不带表头的链式存储，每个结点保存一个字符。假设每个字符占用1个字节，每个指针占用两个字节，则该字符串的存储密度为  D    。
    A. 20%        B. 40%        C. 50%        D. 33.3%
30、在双向链表中，在指针p所指的结点前插入一个指针q所指向的结点，操作是  C  。
    A. p->Prior=q; q->Next=p; p->Prior->next=q; q->Prior=q;
    B. p->Prior=q; p->Prior->next=q; q->next=p; q->Prior=p->Prior;
    C. q->Next=p; q->Prior=p->Prior; p->Prior->Next=q; p->Prior=q;
    D. q->Prior=p->Prior; q->Next=q;    p->Prior=q; p->Next=q;
31、已知循环队列存储在一维数组A[0…n-1]中，且队列非空时front和rear分别指向对头元素和队尾元素，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是  B    。
    A. 0, 0        B. 0, n-1        C. n-1, 0        D. n-1, n-1
32、某队列允许在两端进行入队操作，但仅允许在一端进行出队操作（称为输出受限的双端队列），若a, b, c, d, e元素依次进队，则不可能得到的顺序是    C    。
    A. bacde        B. dbace        C. dbcae        D. ecbad
33、在双向链表中间插入一个结点时，需要修改  D  个指针域。
    A. 1        B. 2        C. 3        D. 4
34、在按行优先顺序存储的三元组表中，下述陈述错误的是    D    。
    A. 同一行的非零元素，是按列号递增次序存储的
    B. 同一列的非零元素，是按行号递增次序存储的
    C. 三元组表中三元组行号是非递减的
    D. 三元组表中三元组列号是非递减的
35、在稀疏矩阵的三元组表示法中，每个三元组表示    D      。
    A. 矩阵中非零元素的值
    B. 矩阵中数据元素的行号和列号
    C. 矩阵中数据元素的行号、列号和值
    D. 矩阵中非零数据元素的行号、列号和值
36、对特殊矩阵采用压缩存储的目的主要是为了    D    。
    A. 表达变得简单            B. 对矩阵元素的存取变得简单
    C. 去掉矩阵中的多余元素        D. 减少不必要的存储空间
37、广义表是线性表的推广，它们之间的区别在于    A      。
    A. 能否使用子表            B. 能否使用原子项
    C. 表的长度                D. 是否能为空
38、已知广义表(a, b, c, d)的表头是    A      ，表尾是  D      。
    A. a        B. ()        C. (a, b, c, d)        D. (b, c, d)
39、下面说法不正确的是    A        。
    A. 广义表的表头总是一个广义表        B. 广义表的表尾总是一个广义表
    C. 广义表难以用顺序存储结构表示        D. 广义表可以是一个多层次的结构
40、若广义表A满足Head(A)=Tail(A)，则A为    B      。