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