第二章-线性表-答案

1、数据结构与算法上机作业第二章 线性表一、选择题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

2、)4、等概率情况下，在有n个结点的顺序表上做插入结点操作，需平均移动的结点数目为 C 。提示：插入的位置有n+1个，移动总数为：1+2+3+nA. nB. (n-1)/2C. n/2D. (n+1)/25、在一个长度为n的顺序存储的线性表中查找值为x的元素时，平均查找长度(及x同元素的平均比较次数，假定查找每个元素的概率都相等)为 C 。A. nB. n/2C. (n+1)/2D. (n-1)/26、在顺序表中，只要知道 D ，就可以求出任一结点的存储地址。A. 基地址B. 结点大小C. 向量大小D. 基地址和结点大小7、将两个各有n个元素的有序表归并为一个有序表，其最少的比较次数是 A 。A

3、. nB. 2n-1C. 2nD. n-18、线性表采用链表存储时其存储地址要求 D 。A. 必须是连续的B. 部分地址必须是连续的C. 必须是不连续的D. 连续的和不连续的都可以9、下面关于线性表的描述中，错误的是 B 。A. 线性表采用顺序存储，必须占用一片连续的存储单元B. 线性表采用顺序存储，便于进行插入和删除操作C. 线性表采用链式存储，不必占用一片连续的存储单元D. 线性表采用链式存储，便于插入和删除操作10、向具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是 B A. O(1)B. O(n)C. O(n2)D. O(log2n)11、在一个带头结点的单链表HL中，

4、若要向表头插入一个由指针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->

5、next=q->next->next; q->next=q;13、设有编号为1, 2, 3, 4的4辆列车，顺序进入一个栈结构的站台，下列不可能的出栈顺序为 D 。A. 1234B. 1243C. 1324D. 142314、4个元素按A, B, C, D顺序进入S栈，执行两次Pop(S, x)运算后，栈顶元素的值是 B 。A. AB. BC. CD. D15、从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列 A 命令。A. x=top; top=top->next;B. top=top->next; x=top->data;C

6、. 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. 3B. 4C. 56. 618、设已将元素A, B, C依次入栈，元素D正等待进栈。那么下列4个序列中不可能出现的出栈顺序为 A 。A. CADBB. CBDAC. CDBAD. DCBA19、栈和队列的

7、相同之处是 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-&g

8、t;rear=SQ->frontB. (SQ->rear+1)%MAXLEN=SQ->frontC. SQ->rear+2 = SQL->frontD. (SQ->rear+2)%MAXLEN=SQL->front23、若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为 B 。A. 5和1B. 4和2C. 2和4D. 1和524、链栈与顺序栈相比，有一个较为明显的优点是 A 。A. 通常不会出现满栈的情况B. 通常不会出现栈空的情况C. 插入操作更加

9、方便D. 删除操作更加方便25、设用一个大小为M=60的顺序表AM表示一个循环队列，如果当前的尾指针rear=32，头指针front=15，则当前循环队列的元素的个数为 C 。A. 42B. 17C. 18D. 4126、串是一种特殊的线性表，其特殊性体现在 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. 0123B. 0121C.

10、 0112D. 012229、若字符串“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->

11、;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、已知循环队列存储在一维数组A0n-1中，且队列非空时front和rear分别指向对头元素和队尾元素，且要求第一个进入队列的元素存储在A0处，则初始时front和rear的值分别是 B 。A. 0, 0B. 0, n-1C. n-1, 0D. n-1, n-132、某队列允许在两端进

12、行入队操作，但仅允许在一端进行出队操作（称为输出受限的双端队列），若a, b, c, d, e元素依次进队，则不可能得到的顺序是 C 。A. bacdeB. dbaceC. dbcaeD. ecbad33、在双向链表中间插入一个结点时，需要修改 D 个指针域。A. 1B. 2C. 3D. 434、在按行优先顺序存储的三元组表中，下述陈述错误的是 D 。A. 同一行的非零元素，是按列号递增次序存储的B. 同一列的非零元素，是按行号递增次序存储的C. 三元组表中三元组行号是非递减的D. 三元组表中三元组列号是非递减的35、在稀疏矩阵的三元组表示法中，每个三元组表示 D 。A. 矩阵中非零元素的值B

