2018年北京市培养单位空间科学与应用研究中心408计算机学科专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key 的记录。设此组记录存放于数组
【答案】算法如下:
本句的有无不影响査找结果
2． 从键盘上输入一串正整数，最后输入-1作为结束标志。如:8，7，1，22，98，46，... ，75，-1。请设计一个非递归程序，创建一棵二叉排序树，并且该二叉排序树也必须是中序线索二叉树。设ltag ，data ，rta9，right) 。该二叉排序树上的结点结构为(teft，其中:data 域为结点的数据场。那么left 域中存在的是该结点的左儿子结点的地址。序遍历次序的前驱结点的地址。
【答案】算法如下:
从键盘上输入一串正整数，建立一棵初始为空的二叉排序树，同时也是线索二叉树
申请结点空间
结点赋值，其线
索初始化
第 2 页，共 32 页
中。若查找成功，则输出该记录在r 数组中的位置及其值，否则显示“not
find ”信息。请编写出算法并简要说明算法思想。
，
，那么left 域中存放的是该结点的按中
，那么right
域中存放的是该结点的右儿子结点的地址。
，那么right 域中存放的是该结点的按中序遍历次序的后继结点地址。
查找结点的插入位置
f 是P 的双亲
根结点
左子女
修改线索
右子树根结点的值大于等于根结点的值
修改线索
读入下个数
算法结束
3． 对给定关键字序号j(1 中找到关键字从小到大排在第j 位上的记 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 4． 元素集合已存入整型数组树T 的非递归算法:CSBT(r，A) 【答案】算法如下: 第 3 页，共 32 页 中，试写出依次取A 中各值构造一棵二叉排序 以存储在数组K 中的n 个关键字，建立一棵初始为空的二叉排序 树 在调用时， T=null f 是P 的双亲 申请结点空间 根结点 左子女 右子树根结点的值大于等于根 结点的值 算法结束 5． 令G=(V, E) 为一个有向无环图，编写一个给图G 中每一个顶点赋以一个整数序号的算法，并满足以下条件:若从顶点i 至顶点j 有一条弧，则应使i 【答案】算法如下: 对以邻接表存储的DAG 图g 重新编号, 使若有 记录结点的逆序序号 ，则编号 求各顶点的入度 二、应用题 6． 请回答下列关于图(Graph)的一些问题: (1)有n 个顶点的有向强连通图最多有多少条边? 最少有多少条边？ (2)表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素? 是否稀疏矩 第 4 页，共 32 页
相关内容
相关标签