最新数据结构第二章试题
第2章线性表
一、选择题
1. 链表不具备的特点是（）。
A．可随机访问任意结点 B. 插入删除不需要移动元素
C. 不必事先估计存储空间
D. 所需空间与其长度成正比
2. 不带头结点的单链表head为空的判定条件是（）。
A.head==NULL
B. head->next==NULL
C.head->next==head
D.head!=NULL
3.带头结点的单链表head为空的判定条件是（）。
A.head==NULL
B. head->next==NULL
C.head->next==head
D.head!=NULL
4．带头结点的双循环链表L为空表的条件是（）。
A．L==NULL B．L->next->==NULL C．L->prior==NULL D.L->next==L
5.非空的循环链表head的尾结点（由P所指向）满足（）。
A．p->next==NULL B．p==NULL C．p->next==head D.p==head
6.在循环双链表的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->right->next=s;
D. s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s;
7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（）存储方式最节省运算时间。
A．单链表 B．给出表头指针的单循环链表
C．双链表 D. 带头结点的双循环链表
8.某线性表最常用的操作是在最后一个结点之后插入一个节点或删除第一个结点，故采用（）存储方式最节省运算时间。
A．单链表 B．仅有头结点的单循环链表
C．双链表 D. 仅有尾指针的单循环链表
9.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是（）。
A．单链表 B．静态链表 C．线性链表 D. 顺序存储结构
10.如果最常用的操作是取第i个结点及前驱，则采用（）存储方式最节省时间。
A．单链表 B．双链表 C.单循环链表 D.顺序表
11.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（）。
A．O(1) B．O(n) C．O(n*n) D. O(nlog2n)
12.在一个长度为n(n>1)的单链表上，设有头和尾两个指针，执行()操作与链表的长度有关。A．删除单链表中的第一个元素 B．删除单链表中的最后一个元素
C. 在单链表第一个元素前插入一个新元素
D.在单链表最后一个元素后插入一个新元素
13.设线性表有n个元素，以下算法中，()在顺序表上实现比在链表上实现效率更高。A．输出第i(0<=i<=n-1)个元素值 B．交换第0个元素与第1个元素的值
C. 顺序输出这n个元素的值
D.输出与给定值x相等的元素在线性表中的序号
14.设线性表有2n个元素，算法()，在单链表上实现比在顺序表上实现效率更高。
A．删除所有值为x的元素 B．在最后一个元素的后面插入一个新元素
C. 顺序输出前k个元素
D.交换第i个元素和第2n-i-1个元素的值(i=0,1,…,n-1)
15.与单链表相比，双链表的优点之一是()。
A．插入、删除操作更简单 B．可以进行随机访问
C. 可以省略表头指针或表尾指针
D.顺序访问相临结点更灵活
16.如果对线性表的运算只有4种，即删除第一个元素，删除最后一个元素，在第一个元素
前面插入新元素，在最后一个元素的后面插入新元素，则最好使用().
A．只有表尾指针没有表头指针的循环单链表
B．只有表尾指针没有表头指针的非循环双链表
C．只有表头指针没有表尾指针的循环双链表
D．既有表头指针也有表尾指针的循环单链表
17.如果对线性表的运算只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，
则最好使用()。
A．只有表头指针没有表尾指针的循环单链表 B．非循环双链表
C. 只有表尾指针没有表头指针的循环单链表
D. 循环双链表
18.设两个长度为n的单链表，结点类型相同。若以h1为表头指针的链表是非循环的，以
h2为表头指针的链表是循环的，则()。
A．对于两个链表来说，删除第一个结点的操作，其时间复杂度都是O(1)
B．对于两个链表来说，删除最后一个结点的操作，其时间复杂度都是O(n)
C.循环链表要比非循环链表占用更多的内存空间
D.h1和h2是不同类型的变量
19.在长度为n的()上，删除第一个结点，其算法的时间复杂度为O(n)。
A．只有表头指针的不带表头结点的循环单链表
B．只有表尾指针的不带表头结点的循环单链表
C. 只有表尾指针的带表头结点的循环单链表
D. 只有表头指针的带表头结点的循环单链表
二、填空题
1.向一个长度为n的顺序表中的第i个元素(0<=i<=n-1)之前插入一个元素时，需向后移动
____个元素。
2.在一个长度为n的顺序表中删除第i个元素(0<=i<=n-1)时，需向前移动____个元素。
3.在单链表中设置头结点的作用____。
4.在单链表中，要删除某一指定的结点，必须找到该结点的____结点。
5.访问单链表中的结点，必须沿着____依次进行。
6.在双链表中，每个结点有两个指针域，一个指向____，另一个指向____。
7.在____链表上，删除最后一个结点其算法的时间复杂度为O(1)。
8.在非循环的____链表中，可以用表尾指针代替表头指针。
9.在一个单链表中的p所指结点之前插入一个s所指结点时，可执行如下操作：
(1)s->next=____;
(2)p->next=s;
(3)t=p->data;
(4)p->data=____;
(5)s->data=____;
10.在一个单链表中删除p所指结点时，应执行以下操作:
Q=p->next;
p->data=p->next->data;
p->next=____;
free(q);
11.在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=____和p->next____的操作。
12.对于一个具有n个结点的单链表，在*p结点后插入一个新结点的时间复杂度是____;在给定值为x的结点后插入一个新结点的时间复杂度是____。
三、简答题
1.简述顺序表和链表存储方式的特点。
2.若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用何种存储结构，为什么？
3.对链表设置头结点的作用是什么？
4.在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头结点指针，能否将结点*p从相应的链表中删去？若可以，其时间复杂度各为多少？
5.下列说法哪些是错误的？
(1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。
(2)静态链表中能容纳的元素个数的最大数在定义时就确定了，以后不能增加。
(3)静态链表与动态链表在元素的插入、删除上类似，不需要元素的移动。
四、算法设计题
1.已知一个顺序表L，其中的元素按值非递减有序排列，设计一个算法插入一个元素x后保持该顺序表仍按递减有序排列。要求算法的空间复杂度为O(1)。
2.设计一个算法从顺序表L中删除所有值为x的元素。要求算法的空间复杂度为O(1)。
3.设计一个算法从一给定的顺序表L中删除元素值在x到y(x<=y)之间的所有元素，要求以较高的效率来实现。要求算法的空间复杂度为O(1)。
第1 章习题参考答案:
1-6 一个电路含有一个2 输入与门（AND2），其每个输入/输出端上都
连接了一个反相器；画出该电路的逻辑图，写出其真值表；能否将该电路简化？
解：电路图和真值表如下：
由真值表可以看出，该电路与一个2 输入或门（OR2）相同。
第2 章习题参考答案:
2.2 将下面的八进制数转换成二进制数和十六进制数。
(a) 12348=1 010 011 1002=29C16
(b) 1746378=1 111 100 110 011 1112=F99F16
(c) 3655178=11 110 101 101 001 1112=1EB4F16
(d) 25353218=10 101 011 101 011 010 0012=ABAD116
(e) 7436.118=111 100 011 110.001 0012=F1E.2416
(f) 45316.74748=100 101 011 001 110.111 100 111 12=4ACE.F2C16
2.3 将下面的十六进制数转换为二进制数和八进制数。
(a) 102316=1 0000 0010 00112=100438
(b) 7E6A16=111 1110 0110 10102=771528