数据结构第二章线性表测试题

数据结构第二章线性表习题02线性表【单选题】1.以下不属于线性结构特点的就是（c）。

ａ、存有且仅有一个数据元素并无轻易前驱ｂ、存有且仅有一个数据元素并无轻易后继ｃ、有且仅有一个数据元素既无直接前驱又无直接后继ｄ、大多数据元素存有且仅有一个轻易前驱，存有且仅有一个轻易后继2.线性表是具有n个（c）的有限序列。

ａ、信息项ｂ、字符ｃ、数据元素ｄ、数据项3.线性表的逻辑顺序与存储顺序总是一致的，这种说法（b）。

ａ、正确ｂ、不正确4.在顺序表，数据元素e1与其轻易后继e2在存储边线上（a）。

ａ、必相连ｂ、必不相连ｃ、可以相连可不相连5.在长为n的顺序表中删除一个数据元素，平均需移动（d）个数据元素。

ａ、nｂ、n-1ｃ、n/2ｄ、(n-1)/26.在短为n的顺序表填入一个数据元素，平均值须要移动（c）个数据元素。

ａ、nｂ、n-1ｃ、n/2ｄ、(n-1)/27.单链表是一种（b）存取的存储结构ａ、随机ｂ、顺序ｃ、索引ｄ、连续8.以下属顺序存储结构优点的就是（a）。

ａ、存储密度大ｂ、插入运算方便ｃ、删除运算方便ｄ、可方便地用于各种逻辑结构的存储表示9.以下属于单链表中优点的就是（c）。

ａ、顺序存取ｂ、插入操作能在o(1)的时间复杂度上完成ｃ、插入时不需移动数据元素ｄ、节省存储空间10.在单链表，数据元素e1与其轻易后继e2在存储边线上（c）。

ａ、必相连ｂ、必不相连ｃ、可以相连可不相连11.以下属单链表与循环链表区别的是（b）。

ａ、结点结构相同ｂ、搜寻结点的算法中，循环完结条件相同ｃ、对存储空间连续性的建议相同ｄ、对与否涵盖头结点的建议相同12.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（a）存储方式最节省时间。

ａ、顺序表中ｂ、双链表中ｃ、率先垂范结点的双向循环链表ｄ、单循环链表13.若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（d）存储方式最节省运算时间。

第2章线性表班级学号__________-姓名一、判断正误（×）1. 链表的每个结点中都恰好包含一个指针。

链表中的结点可含多个指针域，分别存放多个指针。

例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。

（×）2. 链表的物理存储结构具有同链表一样的顺序。

链表的存储结构特点是无序，而链表的示意图有序。

（×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。

链表的结点不会移动，只是指针内容改变。

（×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。

（×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

正好说反了。

顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”（×）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

前一半正确，但后一半说法错误，那是链式存储的优点。

顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。

（×）7. 线性表在物理存储空间中也一定是连续的。

线性表有两种存储方式，顺序存储和链式存储。

后者不要求连续存放。

（×）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。

线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。

（×）9. 顺序存储方式只能用于存储线性结构。

顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。

（后一节介绍）（×）10. 线性表的逻辑顺序与存储顺序总是一致的。

理由同7。

链式存储就无需一致。

数据结构--线性表习题及答案第⼆章线性表⼀、选择题1、若长度为n的线性表采⽤顺序存储结构，在其第i个位置插⼊⼀个新元素算法的时间复杂度（）。

A. O(log2n)B.O(1)C. O(n)D.O(n2)2、若⼀个线性表中最常⽤的操作是取第i个元素和找第i个元素的前趋元素，则采⽤（）存储⽅式最节省时间。

A. 顺序表B. 单链表C. 双链表D. 单循环链表3、具有线性结构的数据结构是（）。

A. 图B. 树C. ⼴义表D.栈4、在⼀个长度为n的顺序表中，在第i个元素之前插⼊⼀个新元素时，需向后移动（）个元素。

A. n-iB. n-i+1C. n-i-1D. i5、⾮空的循环单链表head的尾结点p满⾜（）。

