目录

一：选择题or填空题：

二：判断题

三：简答题

下面的都为知识点 通过知识点的提问看自己是否掌握了 在对应做题。

一：选择题or填空题：

1.给你一个表达式字符串，求next数组

2.中缀转前后缀

3.一个进栈序列 那种顺序是不可能出现的

4.一个程序栈 其中某一行代码实现了多少次

5.最短路径算法名字/Kruskal Prim 弗洛伊德 哈夫曼 迪杰斯特拉（Dijkstra）等是干嘛的

6.给定一个二分查找关键字 求比较次数

7.一个序列 用快速排列 以第一个记录的到的为基准 得到一次划分的结果是什么

8.给定一个广义表表达式 求表的长度和深度

9.AOV网络可以通过什么来测试 它是不是存在回路 (拓拔排序)

10.N个节点的无向图 至少要多少边才能连通：n-1

11.通常把查找对关键字的比较次数作为衡量查找算法的优劣的标准称为 平均比较次数/平均查找长度（ASL）

12.在堆排序中 如果每个节点的值小于或者等于左右孩子的值 则称为 小顶堆

13.一个长度为n的顺序表，删除第i个元素，需要上前移动多少个元素

14.单链表中增加一个头结点的目的是：为了便于运算和实现（简化运算）

15.如果树中结点A有3个兄弟，B是A的双亲，则B的度是多少：4

16.如果有K个关键词互为同义词，用线性探测，再用散列法,把这K 个关键字存在散列中，至少要进行多少次探测：(K(K+1))/2

17.一个完全二叉树，给一个结点数，其叶子结点数是多少

二：判断题

1.数据的逻辑结构是指数据的各数据项之间的逻辑关系。（√）

2. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（×）效率在链表时高一些

3.数据的逻辑结构说明数据元素之间的次序关系，它依赖于数据的存储结构。（×）数据运算的定义依赖于逻辑结构，实现依赖于存储结构

4.算法的优劣与描述算法的语言无关，但与所用计算机的性能有关。（×）算法的优劣与时间空间复杂度有关

5.算法必须有输出，但可以没有输入。（√）

6.线性表的逻辑顺序与存储顺序总是一致的。（×）

7. 顺序存储的线性表可以按序号随机存取。（√）

8. 顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近半的元素需要移动。（×）需要付出很大的代价 每次移动都要移动一半以上的数据

9. 线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性因此属于同一数据对象。 （√）

10.在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（×）

11.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻 。（√）

12. 线性表的链式存储结构优于顺序存储结构。（×）没有x 比×更优的说法，各有各的优点

13.在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。（√）

14.线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（√）

15. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（×）存储结构有4种，不包括单链表

16.静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。（×）

17.线性表的特点是每个元素都有一个前驱和一个后继（×）除了第一个和最后一个

18.栈和队列的存储，既可以采用顺序存储结构，又可以采用链式存储结构。（√）

19.任何一个递归过程都可以转换成非递归过程。（√）

20. 若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列3，2，5，6，4，1。（√）

21.通常使用队列来处理函数的调用。 （×）栈的应用

22.循环队列通常用指针来实现队列的头尾相接。（×）用数组

23.每种数据结构都是一种数据类型 （×）每种数据类型可以看做一种数据结构

24.使用两个栈不能实现一个队列。 （×）两个栈相连

25.使用一个数组能够实现多个队列。（√）

26.串相等是指两个串的长度相等。（×）ASCII值

27.串既可以采用顺序存储，也可以采用链式存储。（√）

28.KMP算法的特点是在模式匹配时指示主串的指针不会变小。（√）

29.稀疏矩阵压缩存储后，必会失去随机存取功能。（√）

30.串是字符的有限序列，空串是由空格构成的。（×） 空串与空格串的区别

31.数组是线性结构的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。（×）

32.若采用三元组存储稀统矩阵，把每个元素的行下标和列下标互换，就完成了该矩阵的转置运算。（×）

33.若一个广义表的表头为空表，则此广义表亦为空表。（×）

34.若一个广义表的表尾为空表，则此广义表亦为空表。（×）

35.所谓取广义表的表尾就是返回广义表中最底少个元素。（×）

36.二叉树的基本形态有5种。（√）

37.由树转换成二叉树，其根结点的右子树总是空的。（√）

38. 先根遍历一棵树和先序遍历与该树对应的二叉树，其结果不同。（×）

39. 先根遍历森林和先序遍历与该森林对应的二叉树，其结果不同。（×）

40.完全二叉树中，若个结点没有左孩子，则它必是叶子。（√）

41.对于有N个结点的 树，其高度为[𝑙𝑜𝑔2N]+1（×）完全二叉树满足

42.若一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树先序遍历序列中的最后一个结点。（×）

43.若一个结点是某二叉树子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。（×）

44.不使用递归也可实现二叉树的先序、中序和后序遍历。（√）

45.先序遍历二叉树的序列中，任何结点的子树的所有结点不一定跟在该结点之后。（×）

46.在后序线索二叉树中，在任何情况下都能很方便地找到任意结点的后继（×）

47. 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。（√）

48.在哈夫曼编码中，出现频率相同的字符编码长度也一定相同。（×）

49.用一维数组存放二叉树时，总是以先序遍历存储结点。（×）

50.由先序序列和后序序列能唯一确定一棵二叉树。（×）

51.由先序序列和中序序列能唯一确定一棵二叉树。（√）

