数据结构——【十五套卷子】考前题型归纳整理

文章目录：

一：选择题

注意2：二维数组位置变化

注意7：二叉树的遍历

注意9：快速排序

注意10：删除单链表中结点

注意16：基数排序

注意19：希尔排序

注意20：归并排序

注意21：返回值

注意22：单链表插入一个新结点时间复杂度不变

注意23：m叉树中N0

注意24：连通图的深度优先遍历顶点序列

注意25:经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是n+1-i

注意26：哈夫曼带权路径长度【最优生成树不唯一】

注意28：时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是堆排序

注意29：二叉树的先序遍历序列和后序遍历序列正好相反则任一结点无右孩子

注意30：一趟排序结束后不一定能够选出一个元素放在其最终位置上的是希尔排序

注意32：顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为O(n)

注意34：入队列的操作

注意35：设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为O(n+e)

注意37：设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为第i列非0元素的个数之和【出入——行列】

注意39：设无向图G中有n个顶点，则该无向图的最小生成树上有n-1 条边

注意41：单向循环链表判空条件

注意42.删除链式栈栈顶元素

注意44：建立一个长度为n的有序单链表的时间复杂度为O(n2)

注意46：散列表P的选择

注意47：在二叉排序树中插入一个关键字值的平均时间复杂度为O(1og2n)

注意48：二分法查找比较元素的顺序

注意49：完全二叉树深度

注意50：三叉链权度数为0的结点

注意51：无向图深度优先遍历

注意52：顺序线性表删除表中第i个元素需要移动n-i个元素

注意53：二叉树和森林的转换

注意54：利用直接插入排序法的思想建立一个有序线性表的时间复杂度为O(n2)

注意55：双向链表后面插入结点

注意56：设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（ n+l -i ）

注意58：度数为0的结点数

注意59：设顺序表的长度为n，则顺序查找的平均比较次数为 (n+1)/2

注意61：有向无环图的拓扑

注意62：二叉排序树的深度【二叉排序树的生成方法】

注意63：单链表插入的结点

注意64：下三角矩阵

注意66：哈夫曼带权路径长度

注意67：线性探测法

注意68：插入排序

注意69：冒泡排序

---

二：判断题

---

三：填空题

注意10：筛选法建立的初始堆

注意11：邻接表的深度优先遍历和广度优先遍历

注意16：中序_______遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）【记忆】

注意20：双向循环链表删除结点

注意21：二叉排序树的方法-求高度【记忆】

注意23：哈夫曼树的构造【记忆】

注意27：顺序线性表插入删除一个元素移动元素个数

注意28：二叉树的遍历序列

注意29：顺序共享栈

注意30：下三角矩阵

注意35：单链表的插入操作

注意36：有向图拓扑排序序列

注意40：二叉树指针指向叶子结点

注意41：双向链表

注意42：直接插入排序

注意43：简单选择排序

注意45：希尔排序

注意46：二叉排序树中插入一个新结点

注意47：单链表插入结点

注意48：双向链表

注意53：单链表插入结点

注意54：冒泡排序

注意55：二叉排序树的平均查找长度

注意56：构造哈夫曼树

注意57：筛选法建成的初始堆

注意58：最小生成树上所有边的权值之和

注意60：多重链表表示【记忆】

注意61：单链表删除结点

注意63：散列表的平均查找长度

注意64：冒泡排序

注意65：简单选择排序

注意66：拓扑排序

---

四：算法填空题

注意1：二叉搜索树的查找——递归算法

注意2：入栈-出栈

注意3：实现在顺序散列表中查找值为x的关键字

注意4：实现在二叉排序树上查找关键值k

注意5：散列函数解决冲突的方法为链地址法

注意6：实现冒泡排序算法

注意7：实现二分查找算法

注意8：无向图的最小生成树边集合和权值

注意9.二叉树平均查找长度

注意10：散列表平均查找长度

注意11：实现一趟快速排序

注意12：建立二叉树

注意13：利用从尾部插入的方法建立单链表

---

五：阅读算法

注意1：单链表【建表-查找-插入-删除】

