数据结构线性表.docx

数据结构线性表.docx

《数据结构线性表.docx》由会员分享，可在线阅读，更多相关《数据结构线性表.docx（73页珍藏版）》请在冰点文库上搜索。

数据结构线性表

数据结构与算法上机作业

第二章线性表

一、选择题

1、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新的元素算法的时间复杂度为C。

A.O（log2n）B.O

（1）C.O（n）D.O（n2）

2、以下关于线性表的说法中，不正确的是B。

A.线性表中的数据元素可以是数字、字符、结构等不同类型

B.线性表中包含的数据元素个数不是任意的

C.线性表中的每一个结点都有且只有一个直接前驱和直接后继

D.存在这样的线性表：

表中各结点都没有直接前驱和直接后继

3、在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为B。

A.O

（1）B.O（n）C.O（n2）D.O（log2n）

4、等概率情况下，在有n个结点的顺序表上做插入结点操作，需平均移动的结点数目为

C。

A.nB.（n-1）/2C.n/2D.（n+1）/2

5、在一个长度为n的顺序存储的线性表中查找值为x的元素时，平均查找长度（及x同元素的平均比较次数，假定查找每个元素的概率都相等）为C。

A.nB.n/2C.（n+1）/2D.（n-1）/2

6、在顺序表中，只要知道A，就可以求出任一结点的存储地址。

A.基地址B.结点大小C.向量大小D.基地址和结点大小

7、将两个各有n个元素的有序表归并为一个有序表，其最少的比较次数是A。

A.nB.2n-1C.2nD.n-1

8、线性表采用链表存储时其存储地址要求D。

A.必须是连续的B.部分地址必须是连续的

C.必须是不连续的D.连续的和不连续的都可以

9、下面关于线性表的描述中，错误的是B。

A.线性表采用顺序存储，必须占用一片连续的存储单元

B.线性表采用顺序存储，便于进行插入和删除操作

C.线性表采用链式存储，不必占用一片连续的存储单元

D.线性表采用链式存储，便于插入和删除操作

10、向具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是A

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.1234B.1243C.1324D.1423

14、4个元素按A,B,C,D顺序进入S栈，执行两次Pop（S,x）运算后，栈顶元素的值是B。

A.AB.BC.CD.D

15、从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列

D命令。

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.3B.4C.56.6

18、设已将元素A,B,C依次入栈，元素D正等待进栈。

那么下列4个序列中不可能出现的出栈顺序为A。

A.CADBB.CBDAC.CDBAD.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.6B.4C.3D.2

21、队列通常采用的两种存储结构是（A）。

A.顺序存储结构和链式存储结构B.散列方式和索引方式

C.链表存储结构和线性存储结构D.线性存储结构和非线性存储结构

22、循环队列SQ队满的条件是B。

A.SQ->rear==SQ->frontB.（SQ->rear+1）%MAXLEN==SQ->front

B.SQ->rear==0D.SQ->front==0

23、若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为B。

A.5和1B.4和2C.2和4D.1和5

24、链栈与顺序栈相比，有一个较为明显的优点是A。

A.通常不会出现满栈的情况B.通常不会出现栈空的情况

C.插入操作更加方便D.删除操作更加方便

25、设用一个大小为M=60的顺序表A[M]表示一个循环队列，如果当前的尾指针rear=32，头指针front=15，则当前循环队列的元素的个数为C。

A.42B.16C.17D.41

26、串是一种特殊的线性表，其特殊性体现在B。

A.可以顺序存储B.数据元素是一个字符

C.可以链式存储D.数据元素可以是多个字符

27、设主串的长度为n，模式串的长度为m，则串匹配的KMP算法的时间复杂度为c。

A.O（m）B.O（n）D.O（m+n）D.O（m×n）

28、已知串S=“abab”，其Next数组值为c。

A.0123B.0121C.0112D.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;

D.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,0B.0,n-1C.n-1,0D.n-1,n-1

32、某队列允许在两端进行入队操作，但仅允许在一端进行出队操作（称为输出受限的双端队列），若a,b,c,d,e元素依次进队，则不可能得到的顺序是C。

A.bacdeB.dbaceC.dbcaeD.ecbad

33、在双向链表中间插入一个结点时，需要修改修改D个指针域。

A.1B.2C.3D.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.aB.（）C.（a,b,c,d）D.（b,c,d）

39、下面说法不正确的是A。

A.广义表的表头总是一个广义表B.广义表的表尾总是一个广义表

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+1）/2。

6、根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单线链表和双向链表。

7、链式存储的特点是利用指针来表示数据元素之间的逻辑关系。

8、静态链表（线性表的游标实现）是指用数组下标表示单链表的指针。

9、在静态链表中，一般都有一个变量available表示的结点链，其中的结点为空闲节点。

10、在栈中，可进行插入和删除操作的一端称端点。

