数据结构习题练习(三)-链表(线性表、栈和队列)-删除链表中大于x小于y的元素/单链表的就地逆置

数据结构习题练习目录

单项选择题

  1. 不带头结点的单链表 head 为空的判定条件是____
    A. head= =NULL B. head—>next= =NULL
    C. head—>next= =head D. head!=NULL
  2. 带头结点的单链表 head 为空的判定条件是____
    A. head= =NULL B. head—>next= =NULL
    C. head—>next= =head D. head!=NULL
  3. 非空的循环单链表 head 的尾结点(由 p 所指向)满足____
    A. p—>next= =NULL B. p= =NULL
    C. p—>next= =head D. p= =head
  4. 在循环双链表的 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;
  5. 在一个单链表中,已知 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;
  6. 在一个单链表中,若 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;
  7. 在一个单链表中,若删除 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;
  8. 从一个具有 n 个结点的单链表中查找其值等于 x 结点时,在查找成功的情况下,需平均比较____个结点。
    A. n B. n/2 C. (n-1)/2 D. (n+1)/2
  9. 在一个具有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是____
    A. O(1) B.O(n) C. O (n2) D.O (nlog2n)
  10. 给定有 n 个元素的向量,建立一个有序单链表的时间复杂度是____
    A. O(1) B.O(n) C. O (n2) D.O (nlog2n)
  11. 向一个栈顶指针为 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;
  12. 从一个栈顶指针为 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;

填空题

  1. 单链表是____的链接存储表示。
  2. 可以使用____表示树形结构。
  3. 在双链表中,每个结点有两个指针域,一个指向____另一个指向____
  4. 在一个单链表中的 p 所指结点之前插入一个 s 所指结点时,可执行如下操作:
    ⑴ s—>next=____;
    ⑵ p—>next=s;
    ⑶ t=p—>data;
    ⑷ p—>data=____;
    ⑸ s—>data=____;
  5. 在一个单链表中删除 p 所指结点时,应执行以下操作:
    q= p—>next;
    p—>data= p—>next—>data;
    p—>next=____;
    free(q);
  6. 带有一个头结点的单链表 head 为空的条件是____
  7. 在一个单链表中 p 所指结点之后插入一个 s 所指结点时,应执行 s—>next=____和 p—> next=____的操作。
  8. 非空的循环单链表 head 的尾结点(由 p 所指向),满足条件____
  9. 在栈顶指针为 HS 的链栈中,判定栈空的条件是____
  10. 对于一个具有 n 个结点的单链表,在已知 p 所指结点后插入一个新结点的时间复杂度是____;在给定值为 x 的结点后插入一个新结点的时间复杂度是____

算法设计题

  1. 已知线性表中的元素以值递增有序排列,并以单链表作存储结构。试写一算法,删除表中所有大于 x 且小于 y 的元素(若表中存在这样的元素)同时释放被删除结点空间。
  2. 试写一算法,实现单链表的就地逆置。
  3. 假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针),试编写相应的队列初始化、入队列和出队列的算法。

