第2章测试题(1)
考研英语辅导书推荐-
一、选择题
1
．
从一个具有
n
个结点的单链表中查找值为<
/p>
x
的结点，
在查找成功情况下，
需平均比较
（
d
）
n
个节点，单链表。
如果
x
等于第一个元素的值。则
要比较
1
次
x
等于第二个元素的值，则要比较<
/p>
2
次
…
最不巧
：
x
值刚好等于第
n
< br>个元素，则要比较
x
次
所以总次数是
1+2+3+
……
+n-1+n=(n+1)*n/2
<
/p>
所以平均需要：
(n+1)/2
次。
顺序数组可以用折半查找，需要
log2
…为低…
N
次个结点。
A
．
n
B
．
n/2
C
．
（
n-1
）
/2
D
．
（
n+1
）
/2
2
．
（
a
）插入、删除速度快，但查找速度慢。
链表只需要修改前驱或者前驱与后继的指针就可以，
查找时链表需要顺序查找，
并且由于读
取指针耗费时间
A
．链表
B
．顺序表
C
．有序顺序表
D
．上述三项无法比较
3
．若希望从链表中快速确定一个结点的前驱，则链表最好采用（
c
）方式。
双链表在结点前驱后继查找上的时间复杂度是
O(1)
A
．单链表
B
．循环单链表
C
．双向链表
D
．任意
4
．在一个单链表中，若删除
p
所指结点
的后继结点，则执行（
d
）
。
p->next
指向
p
指针的后继结点，
p->next->next
指向后继结点的后继结点。
A
．
p->next=p->next
B
．
p=p->next->next
C
．
p=p->next;p->ne
xt=p->next->next;
D
．
< br>p->next=p->next->next
5
．带
头结点的单链表
head
为空的判定条件是（
< br>b
）
。
A
．
head==NULL
B
．
head->next==NULL
C
．
head->next==head
D
．
head!=NULL
6
．在循环双向链表的
p
所指结点之后插入
s
所指结点的操作是（
d
）
。
A
．
p->next=s;s->pr
ior=p;p->next->prior=s;s->next=p->next;
B
．
p->next=s;p->next->prior=
s;s->prior=p;s->next=p->next;
C
< br>．
s->prior=p;s->next=p->next;p->next=
s;p->next->prior=s;
D
．
s->prior=p;s->next=p->next;p->next->prior=s;p
->next=s;
7
．若某线性表最常用的操作是存取任一
指定序号的元素和在最后进行插入和删除运算，则
利用（
a
）存储方式最节省时间。
想要存取任一指定序号的元素，链表实现这个功能的代价很大
本来顺序表的弱点在于插入和删除元素，
但是题目要求只最后进
行插入和删除运算，
所有顺
序表是最好的选择！
A
．顺序表
B
．双向链表
C
．带头结点的双循环链表
D
．单循环链表
二、填空题
1
．对于采用顺序存储结构的线性表，当随机插入或删除一个数据元素时，平均约需移动表
中
一半
元素。
2
．当对一个线性表经常进行的是插入和删除操作时，采用
链式
存储结构为宜。
< br>因为采用链式结构存储线性表，
插入和删除操作需要从头结点起查找被插入或删除
结点的前
驱结点，并修改这些结点的指针域，查找过程平均移动指针域为表长的一半
3
．当对一个线性表经常进行的是存取操
作，而很少进行插入和删除操作时，最好采用
顺序
存储结构。
它的特点是逻辑关系上相
邻的两个元素在物理位置上也相邻，
因此可以随机存取表中任一元
素，它的存储位置可用一个简单，直观的公式来表示
4
．在一个长度为
n
的顺序存储结构的线性表
中，向第
i
个元素（
1
≦
i
≦
n+1
）之前插入一个
新元素时，需向后移动
n-i+1
个元素。
这道题，可以进行举例来验
证，比如要是在第一个元素前插入元素，需要移动
n
个元素。<
/p>
i=1
时，需要移动
< br>n
个，进行验证
5
．从长度是
n
的采用顺序存储结构的线性表中删除
第
i
个元素（
1
≦
i
≦
n
）
，需向前移动
n-i
个元素。
6
．
对于长度是
n
的顺序存储结构的线性
表，
插入或删除元素的时间复杂度为
0
（
n
）
。
7
．在具
有
n
个结点的有序单链表中插入一个新结点并仍然有序的时间复
杂度是
0
（
n
）
。
因为单链表保存的信息只有表头
如果要在特定位置插入一个节点
需要先从表头一路找到
那个节点
这个过程是
O(n)
的
8
．在双向链表中，每个结点共有两个指针域，
一个指向
前驱
结点，另一个则指
向
后继
结点。
三、判断题
1
．链表中的头结点仅起到标识的作用。
（
f
）
头结点的数据域还可以存储一些必要的数据，如表长。
2
．顺序存储结构的主要缺点是不利于插入和删除操作。
（
t
）
3
．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。
（
f
）
结点内部空间是连续的。
4
．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。
（
f
）
还有其他比较参数。如空间利用率，难易程度，存取快捷等。
5
．对任何数据结构链表存储结构一定优于顺序存储结构。
（
f
）
还有其他比较参数。如空间利用率，难易程度，存取快捷等。
6
．顺序存储方式只能用于存储线性结构。
（
f
）
也可用于树、二叉树等
7
．循环链表不是线性表。
（
f
）
8
．为了很方便地插入和删除数据，可以使用双向链表存放数据。
（
t
）
9
．线性表的特点是每个元素都有一个前驱和一个后继。
（
f
）
第一个结点无前驱，最后一个结点无后继。
< br>10
．取线性表的第
i
个元素的
时间与
i
的大小有关。
（
f
）
看线性表的存储机构，链表有关，顺序表无关。
四、应用题
1
．线性表有两种存储结构：一是顺序表，二是链式表。试问：
⑴如果有
n
个线性表同时并存，
并且
在处理过程中各表的长度会动态变化，
线性表的总数也
会自动地
改变。在此情况下，应选用哪种存储结构？为什么？
链表，理
由是链表能够高效的执行插入删除操作，适用于元素变化较多的情形
< br>⑵若线性表的总数基本稳定，
且很少进行插入和删除，
但
要求以最快的速度存取线性表中的
元素，那么应采用哪种存储结构？为什么？
顺序存储结构。顺序表可以随机存取，时间复杂度为
O
（
1
）
2
．线性表的顺序存储结构具有三个弱点：其一，在进行插入或
删除操作时，需移动大量元
素；
其二，
由于难以估计，
必须预先分配较大的空间，
往往使存储空间不能
得到充分的利用。
线性表的链式存储结构是否一定都能克服以上缺点，试讨论之。
链式存储结构一般说克服了顺序存储结构的三个弱点。首先，
插入、
删除不需移动元素，
只
修改指针，时间复杂度为
O(1)
；其次，不需要预先
分配空间，可根据需要动态申请空间；
其三，
表容量只受可用内
存空间的限制。
其缺点是因为指针增加了空间开销，
当空间不允
许
时，就不能克服顺序存储的缺点。
3
．线性表（
a
1
，
a
2
，
...
，
a
n
）用顺序映射表示时，
a
i
和
a
i+1
（
1<=i<
n
）的物理位置相邻吗？链
接表示时呢？
顺序映射时，
ai
与
ai+1
的物理位置相邻；链表表示时
ai
与
ai+1
的物理位置不要求相邻。
4
．试述头结点，首元结点，头指针这三个概念
的区别。
在线性表的链式存储结构中，
头指针指链表的指针，
若链表有头结点则是链表的头结点的指
针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、
方
便
而设立的，
放在第一元素结点之前，
其数据域一般无意义
（当然有些情况下也可存放链表的
长度、用
做监视哨等等）
，有头结点后，对在第一元素结点前插入结点和删除第一结点，其
操作与对其它结点的操作统一了。
而且无论链表是否为空，
头指针均不为空。
首元结点也就
是第一元素结点，
它是头结点后边的第一个结点。
5
．
在单链表和双向链表中，能否从当前结点出发访问到任何一个结点？
< br>在单链表中不能从任意结点
（若结点不是第一结点）
出发
访问到任何一个结点，
链表只能从
头指针开始，
访问到链表中每个结点。
在双链表中求前驱和后继都容易，
从任何一个结点向
前到第一结点，向后到最后结点，可以访问到任何一个结点。
6
．如何通过改链表的方法，把一个单向
链表变成一个与原来链接方向相反的单向链表？
设该链表带头
结点，
将头结点摘下，
并将其指针域置空，
然后从第一元素节点开始，直到最
后一个结点为止，依次前插入头结点的后面，则实
现了链表的逆置
五、算法设计题
1
．
已知单
链表
L
，写一个算法，删除其中的重复结点。
< br>
void delete(LinkList &L)
{LinkNode *p,*q,*s;
ElemType e;
for(p=L->next;p;p=p->next)
{e=p->data;
for(q=p->next;q;)
if(e==q->data)
{s=q; p->next=q->next; q=q->next;
free(s);
}
else q=q->next;
}
2
．
将数据
元素
x
插入到递增有序的顺序表的适当位置，使插入后的顺序表
仍为递增有序。
struct
list *p, *q, *s, *head;
p =
head;
while(p != NULL)
{
if(x > p->data)
{
q = p;
p = p->next;
}
else
{
s
= (struct list*)malloc(sizeof(struct list));
s->data = x;
q->next = s;
s->next = p;
}
}
3
．
假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两
个单链表归并为一个按元素值递减次序排列的单链表，
并要求利用原来
两个单链表的结
点存放归并后的单链表。
#include
#include
struct
list
{
int
data;
struct
list
*next;
};
struct
list
*head1,*head2,*p1,*p2,*q1,*q2;
void
main()
{
int
n=0;
void
unionlist();
p1=q1=(struct
list*)malloc(sizeof(struct
list));
printf(<
/p>
请输入第一个
链表
的信息
n
scanf(
while(p1->data!=0)
{
n=n+1;
if(n==1)
head1=q1;
else
q1->next=p1;
q1=p1;
p1=(struct
list*)malloc(sizeof(struct
list));
scanf(
}
q1->next=NULL;
n=0;
p2=q2=(struct
list*)malloc(sizeof(struct
list));
printf(<
/p>
请输入第二个链表的信息
n
scanf(
while(p2->data!=0)
{
n=n+1;
if(n==1)
head2=q2;
else
q2->next=p2;
q2=p2;
p2=(struct
list*)malloc(sizeof(struct
list));
scanf(
}
q2->next=NULL;
unionlist();