【数据结构】830+848真题易错题汇总（10-23）

【数据结构】830+848易错题汇总(10-23)

文章目录

【数据结构】830+848易错题汇总(10-23)

选择题

1、顺序栈 S 的 Pop(S, e)操作弹出元素 e，则下列(C )是正确的操作。（严书定义）

A. e=*(s.top) B. e=*(s.top--) C. e=*(--s.top) D.e=--s.top

#define MAXSIZE 100
#define Status int
#define OK 1
#define ERROR 0

struct SElemType {
    Status data;
};

typedef struct {
    SElemType *base; //栈底指针
    SElemType *top;  //栈顶指针
    int stacksize;   //栈可用的最大容扯
} SqStack;

Status InitStack(SqStack &S) {
    S.base = new SElemType[MAXSIZE];
    if (!S.base) exit(0);
    S.top = S.base;
    S.stacksize = MAXSIZE;
    return OK;
}

Status Push(SqStack &S, SElemType e) {
    if (S.top - S.base == S.stacksize) return ERROR;
    *S.top++ = e;   //先将元素e压入栈顶，栈顶指针+1
    return OK;
}

Status Pop(SqStack &S, SElemType &e) {
    if (S.top == S.base) return ERROR;
    e = *(--S.top); //栈顶指针-1, 将栈顶元素赋给e
    return OK;
}

SElemType GetTop(SqStack &S) {
    if (S.top != S.base)
        return *(S.top - 1); //返回栈顶元素的值，栈顶指针不变
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

2、设连通图 G 的顶点数为 n,则 G 的生成树的边数为( B)

A. n B. n-1 C.2n D. 2n-1

3、在线索化二叉树中，T 所指结点没有左子树的充要条件是（B ）。

A. T->left=NULL B. T->ltag=1 C. T->ltag=1 且 T->left=NULL D. 以上都不对

二叉树线索化的过程中，会把树中的空指针利用起来作为寻找当前节点前驱和后继的线索，这样就出现了一个问题，即线索和数中原有指向孩子节点的指针无法区分。上边的这种节点设计就是为了区分这两类指针。其中，ltag和rtag为标识域，它们的具体意义如下。

如果ltag==0，表示lchild为指针，指向结点的左孩子；如果ltag==1，表示lchild为线索，指向结点的直接前驱。
如果rtag==0，表示rchild为指针，指向结点的右孩子；如果rtag==1，表示rchild为线索，指向结点的直接后继。

4、在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关（D）

A．不一定相同 B．互为逆序 C．都不相同 D．都相同

5 、对于元素是整数(占 2 个字节)的 n 行 n 列对称矩阵 A,采用以行序为主的压缩存储方式存储到一维数组 s[n*(n+1)/2]中(下三角),若 A[1][1]的起始地址是 400，问元素 A[8][5]的存储地址是(D).
A. 432 B. 563 C. 484 D. 464

ans = 400 + (7*(7 + 1) / 2 + 4 ) = 464

6 、对于元素是整数( 占2个字节)的对称矩阵A,采用以行序为主的压缩存储方式(下三角),若A[0][0]的地址是400, 则元素A[8][5]的存储地址是（ C ）。

A.440 B. 480 C.482 D. 582

ans = 400 + (8*(8 + 1) / 2 + 5 ) = 482

7 、一组记录（50，40，95，20，15，70，60，45，80）进行冒泡排序时，第一趟需进行相邻记录的交换的次数为（ C ）。(严书定义是从前往后比较的)

A.5 B. 6 C. 7 D.8

8、线性表采用链式存储时,其地址（D）

A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续与否均可以

9、若使用二叉链表作为树的存储结构，在有 n 个结点的二叉链表中非空的链域的个数为(A)

A. n-1 B. 2n-1 C. n+1 D. 2n+1

共2n个链域，空链域n+1个则非空链域2n-(n+1)=n-1

10、一个具有 500 个结点的完全二叉树具有一个孩子的结点个数最多为（A）。

A．1 B．250 C．0 D．249

完全二叉树至多有一个度为1的结点，看最后一个结点编号若为奇数则为0，若为偶数则有一个

11、设有一个无向图 G=（V，E）和 G’=（V’，E’），如果 G’为 G 的生成树，则下面不正确的说法是（B ）。
A．G’为 G 的子图 B．G’为 G 的连通分量
C．G’为G的极小连通子图且 V’=V D．G’为 G 的一个无环子图

有向图中称强连通分量，无向图中的极大连通子图称为连通分量，而且连通分量中可能存在回路

生成树是通过对图的一次遍历（深度or广度）产生的，本质上是一棵树，它拥有连通图的所有顶点，且最少的边，同时一个图的生成树是它的极小连通子图，理论上说，如果这个图是一个连通图，那么连通分量和此时的极小图是一样的，但一般情况下，讨论连通分量是在不连通的图中。

12、设有 n 个待排序的记录关键字，则在堆排序中需要（A）辅助记录空间

A． $O (1)$ B. $O (n)$ C. $O(nlog_{2}n)$ D. O（ $n^2$ )

13、设 F 是由 T1，T2 和 T3 三棵树组成的森林，与 F 对应的二叉树为 B，T1，T2 和 T3 的结点数分别为 N1，N2和 N3，则二叉树 B 的根结点的左子树的结点数为（ A）。

A. N1-1 B. N2-1 C. N2+N3 D. N1+N3

森林转换为二叉树

（1）把每棵树转换为二叉树。

（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。

14、计算机内部数据处理的基本单元是（B ）。

A. 数据 B. 数据元素 C. 数据项 D. 数据库

数据元素：(Data element)是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成，数据项是构成数据元素不可分割的最小单位。

15、设哈夫曼树中的叶子结点总数为 m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ B）个空指针域

A. 2m-1 B. 2m C. 2m+1 D. 4m

哈夫曼树没有度为 1 的结点，只有叶子结点有空的指针域，每个叶子有 2个空指针域，于是空指针域数=2m 个

16、对于一个具有 n 个顶点的无向连通图，它包含的连通分量的个数为（B）

A． 0 B．1 C． n D． n+1

图本身就是连通图,所以是一个连通分量

17、在有向图的逆邻接表存储结构中，顶点 v 在表结点中出现的次数是（B ）。

A. 顶点 V 的度 B. 顶点 V 的出度 C. 顶点 V 的入度 D. 依附于顶点 V 的边数

18、顺序栈 s 的 GetTop(s, e)操作是用 e 返回 s 的栈顶元素，则下列(B)是正确的操作。

A. e=*(s.top) B. e=*(s.top-1) C. e=*(--s.top) D. e=s.top-1

19、在一棵非空m阶的B-树上，除根之外的所有非终端结点（ C ）。

A. 至少有 $\lfloor m/2 \rfloor$ 棵子树 B. 至多有 $\lfloor m/2 \rfloor$ 棵子树

C. 至少有 $\lceil m/2 \rceil$ 棵子树 D. 至多有 $\lceil m/2 \rceil$ 棵子树

20、用带头结点的单链表存储队列，其队头指针指向头结点，队尾指针指向队尾结点，则在进行出队时（ D ）。

A. 仅修改队头指针 B. 仅修改队尾指针

C. 对头、尾指针都要修改 D. 对头、尾指针都可能要修改

如果当前队列中仅有一个元素，则删除它时队头、队尾指针都需要修改。如果不是一个元素，只需要修改队头节点。

21、一组记录的关键字为（45,80,55,40,42,85）, 则利用堆排序的方法建立的初始堆为（B）

A. （80,45,55,40,42,85) B. (85,80,55,40,42,45)
C. (85,80,55,45,42,40) D. (85,55,80,42,45,40)

22、利用逐点插入法建立序列（50,72,43,85,75,20,35,45,65,30）对应的二叉排序树以后，查找元素35 要进行（A）

A. 4 次 B. 5 次 C. 3 次 D. 2 次

第几层便要查找几次，根节点也算一次查找

23、假设根结点为第 1 层，深度为 h 层的二叉树至少有( ) 个结点（h>1）

A. $2^{h}$ B. $2^{h-1}$ C. $2^{h}$ +1 D. $2^{h}$ -1

错题，深度为h的完全二叉树至少 $2^{h-1}$ 个结点，深度为h的二叉树至少h个结点

24、用单向链表来实现容量为 n 的堆栈时，链表头指针指向堆栈顶部元素，链表尾指针指向堆栈底部元素，则以下说法错误的是(C )

A. 入栈操作的复杂度为 $O (1)$ B. 出栈操作的复杂度为 $O (1)$
C. 删除底部元素的复杂度为 $O (1)$ D. 插入一个新的堆栈底部元素复杂度为 $O (1)$

删除底部(尾部)元素的复杂度为 O(n), 寻找其前驱指针要遍历整个链表

25、为了提高哈希表的查找效率，以下方法说法不正确的是( B)。
A. 设计好的哈希函数 B. 增加哈希函数的个数
C. 增大存储空间 D. 采用更好的地址冲突解决方法

25、在一个双向链表中，当删除结点 p 时，错误的操作序列为 (A )。(模拟一遍)
A. p=p->prev; p->next->prev=p; p->next=p->next->next;
B. p=p->next; p->prev=p->prev->prev; p->prev->next=p;
C. p->prev->next=p->next; p->next->prev=p->prev;
D. p=p->prev; p->next=p->next->next; p->next->prev=p

对于选项A：正确答案应为：

p=p->prev;p->next->next->pre=p;p->next=p->next->next;

26、有一个 100*90 的整数稀疏矩阵，其中非 0 元素个数为 10；设每个整数占用 3 个字节，则用三元组表示该矩阵时，总共需要的存储空间为(D )字节。

A．30 B．33 C．90 D．99