11、在进栈运算时，应先判别栈是否满。

在出栈运算时应先判别栈是否空。

当栈中元素为n个时，进栈运算时发生上溢，则说明该栈的最大容量为n+1。

12、设有一空栈，现有输入序列为1,2,3,4,5，经过push,push,pop,push,pop,push,push,pop,pop之后，输出序列为2354。

13、对于循环向量的循环队列，求队列长度的公式为（rear-front+n+1）%n。

14、栈的逻辑特点是先进后出。

队列的逻辑特点是先进先出。

两者的共同特点是只允许在它们的端点出插入和删除数据元素，区别是栈在栈顶进行插入删除，队列在队尾插入，队头删除。

15、链队列LQ为空时，LQ->front->next=LQ->rear.

16、在一个链队列中，若队首指针为front，队尾指针为rear，则判断该队列只有一个结点的条件为frontnext=rear。

17、设串S=“Ilikecomputer”，T=“com”，则Length（S）=14。

Index（S,T）=6。

18、在KMP算法中，next[j]只与模式串有关，而与主无关。

19、字符串“ababaab“的Next数组值是0112322。

20、稀疏矩阵一般压缩存储的方式有三种，分别是三元数组存储（行,列,值）、、行指针链表和十字链表。

21、二维数组M中每个元素的长度是3字节，行下标i从0~7，列下标j从0～9，从首地址&M[0][0]开始连续存放在存储器中。

若按行优先的方式存放，元素M[7][5]的起始地址为

SA+225；若按列优先方式存放，元素M[7][5]的起始地址为SA+145。

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函数中进行测试：

先构建两个有序的线性表，然后合并这两个线性表。

四、已知一个单向链表，试给出复制该链表的算法。

要求：

1、定义线性表的节点的结构以及节点的型和位置的型。

2、定义线性表的基本操作

3、在1，2的基础上，完成本题。

4、在main函数中进行测试：

先构建一个线性表，并定义一个空线性表，然后进行复制。

五、写出从一个带表头的单链表中删除其值等于给定值x的结点的算法函数：

intdelete（LIST&L,intx）;如果x在该链表中，则删除对应结点，并返回其在链表中的位置（逻辑位置，第一个结点的逻辑位置为1），否则返回-1。

要求：

1、定义线性表的节点的结构以及节点的型和位置的型。

2、定义线性表的基本操作

3、在1，2的基础上，完成本题。

4、在main函数中进行测试：

先构建一个线性表，然后调用函数删除值等于给定值的节点。

六、写出一个将两个静态链表（属于同一个存储池）合并的算法函数：

voidMerge（cursorM,cursorN）;合并的方法是将N链表中的所有结点添加到M链表的后面，并将N链表的表头结点添加到空闲结点链表中。

要求：

1、定义静态链表的结点的结构以及结点的型SPACE以及位置（position）和游标（cursor）的型。

2、定义静态链表的基本操作：

voidInitialize（）;初始化，将所有存储池中的结点设置为空闲；cursorGetNode（）;从空闲链中获取一个结点；voidFreeNode（cursorq）;将结点q加入到空闲链；voidInsert（elementtypex,positionp,cursorM）;在链表M中的位置为p的元素后面添加一个值为x的结点；voidDelete（cursorM,positionp）;在链表M中删除位置为p的元素的后一个元素。

3、在1、2的基础上完成本题。

4、在main函数中进行测试：

先构建一个存储池，然后在该存储池中创建两个静态表，最后将这两个静态表合并。

七、利用指针表示的线性表（链表）表示一个多项式，并实现两个多项式的相加和相乘运算。

假设多项式形式为：

其中，系数ai≠0，指数ei满足em>em-1>…>e2>e1>=0。

要求：

1、定义多项式每一项的结构。

2、定义两个多项式的相加和相乘运算函数。

3、在main函数中，构建两个多项式，并测试相加和相乘运算。

八、试编写一个整数进制转换的通用函数convert（intnum,STACKS,intn），要求将整数m转换为n进制数，n进制数的各位依次存放在栈S中。

并在主函数中进行测试。

要求：

1、定义栈以及栈的型。

2、定义栈的各种操作。

3、实现函数convert。

4、在main函数中，通过调用函数convert将num的n进制数存放到一个栈中，并通过出栈的方法输出该n进制数

九、设有一个循环队列Queue，只有头指针front，不设尾指针，另设一个含有元素个数的计数器count，试写出相应的判断队列空、判断队列满、出队算法和入队算法。

要求：

1、定义相应的循环队列的型（只有头指针，没有尾指针，但有一个元素个数的计数器）；

2、定义该队列的四个算法：

判断队列空、判断队列满、出队算法和入队算法；

3、在main函数验证算法的正确性。

十、设主串T=“abcaabbabcabaacbacba“，模式为p=“abcabaa”。

