2017年辽宁省培养单位沈阳自动化研究所864程序设计之数据结构考研冲刺密押题
● 摘要
目录
2017年辽宁省培养单位沈阳自动化研究所864程序设计之数据结构考研冲刺密押题（一）.... 2 2017年辽宁省培养单位沈阳自动化研究所864程序设计之数据结构考研冲刺密押题（二）.. 13 2017年辽宁省培养单位沈阳自动化研究所864程序设计之数据结构考研冲刺密押题（三）.. 26 2017年辽宁省培养单位沈阳自动化研究所864程序设计之数据结构考研冲刺密押题（四）.. 38 2017年辽宁省培养单位沈阳自动化研究所864程序设计之数据结构考研冲刺密押题（五）.. 50
第 1 页，共 63 页
一、填空题
1． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。
【答案】稳定
2． 设数组储，则元素为_____。
【答案】9174；8788
【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，
则它的存储地址为
若以列序为主存储顺序，则它的存储地址为
3．
给定一组数据
的值为_____。 【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树：
的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存
的存储地址为_____；若以列序为主序顺序存储，则元素
的存储地址
以它构造一棵哈夫曼树，则树高为_____，
带权路径长度
4． 阅读下列程序说明和裎序，填充程序中的_____。
【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编科略）本程序采用非递归的方法，设立一个堆栈交换左、右子树的算法为：
（1）把根结点放入堆栈。
第 2 页，共 63 页
存放还没有转换过的结点，它的栈顶指针为。
（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。（3）重复（2）直到堆栈为空时为止。
（1）
{（2）
If （ （3） ）
} }} 【答案】
【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈足否为空，如果不为空，则取栈顶元素，交换取出节点的左右指针。并将左右指针分别进桟，重复这一操作。完成二叉树左右孩子的交换。
5． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。
【答案】
6． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
7． 文件由_____组成；记录由_____组成。
【答案】记录；数据项
8． 已知二维数组
为1000的连续存储区域时
，
【答案】1196
【解析】设元素的行标为i ，列标为j 。则它的存储位置为：
9． 二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树
10．栈是_____的线性表，其运算遵循_____的原则。
；后进先出 【答案】操作受限（或限定仅在表尾进行插入和删除操作）
第 3 页，共 63 页
中每个元素占4个单元，在按行优先方式将其存储到起始地址的地址是：_____。
11．一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】完全二叉树的高度
12．如果按关键码值递増的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。
【答案】序查找效率一样为
【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺
二、选择题
13．有向带权图如题图所示，若采用迪杰斯特拉（Dijkstra ）算法求从源点a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b ，第二条最短路径的目标顶点是c ，后续得到的其余各最短路径的目标顶点依次是（ ）。
题图有向带权图
A.d , e , f
B.e , d , f C.f , d , e D.f , e , d 【答案】C 。
【解析】本题主要考查Dijkstra 算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。
执行Dijkstra 算法过程中各步的状态表，故后续目标顶点依次为f ，d , e 。
14．对任意一棵树，设它有n 个结点，这n 个结点的度数之和为（ ）。
A.n
第 4 页，共 63 页
相关内容
相关标签