山东大学二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如下图所示,写出它的完全前序序列.4．最小生成树的prim算法思想ABCEDGF二．回答问题(22分)1.二叉树已知其中序扫描序列和后序扫描序列如何确定这一棵二叉树,并举例说明.2.希尔排序的思想3.说明平衡二叉树LL型的调整规则，给出图示4.给出三种散列过程中处理冲突的方法，并举例说明。5.简述递归过程的实现。三．（8分）已知一中序线索树,写一算法完成对它的中序扫描。四．选做题（以下两题任选一题）（6分）1．试述m阶B树的插入和删除法则。2．试述m阶B+树定义及B+树的查找算法。
