北师大教育技术数据结构考研历年真题总结

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