A. p->next==headB. p->next==NULLC. p==NULLD. p==head6、链表不具有的特点是（）。

A. 可随机访问任⼀元素B. 插⼊删除不需要移动元素C. 不必事先估计存储空间D. 所需空间与线性表长度成正⽐7、在双向循环链表中，在p指针所指的结点后插⼊⼀个指针q所指向的新结点，修改指针的操作是（）。

A. p->next=q;q->prior=p;p->next->prior=q;q->next=q;B. p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;C. q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;D. q->next=p->next;q->prior=p;p->next=q;p->next=q;8、线性表采⽤链式存储时，结点的存储地址（）。

A. 必须是连续的B. 必须是不连续的C. 连续与否均可D. 和头结点的存储地址相连续9、在⼀个长度为n的顺序表中删除第i个元素，需要向前移动（）个元素。

第2章线性表2.1选择题1．对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择（）最节省时间A）顺序表 B）带头结点的双循环链表C）单链表 D）带尾结点的单循环链表【答案】A2．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（）(1≤i≤n+1)。

A） O(0) B） O(1) C） O(n) D） O(n2)【答案】C3．双向链表中有两个指针域，prior和next，分别指向前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（）A） p->prior=q; q->next=p; p->prior->next=q; q->prior=p->prior;B） q->prior=p->prior; p->prior->next=q; q->next=p; p->prior=q->next;C） q->next=p; p->next=q; p->prior->next=q; q->next=p;D） p->prior->next=q; q->next=p; q->prior=p->prior; p->prior=q;【答案】D4．在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（）A）O(nlog2n） B） O(1） C） O(n） D） O(n2）【答案】C5．在一个以 h 为头指针的单循环链中，p 指针指向链尾结点的条件是（）A）p->next==NULL B） p->next==hC）p->next->next==h D） p->data==-1【答案】B6．对于一个具有n个结点的线性表，建立其单链表的时间复杂度是（）A）O(n) B） O(1) C）O(nlog2n) D） O(n2)【答案】A8．在双向链表存储结构中，删除p所指的结点时须修改指针（）A）p->prior->next=p->next p->next->prior=p->prior;B）p->prior=p->prior->prior p->prior->next=p;C）p->next->prior=p p->next=p->next->nextD）p->next=p->prior->prior p->prior=p->next->next;【答案】A9．线性表采用链式存储时，其元素地址（）A）必须是连续的 B）一定是不连续的C）部分地址是连续的 D）连续与否均可【答案】D2.2 填空题1．线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____________。

数据结构第二章线性表基本信息：[矩阵文本题] *1. 在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数为 [单选题] *A．n-i+1(正确答案)B．n-iC．iD．i-12. 若一个顺序表中第一个元素的存储地址为1000，每个元素占4个地址单元，那么，第6个元素的存储地址应是 [单选题] *A．1020(正确答案)B．1010C．1016D．10243. 带头结点的单链表（以head为头指针）为空的判断条件是 [单选题] *A．head!=NULLB．head->next==headC．head->next==NULL(正确答案)D．head ==NULL4. 将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为 [单选题] *A．O(1)B．O(m)(正确答案)C．O(n)D．O(m+n)5. 在一个单链表中，若删除p指向结点的后继结点，则执行的操作为 [单选题] * A．q=p->next；p->next=p->next->next；free(q)；(正确答案)B．p=p->next；q=p->next；p=q->next；free(q)；C．q=p->next->next；p=p->next；free(q)；D．p=p->next->next；q=p->next；free(q)；6. 线性表是一个有限序列，组成线性表的基本单位是 [单选题] *A．数据项B．数据元素(正确答案)C．数据域D．字符7. 顺序表便于 [单选题] *A．插入结点B．删除结点C．按值查找结点D．按序号查找结点(正确答案)8. 对需要频繁插入和删除结点的线性表，适合的存储方式是 [单选题] *A．顺序储存B．链式存储(正确答案)C．索引存储D．散列存储9. 设带头结点的单循环链表的头指针为head，指针变量p指向尾结点的条件是 [单选题] *A．p->next->next==headB．p->next==head(正确答案)C．p->next->next==NULLD．p->next==NULL10. 针对线性表逻辑上相邻的两个元素，下列叙述中，正确的是 [单选题] *A．采用顺序存储时一定相邻，采用链式存储时也一定相邻B．采用顺序存储时一定相邻，采用链式存储时不一定相邻(正确答案)C．采用顺序存储时不一定相邻，采用链式存储时一定相邻D．采用顺序存储时不一定相邻，采用链式存储时也不一定相邻11. 线性表的逻辑顺序和存储顺序总是一致的。

数据结构第二章线性表1答案第二部分线性表一、选择题1．关于顺序存储的叙述中,哪一条是不正确的( B )A.存储密度大B.逻辑上相邻的结点物理上不必邻接C.可以通过计算直接确定第i个结点的位置D.插入、删除操作不方便2．长度为n的单链表连接在长度为m的单链表后的算法的时间复杂度为( C )A O(n)B O(1)C O(m)D O(m+n)3．在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是：( A )A 访问第i个结点（1<=i<=n）和求第i个结点的直接前趋（2<=i<=n）B 在第i个结点（1<=i<=n）后插入一个新结点C 删除第i个结点（1<=i<=n）D 将n个结点从小到大排序4．一个向量第一个元素的存储地址是100 ，每个元素的长度为2 ，则第5 个元素的地址是：( B )（A ）110 （ B ）108 （C ）100 （D ）1205．已知一个顺序存储的线性表，设每个结点需要占m个存储单元，若第一个结点的地址为da，则第i个结点的地址为：( A ) A）da+(i-1)*m B) da+i*m C) da-i*m D) da+(i+1)*m6．在具有n个结点的单链表中，实现（A ）的操作，其算法的时间复杂度为O(n)。

A）遍历链表和求链表的第i个结点B）在地址为p的结点之后插入一个结点C）删除开始结点D）删除地址为p的结点的后继结点7．链表是一种采用（B ）存储结构存储的线性表。

（A ）顺序（B ）链式（ C ）星式（D ）网状8．线性表若采用链式存储结构时，要求内存中可用存储单元的地址：（D ）（A ）必须是连续的（ B ）部分地址必须是连续的（C ）一定是不连续的（ D ）连续或不连续都可以9．线性表Ｌ在（B ）情况下适用于使用链式结构实现。

（Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入（Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂10．在长度为n 的顺序表的第i (1≤i≤n+1) 个位置上插入一个元素，元素的移动次数为( A )A.n-i+1B.n-iC.iD.i-111．线性表是（A）。

第二章线性表一、选择题1.线性表是（）A．一个有限序列，可以为空B．一个有限序列，不可以为空C．一个无限序列，可以为空D．一个无限序列，不可以为空2.一维数组与线性表的特征是（）。

A．前者长度固定，后者长度可变B．两者长度均固定C．后者长度固定，前者长度可变D．两者长度均可变3.用单链表方式存储的线性表，存储每个结点需要两个域，一个数据域，另一个是( ).A．当前结点所在地址域B．指针域C．空指针域D．空闲域4.用链表表示线性表的优点是（）。

A．便于随机存取B．便于进行插入和删除操作C．占用的存储空间较顺序表少D．元素的物理顺序与逻辑顺序相同5.在具有 n 个结点的单链表中，实现___的操作，其算法的时间复杂度都是O（n）。

A．遍历链表和求链表的第i个结点D．删除地址为P的结点的后继结点B．在地址为P的结点之后插入一个结点 C．删除开始结点6.下面关于线性表的叙述中，错误的是（）。

A．线性表采用顺序存储必须占用一片连续的存储单元B．线性表采用顺序存储便于进行插入和删除操作C．线性表采用链式存储不必占用一片连续的存储单元D．线性表采用链式存储便于进行插入和删除操作7.已知单链表的每个结点包括一个指针域next，它指向该结点的后继结点。

现要将指针 q 指向的新结点插入到指针 p 指向的结点之后，下面的操作序列中正确的是（）。

A . q = p->next; p->next = q->next ;B . p->next = q->next; q = p->next ;C . q->next = p->next; p->next = q ;D . p->next = q; q->next = p->next ;8.设 a l，a2， a3为三个结点； p , 10 , 20 代表地址，则如下的链表存储结构称为（）。

A．链表B．单链表C．双向循环链表D．双向链表9.单链表的存储密度（）。

第2章线性表参考答案一、填空1. 【严题集2.2①】在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。

2. 线性表中结点的集合是有限的，结点间的关系是一对一的。

3. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。

4. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。

5. 在顺序表中访问任意一结点的时间复杂度均为 O(1)，因此，顺序表也称为随机存取的数据结构。

6. 【严题集2.2①】顺序表中逻辑上相邻的元素的物理位置必定相邻。

单链表中逻辑上相邻的元素的物理位置不一定相邻。

7. 【严题集2.2①】在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。

8．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。

二、判断正误（在正确的说法后面打勾，反之打叉）（ × ）1. 链表的每个结点中都恰好包含一个指针。

答：错误。

链表中的结点可含多个指针域，分别存放多个指针。

例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。

（ × ）2. 链表的物理存储结构具有同链表一样的顺序。

错，链表的存储结构特点是无序，而链表的示意图有序。

（ × ）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。

错，链表的结点不会移动，只是指针内容改变。

（ × ）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。

（ × ）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

错，正好说反了。

顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”（ × ）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

第2章自测卷答案一、填空1. 【严题集2.2①】在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。

2. 线性表中结点的集合是有限的，结点间的关系是一对一的。

3. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。

4. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。

5. 在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。

6. 【严题集2.2①】顺序表中逻辑上相邻的元素的物理位置必定相邻。

单链表中逻辑上相邻的元素的物理位置不一定相邻。

7. 【严题集2.2①】在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。

8．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。

二、判断正误（在正确的说法后面打勾，反之打叉）（×）1. 链表的每个结点中都恰好包含一个指针。

答：错误。

链表中的结点可含多个指针域，分别存放多个指针。

例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。

（×）2. 链表的物理存储结构具有同链表一样的顺序。

错，链表的存储结构特点是无序，而链表的示意图有序。

（×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。

错，链表的结点不会移动，只是指针内容改变。

（×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。

（×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

错，正好说反了。

顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”（×）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

第2章线性表一、单项选择题1．B2.A3．C4．C5．C6．B7．B8．.A9．D10. B11. B12．B13.C二、判断题（在各题后填写“√”或“×”）1. 链表中的头结点仅起到标识的作用。

(× )2．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。

( √ ) 3．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。

( × )4. 对任何数据结构链式存储结构一定优于顺序存储结构。

(× )5. 所谓静态链表就是一直不发生变化的链表。

( × )6. 线性表的特点是每个元素都有一个前驱和一个后继。

( × )7. 循环链表不是线性表. ( × )8. 线性表只能用顺序存储结构实现。

( × )9. 线性表就是顺序存储的表。

( × )10. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。

(√ )三、填空题1．必定不一定2．头指针头结点指针域前驱结点指针域3．双向链表4． nO(n)n/2O(n)5．. 单链表循环链表双向链表6．指针7．（n-1）/28．py->next=px->next; px->next=py9. 4 210． i=1; i≤st11．(1)L->next=null ∥置空链表,然后将原链表结点逐个插入到有序表中(2)p!=null ∥当链表尚未到尾，p为工作指针(3)q!=null ∥查p结点在链表中的插入位置，这时q是工作指针。

(4)p->next=r->next ∥将p结点链入链表中(5)r->next=p ∥r是q的前驱，u是下个待插入结点的指针。

四、应用题1. 在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。

数据结构第二章习题第2章线性表一、单选题1．线性表是具有n个_________的有限序列。

a、表元素B.字符C.数据元素D.数据项2。

线性表格是。

a．一个有限序列，可以为空b．一个有限序列，不可以为空c．一个无限序列，可以为空d．一个无限序列，不可以为空3．线性表采用链表存储时，其地址_________。

a、 U4。

列表中不连续的部分必须是U4。

a．可随机访问任一结点b．插入删除不需要移动元素c．不必事先估计存储空间d．所需空间与其长度成正比5．设线性表有n个元素，以下操作中，_________在顺序表上实现比在链表上实现效率更高。

a、输出I（1≤ 我≤ n） th元素值b．交换第1个元素与第2个元素的值c．顺序输出这n个元素的值d、输出与线性表中给定值x相等的元素序列号6．设线性表中有2n个元素，以下操作中，_________在单链表上实现要比在顺序表上实现效率更高。

a．删除指定的元素b、在最后一个元素后插入新元素。

C.按顺序输出前k个元素d．交换第i个元素和第2n-i-1个元素的值(i=0,1…,n-1)7.如果最常见的操作是获取第i个节点及其前体，请使用___________________。

a．单链表b．双链表c、与单链表相比，双链表的优点之一是。

a．插入和删除操作更简单b．可以进行随机访问c．可以省略表头指针或表尾指针d．访问前后相邻结点更灵活9．带头结点的单链表l为空的判定条件是_________。

a、 l==nullb.l->next==nullc.l->next==ld.l！=无效的10．在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是_________。

a、 o（1）b.o（n）c.o（n2）d.o（nlog2n）11．在一个长度为n(n>1)的带头结点的单链表h上，另设有尾指针r（指向尾结点），执行_________操作与链表的长度有关。

第二章线性表：习题习题一、选择题1．L是线性表，已知Length(L)的值是5，经运算？Delete(L，2)后，length(L)的值是( c)。

A.5B.0C.4D.62．线性表中，只有一个直接前驱和一个直接后继的是( )。

A．首元素 B.尾元素C．中间的元素 D.所有的元素+3．带头结点的单链表为空的判定条件是( )。

A. head= =NULLB. head->next= =NULLC. head->next=headD. head!=NULL4．不带头结点的单链表head为空的判定条件是( )。

A. head=NULLB. head->next =NULLC.head->next=headD. head!=NULL5．非空的循环单链表head的尾结点P满足()。

A. p->next = =NULLB. p=NULLC. p->next==headD. p= =head6．线性表中各元素之间的关系是( c)关系。

A.层次B.网状C．有序 D.集合7.在循环链表的一个结点中有（）个指针。

A．1B．2 C. 0 D. 38.在单链表的一个结点中有（）个指针。

A．1B．2 C. 0 D. 39.在双链表的一个结点中有（）个指针。

A．1B．2 C. 0 D. 310.在一个单链表中，若删除p所指结点的后继结点，则执行（）。

A．p->next= p->next ->next;B. p=p->next; p->next=p->next->next;C. p->next= p->next;D. p=p->next->next;11.指针P指向循环链表L的首元素的条件是（）。

A．P= =L B. P->next= =L C. L->next=P D. P-> next= =NU LL12. 在一个单链表中，若在p所指结点之后插入s所指结点，则执行（）。

数据结构第二章线性表习题含答案说明：顺序存储的线性表称为向量。

一,单项选择题一个向量第一个元素的地址是100，每个元素的长度为2，则第5个元素的地址是__①_B__。

A) 110 B) 108 C) 100 D) 120线性结构通常采用的两种存储结构是__①A___。

