第2章线性表习题

1、第2章 线性表一 选择题1下述哪一条是顺序存储结构的优点？（ A ）A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示2下面关于线性表的叙述中，错误的是哪一个？（ B ）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。3线性表是具有n个（ C ）的有限序列（n0）。 A表元素 B字符 C数据元素 D数据项 E信息项4若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。

2、A顺序表 B双链表 C带头结点的双循环链表 D单循环链表5某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表6设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表7若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。A单链表 B双链表 C单循环链表 D带头结点的双循环链表23在双向链表指针p的结点前

3、插入一个指针q的结点操作是（ C ）。A. p-Llink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q；B. p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;C. q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q;D. q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;24在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ B ）。Ap-next=s;s-next=p-next; B s-next=p

4、-next;p-next=s;Cp-next=s;p-next=s-next; D p-next=s-next;p-next=s;25对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ B ）Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL26. 在双向链表存储结构中，删除p所指的结点时须修改指针（ A ）。A (p.llink).rlink:=p.rlink (p.rlink).llink:=p.llink;B p.llink:=(p.llink).llink (p.llink).rlink:=p;C (p.rlink

5、).llink:=p p.rlink:=(p.rlink).rlinkD p.rlink:=(p.llink).llink p.llink:=(p.rlink).rlink;二、判断1. 链表中的头结点仅起到标识的作用。( F )2. 顺序存储结构的主要缺点是不利于插入或删除操作。( T )3线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( T )4顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( F )5. 对任何数据结构链式存储结构一定优于顺序存储结构。( F )6顺序存储方式只能用于存储线性结构。( F )三、填空1当线性表的元素总数基本稳定，且很少进行插入

6、和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_顺序_存储结构。2线性表L=（a1,a2,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_(n-1)/2_。3设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:_py-next=px-next_； _px-next=py_;4在一个长度为n的顺序表中第i个元素（1=i=n）之前插入一个元素时，需向后移动_n-i+1_个元素。11.顺序存储结构是通过_物理上

7、相邻_表示元素之间的关系的;链式存储结构是通过_指针_表示元素之间的关系的。第3章 栈和队列一 选择题1. 对于栈操作数据的原则是（ B ）。A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序2. 在作进栈运算时,应先判别栈是否( B ),在作退栈运算时应先判别栈是否( A )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( B )。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( D )分别设在这片内存空间的两端,这样,当( C )时，才产生上溢。 , : A. 空 B. 满 C. 上溢 D. 下溢 : A. n-1

8、B. n C. n+1 D. n/2 : A. 长度 B. 深度 C. 栈顶 D. 栈底 : A. 两个栈的栈顶同时到达栈空间的中心点.B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.3. 一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（ B ）。A. 不确定 B. n-i+1 C. i D. n-i4. 若一个栈的输入序列为1,2,3,n，输出序列的第一个元素是i，则第j个输出元素是（ D ）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的

9、5. 若已知一个栈的入栈序列是1,2,3,n，其输出序列为p1,p2,p3，pN,若pN是n，则pi是( D )。 A. i B. n-i C. n-i+1 D. 不确定6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ C ）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 7. 设栈的输入序列是1，2，3，4,则（ D ）不可能是其出栈序列。A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4，8. 一个栈的输入序列为1

10、2 3 4 5，则下列序列中不可能是栈的输出序列的是（ B ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 222. 用链接方式存储的队列，在进行删除运算时（ D ）。A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改23. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( D )。A仅修改队头指针 B. 仅修改队尾指针 C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改24. 递归过程或函数调用时，处理参数及返回地址，要用一种称

11、为（ C ）的数据结构。A队列 B多维数组 C栈 D. 线性表25. 假设以数组Am存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ A ）。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m26. 循环队列A0.m-1存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( A )。A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front27. 循环队列存储在数组A0.m中，则入队

