01程序设计与数据结构(1).doc

山 东 大 学 二OO一年招收硕士学位研究生入学考试试题 招生专业 计算机软件与理论 考试科目 程序设计与数据结构 高级语言程序设计（50 分） 一. 简要解释下列概念( 共10分，每个2分) a) 常量 b)赋值相容 c)有序类型 d)逐步求精 e)简单表达式 二. 简要回答下列问题（共9分，每个3分） 1） 试简述过程语句的执行过程？ 2） Pascal中，对合法标识符的规定是什么？ 3） 编程中和数组的异同点是什么？ 三．试编写一递归过程，顺序读入字符，以“。”表示结束，然后安以输入相反的顺序输出读入字符。（10分） 四．选做题（以下两题任选一题，两题均做者按得分少者计）（9分） 1） 给定一正文文件，试编写一程序，输入一单词，输出它在文件中出现的次数。 2） 假定有一班级学生成绩文件，每个记录包含学号和成绩两项内容，试编写一程序，对输入任意整数K，输出文件中成绩为第K位学生的学号。 五．给定一整数单链表，要求编写一过程，不新建任何结点，将此链表强大点顺序倒置。（12分） 数据结构部分（共50分） 一． 概念简答（14） 1． 折半检索 2． 。写出二维数组A[c1..d1,c2..d2]在顺序存储下求数组任意元素A[i,j]的存储位置的计算公式，假设每个元素占一个存储单元，数组的开始位置为X。并以此算出数组A[-3..4,-4..5]中A[2,3]的位置.这里假l=4,X=100,数组以行优先次序存放. 3． 已知一棵二叉树T如下图所示,写出它的完全前序序列. A C B D E G F 4． 最小生成树的prim算法思想 二． 回答问题(22分) 1. 二叉树已知其中序扫描序列和后序扫描序列如何确定这一棵二叉树,并举例说明. 2. 希尔排序的思想 3. 说明平衡二叉树LL型的调整规则，给出图示 4. 给出三种散列过程中处理冲突的方法，并举例说明。 5. 简述递归过程的实现。 三．（8分） 已知一中序线索树,写一算法完成对它的中序扫描。 四． 选做题（以下两题任选一题）（6分） 1． 试述m阶B树的插入和删除法则。 2． 试述m阶B+树定义及B+树的查找算法。