13、. 矩阵中数据元素的行号和列号C. 矩阵中数据元素的行号、列号和值D. 矩阵中非零数据元素的行号、列号和值36、对特殊矩阵采用压缩存储的目的主要是为了 D 。A. 表达变得简单B. 对矩阵元素的存取变得简单C. 去掉矩阵中的多余元素D. 减少不必要的存储空间37、广义表是线性表的推广，它们之间的区别在于 A 。A. 能否使用子表B. 能否使用原子项C. 表的长度D. 是否能为空38、已知广义表(a, b, c, d)的表头是 A ，表尾是 D 。A. aB. ()C. (a, b, c, d)D. (b, c, d)39、下面说法不正确的是 A 。A. 广义表的表头总是一个广义表B. 广义表的

14、表尾总是一个广义表C. 广义表难以用顺序存储结构表示D. 广义表可以是一个多层次的结构40、若广义表A满足Head(A)=Tail(A)，则A为 B 。A. ( )B. ()C. ( ),( )D. ( ), ( ), ( )二、填空题1、线性表中结点的集合是有限的，结点之间的关系是 有序 关系。2、顺序表中访问任一个结点的时间复杂度为 O（1） 。3、线性表中第一个结点没有直接前驱，称为 头 结点。4、在一个长度为n的顺序表中删除第i个元素，要移动 n-i 个元素。5、在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移 n-i+1 个元素，在插入操作中，移动元素的均值为 n/

15、2 。6、根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成 单向链表 和 双向链表 。7、链式存储的特点是利用 next指针 来表示数据元素之间的逻辑关系。8、静态链表(线性表的游标实现)是指用 元素的下标 表示单链表的指针。9、在静态链表中，一般都有一个变量available表示的结点链，其中的结点为 空闲结点 。10、在栈中，可进行插入和删除操作的一端称 栈顶 。11、在进栈运算时，应先判别栈是否 满 。在出栈运算时应先判别栈是否 空 。当栈中元素为n个时，进栈运算时发生上溢，则说明该栈的最大容量为 n 。12、设有一空栈，现有输入序列为1, 2, 3, 4, 5，经过p

16、ush, push, pop, push, pop, push, push, pop, pop之后，输出序列为 23541 。13、对于循环队列Q，求队列长度的公式为 (Q.rear-Q.front+maxlength+1)%maxlength 。14、栈的逻辑特点是 先进后出 。队列的逻辑特点是 先进先出 。两者的共同特点是只允许在它们的 端点 出插入和删除数据元素，区别是 栈从一段进出，队列从一端进，另一端出 。15、链队列LQ为空时，LQ->front->next= NULL .16、在一个链队列LQ中，若队首指针为front，队尾指针为rear，则判断该队列只有一个结点的条

17、件为 LQ->front->next!=NULL && LQ->front=LQ-rear 。17、设串S=“Ilikecomputer”，T=“com”，则Length(S)= 13 。Index(S, T)= 5 。18、在KMP算法中，nextj只与 模式 串有关，而与 主 无关。19、字符串“ababaab“的Next数组值是 0112342 。20、稀疏矩阵一般压缩存储的方式有三种，分别是 三元组 、 十字链表 和 行指针链表 。21、二维数组M中每个元素的长度是3字节，行下标i从07，列下标j从09，从首地址&M00开始连续存放在存储器中。