1、计算模式p的nextval函数值

2、不写算法，只画出利用KMP算法进行模式匹配时，每一趟的匹配过程。

要求：

1、写出模式p的nextval值；

2、画出KMP算法的每一趟匹配过程（可参照教材P61从第8行开始的内容）；

3、不需要编写程序。

十一、假设表达式中允许包含三种括号：

圆括号、方括号和大括号。

设计一个算法采用顺序栈（用数组表示的栈）判断表达式中的括号是否正确配对。

要求：

1、定义栈以及栈的型，栈中所存放元素的类型为字符型，定义枚举类型Boolean，其中两个元素分别为TRUE和FALSE。

2、定义栈的各种操作。

3、定义函数Booleancheck（char*s）;判断s中的括号是否正确配对，如果正确配对，返回TRUE，否则返回FALSE。

4、在主函数中验证所编写函数的正确性。

十二、设有一个带头结点的双向链表h，设计一个算法用于查找第一个元素之为x的结点，并将其与其前驱结点进行交换。

要求：

1、定义带头结点的双向链表的型DLIST。

2、定义双向链表DLIST的基本操作。

3、定义函数intswap（elementtypex,DLIST&h），查找第一个元素之为x的结点，如果在链表中存在元素值为x的结点，并其与其前驱结点进行交换，并返回1，否则返回0。

4、在主函数中测试所编写函数的正确性。

十三、试编写一个求三元组顺序表示的稀疏矩阵对角线元素之和的算法

十四、当具有相同行值和列值的稀疏矩阵A和B均以三元组顺序表方式存储时，试写出矩阵相加的算法，其结果存放在以行逻辑链接顺序表方式存储的矩阵C中。

十五、设有一个稀疏矩阵：

1、写出三元组顺序表存储表示

2、写出十字链表存储的顺序表示

十六、画出广义表LS=（（）,（e）,（a,（b,c,d）））的头尾链表存储结构（类似于教材P70图2-27.9）。

要求：

按照教材中的事例画出相应的图形，不需要编程。

其中第一个节点如下：

十七、试编写求广义表中原子元素个数的算法。

要求：

1、定义广义表的节点的型；

2、定义广义表的基本操作；

3、定义本题要求的函数intelements（listpointerL）；函数返回值为广义表中原子的个数。

例如，广义表（a,b,c,d）原子的个数为4，而广义表（a,（a,b）,d,e,（（i,j）,k））中院子的个数为3。

提示：

先利用基本操作Cal（L）获得表头，判断表头是不是原子，再利用基本操作Cdr（L）获得除第一个元素外的其他元素所形成的表L1，利用递归的方法求L1中原子的个数。

要求：

1、上述作业要求在单独完成；

2、完成后，于规定期限内提交到ftp服务器的相应目录中中，注意，在提交时将所编写的程序统一拷贝到一个Word文件中，文件名格式为“学号+姓名”

三（数组表示）

#include

usingnamespacestd;

#definemaxlength100

typedefintposition;

typedefintElementtype;

structLIST{

Elementtypeelements[maxlength];

intlast;

};

positionEnd（LISTL）//线性表长度

{

return（L.last+1）;

}

voidInsert（Elementtypex,positionp,LIST&L）

{

positionq;

if（L.last>=maxlength-1）

cout<<"listisfull"<

elseif（（p>L.last+1）||（p<1））

cout<<"positiondoesnotexit"<

else

{

for（q=L.last;q>=p;q--）

{

L.elements[q+1]=L.elements[q];

}

L.last=L.last+1;

L.elements[p]=x;

}

}

voidDelete（positionp,LIST&L）

{

positionq;

if（（p>L.last）||（p<1））

cout<<"positiondoesnotexist"<

else

{

L.last=L.last-1;

for（q=p;q<=L.last;q++）

L.elements[q]=L.elements[q+1];

}

}

positionLocate（Elementtypex,LISTL）

{

positionq;

for（q=1;q<=L.last;q++）

if（L.elements[q]==x）

returnq;

return（L.last+1）;

}

voidmerge（LIST&L,LIST&L1,LIST&L2）

{

positionp=0,p1,p2;

positionlen1=End（L1）;

positionlen2=End（L2）;

L.last=len1+len2-1;

for（p1=0;p1

{

L.elements[p]=L1.elements[p1];

p++;

}

p--;

for（p2=0;p2

{

L.elements[p]=L2.elements[p2];

p++;

}

p--;

}

voidread（LIST&L）

{

cout<

cout<<"请输入线性表长度"<

cin>>L.last;

for（inti=0;i

{

cin>>L.elements[i];

}

}

voidwrite（LIST&L）

{

for（inti=0;i

{

cout<

}

cout<

}

intmain（）

{

LISTL,L1,L2;

read（L1）;

writ