1、1998 年 一、 请译出以下专业术语： 1、 balanced merging 2、 critical paths 3、 directed graph 4、 field identifier 5、 hashing function 6、 linear linked lists 7、 postorder traversal 8、 recursive procedure 9、 spanning tree 10、 top-down approach 二、 简答： 1、递归算法有何特点？定义递归子程 序时应注意什么？ 2、设计一个好的算法，应具有哪几个基本特性？ 3、 32 阶的 B+树，作为有 1
2、00 万个数据项的索引时，树高为多少？若改用 256 阶的 B+树，最小树高为多少？ 4、简述抽象数据类型队列的定义。 5、面向对象的程序设计，有何优点？ 三、 填空： 1、在 Pascal 程序中，标识符要先 _后 _，各标识符的作用域始于 _,止于 _。 2、在 Pascal 程序块中说明的指针变量如 p: real;中的 p 是 _态的变量，它在该程序块被激活时占有特定存区；而 p是 _型的 _态变量，在 _时才 _相应的存区。 3、使用关键路径方法安排施工计划，图中各顶点代表 _，各个边代表 _，边长表示 _，这类图又称作 _网。 4、哈夫曼编码是在已知诸事件出现几率相差 _时，用来
3、_描述事件序列的代码数的方法，请填表并求平均描述一个事件要用的比特数 _。 事件 出现几率 编码 A 0.8 B 0.1 C 0.06 D 0.04 5、若下方为某有向图的邻接矩阵： A 0 5 6 7 B 0 4 3 C 8 0 5 D 5 0 2 E 9 4 0 则有 A 至 E 的最短路径为 _，其长度为 _；而 E 至 A 的最短路径为_，长度为 _。 四、 读程序，写输出： 1、 program test41; Procedure try(x:integer); Var y:0.4 Begin y:=x mod s; x:=x div s; If x0 then try(x); wr
4、ite (y) End; Begin try(3179) end. 输出为： _ 2、若计算机做加法时，把比运算器最低位之后的数据舍掉； Program test42; CONST M=255 ; ONE=1; HALF=0.5 ; TYPE R=0.5; VAR I : R ; F:=HALF ; BEGIN I:=1 ; F:=HALF; WHILE 、 DO BEGIN I:=I+1; ONE ONE+F 时输出为： _ F:=F * HALF END; WRITELN(I: ,I : 3) F 0 时输出为： _ END. (此题无 需填具体值 ) 五、编写程序或子程序： 1、请编写程
5、序读取文件 DATA.TXT 中的数据，存入数组。该文件是由字处理程序准备好的，上面是多次对同一样本测得的值，数值数目小鱼 200 个。再求这些值的均值和标准差 （ ），并剔除与均值距离超过 3 倍标准差的可疑数据复算均值，直到没有可剔除数据为止。 2、使用二叉链接树时，请编写 Pascal 函数，以使在调用时，指定某个树的根指针时，可求出该树内结点的总数。 六、 top 为栈顶指针，各元素皆为记录型，其中 key 字段类型为 INFO; next 字段类型为 LINK。请改正进栈与退栈过程中的错误。 1999 一、 请译为中文： 1、 Breadth-first search 2、 Disc
6、rete event simulation 3、 Enumerated method 4、 Functional designator 5、 Huffman coding 6、 Liner linked lists 7、 Radix sorting 8、 Recursive routine 9、 Spanning tree 10、 Undirected graph 二、 填空： 1、使用关键路径方法安排施工计划时，通常图中各个顶点代表 _，边代表_，边长表示 _。这类图又称作 _网。 2、 B 树是一种 _树，但在其所有叶子结点内都没有 _； B树是_树，在其诸叶子结点中有 _，没有 _。 3
7、、 Pascal 源程序在 _时能发现语法错，修改后应 _；如果通过编译后再运行时出错则为错，这时应在编辑窗口中 _并 _与运行。 4、哈夫曼编码的目的是 _。为此在已知各事件出现几率时，要用 _的码组表示几率最大的事件，且任一个码组都不能称为其它码组的 _。 5、已经定义好了某数组类型，其下标类型为 index=0.nn 为常量标识符 ， a 为该数组类型的变量，在 a1到 an 中有类型为 item 的排序之值。 三、 简答题： 1、试举例说明用程序设计语言描述堆栈结构时，要涉及哪些问题 ？ 2、在程序设计语言中实现递归的条件是什么？编写递归子程序，应注意什么？ 3、动态查找树，有哪几项基
8、本操作？ 4、举例说明有向图的最短路径算法常用于哪几种情形？ 四、 改错： 2、在数组已排好序的前提下， TEST42 函数用来查找其内值为 key 的元素：若未找到，函数值为 0，否则函数值为该元素的下标值。 五、 按要求编写程序或子程序： 请编写函数子程序以计数指定了指针的某个二叉树内结点的总数。 2、 已知：若 n 为自然数，先后调用 RANDOM(n) 将产生在 0 到 n -1 之间取值的伪随机序列。请编写程序给小学生做四则运算的练习，且要求如下： （ 1）每组 25 道题，每题列出题号、模式及等号，请小学生输入答案； （ 2）若答案正确，该题得 4 分，加到总分中 去，再给出下一题
9、的题目；若第一次的答案不正确，则应指出来，随后重显示原题，请学生答第二次，这次若能答对，仍记 2 分，并立即显示下题；在第二次仍算错后，先指出答案错了，再显示正确的式子； （ 3）加、减、乘、除运算的顺序亦由一种随机数来控制，使各种不同运算无规则地交错进行； （ 4）每组中加、减、乘、除和平方（以两相同数相乘表示）各占 5 题； （ 5）每组题做完要显示学生做该组题的成绩； （ 6）在此组题目中要求被减数大于减数，要求除法恰好除尽； （ 7）运算数的位数应当不 使运算超出 2 字节整数的范围。 2001 一、 请译为中文： 1、 adjacency matrix 2、 binary searc
10、h 3、 complete graph 4、 enumerated scalar 5、 heap sorting 6、 linear linked list 7、 minimal spanning tree 8、 optimal merge tree 9、 pattern matching 10、 postfix notation 11、 preorder traversal 12、 refinement approach 13、 shortest path first 14、 threaded file 二、 简答题： 1、试说明描述数据结构时，必须涉及哪些方面？ 2、好的应用程序应当具有哪
11、些共同特点？ 3、编写与使用递归子程序应注意什么？ 4、阶为 32 的 B 树，构成有 10 万个数据项的索引时，最大搜索长度是多少？若改用阶为 128 的 B 树，这一长度变为多少？ 5、说明对字符串的基 本操作是什么？ 6、给出子图的形式定义？并回答连通图的极小连通图是什么？ 三、 填空： 1、在面向对象的程序设计中，对象是包含 _和 _的逻辑实体，实体内专有的这两部分被封装在一起，较好地解决了 _、 _及模块化这 3 个软件的基本问题。 2、 PASCAL 程序中直接说明的指针型变量 p 是 _态变量，在执行 _(p)过程语句后， p成为新的 _态变量，被称作 _的变量。 3、采用哈夫曼编码的目的是 _，为此出现频度最大的事件要用 _的码组来表示，且任一码组都不应成为其他码组的 _；若第 k 个事件出现的几率为PR， 并满足以下等式 PK=1 ,且 Pn Pn+1 ,(0 k 5),则平均码长为 _。 4、使用关键路径方法安排施工计划时，图中各顶点代表 _，各个弧代表 _，弧长表示 _。这类带权的有向无环图又称作 _网。 5、试以 15、 6、 23、 4、 19 为原始序列，请填出用直接插 入法按升序排序时，每趟处理后的情况： _; _; _; _。 6、 结合你对计算机运算器的理解完成本题填空，使程序运行时的输出正确无误。 四、 改错：