52.对一棵二叉树进行层次遍历时，应借助于一个栈。（×）队列

53.完全二叉树可采用顺序存储结构实现存储，非完全二叉树则不能。（×）

54.满二叉树一定是完全二叉树，反之未必。（√）

55.求最小生成树的Prim算法在边较结点较少，点结点较多时效率较高。（×）

56.图的最小生成树的形状可能不唯一。（√）

57.用邻接矩阵法的法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。（√）

58.邻接表法只用于有向图的存储，邻接矩阵对于有向图和无向图的存储都活用任何有向网络（AOV网络）拓扑排序的结果是唯一的。（×）

59.拓扑排序可以检查一个有向图是否有回路。（√）

60.存储无向图的邻接矩阵是对称的，故只存储邻接矩阵的下(或上)三角部分即可。（√）

61.任何无向连通图都存在生成树。（√）

62.若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（√）

63.连通分量是无向图中的极小连通子图。（×）极大

64.强连通分量是有向图中的极大强连通子图。（√）

65.用邻接矩阵A表示图，判定任意两个结点 𝑉1和𝑉2之间是否有长度为m的路径相连，则只要检查𝐴m的第i行第j列的元素是否为0即可。（√）

66.缩短任意一条关键路径上活动的工期一定能够缩短整个工程的工期（×）

67.缩短关键活动之后，工程的关键路径有可能会改变，所以必须重新求关键路径（√）

68.顺序查找可以在顺序表上进行，不能在单链表进行。（X)

69.折半查找只能在有序的顺序表上进行。（√）

70.对于给定的关键字集合，以不同的次序插入到初始为空的二叉排序树中，得到的二叉排序树是相同的。（×）

71.若二叉排序树中关键字互不相同，那么，最小值结点必定无左孩子， 最大值结点必，定无右孩子。（√）

72.在二叉排序树中，最大值结点和最小结点一定是叶子结点。（√）

73.在二叉树𝑇1先序遍历序列依次插入初始为空的树中，所得到的二叉树𝑇2和𝑇1的形态完全相同。（√）

74.对二叉排序树进行中序遍历得到的序列是由小到大有序的。（√）

75.二叉树为二叉排序树的充分必要条件是任一非终端结点的值大于其左孩子的值、小于右孩子的值。（×）

76.二叉排序树的查找和折半查找的时间复杂度都是O(log2𝑁)，时间性能相同。（×）

77. 采用折半查找法对有序表进行查找总比采用顺序查找法对其进行查找要快。（×）

78. 采用线性探测法处理冲突时，当从散列表中删除一个记录时，不应将这个记录的所在位置置为空，因为这将会影响以后的查找。（√）

79.m阶B树每一个结点的子树个数都小于或等于m。（√）

80.散列表的查找效率主要取决于构造散列表时选取的散列函数和处理冲突的方法。（√）

81.当负载因子a小于1时，则向散列表中插入元素时不会引起冲突。（×）

82.查找表中数据元素的任何数据项都可以作为关键字。（X）

83.m阶B树的任何一个结点的所有子树的高度都相等。（√）

84.在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的相应的指针域置空即可。（√）

85. 在散列存储方式中，负载因子的值越大，则存取元素时发生冲突的可能性就越大。（√）

86.对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的。（√）

87.插入排序是稳定的，选择排序是不稳定的。（√）

88.不稳定的排序算法是没有实用价值的。（×）

89.当待排序的元素很多时，为了交换元素的位置，移动元素要占较多的时间，这是影响时间复杂度的主要原因。（√）

90.对有n个记录的集合进行归并排序，所需要的辅助空间数与初始记录的排列状况有关。（×）

91.对n个记录的集合进行快速排序，所需要的附加空间数是O(n)。（×）

92.堆排序所需要附加空间数与待排序的记录个数无关。（√）

93.对有n个记录的集合进行冒泡排序，所需时间决定于初始记录的排列情况，在初始记录无序的情况下最好。（×）

94.对有n个记录的集合进行快速排序，所需时间决定于初始记录的排列情况，在初始记录无序的情况下最好。（√）

95.对不稳定的排序算法，不论采用何种描述方式，总能举出一个说明它不稳定的实例来。（√）

96.选择排序的比较次数不会随待排序记录的关键字分布情况而改变。（√）

97.先序和中序遍历用线索树方式存储的二叉树，不必使用栈。（×）

98.十字链表可以存储向图和有向图。（×）

99. 散列法存储的基本思想是由关键码的值决定数据的存储地址。（√）

三：简答题

1.一个带头结点的单链表，写一个算法，将它逆置。

2.给一个二叉树的中序和后序，画出这个二叉树，并将它转化为森林。

3.给一个AOE网络，找出这个AOE网的关键路径，并求出工程花费的最短时间。

4.给一个图，表达其邻接矩阵，且用prim求最小生成树

5.给一个表，用这个表构建平衡二叉树，并要求等概率情况下查找成功的平均查找长度和查找失败时，需要进行的关键码的比较次数。（log2（n+1））

6.给一个序列，用冒泡排序对比序列做升序排序，每一趟的结果

7.给两个排序的单链表，将其合成一个链表，不改变排序的性质

8.给一些字母及其频率，设计一个哈夫曼编码

9.给一个图，用Kruskal求最小生成树

10.给一个序列，请给出希尔排序每一趟的结果（步长因子）

11.给一个有向网络，用弗洛伊德求每一对顶点的最短路径，写出求解过程。