【综合文库】
第二章 线性表
一、选择题
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.144C.148D.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-iB．n+i C．n-i+1D．n-i-1 8．对顺序存储的线性表，设其长度为n，在任何位置插入或删除操作都是等概率的。删除一个元素时平均要移动表中的____C____个元素。 A.n/2 B.（n+1）/2C.（n-1）/2D.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=NULLD．P=head 17．某线性表用带头结点的循环单链表存储，头指针为head，当head->next->next==head成立时，线性表的长度是___B____。 A．0B．1C．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．等于5C．小于1D．不能确定
二．判断题
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.设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法：
查看全文