数据结构习题练习（三）-链表(线性表、栈和队列)-删除链表中大于x小于y的元素/单链表的就地逆置
单项选择题
- 不带头结点的单链表 head 为空的判定条件是____。
A. head= =NULL B. head—＞next= =NULL
C. head—＞next= =head D. head!=NULL - 带头结点的单链表 head 为空的判定条件是____。
A. head= =NULL B. head—＞next= =NULL
C. head—＞next= =head D. head!=NULL - 非空的循环单链表 head 的尾结点（由 p 所指向）满足____。
A. p—＞next= =NULL B. p= =NULL
C. p—＞next= =head D. p= =head - 在循环双链表的 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; - 在一个单链表中，已知 q 所指结点是 p 所指结点的前驱结点，若在 q 和 p 之间插入 s 结点，则执行____。
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; - 在一个单链表中，若 p 所指结点不是最后结点，在 p 之后插入 s 所指结点，则执行____。
A. s—＞next=p; p—＞next=s;
B. s—＞next=p—＞next; p—＞next=s;
C. s—＞next=p—＞next; p=s;
D. p—＞next=s; s—＞next=p; - 在一个单链表中，若删除 p 所指结点的后续结点，则执行____。
A. p—＞next= p—＞next—＞next；
B. p= p—＞next; p—＞next= p—＞next—＞next；
C. p—＞next= p—＞next;
D. p= p—＞next—＞next； - 从一个具有 n 个结点的单链表中查找其值等于 x 结点时，在查找成功的情况下，需平均比较____个结点。
A. n B. n/2 C. (n-1)/2 D. (n+1)/2 - 在一个具有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是____。
A. O（1） B.O（n） C. O (n2) D.O (nlog2n) - 给定有 n 个元素的向量，建立一个有序单链表的时间复杂度是____。
A. O（1） B.O（n） C. O (n2) D.O (nlog2n) - 向一个栈顶指针为 HS 的链栈中插入一个 s 所指结点时，则执行____。(不带空的头结点)
A. HS—＞next=s;
B. s—＞next= HS—＞next; HS—＞next=s;
C. s—＞next= HS; HS=s;
D. s—＞next= HS; HS= HS—＞next; - 从一个栈顶指针为 HS 的链栈中删除一个结点时，用 x 保存被删结点的值，则执行____。(不带空的头结点)
A. x=HS; HS= HS—＞next;
B. x=HS—＞data;
C. HS= HS—＞next; x=HS—＞data;
D. x=HS—＞data; HS= HS—＞next;
填空题
- 单链表是____的链接存储表示。
- 可以使用____表示树形结构。
- 在双链表中，每个结点有两个指针域，一个指向____，另一个指向____。
- 在一个单链表中的 p 所指结点之前插入一个 s 所指结点时，可执行如下操作：
⑴ s—＞next=____;
⑵ p—＞next=s;
⑶ t=p—＞data;
⑷ p—＞data=____;
⑸ s—＞data=____; - 在一个单链表中删除 p 所指结点时，应执行以下操作：
q= p—＞next;
p—＞data= p—＞next—＞data;
p—＞next=____;
free(q); - 带有一个头结点的单链表 head 为空的条件是____。
- 在一个单链表中 p 所指结点之后插入一个 s 所指结点时，应执行 s—＞next=____和 p—＞ next=____的操作。
- 非空的循环单链表 head 的尾结点（由 p 所指向），满足条件____。
- 在栈顶指针为 HS 的链栈中，判定栈空的条件是____。
- 对于一个具有 n 个结点的单链表，在已知 p 所指结点后插入一个新结点的时间复杂度是____；在给定值为 x 的结点后插入一个新结点的时间复杂度是____。
算法设计题
- 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表中所有大于 x 且小于 y 的元素（若表中存在这样的元素）同时释放被删除结点空间。
- 试写一算法，实现单链表的就地逆置。
- 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。
单项选择题分析
- 不带头结点的单链表 head 为空的判定条件是____。
A. head= =NULL B. head—＞next= =NULL
C. head—＞next= =head D. head!=NULL
不带头结点的单链表head保存的，是链表中第一个结点地址，
若链表为空，则第一个结点为NULL，即head==NULL
. - 带头结点的单链表 head 为空的判定条件是____。
A. head= =NULL B. head—＞next= =NULL
C. head—＞next= =head D. head!=NULL
不带头结点的单链表head保存的，是链表的信息，或为空仅作指示
head-next是链表中第一个结点地址，
若链表为空，则第一个结点为NULL，即head-next==NULL
. - 非空的循环单链表 head 的尾结点（由 p 所指向）满足____。
A. p—＞next= =NULL B. p= =NULL
C. p—＞next= =head D. p= =head
循环链表中，最后一个结点p的next指向头结点，
即p->next == head
. - 在循环双链表的 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;
在插入删除操作时，如果只知道链表中的一个结点地址，与一个待插入结点地址，
需要先对不知道的结点进行处理，防止后续无法找到该结点位置。
例如，本题中，已知循环双链表中的p结点，与待插入的s结点，
在修改p->right结点前，要先修改p->right结点的前驱与s结点的后继，
因为两者都与p->right结点相关，一旦p->right被修改，已知条件中无法再推出该结点，链表会断裂，
即，s->right=p->right与p->right->left的位置必须位于p->right=s的前面，
答案D的操作是：
1.修改s的前驱与后继，2.再修改p->next结点的前驱，3.再修改p结点的后继。
. - 在一个单链表中，已知 q 所指结点是 p 所指结点的前驱结点，若在 q 和 p 之间插入 s 结点，则执行____。
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;
与前一题不同，这题给出了链表中两个结点，要求在其间插入新结点。
那就是送分题了，因为是单链表，所以直接修改后继即可，顺序不论。
. - 在一个单链表中，若 p 所指结点不是最后结点，在 p 之后插入 s 所指结点，则执行____。
A. s—＞next=p; p—＞next=s;
B. s—＞next=p—＞next; p—＞next=s;
C. s—＞next=p—＞next; p=s;
D. p—＞next=s; s—＞next=p;
这题与第四题类似，需要先将涉及未知结点的操作执行，
即先修改s的后继为p的后继，再修改p的后继为s。
. - 在一个单链表中，若删除 p 所指结点的后续结点，则执行____。
A. p—＞next= p—＞next—＞next；
B. p= p—＞next; p—＞next= p—＞next—＞next；
C. p—＞next= p—＞next;
D. p= p—＞next—＞next；
这题简单了，删除p->next，就是把p的后继改成p->next的后继，
. - 从一个具有 n 个结点的单链表中查找其值等于 x 结点时，在查找成功的情况下，需平均比较____个结点。
A. n B. n/2 C. (n-1)/2 D. (n+1)/2
最好情况是第1个结点就找到，最差情况是第n个结点找到，
因此平均为两者相加除二。
. - 在一个具有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是____。
A. O（1） B.O（n） C. O (n2) D.O (nlog2n)
本题的插入新结点，就是查找结点插入位置，就是上题的结果
但因为时间复杂度一般不保留系数，因此为O(n)。
. - 给定有 n 个元素的向量，建立一个有序单链表的时间复杂度是____。
A. O（1） B.O（n） C. O (n2) D.O (nlog2n)
这题我觉得D也是可以的，
如果是先排序，再建立链表，那么就是排序时间复杂度+建立链表时间复杂度，
建立链表时间复杂度是n，肯定比排序时间复杂度的规模小，可省略，
因此就是一个排序算法的时间复杂度了，
用冒泡排序的话，那就是O(n2)，用快速排序的话，就是O(nlog2n)，
但也有一种可能，他是先找到最小的，再逐个加入链表，
就是将链表的建立加入到冒泡排序中，
那就是O(n2)了。
. - 向一个栈顶指针为 HS 的链栈中插入一个 s 所指结点时，则执行____。(不带空的头结点)
A. HS—＞next=s;
B. s—＞next= HS—＞next; HS—＞next=s;
C. s—＞next= HS; HS=s;
D. s—＞next= HS; HS= HS—＞next;
栈的推入与退出都是在栈顶执行，
链栈中的结点包括了next后继与data数据，
因此插入s结点时，先将s的后继修改为栈顶指针，再将栈顶指向s。
. - 从一个栈顶指针为 HS 的链栈中删除一个结点时，用 x 保存被删结点的值，则执行____。(不带空的头结点)
A. x=HS; HS= HS—＞next;
B. x=HS—＞data;
C. HS= HS—＞next; x=HS—＞data;
D. x=HS—＞data; HS= HS—＞next;
先处理与待删除结点相关的操作，再删除结点，
因此，先保存栈顶结点数据，再将栈顶结点退出。
填空题分析
- 单链表是线性表的链接存储表示。
记下来吧。
. - 可以使用双链表表示树形结构。
记下来吧。
我一直觉得链表这种线性结构不能表示树这种非线性结构，这题令我迷惑。
. - 在双链表中，每个结点有两个指针域，一个指向直接前驱，另一个指向直接后继。
是双链表的结构体定义。
. - 在一个单链表中的 p 所指结点之前插入一个 s 所指结点时，可执行如下操作：
⑴ s—＞next=p->next;
⑵ p—＞next=s;
⑶ t=p—＞data;
⑷ p—＞data=s->data;
⑸ s—＞data=t;
这题的解法是将s插入到p后面，然后交换s与p的data值，
还是很合情合理的，毕竟只给出单链表一个结点，没有指针能指向该结点前驱，
所以通过交换结点值来达到类似效果。
. - 在一个单链表中删除 p 所指结点时，应执行以下操作：
q= p—＞next;
p—＞data= p—＞next—＞data;
p—＞next=p->next->next;
free(q);
这个与上题一样，为了不让链表断裂，p的地址不能变化，
因此只能交换p与p->next的data值，然后将p->next删除了。
. - 带有一个头结点的单链表 head 为空的条件是head->next==NULL。
带头结点的单链表中，头结点的后继结点才是链表第一个结点。
. - 在一个单链表中 p 所指结点之后插入一个 s 所指结点时，应执行 s—＞next=p->next和 p—＞ next=s的操作。
与选择题第六题一样。
. - 非空的循环单链表 head 的尾结点（由 p 所指向），满足条件p->next==head。
循环单链表，在单链表的基础上，将尾结点的后继从NULL改成了head。
但我觉得空链表时的p->next==NULL==head，也满足条件，就很奇怪，
还有一点，如果链表为空，那p->next的访问就会报错，因为p为空，就没有p->next。
这题答案我觉得用单链表的判断就可以了，
即有头结点的head->next != NULL，
无头结点head != NULL。
. - 在栈顶指针为 HS 的链栈中，判定栈空的条件是HS==NULL。
栈空时栈顶指针为空，栈没有类似头指针的东西（当然也可以设置出来，但这题都这样问了不是）
. - 对于一个具有 n 个结点的单链表，在已知 p 所指结点后插入一个新结点的时间复杂度是O(1)；在给定值为 x 的结点后插入一个新结点的时间复杂度是O(n)。
链表结点的插入只要固定数量的语句就行了，
但查找到该结点的插入位置会需要数量不等的时间，是选择题第八题的答案。
算法设计题第一、二题分析
1.已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表中所有大于 x 且小于 y 的元素（若表中存在这样的元素）同时释放被删除结点空间。
void removeRangeInLink(lNode *head, int x, int y) { //移除链表中>x且<y的值。
lNode *node = head->next;
while (node) {
if (node->data >= y) return;
else if (node->data > x) deleteLNode(node);
else node = node->next;
}
}2.试写一算法，实现单链表的就地逆置。
int getLinkNumber(lNode *head) { //用于计算链表中结点个数，给逆置函数使用
lNode *node = head->next;
int number = 0;
while (node) {
number++;
node = node->next;
}
return number;
}
void reverseLink(lNode *head) { //逆置函数，双重循环，将第i个结点与第num-i个结点交换数据
lNode *node = head->next;
lNode *rightNode;
int number = getLinkNumber(head);
int i, temp, i2;
for (i = 1; i <= number / 2; ++i) {
temp = node->data;
rightNode = node;
for (i2 = i; i2 <= number - i; ++i2) {
rightNode = rightNode->next;
}
node->data = rightNode->data;
rightNode->data = temp;
node = node->next;
}
}单链表代码看这：数据结构简单入门/复习（一）-线性链表（C语言）
将函数加入后即可实现，整合后代码：
/*1.已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，
*删除表中所有大于 x 且小于 y 的元素（若表中存在这样的元素）同时释放被删除结点空间。
*2.试写一算法，实现单链表的就地逆置。
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct lNode{
int data;
struct lNode *next;
}lNode;
lNode *createLink();
void insertLNode(lNode *node, int newData);
void deleteLNode(lNode *node);
void printLink(lNode *head);
void removeRangeInLink(lNode *head, int x, int y);
int getLinkNumber(lNode *head);
void reverseLink(lNode *head);
int main() {
lNode *head = createLink();
printf("输出原链表内容：");
printLink(head);
//printf("输出移除后链表内容：");
//removeRangeInLink(head, 2, 8);
//printLink(head);
printf("逆置链表的内容：");
reverseLink(head);
printLink(head);
system("PAUSE");
return 0;
}
int getLinkNumber(lNode *head) { //用于计算链表中结点个数，给逆置函数使用
lNode *node = head->next;
int number = 0;
while (node) {
number++;
node = node->next;
}
return number;
}
void reverseLink(lNode *head) { //逆置函数，双重循环，将第i个结点与第num-i个结点交换数据
lNode *node = head->next;
lNode *rightNode;
int number = getLinkNumber(head);
int i, temp, i2;
for (i = 1; i <= number / 2; ++i) {
temp = node->data;
rightNode = node;
for (i2 = i; i2 <= number - i; ++i2) {
rightNode = rightNode->next;
}
node->data = rightNode->data;
rightNode->data = temp;
node = node->next;
}
}
void removeRangeInLink(lNode *head, int x, int y) { //移除链表中>x且<y的值。
lNode *node = head->next;
while (node) {
if (node->data >= y) return;
else if (node->data > x) deleteLNode(node);
else node = node->next;
}
}
lNode *createLink() { //创建链表，并返回一个带头结点的链表。
lNode *head = (lNode*)malloc(sizeof(lNode));
lNode *node = head;
head->next = NULL;
int i = 0;
for (i = 1; i <= 8; i++) { //链表结点自动生成，用作测试
insertLNode(node, i);
node = node->next;
}
return head;
}
void insertLNode(lNode *node, int newData) { //插入结点
if (node->next == NULL) {
node->next = (lNode*)malloc(sizeof(lNode));
node->next->next = NULL;
node->next->data = newData;
}
else {
lNode *temp = (lNode*)malloc(sizeof(lNode));
temp->next = node->next;
temp->data = newData;
node->next = temp;
}
}
void deleteLNode(lNode *node) { //删除结点
if (node->next == NULL) {
free(node);
}
else {
lNode *temp;
temp = node->next;
node->data = temp->data;
node->next = temp->next;
free(temp);
}
}
void printLink(lNode *head) { //打印带头结点的链表，若不带头结点，将第一行head->next改为head即可。
lNode *node = head->next;
while (node) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}算法设计题第三题分析
3.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。
这题我不是很能理解，因为带头结点的循环链表，不论链表是否为空，都有一个作为指示的头结点，
而队列中，空队列的队头与队尾指向同一个结点，
而该链表作为队列，根据循环链表特性，链表尾会指向链表头，即队尾指向队头，
那么就出现了一个问题，一个空队列，有这些东西：
一个只用作指示的链表头，以及一个无值但是后继指向链表头的队尾（链表尾）。
就非常奇怪，这样插入队列前，就会有一个结点存在，并且这个结点还是无值的。
但我勉强写出来了，但会将这个多余无值的队尾结点也打印出来，
并且退出队列时虽然都退出了，但是队尾的值会变成最后一个退出的值（即虽然结点退出，但空值的队尾又会变成该值）。
因此代码仅作参考。
/*
* 3.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），
* 试编写相应的队列初始化、入队列和出队列的算法。
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct qNode {
int data;
struct qNode *next;
}qNode;
typedef struct queue{
qNode *rear;
}queue;
queue *initQueue();
void enQueue(queue *q, int enData);
int deQueue(queue *q);
void printQueue(queue *q);
int main() {
queue *q = initQueue();
int i;
for (i = 1; i <= 10; i++) {
enQueue(q, i);
}
printQueue(q);
for (i = 1; i <= 5; i++) {
printf("%d", deQueue(q));
}
printQueue(q);
system("PAUSE");
return 0;
}
queue *initQueue() { //初始化空队列。
queue *q = (queue*)malloc(sizeof(queue));
q->rear = (qNode*)malloc(sizeof(qNode)); //队尾
q->rear->next = (qNode*)malloc(sizeof(qNode)); //队头
q->rear->next->next = q->rear; //队头的下一个指向队尾
return q;
}
void enQueue(queue *q, int enData) {
qNode *newNode = (qNode*)malloc(sizeof(qNode));
newNode->next = q->rear->next;
newNode->data = enData;
q->rear->next = newNode;
q->rear = newNode;
}
int deQueue(queue *q) {
qNode *temp = q->rear->next->next;
int returnData = temp->next->data;
q->rear->next->next = q->rear->next->next->next;
free(temp);
return returnData;
}
void printQueue(queue *q) {
qNode *node = q->rear->next->next;
int i = 1;
while (node !=q->rear->next){
printf(" %d", node->data);
node = node->next;
}
printf("\n");
}
共有 0 条评论