2.7 习题
2.7.1 知识点：线性表的逻辑结构
一、选择题1①线性表L= (a1, a2,…)n，下列说法正确的是(D)。
A.每个元素都有一个直接前驱和一个直接后继。
B.线性表中至少要有一个元素。
C.表中诸元素的排列顺序必须是由小到大或由大到小。
D.除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。
2①在线性表的下列运算中，不改变数据元素之间结构关系的运算是
( D)。
A.插入
B.删除
C.排序
D.定位3①线性表是具有n个(C)的有限序列 ( n>0)。
【清华大学1998】
A.表元素
B.字符
C.数据元素
D.数据项
E.信息项
二、判断题(T) 1①线性表中的每个结点最多只有一个前驱和一个后继。
(F) 2①线性表中的每个结点都至少有一个前驱结点和后继结点。
(F) 3① 线性表是N个数的有限序列。
(F) 4①同一线性表的数据元素可以具有不同的特性。
(T) 5①线性表的长度n就是表中数据元素的个数，当n=0时，称为空
(T) 6①线性表是一个相当灵活的数据结构，它的长度可根据需要增长或缩短。
(F)7①对线性表中的数据元素只能进行访问，不能进行插入和删除操作。
2.
7.2 知识点：
线性表的顺序存储结构
一、选择题1①在一个长度为n的顺序表中，在第i个元素(1 <= i v=n+D 之前插入一个新元素时需向后移动(B)个元素.A. n-1B. n-i+1C. n-i-
1D. i2①若某线性表中最常用的操作是取第i个元素和第i个元素的前趋元素，则采用(D)存储方式最节省时间。
A.单链表
B.双链表
C.单向循环
D.顺序表3②一个数组第一个元素的存储地址是100，每个元素的长度为2，则第  5 个元素的地址是( B)
A. 110
B. 108
C. 100
D. 1204①下述哪一条是顺序存储结构的优点(A)。
【北方交通大学2001】
A.存储密度大
B.插入运算方便
C.删除运算方便
D.可方便地用于各种逻辑结构的存储表示5③若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为( C) (1<=i<=n+1) 。
【北京航空航天大学1999】
A. O (0)
B. O (1)
C. O (n)
D. O (n2) 6③对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为( C)。
【青岛大学2000】
A. O(n) O(n)
B. O(n) O(1)
C. O(1) O(n)
D. O(1) O(1)
二、填空题1①线性表的顺序存储的缺点是在任意位置上―插入―数据与__删除___数据费时间。
2①设一线性表的顺序存储，总存储容量为M，其元素存储位置的范围为
__0~M-1 _____ 。
3①向一个长度为n的向量中删除第i个元素(1< i买时，需向前移动_n- i___个元素。
三、简答题1③已知线性表的存储结构为顺序表，阅读下列算法，并回答问题：
voidf30(SeqList*L){inti，j;for(i=j=0;i<L->length;
i++)if(L->data[i]>=0){if (i!=j) L->data[j]=L->data[i];j++; }L->length二j;} (1)设线性表L= (21, -7, -8,
19, 0, -11, 34, 30, -10)，写出执行f30 (&L)后的L状态；(21,19,0,34,30) ( 2)简述算法f30 的功能。
删除顺序表中小于0的元素
四、编程题1④已知顺序表La中数据元素按非递减有序排列。
试写一个算法，将x插入到La的合适位置上，保持该表的有序性。
2.
7.3 知识点：
线性表的链式存储结构
数据结构与算法第二版课后题答案一、选择题1①链表是一种采用(B)存储结构存储的线性表。
A.顺序
B.链式
C.星式
D.网状2①链接存储的存储结构所占存储空间 ( A)。
A.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。
B.只有一部分，存放结点值。
C.只有一部分，存储表示结点间关系的指针。
D.分两部分，一部分存放结点值，另一部分存放结点所占单元数。
3①线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）。
A.必须是连续的
B.部分地址必须是连续的
C. 一定是不连续的
D.连续或不连续都可以4①线性表1在（B）情况下适用于使用链式结构实现。
A.需经常修改L中的结点值
B.需不断对L进行删除插入
C.L中含有大量的结点
D.L中结点结构复杂5①对单链表表示法，以下说法错误的是（C）。
A.数据域用于存储线性表的一个数据元素。
B.指针域（或链域）用于存放一个指向本结点所含数据元素的直接后继所在结点的指针。
C.所有数据通过指针的链接而组织成单链表。
D.NULL称为空指针，它不指向任何结点只起标志作用。
6①以下说法正确的是（D）。
A.顺序存储方式的优点是存储密度大且插入、删除运算效率高
B.链表的
每个结点中都恰好包含一个指针  C.线性表的顺序存储结构优于链式存储结构
D.顺序存储结构属于静态结构而链式结构属于动态结构7①以下说法错误的是（D）。
A.求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存
储结构时实现的效率低  B.顺序存储的线性表可以随机存取  C.由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活D.线性表的链式存储结构优于顺序存储结构8①不带头结点的单链表head为空的判定条件是（A）。
A. head= =NULL
B. head->next= =NULL
C. head->next= 二head
D. head!二
NULL9①带头结点的单链表head为空的判定条件是（B）。
A．head= =NULLB．head->next= =NULLC．head->next= 二headD. head!二
NULL10②在头指针为head的非空单循环链表中，指针p指向尾结点，下列关系成立的是（A）。
A. p->next= =head
B. p->next->next= =head
C. p->next= =NULL
D. p= =head11②
在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q 和p之间插入s
结点，则执行语句（C）。
A. s->next=p->next;p->next=s;
B. p->next=s->next;s->next=p;
C. q->next=s;s-> next二p;
D. p->next二s;s>next二q;12②在一个单链表中，若p所指结点不是最后结点，在p之后插入s结点，则应执行语句（B）。
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;13②在一个单链表中，若删除p所指结点的后续结点，则应执行语句（A）。
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;14②旨针p、q和r依次指向某循环链表中三个相邻的结点，交换结点*q 和结点*r 在表中次序的程序段是（A）。
A. p->next=r；q->next=r->next；r->next=q；
B. p->next=r；r->next=q；
q->next=r->next；C. r->next=q；q->next=r->next；p->next=r；D. r->next=q；
p->next=r; q->next二r->next; 15①链表不具有的特点是（B）【福州大学1998】
A.插入、删除不需要移动元素
B.可随机访问任一元素
C.不必事先估计
存储空间D.所需空间与线性长度成正比16① 下面的叙述不正确的是（BC）
【南京理工大学1996】
A.线性表在链式存储时，查第i个元素的时间同i的值成正比
B.线性表在链式存储时，查第i个元素的时间同i的值无关
C.线性表在顺序存储时，查第i个元素的时间同i的值成正比
D.线性表在顺序存储时，查第i 个元素的时间同i的值无关17①下面关于线性表的叙述中，错误的是哪一个？
（B）【北方交通大学2001】
A.线性表采用顺序存储，必须占用一片连续的存储单元。
B.线性表采用顺序存储，便于进行插入和删除操作。
C.线性表采用链接存储，不必占用一片连续的存储单元。
D.线性表采用链接存储，便于插入和删除操作。
18①在一个以h为头的单循环链中，p指针指向链尾的条件是(A)【南京理工大学1998】
A. p->next二h
B. p->next二NULLC p->next->next二hD. p->data=-119②若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用(A)存储方式最节省时间。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。