2018年北京市培养单位计算机网络信息中心408计算机学科专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 设从键盘输入一整数的序列:a 1，a 2，a 3，... ，a n ，试编写算法实现:用栈结构存储输入的整数，
当
时，将
入栈；当
时，输出栈顶整数并出栈。算法应对异常情况(入栈满等) 给
出相应的信息。
【答案】算法如下
:
栈空间容量
//s是元素为整数的栈，本算法进行入栈和出栈操作
//top为栈顶指针，定义top ＝0时为栈空
//n个整数序列进行处理
//从键盘读入整数序列
//读入的整数不等于﹣1时人栈
//读入的整数等于﹣1时出栈
//算法结束。
中找到关键字从小到大排在第j 位上的记
2． 对给定关键字序号j(1 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 3． 当一棵有n( ) 个结点的二叉树按顺序存储方式存储在中时，试写一个算法，求 出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。 【答案】算法如下: 二叉树顺序存储在数组 中，本算法求结点i 和j 的最近公共祖先结点的值 下标为i 的结点的双亲结点的下标 下标为j 的结点的双亲结点的下标 所査结点的最近公共祖先的下标是 ，值是 设元素类型为 整型 4． 已知一棵高度为K 具有n 个结点的二叉树，按顺序方式存储。 (1)编写用前序遍历树中每个结点的非递归算法； (2)编写将树中最大序号叶结点的祖先结点全部打印输出的算法。 【答案】(1)算法如下: 全局变量 递妇遍历以顺序方式存储的二叉树bt ，i 是根结点下标(初始调用时为 1) 是桟s 的栈顶指针，栈容量足够大 访问根结点，设虚结点 以0表示 右子女的下标位置入 栈 沿左子女向下 取出栈顶元素 结束 (2)算法如下: 打印最大序号叶结点的全部袓先 找最大序号叶结点，该结点存储时在最后 的双亲结点f 从结点c 的双亲结点直到根结点， 路径上所有结点均为祖先结点 逆序输出，最老的祖先最后输出 结束 5． 已知二叉树丁的结点形式为(llink，data ，count ，riink) ，在树中查找值为X 的结点，若找到， 则记数(count)加1; 否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。 【答案】算法如下: 在二叉排序树t 中査找值为x 的结点，若査到，则其结点的count 域值增1，否则， 将其 插入到二叉排序树中 f 指向当前结点的査找值为x 的结点， 双亲 无值为x 的结点，插入之 査询成功，值域为x 的结点的count 增 1 二、应用题 6． 主机H 通过快速以太网连接Internet , IP 地址为 表a , 服务器S 的IP 地址为 。 H 与S 使用TCP 通信时, 在H 上捕获的其中5个IP 分组如表a 所示。