2018年大连海事大学信息科学技术学院810数据结构考研仿真模拟五套题
● 摘要
一、填空题
1． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。
【答案】顺序
【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。
2． 在一个具有n 个单元的顺序栈中，假定以地址高端(即下标为n 的单元) 作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top ＝_____。
【答案】top ﹣1
【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，所以top ﹣1。
3． 文件由_____组成；记录由_____组成。
【答案】记录；数据项
4． 建立索引文件的目的是_____。
【答案】提高查找速度
5．
给定一组数据
WPL 的值为_____。
【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树:
6． 在单链表L 中，指针P 所指结点有后继结点的条件是_____
【答案】P ﹣＞next! ＝NULL
【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。
以它构造一棵哈夫曼树，则树高为_____，带权路径长度
7． 深度为H 的完全二叉树至少有_____个结点:至多有_____个结点; H 和结点总数N 之间的关系是_____。 【答案】
8． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。
【答案】起泡；快速
【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为O(n)，
2而快速排序算 法需要比较的次数达到最大，时间复杂度为O (n) 。
9． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
10．—棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为_____。
【答案】2
【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。
二、判断题
11．广义表(((a，b ，C) ，d ，e ，f)) 的长度是4。（ ）]
【答案】 ×
【解析】长度为1。因为只含一个元素即子表(((a，b ，C) ，d ，e ，f)) 。
12．广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（ ）
【答案】 ×
【解析】广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的表，不可能是原子。
13．若中序遍历平衡的二叉排序树，可得到排好序的关键码序列。（ ）
【答案】√
【解析】二叉排序树对于每一个结点，它的左子树的所有结点的值都小于这个结点的值，而它的右子树的所有结点的值都大于这个结点的值。而釆用中序遍历，遍历顺序为左根右，因此可以得到按增序排列的关键码序列。
14．设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度均为O(1)（ ）。
【答案】 √
【解析】入队和出队操作分别在队尾和队头进行，设有尾指针的循环链表对头和尾元素的操作的时间复杂度是O(1)。
15．文件系统采用索引结构是为了节省存储空间。（ ）
【答案】×
【解析】是为了缩短查找的时间，牺牲了一部分存储空间。
16．对大小均为n 的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（ ）
【答案】√
【解析】查找成功的情况下，顺序表和无序表的平均查找长度是相同的，对于查找失败，无序表需要查找到表尾，而顺序表不需要查到表尾就能确定，所以顺序表的查找长度小于无序表的查找长度。
17．数组是同类型值的集合。（ ）
【答案】 ×
【解析】数组是具有相同性质的数据元素的集合，数据元素不仅有值，还有下标。因此，可以说数组是元素值和下标构成的偶对的有穷集合。
18．哈夫曼树无左右子树之分。（ ）
【答案】×
【解析】哈夫曼树就是一棵二叉树。
19．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ）
【答案】 ×
【解析】前者正确，后者错误。顺序存储方式在插入、删除元素时需要挪动大量的元素，执行效率较低。
20．采用深度优先搜索或拓扑排序算法可以判断出一个有向图中是否有环(回路) 。
【答案】√
【解析】采用深度优先搜索算法主要是通过设置标志位可以判断出一个有向图中是否有环。采用拓扑排序算法，如果能够构成一个拓扑排序，则有向图中没有环，否则，有向图中有环。
三、算法设计题