注意2：二叉树的存储结构【顺序存储-链式存储】

---

 六：应用题

1.简单选择排序和直接插入排序

注意2：双向链表在p之前插入​

注意3：二分查找的平均查找长度

注意4：普里姆算法

5.构造一棵二叉排序树

设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。

---

七：计算题

注意3：用克鲁斯卡尔算法得到最小生成树

注意4：小根堆-大根堆

【算法】堆，最大堆（大顶堆）及最小堆（小顶堆）的实现 

https://www.xuebuyuan.com/2147927.html

堆排序（浅谈大顶堆与小顶堆）

https://blog.csdn.net/weixin_43809223/article/details/100828727

最后一个非叶子节点就是：长度/2-1开始

将最大元素"沉"到数组末端

注意5：画出它的后序线索二叉树

注意6：待散列的线性表写出散列表、平均查找长度

注意7：画出广义表头尾链表存储结

注意8：森林

注意9：散列表​

---

 八：算法设计题/编写算法题

注意1：统计出单链表HL中结点的值等于给定值X的结点数

注意2：设有一组初始记录关键字序列

注意3：设有两个集合A和集合B

注意4：设计在单链表中删除值相同的多余结点的算法

注意5：设计一个求结点x在二叉树中的双亲结点算法

注意6：利用原单链表中结点空间设计出三个单链表的算法

注意7：在链式存储结构上交换二叉树中所有结点左右子树

注意8：在链式存储结构上建立一棵二叉排序树

注意9：判断两个二叉树是否相同

注意10：两个有序单链表的合并排序

注意11：在顺序有序表中实现二分查找的算法

注意12：判断二叉树是否为二叉排序树的算法

注意13：链式存储结构上设计直接插入排序算法

注意14：在链式结构上实现简单选择排序算法

注意15：在顺序存储结构上实现求子串算法

注意16：求结点在二叉排序树中层次的算法

注意17：在链式存储结构上统计二叉树中结点个数

注意18：将无向图的邻接矩阵转为对应邻接表的算法

注意19：计算二叉树中所有结点值之和

注意20：将所有奇数移到所有偶数之前

注意21：设计判断单链表中元素是否是递增

注意22：在链式存储结构上合并排序

注意23：在二叉排序树上查找结点X

注意24：关键字序列(k1，k2，…，kn-1)是堆，设计算法将关键字序列(k1，k2，…，kn-1，x)调整为堆

---

---

一：选择题

1.用链接方式存储的队列，在进行插入运算时(D   ).

        A. 仅修改头指针  　          B. 头、尾指针都要修改

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

注意2：二维数组位置变化

设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。C

          A．688          B．678        C．692        D．69

 

3.设有6个结点的无向图，该图至少应有(    A  )条边才能确保是一个连通图。

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

4.下面关于线性表的叙述错误的是（ D  ）。

(A) 线性表采用顺序存储必须占用一片连续的存储空间

(B) 线性表采用链式存储不必占用一片连续的存储空间

(C) 线性表采用链式存储便于插入和删除操作的实现

(D) 线性表采用顺序存储便于插入和删除操作的实现

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

(A) 2m-1 (B) 2m (C) 2m+1 (D) 4m

二叉树的二叉链表存储结构及C++实现

https://www.cnblogs.com/smile233/p/8145760.html

6.设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（C  ）。