单项选择题分析

  1. 不带头结点的单链表 head 为空的判定条件是____
    A. head= =NULL B. head—>next= =NULL
    C. head—>next= =head D. head!=NULL
    不带头结点的单链表head保存的,是链表中第一个结点地址,
    若链表为空,则第一个结点为NULL,即head==NULL

    .
  2. 带头结点的单链表 head 为空的判定条件是____
    A. head= =NULL B. head—>next= =NULL
    C. head—>next= =head D. head!=NULL
    不带头结点的单链表head保存的,是链表的信息,或为空仅作指示
    head-next是链表中第一个结点地址,
    若链表为空,则第一个结点为NULL,即head-next==NULL

    .
  3. 非空的循环单链表 head 的尾结点(由 p 所指向)满足____
    A. p—>next= =NULL B. p= =NULL
    C. p—>next= =head D. p= =head
    循环链表中,最后一个结点p的next指向头结点,
    即p->next == head

    .
  4. 在循环双链表的 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结点的后继。

    .
  5. 在一个单链表中,已知 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;
    与前一题不同,这题给出了链表中两个结点,要求在其间插入新结点。
    那就是送分题了,因为是单链表,所以直接修改后继即可,顺序不论。

    .
  6. 在一个单链表中,若 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。

    .
  7. 在一个单链表中,若删除 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的后继,
    .
  8. 从一个具有 n 个结点的单链表中查找其值等于 x 结点时,在查找成功的情况下,需平均比较____个结点。
    A. n B. n/2 C. (n-1)/2 D. (n+1)/2
    最好情况是第1个结点就找到,最差情况是第n个结点找到,
    因此平均为两者相加除二。

    .
  9. 在一个具有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是____
    A. O(1) B.O(n) C. O (n2) D.O (nlog2n)
    本题的插入新结点,就是查找结点插入位置,就是上题的结果
    但因为时间复杂度一般不保留系数,因此为O(n)。

    .
  10. 给定有 n 个元素的向量,建立一个有序单链表的时间复杂度是____
    A. O(1) B.O(n) C. O (n2) D.O (nlog2n)
    这题我觉得D也是可以的,
    如果是先排序,再建立链表,那么就是排序时间复杂度+建立链表时间复杂度,
    建立链表时间复杂度是n,肯定比排序时间复杂度的规模小,可省略,
    因此就是一个排序算法的时间复杂度了,
    用冒泡排序的话,那就是O(n2),用快速排序的话,就是O(nlog2n),
    但也有一种可能,他是先找到最小的,再逐个加入链表,
    就是将链表的建立加入到冒泡排序中,
    那就是O(n2)了。

    .
  11. 向一个栈顶指针为 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。

    .
  12. 从一个栈顶指针为 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;
    先处理与待删除结点相关的操作,再删除结点,
    因此,先保存栈顶结点数据,再将栈顶结点退出。

填空题分析

  1. 单链表是线性表的链接存储表示。
    记下来吧。
    .
  2. 可以使用双链表表示树形结构。
    记下来吧。
    我一直觉得链表这种线性结构不能表示树这种非线性结构,这题令我迷惑。

    .
  3. 在双链表中,每个结点有两个指针域,一个指向直接前驱,另一个指向直接后继
    是双链表的结构体定义。
    .
  4. 在一个单链表中的 p 所指结点之前插入一个 s 所指结点时,可执行如下操作:
    ⑴ s—>next=p->next;
    ⑵ p—>next=s;
    ⑶ t=p—>data;
    ⑷ p—>data=s->data;
    ⑸ s—>data=t;
    这题的解法是将s插入到p后面,然后交换s与p的data值,
    还是很合情合理的,毕竟只给出单链表一个结点,没有指针能指向该结点前驱,
    所以通过交换结点值来达到类似效果。

    .
  5. 在一个单链表中删除 p 所指结点时,应执行以下操作:
    q= p—>next;
    p—>data= p—>next—>data;
    p—>next=p->next->next;
    free(q);
    这个与上题一样,为了不让链表断裂,p的地址不能变化,
    因此只能交换p与p->next的data值,然后将p->next删除了。

    .
  6. 带有一个头结点的单链表 head 为空的条件是head->next==NULL
    带头结点的单链表中,头结点的后继结点才是链表第一个结点。
    .
  7. 在一个单链表中 p 所指结点之后插入一个 s 所指结点时,应执行 s—>next=p->next和 p—> next=s的操作。
    与选择题第六题一样。
    .
  8. 非空的循环单链表 head 的尾结点(由 p 所指向),满足条件p->next==head
    循环单链表,在单链表的基础上,将尾结点的后继从NULL改成了head。
    但我觉得空链表时的p->next==NULL==head,也满足条件,就很奇怪,
    还有一点,如果链表为空,那p->next的访问就会报错,因为p为空,就没有p->next。
    这题答案我觉得用单链表的判断就可以了,
    即有头结点的head->next != NULL,
    无头结点head != NULL。

    .
  9. 在栈顶指针为 HS 的链栈中,判定栈空的条件是HS==NULL
    栈空时栈顶指针为空,栈没有类似头指针的东西(当然也可以设置出来,但这题都这样问了不是)
    .
  10. 对于一个具有 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");
}

You may also like...

发表评论

邮箱地址不会被公开。 必填项已用*标注