数据结构期末复习：第二章 线性表（选择题21道+判断题10道+程序填空3道）顺序表/链表/循环链表
数据结构 期末复习 第二章 线性表
一、选择题
1、设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为（C）。
A. n-i
B. n-i-1
C. n-i+1
D. i
2、设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（C）。
A. I B. n-i-1 C. n-i D. n-i+1
3、在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（B）。
A. q->next=NULL B. p->next=q->next
C. p=q->next D. p->next=q
4、在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（C）。
A. p->next= s; s->next= p->next B. p->next=s->next;
C. s->next=p->next; p->next=s; D. p=s->next
5、非空的单向循环链表的尾结点满足（A）（设头指针为head，指针p指向尾结点）。
A. p->next==head B. p==NULL
C. p== head D. p->next==NULL
6、链表不具有的特点是（B）。
A. 不必事先估计存储空间
B. 可随机访问任一元素
C. 逻辑上相邻的元素在物理位置上不一定相邻
D. 插入删除不需要移动元素
7、带头结点的链表为空的判断条件是（C）（设头指针为head）。
A. head->next==head
B. head ==NULL
C. head->next==NULL
D. head!=NULL
8、在一个长度为n的顺序表中为了删除第5个元素，由第6个元素开始从后到前依次移动了15个元素。则原顺序表的长度为（C）。
A. 19 B. 21 C. 20 D. 25
9、有关线性表的正确说法是（D）。
A. 线性表至少要求一个元素
B. 每个元素都有一个直接前驱和一个直接后继
C. 表中的元素必须按由小到大或由大到下排序
D. 除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继
10、向一个有127个元素的顺序表中插入一个新元素，并保持原来的顺序不变，平均要移动（A）个元素。
A. 63.5 B. 7
C. 63 D. 8
11、一个顺序表第一个元素的存储地址是90，每个元素的长度为2，则第6个元素的地址是（D）。
A. 106 B. 98
C. 102 D. 100
12、在一个不带头结点的单循环链表中，p、q分别指向表中第一个结点和尾结点，现要删除第一个结点，且p、q仍然分别指向新表中第一个结点和尾结点。可用的语句是p=p->next;和（A）。
A. q->next=p B. p->next=q
C. q=p D. p=q->next
13、在线性表的顺序结构中，以下说法正确的是（D）。
A. 逻辑上相邻的元素在物理位置上不一定相邻
B. 数据元素是不能随机访问的
C. 进行数据元素的插入、删除效率较高
D. 逻辑上相邻的元素在物理位置上也相邻
14、对链表, 以下叙述中正确的是（A）。
A. 不能随机访问任一结点
B. 插入删除元素的操作一定要要移动结点
C. 结点占用的存储空间是连续的
D. 可以通过下标对链表进行直接访问
15、设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为（A）。
A. n-i+1 B. i
C. n-i-1 D. n-i
16、在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行_____B____。
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;
17、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则以下操作哪个是正确的（D）。
A. s->next=p->next；p->next=s；
B. p->next=s->next；s->next=p；
C. p->next=s；s->next=q；
D. q->next=s；s->next=p；
18、在循环双链表的p所指结点之后插入s所指结点的操作是（D）。
A.p->right=s；s->left=p；p->right->left=s；s->right=p->right；
B. p->right=s；p->right->left=s；s->left=p；s->right=p->right；
C. s->left=p；s->right=p->right；p->right=s；p->right->left=s；
D. s->left=p；s->right=p->right；p->right->left=s；p->right=s；
19、若HL为一个不带表头结点的循环单链表的表头指针，若有HL->next= =HL条件存在，则该循环单链表是（B）。
A.空表 B.只有1个元素；
C.空表或只有一个元素 D.非空表
20、若HL为一个带表头结点的单链表的表头指针，则该表为空表的条件是（B）。
A.HL==NULL B.HL->next==NULL
C.HL->next==HL D.HL!=NULL
21、设头指针为head的非空的单向链表，指针p指向尾结点,则通过以下操作（D）可使其成为单向循环链表。
选择一项：
A. head = p; B. p=head;
C. p->next = NULL ; D. p->next=head;
二、判断题
1、 设有一个不带头结点的单向循环链表，结点的指针域为next，指针p指向尾结点，现要使p指向第一个结点，可用语句p=p->next;。（√）
2、 设有一个单向链表，结点的指针域为next，头指针为head，p指向尾结点，为了使该单向链表改为单向循环链表，可用语句p->next=head 。（√）
3、 设有一个单向循环链表，结点的指针域为next，头指针为head，指针p指向表中某结点，若逻辑表达式p->next==head;的结果为真，则p所指结点为尾结点。（√）
4、 要在一个单向链表中p所指向的结点之后插入一个s所指向的新结点，若链表中结点的指针域为next，可执行 p->next=s; s->next= p->next；的操作。（×）
5、 要在一个单向链表中删除p所指向的结点，已知q指向p所指结点的直接前驱结点，若链表中结点的指针域为next，则可执行q->next= p->next。（√）
6、 要在一个带头结点的单向循环链表中删除头结点，得到一个新的不带头结点的单向循环链表，若结点的指针域为next，头指针为head，尾指针为p，则可执行head=head-> next; p->next=head；。（√）
7、 设有一个单向循环链表，头指针为head，链表中结点的指针域为next，p指向尾结点的直接前驱结点，若要删除尾结点，得到一个新的单向循环链表，可执行操作p->next=head；。（√）
8、 设有一个长度为40的顺序表，要删除第8个元素需移动元素的个数为3。（×）
9、 线性表用关键字的顺序方式存储，可以用二分法排序。（×）
10、线性表用顺序方式存储可以随机访问。（√）
三、程序填空
1、设线性表以不带头结点的单向链表存储，链表头指针为head，以下程序的功能是输出链表中各结点中的数据域data,完成程序中空格部分。
#define NULL 0
void main（）
{ NODE *head ,*p ;
p=head; /*p为工作指针*/
do
{printf(“%d\n”, [ 1 ];
[ 2 ];
}while [ 3 ]；
答案：（1）p >data（2）p=p >next（3）p!=NULL
2、设有一个头指针为head的不带头结点单向链表，p、q是指向链表中结点类型的指针变量，p指向链表中结点a, （设链表中没有结点的数据域与结点a的数据域相同）,写出相关语句
(1)使该单向链表成为单向循环链表
(2)插入结点s,使它成为a结点的直接前驱
q=p; x=p->data;
while（[ 4 ]）q=q->next;
q->next=head;
q=p; p=p->next;
while(p->data!=x)
{ q=p;
[ 5 ]
}
s->next=p;
[ 6 ]
答案：（4）q >next!=NULL（5）p=p >next（6）q >next=s
3、设有一个不带头结点的单向链表，头指针为head，p、prep是指向结点类型的指针，该链表在输入信息时不慎把相邻两个结点的信息重复输入，以下程序段是在该单向链表中查找这相邻两个结点，把该结点的数据域data打印出来，并把其中之一从链表中删除，填写程序中的空格。
prep=head;
p=prep->next;
while(p->data!=prep->data)
{
prep=p;
[ 7 ];
}
printf(“min=%d”, [ 8 ]);
prep->next= [ 9 ];
答案：（7）p=p->next;（8）p->data或prep->data（9）p->next