A) 顺序存储结构和链式存储结构B) 散列方式和索引方式C) 链表存储结构和数组D) 线性存储结构和非线性存储结构不带头结点的单链表head为空的判定条件是__①__A_.A) head==NULL B) head->next==NULLC) head->next==head D) head!=NULL带头结点的单链表head为空的判定条件是__①B___。

A) head==NULL B) head->next==NULLC) head->next==head D) head!=NULL非空的循环链表head的尾结点（由p所指向）满足__①_C__。

A) p->next==NULL B) p==NULLC) P->next==head D) p==head在循环双链表的p所指结点之后插入s所指结点的操作是___①_C_。

A) p->right=s; s->left=p; p->right->left=s; s->right=p->right;B) p->right=s; p->right->left=s; s->left=p; s->right=p->right;C) s->left=p; s->right=p->right; p->right=s; p->right->left=s;D) s->left=p; s->right=p->right; p->right->left=s; p->right=s;在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点, 则执行__①c___。

数据结构第二章——线性表基本信息：[矩阵文本题] *1. 顺序表的第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的存储地址是（） [单选题] *A. 110B. 108(正确答案)C. 100D. 1202. 在 n 个结点的顺序表中,算法的时间复杂度是 O(1)的操作是（）: [单选题] *A. 访问第 i 个结点(1≤i≤n)和求第 i 个结点的直接前驱(2≤i≤n)(正确答案)B. 在第 i 个结点后插入一个新结点(1≤i≤n)C. 删除第 i 个结点(1≤i≤n)D. 将 n 个结点从小到大排序3. 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。

