北师大数据结构考研历年真题总结

北师大数据结构考研历年真题总结1998年一、请译出以下专业术语：1、balancedmerging2、criticalpaths3、directedgraph4、fieldidentifier5、hashingfunction6、linearlinkedlists7、postordertraversal8、recursiveprocedure9、spanningtree10、top-downapproach二、简答：1、递归算法有何特点？定义递归子程序时应注意什么？2、设计一个好的算法，应具有哪几个基本特性？3、32阶的B+树，作为有100万个数据项的索引时，树高为多少？若改用256阶的B+树，最小树高为多少？4、简述抽象数据类型队列的定义。5、面向对象的程序设计，有何优点？三、填空：1、在Pascal程序中，标识符要先_______后________，各标识符的作用域始于_________,止于______________。2、在Pascal程序块中说明的指针变量如p:↑real;中的p是_____态的变量，它在该程序块被激活时占有特定存区；而p↑是_______型的______态变量，在__________时才________相应的存区。3、使用关键路径方法安排施工计划，图中各顶点代表___________，各个边代表_________，边长表示_________，这类图又称作__________网。4、哈夫曼编码是在已知诸事件出现几率相差_______时，用来________描述事件序列的代码数的方法，请填表并求平均描述一个事件要用的比特数________。5、若下方为某有向图的邻接矩阵：A0567∞B∞04∞3C8∞05∞D∞∞502E9∞∞40则有A至E的最短路径为_______，其长度为________；而E至A的最短路径为________，长度为________。四、读程序，写输出：1、programtest41;Proceduretry(x:integer);Vary:0(4)Beginy:=xmods;x:=xdivs;IfxEnd;Begintry(3179)end.输出为：________2、若计算机做加法时，把比运算器最低位之后的数据舍掉；Programtest42;CONSTM=255;ONE=1;HALF=0.5;TYPER=0....5;VARI:R;F:=HALF;BEGINI:=1;F:=HALF;WHILE①、②DOBEGINI:=I+1;①ONEF:=F*HALFEND;WRITELN(‘I:’,I:3)②FEND.(此题无需填具体值)五、编写程序或子程序：1、请编写程序读取文件DATA.TXT中的数据，存入数组。该文件是由字处理程序准备好的，上面是多次对同一样本测得的值，数值数目小鱼200个。再求这些值的均值和标准差（），并剔除与均值距离超过3倍标准差的可疑数据复算均值，直到没有可剔除数据为止。2、使用二叉链接树时，请编写Pascal函数，以使在调用时，指定某个树的根指针时，可求出该树内结点的总数。六、top为栈顶指针，各元素皆为记录型，其中key字段类型为INFO;next字段类型为LINK。请改正进栈与退栈过程中的错误1999一、请译为中文：1、Breadth-firstsearch2、Discreteeventsimulation3、Enumeratedmethod4、Functionaldesignator5、Huffmancoding6、Linerlinkedlists7、Radixsorting8、Recursiveroutine9、Spanningtree10、Undirectedgraph二、填空：1、使用关键路径方法安排施工计划时，通常图中各个顶点代表______________，边代表________________，边长表示____________。这类图又称作_________________网。2、B树是一种__________树，但在其所有叶子结点内都没有____________；B﹢树是___________树，在其诸叶子结点中有____________，没有___________。3、Pascal源程序在____________时能发现语法错，修改后应____________；如果通过编译后再运行时出错则为错，这时应在编辑窗口中__________并__________与运行。4、哈夫曼编码的目的是_______________________。为此在已知各事件出现几率时，要用___________的码组表示几率最大的事件，且任一个码组都不能称为其它码组的________。5、已经定义好了某数组类型，其下标类型为index=0..n{n为常量标识符}，a为该数组类型的变量，在a[1]到a[n]中有类型为item的排序之值。三、简答题：1、试举例说明用程序设计语言描述堆栈结构时，要涉及哪些问题？2、在程序设计语言中实现递归的条件是什么？编写递归子程序，应注意什么？3、动态查找树，有哪几项基本操作？4、举例说明有向图的最短路径算法常用于哪几种情形？四、改错：2、在数组已排好序的前提下，TEST42函数用来查找其内值为key的元素：若未找到，函数值为0，否则函数值为该元素的下标值。五、按要求编写程序或子程序：请编写函数子程序以计数指定了指针的某个二叉树内结点的总数。2、已知：若n为自然数，先后调用RANDOM(n)将产生在0到n-1之间取值的伪随机序列。请编写程序给小学生做四则运算的练习，且要求如下：（1）每组25道题，每题列出题号、模式及等号，请小学生输入答案；（2）若答案正确，该题得4分，加到总分中去，再给出下一题的题目；若第一次的答案不正确，则应指出来，随后重显示原题，请学生答第二次，这次若能答对，仍记2分，并立即显示下题；在第二次仍算错后，先指出答案错了，再显示正确的式子；（3）加、减、乘、除运算的顺序亦由一种随机数来控制，使各种不同运算无规则地交错进行；（4）每组中加、减、乘、除和平方（以两相同数相乘表示）各占5题；（5）每组题做完要显示学生做该组题的成绩；（6）在此组题目中要求被减数大于减数，要求除法恰好除尽；（7）运算数的位数应当不使运算超出2字节整数的范围。2021一、请译为中文：1、adjacencymatrix2、binarysearch3、completegraph4、enumeratedscalar5、heapsorting6、linearlinkedlist7、minimalspanningtree8、optimalmergetree9、patternmatching10、postfixnotation11、preordertraversal12、refinementapproach13、shortestpathfirst14、threadedfile二、简答题：1、试说明描述数据结构时，必须涉及哪些方面？2、好的应用程序应当具有哪些共同特点？3、编写与使用递归子程序应注意什么？4、阶为32的B树，构成有10万个数据项的索引时，最大搜索长度是多少？若改用阶为128的B树，这一长度变为多少？5、说明对字符串的基本操作是什么？6、给出子图的形式定义？并回答连通图的极小连通图是什么？三、填空：1、在面向对象的程序设计中，对象是包含_______和_________的逻辑实体，实体内专有的这两部分被封装在一起，较好地解决了________、__________及模块化这3个软件的基本问题。2、PASCAL程序中直接说明的指针型变量p是________态变量，在执行________(p)过程语句后，p↑成为新的________态变量，被称作__________的变量。3、采用哈夫曼编码的目的是__________，为此出现频度最大的事件要用__________的码组来表示，且任一码组都不应成为其他码组的___________；若第k个事件出现的几率为PR，并满足以下等式ΣPK=1,且PnPn+1,(04、使用关键路径方法安排施工计划时，图中各顶点代表________，各个弧代表________，弧长表示___________。这类带权的有向无环图又称作_________网。5、试以15、6、23、4、19为原始序列，请填出用直接插入法按升序排序时，每趟处理后的情况：_______________________;_______________________;_______________________;_______________________。6、结合你对计算机运算器的理解完成本题填空，使程序运行时的输出正确无误。四、改错：五、请按要求编程序：1、根据公式：编写求e值到尽可能精确，并将结果输出的程序。2、某系统选拨优秀毕业生，要求对近200名毕业班学生的成绩进行统计排序。设已将课程分成公共基础课和专业课两类，每个学生分类计算的两个平均分也已经存入了名为‘LIST.TXT’的文件，该文件是用写字板编辑成的，文件内每行存入一个学生的信息，最左方是学号，随后先是公共基础课平均分，后是专业课平均分，最右方是学生姓名，各项之间有一个或多个空格。学号是8位的数码字符串；两个平均分皆为带两位小数的实数；学生姓名为最多10位的字符串。请编写程序，按公共基础课占4成，专业课占6成计算出综合成绩，并给出最终排好序的选拨名单。排队的规则是先分两档，进入第1档的条件是两类课程平均分都不低于90分，然后在每档内按照综合成绩的高低排序。排好序的结构嬴荡记入一个名为‘SORTED.TXT’文本文件，且将钱20名的情况送往屏幕。文件及屏幕上数据的格式是：名次姓名学号档次综合成绩公共课成绩专业课成绩2021一、请翻译成中文：1、allocationstrategy2、boundarytagmethod3、mergeinsertionsort4、patternmatching5、threadedbinarytrees6、adjacencymultilists7、asymptotictimecomplexity8、indexedsequentialsearch9、implementinglinkedlistsusingarray10、quadraticprobing11、circularlinkedlist12、discreteeventsimulation二、简答题：1、从概念上讲，树、森林和二叉树是三种不同的数据结构，将树、森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。2、面向对象的程序设计方法有何特点，并说明继承的含义。3、一棵二叉树的中序遍历序列为：ECBHFDJIGA，后序遍历序列为ECHFJIGDBA，请构造出这棵二叉树，并写出它的先序遍历序列。4、线性表的顺序存储结构具有三个弱点：第一，在作插入或删除操作时，需要移动大量元素；第二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；第三，表的容量难以扩充。试问，线性表的链式存储结构是否一定能够克服上述三个弱点？请简述之。5、简要叙述Hash表技术中冲突的概念，并给出三种解决冲突的办法。6、何谓算法，其基本特征是什么？三、填空：1、稀疏矩阵一般的压缩存储方法有两种，即____________和____________。2、递归函数f(n)=f(n-1)+n(n1)的递归出口是________，递归体是_______。将递归算法转换成对应的非递归算法时，通常需要使用___________。3、广义表（a,b,(c,d),e,((i,j),k)）的长度是________，深度是_______；广义表运算式HEAD(TAIL((x,y,z),(a,b,c)))的结果为____________。4、以数据集（4,5,6,7,10,12,18）为结点权值所构造的哈夫曼树为_______，其带权路径长度为_____________。5、已知序列{18,19,62,45