18、若按行优先的方式存放，元素M75的起始地址为 &M00+7*8+5 ；若按列优先方式存放，元素M75的起始地址为 &M00+5*10+7 。22、广义表(a, (a, b), d, e, (i, j), k)的长度是 5 ，深度是 3 。23、设广义表A( ), (a, (b), c)，则Cal(Cdr(Cal(Cdr(Cal(A)= (b) 三、写一个算法合并两个已排序的线性表。（用两种方法：数组表示的线性表（顺序表）和指针表示的线性表（链表）要求：1、定义线性表节点的结构，并定义节点的型和位置的型。 2、定义线性表的基本操作 3、在1，2的基础上，完成本题。 4、在main

19、函数中进行测试：先构建两个有序的线性表，然后合并这两个线性表。四、已知一个单向链表，试给出复制该链表的算法。要求：1、定义线性表的节点的结构以及节点的型和位置的型。 2、定义线性表的基本操作 3、在1，2的基础上，完成本题。 4、在main函数中进行测试：先构建一个线性表，并定义一个空线性表，然后进行复制。五、写出从一个带表头的单链表中删除其值等于给定值x的结点的算法函数：int Delete(LIST &L, int x);如果x在该链表中，则删除对应结点，并返回其在链表中的位置（逻辑位置，第一个结点的逻辑位置为1），否则返回-1。要求：1、定义线性表的节点的结构以及节点的型和位置的

20、型。2、定义线性表的基本操作3、在1，2的基础上，完成本题。4、在main函数中进行测试：先构建一个线性表，然后调用函数删除值等于给定值的节点。六、写出一个将两个静态链表（属于同一个存储池）合并的算法函数： void Merge(cursor M, cursor N); 合并的方法是将N链表中的所有结点添加到M链表的后面，并将N链表的表头结点添加到空闲结点链表中。要求：1、定义静态链表的结点的结构以及结点的型SPACE以及位置（position）和游标（cursor）的型。2、定义静态链表的基本操作：void Initialize(); 初始化，将所有存储池中的结点设置为空闲；cursor G

21、etNode(); 从空闲链中获取一个结点；void FreeNode(cursor q); 将结点q加入到空闲链； void Insert ( elementtype x, position p, cursor M ); 在链表M中的位置为p的元素后面添加一个值为x的结点；void Delete (cursor M, position p ); 在链表M中删除位置为p的元素的后一个元素。3、在1、2的基础上完成本题。4、在main函数中进行测试：先构建一个存储池，然后在该存储池中创建两个静态表，最后将这两个静态表合并。七、利用指针表示的线性表(链表)表示一个多项式，并实现两个多项式的相加和相

22、乘运算。假设多项式形式为： 其中，系数ai0，指数ei满足em>em-1>>e2>e1>=0。要求：1、定义多项式每一项的结构。2、定义两个多项式的相加和相乘运算函数。3、在main函数中，构建两个多项式，并测试相加和相乘运算。八、试编写一个整数进制转换的通用函数convert(int num, STACK S, int n)，要求将整数m转换为n进制数，n进制数的各位依次存放在栈S中。并在主函数中进行测试。要求：1、定义栈以及栈的型。2、定义栈的各种操作。 3、实现函数convert。 4、在main函数中，通过调用函数convert将num的n进制数存放到一个

23、栈中，并通过出栈的方法输出该n进制数九、设有一个循环队列Queue，只有头指针front，不设尾指针，另设一个含有元素个数的计数器count，试写出相应的判断队列空、判断队列满、出队算法和入队算法。要求：1、定义相应的循环队列的型（只有头指针，没有尾指针，但有一个元素个数的计数器）；2、定义该队列的四个算法：判断队列空、判断队列满、出队算法和入队算法；3、在main函数验证算法的正确性。十、设主串T=“abcaabbabcabaacbacba“，模式为p=“abcabaa”。 1、计算模式p的nextval函数值2、不写算法，只画出利用KMP算法进行模式匹配时，每一趟的匹配过程。要求：1、写出

24、模式p的nextval值；2、画出KMP算法的每一趟匹配过程（可参照教材P61从第8行开始的内容）；3、编程检验p在T中是否存在，如果存在，输出相应的位置，如果不存在，输出-1。十一、假设表达式中允许包含三种括号：圆括号、方括号和大括号。设计一个算法采用顺序栈（用数组表示的栈）判断表达式中的括号是否正确配对。要求： 1、定义栈以及栈的型，栈中所存放元素的类型为字符型，定义枚举类型Boolean，其中两个元素分别为TRUE和FALSE。2、定义栈的各种操作。3、定义函数Boolean check(char *s); 判断s中的括号是否正确配对，如果正确配对，返回TRUE，否则返回FALSE。4、在主函数中验证所编写函数的正确性。十二、设有一个带头结点的双向链表h，设计一个算法用于查找第一个