2018年宁夏大学数学计算机学院408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 假定用两个一维数组L 【N 】和R 【N 】作为有N 个结点1，2，…，N
的二叉树的存储结构。
和
分别指示结点i 的左儿子和右儿子，
，使
) 表示i 的左(右) 儿子为空。试写一个
存放结点i 的父亲；然后再写一个判别结点u 是否
算法，由L 和R 建立一个一维数组为结点V 的后代的算法。
【答案】算法如下:
和
是含有N 个元素且指示二叉树结点i 左儿子和右儿子的一维数组
T 数组初始化
若结点i 的左子女是则结点L 的
双亲是结点
i
若结点i 的右子女是R , 则R 的
双亲是
i
判断U 是否是V 的后代
2． 请运用快速排序思想，设计递归算法实现求n(n>1)个不同元素集合中的第f(
【答案】算法如下:
第 2 页，共 36 页
本算法据此建立结点i 的双亲数组T , 并判断结点U 是否是结点V 的后代
) 小元素。
在后半部分继续进行划分
在前半部分继续进行划分
3． 元素集合已存入整型数组树T 的非递归算法:CSBT(r，A)
【答案】算法如下:
以存储在数组K 中的n 个关键字，建立一棵初始为空的二叉排序
树
在调用时，
T=null
f 是P 的双亲
申请结点空间
根结点
左子女
右子树根结点的值大于等于根
结点的值
算法结束
4． 给定一个整数数组求出b 中最长平台的长度。
【答案】算法如下:
//求具有N 个元素的整型数组b 中最长平台的长度。
//局部最长平台
//新平台起点
(“最长平台长度
5． 已知二叉树丁的结点形式为(llink，data ，count ，riink) ，在树中查找值为X 的结点，若找到， 则记数(count)加1; 否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。
【答案】算法如下:
第 3 页，共 36 页
中，试写出依次取A 中各值构造一棵二叉排序
b 中连续的相等元素构成的子序列称为平台。试设计算法，
在b 数组中起始下标为”，1，
k)
在二叉排序树t 中査找值为x 的结点，若査到，则其结点的count 域值增1，否则，
将其
插入到二叉排序树中
f 指向当前结点的査找值为x 的结点，
双亲
无值为x 的结点，插入之
査询成功，值域为x 的结点的count 增
1
二、应用题
6． 假设以S 和X 分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S 和X 生成的序列表示(如SXSX) 。
(1)试指出判别给定序列是否合法的一般规则；
(2)两个不同合法序列(对同一输入序列) 能否得到相同的输出元素序列? 如能得到，请举列说明。
【答案】(1)通常有两条规则。第一是给定序列中S 的个数和X 的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S 的个数要大于或等于X 的个数。
(2)可以得到相同的输出元素序列。例如，输入元素为A ，B ，C ，则两个输入的合法序列ABC 和BAC 均可得到输出元素序列ABC 。对于合法序列ABC ，使用SXSXSX 操作序列；对于合法序列BAC ，使用SSXXSX 操作序列。
7． 请回答下列关于图(Graph)的一些问题:
(1)有n 个顶点的有向强连通图最多有多少条边? 最少有多少条边？
(2)表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素? 是否稀疏矩阵？
(3)对于一个有向图，不用拓扑排序，如何判断图中是否存在环？ 【答案】⑴最多有n(n－1) 条边；最少有n 条边。 (2)有有
个矩阵元素；不一定是稀疏矩阵(稀疏矩阵的定义是非零元素个数远小于该矩阵元
第 4 页，共 36 页