2018年北京大学信息科学技术学院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 在一个循环链队中只有尾指针(记为rear ，结点结构为数据域data ，指针域next) ，请给出这种队列的入队和出队操作的实现过程。
【答案】算法如下:
//rear是带头循环链队列的尾指针，本算法将元素X 插入到队尾
//申请结点空间
//将s 结点链入队尾
//rear指向新队尾
//rear是带头结点的循环链队列的尾指针
//本算法执行出队操作，成功输出队头元素；否则给出出错信息
//s指向队头元素
//队头元素出队
//空队列
2． 设有顺序放置的n 个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后。重新安排时，对每粒砾石的颜色只能察看一次，并且只允许交换操作来调整砾石的位置。
【答案】算法如下:
r 为含有n 个元素的线性表，元素是具有红、白和蓝色的砾石，用顺序存储结构存储
本算法对其排序，使所有红色栎石在前，白色居中，蓝色在最后
当前元素是红色
当前元素是白色
当前元素是蓝色
3． 已知关键字序列(
试写出一算法将(
利用(1)的算法写一个建大根堆的算法。 【答案】(1)算法如下:
''
假设
是大堆，本算法把
(2)
4． 已知深度为h 的二叉树，以一维数组应的算法。
【答案】算法如下:
计算深度为h 、以一维数组BT 作为其存储结构的二叉树的叶结点数，n 为数组长度
记叶结点数
若结点无孩子，则
是叶子
存储在数组后一半的元素是叶结点
5． 设从键盘输入一整数的序列:a 1，a 2，a 3，... ，a n ，试编写算法实现:用栈结构存储输入的整数，
当
时，将
入栈；当
时，输出栈顶整数并出栈。算法应对异常情况(入栈满等) 给
出相应的信息。
【答案】算法如下
:
栈空间容量
//s是元素为整数的栈，本算法进行入栈和出栈操作
//top为栈顶指针，定义top ＝0时为栈空
) 是大根堆。
) 调整为大根堆；
调成大堆
作为其存储结构，试编写一算法，求该二叉
树中叶结点的个数，为简单起见，设二叉树中元素结点为非负整数，要求写出算法基本思想及相
//n个整数序列进行处理
//从键盘读入整数序列
//读入的整数不等于﹣1时人栈
//读入的整数等于﹣1时出栈
//算法结束。
二、应用题
6． 设度为m 的树采用多重链表存储。每个结点有m+1个域，其中有1个数据域，m 个指向孩子的指针。则空指针的数目是多少? 说明这种存储方式的利弊。
【答案】(1)空指针数目:n(n>0)个结点的m 度树共有nm 个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有
+1个。
(2)利弊:这种存储结构统一，便于处理但空链域造成存储效率低。
7． 设将n(n>l)个整数存放到一维数组R 中. 试设计一个在时间和空间两方面都尽可能高效的算法，将R 中存有的序列循环左移P(0 中的数据由 . 要求: (1)给出算法的基本设计思想. (2)根据设计思想，采用C 或C++或JA V A 语言描述算法，关键之处给出注释. (3)说明你所设计算法的时间复杂度和空间复杂度. 【答案】(1)算法的基本设计思想:先将n 个数据由得到最终得到结果 (2)用C 语言算法描述如下: 变换为 原地逆置， 然后 ， 再将数组R 中的前，ti-P 个数和后P 个数分别原地逆置，
相关内容
相关标签