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

..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、哈夫曼编码是在已知诸事件出现几率相差_______时,用来________描述事件序列的代码数的方法,请填表并求平均描述一个事件要用的比特数________。事件出现几率编码A0.8B0.1C0.06D0.045、若下方为某有向图的邻接矩阵：A0567∞B∞04∞3C8∞05∞D∞∞502E9∞∞40则有A至E的最短路径为_______,其长度为________；而E至A的最短路径为________,长度为________。读程序,写输出：programtest41;Proceduretry<x:integer>;Vary:0...4Beginy:=xmods;x:=xdivs;Ifx<>0thentry<x>;write<y>End;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;①ONE<>ONE+F时输出为：_________F:=F*HALFEND;WRITELN<‘I:’,I:3>②F<>0时输出为：_________END.<此题无需填具体值>五、编写程序或子程序：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,否则函数值为该元素的下标值。按要求编写程序或子程序：请编写函数子程序以计数指定了指针的某个二叉树内结点的总数。已知：若n为自然数,先后调用RANDOM<n>将产生在0到n-1之间取值的伪随机序列。请编写程序给小学生做四则运算的练习,且要求如下：〔1每组25道题,每题列出题号、模式及等号,请小学生输入答案；〔2若答案正确,该题得4分,加到总分中去,再给出下一题的题目；若第一次的答案不正确,则应指出来,随后重显示原题,请学生答第二次,这次若能答对,仍记2分,并立即显示下题；在第二次仍算错后,先指出答案错了,再显示正确的式子；〔3加、减、乘、除运算的顺序亦由一种随机数来控制,使各种不同运算无规则地交错进行；〔4每组中加、减、乘、除和平方〔以两相同数相乘表示各占5题；〔5每组题做完要显示学生做该组题的成绩；〔6在此组题目中要求被减数大于减数,要求除法恰好除尽；〔7运算数的位数应当不使运算超出2字节整数的范围。..2001请译为中文：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,且Pn>Pn+1,<0<k<5>,则平均码长为__________。4、使用关键路径方法安排施工计划时,图中各顶点代表________,各个弧代表________,弧长表示___________。这类带权的有向无环图又称作_________网。5、试以15、6、23、4、19为原始序列,请填出用直接插入法按升序排序时,每趟处理后的情况：_______________________;_______________________;_______________________;_______________________。结合你对计算机运算器的理解完成本题填空,使程序运行时的输出正确无误。改错：请按要求编程序：1、根据公式：编写求e值到尽可能精确,并将结果输出的程序。2、某系统选拨优秀毕业生,要求对近200名毕业班学生的成绩进行统计排序。设已将课程分成公共基础课和专业课两类,每个学生分类计算的两个平均分也已经存入了名为‘LIST.TXT’的文件,该文件是用写字板编辑成的,文件内每行存入一个学生的信息,最左方是学号,随后先是公共基础课平均分,后是专业课平均分,最右方是学生姓名,各项之间有一个或多个空格。学号是8位的数码字符串；两个平均分皆为带两位小数的实数；学生姓名为最多10位的字符串。请编写程序,按公共基础课占4成,专业课占6成计算出综合成绩,并给出最终排好序的选拨名单。排队的规则是先分两档,进入第1档的条件是两类课程平均分都不低于90分,然后在每档内按照综合成绩的高低排序。排好序的结构嬴荡记入一个名为‘SORTED.TXT’文本文件,且将钱20名的情况送往屏幕。文件及屏幕上数据的格式是：名次姓名学号档次综合成绩公共课成绩专业课成绩..2003请翻译成中文：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<n>1>的递归出口是________,递归体是_______。将递归算法转换成对应的非递归算法时,通常需要使用___________。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,9,37,78,69,88},采用快速排序法对该序列作升序排列时每一趟的结果为:初始：____________________________第一趟：____________________________第二趟：____________________________第三趟：____________________________第四趟：____________________________第五趟：____________________________第六趟：____________________________第七趟：____________________________第八趟：____________________________6、对于长度为n的线性表,顺序查找法的平均查找长度为______,其时间复杂度为_______;二分查找法的平均查找长度为_______,其时间复杂度为_____;若采用分块查找〔假定总块数和每块长度均接近,其时间复杂度为_____。7、在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中,排序是不稳定的有________、_________、__________、__________,平均比较次数最少的排序是_________,需要内存容量最多的排序是_________。8、下面算法是实现对以邻接表存储的图进行深度优先遍历递归算法,请空白处填上适当的内容。Typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];VoidDFSTraverse<ALGraph*G>{inti;for<i=0;i<G->n;i++>visited[i]=_____________;for<i=0;i<G->n;i++>if<!Visited[i]>_________________;}voidDFS<ALGraph*G,inti>{EdgeNode*p;printf<"visitvertex:%c",G->adglist[i],vertex>;visited[i]=TRUE;p=G->adglist[i].firstedge;While<____________>{if<!Visited[p->adjvex]>DFS<G,p->adjvex>;P=___________;}}改错：以下给出在链栈中实现插入操作的算法Push,其类型和算法说明如下〔2处错误：typedefstructstacknode{DataTypedata;structstacknode*next;}StackNode;typedefStacknODE*ListStack;VoidPush<LinkStackls,DataTypex>{//将元素x插入链栈头部p=<StackNode*>malloc<sizeof<StackNode>>;p->number=x;p->next=ls;ls=p->data;}以环形顺序队列的存储方式实现队列的基本算法如下〔3处错误：#include<iostream.h>#defineMaxLen20typedefcharelemtype;typedefstruct{elemtypedata[MaxLen];intfront,rear;}queue;//front为队头指针,rear为队尾指针。voidinit<queue*sq>//初始化队列{sq->front=0;sq->rear=0;}intinqueue<queue*sq,elemtypex>//入队列{if<<sq->rear+1>%MaxLen==sq->front>//队列上溢出return0;else{sq->rear=<sq->rear+1>%MaxLen;sq->data<sq->rear+1>=x;return1;}}intoutqueue<queue*sq,elemtype*x>//出队列{if<<sq->front>==sq->rear>//队列下溢出return0;else{sq->front=<sq->front+1>%MaxLen;*x=sq->data[sq->front+1];return1;}}intempty<queue*sq>//判断队列是否为空队{if<<sq->rear>==sq->front>return1;elsereturn0;}intgethead<queue*sq,elemtype*x>//取队头{if<<sq->rear>==sq->front>return0;//队列下溢出else{*x=sq->data[sq->front>%MaxLen];return1;}}请按要求编写程序：已知函数M<x>定义如下：编写一个非递归函数计算给定x的M<x>值；编写一个递归函数计算给定x的M<x>值。设计一种算法用于判定一棵给定的二叉树是否为完全二叉树。设有文件"PERSONEL.TXT"存放职工的数据,该文件是用写字板编辑成的,其内容包括：职工号、姓名、性别、年龄、职称、基本工资、津贴、奖金、扣款、实发工资等〔假设没有重复的职工号。编写实现如下功能的函数：在PERSONEL.TXT文件末尾追加职工记录,其中基本工资、津贴、奖金、扣款由用户输入,而实发工资由计算机自动计算,即实发工资=基本工资+津贴+奖金-扣款；根据用户输入的职工号和对应的数据修改该职工的数据；根据用户输入的职工号删除该职工的数据；根据用户输入的工资数,显示实发工资数额大于该工资数的职工的所有信息,并送往屏幕,其显示格式为：职工号姓名性别年龄职称基本工资津贴奖金扣款实发工资..2004请翻译成中文:1、randomnumbermethod2、sparsematrix3、replacementselectionsort4、Huffmancodes5、minimalspanningtree6、threadedlinkedlists7、IndexedSequentialAccessMethod8、DynamicSearchTable9、polymorphicdatetype10、garbagecollection11、foldingattheboundaries12、orthogonallist简答题：1、简述数据结构的四种基本关系并画出它们的关系图。2、何谓队列的上溢现象和假溢现象？解决它们有哪些方法？3、回答下列问题：〔1什么叫Huffman树？〔2什么叫B树？〔3什么是图的生成树？〔4什么是最小-最大堆？4、简述无向图和有向图有哪几种存储结构,并说明各种结构在图中的不同操作〔图的遍历,有向图的拓扑排序等中有什么样的优越性?5、评价一个算法一般从哪些方面进行？和算法执行时间相关的因素有哪些？6、指出对象和类的区别,使用矩形类说明对象和类的区别。判断题,错误的请说明理由。1、栈的输入序列为123...n,输出序列为a1a2...an,若ai=n<1≤i<n-1>,则ai>ai+1>an。〔2、无向图的邻接矩阵一定是对称矩阵,且有向图的邻接矩阵一定是非对称矩阵。〔3、哈希表的查找效率主要取决于哈希建表时所选取的哈希函数和处理冲突的方法。〔4、一个稀疏矩阵Am*n采用三元组形式表示。若把三元组中有关行下标与列下标的值互换,并把m和n的值互换,则就完成了Am*n的转置运算。〔填空：1、表长为n的顺序表中,若在第i个数据元素〔1≤i≤n+1之前插入一个数据元素,需要向后移动________个数据元素；删除第i个元素需要向前移动______个数据元素；在等概率的情况下,插入一个数据元素平均需要移动_____个数据元素,删除一个数据元素平均需要移动_______个数据元素。2、用某种排序方法对线性表{24,88,21,48,15,27,69,35,20},进行排序时,元素序列的变化情况如下：〔124,88,21,48,15,27,69,35,20〔315,20,21,24,35,27,48,69,88〔415,20,21,24,27,35,48,69,88则所采用的排序方法是_________。快速排序B、选择排序C、希尔排序D、归并排序3、在AOE网中,结点表示_________,边表示_________,从源点到汇点路径上各活动的时间总和最长的路径称为____________。4、在堆排序、快速排序和归并排序中,若从节省存储空间考虑,则应首先选取_________方法,其次选取__________方法,最后选取_________方法；若只从排序结果的稳定性考虑,则应选择_________方法；若只从平均情况下排序的速度来考虑,则应选取__________方法；若只从最坏情况下排序最快并且要节省内存考虑,则应选取__________方法。5、已知广义表〔〔a,b,c,<d,e,f>,从A中取出原子e的运算时______。<1>tail<head<A>><2>head<tail<A>><3>head<tail<tail<head<A>>>><4>head<head<tail<tail<A>>>>改错：1、假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点〔不设头指针,类型定义和出对与入队算法如下。〔2处错误：2、以顺序栈的存储方式实现栈的基本运算,其算法如下〔4处错误：应用题：1、已知一个长度为12的表{Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec},〔1试按表中元素的顺序依次插入一棵初始为空的二叉排序树〔字符之间以字典顺序比较大小,请画出对应的二叉排序树,并求出在等概率情况下对此有序表进行折半检索时检索成功的平均检索长度。若对表中元素先进行排序构成有序表,试求在等概率情况下对此有序表进行折半检索时检索成功的平均检索长度。按表中元素顺序构造一棵平衡二叉排序树,试求在等概率的情况下检索成功的平均检索长度。已知一棵二叉树的中序遍历序列和按层次遍历的序列,试编写算法生成此二叉树的二叉链表。3、已知递归函数F<m><其中DIV为整除>：写出求F〔m递归算法；写出求F〔m的非递归算法。..2005请翻译成中文：1、VirtualStorageAccessMethod2、directedacyclinegraph3、balancedbinarytree4、havevariablesizerecords5、recursivefunction6、weightedpathlength7、LeastSignificationDigitfirst8、Fibonaccisearch9、immediatesuccessor10、fixed-aggregatedatatype11、randomprobing12、diminishingincrementsort简答题：1、简述数据的四种存储方式及各自特点。2、线性表的基本运算包括哪些？简述线性表的链式存储结构的几种形式。3、名词术语解释：〔1平均查找长度〔AVL〔2抽象数据类型〔3广义表〔4强连通图与强连通分量4、什么叫AOE网中的源点、汇点和关键路径,一个正常的AOE网中只有一个源点、汇点和一条关键路径吗？5、描述头指针、头结点和首元结点三个概念的区别。6、试比较顺序文件、索引顺序文件和散列文件的存储代价、检索、插入及删除记录时的优点和缺点。判断题,错误的请说明理由。1、子串定位函数的时间复杂度在最坏情况下为O<n×m>,因此子串定位函数没有实际使用的价值。〔2、一般来说,若深度为k的n个结点的二叉树只有最小路径长度,那么从根结点到第k-1层具有最多的结点数为2k-1-1,余下的n-2k-1+1个结点在第k层的任一位置上。〔3、用邻接矩阵存储一个图时,所占用的存储空间大小只与图中结点的个数有关,而与图的边数无关。〔4、对于满足折半查找和分块查找条件的文件而言,无论它存放在任何介质上,均能进行顺序查找,折半查找和分块查找。〔填空：1、一维数组的逻辑结构是_________,存储结构是________；对二维或多维数组,分为按________和__________两种不同的存储方式。2、具有n个结点的完全二叉树若层次从上到下、从左到右对其编号〔根结点为1,则编号最大的分支结点序号是________。编号最小的分支结点序号是_______,编号最大的叶子结点序号是______,编号最小的叶子结点是_______。3、遍历图的过程实质上是______。设图G有n个顶点和e条边,则对用邻接矩阵表示的图进行深度或广度优先搜索遍历时的时间复杂度为________,而对用邻接表表示的图进行深度或广度优先搜索遍历时的时间复杂度为_______；图的深度或广度优先搜索遍历时的空间复杂度均为_________。4、构造哈希〔Hash函数的方法有_________、__________、__________等。5、参照下面的树,回答各个问题：〔1如果插入结点33,它的父结点是________；〔2如果插入结点64,它的父结点是________；〔3如果删除结点30后,根据算法将选取_______结点来替换；〔4如果删除结点90后,根据算法将选取_______结点来替换；〔5如果删除了根结点50,则应该用_______结点来替换。改错：1、以下算法使用少一个元素空间的方法来区别循环队列的队空和队满条件,借以描述出队、入队的基本操作〔2处错误：2、以下算法通过单链表实现了接收用户输入的一个字符串,统计其中出现过的所有字符,并按其出现的频率从高到低的顺序排列输出。〔4处错误应用题：给出一组关键字30,19,26,48,59,11,53,10,分别写出按下列各种排序方法进行排序时的变化过程：〔1归并排序,每归并一次书写一个次序。〔2快速排序,每划分一次书写一个次序。〔3堆排序,先建成一个堆,然后每从堆顶取下一个元素后,将堆调整一次。已知Ackermann函数的定义如下：〔1写出Ack<2,1>的计算过程；〔2写出计算Ack<m,n>的非递归算法。3、已知深度为n的二叉树采用顺序存储结构存放数组B[1...2n-1]中,请编写一个非递归算法产生该二叉树的二叉链表结构。设二叉链表节点的结构为：指向左右孩子的指针lchild,rchild及数据域data,根节点的指针为t。..2006简答题：列举数据逻辑结构上定义的基本运算,简述度量算法效率的方法及各自特点。根据结构中数据元素之间存在的关系,比较树形结构与线性结构的异同。名词术语解释：〔1循环队列〔2十字链表〔3线索二叉树〔4索引顺序文件说明在图的遍历中,设置访问标志数组的作用。并说明采用图的深度优先搜索模式能否完成拓扑排序的基本思路。简述哈希表的设计过程以及哈希函数的构造原则,并列举常用的构造哈希函数的方法。什么是串的存储密度？如果串采用块链结构存储,试分析：〔1一个节点只存储一个字符与一个节点存储4个字符两种情况下串的存储密度〔字链指针占用4个字节,一个字符占用1个字节；〔2上述两种情况下,哪种存储结构的空间利用率高。判断题,错误的说明理由。图G的一棵最小生成树的代价未必小于G的其他任何一棵生成树的代价。〔二维数组A的每个元素是由6个字符组成的串,其行下标i=0、1、...、8,列下标j=1、2、...、10,若A按行先存储,元素A[8,5]的起始地址与当A按列先存储时的元素A[5,10]的起始地址相同〔设每个字符占一个字节。〔用邻接矩阵A表示图,判定任意两个结点Vi和Vj之间是否有长度为m的路径相连,则只要检查Am的第i行和第j列的元素是否为0即可。〔已知待排序的n个元素可以分为n/k组,每个组包含k个元素,且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素,若采用基于比较的排序,其时间下界应为O<nlogk>。〔>填空：下列程序的功能是按照右侧的格式输出6行杨辉三角形。请填空将程序补充完整。具有条边的无向图称为________,简称为_________,其中n表示无向图中顶点的个数,是具有n个顶点无向图所拥有边的__________。在AOV网中不可以出现有向环或回路,这意味着某项活动是________,这样的工程无法进行,对于计算机中的程序流程图来说就是__________,也相当于操作系统中的__________。比较以下4种排序方法,填写下表：函数expand<chars[],chart[]>在将字符串s复制到字符串t时,将其中的换行符和制表符转换为可见的转义字符,即用"\n"表示换行符,用"\t"表示制表符,填空将程序补充完整。五、应用题：1、已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1:2h-1]中,请写算法,产生该二叉树的二叉链表结构,设二叉链表中链结点的构造为：lchilddatarchild根结点所在链结点的指针有BT给出。依据图1所示无向图,分别使用Prim和Kruskal算法,完成如下要求：写出构造该图的最小生成树的过程；写出相应的构造最小生成树算法。设有n个活动需要演讲会场,而在同一时间内会场只能分配给其中一个活动。如果用E表示活动集合,E={1,2,...,n},每个活动i使用会场有一个起止时间〔si,fi,其中si<fi。如果两个活动i和j的时间段不相交,则称活动i与活动j是相容的,前后活动的时间边界重合不算相交。给定规模为10的问题实例E如下：{<1,3>,<0,5>,<7,10>,<6,7>,<3,6>,<8,9>,<1,2>,<11,12>,<8,11>,<10,13>}给出以上问题实例的解及求解过程。设计一个求解"活动方案"的算法,使得在方案中安排的所有活动都是相容的且活动数目最多。..2007填空：1、设将整数1,2,3,4依次进栈,可能的出栈序列有〔种；下面四个输出序列中〔不可能是它的输出序列。A、1,3,2,4B、2,3,4,1C、3,4,2,1D、4,3,1,2具有m个叶结点的霍夫曼树,其分支节点总数为〔；对电文"dodoesdoordoors"进行霍夫曼编码,其霍夫曼树的节点个数为〔,该电文的总编码长度为〔。有n个顶点的有向连通图最多有〔条边,最少有〔条边；其存储方式可以为〔、〔或〔。设哈希表中已存在多个记录〔如下所示。哈希函数为H<K>=KMOD11,用二次探测再散列处理冲突。请问关键字为94的记录的存储地址是〔。0123456789104516396276B-树只有一个查找的入口指针,指向其〔；B+树有两个查找的入口指针,其中一个指向〔,另一个指向〔。下面是中序遍历的非递归算法,请在算法的空缺处填入适当内容,使之能够正常工作。算法中设置了一个顺序存储结构的堆栈STACK[M]来保存遍历过程中结点的存储位置,栈顶指针为top,初始时top=0；同时,算法中还设置了一个活动指针变量p,用来指向当前要访问的那个结点,初始时指向二叉树的根结点。判断下面个陈述是否正确,并说明理由。使用三元组表表示稀疏矩阵可以节省存储空间。度为2的树是二叉树。当在函数定义中作为形参时,chars[]和char*s是等价的。二叉树叶结点的数目只与度为2的结点的数目有关。对于有序链表可以采用折半查找。在执行某种排序算法的过程中,出现了数据元素朝着与其在最终排序结果中的位置相反方向移动的情况,因此断定该排序算法是不稳定的。简答题：已知有实现同一功能的两个算法,其时间复杂度分别为O<2n>和O〔n10,假设现实计算机可连续运行的时间为107秒〔约100天,又每秒可执行基本操作为105次。试问在此条件下,这两个算法可解决的问题的规模〔即n的范围各为多少？哪个算法更合适？试说明理由。已知广义表L=〔<a,b>,<c,<d,<e>>>,f试利用广义表取表头head<L>和取表尾tail〔L的基本运算,将原子c从广义表L中分解出来,请写出运算表达式。请给出下列表达式的运算结果：head<tail<head<tail<L>>>>tail<tail<head<L>>>能够生成下图所示的二叉排序树的关键字初始序列有几种？写出所有这些序列组合。已知一带权连通图采用邻接矩阵存储方法,并且邻接矩阵采用三元组表来表示,其中第一个三元组〔5,5,16分别表示邻接矩阵的行数、列数与非零元素的个数,从第二个三元组开始,依次按行序为主序的次序分别给出16个非零元素,它们依次为〔1,2,7、〔1,3,6、〔1,4,9、〔2,1,7、〔2,3,8、〔2,4,4、〔2,5,4、〔3,1,6、〔3,2,8、〔3,4,6、〔4,1,9、〔4,2,4、〔4,3,6、〔4,5,2、〔5,2,4、〔5,4,2。请分别画出该带权连通图的两棵最小生成树。将数组13,5,10,7,27,9,4,15,33,20调整成极小堆,画出这个极小堆的逻辑图和内存映像。设某有序的连续顺序文件的记录按关键字值从小到大排列,请用文字叙述在该文件中采用折半查找方法确定一个记录存在与否的过程。改错：假设带头结点的单链表中只设一个指针指向头节点,下面算法将实现以下功能：在单链表中查找值为value的节点并删除。已知二叉树的存储结构为二叉链表,下面算法将实现以下功能：将二叉树T中分支节点按照后序遍历序列逆序保存在单链表L中。应用题：已知一个非空的线性链表的首结点地址由list指出,请编写程序,将链表中数据域值最小的那个结点移到链表的最前面去。已知某二叉树有n个结点,各结点存放的值是互不相同的字符,其先序遍历和中序遍历的序列分别存放在数组pre和in中。编写一个函数建立该树的二叉链表。假设已知二叉树的谦虚便利序列为ABCEFHIDG,中序遍历序列为ECHFIBDGA,请画出该二叉树,并给出它的后序遍历序列。有一只小袋鼠路过一条河,看到河中一块石头上有一个布娃娃,于是它想跳过去把布娃娃捡起来玩。可是那块石头离它的距离超出了它所能跳的最远距离,因此小松鼠决定把河中其他一些石头当作中继站,这样它就可以每次跳比较短的距离〔但需要跳多次,最后到达布娃娃所在的那块石头上。在这样一串石头间连续跳跃,显然小袋鼠一次能够跳跃的距离必须至少等于这串石头间间隔最远的距离,这一距离称为该串石头间的跳跃距离例如,如果在袋鼠跳跃路径上各石头之间的间距分别为2,1,3,3,5和2,则这里的跳跃距离为5。输入：第一个输入数据是一个整数n〔2≤n≤200。接下来的n组数据是n组二维坐标。其中第一组为小袋鼠所在位置的坐标,第二组为布娃娃所在石头的坐标,其余n-2组为可以当作中继站的其他石头的坐标。输出：袋鼠到达布娃娃所要跳的最小跳跃距离。按照上述的输入、输出要求编写解决该问题的算法。用下面的输入实例给出算法的运行过程及结果。输入实例：5,〔2,4,〔4,5,〔3,5,〔1,2,〔4,1..2008简答题：数据类型和抽象数据类型的含义。算法的特性与算法的时间复杂度。快速排序方法最好和最坏的情况是什么？简要分析说明。栈、队列的共同点与不同点,说明其属于线形表的原因。方法选择：一棵二叉排序树中各结点不相同,欲得到一个由大到小的结点值递减序列,你认为采用什么方法能得到要求的结果？设有1000个无序元素,仅要求找出前10个最小元素,在下列排序方法中〔归并排序,基数排序,快速排序,堆排序,插入排序,哪种方法最好,为什么？三、已知一个循环单链表la,av是可利用栈的头指针,请用3个赋值语句,完成将整个循环链表释放的功能。〔即将表整个归还到可用的栈空间给出求N阶hanoi塔的函数定义如下：写出执行hanoi<3,a,b,c>时递归函数的实在参变量变化,以及move的搬运过程。已知关键字序列为：〔75,33,52,41,12,88,66,27,哈希表长为10,哈希函数为：H〔k=kMOD7,解决冲突用线性探测再散列法,要求构造哈希表,求出等概率下查找成功查找长度。已知一棵二叉树,中序序列DBCAFGE,后序序列DCBGFEA,构造该二叉树。给定权值{8,12,4,5,26,16,9},构造一个哈夫曼树,并计算其带权路径长度。编写程序：建立线形表,〔a1,a2,a3,...,an的单链表存储,并实现其就地逆置为〔an,an-1,...,a2,a1。编写程序：在中序线索树中,要找出X结点的前驱结点,请写出相关函数定义。编写算法：已知有N个结点的无向图,采用邻接表结构存储,要求对每个连通子图中一个生成树中的各条边逐层删除。编写算法：写出建立二叉树,二叉链表存储结构的算法。已知二叉树采用二叉链表方式存放