2017年北方工业大学计算机学院861数据结构考研仿真模拟题
● 摘要
一、填空题
1． 设为哈夫曼树的叶结点数日，则该哈夫曼树共有_____个结点。
【答案】
【解析】哈夫曼树只有度为0和2的节点。
2． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：
【答案】
【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
3． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。
【答案】
4． 实现字符串拷贝的函数strcpy 为：
【答案】
5． 己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_____次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。
【答案】2；4；3
【解析】二分法查找元素次数列表
查
找100是找到115就停止了。
6． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
7． 在单链表中设置头结点的作用是_____。
【答案】方便运算 8
．
求REPLACE （S ，V , m ）=_____。
【答案】
9． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。
【答案】集合；线性结构；树形结构；图状结构（网状结构）
10．二进制地址为011011110000，大小为
【答案】011011110100；011011100000
011011110000是块的起始地址，
【解析】大小分别为式如下：
当大小为4时，起始地址
为
当大小为16时，起始地址为
：和
其伙伴块的起始地址计算公
和
块的伙伴地址分别为：_____
已
知
二、判断题
11．在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（ ）
【答案】√
【解析】在进行分块查找时，首先查找元素在哪一块，然后在确定的块中查找元素，因此，在索引顺序表中，进行分块查找的平均查找长度不仅与表中元素的个数有关，而且与每块中的元素个数有关。
12．倒排序文件的优点是维护简单。（ ）
【答案】×
【解析】倒排文件的优点是检索记录较快。特别是对某些询问，不用读取记录，就可得到解答。
13．—个稀疏矩阵
【答案】×
【解析】稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三元组中的位置。
14．数据元素是数据的最小单位。（ ）
【答案】
【解析】数据项是数据的不可分割的最小单位，而数据元素是数据的基本单位。
15．取线性表的第i 个元素的时间同i 的大小有关。（ ）
【答案】
【解析】不一定，如果是顺序存储结构，它访问数据元素时的时间效率都是0（1）。
16．—个有向图的邻接表和逆邻接表中的结点个数一定相等。（ ）
【答案】×
【解析】图的邻接表表示法类似于树的孩子链表示法。对于图G 中的每个顶点V i ，该方法把所以邻接于顶点V i 的V j 链接成一个带头。在有向图中，为图中每个顶点V i 建立一个入边表的方法称为逆邻接表示法。
17．在平衡二又树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。（ ）
【答案】×
【解析】不一定，比如一个平衡因子为1的结点，这时往它的右部插入一个新结点，就不会引起平衡旋转
18．数组是同类型值的集合。（ ）
【答案】×
【解析】数组是具有相同性质的数据元素的集合，数据元素不仅有值，还有下标。因此，可以说数组是元素值和下标构成的偶对的有穷集合。
19．在二叉排序树中插入一个新结点，总是插入到叶结点下面。（ ）
【答案】×
采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m
的转置运算。（ ）
和n 的值互换，则就完成了