三元组除了存储矩阵非0元素外，还一般要用三个整数来存储矩阵的行数、列数和总元素个数，故(10*3+3)*3=99

27、根据使用频率，为 5 个字符设计的哈夫曼编码不可能是（ C）

A. 000，001，010，011，1 B. 000，001，01，10，11
C. 00，100，101，110，111 D. 0000，0001，001，01，1

哈夫曼树没有度为1的结点

28、哈希表的平均查找长度说法错误的是 ( D)。
A. 与处理冲突方法有关而与表的长度无关
B. 与选用的哈希函数有关
C. 与哈希表的饱和程度有关
D. 与表中填入的记录数有关

散列表的平均查找长度依赖于散列表的装填因子a,而不直接依赖于记录数或表长，散列表的查找效率取决于三个因素：散列函数、处理冲突的方法和装填因子。

29、已知一个长度为 11 的顺序表，其元素按关键字有序排列，若采用折半查找查找一个其中不存在的元素，则关键字的比较次数最多是（B）。
A．3 B．4 C．5 D．6

30、m 阶 B-树是一棵（C ）。
A .m 叉排序树 B. m-1 叉平衡排序树 C. m 叉平衡排序树 D. m+1 叉平衡排序树

31、下列程序段的时间复杂度是 (A)。

void func(int n){
	int i = 0, m = 0;
	while (m < n * n){
		i ++:
		m= m + i;
	}
}
1
2
3
4
5
6
7

A. O(n) B. O( $l o g n$ ) C. O( $n l o g n$ ) D. O( $n^2$ )

32、设p指向一个非空双向链表中的某个结点，将一个q所指新结点插入到该双向链表中，使其成为p所指结点的前驱结点，能正确完成此要求的语句段是 (C )。

A. q->next=p; q->prior=p->prior; p->prior=q; p->prior->next=q;

B. p->prior=q; q->next=p; p->prior->next=q; q->prior=p->prior;

C. q->prior=p->prior; q->next=p; p->prior->next=q;p->prior=q;

D. q->prior=p->next; q->next=p; p->prior->next=q; p->prior=q;

33、一个栈的入栈序列为1,2,3，···，n，其出栈序列是p1，p2，p3，···，Pn。若p1＝4，则p3可能取值的个数是多少？(D)

A. n-3 B. n-2 C. n-1 D. 无法确定

34、18. 如果无向图 G 必须进行两次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是
（B）。
A.G 肯定不是完全图 B.G 中一定有回路 C.G 一定不是连通图 D.G 有 2 个连通分量

连通图是指在无向图中，任意两个顶点都是连通的。如果一个图需要进行两次广度优先搜索才能访问其所有顶点，那么这个图肯定不是连通图，因为存在至少一个顶点，它不能在第一次广度优先搜索中被访问到。和图中是否有回路无关。

35、为了操作方便，用单链表表示的链式队列的队头应设在链表的（A）位置。
A.表头 B.表尾 C.表头和表尾均可 D.链中

链式队列队尾插入，队头删除，设置表头有助于删除结点，若设置在尾部则需遍历找前驱结点，需要更高的时间复杂度。

填空题

1、在散列表（hash）查找中，评判一个散列函数优劣的两个主要条件是计算简单和散列函数分布均匀。

2、为了能有效地应用HASH查找技术，必须解决的两个问题是(1)如何构造哈希函数和 (2)处理冲突的方法。

3 、稀疏矩阵一般的压缩存储方法有两种, 即: 三元组和十字链表。

4、循环链表的主要优点是：从表中任一节点出发都能遍历整个链表。

5、对于一个具有 n 个记录的序列，若采用冒泡排序，记录之间最少的比较次数是 $n - 1 次$ 最多的比较次数是 $n (n - 1) /2$ 次。

6 、由 n 个权值构成的哈夫曼树共有 $2 * n - 1$ 个结点

7、向栈中压入元素的操作是先存入元素，后 移动栈顶指针。（按严书定义）

8、在队列中仅有一个元素的情况下，链队列的出队操作需要修改尾指针。

9 、所谓连通图 G 的生成树,是 G 的包含其全部 n 个顶点的一个极小连通子图。它必定包含且包含 G 的 n-1条边。

10、设 GetHead(p)为求广义表 p 的表头函数，GetTail(p)为求广义表 p 的表尾函数。其中()是函数符号，运算 GetTail(GetHead((a,b),(c,d,e)))的结果是 (b)。

注：广义表的表头是元素，表尾是广义表。

11、对 n 个结点进行快速排序，最大比较次数是 $n (n - 1) /2$

注：最大比较次数出现在最坏情况，也就是初始序列完全有序的情况，种情况下每次划分都是最不均匀的，即一边是零个另一边是全部。

12、单链表中设置头结点的作用是使得不需要对表头元素的操作进行特殊化处理，空表和非空表插入元素时的处理得到统一。

13、有一个100×90的稀疏矩阵，非0元素有10，设每个整型数占2个字节，则用三元组表示该矩阵时，所需的字节数是 66 。

三元组存储矩阵的行列和元素个数，以及非0元素， 2*3 + 10*3*2 = 66

14、根据数据元素之间关系的不同特性, 基本逻辑结构分为集合、线性结构、树形结构和网状结构 四种。

15 、对于 n 个记录（假设每个记录含 d 个关键字）进行链式基数排序，总共需要进行 d趟分配和收集。

16 、设数组 Data[0…m]作为循环队列 SQ 的存储空间，front 为队头指针，rear 为队尾指针则执行出队操作时 front 指针的值应更新为 front=(front+1)%(m+1) 。

17、当向 B-树中插入关键字时,可能引起结点的分裂 ,最终可能导致整个 B-树的高
度增加 1。

18、. 设散列表的长度为 8，散列函数 H(k)=k%7，用线性探测法解决冲突，则根据一组初始关键字序列(8，15，16，22，30，32)构造出的散列表的平均查找长度是 8/3。

address	0	1	2	3	4	5	6	7
key	1	15	16	22	30	32
count	1	2	2	44	4	3

$A S L = (1 + 2 + 2 + 4 + 4 + 3) /6 = 16/6 = 8/3$

19、设在一棵度数为 3 的树中，度数为 3 的结点数有 2 个，度数为 2 的结点数有 1 个，度数为1 的结点数有 2 个，那么度数为 0 的结点数有6个

$n_3=2,n_2=1,n_1=2$ , 由于结点数=总度数+1，设 $n_0$ ,

$3*n_3 +2*n_2+1*n_1 + 1 = n_0+5$ , 解得 $n 0 = 6$

20、单链表中设置头结点的作用：无需再对第一个结点进行特殊处理，空表和非空表的处理得到统一。

21、在中序线索二叉树上，若当前访问节点的右标志为 0，根据中序遍历的定义，它的后继结点是当前访问节点的右孩子

右子树中最左下的结点

22、 Dijkstra算法是按路径长度递增 次序产生一点到其余各定点最短路径的算法。

23、对于一个循环队列Q[0…m-1]，队头、队尾指针分别为f、r，其判空的条件是 f == r，判满的条件是f==(r+1)%m 。

24、已知二维数组A[m][n]采用行序为主序存储，每个元素占k个存储单元，并且第一个元素的存储地址是Loc(A[0][0]), 则A[i][j]的地址是Loc(A[0]0[0])+k(i*n+j) 。

25、设Hash表为m=11，散列函数H(k)=k%11，表中已有4个结点，地址分别为：addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7，其余地址为空。如果用二次探测再散列处理冲突，关键字为49的结点的地址是9。

26、一个连通图的 生成树 是一个极小连通子图。

27、设有数组 A[i][j]，数组的每个元素长度为 3 字节，i 的值为 1 到 8，j 的值为 1 到10，数组从内存首地址 BA 开始顺序存放，当用以列为主存放时，元素 A[5][8]的存储首地址为BA+180 。

28、对 22 个记录的有序表作折半查找，当查找失败时候，至多需要比较 5次关键字，至少需要比较 4次关键字。

解释：22 个记录的有序表，其折半查找的判定树深度为 $\lceil log_2^{22} \rceil$ +1=5，且该判定树不是满二叉树，即查找失败时至多比较 5 次，至少比较 4 次。

29、最大容量为 s 的循环队列，队尾指针是 rear，队头是 front，则队满的条件
是 front == (rear + 1) % s。

30、. G 是一个非连通无向图，共有 28 条边，则该图至少有 9个顶点。

31、数据结构的三要素是：逻辑结构，存储结构，数据的运算。

数据结构研究的是数据的物理结构、逻辑结构以及它们之间的相互关系。

32、将对称矩阵 A[8][8]的下三角部分逐行存储到起始地址为 2000 的内存单元中，已知每个元素占 4 个单元，假设第一个元素是 A[0][0]，则 A[4][6]的地址是 2100

$Loc_{A[4][6]}=Loc_{A[6][4]}=2000+(6*(6+1)/2+4)*4=2100$

33、在顺序表中插入一个元素，需要平均移动表中一半元素，具体移动元素的个数与元素在表中的位置有关。

34、高度为3的满二叉树B（设根结点为第一层），将其还原为森林T，其中包含根结点的那棵树中有 (4 ) 个结点。

35、设G为具有37条边的无向连通图，则G至少有 (10 ) 个顶点,至多有 (38 ) 个顶点。

一个完全无向图最多有n*(n-1)/2条边 9*8/2=36说明9个结点不够，至少需要10个结点。一个n个结点的无向图连通图至少需要n-1条边。

36、含有n个顶点e条边的无向连通图，利用Prim算法生成最小生成树的时间复杂度为 O（ $n^2$ ） 。采用邻接矩阵的方法存储图时，查找图的某一条边的时间复杂度是 O(1)。

判断题