[单选题] *A. 8B. 63.5(正确答案)C. 63D. 74. 链接存储的存储结构所占存储空间（）。

[单选题] *A. 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针(正确答案)B. 只有一部分，存放结点值C. 只有一部分，存储表示结点间关系的指针D. 分两部分，一部分存放结点值，另一部分存放结点所占单元数5. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。

[单选题] *A. 必须是连续的B. 部分地址必须是连续的C. 一定是不连续的D. 连续不连续都可以(正确答案)6. 线性表L在（）情况下适用于使用链式结构实现。

[单选题] *A. 需经常修改L中的结点值B. 需不断对L进行删除插入(正确答案)C. L中含有大量的结点D. L中结点结构复杂7. 单链表的存储密度（）。

[单选题] *A. 大于1B. 等于1C. 小于1(正确答案)D. 不确定8. 将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是（）。

[单选题] *A. n(正确答案)B. 2n-1C. 2nD. n-19. 在一个长度为n的顺序表中向第i个元素(1≤i≤n+l )之前插入一个新元素时，需向后移动（）个元素。

数据结构线性表试题.txt我自横刀向天笑，笑完我就去睡觉。

你的手机比话费还便宜。

路漫漫其修远兮，不如我们打的吧。

第2章线性表2.1选择题1．对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择（）最节省时间A）顺序表 B）带头结点的双循环链表C）单链表 D）带尾结点的单循环链表【答案】A2．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（）(1≤i≤n+1)。