12、时的操作为（ D ）。A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 28. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( B ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 29. 已知输入序列为abcd 经过输出受限的双向队列后能得到的输出序列有（ BD ）。 A. dacb B. cadb C. dbca D. bdac E.

13、以上答案都不对 30. 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是( C )。A. 1234 B. 4132 C. 4231 D. 4213 32. 栈和队列的共同点是（ C ）。A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点33. 栈的特点是（ B ）,队列的特点是（ A ）,栈和队列都是（ C ）。若进栈序列为1,2,3,4 则（ C ）不可能是一个出栈序列（不一定全部进栈后再出栈）；若进队列的序列为1,2,3,4 则（ F ）是一个出队列序列。, : A. 先进先出 B.

14、后进先出 C. 进优于出 D. 出优于进: A.顺序存储的线性结构 B.链式存储的线性结构 C.限制存取点的线性结构 D.限制存取点的非线性结构, : A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 4,3,2,1 F. 1,2,3,4 G. 1,3,2,4三 填空题 1 栈是_操作受限_的线性表，其运算遵循_后进先出_的原则。2 _栈_是限定仅在表尾进行插入或删除操作的线性表。3 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_312_。4. 设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUS

15、H,POP,PUSH,PUSH之后，输出序列是_23_，而栈顶指针值是_100C_H。设栈为顺序栈，每个元素占4个字节。15. 队列的特点是_先进先出_。16队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是先进先出。第四章 串一、选择题1下面关于串的的叙述中，哪一个是不正确的？（ B ）A串是字符的有限序列 B空串是由空格构成的串C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储2 若串S1=ABCDEFG, S2=9898 ,S3=#,S4=,执行concat(replace(S1,substr(S1,length(S2),length(S3),S

16、3),substr(S4,index(S2,8),length(S2)其结果为（ E ）AABC#G0123 BABCD#2345 CABC#G2345 DABC#2345EABC#G1234 FABCD#1234 GABC#012343设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ C ）A求子串 B联接 C匹配 D求串长4已知串S=aaab,其Next数组值为（ A ）。A0123 B1123 C1231 D12115串 ababaaababaa 的next数组为（ C ）。A9 B2 C6 D4510串的长度是指（ B ）A串中所含不同字母的个数 B串中所含字符

17、的个数C串中所含不同字符的个数 D串中所含非空格字符的个数二、填空题1 空格串是指_有空格字符所组成的字符串_，其长度等于_空格个数_。 2 组成串的数据元素只能是_字符_。 3一个字符串中_任意个连续的字符组成的子序列_称为该串的子串 。 6模式串P=abaabcac的next函数值序列为_。9串是一种特殊的线性表，其特殊性表现在_其数据元素都是字符_；串的两种最基本的存储方式是_顺序存储_、_链式存储_；两个串相等的充分必要条件是_串的长度相等且两串中对应位置的字符也相等_。 10两个字符串相等的充分必要条件是_两串的长度相等且两串中对应位置的字符也相等_。第 5 章 数组和广义表一、选择

18、题1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ B ）。A. 13 B. 33 C. 18 D. 403. 设有数组Ai,j，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A5，8的存储首地址为( B )。A. BA+141 B. BA+180 C. BA+222 D. BA+2258. 二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙

19、述中（ ）内的正确答案。（1）存放A至少需要（ E ）个字节；（2）A的第8列和第5行共占（ A ）个字节；（3）若A按行存放，元素A8，5的起始地址与A按列存放时的元素（ B ）的起始地址一致。供选择的答案：（1）A. 90 B. 180 C. 240 D. 270 E. 540 （2）A. 108 B. 114 C. 54 D. 60 E. 150 （3）A. A8,5 B. A3,10 C. A5,8 D. A0,9 10. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B1.(n(n+1)/2中，则在B中确定aij（ij）的位置k的关系

20、为( B )。A. i*(i-1)/2+j B. j*(j-1)/2+i C. i*(i+1)/2+j D. j*(j+1)/2+i12. AN，N是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组TN（N+1）/2中，则对任一上三角元素aij对应Tk的下标k是（ B ）。A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+119. 已知广义表LS(a,b,c),(d,e,f),运用head和tail函数取出LS中原子e的运算是( C )。 A. head(tail(LS) B. tail(head(LS)C. head(tail(head(tail(LS) D. head