线性表答案

《线性表答案》由会员分享，可在线阅读，更多相关《线性表答案（11页珍藏版）》请在金锄头文库上搜索。

1、第二章线性表答案（总页）-本页仅作为文档封面，使用时请直接删除即可-内页可以根据需求调整合适字体及大小-数据结构与算法上机作业第二章线性表一、选择题1、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新的元素 算法的时间复杂度为C 。A. O(log2 n)B. 0(1)C. 0( n)D. 0(n2)2、以下关于线性表的说法中，不正确的是C 。A. 线性表中的数据元素可以是数字、字符、结构等不同类型B. 线性表中包含的数据元素个数不是任意的C. 线性表中的每一个结点都有且只有一个直接前驱和直接后继D. 存在这样的线性表：表中各结点都没有直接前驱和直接后继3、 在有n个结点的顺序表上

2、做插入、删除结点运算的时间复杂度为。A. 0(1)B. 0( n)C. 0( n2)D. O(log2n)4、等概率情况下，在有 n 个结点的顺序表上做插入结点操作，需平均移动的结 点数目为C。提示：插入的位置有n+1个，移动总数为：1+2+3+.+nA. nB. (n-1)/2C. n/2D. (n+1)/25、在一个长度为n的顺序存储的线性表中查找值为x的元素时，平均查找长度 (及x同元素的平均比较次数，假定查找每个元素的概率都相等)为匚。A. nB. n/2C. (n+1)/2 D. (n-1)/26、 在顺序表中，只要知道D ，就可以求出任一结点的存储地址。A. 基地址B.结点大小C.

3、向量大小D.基地址和结点大小7、将两个各有 n 个元素的有序表归并为一个有序表，其最少的比较次数是A。A. nB. 2n-1C. 2nD. n-18、 线性表采用链表存储时其存储地址要求_。A.必须是连续的B.部分地址必须是连续的C. 必须是不连续的D. 连续的和不连续的都可以9、 下面关于线性表的描述中，错误的是B 。A. 线性表采用顺序存储，必须占用一片连续的存储单元B. 线性表采用顺序存储，便于进行插入和删除操作C. 线性表采用链式存储，不必占用一片连续的存储单元D. 线性表采用链式存储，便于插入和删除操作10、向具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度 是_BA.

4、 0(1)B. 0( n)C. 0( n2)D. 0(log2 n)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

5、-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)运算后，栈顶元素 的值是旦。A. AB. BC. CD. D15、从一个栈顶指针为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=

6、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、栈和队列的相同之处是C 。A.元素的进出满足先进后出B.元素的进出满足后进先出C.只允许在端点进行插入

7、和删除操作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. 221、队列通常采用的两种存储结构是A。A.顺序存储结构和链式存储结构B.散列方式和索引方式C.链表存储结构和线性存储结构D.线性存储结构和非线性存储结构22、 循环队列SQ队满的条件是D 。A. SQ-rear=SQ-fro ntB. (SQ-rear+1)%MAXLEN=SQ-frontC. SQ-rear+2 = SQL-f

8、rontD. (SQ-rear+2)%MAXLEN=SQL-front23、若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别 为3和0,当从队列中删除一个元素，再加入两个元素后，fro nt和rear的值分 别为B 。A. 5 和 1B. 4 和 2C. 2 和 4D. 1 和 524、 链栈与顺序栈相比，有一个较为明显的优点是。A.通常不会出现满栈的情况B.通常不会出现栈空的情况C. 插入操作更加方便 D. 删除操作更加方便25、设用一个大小为M=60的顺序表AM表示一个循环队列，如果当前的尾指 针rear=32，头指针front=15，贝V当前循环队列的元素的个数为

