线性表典型例题
一、单项选择题
[例7-1]在数据结构中，与所使用计算机无关的数据叫( ①)结构；链表是一种采用( ②)存储结构存储的线性表；链表适用于( ③)查找；在链表中进行( ④)操作的效率比在线性表中进行该操作的效率高。
①A．存储B．物理C．逻辑D．物理和逻辑
②A．顺序B．网状C．星式D．链式
③A．顺序B．二分法C．顺序及二分法D．随机
④A．二分法查找B．快速查找C．顺序查找D．插入
解析：本题考查的是基本概念。本题答案为：①C；②D；③A；④D。
[例7-2] 链表不具备的特点是( )。
A．插入和删除不需要移动元素B．可随机访问任一结点
C．不必预分配空间D．所需空间与其长度成正比
解析：线性表可随机访问任一结点，而链表必须从第一个数据结点出发逐一查找每个结点。本题答案为：B。
[例7-3] 不带头结点的单链表head为空的判定条件是( )。
A．head＝＝NULL B．head_>next＝＝NULL
C．head_>next＝＝head D．head!＝NULL
解析：在不带头结点的单链表head中，head指向第一个数据结点。空表即该表没有结点，head＝＝NULL表示该单链表为空。本题答案为：A。
[例7-4] 带头结点的单链表head为空的判定条件是( )。
A．head＝＝NULL B．head—>next＝＝NULL
C．head—> next＝＝head D．head!＝NULL
解析：在带头结点的单链表head中，head指向头结点。空表即该表只有头结点，head —>next＝＝NULL表示该单链表为空。本题答案为：B。
[例7-5] 带头结点的循环单链表head中，head为空的判定条件是( )。
A．head＝＝NULL B．head—>next＝＝NULL
C．head—> next＝＝head D．head!＝NULL
解析：在带头结点的循环单链表head中，head指向头结点。空表即该表只有头结点，head—>next＝＝head表示该单链表为空。本题答案为：C。
[例7-6] 线性表采用链式存储时其存储地址( )。
A．必须是连续的B．部分地址必须是连续的
C．一定是不连续的D．连续不连续都可以
解析：链式存储采用动态存储，地址一般不连续。本题答案为：D。
[例7-7] 在双向链表的* p结点前插入新结点*s的操作为( )。
A．p—>prior=s；s—>next=p；p—>prior—>next=s；s—>prior=p—>prior；
B．p—>prior=s；p—>prior—>next=s；s—>next=p；s—>prior=p—>prior；
C．s—>next=p；s—>prior=p—>prior；p—>prior=s；p—>prior—>next=s；
D．s—>next=p；s—>prior=p—>prior；p—>prior—>next=s；p—>prior=s；
解析：在双向链表的* p结点前插入新结点* s的操作如图7.12所示，图中虚线为所作的操作，序号为操作顺序。本题答案为：D。
图7.12 双向链表插入结点的过程示意图
(例7-8)若某表最常用的操作是在最后一个结点后插入一个结点和删除第一个结点，则采用( )存储方式最节省运算时间。
A．单链表B．双向链表
C．给出表头指针的循环单链表D．给出尾指针的循环单链表
解析：在链表中插入或删除一个结点，需修改相邻结点的指针域。上述四个选项中，只有选项D才能从尾指针经过最少的结点来进行题目要求的插入或删除操作。本题答案为：D。
[例7-9] 若线性表中有2n个元素，算法( )在单链表上实现要比在顺序表上实现效率更高。
A．删除所有值为x的元素B．在最后一个元素的后面插入一个新元素C．顺序输出前k个元素D．交换其中某两个元素的值
解析：对于选项A，在单链表上和顺序表上实现的时间复杂度都为O(n)，但后者要移动大量的元素，因此在单链表上实现效率更高。本题答案为：A。
(例7-10) 在长度为n的( )上，删除第一个元素，其算法复杂度为O(n)。
A．只有表头指针的不带头结点的循环单链表
B．只有尾指针的不带表头结点的循环单链表
C．只有表尾指针的带头结点的循环单链表
D．只有尾指针的带表头结点的循环单链表
解析：本题答案为：A。具体算法如下：
linklist * delfirst(linklist * h)
{
Linklist * p＝h；
while(p—> next!＝h) //找到表尾结点
p＝p—>next；
p—>next=h—> next；
free(h)；
returnp一>next；//返回头指针
}
二、填空题
[例7-11] 在单链表中结点* p后插入结点* s的指令序列为；。
解析：在单链表中结点* p后插入结点* s，即将* p 的后继结点变为* s 的后继结点，* s 则成为* p的后继结点。操作指令序列为：s—>next＝p—>next；p—>next＝s。
[例7-12]在线性表的链式存储结构中，根据每个结点所含指针的个数，链表可分为和；而根据指针的链接方式，链表又可分为和。
解析：本题答案为：单链表；多重链表；循环链表；普通链表(非循环链表)。
[例7-13] 在单链表中，要删除某一个指定的结点，必须找到该结点的 结点。 解析：由单链表的特点可知，删除某一个结点的操作是将其前驱结点的next 指针域指 向该结点的后继结点。本题答案为：前驱。
[例7-14] 在一个长度为n 的顺序表中删除第i(0≤i ≤n 一1)个元素，需向前移动 个元素。
解析：需将第i 个元素后的元素依次前移一个位置，总共移动(n-1)-(i+1)+1个元素。本题答案为：n-i-1。
[例7-15] 在一个具有n 个结点的单链表，在 * p 结点后插入一个新结点的时间复杂度是 ；在给定值为x 的结点后插入一个新结点的时间复杂度是 。
解析：在 * p 结点后插入一个新结点 * s 的操作是：s —> next ＝p —> next ；p —>next ＝ s ；其时间复杂度为0(1)。
在给定值为x 的结点后插入一个结点，首先要找到该结点，然后再进行插入。找到该 结点的时间复杂度为O(n)，插入的时间复杂度为O(1)。本题答案为：O(1)；O(n)。
三、应用题
(例7-16) 设A 是一个线性表(a 0，a 1，…，a i ，…，a n-1)，采用顺序存储结构，则在等概率情况下平均每插入一个元素需要移动的元素个数是多少?若元素插在a i 和a i+1之间 (0≤i ≤n-1)的概率为1(1)/2
n n n -+，则平均每插入一个元素所需要移动的元素个数是多少?
解析：在等概率情况下，平均每插入一个元素需要移动的元素个数为：
(012)12
n n n ++++=+ 若元素插在a i 和a i+l 之间(0≤i ≤n-1)的概率为
(1)/2n i n n -+，则平均每插入一个元素所需 要移动的元素个数为：
10n i -=∑2222()221(1)1(1)/2(1)3
n i n n n n n n n -+??=+-++=??++ (例7-17) 简述线性表采用顺序存储方式和链式存储方式的优缺点。
解析：顺序表的优点是可以随机访问数据元素，而且不需要额外的空间存储元素间的逻辑关系；缺点是表的大小固定，增减结点需要移动大量元素。链表的优点是增减元素非常方便，只需要修改指针内容；缺点是只能进行顺序访问，另外在每个结点上增加指针域会造成存储空间增大。
[例7-18] 若频繁地对一个线性表进行插入和删除操作，则应采用何种存储结构来存储该线性表?为什么?
解析：应采用链式结构来存储该线性表。采用链式存储结构来存储线性表，在进行插 入和删除操作时的复杂度体现在查找插入或删除结点的前驱结点的操作上，查找过程中平 均移动指针域的次数为表长的一半；而采用顺序存储结构存储线性表，在进行插入和删除 操作时的复杂度则体现在元素的移动上，平均需移动表中的一半元素。因为指针域的移动 操作次数比元素的移动操作次数少得多，所以应采用链式结构来存储该线性表。
(例7—19) (1)写出在双向链表中的结点 * p 前插入一个结点 *s 的语句序列。
(2)写出判断带头结点的双向循环链表L 为空表的条件。
解析：(1)s —>prior ＝p —>prior ；p —>prior — >next ＝s ；
s —>next ＝p ；p —>prior ＝s ；
(2)(L＝＝L—>next)&&(L＝＝L—>prior)
[例7-20] 链表所表示的元素是否是有序的?如果有序，则有序性体现在何处?链表所表示的元素是否一定要在物理上是相邻的?有序表的有序性又如何理解?
解析：链表所表示的元素是有序的，其有序性体现在逻辑有序，即指针有指向。链表所表示的元素在物理上不一定相邻。有序表的有序性不仅在逻辑结构上有序，而且在物理结构上也有序。
四、算法设计题
(例7-21)编写一个算法，将一个带头结点的单链表逆转。要求在原链表空间上进行逆转，即不允许构造新的链表结点；
解析：从单链表的一种构造方法——头插法中可以得知，该方法构造的线性表中结点的顺序与插人次序相反。因此我们可以将表结点从前往后逐个拆下并用头插法插人新表，所构造的单链表即为原表的逆转。
具体算法如下：
linklist * reverse(1inklist * h)
{
linklist * p，*q，*r；
p＝h—>next；
h—>next=NULL；//构造空表
while(p!＝NULL)
{
q=p；//拆下结点
p=p—> next；
q—>next=h—>next；//用头插法插入
h—>next=q；
}
return h；
}
(例7-22) 已知一个顺序表La的元素按值非递减有序，编写一个算法将元素x插人后保持该表仍然按值非递减有序。
解析：要让插入新元素后的顺序表仍然按值非递减有序，必须把x插入到表中第一个大于等于x的元素之前。应先在表中找到该位置，然后后移该元素，空出一个位置，再将x 插入。
具体算法如下：
insert(sqlist *La，datatype x) //La为指向顺序表的指针
{
int i=0，j；
while(i<= La—>last) //查找插入位置i
{
if(x<=La—>data[i])
break；
i++；
}
for(j=La—>last+1；j>i；j--) //后移所有大于等于x的元素
La—>data[j]=La—>data[j-1]；
La—>data[i]＝x；//将x插入
La—>last++；//表长度加1
}
(例7-23)用顺序表A、B表示集合，编写算法求集合A和集合B的交集C(假设A、B 表内无重复元素)。’
解析：求C＝A∩B，C中元素是A、B中的公共元素。对于表A中的每个元素，在表B中扫描，若有与它相同的元素，则为交集元素，将其放到C中。
具体算法如下：
intersection(sqlist A，sqlist B，sqlist * C)
{
int i，j，k＝0；
for(i＝0；i<＝A．1ast；i++)
{
j=0；
while(j<＝B.1ast&& A.dara[i]!＝B.data[j]
j++；
if(j<＝B.1ast) //表示A.data[i]在B中
C—>data[k++]＝A.data[i]
}
C—>last=k—l；//修改表长度
}
[例7-24]编写一个算法，计算在头指针为head的单链表中数据域值为x的结点个数。
解析：先设一计数器n，初值为0。然后遍历链表中的每个结点，每遇到一个结点都需要判断其数据域值是否为x，如果是，计数器n加1。遍历完成后计数器n的值就是所求的结点数。
具体算法如下：
int count(linklist * head, datatype x)
{
int n=0；
linklist * p；
p = head；
while(p ! = NULL)
{
if(p—> data = = x)
n++;
p=p—>next；
}
return n；
}
(例7-25)用单链表La、Lb表示集合A、B，编写算法求集合A和集合B的差集C，并用链表Lc表示(假设A、B内无重复元素)。
解析：根据集合运算规则可知，集合A—B中包含所有属于集合A而不属于集合B的元素。具体做法是：从头到尾扫描单链表La，并判断当前元素是否在单链表Lb中；若不
在，则将其插入单链表Lc中。
具体算法如下：
linklist * difference(linklist * La, linklist * Lb)
{
linklist *Lc, * pa, *pb, * s, * r；
pa= La—>next
Lc = (linklist * ) malloc (sizeof (linklist)) ;
r=Lc;
while(pa! = NULL)
{
pb=Lb—> next;
while (phb! = NULL & & pb—> data ! = pa—> data)
pb= pb—>next；
if(pb = = NULL)
{
s= (linklist * )malloe(sizeof(linklist));
s—> data= pa—>data；
r—>next=s；
r—s；
}
pa= pa—>next；
}
r—>next = NULL；
return Lc；
}
(例7-26) 已知两个头指针分别为La和Lb的单链表，它们的元素按值递增有序。编写一算法将两个单链表合并，要求合并后链表仍然递增有序，不允许开辟另外的链表空间。
解析：由于题目要求不开辟另外的链表空间，所以首先以两个链表中的一个头结点为新链表的头结点构造一个空的单链表。从头到尾逐个比较La和Lb表中的元素，将值较小的元素结点链接到新表的末尾，若结点值相同则将其中一个链接到新表的末尾而释放另一个。当La或Lb为空后，把另一个链表余下的结点链接到新表的末尾。
具体算法如下：
linklist * union(linklist * La, linklist * Lb)
{
linklist * pa, * pb, * r；
pa = La—> next；
pb= Lb—>next；
r=La；//以*La为新表头结点，r为新表尾指针
free(Lb); //释放Lb表头结点
while(pa! =NULL && pb! =NULL)
{
if ( pa—> data< pb—> data)
{
r=pa;
pa= pa—>next；
}
else if(pa—>data
{
r—> next = pb；
r=pb；
pb = pb—> next;
r—>next= pa；
}
else //pa->data = = Pb—>data的情况
{
r=pa；//将原La表结点插入，原Lb表结点删除
pa = pa—> next；
s=pb；
pb = pb—>next；
free(s)；
}
}
if(pa==NULL) //将Lb表剩余结点链到新表
r—>next=pb；
return La；//返回新表头结点地址
}
(例7-27) 设计——个将循环双链表中结点*p与其后继结点交换位置的算法。解析：本题应充分利用双向链表可对前驱结点和后继结点进行操作的特点。
具体算法如下：
int swap(dlinklist * p)
{
dlinklist * q；
if(p—>next= = p—>prior) //只有一个数据结点，不能交换
return 0；//交换失败
q=p—>next；//q指向* p的后继
p—>next=q—>next；//删除* q
q—>next—>prior= p；
q—>prior= p—>prior；//把*q插入*p前
q—>next=p；
p—>prior—>next=q；
p—>prior=q；
return 1；//交换成功
}
线性表习题
一单项选择题
1．下面关于线性表的叙述中，错误的是[]
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于进行插入和删除操作。
2．带头结点的双向链表head为空的判定条件是[]
A.head==NULL
B.head->next==NULL
C.head->next==head
D.head!=NULL
3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用[]存储方式最节省时间
A．顺序表 B.双链表 C 带头结点的双循环链表 D 单循环链表
4．链表不具有的特点是[]
A 插入和删除不需要移动元素
B 可随机访问任一元素
C 不必事先估计存储空间
D 所需空间与线性长度成正比
5．下面叙述中不正确的是[]
A 线性表在链式存储时，查找第i个元素的时间与i的值成正比
B线性表在链式存储时, 查找第i个元素的时间必须经过前i-1个元素
C 线性表在顺序存储时，查找第i个元素的时间与i的值成正比
D线性表在顺序存储时，查找第i个元素的时间与i的值无关
6对于顺序存储的线性表，访问结点和增加，删除结点的时间复杂度分别是
A O(n), O(n)
B O(n), O(1)
C O(1) O(n)
D O(1) O(1)
7 在一个以h为头指针的单循环链表中，p指针指向链尾的条件是
A p->next=h
B p->next=NULL
C p->next->next=h
D p->data=-1
8在单链表指针为p的结点之后插入指针为s的结点，正确的操作是
A p->next=s;s->next= p->next
B s->next= p->next; p->next=s
C p->next=s; p->next=s->next
D p->next=s->next; p->next=s
9 在双向链表存储结构中，删除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->next
D p->next= p->prior->prior; p->prior= p->next->next
10 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是
A 单链表
B 静态链表
C 线性链表
D 顺序存储结构
11如果最常用的操作是取第i个结点及其前驱，则采用[]存储方式最节省时间
A 单链表
B 双链表
C 单循环链表
D 顺序表
12 在一个长度n(n>1)的单链表上设有头和尾两个指针，执行[]操作与链表
的长度有关
A 删除单链表中第一个元素结点
B删除单链表中最后一个元素结点
C 在单链表第一个元素结点前插入一个新结点
D 在单链表最后一个元素结点后插入一个新结点
13 与单链表相比，双链表的优点之一是
A插入和删除操作更简单 B 可以进行随机访问
C 可以省略头指针和表尾指针
D 访问相邻结点更灵活
14 设有两个长度为n的单链表，结点类型相同，若以h1为表头指针的链表是非循环链表，以h2为表头指针的链表是循环链表，则
A 对于两个链表来说，插入任意一个结点的操作，其时间复杂度是O（1） B对于两个链表来说，删除最后一个结点的操作，其时间复杂度是O（n）
C h2要比h1占用更多的存储空间
D h1和h2是不同类型的变量
二．判断题
1链表中的头结点仅起到标识的作用
2 顺序存储结构的主要缺点之一是不利于插入和删除操作
3 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的
4 顺序存储方式的插入和删除操作效率太低，因此它不如链式存储方式好
5 顺序存储方式只能用于存储线性结构
6 线性表的特点是每个元素都有一个前驱和一个后继
7 取线性表的第i个元素的时间同i的大小有关
8 线性表只能用顺序存储结构实现
9 顺序存储方式的优点是存储密度大，且插入和删除运算效率高
10 链表是采用链式存储结构的线性表，进行插入和删除操作时，一般在链表中比在顺序存储结构中的效率高
三．填空题
1 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用[ ]存储结构。
2 线性表L=（a1,a2,…,an）用数组表示，若删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是[ ]
3 已知指针px指向单链表中数据域值为x的结点，指针py指向数据域值为y的新结点，若将结点y插入结点x之后，则需要执行以下语句：[ ]
4 在一个长度为n的顺序表中的第i个元素(0<=i<=n-1)之前插入一个新元素时，需向后移动[ ]个元素
5 对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为[ ]，在给定值为x的结点后插入一个新结点的时间复杂度为[ ]
6 链接存储的特点是利用[ ]来表示数据元素之间的逻辑关系。
7 对于双向链表，在两个结点之间插入一个新结点需修改的指针共为[ ]个，而对于单链表则为[ ]个。
8循环单链表的最大特点是：[ ]
9 带头结点的双循环链表L中只有一个元素结点的条件是：[ ]
10 在单链表L中，指针p所指结点有后继结点的条件是：[ ]
11 将一个单链表中的*p结点删除，可执行如下操作：
q=p->next; p->data=p->next->data;
p->next=[ ];
free(q);
第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 ）存储方式最节省时间。 AHA12GAGGAGAGGAFFFFAFAF
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链 表 C．双链表D．仅有尾指针的单循环链表 6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。 AHA12GAGGAGAGGAFFFFAFAF
A．单链表 B．双链表 C．单循环链 表 D．带头结点的双循环链表 8. 静态链表中指针表示的是（ BC ）. A．内存地址 B．数组下标 C．下一元素地址D．左、右孩子地址 9. 链表不具有的特点是（ C ） A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比 10. 下面的叙述不正确的是（ BC ） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 AHA12GAGGAGAGGAFFFFAFAF
第二章线性表练习题 一、选择题 1.线性表是具有n个的有限序列。 A、表元素 B、字符 C、数据元素 D、数据项 E、信息项 2.线性表的静态链表存储结构与顺序存储结构相比优点是。 A、所有的操作算法实现简单 B、便于随机存储 C、便于插入和删除 D、便于利用零散的存储器空间 3.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为。 A、O(log2n) B、O(1) C、O(n) D、O(n2) 4.（1）静态链表既有顺序存储的特点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关； （2）静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加；（3）静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是。 A、（1）、（2） B、（1） C、（1）、（2）、（3） D、（2） 6.在双向链表存储结构中，删除p所指的结点时须修改指针。 A、p－＞next－＞prior=p－＞prior; p－＞prior－＞next=p－＞next; B、p－＞next=p－＞next－＞next;p－＞next－＞prior=p; C、p－＞prior－＞next=p;p－＞prior=p－＞prior－＞prior; D、p－＞prior=p－＞next－＞next;p－＞next=p－＞prior－＞prior;
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.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。 A、 n b、2n－1 c、2n d、n－1 9.在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动个元素。 A、n－i B、n－i+1 C、n－i－1 D、i 10.线性表L=(a1，a2,……an)，下列说法正确的是。 A、每个元素有有一个直接前驱和一个直接后继 B、线性表中至少有一个元素 C、表中诸元素的排列必须是由小到大或由大到小。 D、除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。 11.对单链表表示法，以下说法错误的是。 A、数据域用于存储线性表的一个数据元素 B、指针域(或链域)用于存放一指向本结点所含数据元素的直接后继所在结点的指针 C、所有数据通过指针的链接而组织成单链表 D、NULL称为空指针，它不指向任何结点只起标志作用
第2章线性表习题解答
第2章习题 (2) 第2章习题 2.1若将顺序表中记录其长度的分量listlen改为指向最后一个元素的位置last，在实现各基本运算时需要做那些修改？ 【解】 //用线性表最后一个元素的下标last代替listLen实现顺序表 #define MAXLEN 100 typedef int elementType; typedef struct sllLast { elementType data[MAXLEN]; int last; }seqList; //初始化 void initialList(seqList &S)
{ https://www.doczj.com/doc/4a1948047.html,st=-1; } //求表长度 int listLength(seqList S) { return https://www.doczj.com/doc/4a1948047.html,st+1; } //按序号取元素 bool getElement(seqList S,int i,elementType &x) { if(i<1 || i>https://www.doczj.com/doc/4a1948047.html,st+1) //i为元素编号，有效范围在https://www.doczj.com/doc/4a1948047.html,st+1之间 return false; else { x=S.data[i-1];
return true; } } //查找元素x，成功：返回元素编号；失败：返回0 int listLocate(seqList S,elementType x) { int i; for(i=0;i<=https://www.doczj.com/doc/4a1948047.html,st;i++) { if(S.data[i]==x) return i+1; //找到，转换为元素编号输出 } return 0; } //插入元素 int listInsert(seqList &S,elementType x, int i)
习题二参考答案 一、选择题 1. 链式存储结构的最大优点是（ D ）。 A.便于随机存取 B.存储密度高 C.无需预分配空间 D.便于进行插入和删除操作 2. 假设在顺序表{a 0,a 1,……,a n －1}中，每一个数据元素所占的存储单元的数目为4，且第0个数据元素的存储地 址为100，则第7个数据元素的存储地址是（ D ）。 A. 106 B. 107 C.124 D.128 3. 在线性表中若经常要存取第i 个数据元素及其前趋，则宜采用（ A ）存储方式。 A.顺序表 B. 带头结点的单链表 C.不带头结点的单链表 D. 循环单链表 4. 在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜采用（ C ）存储方 式。 A. 顺序表 B. 用头指针标识的循环单链表 C. 用尾指针标识的循环单链表 D. 双向链表 5. 在一个单链表中的p 和q 两个结点之间插入一个新结点，假设新结点为S,则修改链的java 语句序列是（ D ）。 A. s.setNext(p); q.setNext(s); B. p.setNext(s.getNext()); s.setNext(p); C. q.setNext(s.getNext()); s.setNext(p); D. p.setNext(s); s.setNext(q); 6. 在一个含有n 个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是（ C ）。 A. O (1) B. O (log 2n) C. O (n) D. O (n2) 7. 要将一个顺序表{a 0,a 1,……,a n-1}中第i 个数据元素a i (0≤i ≤n-1)删除，需要移动（ B ）个数据元素。 A. i B. n-i-1 C. n-i D. n-i+1 8. 在带头结点的双向循环链表中的p 结点之后插入一个新结点s ，其修改链的java 语句序列是（ D ）。 A. p.setNext(s); s.setPrior(p); p.getNext().setPrior(s); s.setNext(p.getPrior()); B. p.setNext(s); p.getNext().setPrior(s); s.setPrior(p); s.setNext(p.getNext()); C. s.setPrior(p); s.setNext(p.getNext()); p.setNext(s); p.getNext().setPrior(s); D. s.setNext(p.getNext()); s.setPrior(p); p.getNext().setPrior(s); p.setNext(s); 9. 顺序表的存储密度是（ B ），而单链表的存储密度是（ A ）。 A ．小于1 B. 等于1 C. 大于1 D. 不能确定 10. 对于图2.29所示的单链表，下列表达式值为真的是（ D ）。 图2.29 单链表head 的存储结构图 A. head.getNext().getData()=='C' B. head.getData()=='B' C. P 1.getData()==’D ’ D. P 2.getNext()==null 二、填空题 1. 线性表是由n （n ≥0）个数据元素所构成的 有限序列 ，其中n 为数据元素的个数，称为线性表的 长度 ，
第二章线性表练习题 一、单选题 1．在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤ n+1)之前插入一个新元素时，需要从后向前依次后移( )个 元素。 A、n-i B、n-i+1 C、n-i-1 D、i 2．在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i ≤n+1)时，需要从前向后依次前移( )个元素。 A、n-i B、n-i+1 C、n-i-1 D、i 3．在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每 个元素的概率都相等）为( )。 A、n B、n/2 C、(n+1)/2 D、(n-1)/2 4．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 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; 5．在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行( )。 A、q->next = p->next ; p->next = q; B、p->next = q->next; q = p; C、q->next = p->next; p->next = q; D、p->next = q->next ; q->next = p; 6．在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行( )。 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; 7. 下面关于线性表的叙述错误的是（）。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 8、设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。
（A ）需经常修改L 中的结点值 （E ）需不断对L 进行删除插入 第二部分线性表 、选择题 1 ?关于顺序存储的叙述中，哪一条是不正确的 （B ） A. 存储密度大 B. 逻辑上相邻的结点物理上不必邻接 C. 可以通过计算直接确定第 i 个结点的位置 D. 插入、删除操作不方便 2.长度为n 的单链表连接在长度为 m 的单链表后的算法的时间复杂度为 （C ） A 0（ n ） B 0（1） C 0（m ） D 0（m+n ） 3 .在n 个结点的顺序表中，算法的时间复杂度是 0（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 ) 120 5 .已知一个顺序存储的线性表， 设每个结点需要占 m 个存储单元，若第一个结点的地址为 da , 则第i 个结点的地址为：（A ） 7 .链表是一种采用（ B ）存储结构存储的线性表。 （A ）顺序 （B ）链式 （C ）星式 （D ）网状 8 .线性表若采用链式存储结构时，要求内存中可用存储单兀的地址： （D ） （A ）必须是连续的 （B ）部分地址必须是连续的 （C ）一定是不连续的 （D ）连续或不连续都可以 9 .线性表L 在_ （ B ）情况下适用于使用链式结构实现。 A ） da+（i-1）*m B ） da+i*m 6.在具有n 个结点的单链表中，实现（ A ）遍历链表和求链表的第 i 个结点 C ）删除开始结点 C ） da-i*m D ） da+（i+1）*m A ）的操作，其算法的时间复杂度为 0（n ）。 B ）在地址为p 的结点之后插入一个结点 D ） 删除地址为p 的结点的后继结点
第二章线性表 1、描述一下三个概念的区别：头指针，头结点，首元结点。并给予图示。 2、对于有头结点的单链表，分别写出定位成功时，实现下列定位语句序列。(1)定位到第i 个结点a i ； (2)定位到第i 个结点的前驱a i-1； (3)定位到尾结点； (4)定位到尾结点的前驱。 3、已知L 是有表头结点的单链表，且P 结点既不是首元结点，也不是尾结点，试写出实现下列功能的语句序列。 (1)在P 结点后插入S 结点；(2)在P 结点前插入S 结点；(3)在表首插入S 结点；(4)在表尾插入S 结点 . p=head; p=head; j=0; while ( p && jnext; j++;} p=head; j=0; while ( p && j
4、设计算法：在顺序表中删除值为e 的元素，删除成功，返回1；否则，返回0。 5、设计一个算法，将一个带头节点的数据域依次为a 1，a 2，…，a n （n ≥3）的单链表的所有节点逆置，即第一个节点的数据域变为a n ，…，最后一个节点的数据域为a 1。（注意：先用自然语言描述算法基本思想，然后用类C++语言描述） int Sqlist
第二章线性表习题及答案 一、基础知识题 2.1 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。 答：始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。 链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。 头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。 2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑： 1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。 2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。 2.3 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素? 答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i 越接近n则所需移动的结点数越少。 2.4 为什么在单循环链表中设置尾指针比设置头指针更好? 答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和rear, 查找时间都是O(1)。 若用头指针来表示该链表，则查找终端结点的时间为O(n)。 2.5 在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少? 答：我们分别讨论三种链表的情况。 1. 单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。 2. 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。 3. 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。 2.6 下述算法的功能是什么? LinkList Demo(LinkList L){ // L 是无头结点单链表 ListNode *Q,*P; if(L&&L->next){ Q=L;L=L->next;P=L;
第2章线性表习题参考答案 习题二 一、选择题 1. 链式存储结构的最大优点是（ D ）。 A.便于随机存取 B.存储密度高 C.无需预分配空间 D.便于进行插入和删除操作 2. 假设在顺序表{a0,a1,……,an－1}中，每一个数据元素所占的存储单元的数目为4，且第0 个数据元素的存储地址为100，则第7个数据元素的存储地址是（ D ）。 A. 106 B. 107 C.124 D.128 3. 在线性表中若经常要存取第i个数据元素及其前趋，则宜采用（ A ）存储方式。 A.顺序表 B. 带头结点的单链表 C.不带头结点的单链表 D. 循环单链表 4. 在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜 采用（ C ）存储方式。 A. 顺序表 B. 用头指针标识的循环单链表 C. 用尾指针标识的循环单链表 D. 双向链表
5. 在一个单链表中的p和q两个结点之间插入一个新结点， 假设新结点为S,则修改链的 java语句序列是（ D ）。 A. s.setNext(p); q.setNext(s); B. p.setNext(s.getNext()); s.setNext(p); C. q.setNext(s.getNext()); s.setNext(p); D. p.setNext(s); s.setNext(q); 6. 在一个含有n个结点的有序单链表中插入一个 新结点，使单链表仍然保持有序的算法的 时间复杂度是（ C ）。 A. O(1) B. O(log2n) C. O(n) D. O(n2) 7. 要将一个顺序表{a0,a1,……,an-1}中第i个数据元素 ai(0≤i≤n-1)删除，需要移动（ B ） 个数据元素。 A. i B. n-i-1 C. n-i D. n-i+1 8. 在带头结点的双向循环链表中的p结点之后插入一个新结 点s，其修改链的java语句序 列是（ D ）。 A. p.setNext(s); s.setPrior(p); p.getNext().setPrior(s); s.setNext(p.getPrior()); B. p.setNext(s); p.getNext().setPrior(s); s.setPrior(p); s.setNext(p.getNext()); C. s.setPrior(p); s.setNext(p.getNext()); p.setNext(s); p.getNext().setPrior(s);
《数据结构》 第二章线性表习题 一、单项选择题 1. 线性表是________。 A．一个有限序列，可以为空B．一个有限序列，不可以为空 C．一个无限序列，可以为空D．一个无限序列，不可以为空 2. 在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动个元素。 A．n-i B．n-i+l C．n-i-1 D．i 3. 线性表采用链式存储时，其地址________。 A．必须是连续的B．一定是不连续的 C．部分地址必须是连续的D．连续与否均可以 4. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较________个元素结点。 A．n/2 B．n C．（n+1）/2 D．（n-1）/2 5. 在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是____。 A． p->next=s; s->prior=p; p->next->prior=s; s->next=p->next; B． s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; C． p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; D． s->prior=p; s->next=p->next; p->next->prior=s; p->next=s; 6. 设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为________。A．p->next=p->next->next; B．p=p->next; C．p=p->next->next; D．p->next=p; 7. 在一个长度为n的顺序表中向第i个元素(0< i
第二章测试试题 班级：学号：姓名：成绩： 一、选择题（每小题5分） 1.线性表是( A )。 A一个有限序列，可以为空；B一个有限序列，不能为空； C一个无限序列，可以为空；D一个无序序列，不能为空。 2.用链表表示线性表的优点是（C）。 A便于随机存取 B花费的存储空间较顺序存储少 C便于插入和删除 D数据元素的物理顺序与逻辑顺序相同 3.某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( D )存储方式最节省运算时间。 A单链表 B双链表 C单循环链表 D带头结点的双循环链表 4.带头结点的单链表head为空的判定条件是（B ）。 A.head==NULL; B.head->next==NULL; C.head->next==head; D.head!=NULL; 5.在一个单链表中，已知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; 二、填空题（每小题5分） 1．给定有n个结点的向量，建立一个单链表的时间复杂度_______。建立一个有序单链表的时间复杂度_______。 2．从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_____个结点。 3．在一个长度为n的线性表（采用顺序存储结构）中删除第i个元素(1≤i≤n)时，需向前移动____个元素。 4．当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_____存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_______存储结构为宜。5．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的个元素。 三、算法设计题（每小题25分） 1．设有一个用向量表示的线性表L，要求写出一个将该表逆置的过程，允许在原表的存储空间外再增加一个附加的工作单元。 2．已知两个整数集合A和B，它们的元素分别依元素值递增有序存放在两个单链表HA 和HB中，编写一个函数求出这两个集合的并集C，并要求集合C的链表的结点仍依元素值递增有序存放。（注意：并集不是归并）
第二章线性表 一、填空题 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））；
第2章习题 (1) 第2章习题 2.1若将顺序表中记录其长度的分量listlen改为指向最后一个元素的位置last，在实现各基本运算时需要做那些修改？ 【解】 //用线性表最后一个元素的下标last代替listLen实现顺序表 #define MAXLEN 100 typedef int elementType; typedef struct sllLast { elementType data[MAXLEN]; int last; }seqList; //初始化 void initialList(seqList &S) { https://www.doczj.com/doc/4a1948047.html,st=-1; } //求表长度 int listLength(seqList S) { return https://www.doczj.com/doc/4a1948047.html,st+1; } //按序号取元素 bool getElement(seqList S,int i,elementType &x) { if(i<1 || i>https://www.doczj.com/doc/4a1948047.html,st+1) //i为元素编号，有效范围在https://www.doczj.com/doc/4a1948047.html,st+1之间 return false; else { x=S.data[i-1]; return true; }
} //查找元素x，成功：返回元素编号；失败：返回0 int listLocate(seqList S,elementType x) { int i; for(i=0;i<=https://www.doczj.com/doc/4a1948047.html,st;i++) { if(S.data[i]==x) return i+1; //找到，转换为元素编号输出} return 0; } //插入元素 int listInsert(seqList &S,elementType x, int i) { int k; if(https://www.doczj.com/doc/4a1948047.html,st>MAXLEN-1) return 0; //表满，返回0 else if(i<1 || i>https://www.doczj.com/doc/4a1948047.html,st+2) return 1; //插入位置查处范围，返回1 else { for(k=https://www.doczj.com/doc/4a1948047.html,st;k>=i-1;k--) S.data[k+1]=S.data[k]; S.data[i-1]=x; https://www.doczj.com/doc/4a1948047.html,st++; return 2; } } //删除元素 int listDelete(seqList &S,int i) { int k; if(https://www.doczj.com/doc/4a1948047.html,st==-1) return 0; //空表，返回0 else if(i<1 || i>https://www.doczj.com/doc/4a1948047.html,st+1) return 1; //删除元素编号超出范围，返回1 else
一、选择题 1. D 2. B 3. B 4. B 5. B 6. B 7. D 8. B 9. C 10. B 11. C 12. C 13. B 14. D 15. A 16. B 17. B 18. C 19. A 20. C 21. D 22. A 23. A 24. A 二、填空题 1. 首元素其直接前驱结点的链域的值 2. HL→next =NULL； HL=HL→next 3. 有限、一对一 4. O(1) 随机存取 5. 表中一半表长和该元素在表中的位置 6. 必定不一定 7. O（1） O（n） 8. 前驱结点的地址 O（n） 9. n-i+1 n-i 10. s->left=p p->right 三、判断题 1. × 2. × 3. × 4. × 5. × 6. × 7. √ 8. × 9. × 10. × 11. × 四、简答题 1. 线性表为：（78，50，40，60，34，90） 2. (36, 12, 8, 50, 25, 5, 15) 3. 解答： 尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next和rear, 查找时间都是O(1)。
若用头指针来表示该链表，则查找终端结点的时间为O(n)。 五、编程题 1. 解答：由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法如下： int ListLength ( LinkList L ) { int len=0 ; ListNode *p; p=L; //设该表有头结点 while ( p->next ) { p=p->next; len++; } return len; } 2. int searchmin(linklist l) { int min; int *p; p=l; min=p->data; p=p->next; while (p->next< >nil) { if (min>p->data) min=p->data; p=p->next; } return min; } 3. int searchmax(linklist l) { int max; int *p; p=l; max=p->data; p=p->next; while (p->next< >nil) { if (max
数据结构与算法上机作业第二章线性表
一、选择题 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
线性表专题 一、选择题 1．关于顺序存储的叙述中,哪一条是不正确的( ) A.存储密度大 B.逻辑上相邻的结点物理上不必邻接 C.可以通过计算直接确定第i个结点的位置 D.插入、删除操作不方便 2．长度为n的单链表连接在长度为m的单链表后的算法的时间复杂度为( ) A O(n) B O(1) C O(m) D O(m+n) 3．在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是：( ) 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 个元素的地址是：( ) （A ）110 （ B ）108 （C ）100 （D ）120 5．已知一个顺序存储的线性表，设每个结点需要占m个存储单元，若第一个结点的地址为da，则第i个结点的地址为：( ) A）da+(i-1)*m B) da+i*m C) da-i*m D) da+(i+1)*m 6．在具有n个结点的单链表中，实现（）的操作，其算法的时间复杂度为O(n)。 A）遍历链表和求链表的第i个结点B）在地址为p的结点之后插入一个结点 C）删除开始结点D）删除地址为p的结点的后继结点 7．链表是一种采用（）存储结构存储的线性表。 （ A ）顺序（B ）链式（ C ）星式（D ）网状 8．线性表若采用链式存储结构时，要求内存中可用存储单元的地址：（） （ A ）必须是连续的（ B ）部分地址必须是连续的 （ C ）一定是不连续的（ D ）连续或不连续都可以 9．线性表Ｌ在（）情况下适用于使用链式结构实现。 （Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入 （Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂 10．在长度为n 的顺序表的第i (1≤i≤n+1) 个位置上插入一个元素，元素的移动次数为( )
第二章线性表 一．名词解释 1.线性结构 2.数据结构的顺序实现 3.顺序表 4.链表 5.数据结构的链接实现 6. 建表 7.字符串 8.串 9.顺序串 10.链串 二、填空题 1.为了便于讨论，有时将含n(n>=0)个结点的线性结构表示成(a1，a2,……a n)，其中每个a i代表一个______。a1称为______结点，a n称为______结点，i称为a i在线性表中的________或______。对任意一对相邻结点a i、a i┼1(1<=i