北京师范大学

一九九九年攻读硕士学位研究生入学考试试题

　

专业：计算机应用技术；教育技术学；通信与信息系统

研究方向：各相关的研究方向

考试科目：数据结构与程序设计

一、请译为中文：（10分）

1、 Breadth-first search

2、 Discrete event simulation

3、 Enumerated method

4、 Functional designator

5、 Huffman coding

6、 Linear linked lists

7、 Radix sorting

8、 Recursive routine

9、 Spanning tree

10、Undirected graph

二、填空：（25分）

1、 使用关键路径方法安排施工计划时，通常图中各个顶点代表___________，边代表____________ , 边长表示________。

这类图又称作______________网。

2、 Ｂ树是一种__________树，但在其所有叶子结点内都没有______________；Ｂ+树是______树，

在其诸叶子结点中有_________，没有________。

3、 Pascal　源程序在________时能发现语法错，修改后应__________；如果通过编译后在运行时出错则为错，

这时应在编辑窗口中_________并__________与运行。

4、 哈夫曼编码的目的是__________。为此在已知各事件出现几率时，要用___________的码组表示几率最大的事件，

且任一个码组都不能成为其它码组的________ 。

5、 已经定义好了某数组类型，其下标类型为index某=o ..n {n 为常量标识符}，a为该数组类型的变量，

在a[1]到a[n]中有类型为item的待排序之值。

Procedure sort; {这是__________________________法排序}

Var 1, j:indes; x: item;

Begin

For 1: =2 to n do

Begin x: =a [1]; a[0] := x;

J; 1-1;

While X < a [j] do {这是按____________排序}

Begin a [j+1]: a [J]; j:=j-1 end;

A [j+1]:= x

End

End;

若n=7, item 为整型，

且初始序列为：22　89　5　57　43　17　11　则

　　第一趟　之后：　______________________________________

第二趟　之后：　______________________________________

第三趟　之后：　______________________________________

　　第四趟　之后：　______________________________________

第五趟　之后：　______________________________________

　 第六趟　之后：　______________________________________

最后结果是：　____________________________________________

三、简答题：（２０分）

１、试举例说明用程序设计语言描述堆栈结构时，要涉及那些问题？

２、在程序设计语言中实现递归的条件是什么？编写递归子程序，应注意什么？

３、动态查找树，有哪几项基本操作？

４、举例说明有向图的最短路径算法常用于哪几种情形？

四、改错：（６分）

１、将自然对数底e计算到实型量能表达的最大精度：

PROGRAM TEST41(OUTPUT);

VAR E: REAL; N:INTEGER;

BEGIN N:=ONE; E:=N; ITEM:=E;

WHILE E<> E+ITEM DO

E: = E+ITEM;

N: = N+ONE;

ITEM: = ITEM/N;

WRITELN (‘e=’, E:12:10)

END

２、在数组已排好序的前提下，TEST42函数用来查找其内值为key的元素：若未找到，函数值为o，

否则函数值为该元素的下标值。

FUNCTION TEST42 (L,R:INTEGER):INTEGER; VAR M: INTEGER;

BEGIN

IF L>R THEN TEST42:=O

ELSE

BEGIN M:=(L+R) DIV 2;

IF A［M］=key THEN TEST42:=M;

IF A［M］>key THEN TEST42:=TEST42(L,M-1)

ELSE TEST42:=TEST42(M+1,R)

END;

五、按要求编写程序或子程序：（３９分）

１、在type pin = tree;

tree = record

key: integer;

L, R: pin

End;

之后，有VAR ROOT1, ROOT2,……：PIN;

请编写函数子程序以计数指定了根指针的某个二叉树内结点的总数。（１０分）

２、已知：若n为自然数，先后调用RANDOM（n）将产生在0到n-1之间取值的伪随机序列。

请编写程序给小学生做四则运算的练习，且要求如下：

? 每组25道题，每题列出题号、横式及等号，请小学生输入答案；

? 若答案正确，该题得4分，加到总分中去，再给出下一题的题目；若第一次的答案不正确，则应指出来，

随后重显示原题，请学生答第二次，这次若能答对，仍记2分，并立即显示下题；在第二次仍算错后，

先指出答案错了，再显示正确的式子；

? 加、减、乘、 除运算的顺序亦由一种随机数来控制，使各种不同运算无规则地交错进行；

? 每组中加、减、乘、除和平方（以两相同数相乘表示）各占5题；

? 每组题做完要显示学生做该组题的成绩；

? 在此组题目中要求被减数大于减数，要求除法恰好除尽；

? 运算数的位数应当不使运算超出2字节整数的范围。

注意：填空和改错题请在试题纸上直接做；改错题应尽量少改，只改非改不可之处。

回首页
建议使用IE4.0以上版本浏览器和800*600分辨率显示器浏览
版权所有 (C)2000 考研在线工作室
制作&维护——Freebird