55．单链表中，增加一个头结点的目的是为了( ）。
A．使单链表至少有一个结点 B．标识表结点中首结点的位置 C．方便运算的实现 D．说明单链表是线性表的链式存储
56．对于双向循环链表,在p指针所指的结点之后插入s指针所指结点的操作应为（ ）。 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 ; 57．对于一个线性表既要求能够进行较快速的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用( )。
A. 顺序存储方式 B. 链式存储方式 C. 散列存储方式 D. 以上均可以 58．在单链表指针为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; 59．线性表的顺序存储结构是一种（ ）。
A. 随机存取的存储结构 B. 顺序存取的存储结构 C. 索引存取的存储结构 D. Hash存取的存储结构 60．顺序表是线性表的（B ）
A、链式存储结构 B、顺序存储结构 C、索引存储结构 D、散列存储结构 61．带头结点的单链表head为空的条件是（ B ） A、head=NULL B、head->next=NULL C、head->next=head D、head!=NULL 62．链表不具有的特点是（ B ）
A．插入、删除不需要移动元素 B．可随机访问任一元素
C．不必事先估计存储空间 D．所需空间与线性长度成正比 63．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表
64．下面关于线性表的叙述中，错误的是哪一个？（ B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。
二、填空题
1．设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中_______个数据元素；删除第i个位置上的数据元素需要移动表中_______个元素。n+1-i，n-i
2. 设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为_________________________________________________________（设结点中的两个指针域分别为llink和rlink）。p>llink->rlink=p->rlink; p->rlink->llink=p->rlink
6
3．设指针变量p指向单链表中结点A，则删除结点A的语句序列为：
q=p->next；p->data=q->data；p->next=___________；feee(q)；q->next 4．在带头结点的单链表L中, 第一个元素所对应的结点的指针表达式是_____________。L->next
5．在双向循环链表中，在结点*Ｐ之前插入结点*Ｓ的语句序列是：
S-> prior = P-> prior ; S->next=P; P->prior=S; __________________。S-> prior->next=S;
6．在有n个元素的链队列中，入队和出队操作的时间复杂度分别为_____O(1)____和______O(1)____。
7．在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向_ _和_ 。前驱、后继
8．在循环队列中，存储空间为0~n-1。设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front，队满标志为_ ______。_(rear+1)%n=front
9．下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。
typedef struct node {int data; struct node *next;} lklist; void lklistcreate(_____________ *&head ) {
for (i=1;i<=n;i++) {
p=(lklist
*)malloc(sizeof(lklist));scanf(“%d”,&(p->data));p->next=0;
if(i==1)head=q=p;else {q->next=p;____________;} } }
lklist，q=p
10．设指针p指向单链表中结点A，指针s指向被插入的结点X，则在结点A的前面插入结点X时的操作序列为：
1) s->next=___________；2) p->next=s；3) t=p->data； 4) p->data=___________；5) s->data=t；p->next，s->data
11．设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列：s->next=p->next; _________________;。p->next=s
12．设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，则指针变量p和指针变量head之间的关系是p=_________和head=__________（设结点中的两个指针域分别为llink和rlink）。head->rlink，p->llink
13．设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为_________=p；s->right=p->right；__________=s； p->right->left=s；（设结点中的两个指针域分别为left和right）。s->left=p，p->right
14．设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X，则进行插入操作的语句序列为__________________________（设结点的指针域为
7
next）。s->next=p->next; p->next=s
15．在一个单链表HL 中，若要向表头插入一个由指针p指向的结点，则应执行语句： 。p->next=HL; HL=p;
16．在采用独立结点构成的双向链表中，设p和q 分别是具有Dnode * 类型的指针变量。若双向链表中p结点之后插入一个q结点，其操作步骤为：
； ； ； ； q->right=p->right;
if (p->right) p->right->left=q; q->left=p; p->right=q; 17．对于一个顺序存储的线性表，在表头插入元素的时间复杂度为____________,在表尾插入元素的时间复杂度为________________。O(n) O(1)
18．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动___n-i+1_____个元素。
19．设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，指针s指向双链表中的一个结点（该结点既非头结点，也非尾结点），则删除s指针所指向结点的操作为“s->tl->r1=s->r1；”和“__s->rl->tl=s->tl_______”。
20．设有指针head指向不带表头结点的单链表，用next表示结点的一个链域，指针p指向与链表中结点同类型的一个新结点。现要将指针p指向的结点插入表中，使之成为第一个结点，则所需的操作为“p→next=head；”和“__head=p________”。
21．单链表中逻辑上相邻的两个元素在物理位置上_____不一定_____相邻。 22．在一个长度为n的数组中删除第i个元素（1≤i≤n）时，需要向前移动的元素的个数是_____n-i_____。
23．在顺序表上读表元算法的时间复杂度为___O（1）____。
24．双链表中前驱指针为prior，后继指针为next，在指针P所指结点前插入指针S所指的结点，需执行下列语句：
S→next=P;S→prior=P→prior;P→prior=S;__p->prior->next=s_____;
next 25．设某非空双链表，其结点形式为prior data q所，若要删除指针 指向的结点，则需执行下述语句段：
q->prior->next＝q->next; _q->next->prionr=p->prior____。 26．对长度为n的顺序表执行删除操作，其删除算法在最坏情况下的时间复杂性为__O（n）。
27．在一个长度为n的顺序表中插入一个元素，最少需要移动 元素，最多需要移动 元素，0，n; 28．双向循环链表的优点是 既可以方便的找到后继结点又可以方便的找到前驱结点。
29．在一个长度为n的顺序表中删除一个元素，最少需移动 个元素，最多需移动________个元素。0 n－1
30．在长度为n的顺序表中插入第i个元素（假设i值可操作），要将元素从第
8
个到第 个元素向 （前或后）移动。 n 、 i+1 、 后 31．将指向单链表中的某个结点的指针p移动到该结点的后继结点表示为 。 p=p->next
32．在线性表的单链接存储结构中，每个结点包含有两个域，一个叫 域，另一个叫 域。元素值、指针
33．在下面数组a中链接存储着一个线性表，表头指针为a[0].next，则该线性表为 。
a 012345678 data605642387425
next4376201
( 38 , 56 , 25 , 60 , 42 , 74 )
34．对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为 ，在表尾插入元素的时间复杂度为 。O(n)、O(1)
35．对于一个长度为n的单链接存储的线性表，在表头插入元素的时间复杂度为 ，在表尾插入元素的时间复杂度为 。O (1)、O(n)
36．在线性表的顺序存储中，若一个元素的下标为i，则它的前驱元素的下标为 ，后继元素的下标为 。i-1、i+1
37．在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为 ，若假定p为一个数组a中的下标，则其后继结点的下标为 。p->next 、a[p].next
38．在循环单链表中，最后一个结点的指针指向 结点。表头
39．在双向链表中每个结点包含有两个指针域，一个指向其 结点，另一个指向其 结点。前驱、后继
40．在循环双向链表中表头结点的左指针域指向 结点，最后一个结点的右指针域指向 结点。表尾、表头
41．在以HL为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为 和 。HL->next = = NULL 、HL->next = = HL
42．队列的插入操作在 进行，删除操作在 进行。队尾、队首 43．栈又称为 表，队列又称为 表。后进先出(LIFO)、先进先出(FIFO)
44．向一个顺序栈插入一个元素时，首先使 后移一个位置，然后把待插入元素 到这个位置上。栈顶指针、存储
45．从一个栈中删除元素时，首先取出 ，然后再前移一位 。栈顶元素、栈顶指针
46．在一个循环顺序队列Q中，判断队空的条件为 ，判断队满的条件为 。front = = rear 、(rear+1)%QueueMaxSize = = front
47．在一个顺序栈中，若栈顶指针等于 ，则为空栈；若栈顶指针等于 ，则为满栈。–1 、StackMaxSize-1
48．在一个链栈中，若栈顶指针等于NULL，则为 ；在一个链队中，若队首指针与队尾指针的值相同，则表示该队列为 或该队列为 。栈
9
空、空队、队列只有一个元素
49．在下面的数组a中链接存储着一个线性表，表头指针为a[o].next，则该线性表为_________________________________________________。
a 0 1 2 3 4 5 6 7 8 dat
60 56 42 38 74 25 a
4 3 7 6 2 0 1 next
（38，56，25，60，42，74）；
50．在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为________________和____________________。HL→next =NULL； HL=HL→next； 51．用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的___________，该循环队列的最大长度为__________。前一个位置； n-1； 52．当堆栈采用顺序存储结构时，栈顶元素的值可用———————表示；当堆栈采用链接存储结构时，栈顶元素的值可用_______________表示。S.stack [S.top]; HS→data;
53．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:_______； ______;【华中理工大学 2000 一.4（2分）】py->next=px->next; px->next=py
54．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。【北京工商大学 2001 二.4（4分）】n-i+1 55．在单链表中设置头结点的作用是________。【哈尔滨工业大学 2000 二.1（1分）】有头结点后，插入元素和删除元素的算法统一了，不再需要判断是否在第一个元素之前插入和删除第一个元素。另外，不论链表是否为空，链表指针不变。
56．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为________。【哈尔滨工业大学 2001 一.1（2分）】 O(1)，O(n)
57．在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_______、_______、_______、________。【中国矿业大学 2000 一.1（3分）】f->next=p->next; f->prior=p; p->next->prior=f; p->next=f;
58．顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过________表示元素之间的关系的。【北京理工大学 2001 七.2 （2分）】物理上相邻 指针
59．在单链表L中，指针p所指结点有后继结点的条件是：________ 【合肥工业大学 2001 三.3 （2分）】p->next!=null
60. 单链表与多重链表的区别是 。链域数目不同
三、判断题
10