数据结构考题汇总(C语言版, 附代码)

您所在的位置：网站首页 › c语言的期末考试题 › 数据结构考题汇总(C语言版, 附代码)

数据结构考题汇总(C语言版, 附代码)

2024-01-11 18:45| 来源: 网络整理| 查看: 265

数据结构考题1.4

更新了时间复杂度理论和计算方法（简单快速）

1.基本概念

范围：数据项(最小单位)next; }

插入

// 头插法把s插入p结点后 Node *s = (*Node)malloc(sizeof(Node)) s->next = p->next; p->next = s;

删除

// 删除p的后继（单链表中只能删后继，所以记得保存一个前驱结点pre） s = p->next; p->next = s->next; free(s);

建立

void createList(LinkedList &L, DataType array[], int length) // 头插法 p=L for (i=0; idata=array[i]; s->next = p->next; p->next = s; } // 尾插法 r=L; for (i=0; idata=array[i]; s->next = NULL; r->next = s; r=s; }

循环链表与单链表的区别是最后一个元素的next指向L(头结点) 判空区别，单链表：L->next == NULL; 循环链表：L->next == L; 应用：两个设立尾结点的循环的合并： A、B为两个循环链表的尾结点。

p=B->next->next; B->next=A->next; A->next=p;

双向链表在循环链表的基础上每个结点增加前驱指针（考的很少）

2.3. 应用

有序链表的合并

void combine(List &a, List &b, List &c) // a和b合并到c链表，且不占用新内存空间 { p1=a->next, p2=b->next; c=a; // 让c用a的头结点 pc=c; while (p1 && p2) { // 选择a和b的结点中小的一个，插入c表后面 if (p1->data < p2->data) { pc->next=p1; pc=p1; p1=p1->next; } else { pc->next=p2; pc=p2; p2=p2->next; } } if (!p1) pc->next=p2; if (!p2) pc->next=p1; free(b); }

链表原地反向

