1. 按增长率升序排列函数 2100, (2/3)n, nn, n, n3/2, log2n, nlog2n： 。
升序排列：2100<(32)n<log2n<n<nlog2n<n3/2<nn
n 个结点的完全二叉树中，叶子结点数是 。
n0=(n+1)/2 n是奇数
n0=n/2 n是偶数
推导：
设 n 为总结点数，n0 为叶子结点数，n1 为度 1 结点数，n2 为度 2 结点数。
根据二叉树性质：
n=n0+n1+n2
n0=n2+1
完全二叉树中 n1 只能是 0 或 1
x=n;//n>1
y =0;
while (x>=(y+1)*(y+1))
y++;
求时间复杂度(指的是代码的执行次数)
设执行次数为k次
有 n >= k^2
和 n < (K+1)^2
k≈√n
简单分析字符串匹配的BF算法原理。字符串S="aaaabaa",字符串 T= "aab" , 使用BF算法进行子串匹配,则成功匹配需要比较多少次?
BF算法（Brute Force）原理分析
BF算法，也称暴力匹配算法或朴素模式匹配算法。
其基本原理是：
逐位对齐：从主串 \(S\) 的第一个字符起，与模式串 \(T\) 的第一个字符进行比较。
匹配则递进：若当前字符相等，则主串和模式串的指针同时向后移动，比较下一位。
失配则回溯：若字符不相等（即发生“失配”），主串指针回溯到本轮开始位置的下一个字符，模式串指针回到首位，重新进行下一轮比较。
循环往复：直到模式串 \(T\) 全部比较完毕（匹配成功），或主串 \(S\) 遍历结束（匹配失败）。
综上，本题答案为9次
3、将编号为0和1的两个栈存放于一个数组空间V[]中,栈底分别处于数组的两端。当第 0号栈的栈顶指针top[0]等于-1时该为空,当第1号的顶指针top[1]等于m时该 栈为空。两个栈均从两端向中间增长。给出实现这种机制的数据结构定义并进行简单的 基本算法分析。
答：
数据结构定义：
#define MAXSIZE 100 // 假设数组最大容量为 m
typedef struct {
int V[MAXSIZE]; // 共享数组空间
int top[2]; // 两个栈的栈顶指针：top[0] 为 0号栈，top[1] 为 1号栈
} DualStack;
// 初始化
void InitStack(DualStack *S) {
S->top[0] = -1; // 0号栈底在左侧，空栈时指向 -1
S->top[1] = MAXSIZE; // 1号栈底在右侧，空栈时指向 m (即 MAXSIZE)
}
基本算法分析：
判空：
top[0] == -1
top[1] == m
判满：
top[0]+1 == top[1]
进栈：
进栈时需要先判断是否栈满，再移动指针并赋值。
0号栈进栈：执行 S->top[0]++，然后 S->V[S->top[0]] = x。
1号栈进栈：执行 S->top[1]--，然后 S->V[S->top[1]] = x。
出栈：
出栈时需要先判断对应栈是否为空，再取值并移动指针。
0号栈出栈：取值后执行 S->top[0]--。
1号栈出栈：取值后执行 S->top[1]++。
性能优势
空间利用率高：两个栈互补。只有当数组空间全满时才会发生上溢（Stack Overflow），而不会因为其中一个栈满了、另一个还空着而导致资源浪费。
时间复杂度：所有基本操作（进栈、出栈、判空、判满）的时间复杂度均为 \(O(1)\)，与普通单栈一致。
如上图所示，画出该图。从结点2出发,每行接从左到右的顺序,给 出G1的深度和广度优先遍历的顺序。
深度优先遍历 (DFS) 采用栈（或递归）实现，优先深入探索路径。遵循“每行从左到右”（即优先访问编号小的邻接点）的顺序：
访问 2。标记 2 已访问。
查找 2 的邻接点：1, 5。优先访问 1。标记 1 已访问。
查找 1 的邻接点：2 (已访问), 3, 4。优先访问 3。标记 3 已访问。
查找 3 的邻接点：1 (已访问), 5。优先访问 5。标记 5 已访问。
查找 5 的邻接点：2 (已访问), 3 (已访问)。无未访问邻接点，回溯到 3。
回溯到 1。
查找 1 的下一个未访问邻接点：4。访问 4。标记 4 已访问。
查找 4 的邻接点：1 (已访问), 6。优先访问 6。标记 6 已访问。
查找 6 的邻接点：4 (已访问)。无未访问邻接点，回溯到 4。
回溯到 1，再回溯到 2。遍历结束。
广度优先遍历 (BFS) 采用队列实现，按层次探索图，先访问距离起点近的节点。遵循“每行从左到右”（即优先将编号小的邻接点加入队列）的顺序：
将 2 加入队列，标记 2 已访问。
从队列取出 2。将其所有未访问邻接点加入队列：1, 5。标记 1, 5 已访问。队列: [1, 5]。
从队列取出 1。将其所有未访问邻接点加入队列：3, 4 (2 已访问)。标记 3, 4 已访问。队列: [5, 3, 4]。
从队列取出 5。将其所有未访问邻接点加入队列：无 (2, 3 已访问)。队列: [3, 4]。
从队列取出 3。将其所有未访问邻接点加入队列：无 (1, 5 已访问)。队列: [4]。
从队列取出 4。将其所有未访问邻接点加入队列：6 (1 已访问)。标记 6 已访问。队列: [6]。
从队列取出 6。将其所有未访问邻接点加入队列：无 (4 已访问)。队列: [ ]。
队列为空，遍历结束。
所以答案是
BFS:2 -> 1 -> 3 -> 5 -> 4 -> 6
DFS:2 -> 1 -> 5 -> 3 -> 4 -> 6
分析线性表的主要特点,并设计下面问题的算法,给出思路或伪代码。(本题10分) 将两个递增的有序链表合并为一个递增的有序链表。要求结果链表不使用额外的存储空间。
线性表的主要特点
线性表是一种最基本、最常用的数据结构，其主要特点体现在元素的逻辑关系上：
有序性：线性表中的所有元素是按线性顺序排列的，存在一个唯一的“第一个”元素和一个唯一的“最后一个”元素。
一对一关系：除第一个和最后一个元素外，任何一个元素都有且仅有一个直接前驱元素和有且仅有一个直接后继元素。
有限性：线性表中的元素个数是有限的。
同质性：所有元素都具有相同的数据类型。
代码：
typedef struct ListNode {
int data;
struct ListNode *next;
} ListNode;
ListNode* MergeTwoLists(ListNode *l1, ListNode *l2) {
if (l1 == NULL) return l2;
if (l2 == NULL) return l1;
// 确保l1为较小节点起始链表
if (l1->data > l2->data) {
ListNode *temp = l1;
l1 = l2;
l2 = temp;
}
ListNode *res = l1; // 结果链表头
while (l1 != NULL && l2 != NULL) {
ListNode *prev = NULL;
// 找到l1中小于等于l2->data的最后一个节点
while (l1 != NULL && l1->data <= l2->data) {
prev = l1;
l1 = l1->next;
}
prev->next = l2; // 连接l2到l1
// 交换l1和l2，继续循环
ListNode *temp = l1;
l1 = l2;
l2 = temp;
}
return res;
}
分析队列的主要特点,并设计下面问题的算法,给出思路或伪代码。(本题10分) 用队列实现二叉树的层序遍历的非递归算法。
队列（Queue）是一种遵循“先进先出（First-In, First-Out, FIFO）”原则的线性数据结构。其核心特点包括：
FIFO原则：这是最本质的特点。第一个进入队列的元素将是第一个离开队列的元素。
线性结构：元素之间是线性排列的，每个元素只有一个前驱和后继。
双端操作：队列的操作集中在两端：队头（Front）用于删除元素（出队），队尾（Rear）用于插入元素（入队）。
抽象数据类型（ADT）：队列支持的主要操作通常包括 enqueue (入队)、dequeue (出队)、front (查看队头元素)、isEmpty (判空) 和 isFull (判满)。
代码：
typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
void LevelOrderTraversal(TreeNode *root) {
if (root == NULL) return;
Queue *q = InitQueue(); // 初始化队列
EnQueue(q, root); // 根节点入队
while (!IsQueueEmpty(q)) {
TreeNode *node = DeQueue(q); // 队头出队
printf("%d ", node->data); // 访问节点
if (node->left != NULL) EnQueue(q, node->left); // 左子节点入队
if (node->right != NULL) EnQueue(q, node->right); // 右子节点入队
}
DestroyQueue(q); // 销毁队列
}
四、写出二叉树的二叉链表存储表示,并设计下面问题的算法,给出算法思路或伪代码(本 题10分)
设计一个算法,统计二叉树中叶子结点的个数。
二叉树的存储表示：
typedef struct BiTNode {
int data; // 节点数据域
struct BiTNode *lchild; // 指向左子节点的指针
struct BiTNode *rchild; // 指向右子节点的指针
} BiTNode, *BiTree;
代码：
int CountLeafNodes(BiTree T) {
if (T == NULL) return 0; // 空树，叶子数为0
if (T->left == NULL && T->right == NULL) {
return 1; // 叶子节点，计数1
}
// 递归统计左右子树叶子数之和
return CountLeafNodes(T->left) + CountLeafNodes(T->right);
}
五、图3为某无向带权图(无向网络)的邻接表,画出其邻接矩阵,并使用普里(Prim) 算法求其最小生成树。写出添加每一条边的过程,格式如:第一步,只有一个节点 V_{1}; 第二 步,添加边 (V_{1}, V_{y}) ;......并画出最终的最小生成树结果图。(本题10分)
1.写邻接矩阵
节点 V1 V2 V3 V4 V5 V6
V1 0 6 1 5 ∞ ∞
V2 6 0 5 ∞ 3 ∞
V3 1 5 0 5 5 ∞
V4 5 ∞ 5 0 ∞ 2
V5 ∞ 3 5 ∞ 0 6
V6 ∞ ∞ ∞ 2 6 0
2. Prim 算法过程（以 V1 为起点）
第一步：只有一个节点 V1
第二步：
从 V1 到其他节点的最短边是 (V1,V3)，权值 1
添加边 (V1,V3)
第三步：
当前集合 {V1,V3} 到其他节点的最短边是 (V1,V4)，权值 5
添加边 (V1,V4)
第四步：
当前集合 {V1,V3,V4} 到其他节点的最短边是 (V4,V6)，权值 2
添加边 (V4,V6)
第五步：
当前集合 {V1,V3,V4,V6} 到其他节点的最短边是 (V3,V2)，权值 5
添加边 (V3,V2)
第六步：
当前集合 {V1,V3,V4,V6,V2} 到其他节点的最短边是 (V2,V5)，权值 3
添加边 (V2,V5)
(V1, V3) 权值 1
(V1, V4) 权值 5
(V4, V6) 权值 2
(V3, V2) 权值 5
(V2, V5) 权值 3
总权值：1+5+2+5+3=16
分析图这种数据结构的主要特点,并使用Dijkstra算法求出上页图2(图1旁边)所示 有向加权图中 \(V_{0}\) 节点到其他所有节点的最短路径及距离。根据算法执行的每一步结果填写表。
边 权值
(V0,V2) 10
(V0,V4) 30
(V0,V5) 100
(V1,V2) 5
(V2,V3) 50
(V3,V5) 10
(V4,V3) 20
(V4,V5) 60
步骤 选中节点 Vs（距 V0 最近） 终点 V1 终点 V2 终点 V3 终点 V4 终点 V5
初始 - 距离：∞ 距离：10 距离：∞ 距离：30 距离：100
路径：无 路径：<V0,V2> 路径：无 路径：<V0,V4> 路径：<V0,V5>
1 V2（距离 10） 距离：∞ 距离：10（已选中） 距离：10+50=60 距离：30 距离：100
路径：无 路径：<V0,V2> 路径：<V0,V2,V3> 路径：<V0,V4> 路径：<V0,V5>
2 V4（距离 30） 距离：∞ 距离：10（已选中） 距离：min(60,30+20)=50 距离：30（已选中） 距离：min(100,30+60)=90
路径：无 路径：<V0,V2> 路径：<V0,V4,V3> 路径：<V0,V4> 路径：<V0,V4,V5>
3 V3（距离 50） 距离：∞ 距离：10（已选中） 距离：50（已选中） 距离：30（已选中） 距离：min(90,50+10)=60
路径：无 路径：<V0,V2> 路径：<V0,V4,V3> 路径：<V0,V4> 路径：<V0,V4,V3,V5>
4 V5（距离 60） 距离：∞ 距离：10（已选中） 距离：50（已选中） 距离：30（已选中） 距离：60（已选中）
路径：无 路径：<V0,V2> 路径：<V0,V4,V3> 路径：<V0,V4> 路径：<V0,V4,V3,V5>
5 V1（距离∞，无可达路径） 距离：∞ 距离：10（已选中） 距离：50（已选中） 距离：30（已选中） 距离：60（已选中）
路径：无 路径：<V0,V2> 路径：<V0,V4,V3> 路径：<V0,V4> 路径：<V0,V4,V3,V5>
终点 最终最短路径 距离
V1 无 ∞
V2 <V0,V2> 10
V3 <V0,V4,V3> 50
V4 <V0,V4> 30
V5 <V0,V4,V3,V5> 60
设有一组关键字(9,1, 23,14, 55, 20, 84, 27),采用散列函数 H( key )= key % 7 ,表 长为10,用开放地址法的二次探测法处理冲突。对该关键字序列构造散列表,填写表2,并 计算查找成功的平均查找长度。限定 d_{1} 取值为1,2,.. k^{2}(k ≤m / 2)(在答题卡自己重 画表2并填空,本题10分)
介绍：
dk=(d±k2)mod m
d=H(key)：初始散列地址；
+k²：正向二次探测（地址向后偏移 k²）；
-k²：反向二次探测（地址向前偏移 k²）；
mod m：确保地址在表长范围内（0~m-1）。
核心特点
探测步长是平方数：不同于线性探测（步长固定为 1），二次探测的步长随冲突次数 k 增长为 1²,2²,3²,...，避免线性探测的 聚集现象（大量冲突集中在某一区域）。
探测范围有限：通常限制 k≤m/2，因为当 k 超过 m/2 后，探测地址会重复，无法覆盖所有空地址。
查找效率更高：相比线性探测，二次探测能更快跳出冲突聚集区域，平均查找长度更短。
答案：
散列地址 0 1 2 3 4 5 6 7 8 9
关键字 14 1 9 23 - 27 55 20 84 -
比较次数 1 1 1 2 0 2 1 2 3 0
1.谈谈你对数据结构的认识。
2.谈谈栈、队列、串这几种特殊的线性表之间的区别与联系。
1.数据结构是计算机科学中组织、存储和处理数据的核心方式，是连接数据与算法的桥梁，其本质是 “数据的逻辑关系 + 存储结构 + 操作方法” 的三位一体。
从分类来看，数据结构可分为三大类：
线性结构：元素间为一对一的线性关系，如数组、链表、栈、队列，适合表示有序序列；
非线性结构：元素间为一对多或多对多关系，如树（层次关系）、图（任意关联关系），适合表示复杂关联数据（如文件系统、社交网络）；
集合结构：元素间无明确关系，仅强调 “属于同一集合”，是基础数据组织形式。
2.核心联系：同为特殊的线性表
核心区别：操作规则与应用场景
特性 栈 (Stack) 队列 (Queue) 串 (String)
操作原则 后进先出 (LIFO) 先进先出 (FIFO) 随机存取、模式匹配
操作限制 只允许在一端（栈顶）进行插入和删除操作 只允许在两端（队头出队，队尾入队）进行操作 关注序列本身的内容、长度和子串操作
应用场景 函数调用栈、表达式求值、递归 任务调度、消息队列、缓冲区管理 文本处理、数据检索、密码学
暂无评论