1、一颗满二叉树同时又是一颗平衡二叉树（F)（按严书定义）

注：平衡二叉树一定是二叉排序树，但满二叉树不一定是一颗平衡二叉树

2、已知一颗树的先序序列和后序序列，一定能构造出该树（T）

注：树的后序遍历等同于二叉树的中序遍历

3、在n个结点的无向图中，若边数大于n-1，则该图必是连通图（F）

注：以下两种说法是对的：

在n个结点的无向图中，若该图是连通图,则其边数大于等于n-1
在n个结点的无向图中，若边数大于 $(n - 2) (n - 1) /2$ ，则该图必是连通图

4、向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度（F）

注：每一层只比较一次，不会超过树的深度

5、若一个叶子结点是某子树的中序遍历序列的最后一个结点，则它必是孩子树的先序遍历中的最后一个结点。（T）

注：一个结点是某子树的中序遍历序列的最后一个结点，则它必是孩子树的先序遍历中的最后一个结点，这句话就是错的，因为该结点可能只有左子树没有右子树，但题目中强调了叶子结点，那就对了

6、一个广义表的表尾总是一个广义表。（T）

注：广义表的表头是元素，表尾是广义表。

7、拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序（ F ）

8、B和B+树都能有效地支持随机查找。（ T ）

注：B-树和B+树都支持随机查找，B+树支持顺序查找

一棵 m 阶非空 B-树，每个结点最多有 m棵子树，除根之外的所有非终端结点至少有 $\lceil m/2 \rceil$ 棵子树。

9、当向二叉排序树中插入一个结点，则该结点一定成为叶子结点（T）

10、由树转化成二叉树，该二叉树的右子树不一定为空。（F）

11、图的多重邻接表表示法中，表中结点的数目是图中边的条数。（T ）

12、哈希表查找效率高，当查找主键在范围[a,b]内所有的记录时，也应该优先选择哈希表。( F )

13、将包含 n 个元素的升序线性链表改成降序线性链表所需要的时间复杂度为 O(n) （T）。

时间复杂度O(n) 空间复杂度O(1)

14、在各种查找方法中，平均查找长度与结点个数无关的查找方法是哈希查找（T）

散列查找的平均查找长度与表长和元素个数无关，只与散列函数和装填因子有关

15、在中序线索化链表中，如果结点有右子树，则结点的后继为对右子树进行中序遍历时访问的第一个结点。(T)

16、队列的链式存储结构和顺序存储结构相比，其中一个优点是节省了存储空间。 ( F)

17、在一个AOE网中，一个关键活动提前完成，另一个关键活动延期完成，那么整个工程有可能会按时完成。 ( T)

18、希尔排序的时间复杂度为 $O(n^2)$ (F)

希尔排序是一种不稳定的排序算法。

希尔排序的平均时间复杂度和最坏时间复杂度与间距序列的选取有关。设间距序列为 $O (n)$ ，下面给出的两种经典选取方式，这两种选取方式均使得排序算法的复杂度降为 $O(n^2)$ 级别。

题目没有特别说明的情况下，希尔排序的时间复杂度不是 $O(n^2)$

19、子串 “ABC” 在主串 “AABCABCD” 中的位置为 2（序号从 0 开始）（F）

序号从0开始位置就为1

20、哈夫曼树中权值最小的结点离根最近（F）

简答题：

1、简述数据的逻辑结构和物理结构的区别和联系。

2、简述逻辑结构的四种基本关系并画出它们的关系图。（10 分）

（1）集合结构
数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是
否为班级成员，只需将班级看做一个集合结构。
（2）线性结构
数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺
序进行排列，将组成一个线性结构。
（3）树结构
数据元素之间存在一对多的关系。例如，在班级的管理体系中，班长管理多个组长，每
位组长管理多名组员，从而构成树形结构。
（4）图结构或网状结构
数据元素之间存在多对多的关系。例如，多位同学之间的朋友关系，任何两位同学都可
以是朋友，从而构成图形结构或网状结构。
其中树结构和图结构都属于非线性结构。

在这里插入图片描述

3、描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。（6 分）

1、头结点：头结点是在链表的首元结点之前附设的一个结点。
2、首元结点：首元结点是指链表中存储线性表中第一个数据元素a1的结点。
3、头指针：头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针

4、简述线性表、队列和堆栈这三种数据类型的相同点和差异处。

相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。
不同点： ①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。 ② 用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。

5、在程序设计中，可采用下列三种方法实现输出和输入:

（1）通过 scanf 和printf语句;
(2) 通过函数的参数显式传递; (3) 通过全局变量隐式传递。试讨论这三种方法的优缺点。（6分)

(1) 用scanf和printf直接进行输入输出的好处是形象、直观，但缺点是需要对其进行格式控制，较为烦琐，如果出现错误，则会引起整个系统的崩溃。
(2) 通过函数的参数传递进行输入输出，便于实现信息的隐蔽，减少出错的可能。
(3) 通过全局变量的隐式传递进行输入输出最为方便，只需修改变量的值即可，但过多的全局变量使程序的维护较为困难。

6、试着描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。（6 分）

数据结构是指相互之间存在一定关系的数据元素的集合。而抽象数据类型是指一个数据结构以及定义在该结构上的一组操作。程序设计语言中的数据类型是一个值的集合和定义在这个值集上一组操作的总称。

7、针对二叉树，回答以下问题：
（1）具有 n 个结点的二叉树的最小深度是多少？最大深度是多少？（4 分）
（2）具有 n 个结点的完全二叉树中有多少个叶子结点？有多少个度为 2 的结点？（4 分）
（3）具有 n0个叶子结点的完全二叉树中共有多少个结点？（4 分）

8、一个带权无向图的最小生成树是否一定唯一？在什么情况下构造出的最小生成树可能不唯一？（6 分）

一个带权无向图的最小生成树不一定是唯一的。从Kruskal算法构造最小生成树的过程可以看出，当从图中选择当前权值最小的边时，如果存在多条这样的边，并且这些边与已经选取的边构成回路，此时这些边就不可能同时出现在一棵最小生成树中，对这些边的不同选择结果可能会产生不同的最小生成树

9、设G为有n个顶点的无向连通图，证明G至少有n-1 条边。（7分）

假设使用n-1条无向边可以使得含有n个顶点得无向图连通。

①当n=1时，成立

②设当n=k时，使用k-1条无向边可以使得无向图连通

③当n=k+1时，因为k-1条无向边可以使得k个顶点连通，则无向图G有k+1个顶点，使用k-1条无向边将k个顶点连通后，无向图G有两个连通分量，从两个连通分量中各取一个顶点建立一条无向边则使得整个图连通，即使用k条无向边可以使得含有n个顶点的无向图连通，成立。

又因为一条边仅可以连接两个顶点，故当无向图G的顶点数为n，显然n-2条无向边无法使得无向图连通。

由此可得，G为有n个顶点的无向连通图至少有n-1 条边证明成立。

10、什么是线索二叉树？简述创建线索二叉树的目的，以及建立线索二叉树的思路

规定若无左子树则令lchild指向其前驱结点；若无右子树，则令rchild指向其后继结点，还需要增加两个标志域标识指针域是指向左右孩子还是指向前驱后继，以这种结构构成的二叉链表作为二叉树的存储结构，成为线索链表，加上线索的二叉树称为线索二叉树。
目的：直接从二叉树上得到某结点在中序或者先序或后序遍历方式下的直接前驱和直接后继。

思路：线索化的实质是在按照某种遍历次序进行遍历二叉树的过程中修改结点的空指针，使其指向其在该遍历次序下的直接前驱或直接后继的过程。

11、给定一棵二叉链表存储的二叉树，试用文字描述判定一棵二叉树是否是完全二叉树的算法基本思想。

思路1：对二叉树进行广度优先搜索，如果访问到了null结点，把null结点也入队，并且设置一个state 标记为true。如果在state为true的情况下访问到了一个非空结点则其一定不是完全二叉树（也即空结点只能存在最后一层的最右边）。

思路2：把一颗树的节点（包括空节点）按层序遍历排成一行，当且仅当存在两个相邻节点：前一个为null，后一个不为null时，才不是完全二叉树。

12、已知一棵完全二叉树共有67 个结点，试求: （7分）

(1) 树的深度；(2) 度为1的结点数； (3) 叶子结点数；

（1） $\lceil log_2^{67+1} \rceil$ = 7

（2） 67为奇数，0个度为1的结点

（3） $n 0 = n 2 + 1, n 1 = 0, n 0 + n 1 + n 2 = 67, n 0 = 34$

13、设二维数组 $n u m [1 \dots . m, 1 \dots n]$ 含有 $m * n$ 个整数，请分析判断数组中元素是否互不相同的算法的时间复杂度。（8 分）

法一：四重循环枚举，时间复杂度 $O（n^2m^2）$
法二：将所有元素存入一个新的数组中，再对这个数组进行快速排序，随后遍历数组，判断前后两个元素是否相同。时间复杂度 $O(nmlog_2{nm})$
法三：空间换时间的思想，采用哈希表记录冲突，时间复杂度 $O （ nm ）$

14、由 n 个权值构成的哈夫曼树共有多少个结点？（4 分）为什么？（4 分）

$2 n - 1$ 个结点。哈夫曼树中没有度为1的结点， $n$ 个权值构造即有 $n$ 个度为0的结点,又因为 $n 0 = n 2 + 1$ ,因此共有 $n 0 + n 1 + n 2 = 2 n - 1$ 个结点。

