2018年北京市培养单位计算机网络信息中心408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT 中，写出计算该算术表达式值的算法。
【答案】算法如下:
以后序遍历算法求以二叉树表示的算术表达式的
值
.
2． 编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件(字符串中的合法字符为A 〜Z 这26个字母和0〜9这10个数字) 。
【答案】算法如下:
（ ）
//统计输入字符串中数字字符和字母字符的个数
//初始化
//’#’表示输入字符串结束
'//数字字符
//字母字符
//输出数字字符的个数
第 2 页，共 34 页
求左子树表示的子表达式的值
求右子树表示的子表达式的值
("数字％d 的个数＝
//求出字母字符的个数
("字母字符％c 的个数＝
//算法结束。
) ；
) ；
3． 请用流程图或高级语言表示算法。已知有向图有n 个顶点，请写算法，根据用户输入的数对建立该有向图的邻接表。即接受用户输入的
(以其中之一为0标志结束) ，对于每条这样的
边，申请一个结点，并插入到的单链表中，如此反复，直到将图中所有边处理完毕。
提示:先产生邻接表的n 个头结点(其结点数值域从1到n) 。 【答案】算法如下:
建立有向图的邻接表存储结构
输入顶点信息
题目要求两顶点之一为0表示结束
4． 已知关键字序列(
试写出一算法将(
利用(1)的算法写一个建大根堆的算法。 【答案】(1)算法如下:
''
假设
是大堆，本算法把
(2)
5． 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key 的记录。设此组记录存放于数组
【答案】算法如下:
第 3 页，共 34 页
) 是大根堆。
) 调整为大根堆；
调成大堆
中。若查找成功，则输出该记录在r 数组中的位置及其值，否则显示“not
find ”信息。请编写出算法并简要说明算法思想。
本句的有无不影响査找结果
二、应用题
6． 解答问题。设有数据逻辑结构为:
(1)画出这个逻辑结构的图示。
(2)相对于关系R ，指出所有的开始结点和终端结点。 (3)分别对关系R 中的开始结点，举出一个拓扑序列的例子。 (4)分别画出该逻辑结构的正向邻接表和逆向邻接表。 【答案】(1)如图1所示:
图1
(2)开始结点(入度为0) :(3)拓扑序列:
规则:开始结点为K 1或K 2，之后，若遇多个入度为0的顶点，按顶点编号顺序选择。 (4)正向邻接表如图2所示，逆向邻接表如图3所示:
; 终端结点(出度为0) :
。
第 4 页，共 34 页