北京师范大学1999年攻读硕士学位研究生入学考试数据结构与程序设计试题
专业：计算机应用技术；教育技术学；通信与信息系统 研究方向：各相关的研究方向 一、请译为中文：（10分） 1、Breadth-firstsearch 2、Discreteeventsimulation 3、Enumeratedmethod 4、Functionaldesignator 5、Huffmancoding 6、Linearlinkedlists 7、Radixsorting 8、Recursiveroutine 9、Spanningtree 10、Undirectedgraph 二、填空：（25分） 1、使用关键路径方法安排施工计划时，通常图中各个顶点代表___________，边代表____________,边长表示________。这类图又称作______________网。 2、Ｂ树是一种__________树，但在其所有叶子结点内都没有______________；Ｂ 树是______树，
在其诸叶子结点中有_________，没有________。 3、Pascal 源程序在________时能发现语法错，修改后应__________；如果通过编译后在运行时出错则为错，
这时应在编辑窗口中_________并__________与运行。 4、哈夫曼编码的目的是__________。为此在已知各事件出现几率时，要用___________的码组表示几率最大的事件，
且任一个码组都不能成为其它码组的________。 5、已经定义好了某数组类型，其下标类型为index某=o..n{n为常量标识符}，a为该数组类型的变量，
在a[1]到a[n]中有类型为item的待排序之值。 Proceduresort;{这是__________________________法排序} Var1,j:indes;x:item; Begin For1:=2tondo Beginx:=a[1];a[0]:=x; J;1-1; WhileX<a[j]do{这是按____________排序} Begina[j 1]:a[J];j:=j-1end; A[j 1]:=x End End; 若n=7,item为整型， 且初始序列为：22 89 5 57 43 17 11 则 第一趟 之后： ______________________________________ 第二趟 之后： ______________________________________ 第三趟 之后： ______________________________________ 第四趟 之后： ______________________________________ 第五趟 之后： ______________________________________ 第六趟 之后： ______________________________________ 最后结果是： ____________________________________________ 三、简答题：（２０分） １、试举例说明用程序设计语言描述堆栈结构时，要涉及那些问题？ ２、在程序设计语言中实现递归的条件是什么？编写递归子程序，应注意什么？ ３、动态查找树，有哪几项基本操作？ ４、举例说明有向图的最短路径算法常用于哪几种情形？ 四、改错：（６分） １、将自然对数底e计算到实型量能表达的最大精度： PROGRAMTEST41(OUTPUT); VARE:REAL;N:INTEGER; BEGINN:=ONE;E:=N;ITEM:=E; WHILEE<>E ITEMDO E:=E ITEM; N:=N ONE; ITEM:=ITEM/N; WRITELN(‘e=’,E:12:10) END ２、在数组已排好序的前提下，TEST42函数用来查找其内值为key的元素：若未找到，函数值为o，
否则函数值为该元素的下标值。 FUNCTIONTEST42(L,R:INTEGER):INTEGER;VARM:INTEGER; BEGIN IFL>RTHENTEST42:=O ELSE BEGINM:=(L R)DIV2; IFA［M］=keyTHENTEST42:=M; IFA［M］>keyTHENTEST42:=TEST42(L,M-1) ELSETEST42:=TEST42(M 1,R) END; 五、按要求编写程序或子程序：（３９分） １、在typepin=tree; tree=record key:integer; L,R:pin End; 之后，有VARROOT1,ROOT2,……：PIN; 请编写函数子程序以计数指定了根指针的某个二叉树内结点的总数。（１０分） ２、已知：若n为自然数，先后调用RANDOM（n）将产生在0到n-1之间取值的伪随机序列。
请编写程序给小学生做四则运算的练习，且要求如下： ?每组25道题，每题列出题号、横式及等号，请小学生输入答案； ?若答案正确，该题得4分，加到总分中去，再给出下一题的题目；若第一次的答案不正确，则应指出来，
随后重显示原题，请学生答第二次，这次若能答对，仍记2分，并立即显示下题；在第二次仍算错后，
先指出答案错了，再显示正确的式子； ?加、减、乘、除运算的顺序亦由一种随机数来控制，使各种不同运算无规则地交错进行； ?每组中加、减、乘、除和平方（以两相同数相乘表示）各占5题； ?每组题做完要显示学生做该组题的成绩； ?在此组题目中要求被减数大于减数，要求除法恰好除尽； ?运算数的位数应当不使运算超出2字节整数的范围。 注意：填空和改错题请在试题纸上直接做；改错题应尽量少改，只改非改不可之处。
页:
[1]