15、设 Huffman 编码的长度不超过 4，若已对两个字符编码为 01 和 11，则最多还可以对多少个字符编码，为什么？(7 分）

应用题：

树：二叉树的中序，前序，后序递归与非递归遍历,以及根据前序+中序建树，或者中序+后序，或层序+中序构造一颗二叉树, 二叉树转换成森林以及森林转化为二叉树,二叉树排序树的构造、插入、删除,B-树的插入与删除，哈夫曼树，哈夫曼编码的构造，计算WPL， DFS, BFS 以及其生成树
散列表：再散列法（即 $+ 1 ， + 2 ， + ... ， + n$ ），平法探测法(即 $1^2 , -1^2 , + 2^2, -2^2 ... + n^2, -n^2$ )，求ASL
图的应用：邻接表，逆邻接表，邻接多重表的画图，Dijkstra算法、Floyd算法求最短路手算过程， Kruskal和Prim算法构造最小生成树，拓扑排序算法以及DFS求拓扑序，并查集算法，AOE网中求出所有事件和活动允许发生的最早及最晚时间,并给出关键路径
排序算法：简单选择排序，直接插入排序，希尔排序，冒泡排序，快速排序，堆排序，链式基数排序，归并排序等等的模拟
关于堆排序：升序排序构造大根堆降序排序构造小根堆

1、试问执行以下串函数会产生怎样的输出结果？(6 分)

void compute( ) {
     StrAssign(s, ’This is a book’); 
     // s = "This is a book"
     Replace(s, SubString(s,3,7), ’ese are’);
     // s = "These are book"
     StrAssign(t, Concat(s, ’s’));
     // t = "These are books"
     StrAssign(u, ’mnmnmnmnmnmn’);
     // u = 
     StrAssign(v, SubString(u,6,3)); // v = "nmn"
     StrAssign(w, ’c’); // w = "c"
     printf(‘t=’, t, ’ v=’, v, ’ u=’, Replace(u, v, w));
     // u = "mcmcmc"
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2、阅读如下程序，写出此程序的输出结果（其中栈的元素类型为char）。

void main ( ) 
{ 	 Stack S;
     char x, y;
     InitStack(S);
     x='y'; y='s' ; 
     Push(S,x); Push(S,y);
     Pop(S,x); Push(S,'k'); Push(S,x);
     while(!StackEmpty(S)) {Pop(S,y); printf(y);}
 	 // ans = Sky
 }
1
2
3
4
5
6
7
8
9
10

2、设有一段正文是由字符集{A,B,C,D,E,F}组成的，正文长度为 100 个字符，其中每个字符在正文中出现的次数分别为 17,12,5,28,35,3。若采用 Huffman 编码对这段正文进行压缩存储，请完成如下工作：（10 分）
(1) 构造出 Huffman 树(规定权值较小的结点为左子树);
(2) 写出每个字符的 Huffman 编码；
(3) 计算按 Huffman 编码压缩存储这段正文共需要多少个字节(设每个字节为 8 位二进制位组成；
(4) 若有另一段正文的二进制编码序列为 01101010110011,请用(2)的 Huffman 编码将它翻译成所对应的正文。

（1）略
（2） A ：00, B: 011, C:0101, D:10, E:11, F:0100
（3） $2 * (17 + 28 + 35) + 12 * 3 + 4 * (3 + 5) = 228 bi t = 228/8 B = 28.5 B$
（4） BABCE

3、给定图3所示带权有向图及其邻接矩阵，利用Floyd算法，求每一对顶点之间的最短路径及其路径长度（要求写出求解过程）。（12分）

在这里插入图片描述

4、设有一组关键字(33,41,20,24,30,13,01,67), 采用散列函数H(key)=(3*key)%11, 采用线性探测再散列解决冲突, Hi=(H(key)+di)%11,其中di=1,2,…,10. 试在0～10的散列地址空间中对该关键字序列（按从左到右的次序）构造散列表，并计算在查找概率相等的前提下，查找成功时的平均查找长度。（10分）

5、对于给定11个数据元素的有序表T=｛2,3,10,15,20,25,28,29,30,35,40｝采用折半查找，请回答以下问题。（本题共三小题，前两小题各2分，第三小题4分，共计8分）

（1）若查找给定值为20的元素，将依次与表中哪些元素比较？

（2）若查找给定值为26的元素，将依次与哪些元素比较？

（3）假设查找表中每个元素的概率相同，求查找成功时的平均查找长度和查找不成功时的平均查找长度

算法填空与算法设计题相关算法汇总

线性表：单链表创建，单链表就地逆置，单链表插入元素，双链表直接插入排序，删除有序单链表中所有重复的元素，删除单链表中指定范围内的元素。
栈，数组，队列：汉诺塔问题，括号匹配问题。
树：二叉排序树的查找算法，树的非递归的先序，中序后序遍历算法。
图论算法：①邻接矩阵与邻接表的图结构；②拓扑排序，Dijkstra算法，Floyd算法，Kruskal算法，Prim算法；③哈夫曼树的构造算法。
排序算法：快速排序算法。
非常规算法：文件读写，找鞍点，判断回文串，进制转换，判断重复元素；

算法设计题

一、线性表部分

1、设计算法: 输入 n 个元素的值，创建带头结点的单链线性表 L。

typedef struct LNode {
    int data;           //数据域
    struct LNode *next; //指针域
} LNode, *LinkList;

//逆向建立单链表
LinkList List_headInsert(LinkList &L, int n) {
    LNode *s;
    L = (LNode *) malloc(sizeof(LNode)); //创建头结点
    L->next = nullptr; //初始化为空链表
    while (n--) {
    	int x;
    	cin >> x;
        s = (LNode *) malloc(sizeof(LNode)); //创建新结点
        s->data = x;
        s->next = L->next;
        L->next = s;
    }
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2、设计将两个有序链表合并为一个有序链表的算法. 假设有序链表的元素按照非递减排列.(10 分）

typedef struct LNode {
    int data;           //数据域
    struct LNode *next; //指针域
} LNode, *LinkList;

// 两个有序链表合并
void merge(LinkList &L1, LinkList &L2) {
    LinkList pa = L1->next, pb = L2->next;
    LinkList pc = pa;
    while (pa && pb) {
        if (pa->data <= pb->data) {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        } else {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb;
    free(L2);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3、已知线性表中的元素按值递增有序排列，并以带头结点的单链表作存储结构。试编写算法，删除表中所有值大于 x 且小于 y 的元素（若表中存在这样的元素）, 同时释放被删除结点空间。（10 分）

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

//删除递增有序序列链表中大于x小于y的所有元素
LinkList DeleteElements(LinkList &L, int x, int y) {
    LNode *p, *pre, *q;
    p = L->next;
    while (p && p->data <= x) { //查找第一个大于x的结点
        pre = p;
        p = p->next;
    }
    if (p) {
        //查找第一个大于y的结点
        while (p && p->data < y) p = p->next;
        //修改指针
        q = pre->next;
        pre->next = p;
        //释放结点空间
        while (p != q) {
            LNode *s = q->next;
            delete q;
            q = s;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

4、已知 f 为单链表的表头指针，链表中存储的都是整型数据，请写出实现下列运算的递归算法，求（1）链表中最大整数；（2）所有整数的平均值。（10 分）

int Max(LinkList &L) {
    int res = 0;
    if (!L->next) return res;
    res = Max(L->next);
    return res >= L->data ? res : L->data;
}
int Length(LinkList &L) {
    if (!L) return 0;
    return Length(L->next) + 1;
}
double getSum(LinkList &L) {
    if (!L) return ;
    return getSum(L->next) + L->data;
}
void main() {
    LinkList L = NULL;
    creatLinkList(L);
    LinkNode* p = L->next;
    int MaxNum = Max(p);
    int length = Length(p);
    double avg = getSum(p) / length * 1.0;
    cout << MaxNum << ' ' << avg << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

5、设计在顺序有序表中实现折半查找的算法（10分）。

typedef struct {
    int data[MaxSize]; //静态分配内存
    int length;
} SqList;

int BinarySearch(SqList &L, int x) {
    int l = 0, r = L.length - 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (L.data[mid] == x) {
            return mid;   //查找成功
        } else if (L.data[mid] < x) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return -1;  //查找失败
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

6、试写出一种算法在带头结点的单链表结构上实现线性表操作 Length(L)。（8 分）

int Length(List L) {
    List p = L->next;
   	int res = 0;
    while (p != nullptr) {
        p = p->next;
        res ++;
    }
    return res;
}
1
2
3
4
5
6
7
8
9

7、已知由一个线性链表表示的线性表中含有三类字符的数据元素(如:字母字符、
数字字符和其他字符)，试编写算法将该线性表分割为三个循环链表，其中每个循
环链表表示的线性表中均只含一类字符。（10 分）(严蔚敏书2.33)

//把单链表L的元素按类型分为三个循环链表.CiList为带头结点的单循环链表类型.
Status LinkList_Divide(LinkList &L, CiList &A, CiList &B, CiList &C) {
    s = L->next;
    A = (CiList *) malloc(sizeof(CiLNode));
    p = A;
    B = (CiList *) malloc(sizeof(CiLNode));
    q = B;
    C = (CiList *) malloc(sizeof(CiLNode));
    r = C; //建立头结点
    while (s) {
        if (isalphabet(s->data)) {
            p->next = s;
            p = s;
        } else if (isdigit(s->data)) {
            q->next = s;
            q = s;
        } else {
            r->next = s;
            r = s;
        }
    }//while
    p->next = A;
    q->next = B;
    r->next = C; //完成循环链表
}//LinkList_Divide 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

8、试编写一个算法，在链式存储结构上实现直接插入排序算法。(8 分）

typedef struct LNode {
    int data;           //数据域
    struct LNode *next; //指针域
} LNode, *LinkList;

//在链表上实现直接插入排序算法
LinkList InsertSort(LinkList &L) {
    if (!L->next) return nullptr;
    LNode *sorted = L->next;    //表示已排序元素
    LNode *cur = sorted->next;  //等待排序元素
    while (cur != nullptr) {
        if (sorted->data <= cur->data) {    //若已排最后一个元素小于待排元素，则不需要排序
            sorted = sorted->next;
        } else {
            LNode *pre = L; //头结点
            while (pre->next->data <= cur->data) {
                pre = pre->next; //从头结点开始遍历找到第一个大于待排元素的结点
            }
            sorted->next = cur->next; //插入待排结点
            cur->next = pre->next;
            pre->next = cur;
        }
        cur = sorted->next;
    }
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

9、试编写一个算法，在链式存储结构上实现简单选择排序算法

typedef struct LNode {
    int data;           //数据域
    struct LNode *next; //指针域
} LNode, *LinkList;

void LinkListSelectSort(LinkList &L) {
    LinkList p = L->next, q, r;
    //本算法一趟找出一个关键字最小的结点，其数据和当前结点进行交换;
    // 若要交换指针， 则须记下当前结点和最小结点的前驱指针
    while (p != nullptr) {
        q = p->next;
        r = p;
	while (q != nullptr) {
            if (q->data < r->data) r = q;
            q = q->next;
        }
        if (r != q)
            swap(r->data, p->data);
        p = p->next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

10、设一个带头结点的单链表 L，数据元素为整数，其中大部分为正数，少数为负数，编写函数，实现将负数结点移到链表尾部，并返回调整后链表中第一个负数结点的位置。要求先给出算法思想，再写出相应算法。（11 分）

typedef struct LNode {
    int data;           //数据域
    struct LNode *next; //指针域
} LNode, *LinkList;

//新建链表B，将负数移到B中，最后接上
LinkList moveList(LinkList &L) {
    if (!L) return nullptr;
    LinkList B = (LinkList)malloc(sizeof(LNode));
    LinkList pre = L, p = L->next;
    while (p) {
        //将负数移到B中
        if (p->data < 0) {
            //pre->next = p->next;
            p->next = B->next;
            B->next = p;
            p = pre->next;
        } else {
            pre = pre->next;
            p = p->next;
        }
    }
    pre->next = B->next;//将B接上
    free(B);
    return pre->next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

二、树

1、试编写统计二叉树中叶子结点个数的算法。（830-2012，830-2017)

struct TreeNode {
	int data;
	TreeNode *left, *right;
	TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

int CountLeaves(TreeNode *root) {
    if (!root) return 0;
    if (!root->left && !root->right) return 1;
    return CountLeaves(root->left) + CountLeaves(root->right);
}
1
2
3
4
5
6
7
8
9
10
11

2、设有一整型数组 w 保存 n 个字符的权值（均大于 0），请写出

(1) 构造赫夫曼树(Huffman)的算法。（8 分）
(2) 求各字符赫夫曼编码的算法。（7 分）

#include 
#include 

using namespace std;

const int inf = 0x3f3f3f3f;

typedef char **HuffmanCode;
typedef double DataType;

typedef struct {
    DataType weight;            //结点的权值
    int parent, lchild, rchild; //结点的双亲、左孩子、右孩子的下标
} HTNode, *HuffmanTree;         //动态分配数组存储哈夫曼树


//选择两个其双亲域为0,且权值最小的结点,并返回它们在HT中的序号
void Select(HuffmanTree HT, int n, int &idx1, int &idx2) {
    double minv1 = inf, minv2 = inf;
    for (int i = 1; i <= n; i++) {
        if (HT[i].weight < minv1 && HT[i].parent == 0) {
            minv1 = HT[i].weight;
            idx1 = i;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (HT[i].weight < minv2 && i != idx1 && HT[i].parent == 0) {
            minv2 = HT[i].weight;
            idx2 = i;
        }
    }
}

void CreateHuffmanTree(HuffmanTree &HT, DataType *w, int n) {
    if (n <= 1) return;
    int m = 2 * n - 1;//一棵有n个叶子节点的哈夫曼树共有2*n-1个结点
    HT = new HTNode[m + 1];
    for (int i = 1; i <= m; i++) {
        HT[i].parent = 0, HT[i].lchild = 0, HT[i].rchild = 0;
    }
    for (int i = 1; i <= n; i++) {  //输入前n个单元中叶子结点的权值
        HT[i].weight = w[i];
    }
    //通过n-1次的选择、删除、合并来创建哈夫曼树
    for (int i = n + 1; i <= m; i++) {
        int idx1, idx2;
        Select(HT, i - 1, idx1, idx2);
        //让最小两个节点的双亲指向这个新数组下标
        HT[idx1].parent = HT[idx2].parent = i;
        //得到新结点i，从森林中删除idx1,idx2，将idx1和idx2的双亲域由0改为i
        HT[i].lchild = idx1, HT[i].rchild = idx2;//左孩子指向最小数据的下标，右孩子指向第二小的
        HT[i].weight = HT[idx1].weight + HT[idx2].weight;//让两个数据的权值相加变为新结点权值
    }
    // 输出哈夫曼树
    printf("哈夫曼树为:>\n");
    printf("下标   权值     父结点   左孩子   右孩子\n");
    printf("0                                  \n");
    for (int i = 1; i <= 2 * n - 1; i++) {
        printf("%-4d   %-6.2lf   %-6d   %-6d   %-6d\n", i,
               HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
    }
    printf("\n");
}

void CreateHuffmanCode(HuffmanTree &HT, HuffmanCode &HC, int n) {
    HC = new char *[n + 1];
    char *code = new char[n];
    code[n - 1] = '\0';
    for (int i = 1; i <= n; i++) {
        int start = n - 1;
        int tmp = i;
        int p = HT[i].parent;
        while (p != 0) {
            HT[p].lchild == tmp ? code[--start] = '0' : code[--start] = '1';
            tmp = p;
            p = HT[p].parent;
        }
        HC[i] = new char[n - start];
        strcpy(HC[i], &code[start]);
    }
    delete[]code;
    printf("哈夫曼编码为：\n");
    for (int i = 1; i <= n; i++) {
        printf("数据%.2lf的编码为：%s\n", HT[i].weight, HC[i]);
    }
}

int main() {
    int n;
    cin >> n;
    auto *w = new DataType[n + 1];
    // 一组测试数据
    // 8
    // 0.05 0.29 0.07 0.08 0.14 0.23 0.03 0.11
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    auto HT = new HTNode;
    CreateHuffmanTree(HT, w, n);// 创建哈夫曼树

    HuffmanCode HC;
    CreateHuffmanCode(HT, HC, n);// 创建哈夫曼编码
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

3、假设二叉树采用二叉链存储结构存储，试编写一个非递归算法，输出先序遍历序列中第k个结点的数据值。（10分）

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void preOrder(TreeNode *root, int k) {
    stack<TreeNode *> s;
    s.push(root);
    int cnt = 0;
    while (!s.empty()) {
        auto t = s.top();
        cnt ++;
        if (cnt == k) {
        	cout << t->val << ' ';
        }
        // 先访问右子树 再访问左子树即可
        if (t->right) s.push(t->right);
        if (t->left) s.push(t->left);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4、试编写算法，从大到小输出二叉排序树中所有的值不小于x的关键字。

typedef struct bitTree{
    elemType data;
    bitTree *lchild, *rchild;
};
void printBt(bitTree &p){
    if(!p) return;
    if(p->data < x) printBt(p->rchild);
    else {
        printBt(p->rchild);     //遍历右子树
        print(p->data);         //打印关键字
        printBt(p->lchild);     //遍历左子树
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

5、已知一棵具有 n 个结点的完全二叉树被顺序存储在一维数组 A[n]中，试着编程一个算法输出 A[i]的结点的双亲与所有孩子。（10 分）

int A[N];

void child(int A[], int n, int u) {
    if (u <= n) {
        cout << A[u] << ' ';
        child(A, n, u * 2);
        child(A, n, u * 2 + 1);
    }
}

void solve() {
    //假设A[]存储从1~n
    for (int i = 1; i <= n; i++) {
        if (i != 1) {
            cout << "结点" << i << "的双亲为：" << A[i / 2] << endl;
        } else {
            cout << i << "无双亲" << endl;
        }
        cout << "结点" << i << "的孩子为：";
        child(A, n, i * 2);
        child(A, n, i * 2 + 1);
        cout << endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

6、设树的存储结构为孩子兄弟链表，试编写算法，输出树中所有从根到叶子的路径。（10 分）

//孩子-兄弟表示法, 称二叉树表示法，或二叉链表表示法
//链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点
typedef struct CSNode {
    int data;
    struct CSNode *firstchild, *nextsib;
} CSNode, *CSTree;

//设树的存储结构为孩子兄弟链表，试编写算法，输出树中所有从根到叶子的路径。
void printPath(CSTree &T, int path[], int cnt) {
    if (!T) return;
    path[cnt++] = T->data;
    // 如果是叶子节点，打印路径
    if (!T->firstchild) {
        printf("Path:");
        for (int i = 0; i < cnt; i++) {
            printf("%d ", path[i]);
        }
        printf("\n");
    } else {
        // 递归处理孩子节点
        printPath(T->firstchild, path, cnt);
    }
    // 递归处理下一个兄弟节点
    printPath(T->nextsib, path, cnt);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

7、假设二叉树采用二叉链表存储，试写出中序遍历二叉搜索树的的非递归算法，要求写出二叉树的数据类型（7分）；

#define MAXTSIZE 100
typedef struct BiTNode {
    int data;                           //结点数据域
    struct BiTNode *lchild, *rchild;    //左右孩子指针
} BiTNode, *BiTree;

typedef struct Stack {
    BiTree st[MAXTSIZE];
    int top = -1;
};

void InitStack(Stack &S);
void Push(Stack &S, BiTNode *e);
void Pop(Stack &S, BiTNode *e);
bool StackEmpty(Stack S);

//中序遍历二叉树T的非递归算法
void InOrderTraverser(BiTree T) {
    Stack S;
    InitStack(S);
    BiTree p = T;
    auto *q = new BiTNode;
    while (p || !StackEmpty(S)) {
        if (p) {    //p非空
            Push(S, p); //根指针栈
            p = p->lchild;    //根指针进栈，遍历左子树
        } else {
            Pop(S, q);  //退栈
            cout << q->data;  //访问根结点
            p = q->rchild;    //访问右子树
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

8、假设二叉树采用二叉链表存储结构，试编写一个非递归算法，输出中序遍历序列中第 k个结点的数据值。(8 分)

struct TreeNode {
    int val;
    TreeNode *left, *right;
    explicit TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

int findInorderK(TreeNode *T, int k) {
    stack<TreeNode*> st;
    int cnt = 0;
    TreeNode *p = T;
    while (p || !st.empty()) {
        if (p) {
            st.push(p);
            p = p->left;
        } else {
            st.pop();
            cnt ++;
            if (cnt == k) return p->val;
            p = p->right;
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

9、补充关于树的遍历的非递归算法模板（自用）

struct TreeNode {
    int val;
    TreeNode *left, *right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void preOrder(TreeNode *root) {
    stack<TreeNode *> s;
    s.push(root);
    while (!s.empty()) {
        auto t = s.top();
        cout << t->val << ' ';
        // 先访问右子树 再访问左子树即可
        if (t->right) s.push(t->right);
        if (t->left) s.push(t->left);
    }
}

void inOrder(TreeNode *root) {
    stack<TreeNode *> s;
    TreeNode *p = root;
    while (p || !s.empty()) {
        while (p) { // 一直向左并将沿途结点压入堆栈
            s.push(p);
            p = p->left;
        }
        // 每次取出栈顶，访问它，再访问其右子树
        p = s.top();
        s.pop();
        cout << p->val << ' ';
        p = p->right;
    }
}

void postOrder(TreeNode *root) {
    if (!root) return;
    vector<int> res;
    stack<TreeNode *> st;
    st.push(root);
    while (!st.empty()) {
        auto t = st.top();
        st.pop();
        if (t->left) st.push(t->left);
        if (t->right) st.push(t->right);
    }
    for (int i = res.size() - 1; i >= 0; i--) {
        cout << res[i] << ' ';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

三、基础图论

1、设计一数据结构，用来表示图的邻接矩阵存储结构（包括弧的结构和图的结构）。(5 分）

typedef int Status;
typedef char VertexType;
typedef int EdgeType;

typedef struct {
    VertexType vex[MAXSIZE];         //顶点表
    EdgeType arcs[MAXSIZE][MAXSIZE]; //邻接矩阵
    int vexnum, arcnum;              //图的当前点数和边数
} MGraph;
1
2
3
4
5
6
7
8
9

2、设计一个图的数组表示存储结构，并编写采用数组表示法构造一个无向网的算法。（14分）

typedef struct {
    int Vec[MaxSize];
    int Edge[MaxSize][MaxSize];
    int vexnum, arcnum;
} MGraph;

void Init(MGraph &G, int n) {
    G.vexnum = n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            G.Edge[i][j] = INF;
        }
    }
    for (int i = 1; i <= n; i++) {
        G.Edge[i][i] = 0;
    }
}

void creatUDG_By_AdjacentMatrix(MGraph &G, int n) {
    int u, v, w;
    Init(G, n); // 初始化邻接矩阵
    while (cin >> u >> v >> w) {
        if (u == 0 || v == 0) break;
        if (u < 0 || v < 0 || u > n || v > n) continue;
        G.Edge[u][v] = w;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

3、编写一个算法根据用户输入的偶对（以输入0表示结束）建立其有向图的邻接表（设有n个顶点）。

const int MaxVertexNum = 500, INF = 0x3f3f3f3f;

typedef struct ArcNode {
    int adjvex;
    struct ArcNode *nextarc;
    // InfoType other-info;
} ArcNode;

typedef struct VNode {
    int data;
    ArcNode *firstarc;
} VNode, Adjlist[MaxVertexNum];

typedef struct {
    Adjlist vertices;
    int vexnum, arcnum;
} ALGraph;

void creatDAG_By_AdjacentMatrix(ALGraph &G, int n) {
    //初始化顶点表
    G.vexnum = n;
    for (int i = 1; i <= G.vexnum; i++) {
        G.vertices[i].data = i;
        G.vertices[i].firstarc = nullptr;
    }
    //输入偶对构造边表
    int u, v;
    while (cin >> u >> v && u, v) {
        if (u < 0 || v < 0 || u > G.vexnum || v > G.vexnum || u == v)
            continue;
        G.arcnum ++;
        auto *p = new ArcNode;
        p->adjvex = v;
        p->nextarc = G.vertices[u].firstarc;
        G.vertices[u].firstarc = p;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

4、假设在 n 个城市之间的公路网中，已知直达城市之间的乘车费用，各城市之间均存在通路，从 V0城市开始乘车，经过若干个城市到 S 城市，有多条路线可以选择，设计算法：选择一条最节省费用的路线。

（1）选择一种合适的数据结构，描述 n 个城市之间的公路网；（4 分）
（2）用伪代码描述求从 V0城市到 S 城市最节省费用的路线。（8 分）

typedef struct {
    int Vec[MaxSize];
    int Edge[MaxSize][MaxSize];
    int vexnum, arcnum;
} MGraph;

int vis[MaxSize], dist[MaxSize], path[MaxSize];

void Dijkstra(MGraph &G, int n, int S, int V0) {
    memset(vis, false, sizeof vis);
    memset(dist, 0x3f, sizeof dist);
    vis[S] = true, dist[S] = 0;
    for (int i = 0;i < G.vexnum; i++) {
        int t = -1;
        for (int j = 1; j <= G.vexnum; j++)
            if (!vis[j] && (t == -1) || dist[t] > dist[j])
                t = j;
        vis[t] = true;
        for (int j = 0; j < G.vexnum; j++) {
            if (dist[j] > dist[t] + G.Edge[t][j]) {
                dist[j] = dist[t] + G.Edge[t][j];
                path[j] = t;
            }
        }
    }
    cout << "最节省费用的路线为 : " << endl;
    int k = 0;
    int ans[MaxSize];
    for (int i = V0; i > 1; i = path[i]) {
        ans[k ++] = path[i];
    }
    for (int i = 0; i < k; i++) {
        cout << ans[i] << " ";
        if (i == k - 1) cout << endl;
    }
    cout << "总费用为：" << dist[V0] << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

5、设计AOV网络拓扑排序的算法（12分）。

#define MaxVertexNum 100

typedef struct ArcNode {    //边表结点
    int adjvex;             //该弧所指向的顶点位置
    struct ArcNode *nextarc;   //指向下一条弧的指针
    //infoType info;        //和边相关的信息
} ArcNode;

typedef struct VNode {      //顶点表结点
    int data;               //顶点信息
    ArcNode *firstarc;      //指向第一条依附该顶点的弧的指针
} VNode, AdjList[MaxVertexNum];

typedef struct {
    AdjList vertices;       //邻接表
    int vexnum, arcnum;     //图的顶点和弧数
} ALGraph;                  //表示以邻接表存储的图类型

int degree[MaxVertexNum];

void topsort(ALGraph &G) {
    queue<int> q;
    for (int i = 1; i <= G.vexnum; i++)
        if (!degree[i])
            q.push(i);

    vector<int> ans;
    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        ans.push_back(t);
        for (auto *p = G.vertices[t].firstarc; p; p = p->nextarc) {
            int j = p->adjvex;
            if (--degree[j] == 0)
                q.push(j);
        }
    }
    if (ans.size() < G.vexnum) cout << -1;
    else {
        for (auto c: ans) cout << c << ' ';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

6、给定带权有向图 G 和源点 V0, 设计 V0到其余顶点的最短路径.(15 分）(见第4题)

7、设计一个算法，求不带权无向连通图 G 中距离顶点 v 的最远顶点。（15 分）（BFS求最长路）

cosnt int MaxSize = 500;

typedef struct {
    int Vec[MaxSize];
    int Edge[MaxSize][MaxSize];
    int vexnum, arcnum;
} MGraph;

int dist[N];
bool vis[N];

void BFS(MGraph &G, int v) {
    queue<int> q;
    q.emplace(v);
    dist[v] = 0;
    while (!q.empty()) {
        auto t = q.front(); q.pop();
        for (int j = 0; j < G.vexnum; j++) {
            if (!st[t] && dist[t] < G.Edge[t][j]) {
                dist[j] = dist[t] + 1;
                st[j] = true;
                q.emplace(j);
            }
        }
    }
    int maxdist = -1, res = -1;
    for (int i = 0; i < n; i++) {
        if (dist[i] > maxdist) {
            maxdist = dist[i];
            res = i;
        }
    }
    cout << res << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

8、已知 n 个顶点的带权图用邻接矩阵表示，试编写算法实现用 kruskal 算法构造最小生成树。（15 分)（830-2017）

const int MaxSize = 500, INF = 0x3f3f3f3f;
typedef struct {
    int Vec[MaxSize];
    int Edge[MaxSize][MaxSize];
    int vexnum;
    int arcnum;
} MGraph;

struct Edge {
    int u, v, w;
    bool operator<(const Edge &o) const {
        return w < o.w;
    }
};

void Init(MGraph &G, int n) {
    G.vexnum = n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            G.Edge[i][j] = INF;
        }
    }
    for (int i = 1; i <= n; i++) {
        G.Edge[i][i] = 0;
    }
}

void creatDAG_By_AdjacentMatrix(MGraph &G, int n) {
    int u, v, w;
    Init(G, n); // 初始化邻接矩阵
    while (cin >> u >> v >> w) {
        if (u == 0 || v == 0) break;
        if (u < 0 || v < 0 || u > n || v > n) continue;
        G.Edge[u][v] = w;
    }
}

int p[N];

int find(int x) {
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

Edge edges[MaxSize * MaxSize];
int cnt = 0, res = 0;

void Kruskal(MGraph &G) {
    for (int i = 0; i <= G.vexnum; i++) p[i] = i;
    for (int i = 0; i < G.vexnum; i++) {
        for (int j = 0; j < G.vexnum; j++) {
            if (G.Edge[i][j] != 0) {
                edges[cnt++] = {i, j, G.Edge[i][j]};
            }
        }
    }
    sort(edges, edges + cnt);
    int k = 0;
    for (int i = 0; i < cnt; i++) {
        int a = edges[i].u, b = edges[i].v, c = edges[i].w;
        if (find(a) != find(b)) {
            p[find(a)] = find(b);
            res += c;
            k++;
        }
    }
    if (k < cnt - 1) cout << "impossible!";
    else cout << res << endl;
}

int main() {
    MGraph G;
    creatDAG_By_AdjacentMatrix(G, n);
    Kruskal(G);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

9、采用邻接表存储结构，编写一个算法，判别无向图中任意给定的两个顶点之间是否存在一条长度为 k 的简单路径。（10 分）(严蔚敏书7.27)

const int MAXSIZE = 1e5 + 7;

int visited[MAXSIZE];

//判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径
int exist_path_len(ALGraph G, int i, int j, int k) {
    if (i == j && k == 0) return 1; //找到了一条路径,且长度符合要求
    else if (k > 0) {
        visited[i] = 1;
        for (p = G.vertices[i].firstarc; p; p = p->nextarc) {
            l = p->adjvex;
            if (!visited[l])
                if (exist_path_len(G, l, j, k - 1)) return 1; //剩余路径长度减一
        }//for
        visited[i] = 0; //本题允许曾经被访问过的结点出现在另一条路径中
    }//else
    return 0; //没找到
}//exist_path_len 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

10、假设无向图G采用邻接表存储，编写程序，判断图G是否连通图，如果是连通图，则返回1，否则返回0。要求先给出算法思想，再写出相应代码（8分）。

#include 

using namespace std;

const int MaxVertexNum = 100;
typedef struct ArcNode {    //边表结点
    int adjvex;             //该弧所指向的顶点位置
    struct ArcNode *nextarc;//指向下一条弧的指针
    //infoType info;        //和边相关的信息
} ArcNode;

typedef struct VNode {      //顶点表结点
    int data;               //顶点信息
    ArcNode *firstarc;      //指向第一条依附该顶点的弧的指针
} VNode, AdjList[MaxVertexNum];

typedef struct {
    AdjList vertices;   //邻接表
    int vexnum, arcnum; //图的顶点和弧数
} ALGraph;               //表示以邻接表存储的图类型
/*
算法1：并查集，将所有连通的两点加到一个集合中，若最后只有一个集合则图连通，否则图不连通。
*/

int fa[MaxVertexNum];   //并查集父亲结点

void init(int n) {      //并查集初始化
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
}

int find(int x) {       //寻找父节点
    if (x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}

void Union(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx != fy) fa[fy] = fx;
}

bool IsConnection(ALGraph &G) {
    init(G.vexnum);
    int cnt = 0;
    for (int i = 0; i < G.vexnum; i++) {
        for (ArcNode *p = G.vertices[i].firstarc; p; p = p->nextarc) {
            Union(i, p->adjvex);
            cnt++;
        }
    }
    return cnt == G.vexnum;
}

/*算法2：DFS，从任一结点开始，进行一次深度优先遍历。
 * 深度优先遍历的结果是一个图的连通分量。当一次遍历没有访问到所有结点，
 * 那么就说明图是不连通。开一个visit[]数组记录是否访问过某结点，
 * cnt记录遍历过的结点数，若最后遍历的结点数`cnt!=n`则不连通，否则连通。
 * */

bool Visited[MaxVertexNum];
int cnt = 0;

void DFS(ALGraph &G, int u) {
    Visited[u] = true;
    cnt++;
    for (ArcNode *p = G.vertices[u].firstarc; p; p = p->nextarc) {
        int w = p->adjvex;
        if (!Visited[w]) {
            DFS(G, w);
        }
    }
}

void solve_by_DFS(ALGraph &G) {
    fill(Visited, Visited + G.vexnum, false);
    DFS(G, 0);
    cout << (cnt == G.vexnum) ? "连通！" : "不连通！";
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

11、试编写一个算法，在有向图 G 中，判定从顶点Vi到顶点Vj是否有通路。（10 分）

#define MAXSIZE 100

int visited[MAXSIZE];

bool DFS(ALGraph &G, int vi, int vj) {
    if (vi == vj) return true;
    visited[vi] = true;
    for (ArcNode *p = G.vertices[vi].firstarc; p; p = p->nextarc) {
        int j = p->adjvex;
        if (!visited[j] && DFS(G, j, vj))
            return true;
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

12、设图G有n个顶点，按照如下提示设计一个算法，将G的邻接矩阵转换为对应的邻接表。

typedef int InfoType;
typedef int Vertex;

const int MAXV = 100;

/*G的邻接表存储类型定义如下*/
typedef struct ArcNode {
    int adjvex;
    struct ArcNode *nextarc;
    InfoType weight;
} ArcNode;

typedef struct Vnode {
    Vertex data;
    ArcNode *firstarc;
} VNode;

typedef struct {
    VNode adjlist[MAXV];
    int n, e;
} AdjGraph;

typedef struct {
    int no;
    InfoType info;
} VertexType;
/*G的邻接矩阵存储类型定义如下*/
typedef struct {
    int edges[MAXV][MAXV];
    int n, e;
    VertexType vexs[MAXV];
} MatGraph;

void transfer(MatGraph &G1, AdjGraph &G2) {
    G2.n = G1.n, G2.e = G1.e;
    //初始化顶点表
    for (int i = 0; i < G2.n; i++) {
        G2.adjlist[i].data = i;
        G2.adjlist[i].firstarc = NULL;
    }
    //转换边表
    for (int i = 0; i < G1.n; i++) {
        for (int j = 0; j < G1.n; j++) {
            if (G1.edges[i][j] && i != j) {
                auto *p1 = new ArcNode;
                p1->adjvex = j;
                p1->nextarc = G2.adjlist[i].firstarc;
                G2.adjlist[i].firstarc = p1;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

13 、一个公司在某地区有n个产品销售点，现打算在这个地区的某个销售点上建一个中心仓库，负责向该地区的各个销售点提供销售产品。由于运输线路和公交条件不同，向每个销售点运输一次产品的费用也不相同。若公司每天都会向每个运输点运输一次产品，试设计一个算法，以帮助公司解决应将中心仓库建立在哪个销售点上才能使运输费用达到最低的问题。

typedef int Status;
typedef char VertexType;
typedef int EdgeType;

typedef struct {
    VertexType vex[MAXSIZE];         //顶点表
    EdgeType arcs[MAXSIZE][MAXSIZE]; //邻接矩阵
    int vexnum, arcnum;              //图的当前点数和边数
} MGraph;

void init(MGraph &G) {
    for (int i = 0; i < G.vexnum; i++) {
        for (int j = 0; j < G.vexnum; j++) {
            G.arcs[i][j] = INF;
        }
    }
    for (int i = 0; i < G.vexnum; i++) G.arcs[i][i] = 0;
    for (int i = 0; i < G.arcnum; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G.arcs[u][v] = G.arcs[v][u] = w;
    }
}

void floyd(MGraph &G) {
    for (int i = 0; i < G.vexnum; i++) {
        for (int j = 0; j < G.vexnum; j++) {
            for (int k = 0; k < G.vexnum; k++) {
                G.arcs[i][j] = min(G.arcs[i][j], G.arcs[i][k] + G.arcs[k][j]);
            }
        }
    }
}

void findMinCost(MGraph &G) {
    int minv = INF, res = 0;
    for (int i = 0; i < G.vexnum; i++) {
        int sum = 0;
        for (int j = 0; j < G.vexnum; j++) {
            if (G.arcs[i][j] != INF)
                sum += G.arcs[i][j];
        }
        if (minv > sum) {
            minv = sum;
            res = i;
        }
    }
    cout << "中心仓库应建立在" << res << "号销售点上，且最低消费为：" << minv << endl; 
}

void solve(MGraph &G) {
    init(G);
    floyd(G);
    findMinCost(G);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

四、排序算法（快排划分思想）

1、设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在 $O (n)$ 的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于 Ki，右半部分的每个关键字均大于等于 Ki。（10 分）

void paratition(int a[], int n, int i) {
    int pivot = a[i];
    int low = 0, high = n - 1;
    while (low < high) {
        while (low < high && a[high] >= pivot) high --;
        a[low] = a[high];
        while (low < high && a[low] <= pivot) low ++;
        a[high] = a[low]
    }
   	a[low] = pivot;
}
1
2
3
4
5
6
7
8
9
10
11

2、设计算法，对n个关键字取实数值的记录序列进行整理，以使所有关键字为负值的记录排序在非负值的记录之前（要求尽量减少记录的交换次数）。

void paratition(int a[], int n) {
    int low = 0, high = n - 1;
    while (low < high) {
        while (low < high && a[high] >= 0) high --;
        while (low < high && a[low] <= 0) low ++;
        if (low < high) {
            swap(a[low], a[high]);
            //low ++, high --;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11

3、设有一个长度为n的线性表L采用顺序存储结构存储。设计一个算法，以第一个元素为分界线（基准），将所有小于或等于它的元素移到该元素的前面，将所有大于它的元素移到该元素的后面。要求算法的时间复杂度为O（n），且算法最多只能借助1个辅助变量。

const int MaxSize = 10;

typedef struct {
    int data[MaxSize]; //静态分配内存
    int length;
} SqList;

//快速排序的一次划分操作
void Partition(SqList &L) {
    int pivot = L.data[0];
    int low = 0, high = L.length - 1;
    while (low < high) {
        while (low < high && L.data[high] >= pivot) high--;
        L.data[low] = L.data[high];
        while (low < high && L.data[low] <= pivot) low++;
        L.data[high] = L.data[low];
    }
    L.data[low] = L.data[high];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

4、设有顺序放置的 n 个桶，每个桶中装有一个球，每个球的颜色是红、白、蓝之一。要求重新安排这些球，使得所有红色球在前，所有白色球居中，所有蓝色球居后，重新安排时对每个球的颜色只能看一次，并且只允许交换操作来调整球的位置，请写出以上算法的伪代码。（10 分）Leetcode75.颜色分类

算法思想：顺序扫描线性表，将红色条块交换到线性表的最前面，蓝色条块交换到线性表的最后面。为此，设立三个指针，其中，j为工作指针，表示当前扫描的元素，i以前的元素全部为红色，k以后的元素全部为蓝色。根据j所指示元素的颜色，决定将其交换到序列的前部或尾部。算法的实现如下

const int N = 100;
typedef enum{ 
    Red, White, Blue 
}color;
void divide(int color[], int n) {
    int i = 0, j = 0, k = 0;
    while (j <= k) {
        switch(a[j]) {
            case Red : swap(a[i], a[j]), i ++, j ++; break;
           //红色，则和i交换
            case White : j ++; break; 	//白色 不处理
            case Blue : Swap(a[j], a[k]); k--;
            // 蓝色，则和k交换
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

五、栈、数组、队列的应用

1、试编写出一个判别表达式中左、右小括号是否配对出现的算法。（7分）

bool judge(char *s){
    int cnt = 0;
    //cnt表示当前遍历位置下未形成配对状态下的左括号个数
    for (int i = 0; s[i]; i++) {
        if (s[i] == '(') cnt ++;
        else {
            cnt --;
            if (cnt < 0) return false;
        }
    }
    return cnt == 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

2、编写实现栈的两个基本运算的函数，入栈和出栈（要求采用顺序存储结构）。

#define MAXSIZE 100

struct SElemType {
    int data;
};

typedef struct{
    SElemType *base;
    SElemType *top;
    int stacksize;
} Stack;

bool InitStack(Stack &S) {
    S.base = new SElemType[MAXSIZE];
    if (!S.base) exit(0);
    S.top = S.base;
    S.stacksize = MAXSIZE;
    return true;
}

bool Push(Stack &S, SElemType e) {
    if (S.top - S.base == S.stacksize)
        return false;
    *S.top ++ = e;
    return true;
}

bool Pop(Stack &S, SElemType &e) {
    if (S.top == S.base) return false;
    e = *(--S.top);
    return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

3、如果允许在循环队列的两端都可以进行插入和删除操作。（12 分）

（1）写出循环队列的类型定义；
（2）写出“从队尾删除”和“从队头插入”的算法。

//手写双端队列
class Deque {
private:
    int *deque;
    std::size_t left, right, size;
public:
    Deque(std::size_t);     //构造函数
    inline ~Deque();        //析构函数
    void push_back(int);    //队尾插入
    void push_front(int);   //队头插入
    void pop_back();        //队尾删除
    void pop_front();       //队头删除
    int back();
    int front();
    inline bool empty();    // 判空
    inline bool full();      //判满
};

bool Deque::empty() {
    return (left + 1) % size == right;
}

bool Deque::full() {
    return left == right;
}

void Deque::push_back(int val) {
    if (full()) {
        std::cerr << "Deque is full!" << endl;
    } else {
        deque[right] = val;
        right = (right + 1) % size;
    }
}

void Deque::pop_front() {
    if (empty()) {
        std::cerr << "Deque is empty!" << endl;
        return;
    } else {
        left = (left + 1) % size;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

六、非数据结构中的常规算法

1、写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为 A-Z 这 26 个字母与 0-9 这 10 个数字）。（10 分）

void solve() {
    int hash_map[256] = {0};
    memset(hash_map, 0, sizeof(hash_map));
    ofstream file_outPut("..//test/count.txt", ios::out);
    string str;
    cin >> str;
    int n = str.size();
    for (int i = 0; i < n; i++) {
        hash_map[str[i] - '0']++;
    }
    for (char i = '0'; i <= '9'; i++) {
        file_outPut << i << "的频度为：" << hash_map[i - '0'] << endl;
    }
    for (char c = 'A'; c <= 'Z'; c++) {
        file_outPut << c << "的频度为：" << hash_map[c - '0'] << endl;
    }
    file_outPut.close();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2、请用顺序存储的方式，用 C 语言写出实现把串 S1 复制到串 S2 的串复制函数 strcpy（S1，S2）。（8 分）

char *strcpy(char *a, char *b) {
    if (a != NULL && b != NULL) {
        char *res = a;
        while ((*b++ = *a++));
        return res;
    }
    return NULL;
}
1
2
3
4
5
6
7
8

3、假设称正读和反读都相同的字符序列为 “回文”，例如， ‘abba’和‘abcba’是回文， ‘abcde’和‘ababab’ 则不是回文。试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是 “回文”。（10 分）

void solve() {
    string str;
    cin >> str;
    str.pop_back();
    cout << str << endl;
    int n = str.size();
    bool flag = true;
    for (int i = 0; i < n; i++) {
        if (str[i] != str[n - i - 1]) {
           flag = false;
           break;
        }
    }
    cout << flag << endl;
    cout << (flag ? "是回文序列" : "不是回文序列") << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

4、试编写一个算法完成下面的功能：对于输入的任意一个非负十进制整数，输出与其等值的八进制数。（10 分）

#include 
#include 

using namespace std;

int main() {
    int n;
    cin >> n;
    string res;
    while (n) {
        res += to_string(n % 8);
        n /= 8;
    }
    reverse(res.begin(), res.end());
    cout << res << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

5、设二维数组 $a [1.. m, 1.. n]$ 含有 $m * n$ 个整数。写一个算法判断 a 中所有元素是否互不相同?并输出相关判断信息。（8 分）

#include 

using namesapce std;

const int N = 100, M = 100;

int n, m;
int a[N][M];
//O(m*n*m*n)
bool check() {
    bool flag = true;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            int tmp = a[i][j];
            for (int i1 = 1; i <= m; i1++) {
                for (int j1 = 1; j1 <= n; j1++) {
                    if (i1 != i && j1 != j) {
                        if (a[i1][j1] == tmp) {
                            cout << "有重复信息" << endl;
                           	return false;
                        }   
                    }
                }
            }
        }
    }
    cout << "没有重复信息" << endl;
    return true;
}

//手写哈希
const int N = 2e5 + 7, null = 0x3f3f3f3f;
int h[N], e[N], ne[N], idx = 0;

void insert(int x) {
    int k = (x % N + N) % N;
    e[idx] = x, ne[idx] = h[k], h[k] = idx ++;
}
//拉链法实现
bool find(int x) {
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i]) {
        if (e[i] == x)
            return true;
    }
    return false;
}
//O(m*n)
bool check_by_hash() {
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            insert(a[i][j]);
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (find(a[i][j])) {
                cout << "有重复信息" << endl;
                return false;
            }
        }
    }
    cout << "没有重复信息" << endl;
    return true;
}
// O(m*n*log(m*n))
bool check_by_sort() {
    int nums[N], cnt = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            nums[cnt ++] = a[i][j];
        }
    }
    sort(nums, nums + cnt);
    for (int i = 2; i <= cnt; i++) {
        if (nums[i] == nums[i - 1]) {
            cout << "有重复信息" << endl;
            return false;
        }
    }
    cout << "没有重复信息" << endl;
    return true;
}

int main() {
    check();
    //check_by_hash();
    //check_by_sort();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

6、若矩阵 $A_{m*n}$ 中的某个元素 $a_{ij}$ 是第 $i$ 行中的最小值，同时又是第 $j$ 列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设二维数组存储矩阵 $A_{m*n}$ ，试编写求出矩阵中所有马鞍点的算法。(8 分)

#include 

using namesapce std;

const int N = 10;

int a[N][N];
int m, n;

void findSaddlePoint() {
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            int minv = 0x3f3f3f3f;
            for (int k = 1; k <= n; k++) { // 遍历第i行
                minv = min(a[i][k], minv);
            }
            int maxv = -1;
            for (int k = 1; k <= m; k++) { //遍历第j列
                maxv = max(maxv, a[k][j]);
            }
            if (maxv == minv) {
                cout << i << ' ' << j << a[i][j] << endl;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

参考书目

《2024王道计算机数据结构考研复习指导》
《数据结构(C语言版）（第2版）》（严蔚敏）
《数据结构习题解析与实验指导（第2版）》（严蔚敏）

相关阅读:
开发笔记 03，为什么不要问别人在做什么小产品？
计算机三级数据库高级查询
u盘坏了数据可以恢复吗?实用小方法
读《长安的荔枝》有感
Spring Boot配置多个Kafka数据源
操作文档的用户故事怎么写，敏捷开发
力扣解法汇总641-设计循环双端队列
第十七章源代码文件 REST API 教程（二）
阿里云服务器怎么退款？云服务器退款流程图
源码编译postgresql

原文地址：https://blog.csdn.net/weixin_55664293/article/details/133911582