第二章线性表
第二章线性表
一、选择题
1．线性表是具有n个__C___的有限序列（n>0）。
A．表元素B．字符C．数据元素D．数据项2．一个顺序表所占用的存储空间大小与___B___无关。A．表的长度C．元素的类型
B．元素的存放顺序
D．元素中各字段的类型
3．线性表的顺序存储结构是一种__A___。A．随机存取的存储方式C．索引存取的存储方式
B．顺序存取的存储方式D．Hash存取的存储方式
4. 若线性表采用顺序存储结构，每个元素占用4 个存储单元，第一个元素的存储地址为100,则第12 个元素的存储地址是__B____。A．112 B.144 C.148 D.412
5. 线性表是__A____。
A．一个有限序列，可以为空B．一个有限序列，不能为空C．一个无限序列，可以为空D．一个无限序列，不能为空
6．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为__C____。A．O（n）O（n）B．O（n）O
（1）C．O（1）O（n）D．O（1）O(1) 7．若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，首先需要移动表中___A____中数据元素。
A．n-i B．n+i C．n-i+1 D．n-i-1 8．对顺序存储的线性表，设其长度为n，在任何位置插入或删除操作都是等概率的。删除一个元素时平均要移动表中的____C____个元素。A.n/2 B.（n+1）/2 C.（n-1）/2 D.n 9．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为__C____。（1≤i≤n+1）
A．O（0）B．O（1）C．O（n）D．O（n2）10．线性表中各链接点之间的地址___C____。A．必须连续
B．部分地址必须连续
C．不一定连续D．连续与否无所谓
11．在n个结点的线性表的数组表示中，算法的时间复杂度是O（1）的操作是_A______。
A．访问第i个结点后插入一个新结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i 个结点（1≤i≤n）D．以上都不对
12．单链表中，增加一个头结点的目的是为了____C_____。
A．使单链表至少有一个结点B．标识表结点中首结点的位置C．方便运算的实现
D．说明单链表是线性表的链式存储
13．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是_B____。A．head==NULL C．head->next==head
B．head->next==NULL D．head!=NULL
14．将长度为n的单链表链接在长度为m的单链表后面的算法的时间复杂度采用大O形式表示应该是___C____。
A．O（1）B．O（n）C．O（m）D．O（n+m）15．静态链表中指针表示的是___C____。A．下一个元素的地址C．下一个元素在数组中的位置
B．内存储器的地址
D．左链或右链指向的元素的地址
16．非空的循环单链表head的尾结点p满足__A______。A．P->link=head B．P->link=NULL C．P=NULL D．P=head 17．某线性表用带头结点的循环单链表存储，头指针为head，当head->next->next==head成立时，线性表的长度是___B____。A．0 B．1 C．2 D．3 18．在什么情况下，应使用链式结构存储线性表L?___B____ A．需经常修改L中的结点值C．需要经常查询L中的结点值
B．需不断对L进行删除插入D．L中结点结构复杂
19．与单链表相比较，双向链表的优点之一是___D_____。A．可以省略头结点指针C．插入、删除操作更简单
B．可以随机访问
D．顺序访问相邻结点更灵活
20．某线性表常发生的操作为删除第一个数据元素和最后一个元素后添加新元素，采用__D__作为存储结构，能使其存储效率和时间效率最高。A．单链表C．双向循环链表B．仅用头指针的循环单链表D．仅用尾指针的循环单链表21．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用_D___存储方式最节省运算时间。
A．单链表B．双链表C．单循环链表D．带头结点的双循环链表22．对于一个线性表既要求能够进行较快的插入和删除，又要求存储结构能够反映数据之间的逻辑关系，则应用___C____。
A．顺序方式存储B．散列方式存储C．链接方式存储D．以上方式均可23．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用___A___存储方式最节省时间。
A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表24．若线性表最常用的操作是存取第i个元
素及其前驱和后继元素的值，为节省时间应采用的存储方式为___D_____。
A．单链表B．双向链表C．单循环链表D．顺序表25．下面哪一条是顺序存储结构的优点？___C______ A．插入运算方便C．存储密度大
B．可方便地用于各种逻辑结构的存储表示D．删除运算方便
26．下面关于线性表的叙述中，错误的是___B_____。A.线性表采用顺序存储，必须占用一批连续的存储单元 B.线性表采用顺序存储，便于进行插入和删除的操作 C.线性表采用链接存储，不必占用一片连续的存储单元 D.线性表采用链接存储，便于插入和删除操作
27．在非空线性链表中由p所指的链接点后面插入一个由q 所指的链接点的过程是依次执行动作__B____。
A．q->link=p；p->link=q；C．q->link=p->link；p=q；
B．q-link=p->link；p->link=q；D．p->link=q；q->link=p；26．在非空双向循环链表中由q所指的链接点前面插入一个由p指的链接点的过程是依次执行语句p->rlink=q；p->llink=q->llink;q->llink=p; ____D____。A．q->rlink->llink=p; C．p->rlink->llink=p;
B．q->llink->rlink=p; D．p->llink->rlink=p;
29．在非空双向循环链表中由q所指的链接点后面插入一个
由p指的链接点的动作依次为__D____。
A．p->llink=q ; p->rlink=q->rlink ; q->rlink=p ; q->rlink->llink=p；B．p->rlink=q->rlink ; p->llink=q ; q->rlink ; q->rlink->llink=p；C．p->llink=q ; p->rlink=q->rlink ; q->rlink=p ; p->llink->rlink=p；D．p->llink=q ; p->rlink=q->rlink ; q->rlink=p ; p->rlink->llink=p；30．在双向链表存储结构中，删除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->llink=p ; p->rlink=p->rlink->rlink ; D．p->rlink=p->llink->llink ; p->llink=p->rlink->rlink ; 31．单链表的存储密度为__C____。A．大于 1 B．等于 5 C．小于 1 D．不能确定
二．判断题
1. 线性表的逻辑顺序与存储顺序总是一致的。（）
2. 线性表的顺序存储结构比链式存储结构更好。（）
3. 线性表中的所有元素都有一个前驱元素和后继元素。（）
4. 不论线性表采用顺序存储结构还是链式存储结构，删除值为X 的结点的时间复杂度均为O(n)。（）
5. 线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（）
6. 非空线性表中任意一个数据元素都有且仅有一个直接后继元素。（）
7. 用一组地址连续的存储单元存放
的元素一定构成线性表。（）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。（）
9. 顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（）
10. 顺序表中所有结点的类型必须相同。（）11. 对链表进行插入和删除操作时不必移动链表中结点。（）12. 非空的双向循环链表中任何结点的前驱指针均不为空。（）13. 链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。（）14. 单链表从任何一个结点出发，都能访问到所有结点。（）15. 符号p->next 出现在表达式中表示p 所指的那个结点的内容。（）16. 带表头结点的双向循环链表判空的条件是：first->rlink == first（first 为表头指针）。（）
三、综合应用题
1.利用顺序表的操作，实现以下函数：
1）从顺序表中删除具有最小值的元素并由函数返回被删除元素的值。空出的位置由最后一个元素填补，若顺序表为
空则显示出错信息并退出运行。
2）从顺序表中删除第i个元素并由函数返回被删除元素的值，如果i不合理或顺序表为空则显示出错信息并退出运行。3）向顺序表中第i个位置插入一个新元素x。如果i不合理则显示出错信息并退出运行
4）从顺序表中删除具有给定值x的所有元素。
5）从顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。如果s或t不合理或者顺序表为空，则显示错误信息并退出。
6）从有序顺序表中删除其值在给定值s与t之间（要求s 小于t）的所有元素，如果s或t不合理或顺序表为空，则显示错误信息并退出。
7）将两个有序顺序表合并成一个新的有序顺序表并由函数返回结果顺序表
8）从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。
2.请设计算法将不带头结点的单链表就地逆置。
3.有一个单链表L（至少有1个结点），其头结点指针为head，编写一个过程将L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。
4.设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法：
《数据结构》 第2章线性表 共55题 一、单选 1. (1)分题目ID号：10545 题目难度：容易 在一个长度为n的顺序存储的线性表中，向第i个元素(1≤i≤i十1)位量插入一个新元素时，需要从后向前依次后移【1】个元素。 A. n—i B. n—i十1 C. n一i一 1 D. i 题目答案：B 2. (1)分题目ID号：10546 题目难度：容易 线性表是【1】。 A. 一个有限序列，可以为空 B. 一个有限序列，不能为空 C. 一个无限序列，可以为空 D. 一个无序序列，不能为空题目答案：A 3. (1)分题目ID号：10548 题目难度：容易 在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为【1】 A. (n十1)／2 B. n／2 C. n D. n十l 题目答案：C 4. (1)分题目ID号：10549 题目难度：容易 在一个顺序表的表尾插入一个元素的时间复杂度的量级为【1】 A. ○(n) B. ○(1) C. ○(n*n) D. ○(lbn)题目答案：B 5. (1)分题目ID号：10550 题目难度：容易 单链表的存储密度为【1】 A. 大于1 B. 等于1 C. 小于1 D. 不能确定 题目答案：C 题目分析：存储密度=单链表数据项所占空间/结点所占空间 结点所占空间由数据项所占空间和存放后继结点地址的链域，所以，存储密度小于1 。 6. (4)分题目ID号：10551 题目难度：难 设单链表中指针p指向结点ai，指针q指着将要插入的新结点x，问： [1] 当x插在链表中两个数据元素ai和ai+1之间时，只要先修改【1】后修改【2】 即可。 A.p一＞next＝q B.p一＞next＝p 一>next->next
第2章线性表 本章主要内容： 1、线性表的概念、特点、及其基本操作定义 2、线性表的顺序存储结构及其算法实现 3、线性表的链式存储结构及其算法实现 4、循环链表及其线性表的应用 本章重点难点： 1、线性表的存储结构及算法实现。 2、链式存储结构及算法实现。 3、循环链表 2.1 线性表的定义和基本操作 2.1.1 线性表的定义及特点 1.线性表的定义 线性表是由n（n≥0）个类型相同的数据元素组成的有限序列。n表示线性表中数据元素的个数,称为线性表的长度(简称表长)。当n=0时，线性表为空，称为空线性表。 线性表的逻辑结构通常用数学中的向量形式表示： L=( a 1,a 2 ,...,a i-1 ,a i ,a i+1 ,...,a n ) 或者 L=( a 0,a 1 ,...,a i-1 ,a i ,a i+1 ,...,a n-1 ) 其中：L为线性表名称，习惯用大写书写；a i 为组成该线性表的数据元素，元素的数据类型可以是可以表示出的任何类型。 例 1：分析下列线性表的数据类型： La=（34，89，765，12，90，-34，22）；
Lb=(January, February，March，April，May，June，July，August，September，October，November，December，World, China,Welcome)； Lc=（stu1,stu2,...,stu50) ；其中，数据元素stui的数据类型为： struct student{ char Num; //学号 char *name; //姓名 }; 2、线性表的特点。 除第一个元素外，每个元素有且仅有唯一一个直接前驱，第一个元素无直接前驱，除最后一个元素外，每个元素有且仅有唯一一个直接后继，最后一个元素无直接后继。1-1这种次序描述了元素之间的 1 对 1关系。此外，我们所研究的线性表的元素个数是有限的，各元素的数据类型是相同德，且数据元素可以是任意类型。 2.1.2、线性表的基本操作 （1）初始化线性表L InitList(L) （2）清空线性表L ClearList(L) （3）求线性表L的长度 ListLength(L) （4）判断线性表L是否为空 IsEmpty(L) （5）获取线性表L中的某个数据元素内容 GetElem(L,i,e) （6）查找值为e的数据元素 LocateELem(L,e) （7）返回线性表L中e的直接前驱元素 PriorElem(L,e) （8）返回线性表L中e的直接后继元素 NextElem(L,e) （9）在线性表L中插入一个数据元素 ListInsert(L,i,e) （10）删除线性表L中第i个数据元素 ListDelete(L,i,e)
第二章线性表 一、填空题 1、数据逻辑结构包括线性结构、树型结构、图型结构这三种类型，树形结构和图形结构合称为非线性结构。 2、在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有个前驱结点，最后一个结点没有后续结点，其余每个结点有且只有一个后续结点。 3、在顺序表中插入或删除一个元素，需要平均移动一半元素，具体移动的元素个数与插入或删除的位置有关。 4、在顺序表中，逻辑上相邻的元素，其物理位置一定相邻。在单链表中，逻辑上相邻的元素，其物理位置不一定相邻。 5、在带头结点的非空单链表中，头结点的存储位置由头指针指示，首元素结点的存储位置由头结点的next域指示，除首元素结点外，其它任一元素结点的存储位置由其直接前趋结点的next域指示。 6、阅读下列算法，并补充所缺内容。 void purge_linkst( ListNode *& la ) { // 从头指针为 la 的有序链表中删除所有值相同的多余元素，并释放被删结点空间ListNode *p,*q; if(la==NULL) return; q=la; p = la->link; while (p) { if (p && ___(1)p->data!=q->data___) {q=p; p = p->link;} else { q->link= ___(2)p->link___; delete(p); p=___(3)q->link___; } }//while }// purge_linkst 二、选择题 1、在数据结构中，从逻辑上可以把数据结构分成 C。 A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 2、线性表的逻辑顺序与存储顺序总是一致的，这种说法 B。 A、正确 B、不正确 3、线性表若采用链式存储结构时，要求内存中可用存储单元的地址D。 A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以 4、在以下的述叙中，正确的是B。 A、线性表的线性存储结构优于链表存储结构 B、二维数组是其数据元素为线性表的线性表 C、栈的操作是先进先出 D、队列的操作方式是先进后出 三、综合题 1、已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 A、在P结点后插入S结点的语句序列是（（4）、（1））； B、在P结点前插入S结点的语句序列是（（7）、（11）、（8）、（4）、（1））； C、在表首插入S结点的语句序列是（（5）、（12））；
第二章线性表
第二章线性表 一、选择题 1．线性表是具有n个__C___的有限序列（n>0）。 A．表元素B．字符C．数据元素D．数据项2．一个顺序表所占用的存储空间大小与___B___无关。A．表的长度C．元素的类型 B．元素的存放顺序 D．元素中各字段的类型 3．线性表的顺序存储结构是一种__A___。A．随机存取的存储方式C．索引存取的存储方式 B．顺序存取的存储方式D．Hash存取的存储方式 4. 若线性表采用顺序存储结构，每个元素占用4 个存储单元，第一个元素的存储地址为100,则第12 个元素的存储地址是__B____。A．112 B.144 C.148 D.412 5. 线性表是__A____。 A．一个有限序列，可以为空B．一个有限序列，不能为空C．一个无限序列，可以为空D．一个无限序列，不能为空 6．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为__C____。A．O（n）O（n）B．O（n）O
（1）C．O（1）O（n）D．O（1）O(1) 7．若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，首先需要移动表中___A____中数据元素。 A．n-i B．n+i C．n-i+1 D．n-i-1 8．对顺序存储的线性表，设其长度为n，在任何位置插入或删除操作都是等概率的。删除一个元素时平均要移动表中的____C____个元素。A.n/2 B.（n+1）/2 C.（n-1）/2 D.n 9．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为__C____。（1≤i≤n+1） A．O（0）B．O（1）C．O（n）D．O（n2）10．线性表中各链接点之间的地址___C____。A．必须连续 B．部分地址必须连续 C．不一定连续D．连续与否无所谓 11．在n个结点的线性表的数组表示中，算法的时间复杂度是O（1）的操作是_A______。 A．访问第i个结点后插入一个新结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i 个结点（1≤i≤n）D．以上都不对 12．单链表中，增加一个头结点的目的是为了____C_____。
第2章线性表 一、填空题 1、线性结构反映结点间的逻辑关系是一对一的。 2、线性结构的特点： 1）只有一个首结点和尾结点 2）除首尾结点外，其他结点只有一个直接前驱和一个直接后继 3、线性表的顺序表示又称为顺序存储结构。 4、结点只有一个指针域的链表，称为单链表。 5、首尾相接的链表称为循环链表。 6、线性表的链式表示又称为非顺序映像。 7、指向链表中第一个结点的指针称为头指针。 8、链表中存储第一个数据元素的结点称为首元结点。 二、判断题 1、线性表的逻辑顺序与存储顺序总是一致的。（╳） 2、顺序存储的线性表可以按序号随机存取。（√） 3、顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。（╳） 4、线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（√） 5、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（╳） 6、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√） 7、线性表的链式存储结构优于顺序存储结构。（╳） 8、在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。（√） 9、线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（√） 10、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（╳） 11、线性表的特点是每个元素都有一个前驱和一个后继。（╳） 三、单项选择题 1、顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（B）。 A．110 B．108 C．100 D．120 解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。 2、在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个结点从小到大排序 解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是O(1)。
第二章线性表习题 一判断题 1．线性表的逻辑顺序与存储顺序总是一致的。 2．顺序存储的线性表可以按序号随机存取。 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 7．线性表的链式存储结构优于顺序存储结构。 8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。 二单选题 (请从下列A，B，C，D选项中选择一项) 1．线性表是( ) 。 (A) 一个有限序列，可以为空；(B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空；(D) 一个无序序列，不能为空。 2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（）个元素。 (A) n/2 (B) n+1/2 (C) n -1/2 (D) n 3．线性表采用链式存储时，其地址( ) 。 (A) 必须是连续的；(B) 部分地址必须是连续的； (C) 一定是不连续的；(D) 连续与否均可以。 4．用链表表示线性表的优点是（）。 (A)便于随机存取 (B)花费的存储空间较顺序存储少 (C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同 5．某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。 (A)单链表 (B)双链表 (C)单循环链表 (D)带头结点的双循环链表 6．循环链表的主要优点是( )。 (A)不再需要头指针了 (B)已知某个结点的位置后，能够容易找到他的直接前趋 (C)在进行插入、删除运算时，能更好的保证链表不断开 (D)从表中的任意结点出发都能扫描到整个链表 7．下面关于线性表的叙述错误的是( )。 (A)线性表采用顺序存储，必须占用一片地址连续的单元；
第2章线性表 一选择题 1．下述哪一条是顺序存储结构的优点？（ A ） A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（ B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（ C ）的有限序列（n>0）。 A．表元素 B．字符 C．数据元素 D．数据 项 E．信息项 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链表 C．双链表D．仅有尾指针的单循环链表 6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。 A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表 8. 静态链表中指针表示的是（ BC ）. A．内存地址 B．数组下标 C．下一元素地址D．左、右孩子地址 9. 链表不具有的特点是（ C ） A．插入、删除不需要移动元素 B．可随机访问任一元素
第二章线性表：习题 习题 一、选择题 1．L是线性表，已知Length(L)的值是5，经运算？Delete(L，2)后，length(L)的值是( c)。 A.5 B.0 C.4 D.6 2．线性表中，只有一个直接前驱和一个直接后继的是( )。 A．首元素 B.尾元素 C．中间的元素 D.所有的元素 +3．带头结点的单链表为空的判定条件是( )。 A. head= =NULL B. head->next= =NULL C. head->next=head D. head!=NULL 4．不带头结点的单链表head为空的判定条件是( )。 A. head=NULL B. head->next =NULL C.head->next=head D. head!=NULL 5．非空的循环单链表head的尾结点P满足()。 A. p->next = =NULL B. p=NULL C. p->next==head D. p= =head 6．线性表中各元素之间的关系是( c)关系。 A.层次 B.网状C．有序 D.集合 7.在循环链表的一个结点中有（）个指针。 A．1B．2 C. 0 D. 3 8.在单链表的一个结点中有（）个指针。 A．1B．2 C. 0 D. 3 9.在双链表的一个结点中有（）个指针。 A．1B．2 C. 0 D. 3 10.在一个单链表中，若删除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 LL 12. 在一个单链表中，若在p所指结点之后插入s所指结点，则执行（）。 A．s->next=p; p->next=s; B. s->next=p->next; p->next=s; C. s->next=p->next; p=s; D. p->next=s; s->next=p;
数据结构与算法上机作业第二章线性表
一、选择题 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) 4、等概率情况下，在有n个结点的顺序表上做插入结点操作，需平均移动的结点数目为 C 。提示：插入的位置有n+1个，移动总数为：1+2+3+……+n A. n B. (n-1)/2 C. n/2 D. (n+1)/2 5、在一个长度为n的顺序存储的线性表中查找值为x的元素时，平均查找长度(及x同元素的平均比较次数，假定查找每个元素的概率都相等)为 C 。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 6、在顺序表中，只要知道 D ，就可以求出任一结点的存储地址。 A. 基地址 B. 结点大小 C. 向量大小 D. 基地址和结点大小 7、将两个各有n个元素的有序表归并为一个有序表，其最少的比较次数是 A 。 A. n B. 2n-1 C. 2n D. n-1 8、线性表采用链表存储时其存储地址要求 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中，若要向表头插入一个由指针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. 1234 B. 1243 C. 1324 D. 1423 14、4个元素按A, B, C, D顺序进入S栈，执行两次Pop(S, x)运算后，栈顶元素的值是B 。
第二章线性表（答案） 第二章线性表 一、选择题 1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( ) （A）110 （B）108（C）100 （D）120 2. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。 （A）64（B）63 （C）63.5 （D）7 3.线性表采用链式存储结构时，其地址（）。 (A) 必须是连续的(B) 部分地址必须是连续的 (C) 一定是不连续的(D) 连续与否均可以 4. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（） （A）s->next=p;p->next=s; （B）s->next=p->next;p->next=s; （C）s->next=p->next;p=s; （D）p->next=s;s->next=p; 5.在一个单链表中，若删除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; 6.下列有关线性表的叙述中，正确的是（） （A）线性表中的元素之间隔是线性关系 （B）线性表中至少有一个元素 （C）线性表中任何一个元素有且仅有一个直接前趋 （D）线性表中任何一个元素有且仅有一个直接后继 7.线性表是具有n个（）的有限序列（n≠0) （A）表元素（B）字符（C）数据元素（D）数据项 二、判断题
1.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。（F ） 2.如果没有提供指针类型的语言，就无法构造链式结构。（T ） 3.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余 的结点只有一个前驱和后继。（T ） 4.语句p=p->next完成了指针赋值并使p指针得到了p指针所指后继结点的数据域值。（F ） 5.要想删除p指针的后继结点，我们应该执行q=p->next ； p->next=q->next；free(q)。（T ） 三、填空题 1.已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：___ s->next=p->next; p->next=s;____________________ 。 2.顺序表中逻辑上相邻的元素物理位置(一定)相邻，单链表中逻辑上相邻的元素物理位置___不一定______相邻。 3.线性表L＝（a1，a2，...，an）采用顺序存储，假定在不同的n ＋1个位 置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是_______ n/2__________. 4.在非空双向循环链表中，在结点q的前面插入结点p的过程如下： p->prior=q->prior; q->prior->next=p; p->next=q; ____ q->prior=p;__________________; 5.已知L是无表头结点的单链表，是从下列提供的答案中选择合适的语句序列，分别实现： （1）表头插入s结点的语句序列是________6) 3) (2) 表尾插入s结点的语句序列是_______ 2) 9）1) 7)_____ 1.p->next=s;
第二章线性表 第二章线性表 一、通信录管理 1. 题目要求： 利用链表结构解决通讯录的使用问题，通过菜单实现其常用的几种功能： 1、菜单内容 程序运行后，给出6个菜单项的内容和输入提示； 1、通讯录链表的建立 2、通讯录结点的插入 3、通讯录结点的查询 4、通讯录结点的删除 5、通讯录结点的输出 0、退出管理系统 请选择0—5： 2、设计要求 使用数字0—5来选择菜单项，执行相应的操作，其他输入则不起作用。 2. 算法分析： 按照单链表的结构，设计单链表的建立、结点的插入、结点的查找、结点的删除和链表的输出等相应的子函数。为实现菜单的调用功能，需要设计一个函数用于输出提示信息和处理输入，并将返回值提供给主函数实现相应的子函数调用。 二、约瑟夫生死者游戏 1.题目要求： 约瑟夫游戏的大意是：每30个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分。因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免于难。无奈，大家只能同意这种办法，并议定30个人围成一圈，由第一个人数起，依次报数，数到第9个人，
便把他投入海中，然后再从他的下一个数起，数到第9人，再将他投入海中，如此循环进行，直到剩下15人为止。 要求采用单循环链表实现，利用结点的数据域存放位置。 2.算法分析： 采用单循环链表解决这一问题。将链表结点的数据域存放位置，然后将它们组成一个单循环链表。为了不失一般性，将人数用n表示，报数上限用k表示。算法描述如下： 1、创建含有n个结点的单循环链表； 2、生者与死者的选择： p指向链表第一个结点，初始i置1； while(i<=n/2) { 从p指向的结点沿链前进k-1步； 删除第k个结点（q所指向的结点）；p指向q的下一个结点； 输出其位置q->data; i自增1； } 3、输出所有生者的位置。 三、链表的综合应用设计要求 1.题目要求： 设计一个程序，实现链表的以下功能： 1.建立单链表（头插法，不带头结点）； 2.建立单链表（头插法，带头结点）； 3.建立单链表（尾插法，不带头结点）； 4.建立单链表（尾插法，带头结点）； 5.逆置单链表； 6.有序链表插入； 7.有序链表删除重复元素； 8.无序链表删除重复元素； 9.两链表合并并排序； 10.两链表并集。
第二章线性表 课程简要说明 数据结构是计算机学科的一门核心专业基础课程，是计算机程序设计的重要理论和实践基础。本课程讨论了软件设计中经常遇到的线性表、堆栈、队列、串、数组、二叉树、图等典型数据结构的设计方法以及各种典型排序和查找算法的性能和设计方法，并介绍了各种典型数据结构的应用。通过本课程的学习，学生对软件设计的基本要素和软件的基本结构有了深入理解，并通过算法设计方法学习和上机编程实践，编程能力有了进一步提高。课程要求掌握主要内容包括：线性表、堆栈、队列、串、数组、树、二叉树、图等典型数据结构问题的逻辑结构、存储结构和操作的实现方法，各种典型的排序和查找算法，以及递归算法的设计方法。 通过本课程的学习，应使学生掌握各种数据结构的特点：存贮表示、运算方法以及在计算机科学中最基本的应用，培养、训练学生选用合适的数据结构和运用C语言编写质量高、风格好的应用程序及初步评价算法程序的能力；为编译技术、操作系统和数据库等后续课程的学习以及为应用软件特别是非数值应用软件的开发打下良好的理论基础和实践基础。 要求结合实际问题，学会分析计算机加工的数据对象的特性，能够选择适当的数据结构和存储结构以及相应的算法，并初步掌握算法的简单时间复杂度分析方法，训练掌握各种数据结构的表示方法和实现的算法。 (1)知识要求：学生通过学习该课程后主要应掌握以下内容：①掌握程序设计的基本原理和方法②了解对各种抽象数据类型的性质③掌握处理各种抽象数据类型的基本算法④初步掌握算法的简单时间复杂度分析方法 (2)素质要求：学生通过学习该课程后能够运用数据结构的思想，针对不同数据对象的特性，能够选择适当的数据结构和存储结构以及相应的算法，解决实际的问题。
第二章线性表 第二章线性表 1.假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。 LinkedList Union(LinkedList la,lb)//la.,lb分别是带头结点的两个单链表的头指针， { pa=la->next; pb=lb->next; //pa,pb分别是链表la和lb的工作指针 la->next=null; //la作结果链表的头指针，先将结果链表初始化为空while(pa!=null&&pb!=null) //当两链表均不为空时作if (pa->data<=pb->data) { r=pa->next; //将pa的后结继结点暂存于r。 pa->next=la->next; //将pa结点链于结果表中，同时逆置 la->next=pa; pa=r; //恢复pa为当前的比较结点。 } else { r=pb->next; //将pb的后继结点暂存于r。 pb->next=la->next; //将pb结点链接于结果表中，同时逆置la->next=pb; pb=r; //恢复pb为当前的比较结点。 } while (pa!=null) { r=pa->next; pa->next=la->next;
la->next=pa;pa=r;} while (pb!=null) { r=pb->next; pb->next=la->next; la->next=pb;pb=r; } } 2.已知递增有序的单链表A,B和C分别存储了一个集合，设计算法实现A=A∪（B ∩C），并使求解结构A仍保持递增。要求算法的时间复杂度为O(|A|+|B|+|C|)。其中,|A|为集合A的元素个数。 LinkedList union(LinkedList A,B,C) { pa=A->next; pb=B->next; pc=C->next; //设置三个工作指针。 pre=A; //pre指向结果链表中当前待合并结点的前驱。 if(pa->datadata||pa->datadata) //A中第一个元为结果表的第一元素。 { pre->next=pa; pre=pa; pa=pa->next; } else{while(pb&&pc) //找B表和C表中第一个公共元素。 if(pb->datadata) pb=pb->next; else if(pb->data>pc->data) pc=pc->next; else break; //找到B表和C表的共同元素就退出while循环。
第二章线性表 1. 下面关于线性表的叙述错误的是（）。 A.线性表采用顺序存储必须占用一片连续的存储空间 B. 线性表采用链式存储不必 占用一片连续的存储空间 C. 线性表采用链式存储便于插入和删除操作的实现 D. 线性表 采用顺序存储便于插入和删除操作的实现 2. 设指针变量p指向单链表中结点A，若删除 单链表中结点A，则需要修改指针的操作序列为（）。 A.q=p->next；p->data=q->data；p->next=q->next；free(q)； B. q=p->next；q- >data=p->data；p->next=q->next；free(q)； C. q=p->next；p->next=q->next； free(q)； D. q=p->next；p->data=q->data；free(q)； 3. 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为 （）。 A. O(n) B. O(nlog2n) C. O(1) D. O(n2) 4．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保 持有序，则该操作的时间复杂度为（）。 2 A. O(log2n) B. O(1) C. O(n) D. O(n) 5．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）。 A. head==0 B.head->next==0 C. head->next==head D.head!=0 6．设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（）。 A. head==0 B. head->next==0 C. head->next==head D. head!=0 7．建立一个长度为n的有序单链表的时间复杂度为（） A. O(n) B. O(1) C. O(n2) D. O(log2n) 8．设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。 A. n-i B. n+l -i C. n-1-i D. i 9．设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点 A的后面插入结点X的操作序列为（）。 A. p->right=s； s->left=p； p->right- >left=s； s->right=p->right； B. s->left=p；s->right=p->right；p->right=s； p->right->left=s；
第二章线性表 一、描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。 并说明头指针和头结点的作用。 答：头指针是一个指针变量，里面存放的是链表中首结点的地址，并以此来标识一个链表。如链表H，链表L等，表示链表中第一个结点的地址存放在H、L中。 头结点是附加在第一个元素结点之前的一个结点，头指针指向头结点。当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点，为空表时，该指针域为空。 开始结点指第一个元素结点。 头指针的作用是用来惟一标识一个单链表。 头结点的作用有两个：一是使得对空表和非空表的处理得以统一。二是使得在链表的第一个位置上的操作和在其他位置上的操作一致，无需特殊处理。 二、填空题 1、在顺序表中插入或删除一个元素，需要平均移动（表中一半）元素，具体移动的元素个数与（表长和该元素在表中的位置）有关。 2、顺序表中逻辑上相邻的元素的物理位置（必定）相邻。单链表中逻辑上相邻的元素的物理位置（不一定）相邻。 3、在单链表中，除了首元结点外，任一结点的存储位置由（其直接前驱结点的链域的值）指示。 4、在单链表中设置头结点的作用是（插入和删除元素不必进行特殊处理）。 三、何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑： 1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。 2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。 十一、设顺序表中的数据元素递增有序，试写一算法，将X插入到顺序表的适当位置上，以保持该表的有序性。 答：因已知顺序表L是递增有序表，所以只要从顺序表终端结点（设为i位置元素）开始向前寻找到第一个小于或等于x的元素位置i后插入该位置即可。 在寻找过程中，由于大于x的元素都应放在x之后，所以可边寻找，边后移元素，当找到第一个小于或等于x的元素位置i时，该位置也空出来了。 算法如下： //顺序表存储结构如题2.7 void InsertIncreaseList( Seqlist *L , Datatype x ) { int i; if ( L->length>=ListSize) Error(“overflow"); for ( i=L -> length ; i>0 && L->data[ i-1 ] > x ; i--)
第二课线性表 一选择题 1．下列属顺序存储结构优点的是（）。 A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示参考答案：A 2．下列关于线性表的叙述中，错误的是（）。 A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 参考答案：B 3．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。 A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表 参考答案：A 4．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。 A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表 参考答案：D 5．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（）存储方式最节省运算时间。 A．单链表B．双链表C．带尾指针的单循环链表D．带头结点的双循环链表 参考答案：D 6．静态链表中指针表示的是（）。 A．下一元素的地址B．内存储器的地址 C．下一元素在数组中的位置D．左链或右链指向的元素的地址 参考答案：C 7．链表不具有的特点是（）。 A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 参考答案：B 8．双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链表中的一个结点，现要求删去p所指结点，则正确的删除是（）（链中结点数大于2，p不是第一个结点）。 A．p->llink->rlink=p->llink; p->llink->rlink=p->rlink; free(p); B．free (p); p->llink->rlink=p->llink; p->llink->rlink=p->rlink; C．p->llink->rlink=p->llink; free (p); p->llink->rlink=p->rlink; D．以上A，B，C都不对。 参考答案：D
数据结构复习资料第二章线性表 第二章线性表 重点：重点讨论单链表的表示，插入和删除操作的实现及其算法的时间和空间复杂性讨论。掌握循环链表和双向链表的基本概念；掌握静态链表的基本概念及基本操作的实现。了解一元多项式的表示及相加。 难点：单链表的表示及基本操作的实现，静态链表的基本概念及基本操作的实现，算法时间复杂度的分析。 学习提要： 1. 了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。 2. 熟练掌握这两类存储结构的描述方法，如一维数组中一个区域]..[j i 的上、下界和长度之间的变换公式(1,1,1-+=+-=+-=L i j L j i i j L )，链表中指针p 和结点p *的对应关系(结点)(next p >-*是结点p *的后继等)，链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求。 3. 熟练掌握线性表在顺序存储结构上实现基本操作：查找、插入和删除的算法。 4. 熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构。 5. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。 2.1 线性表的逻辑结构 一．线性表及基本运算 1. 线性表（逻辑结构） （1）定义
（2）特性 （3）举例（略） 2.线性表的基本运算（即常规操作） 例2-1、2-2见书20P 。 2.2 线性表的顺序存储结构 线性表按存储方式分为链表 顺序表 1.顺序存储 顺序存储结构（或顺序映象sequential mapping ）的特点： * 线性表的顺序存储结构是一种“随机存取”存储结构。 2.顺序表的具体实现 3.顺序表的基本操作的实现 (1) 顺序表的插入操作),,(x i l insert 着重在于分析及用函数来表示算法的一般格式。 (2) 顺序表的删除操作),(i l delete （3）定位操作),(x l locate (4) 讨论分析相应算法的时间复杂度 顺序表与数组的区别：顺序表在逻辑上相邻的两个结点，物理位置上也相邻；顺序表可作插入、删除操作，而数组是不可作这些操作的，所以，顺序表和数组又是不同的。 2.3 线性表的链式存储结构 顺序表的优缺点： 优点 缺点 可利用空间表等双向链表 循环链表单链表） 线性链表链表分为 ( 1.线性链表（单链表） （1）定义
第 2 章线性表 课后习题讲解 1. 填空 ⑴在顺序表中，等概率情况下，插入和删除一个元素平均需移动（）个元素，具体移动元素的个数与（）和（）有关。 【解答】表长的一半，表长，该元素在表中的位置 ⑵顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（）。【解答】108 【分析】第5个元素的存储地址=第1个元素的存储地址＋(5－1)×2=108 ⑶设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（）。 【解答】p->next=(p->next)->next ⑷单链表中设置头结点的作用是（）。 【解答】为了运算方便 【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。 ⑸非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。 【解答】p->next=head 【分析】如图2-8所示。 ⑹在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（）；删除开始结点的操作序列为（）。 【解答】s->next =rear->next; rear->next =s; rear =s; q=rear->next->next; rear->next->next=q->next; delete q; 【分析】操作示意图如图2-9所示：
⑺一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（）；在给定值为x的结点后插入一个新结点的时间复杂度为（）。 【解答】Ο(1)，Ο(n) 【分析】在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο(1)；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为Ο(n)。 ⑻可由一个尾指针唯一确定的链表有（）、（）、（）。 【解答】循环链表，循环双链表，双链表 2. 选择题 ⑴线性表的顺序存储结构是一种（）的存储结构，线性表的链接存储结构是一种（）的存储结构。 A 随机存取 B 顺序存取 C 索引存取 D 散列存取 【解答】A，B 【分析】参见2.2.1。 ⑵线性表采用链接存储时，其地址（）。 A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 连续与否均可以 【解答】D 【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。 ⑶单循环链表的主要优点是（）。 A 不再需要头指针了 B 从表中任一结点出发都能扫描到整个链表； C 已知某个结点的位置后，能够容易找到它的直接前趋； D 在进行插入、删除操作时，能更好地保证链表不断开。 【解答】B ⑷链表不具有的特点是（）。 A 可随机访问任一元素 B 插入、删除不需要移动元素 C 不必事先估计存储空间 D 所需空间与线性表长度成正比 【解答】A ⑸若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋，则采用（）存储方法最节省时间。 A 顺序表 B 单链表 C 双链表 D 单循环链表 【解答】A 【分析】线性表中最常用的操作是取第i 个元素，所以，应选择随机存取结构即顺序表，同时在顺序表中查找第i个元素的前趋也很方便。单链表和单循环链表既不能实现随机存取，查找第i个元素的前趋也不方便，双链表虽然能快速查找第i个元素的前趋，但不能实现随机存取。 ⑹若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（）存储方法最节省时间。 A 单链表 B 带头指针的单循环链表 C 双链表 D 带尾指针的单循环链表