void reverse_list(List &L) { // 同时记录三个指针：pre, p, pNext；每次先保存pNext，把p指向pre p=L->next; pre=L; while (p) { pNext=p->next; p->next=pre; pre=p; p=pNext; } }

（持续更新）

3. 栈和队列

栈和队列都是操作受限的线性表，只能在表的两端进行操作（栈只能在一端操作）受容量限制，虽可以重新分配空间但工作量较大

3.1. 顺序栈

用顺序表实现栈，有两个指针base和top，base指向栈底元素，top指向栈顶的下一个

typedef struct { SDataType *base; // 栈底指针，若==NULL，则栈不存在 SDataType *top; // 栈顶指针，初始时top=base，top==base: 栈空 int stack_size; }SqStack // 创建顺序栈 bool create_stack(SqStack &s) { s.base = (SDataType*)malloc(MAX_SIZE * sizeof(SDataType)); if (!s.base) return false; s.top=s.base; s.stack_size = MAX_SIZE; return true; }

入栈

bool push(SqStack &s, SDataType e) { if (s.top-s.base==s.stack_size) return false; // 满栈 *s.top++ = e; return true; }

出栈

bool pop(SqStack &s, SDataType &x) { if (s.top==s.base) return false; // 栈空 x = *--s.top; return true; }

取顶

bool top(SqStack s, SDataType &x) { if (s.top==s.base) return false; // 栈空 x = *(s.top-1); return true; } 3.2. 链栈

用链表形式实现栈

typedef StackNode { DataType data; struct StackNode *next; }StackNode, *LinkStack; void initStack(LinkStack &s) // 初始化，置空指针 { s=NULL; }

入栈

bool push(LinkStack &s, DataType e) // 插入后部并栈顶指针后移 { StackNode *p = (*StackNode)malloc(sizeof(StackNode)); if (!p) return false; // 分配空间失败 p->data=e; p->next=s s=p; return true; }

出栈

bool pop(LinkStack &s, DataType &x) { if (s==NULL) return false; StackNode* q=s; x=q->data; s=s->next; free(q); return true; } 3.3. 栈的应用

n个元素的出栈顺序有几种？我们设F函数为解，则当n=0,1,2,3时，F(0)=F(1)=1, F(2)=2, F(3)=5 F(n)=C(2n, n) / (n + 1) = C(2n, n) - C(2n, n-1) [n个结点的二叉树有几种] 数值转换

// 十进制转八进制 void conversion() { initStack(s); scanf("%d", &n); while(n) { push(s, n%8); // 可转为任意(10以下)进制 n/=8; } while (!empty(s)) { pop(s, e); printf("%d", e); } }

括号检测

bool valid(char str[], int length) { bool flag=true; for (i=0; idata = d; p->next = NULL; q.rear->next = p; q.rear = p; return true; }

出队

bool DeQueue(LinkQueue &q, DataType &d) { if (q.rear == q.front) return false; p = q.front->next; d = p->data; q.front->next = p->next; if (p == q.rear) q.rear = q.front; // 最后一个元素出队后，要手动把rear=front free(p); return true; } 4.串、数组和广义表 typedef struct { char *str; int length; }String; 4.1 模式匹配算法

KMP next数组计算方法(教材的值)：

s串第0个字符的next[0]=0对于第i个字符(0right); */ /** 后序 postOrder(T->left); postOrder(T->right); d = T->data; */ } void levelTravel(BiTree T) { Queue q; initQueue(q); enQueue(q, T); while (!empty(q)) { BiTNode node; deQueue(q, node); printf("%d", node->data); // 若数据为整型 if (T->left != NULL) enQueue(q, T->left); if (T->right != NULL) enQueue(q, T->right); } }

复制二叉树

void copy(BiTree T, BiTree newT) { if (T == NULL) { newT = NULL; return; } newT = (*BiTNode)malloc(sizeof(BiTNode)); newT->data = T->data; copy(T->left, newT->left); copy(T->right, newT->right); }

计算深度

int depth(BiTree T) { if (T == NULL) return 0; else return max(depth(T->left), depth(T->right)) + 1; }

计算最大宽度

void getWidth(BiTree T, int count[], int level) // 用count数组存储每层的数量，最大宽度是Max(count) { if (T == NULL) return 0; else { count[level]++; getWidth(T->left, count, level + 1); getWidth(T->right, count, level + 1); } } 5.4 线索二叉树

（考的少）线索化是指：对二叉树的遍历结果中，体现出前驱后继的关系。建立线索化：先进行X序遍历（先、中、后、层次）得到序列，在原树的结点加入Ltag和Rtag，若0则left, right指针指向左右孩子；若1则指向直接前驱和后继。

5.5 森林、树和二叉树

参考：树、二叉树和森林的转换

森林转二叉树：一棵树中，每一层中靠右的兄弟变成靠左兄弟的右孩子，最左的兄弟成为父结点的左孩子。对每棵树之间，靠右的树根成为靠左的树根的右孩子，最左的树根成为二叉树的根。二叉树转森林：把根与右孩子分开成若干单独的二叉树（单独树没有右孩子）对于每棵二叉树，右孩子变兄弟连接到最左的兄弟的父结点，左孩子依然是孩子。

遍历树的遍历先根遍历：先访问根结点后访问孩子(从左至右) 后根遍历：先访问孩子后访问根结点森林的遍历先序遍历：先访问第一棵树的根结点，再访问根的子树，最后访问剩下的树中序遍历：先中序遍历第一棵树的子树（从左至右，从叶到根的顺序）在访问根节点，最后访问剩下的树

5.6 霍夫曼树

会手动操作就行主要思路：每次选择最小的两个值组成新结点，并加入到结点列表中，重复。霍夫曼编码过程则是在建立树之后，按左为1，右为0的方式。直到叶结点。 HT表的构建参考电子书P129

5.7 其他应用

通过先序、中序，中序、后序，而得到一棵唯一的树（简单题目）先序、后序不能得到一棵唯一的树

6. 图 6.1 图的建立

邻接矩阵

typedef VexType char; typedef ArcType int; typedef struct { VexType vexs[MAX_NUM]; // 顶点表，用来映射顶点名称(一般char)和数字下标(int) ArcType arcs[MAX_NUM][MAX_NUM]; // 邻接矩阵 int vex_num, arc_num; }AMGraph;

特点：

对于无向图，第i行元素之和表示顶点i的度。对于有向图，第i行元素之和表示顶点i的出度，第i列表示顶点i的入度。mat[i][j]=1表示i和j之间有边不利于增加删除顶点不利于统计边数空间复杂度高，n个顶点需要O(n2)的空间

邻接表默认为邻接出表，即指向顶点的出度

typedef struct ArcNode // 边结点 { int adjvex; struct ArcNode* nextarc; InfoType info; }ArcNode; typedef struct VNode // 顶点结点 { VexType vex; struct ArcNode *firstarc; }VNode, AdjList[MAX_NUM]; typedef struct { AdjList vertices; // 邻接表 int vex_num, arc_num; }ALGraph;

插入新边（有向图）

void insert(ALGraph &G, VexType v1, VexType v2, InfoType info) { i = locate(G, v1); j = locate(G, v2); // 确定v1和v2在G的位置 struct ArcNode* p = (ArcNode*) malloc(sizeof(ArcNode)); p->adjvex = j; p->info = info; p->next = G.vertices[i]->firstarc; G.vertices[i]->firstarc = p; // 若为无向图，则把i和j反过来再插入一次即可 }

特点：

利于增加删除结点统计边数方便，时复O(n+e)空间效率高，空复O(n+e)不利于判断v1和v2是否存在边，需要扫描v1和v2的边表，最差O(n)不利于统计顶点的度，出表可以计算出度，但是计算入度需要遍历整个表。逆邻接表计算入度方便却计算出度困难 6.2 图的遍历

深度优先搜索和广度优先搜索题目中可能考察深度优先生成树和广度优先生成树两个遍历方法中，用邻接矩阵的时间复杂度是O(n2), 用邻接表复杂度为O(n+e)

6.3 图的应用

最小生成树

Prim算法：先随机确定一点，再每次选连通分量周围最小的边，复杂度O(n2)，适合稠密图Kruskal算法：每次选不构成回路的最小边，复杂度O(eloge)，其中包含排序，适合稀疏图

最短路径 Dijskra算法：从源点到其他点最小距离（注意题目中可能要求完成距离变化表，电子书P157）思路： (1) 用d数组记录距离，起点为0，其他点为正无穷。从起点开始运算 (2) 对当前点所有邻边进行访问，若当前点的d值 + 其邻边代价 < 邻边的d值：则更新邻边的d值和其父结点 (3) 找到更新后的最小d值的点，放入“已完成”集合中，并把此边作为下一个运算的顶点 (4) 若“已完成”集合包含了所有顶点，则d值更新完成 (5) 终点的d值则为全局最小代价。从终点开始，循环访问其父结点可找到起点，这就是最短路径 Floyd算法：每个点之间最小距离（只适合邻接矩阵）

拓扑排序一定是有向无环图，所以可以检测有向图中是否有环，无解则有环过程：选一个无入度的顶点并输出，再删除这个顶点以它为尾的弧，重复。

关键路径题目中主要是完成关键路径表注意：影响关键活动的因素有很多，若子工程的时间有变化，则要重新计算关键路径，所以单提高一条关键路径上的关键活动速度，还不能导致工程缩短工期，必须同时提高几条关键路劲上的活动速度

6.4 十字链表

十字链表是有向图的另外一种存储方式，通常可视为把邻接表和逆邻接表结合的方式。定义：弧结点：tailvex, headvex, headLink, tailLink, info(信息位) tailvex和headvex分别表示弧尾和弧头链接的顶点在图中的位置 headLink和tailLink分别表示弧尾和弧头指向（的顶点）相同的下一条弧（也就是说：如果tailvex相同，则用tailLink连接，headvex相同用headLink连接）顶点结点：data(信息位), firstIn, firstOut firstIn表示第一个入度的边 firstOut表示第一个出度的边

稀疏矩阵压缩也可以用十字链表方式通常也分为两个元素结点: 行标、列标、元素值、指针A、指针B 其中前三个（行标、列标、元素值）一般也是三元组的组成，后面两个指针，A指向同行的下一个，B指向同列的下一个表头：chead, rhead 数组chead存储所有的列表头，数组rhead存储所有行表头

7. 查找 7.1 顺序表

顺序查找ASL=(n+1)/2。可为顺序结构也可为链式结构折半查找比较次数最多=floor(log2(n)) + 1，ASL=log2(n + 1) - 1。只能为可随机存储的顺序结构

int biSearch(SqList list, DataType e) { low = 0; high = list.length - 1; while (low e) high = mid - 1; else low = mid + 1; } return -1; }

折半查找虽然数值上比顺序查找高效，但是不一定快于后者

7.2 二叉排序树

左子树若不为空，则比根结点小。右子树若不为空，则比根结点大。左右子树都是二叉排序树。增加结点简单，比结点大就放左子树，比结点小就放右子树，若不为空则继续

void insert(BSTree &T, BSDataType e) { if (T == NULL) { T = (BSTNode*) malloc(sizeof(BSTNode)); T->data = e; T->left = T->right = NULL; } else { if (e < T->data) insert(T->left, e); else insert(T->right, e); } }

删除结点分为三个情况（删除x结点）

x为叶结点，直接删除即可x有一个非空子树，直接把此子树替代x结点x有两个非空子树，让中序序列的x的直接前驱替代x，左子树的最右的结点（相当于删去此结点替换到x的位置，若此结点也有子树(只有左子树)则启用方法2） 7.3 平衡二叉树

左右子树深度差为-1、0、1（称为平衡因子），左右子树都是平衡二叉树四个旋转LL、RR、LR、RL，参考旋转方式

7.4 B-树

参考m阶b-树的特点：

每个结点最多m个子树，最少ceil(m/2)个子树每个结点有n个信息，ceil(m/2)-1 ≤ n ≤ m-1（4阶b-树为[1,3]，5阶b-树为[2,4]）叶结点都在同一层

增加结点：简单以三阶b树为例：每次插入到叶子结点，若信息达到3个，则把下标m/2的信息（即中间的，第二个）上提到父结点，若父节点也达到3个，重复。删除结点：三种情况，电子书P199 对于非终端结点，则用右子树的最左结点（即右边最小的元素）替代此结点并删除该叶子结点的元素对于终端结点，如果信息 > ceil(m/2)-1，则无需更多操作若 == ceil(m/2)-1，则向父结点借一位刚好比自己大的信息，若不满足，继续上借，直到下沉（参考文章）

7.5 散列表的查找

构建散列函数要求：计算简单，尽量做到一个关键词一个散列地址。散列值在表长范围内，尽量减少冲突，并且均匀分布没有好与不好的函数，只有适合与不适合的函数，处理冲突的方法也如此处理冲突

开放地址法：若地址H0冲突则通过合适的计算得到另外一个地址H1 线性探测，二次探测（下一个位置为12, -12, 22, -22, …），伪随机探测（下一个地址Hi=base+di(伪随机序列)）优点：充分利用散列表空间，缺点：线性探测容易发生“二次聚集”现象，二次探测和伪随机探测可以避免，但还是不可避免不断地地址冲突

链地址法：把相同散列值记录在单链表上

散列因子a = 状如表的元素数量n / 散列表长度length 一般情况下，a越大，空间利用越高，越容易发生冲突。a越小，不易冲突但空间浪费多

等概率情况下ASL查找成功查找失败线性探测1/2 (1 + 1 / (1 - a))1/2 (1 + 1 / (1 - a)2)二次探测，伪随机探测-1/a ln(1 - a)1 / (1 - a)链地址法1 + a / 2a + e-a

一般做题不会用上面公式，而是查找成功/失败的ASL用比较次数之和/总查找元素个数(电子书p209)

8. 排序 8.1 插入排序

思路：将待排序关键字插入到已排序好的序列中合适的位置直接插入排序：顺序遍历序列，每次选择一个关键字插入到已排序好的序列中（从后往前），如果序列趋于正序，则插入部分速度越快，接近O(1)，最好情况是O(n)，最坏情况下序列完全颠倒O(n2)，平均O(n2)，空间辅助O(1)，排序稳定，可适用于顺序表和链表

折半插入排序：在直接插入的基础上改为折半查找并插入，性能和上面一样。序列趋于有序和无序速度接近，且不能适用于链表，只适合顺序表

希尔排序：缩小增量排序，增量k的意义是将表每隔k个元素进行一次直接插入排序（最好最好平均复杂度可参考上文直插排序），然后缩小k并重复上述操作，直到k=1时序列趋于有序，再对全体进行直插入排序。时复O(n1.3)，空间辅助O(1)，排序不稳定，只可用于顺序表，而且序列n越大越明显

8.2 交换排序

思路：两两进行比较，若不符合次序则交换，直至整个有序冒泡排序：对序列中相邻的两个数，若不符合顺序则进行交换，并继续迭代。如果没有发生交换，则算法结束。对于趋于正序，发生交换的次数减少，则迭代次数减少，最好情况是完全正序，时间复杂度O(n)，一般和最差时复O(n2)，空间辅助O(1)，排序稳定。可适用于顺序表和链表

快速排序：选择待排序列的某一个元素作为中枢pivot(一般第一个)，序列最后下标为high，第一个元素为low。从high往左找第一个比pivot小的元素，与pivot进行交换。再从low往右边找第一个比pivot大的元素，与pivot进行交换。重复操作直到low==high，则固定了这个元素在已排好序列中的位置。最后对此元素的左右子序列进行同样的交换操作。对于元素趋于有序（正序or反序），快速排序则退化成直接选择排序，复杂度O(n2)，最好的情况是分布均匀的序列，复杂度O(nlogn)，平均O(nlogn)，因为用到了递归，则最坏空间辅助O(n)，平均空间辅助O(logn)，，不稳定排序，仅适用于顺序表

8.3 选择排序

思路：每一趟选择最小的关键字，放在已排好序列的最后直接选择排序：序列前一段是已排序，后一段是未排序。每一趟在未排序序列中选择最小的元素，与未排序第一个进行交换。无论是否趋于有序，选择最小元素必须遍历一次序列，所以最好最坏平均复杂度都是O(n2)，辅助O(1)，不稳定排序，可用于顺序表和链表

堆排序：通过维护一个堆进行排序（以小根堆为例：从最后的非叶结点开始建立堆，即把根和左右孩子中最小元素作为根，并往前遍历直到整个堆的根，此过程复杂度O(n)），每次选出第一个元素，把最后一个元素放第一个后维护堆（此过程简述为：换上来的根元素X与最小的孩子进行交换，发生交换的一边继续交换，直到X比左右孩子都小，复杂度为O(logn)），堆为空的时候完成排序。复杂度O(nlogn)，空间可不用辅助数组O(1)，不稳定排序，仅顺序表

8.4 归并排序

思路：将两个及以上的有序表合并成一个有序表 2-路归并排序：1. 分治阶段：每次从中间分割序列，直到子序列长度

【本文地址】

数据结构考题汇总(C语言版, 附代码)

数据结构考题汇总(C语言版, 附代码)

今日新闻

推荐新闻