2017年北京联合大学信息无障碍辅助技术803软件基础之数据结构考研冲刺密押题
● 摘要
目录
2017年北京联合大学信息无障碍辅助技术803软件基础之数据结构考研冲刺密押题（一） ... 2 2017年北京联合大学信息无障碍辅助技术803软件基础之数据结构考研冲刺密押题（二） . 13 2017年北京联合大学信息无障碍辅助技术803软件基础之数据结构考研冲刺密押题（三） . 25 2017年北京联合大学信息无障碍辅助技术803软件基础之数据结构考研冲刺密押题（四） . 35 2017年北京联合大学信息无障碍辅助技术803软件基础之数据结构考研冲刺密押题（五） . 48
一、填空题
1．
给定一组数据
的值为_____。 【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树：
以它构造一棵哈夫曼树，则树高为_____，
带权路径长度
2． 求最短路径的Dijkstra 算法的时间复杂度为_____。
【答案】
3． 在单链表L 中，指针P 所指结点有后继结点的条件是_____
【答案】
【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。
4． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
【答案】
【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
5． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。
【答案】稳定
6． 在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。
【答案】满；空；n ; 栈底；两栈顶指针相邻（即值之差的绝对值为1） 7． 设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若
的地址为将代入得33。
8． 建立索引文件的目的是_____。 则
【答案】提高查找速度
9． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。
【答案】2
【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。
，）则 的地址为_____。
若
则的地址为
10．顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
二、选择题
11．在一株高度为2的5阶B 树中，所含关键字的个数最少是（ ）
A.5 B.7 C.8 D.14
【答案】A
【解析】根据B 树的定义可知，跟结点最少含有
个关键字，高度为2的阶B
树最少有（5-1）+1=5个关键字，其中根节点含有个关键字，第2层结点含有1关键字。
12．若一棵二叉树的前序遍历序列和后序遍历序列分别为1，2, 3, 4和4, 3, 2, 1，则该二叉树的中序遍历序列不会是（ ）。
A.1, 2.3.4 B.2，3, 4.1 C.3, 2, 4, 1 D.4, 3, 2, 1
【答案】C
【解析】题目中的二叉树的先序序列和后序序列正好相反，这样的二叉树每层只有一个结点。该二叉树的形态如下图所示。
从左至右，这8棵二叉树的中序序列分别为： （1）4. 3. 2. 1， （2）3, 4, 2, 1 （3）2, 4, 3, 1 （4）2, 3, 4，1 （5）1，4，3, 2 （6）1, 3, 4, 2