2018年北方工业大学计算机学院861数据结构考研仿真模拟五套题
● 摘要
一、填空题
1． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。
【答案】69
【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。
2． 设有N 个结点的完全二叉树顺序存放在向量 中，其下标值最大的分支结点为_____。
【答案】
【解析】最大的分支结点是最后一个叶子结点的父结点。
3． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e
【答案】克鲁斯卡尔
【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。
4． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k ＝_____。(注:矩阵元素下标从1开始)
【答案】93
【解析】对于上三角矩阵，k ＝(i﹣l)(2n﹣i ＋2)/2＋(j﹣i) ＋l 。将i ＝j ＝9，n ＝15代入得93。
5．
给定一组数据以它构造一棵哈夫曼树，则树高为_____，带权路径长度WPL 的值为_____。
【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树:
在B
6． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度, 当它为一棵_____时，具有最大高度。
【答案】完全；只有一个叶结点的二叉树
7． 设广义表L ＝(（ ），（ ）) ，则head(L)是_____tail(L)是_____L的长度是_____；深度是_____。
【答案】（ ）；(（ ）) ；2；2
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
8． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____, 设计出相应的_____。
【答案】逻辑结构；物理结构；操作(运算) ；算法
9． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空:
(_____i)；
＝
_____.
_____
【答案】a ＋l ；n%10
【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
10．表达式23＋((12*3﹣2)/4＋34，5/7) ＋108/9的后缀表达式是_____。 【答案】
(表达式中的点(.)是数分隔符，如是三个数)
二、判断题
11．取线性表的第i 个元素的时间同i 的大小有关。（ ）
【答案】 ×
【解析】不一定，如果是顺序存储结构，它访问数据元素时的时间效率都是O(1)。
12．为了很方便的插入和删除数据，可以使用双向链表存放数据。（ ）
【答案】 √
【解析】链式存储结构便于数据的插入和删除，但只能顺序访问表中的元素。
13．由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间更多。（ ）
【答案】×
【解析】希尔排序把序列分成很多小序列，对于直接插入排序，记录少时的效率会大大提高。并且序列在基本有序的情况下，直接插入排序也会提高。
14．数据结构的抽象操作的定义与具体实现有关。（ ）
【答案】 ×
【解析】数据结构抽象操作定义取决于客观存在的一组逻辑特性，与其在计算机内具体表现和实现无关
15．通常使用队列来处理函数或过程的调用。（ ）
【答案】 ×
【解析】经常使用栈来处理函数或过程的调用。
16．即使有向无环图的拓扑序列唯一，也不能唯一确定该图。（ ）
【答案】×
【解析】如果有向无环图的拓扑序列唯一，则能够确定每个结点的唯一前驱和后继，因此能够确定该图。
17．在平衡二又树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。（ ）
【答案】×
【解析】不一定，比如一个平衡因子为1的结点，这时往它的右部插入一个新结点，就不会引起平衡旋转
18．树形结构中元素之间存在一对多的关系。（ ）
【答案】√
【解析】树形结构是非线性结构，存在一对多的关系。
19．最小生成树的Krusakl 算法是一种贪心法。（ ）
【答案】√
【解析】在构建最小生成树常见的有三种贪心算法:。
20．如果数据元素保持有序，则查找时就可以采用折半查找方法。（ ）
【答案】×
【解析】采用折半查找的条件是数据元素有序且存储方式为顺序存储，对于常见的链式存储，