A） O(0) B） O(1) C） O(n) D） O(n2)【答案】C3．双向链表中有两个指针域，prior和next，分别指向前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（）A） p->prior=q; q->next=p; p->prior->next=q; q->prior=p->prior;B） q->prior=p->prior; p->prior->next=q; q->next=p; p->prior=q->next;C） q->next=p; p->next=q; p->prior->next=q; q->next=p;D） p->prior->next=q; q->next=p; q->prior=p->prior; p->prior=q;【答案】D4．在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（）A）O(nlog2n） B） O(1） C） O(n） D） O(n2）【答案】C5．在一个以 h 为头指针的单循环链中，p 指针指向链尾结点的条件是（）A）p->next==NULL B） p->next==hC）p->next->next==h D） p->data==-1【答案】B6．对于一个具有n个结点的线性表，建立其单链表的时间复杂度是（）A）O(n) B） O(1) C）O(nlog2n) D） O(n2)【答案】A8．在双向链表存储结构中，删除p所指的结点时须修改指针（）A）p->prior->next=p->next p->next->prior=p->prior;B）p->prior=p->prior->prior p->prior->next=p;C）p->next->prior=p p->next=p->next->nextD）p->next=p->prior->prior p->prior=p->next->next;【答案】A9．线性表采用链式存储时，其元素地址（）A）必须是连续的 B）一定是不连续的C）部分地址是连续的 D）连续与否均可【答案】D2.2 填空题1．线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____________。