9、。A. 42B. 17C. 18D. 4126、 串是一种特殊的线性表，其特殊性体现在。A.可以顺序存储B.数据元素是一个字符C.可以链式存储D.数据元素可以是多个字符27、设主串的长度为n,模式串的长度为m,则串匹配的KMP算法的时间复杂 度为丄。A. 0(m)B. 0(n)C. 0(m+n)D. O(m X n)28、已知串S= “abab”，其Next数组值为C 。A.0123B.0121C. 0112D.012229、若字符串“ ABCDEFG ”采用不带表头的链式存储，每个结点保存一个字 符。假设每个字符占用 1 个字节，每个指针占用两个字节，贝该字符串的存储 密度为D 。A. 20

10、%B. 40%C. 50%D. %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、已知循环队列存储在一维数组A0.n-1 中，且队列非空时

11、front和rear分 别指向对头元素和队尾元素，且要求第一个进入队列的元素存储在A0处，则 初始时front和rear的值分别是B 。A. 0, 0B. 0, n-1C. n-1, 0D. n-1, n-132、某队列允许在两端进行入队操作，但仅允许在一端进行出队操作(称为输 出受限的双端队列)，若a, b, c, d, e元素依次进队，则不可能得到的顺序是C_。A. bacdeB. dbaceC. dbcaeD. ecbad33、在双向链表中间插入一个结点时，需要修改D个指针域。A. 1B. 2C. 3D. 434、 在按行优先顺序存储的三兀组表中，下述陈述错误的是。A. 同一行的非零元素

12、，是按列号递增次序存储的B. 同一列的非零元素，是按行号递增次序存储的C. 三元组表中三元组行号是非递减的D. 三元组表中三元组列号是非递减的35、 在稀疏矩阵的三元组表示法中，每个三元组表示。A. 矩阵中非零元素的值B. 矩阵中数据元素的行号和列号C. 矩阵中数据元素的行号、列号和值D. 矩阵中非零数据元素的行号、列号和值36、对特殊矩阵采用压缩存储的目的主要是为了 D 。A.表达变得简单B.对矩阵元素的存取变得简单C. 去掉矩阵中的多余元素 D. 减少不必要的存储空间37、 广义表是线性表的推广，它们之间的区别在于_。A.能否使用子表B.能否使用原子项C.表的长度D.是否能为空38、 已知

13、广义表(a, b, c, d)的表头是 A，表尾是。A. aB. ()C. (a, b, c, d)D. (b, c, d)39、 下面说法不正确的是A 。A.广义表的表头总是一个广义表B.广义表的表尾总是一个广义表C. 广义表难以用顺序存储结构表示D. 广义表可以是一个多层次的结构40、 若广义表A满足Head(A)=Tail(A),则A为_。A. ( )B. ()C. ( ),( )D.(),(),()二、填空题1、线性表中结点的集合是有限的，结点之间的关系是有序关系。2、 顺序表中访问任一个结点的时间复杂度为 0(1)。3、 线性表中第一个结点没有直接前驱，称为结点。4、 在一个长度为n

14、的顺序表中删除第i个元素，要移动n-i个元素。5、 在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移 n-i+1个元素，在插入操作中，移动元素的均值为n/2。6、根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成 单向链表和双向链表。7、链式存储的特点是利用next指针 来表示数据元素之间的逻辑关系。8、静态链表(线性表的游标实现)是指用元素的下标表示单链表的指针。9、在静态链表中，一般都有一个变量available表示的结点链，其中的结点为 空闲结点。10、在栈中，可进行插入和删除操作的一端称栈顶 。11、在进栈运算时，应先判别栈是否。在出栈运算时应先判别栈是否 空。当栈中元素为n个时，进栈运算时发生上溢，则说明该栈的最大容量为n。12、设有一空栈，现有输入序列为1, 2, 3, 4, 5，经过push, push, pop, push, pop,push, push, pop, pop 之后，输出序列为 23541。13、对于循环队列Q,求队列长度的公式为_。14、 栈的逻辑特点是先进后出。队列的逻辑特点是先进先出。两者的共 同特