3.9 KiB
前排直链： 油猴脚本：Tampermonkey 下载 划词脚本：魔改题海划词+ChatGPT 自动搜题答题：全平台自动答题脚本 自动学习课程：OCS 网课助手 超星万能 签到：Github自行查找 (防止太多人不去上课了影响到我的操作❤) 程序段的功能是将L1,L2中长的链表连接在短的链表后一起，主要操作时间花费在查找短表的终端结点上，所以本算的法时间复杂度为O(min(m,))
选择题a,e,d,f,c,b 选择题3 4 6 5 2 1 选择题4 3 1 2 5
23 49 76 58 34 42 80 95 49 76 58 80 95 23 42 34 49 58 76 95 80 76 58 49 95 40
8 0 4 5 64 46 2.5
4 30 53
A-B(6) C-G(6) E-F(7) C-D(8) 49
简答题(共4题;共29.0分) 1.给定二叉树T，假设n0为T中叶子节点数，n2为T中度为2的节点数，试证明n0=n2+1。 (6.0分)泰考含案 证明:设 n1为二叉树T中度为1的结点数，n 为总结点数则n=n0+n1+n2(1)再看分支数，除根结点外，每个顶点都对应一个分支数即n-1=n1+2"n2(2)有(1)和(2)可得 n0=n2+1 4.设计一个算法，通过遍历一趟，将单链表中所有结点的链接方向逆转，仍利用原链表的存储空间。
void inverse(LinkList &L) (
// 逆置带头结点的单链表L
p=L->next; L->next=NULL:
while ( P)(
q=P->next;//q指向p的后继
P->next=L->next:
L->next=p; //p 插入在头结点之后
P=q;
}
}
p p=p->lchild p=p->rchild
Q.front == Q.rear Q.front == (Q.rear+1)%M
填空题 7 LA->data[i]data[j] ilength jlength LC->length=k
填空题 8 true BST->left BST->right
二分查找思路:要求线性表中的元素必须己按关键字值有序(递增或递减)排列。围绕选取和对比中间位置元素的关键词而进行。
int binarySearch(SeqList L, int Key) {
int low = 0;
int high = L.length - 1;
while (low <= high) { // 当 low>high 时搜索结束
int mid = (low + high) / 2;
if (L.elem[mid] == Key) { // 找到关键字
return mid;
} else if (L.elem[mid] < Key) { // 在右半部分继续查找
low = mid + 1;
} else { // 在左半部分继续查找
high = mid - 1;
}
}
return -1; // 没有找到关键字
}
3.设待排序的关键字序列为(12，2,1，30281016*，20618),试分别写出使用希尔排序(增量选取 5,3，1)和快速排序 (6.0分)方法，每趟排序结束后关键字序列的状态 参考答案 希尔排序 (增量选取 5，3，1) 10 2 16 6 18 12 16* 20 30 28(增量选取5) 6 2 12 10 18 16 16* 20 30 28(增量选取3) 2 6 10 12 16 16* 18 20 28 30(增量选取1） 快速排序: 12 [6 2 10] 12 [28 30 16* 20 16 18] 6 [2] 6 [10] 12 [28 30 16* 20 16 18] 28 2 6 10 12 [18 16 16* 20]28 [30] 18 2 6 10 12 [16* 16] 18 [20] 28 30 16* 2 6 10 12 16*[16] 18 20 28 30 左子序列递归深度为 1，右子序列递归深度为 3
typedef char ElemType;
// 定义链表结构体
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkNode;
// 删除与给定值相等的元素
int LinkChange(LinkNode *L, ElemType x) {
LinkNode p = *L, q = NULL;
int flag = 0;
while (p != NULL) {
if (p->data == x) {
if (q == NULL) {
*L = p->next;
} else {
q->next = p->next;
}
LinkNode temp = p;
p = p->next;
free(temp);
flag = 1;
} else {
q = p;
p = p->next;
}
}
return flag;
}