(A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M

注意7：二叉树的遍历

7.1 设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（  A ）。

(A) BADC (B) BCDA (C) CDAB (D) CBDA

C

    A            D

       B

 

7.2

8.设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ C ）。

(A) 9 (B) 10 (C) 11 (D) 12

注意9：快速排序

9.1 设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（C  ）。

(A) 2，3，5，8，6 (B) 3，2，5，8，6

(C) 3，2，5，6，8 (D) 2，3，6，5，8

 

9.2设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( A )。

(A) 10，15，14，18，20，36，40，21

(B) 10，15，14，18，20，40，36，21

(C) 10，15，14，20，18，40，36，2l

(D) 15，10，14，18，20，36，40，21

 

9.3 设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的一趟快速排序结果为____(5，16，71，23，72，94，73)___。

 

9.4 已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。

 

9.5  

9.6

设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是（ C ）。

(A) 40，42，45，55，80，83 (B) 42，40，45，80，85，88

(C) 42，40，45，55，80，85 (D) 42，40，45，85，55，80

 

9.7

执行一趟快速排序能够得到的序列是（ A ）。

(A) [41，12，34，45，27] 55 [72，63]

(B) [45，34，12，41] 55 [72，63，27]

(C) [63，12，34，45，27] 55 [41，72]

(D) [12，27，45，41] 55 [34，63，72]

 

9.8

设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是（ C ）。

(A) 40，42，60，55，80，85 (B) 42，45，55，60，85，80

(C) 42，40，55，60，80，85 (D) 42，40，60，85，55，80

 

注意10：删除单链表中结点

11.设有n个待排序的记录关键字，则在堆排序中需要（  A）个辅助记录单元。

(A) 1 (B) n (C) nlog2n (D) n2

12.设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（ B ）。

(A) O(1) (B) O(log2n) (C) (D) O(n2)

13.设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（B  ）方法可以达到此目的。

(A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 插入排序

14.下列四种排序中（ D ）的空间复杂度最大。

(A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 归并排序

15.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C  ）。

(A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2)

注意16：基数排序

设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（A  ）趟的分配和回收才能使得初始关键字序列变成有序序列。

(A) 3 (B) 4 (C) 5 (D) 8

17.设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（  C）。

(A) N0=N1+1 (B) N0=Nl+N2 (C) N0=N2+1 (D) N0=2N1+l

18.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（  A）。

(A) log2n+1 (B) log2n-1 (C) log2n (D) log2(n+1)

注意19：希尔排序

设一组初始记录关键字序列为(50，40，95，20，|15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（ B  ）。

(A) 40，50，20，95 (B) 15，40，60，20

(C) 15，20，40，45 (D) 45，40，15，20

8个   8/2=4           第四个结点

注意20：归并排序

设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ A  ）。

(A) 15，25，35，50，20，40，80，85，36，70

(B) 15，25，35，50，80，20，85，40，70，36

(C) 15，25，35，50，80，85，20，36，40，70

(D) 15，25，35，50，80，20，36，40，70，85

10  10/2 =5

25 50/15 35/80 85/20 40/36 705个长度为2的有序子表

15 25 35 50/20 40 80 85/36 70

 

15 20  25  35 40 50 80 85/36 70

15 20  25 35 36 40 50 70 80 85

注意21：返回值

函数substr(“DATASTRUCTURE”，5，9)的返回值为（  A）。

(A) “STRUCTURE” (B) “DATA”

(C) “ASTRUCTUR” (D) “DATASTRUCTURE”

 

这个函数的意思是从字符串“DATASTURCTURE”的第五个字符S开始，截取后面的9个字符。
所以为：
STRURCTURE

注意22：单链表插入一个新结点时间复杂度不变

设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（D  ）。

(A) O(log2n) (B) O(1) (C) O(n2) (D) O(n)

注意23：m叉树中N0

设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（B  ）。

(A) Nl+N2+……+Nm (B) l+N2+2N3+3N4+……+(m-1)Nm

(C) N2+2N3+3N4+……+(m-1)Nm (D) 2Nl+3N2+……+(m+1)Nm

注意24：连通图的深度优先遍历顶点序列

设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（ B ）。

(A) abedfc (B) acfebd (C) aebdfc (D) aedfcb

相当于先序遍历：

a——b\e\c

b——e

e——d

d——f

f——c

注意25:经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是n+1-i

设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（ C ）。

(A) n-i (B) n-1-i (C) n+1-i (D) 不能确定

注意26：哈夫曼带权路径长度【最优生成树不唯一】

设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（  D）。

(A) 20 (B) 30 (C) 40 (D) 45

首先构造哈夫曼树

            20

          6     14

            5         9

                   4       5    

                         2      3

1*6+5*2+4*3+2*4+3*4=6+10+12+8+12=48

27.

设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（  A）。

(A) head==0 (B) head->next==0

(C) head->next==head (D) head!=0

注意28：时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是堆排序

时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（  A）。

(A) 堆排序 (B) 冒泡排序 (C) 希尔排序 (D) 快速排序

注意29：二叉树的先序遍历序列和后序遍历序列正好相反则任一结点无右孩子

设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（D  ）。

(A) 空或只有一个结点 (B) 高度等于其结点数

(C) 任一结点无左孩子 (D) 任一结点无右孩子

注意30：一趟排序结束后不一定能够选出一个元素放在其最终位置上的是希尔排序

一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（ D ）。

(A) 堆排序 (B) 冒泡排序 (C) 快速排序 (D) 希尔排序

31.设某棵三叉树中有40个结点，则该三叉树的最小高度为（B  ）。

(A) 3 (B) 4 (C) 5 (D) 6

注意32：顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为O(n)

顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（ A ）。

(A) O(n) (B) O(n2) (C) O(n1/2) (D) O(1og2n)

33.二路归并排序的时间复杂度为（ C ）。

(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)

注意34：入队列的操作

设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（C  ）。

(A) front->next=s；front=s； (B) s->next=rear；rear=s；

(C) rear->next=s；rear=s； (D) s->next=front；front=s

注意35：设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为O(n+e)

设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（A  ）。

(A) O(n+e) (B) O(n2) (C) O(ne) (D) O(n3)

36.设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（ D ）。

(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)

注意37：设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为第i列非0元素的个数之和【出入——行列】

设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（  B）。

(A) 第i行非0元素的个数之和 (B) 第i列非0元素的个数之和

(C) 第i行0元素的个数之和 (D) 第i列0元素的个数之

38.设某无向图有n个顶点，则该无向图的邻接表中有（ B ）个表头结点。

(A) 2n (B) n (C) n/2 (D) n(n-1)

注意39：设无向图G中有n个顶点，则该无向图的最小生成树上有n-1 条边

设无向图G中有n个顶点，则该无向图的最小生成树上有（ B）条边。

(A) n (B) n-1 (C) 2n (D) 2n-139.

40.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ B ）。

(A) 2i+1 (B) 2i (C) i/2 (D) 2i-1

注意41：单向循环链表判空条件

设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（C  ）。

(A) head==0 (B) head->next==0

(C) head->next==head (D) head!=0

42.设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（C  ）。

(A) 20 (B) 256 (C) 512 (D) 1024

注意42.删除链式栈栈顶元素

设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（D  ）。

(A) top=top+1; (B) top=top-1;

(C) top->next=top; (D) top=top->next;

43.字符串的长度是指（ C  ）。

(A) 串中不同字符的个数 (B) 串中不同字母的个数

(C) 串中所含字符的个数 (D) 串中不同数字的个数

注意44：建立一个长度为n的有序单链表的时间复杂度为O(n2)

建立一个长度为n的有序单链表的时间复杂度为（ C ）

(A) O(n) (B) O(1) (C) O(n2) (D) O(log2n)

45.两个字符串相等的充要条件是（ C ）。

(A) 两个字符串的长度相等 (B) 两个字符串中对应位置上的字符相等

(C) 同时具备(A)和(B)两个条件 (D) 以上答案都不对

注意46：散列表P的选择

设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（ B ）。

(A) 99 (B) 97 (C) 91 (D) 93

首先明确哈希函数的除留余法的P选择小于长度的最大质数比较好

所以C 质数也就是素数，就是除了1和本身不能让其他除尽的

注意47：在二叉排序树中插入一个关键字值的平均时间复杂度为O(1og2n)

在二叉排序树中插入一个关键字值的平均时间复杂度为（ B ）。

(A) O(n) (B) O(1og2n) (C) O(nlog2n) (D) O(n2)

注意48：二分法查找比较元素的顺序

设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为(C  )。

(A) A[1]，A[2]，A[3]，A[4] (B) A[1]，A[14]，A[7]，A[4]

(C) A[7]，A[3]，A[5]，A[4] (D) A[7]，A[5] ，A[3]，A[4]

注意49：完全二叉树深度

设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（ B ）。

(A) 8 (B) 7 (C) 6 (D) 5

使用log2(n)+1或者log2(2n)判断

应该是7 因为2^6- 1 <  65  < 2^7- 1  所以是6+ 1 =7

log2N（向下取整）+1      log2 65 +1=7

注意50：三叉链权度数为0的结点

设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有（C  ）个度数为0的结点。

(A) 5 (B) 6 (C) 7 (D) 8

三叉树结点的度数均不大于3，结点总数应等于i度结点数(记为ni)和：N=n0+n1+n2+n3 (1)

二：i度结点有i个孩子，根结点不是任何结点的孩子，结点总数为：N=n1+2n2+3n3+1 (2)

1、2得到：n0=n2+2n3+1=2+2*2+1=7

注意51：无向图深度优先遍历

设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（A  ）。

(A) aedfcb (B) acfebd (C) aebcfd (D) aedfbc

注意52：顺序线性表删除表中第i个元素需要移动n-i个元素

设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（ A ）个元素。

(A) n-i (B) n+l -i (C) n-1-i (D) i

注意53：二叉树和森林的转换

设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

二叉树和森林的转换

http://www.cnblogs.com/zhuyf87/archive/2012/11/04/2753950.html

注意54：利用直接插入排序法的思想建立一个有序线性表的时间复杂度为O(n2)

利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（  C）。

   (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(1og2n)

注意55：双向链表后面插入结点

设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（D  ）。

(A) p->right=s； s->left=p； p->right->left=s； s->right=p->right；

(B) s->left=p；s->right=p->right；p->right=s； p->right->left=s；

(C) p->right=s； p->right->left=s； s->left=p； s->right=p->right；

(D) s->left=p；s->right=p->right；p->right->left=s； p->right=s；

注意56：设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（ n+l -i ）

(A) n-i (B) n-1-i (C) n+l -i (D) 不能确定

57.设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择（B  ）。

(A) 小于等于m的最大奇数 (B) 小于等于m的最大素数

(C) 小于等于m的最大偶数 (D) 小于等于m的最大合数

注意58：度数为0的结点数

设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（C  ）个。

(A) 4 (B) 5 (C) 6 (D) 7

除了根结点外,其他结点均为孩子结点,而孩子结点数等于总的分支数，即1*n1+2*n2+3*n3

所以总结点数=1（根节点）+1*n1+2*n2+3*n3（孩子结点数）=11

度数为0的结点数=11-n1-n2-n3=6

注意59：设顺序表的长度为n，则顺序查找的平均比较次数为 (n+1)/2

(A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/2

60.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（ D ）。

(A) 6 (B) 11 (C) 5 (D) 6.5

注意61：有向无环图的拓扑

设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（ A ）。

(A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，3

每次删除入度为0的顶点并输出

注意62：二叉排序树的深度【二叉排序树的生成方法】

设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（A  ）。

(A) 4 (B) 5 (C) 6 (D) 7

注意63：单链表插入的结点

设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（ B ）。

(A) s->next=p->next；p->next=-s； (B) q->next=s； s->next=p；

(C) p->next=s->next；s->next=p； (D) p->next=s；s->next=q；

注意64：下三角矩阵

设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（B  ）。

(A) 10 (B) 19 (C) 28 (D) 55

65.

假设叶子结点数为n0,并假设树的结点数为N,N = n0+n1+n2+...+nm
N = n1+2*n2+3*n3+...+m*nm+1
这样得到n0+n1+n2+...+nm = 1+n1+2*n2+3*n3+...+m*nm
即得：n0 = n2+2*n3+3*n4+...+(m-1)*nm+1 

注意66：哈夫曼带权路径长度

设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（ D ）。

(A) 129 (B) 219 (C) 189 (D) 229

注意67：线性探测法

设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做（ D ）次线性探测。

(A) n2  (B) n(n+1) (C) n(n+1)/2 (D) n(n-1)/2

68.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（  C）个结点。

(A) 2n (B) n+l (C) 2n-1 (D) 2n+l

二叉树中一个性质：度为0的结点（叶子节点）个数n0等于度为2的结点个数n2加1，即N2=N0-1。总结点数N=N0+N1+N2=N0+0+(No-1)=2N0-1。N1表示树中度为1的结点。

注意68：插入排序

设一组初始记录关键字的长度为8，则最多经过（ B ）趟插入排序可以得到有序序列。

(A) 6 (B) 7 (C) 8 (D) 9

注意69：冒泡排序

设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（  D ）。

(A)  F，H，C，D，P，A，M，Q，R，S，Y，X

(B)  P，A，C，S，Q，D，F，X，R，H，M，Y

(C)  A，D，C，R，F，Q，M，S，Y，P，H，X

(D)  H，C，Q，P，A，M，S，R，D，F，X，Y

---

 

二：判断题

---

三：填空题

1.通常从四个方面评价算法的质量：__准确性____易读性___强壮性_____高效率_____。

2.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有_____2n___个指针域，其中有__n-1______个指针域是存放了地址，有_____n+1___________个指针是空指针。【记忆】

3.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有___e____个和____2e____个。

4.AOV网是一种__________有向无回路_________的图。

AOV网:有向无回路的图【记忆】

AOE网:带权的有向无环图【记忆】

https://blog.csdn.net/liu17234050/article/details/106729076

5.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为____(12,40)____0、_____(74)___2、____(23,55,63)______3,3,3和________()_______。

6.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度__增加1____。【记忆】

7.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为__O（log2^n）______，整个堆排序过程的时间复杂度为__O（nlog2^n）______。

8.为了能有效地应用HASH查找技术，必须解决的两个问题是____构造一个好的HASH函数_______和______确定解决冲突的方法____。【记忆】

9.设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数为___N0-1______；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_2N0+N1___个空指针域。【记忆】

注意10：筛选法建立的初始堆

10.1 设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立的初始堆为

____(31，38，54，56，75，80，55，63)

初始堆——调整为小根堆

https://www.zybang.com/question/04444183fd5131cfe1a7f5fcbbd3c821.html大根堆

 

10.2 调整为小根堆

注意11：邻接表的深度优先遍历和广度优先遍历

12.设一棵完全二叉树中有500个结点，则该二叉树的深度为____9______；若用二叉链表作为该完全二叉树的存储结构，则共有_____501______个空指针域。

13.设输入序列为1、2、3，则经过栈的作用后可以得到______5_____种不同的输出序列

14.设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的_____出度___，第i列上所有元素之和等于顶点i的___入度_____【记忆】

15.设哈夫曼树中共有n个结点，则该哈夫曼树中有_____0___个度数为1的结点【记忆】

注意16：中序_______遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）【记忆】

⑴ 若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
⑵ 若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
⑶ 左、右子树本身又各是一棵二叉排序树。二叉排序树的性质： 按中序遍历二叉排序树，所得到的中序遍历序列是一个递增有序序列。

17.设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较____7____次就可以断定数据元素X是否在查找表中。

18.不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为_____O（1）_______【记忆】

19.设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为___i/2_________，右孩子结点的编号为___2i+1_______【记忆】

注意20：双向循环链表删除结点

注意21：二叉排序树的方法-求高度【记忆】

根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为___3_________

22.设初始记录关键字序列为(K1，K2，…，Kn)，则用筛选法思想建堆必须从第__n/2____个元素开始进行筛选

注意23：哈夫曼树的构造【记忆】

24.设哈夫曼树中共有99个结点，则该树中有____50_____个叶子结点；若采用二叉链表作为存储结构，则该树中有___100__个空指针域

 

Huffman 树只有叶子和度为2的结点，因为n0 = n2 + 1，所以n0 + n0-1= 99，所以n0 = 50，也就是说是50个叶子，用二叉链表存储时每个叶子有2个空指针域，自然二叉链表确实是有100个空指针域【记忆】

25.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有2m个空指针域。

 

哈夫曼树有m个叶子，由于哈夫曼树是无度为1的结点的二叉树，故度为2的结点有m-1个，共2m-1个结点。

度为2的m-1

度为0的m

共计m+m-1=2m-1

空指针数＝2叶子结点【记忆】

26.设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储___m-1_____个队列元素；当前实际存储___(R-F+M)%M_____________个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）【记忆】

注意27：顺序线性表插入删除一个元素移动元素个数

设顺序线性表中有n个数据元素，

则第i个位置上插入一个数据元素需要移动表中_n+1-i______个数据元素；

删除第i个位置上的数据元素需要移动表中__n-i_____个元素。【记忆】

注意28：二叉树的遍历序列

设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该二叉树的序列为__BDCA___________

注意29：顺序共享栈

设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是_____top1+1=top2_______________。【记忆】

30.在图的邻接表中用顺序存储结构存储表头结点的优点是___可以随机访问到任一顶点的简单链表________________

注意30：下三角矩阵

31.栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为____FILO______表；【记忆】

队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为__FIFO_______表

32.设一棵完全二叉树有128个结点，则该完全二叉树的深度为__8______，有____64______个叶子结点【记忆】。

33.设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的____出度____，第i列中所有非零元素个数之和等于顶点i的__入度________。【记忆】

34.设一组初始记录关键字序列(k1，k2，……，kn)是堆，则对i=1，2，…，n/2而言满足的条件为_______________________________。【记忆】

注意35：单链表的插入操作

注意36：有向图拓扑排序序列

37.设无向图G中有n个顶点，则该无向图中每个顶点的度数最多是n-1__个_______【记忆】

38.设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有___129____个结点数

39.

注意40：二叉树指针指向叶子结点

注意41：双向链表

注意42：直接插入排序

注意43：简单选择排序

44.设一棵二叉树的前序序列为Azhu'yBC，则有___5___种不同的二叉树可以得到这种序列

注意45：希尔排序

注意46：二叉排序树中插入一个新结点

zhuy

注意47：单链表插入结点

注意48：双向链表

49.完全二叉树中第5层上最少有_____1_____个结点，最多有_____16____个结点。【记忆】

50.设有向图中不存在有向边<Vi,Vj>，则其对应的邻接矩阵A中的数组元素A[i][j]的值等于______0______。【记忆】

带权图：边<Vi，Vj>的权

无权图：1

51.设连通图G中有n个顶点e条边，则对应的最小生成树上有_____n-_1_____条边【记忆】

52.设有一组初始记录关键字序列为(50，16，23，68，94，70，73)，则将它们调整成初始堆只需把16与______50_____相互交换即可

注意53：单链表插入结点

54.设某棵完全二叉树中有100个结点，则该二叉树中有______50________个叶子结点

55.设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储__m-1_____队列元素【记忆】

注意54：冒泡排序

对一组初始关键字序列（40，50，95，20，15，70，60，45，10）进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为___6_______，在整个排序过程中最多需要进行_______8___趟排序才可以完成。

55.在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择_____快速____排序，如果从节省存储空间的角度来考虑则最好选择____堆____排序

注意55：二叉排序树的平均查找长度

设一组初始记录关键字序列为(20，12，42，31，18，14，28)，则根据这些记录关键字构造的二叉排序树的平均查找长度是___19/7____________________________。

注意56：构造哈夫曼树

设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为____6____________。

注意57：筛选法建成的初始堆

注意58：最小生成树上所有边的权值之和

设无向图G（如右图所示），则其最小生成树上所有边的权值之和为___________8______。

59.设需要对5个不同的记录关键字进行排序，则至少需要比较___4__________次，至多需要比较_____10________次

注意60：多重链表表示【记忆】

注意61：单链表删除结点

62.

注意63：散列表的平均查找长度

注意64：冒泡排序

注意65：简单选择排序

注意66：拓扑排序

---

四：算法填空题

注意1：二叉搜索树的查找——递归算法

https://blog.csdn.net/liu17234050/article/details/106315650#1.3%20%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E8%83%A1%E7%9A%84%E6%9F%A5%E6%89%BE

 

注意2：入栈-出栈

https://blog.csdn.net/liu17234050/article/details/106315650#2.2%20%E5%87%BA%E6%A0%88-%E8%BF%9B%E6%A0%88-%E6%A0%88%E6%BB%A1-%E6%A0%88%E7%A9%BA%C2%A0

https://blog.csdn.net/liu17234050/article/details/106315650#3.2.1%20%E5%85%A5%E6%A0%88 

注意3：实现在顺序散列表中查找值为x的关键字【注意】

注意4：实现在二叉排序树上查找关键值k

https://blog.csdn.net/liu17234050/article/details/106315650#1.3%20%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E8%83%A1%E7%9A%84%E6%9F%A5%E6%89%BE 

注意5：散列函数解决冲突的方法为链地址法【注意】

注意6：实现冒泡排序算法

注意7：实现二分查找算法

注意8：无向图的最小生成树边集合和权值

注意9.二叉树平均查找长度

注意10：散列表平均查找长度

注意11：实现一趟快速排序【注意】

注意12：建立二叉树

注意13：利用从尾部插入的方法建立单链表

https://blog.csdn.net/liu17234050/article/details/106315650#3.1%20%E5%BB%BA%E7%AB%8B%E5%8D%95%E9%93%BE%E8%A1%A8%E3%80%90%E5%A4%B4%E6%8F%92%E6%B3%95-%E5%B0%BE%E6%8F%92%E6%B3%95%E3%80%91 

---

五：阅读算法

注意1：单链表【建表-查找-插入-删除】

注意2：二叉树的存储结构【顺序存储-链式存储】

---

六：应用题

1.简单选择排序和直接插入排序

注意2：双向链表在p之前插入

注意3：二分查找的平均查找长度

注意4：普里姆算法

5.构造一棵二叉排序树

设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。

---

七：计算题

1.写出线性表

2.请画出下图的邻接矩阵和邻接表。

注意3：用克鲁斯卡尔算法得到最小生成树

先画图 

注意4：小根堆-大根堆

【算法】堆，最大堆（大顶堆）及最小堆（小顶堆）的实现 

https://www.xuebuyuan.com/2147927.html

堆排序（浅谈大顶堆与小顶堆）

https://blog.csdn.net/weixin_43809223/article/details/100828727

最后一个非叶子节点就是：长度/2-1开始

将最大元素"沉"到数组末端

注意5：画出它的后序线索二叉树【注意】

注意6：待散列的线性表写出散列表、平均查找长度

注意7：画出广义表头尾链表存储结构【注意】

注意8：森林

https://blog.csdn.net/liu17234050/article/details/106315650#2.%E6%A0%91%E5%92%8C%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BD%AC%E6%8D%A2 

二叉树和森林的转换

http://www.cnblogs.com/zhuyf87/archive/2012/11/04/2753950.html

注意9：散列表

---

八：算法设计题/编写算法题

注意1：统计出单链表HL中结点的值等于给定值X的结点数

注意2：设有一组初始记录关键字序列

注意3：设有两个集合A和集合B

注意4：设计在单链表中删除值相同的多余结点的算法

注意5：设计一个求结点x在二叉树中的双亲结点算法

注意6：利用原单链表中结点空间设计出三个单链表的算法

注意7：在链式存储结构上交换二叉树中所有结点左右子树

注意8：在链式存储结构上建立一棵二叉排序树

注意9：判断两个二叉树是否相同

注意10：两个有序单链表的合并排序

注意11：在顺序有序表中实现二分查找的算法

注意12：判断二叉树是否为二叉排序树的算法

注意13：链式存储结构上设计直接插入排序算法

注意14：在链式结构上实现简单选择排序算法

注意15：在顺序存储结构上实现求子串算法

注意16：求结点在二叉排序树中层次的算法

注意17：在链式存储结构上统计二叉树中结点个数

注意18：将无向图的邻接矩阵转为对应邻接表的算法

注意19：计算二叉树中所有结点值之和

注意20：将所有奇数移到所有偶数之前

注意21：设计判断单链表中元素是否是递增

注意22：在链式存储结构上合并排序

注意23：在二叉排序树上查找结点X

注意24：关键字序列(k1，k2，…，kn-1)是堆，设计算法将关键字序列(k1，k2，…，kn-1，x)调整为堆