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

1、1998年一、 请译出以下专业术语： 1、balanced merging 2、critical paths 3、directed graph 4、field identifier 5、hashing function 6、linear linked lists 7、postorder traversal 8、recursive procedure 9、spanning tree 10、top-down approach二、 简答： 1、递归算法有何特点？定义递归子程序时应注意什么？ 2、设计一个好的算法，应具有哪几个基本特性？ 3、32阶的B+树，作为有100万个数据项的索引时，树高为多少？

2、若改用256阶的B+树，最小树高为多少？ 4、简述抽象数据类型队列的定义。 5、面向对象的程序设计，有何优点？三、 填空： 1、在Pascal程序中，标识符要先_后_，各标识符的作用域始于_,止于_。 2、在Pascal程序块中说明的指针变量如p:real;中的p是_态的变量，它在该程序块被激活时占有特定存区；而p是_型的_态变量，在_时才_相应的存区。 3、使用关键路径方法安排施工计划，图中各顶点代表_，各个边代表_，边长表示_，这类图又称作_网。 4、哈夫曼编码是在已知诸事件出现几率相差_时，用来_描述事件序列的代码数的方法，请填表并求平均描述一个事件要用的比特数_。事件出现几率编码A0.

3、8B0.1C0.06D0.04 5、若下方为某有向图的邻接矩阵：A 0 5 6 7 B 0 4 3C 8 0 5 D 5 0 2E 9 4 0则有A至E的最短路径为_，其长度为_；而E至A的最短路径为_，长度为_。四、 读程序，写输出：1、 program test41; Procedure try(x:integer); Var y:0.4 Begin y:=x mod s; x:=x div s; If x0 then try(x); write (y) End;Begin try(3179) end. 输出为：_2、若计算机做加法时，把比运算器最低位之后的数据舍掉；Program tes

4、t42; CONST M=255 ; ONE=1; HALF=0.5 ; TYPE R=0.5; VAR I : R ; F:=HALF ; BEGIN I:=1 ; F:=HALF;WHILE 、 DO BEGIN I:=I+1; ONE ONE+F时输出为：_ F:=F * HALF END;WRITELN(I: ,I : 3) F 0时输出为：_END.(此题无需填具体值)五、编写程序或子程序： 1、请编写程序读取文件DATA.TXT中的数据，存入数组。该文件是由字处理程序准备好的，上面是多次对同一样本测得的值，数值数目小鱼200个。再求这些值的均值和标准差 （ ），并剔除与均值距离超过

5、3倍标准差的可疑数据复算均值，直到没有可剔除数据为止。 2、使用二叉链接树时，请编写Pascal函数，以使在调用时，指定某个树的根指针时，可求出该树内结点的总数。六、 top为栈顶指针，各元素皆为记录型，其中key字段类型为INFO; next字段类型为LINK。请改正进栈与退栈过程中的错误1999一、 请译为中文： 1、Breadth-first search 2、Discrete event simulation 3、Enumerated method 4、Functional designator 5、Huffman coding 6、Liner linked lists 7、Radix

6、 sorting 8、Recursive routine 9、Spanning tree 10、Undirected graph二、 填空： 1、使用关键路径方法安排施工计划时，通常图中各个顶点代表_，边代表_，边长表示_。这类图又称作_网。 2、B树是一种_树，但在其所有叶子结点内都没有_；B树是_树，在其诸叶子结点中有_，没有_。 3、Pascal源程序在_时能发现语法错，修改后应_；如果通过编译后再运行时出错则为错，这时应在编辑窗口中_并_与运行。 4、哈夫曼编码的目的是_。为此在已知各事件出现几率时，要用_的码组表示几率最大的事件，且任一个码组都不能称为其它码组的_。 5、已经定义好了

7、某数组类型，其下标类型为index=0.nn 为常量标识符，a为该数组类型的变量，在a1到an 中有类型为item 的排序之值。三、 简答题： 1、试举例说明用程序设计语言描述堆栈结构时，要涉及哪些问题？ 2、在程序设计语言中实现递归的条件是什么？编写递归子程序，应注意什么？ 3、动态查找树，有哪几项基本操作？ 4、举例说明有向图的最短路径算法常用于哪几种情形？四、 改错： 2、在数组已排好序的前提下，TEST42 函数用来查找其内值为key的元素：若未找到，函数值为0，否则函数值为该元素的下标值。五、 按要求编写程序或子程序： 请编写函数子程序以计数指定了指针的某个二叉树内结点的总数。2、

8、已知：若n为自然数，先后调用RANDOM(n) 将产生在0 到n -1 之间取值的伪随机序列。请编写程序给小学生做四则运算的练习，且要求如下： （1）每组25道题，每题列出题号、模式及等号，请小学生输入答案； （2）若答案正确，该题得4分，加到总分中去，再给出下一题的题目；若第一次的答案不正确，则应指出来，随后重显示原题，请学生答第二次，这次若能答对，仍记2分，并立即显示下题；在第二次仍算错后，先指出答案错了，再显示正确的式子； （3）加、减、乘、除运算的顺序亦由一种随机数来控制，使各种不同运算无规则地交错进行； （4）每组中加、减、乘、除和平方（以两相同数相乘表示）各占5题； （5）每组题做

9、完要显示学生做该组题的成绩； （6）在此组题目中要求被减数大于减数，要求除法恰好除尽； （7）运算数的位数应当不使运算超出2字节整数的范围。2001一、 请译为中文： 1、adjacency matrix 2、binary search 3、complete graph 4、enumerated scalar 5、heap sorting 6、linear linked list 7、minimal spanning tree 8、optimal merge tree 9、pattern matching 10、postfix notation 11、preorder traversal 12

10、、refinement approach 13、shortest path first 14、threaded file二、 简答题： 1、试说明描述数据结构时，必须涉及哪些方面？ 2、好的应用程序应当具有哪些共同特点？ 3、编写与使用递归子程序应注意什么？ 4、阶为32的B树，构成有10万个数据项的索引时，最大搜索长度是多少？若改用阶为128的B树，这一长度变为多少？ 5、说明对字符串的基本操作是什么？ 6、给出子图的形式定义？并回答连通图的极小连通图是什么？三、 填空：1、在面向对象的程序设计中，对象是包含_和_的逻辑实体，实体内专有的这两部分被封装在一起，较好地解决了_、_及模块化这3个

11、软件的基本问题。2、PASCAL程序中直接说明的指针型变量p是_态变量，在执行_(p)过程语句后，p成为新的_态变量，被称作_的变量。3、采用哈夫曼编码的目的是_，为此出现频度最大的事件要用_的码组来表示，且任一码组都不应成为其他码组的_；若第k个事件出现的几率为PR，并满足以下等式PK=1 ,且Pn Pn+1 ,(0 k 1)的递归出口是_，递归体是_。将递归算法转换成对应的非递归算法时，通常需要使用_。 3、广义表（a,b,(c,d),e,(i,j),k)）的长度是_，深度是_；广义表运算式HEAD(TAIL(x,y,z),(a,b,c)的结果为_。 4、以数据集（4,5,6,7,10,1

12、2,18）为结点权值所构造的哈夫曼树为_，其带权路径长度为_。 5、已知序列18,19,62,45,9,37,78,69,88，采用快速排序法对该序列作升序排列时每一趟的结果为: 初 始：_ 第一趟：_ 第二趟：_ 第三趟：_ 第四趟：_ 第五趟：_ 第六趟：_ 第七趟：_ 第八趟：_ 6、对于长度为n的线性表，顺序查找法的平均查找长度为_，其时间复杂度为_;二分查找法的平均查找长度为_，其时间复杂度为_;若采用分块查找（假定总块数和每块长度均接近），其时间复杂度为_。 7、在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有_、_、_、_，平均比较次数最少

13、的排序是_，需要内存容量最多的排序是_。 8、下面算法是实现对以邻接表存储的图进行深度优先遍历递归算法，请空白处填上适当的内容。 Typedef enum FALSE,TRUE Boolean; Boolean visitedMax VertexNum; Void DFSTraverse(ALGraph *G) int i; for(i=0;in;i+) visitedi=_; for(i=0;in;i+) if(!Visitedi) _; void DFS(ALGraph *G,int i) EdgeNode *p; printf(“visit vertex:%c”,G-adglisti,v

14、ertex); visitedi=TRUE; p=G-adglisti.firstedge; While(_) if(!Visitedp-adjvex) DFS(G,p-adjvex); P=_; 四、 改错：1、 以下给出在链栈中实现插入操作的算法Push，其类型和算法说明如下（2处错误）： typedef struct stacknode DataType data; struct stacknode *next; StackNode; typedef StacknODE *ListStack; Void Push(LinkStack ls,DataType x) /将元素x插入链栈头部

15、p=(StackNode *)malloc(sizeof(StackNode); p-number=x; p-next=ls; ls=p-data; 2、 以环形顺序队列的存储方式实现队列的基本算法如下（3处错误）： #include #define MaxLen 20 typedef char elemtype; typedef struct elemtype dataMaxLen; int front,rear;queue; /front为队头指针，rear为队尾指针。void init(queue *sq) /初始化队列 sq-front=0; sq-rear=0;int inqueue

16、(queue *sq,elemtype x) /入队列 if(sq-rear+1)%MaxLen=sq-front) /队列上溢出 return 0; else sq-rear=(sq-rear+1)%MaxLen; sq-data(sq-rear+1)=x; return 1; int outqueue(queue *sq,elemtype *x) /出队列 if(sq-front)=sq-rear) /队列下溢出 return 0; else sq-front=(sq-front+1)%MaxLen; *x=sq-datasq-front+1; return 1; int empty(qu

17、eue *sq) /判断队列是否为空队 if(sq-rear)=sq-front) return 1; else return 0;int gethead(queue *sq,elemtype *x) /取队头 if(sq-rear)=sq-front) return 0; /队列下溢出 else *x=sq-datasq-front)%MaxLen; return 1; 五、 请按要求编写程序：1、 已知函数M(x)定义如下：（1） 编写一个非递归函数计算给定x的M(x)值；（2） 编写一个递归函数计算给定x的M(x)值。2、 设计一种算法用于判定一棵给定的二叉树是否为完全二叉树。3、 设有

18、文件“PERSONEL.TXT”存放职工的数据，该文件是用写字板编辑成的，其内容包括：职工号、姓名、性别、年龄、职称、基本工资、津贴、奖金、扣款、实发工资等（假设没有重复的职工号）。编写实现如下功能的函数：（1） 在PERSONEL.TXT文件末尾追加职工记录，其中基本工资、津贴、奖金、扣款由用户输入，而实发工资由计算机自动计算，即实发工资=基本工资+津贴+奖金-扣款；（2） 根据用户输入的职工号和对应的数据修改该职工的数据；（3） 根据用户输入的职工号删除该职工的数据；（4） 根据用户输入的工资数，显示实发工资数额大于该工资数的职工的所有信息，并送往屏幕，其显示格式为：职工号 姓名 性别 年

19、龄 职称 基本工资 津贴 奖金 扣款 实发工资2004一、 请翻译成中文: 1、random number method 2、sparse matrix 3、replacement selection sort 4、Huffman codes 5、minimal spanning tree 6、threaded linked lists 7、Indexed Sequential Access Method 8、Dynamic Search Table 9、polymorphic date type 10、garbage collection 11、folding at the boundari

20、es 12、orthogonal list二、 简答题： 1、简述数据结构的四种基本关系并画出它们的关系图。 2、何谓队列的上溢现象和假溢现象？解决它们有哪些方法？ 3、回答下列问题： （1）什么叫Huffman树？ （2）什么叫B树？ （3）什么是图的生成树？ （4）什么是最小-最大堆？ 4、简述无向图和有向图有哪几种存储结构，并说明各种结构在图中的不同操作（图的遍历，有向图的拓扑排序等）中有什么样的优越性? 5、评价一个算法一般从哪些方面进行？和算法执行时间相关的因素有哪些？ 6、指出对象和类的区别，使用矩形类说明对象和类的区别。三、 判断题，错误的请说明理由。 1、栈的输入序列为123.

21、n，输出序列为a1a2.an,若ai=n(1iai+1an。 （ ） 2、无向图的邻接矩阵一定是对称矩阵，且有向图的邻接矩阵一定是非对称矩阵。 （ ） 3、哈希表的查找效率主要取决于哈希建表时所选取的哈希函数和处理冲突的方法。 （ ） 4、一个稀疏矩阵Am*n采用三元组形式表示。若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。 （ ）四、 填空： 1、表长为n的顺序表中，若在第i个数据元素（1in+1）之前插入一个数据元素，需要向后移动_个数据元素；删除第i个元素需要向前移动_个数据元素；在等概率的情况下，插入一个数据元素平均需要移动_个数据元素，删除

22、一个数据元素平均需要移动_个数据元素。 2、用某种排序方法对线性表24,88,21,48,15,27,69,35,20，进行排序时，元素序列的变化情况如下：（1）24,88,21,48,15,27,69,35,20（2）20,15.21.24.48.27.69.35.88（3）15,20,21,24,35,27,48,69,88（4）15,20,21,24,27,35,48,69,88则所采用的排序方法是_。A、 快速排序 B、选择排序 C、希尔排序 D、归并排序 3、在AOE网中，结点表示_，边表示_，从源点到汇点路径上各活动的时间总和最长的路径称为_。 4、在堆排序、快速排序和归并排序中，

23、若从节省存储空间考虑，则应首先选取_方法，其次选取_方法，最后选取_方法；若只从排序结果的稳定性考虑，则应选择_方法；若只从平均情况下排序的速度来考虑，则应选取_方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取_方法。 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、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（不设头指针），类型定义和出对与入队算法如

24、下。（2处错误）： 2、以顺序栈的存储方式实现栈的基本运算，其算法如下（4处错误）：五、 应用题：1、已知一个长度为12的表 Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec，（1）试按表中元素的顺序依次插入一棵初始为空的二叉排序树（字符之间以字典顺序比较大小），请画出对应的二叉排序树，并求出在等概率情况下对此有序表进行折半检索时检索成功的平均检索长度。（2） 若对表中元素先进行排序构成有序表，试求在等概率情况下对此有序表进行折半检索时检索成功的平均检索长度。（3） 按表中元素顺序构造一棵平衡二叉排序树，试求在等概率的情况下检索成功的平均检索长

25、度。2、 已知一棵二叉树的中序遍历序列和按层次遍历的序列，试编写算法生成此二叉树的二叉链表。3、已知递归函数F(m)(其中DIV为整除)：（1） 写出求F（m）递归算法；（2） 写出求F（m）的非递归算法。2005一、 请翻译成中文： 1、Virtual Storage Access Method 2、directed acycline graph 3、balanced binary tree 4、have variable size records 5、recursive function 6、weighted path length 7、Least Signification Digit

26、first 8、Fibonacci search 9、immediate successor 10、fixed-aggregate data type 11、random probing 12、diminishing increment sort二、 简答题： 1、简述数据的四种存储方式及各自特点。 2、线性表的基本运算包括哪些？简述线性表的链式存储结构的几种形式。 3、名词术语解释： （1）平均查找长度（AVL） （2）抽象数据类型 （3）广义表 （4）强连通图与强连通分量 4、什么叫AOE网中的源点、汇点和关键路径，一个正常的AOE网中只有一个源点、汇点和一条关键路径吗？ 5、描述头指针、

27、头结点和首元结点三个概念的区别。 6、试比较顺序文件、索引顺序文件和散列文件的存储代价、检索、插入及删除记录时的优点和缺点。三、 判断题，错误的请说明理由。 1、子串定位函数的时间复杂度在最坏情况下为O(nm)，因此子串定位函数没有实际使用的价值。 （ ） 2、一般来说，若深度为k的n个结点的二叉树只有最小路径长度，那么从根结点到第k-1层具有最多的结点数为2k-1-1，余下的n-2k-1+1个结点在第k层的任一位置上。 （ ） 3、用邻接矩阵存储一个图时，所占用的存储空间大小只与图中结点的个数有关，而与图的边数无关。 （ ） 4、对于满足折半查找和分块查找条件的文件而言，无论它存放在任何介质

28、上，均能进行顺序查找，折半查找和分块查找。 （ ）四、 填空： 1、一维数组的逻辑结构是_，存储结构是_；对二维或多维数组，分为按_和_两种不同的存储方式。 2、具有n个结点的完全二叉树若层次从上到下、从左到右对其编号（根结点为1），则编号最大的分支结点序号是_。编号最小的分支结点序号是_，编号最大的叶子结点序号是_，编号最小的叶子结点是_。 3、遍历图的过程实质上是_。设图G有n个顶点和e条边，则对用邻接矩阵表示的图进行深度或广度优先搜索遍历时的时间复杂度为_，而对用邻接表表示的图进行深度或广度优先搜索遍历时的时间复杂度为_；图的深度或广度优先搜索遍历时的空间复杂度均为_。 4、构造哈希（H

29、ash）函数的方法有_、_、_等。 5、参照下面的树，回答各个问题： （1）如果插入结点33，它的父结点是_； （2）如果插入结点64，它的父结点是_； （3）如果删除结点30后，根据算法将选取_结点来替换； （4）如果删除结点90后，根据算法将选取_结点来替换； （5）如果删除了根结点50，则应该用_结点来替换。五、 改错： 1、以下算法使用少一个元素空间的方法来区别循环队列的队空和队满条件，借以描述出队、入队的基本操作（2处错误）： 2、以下算法通过单链表实现了接收用户输入的一个字符串，统计其中出现过的所有字符，并按其出现的频率从高到低的顺序排列输出。（4处错误）六、 应用题：1、 给出一

30、组关键字30,19,26,48,59,11,53,10，分别写出按下列各种排序方法进行排序时的变化过程： （1）归并排序，每归并一次书写一个次序。 （2）快速排序，每划分一次书写一个次序。 （3）堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。2、 已知Ackermann函数的定义如下： （1）写出Ack(2,1)的计算过程； （2）写出计算Ack(m,n)的非递归算法。3、 已知深度为n的二叉树采用顺序存储结构存放数组B1.2n-1中，请编写一个非递归算法产生该二叉树的二叉链表结构。设二叉链表节点的结构为：指向左右孩子的指针lchild , rchild 及数据域data，根

31、节点的指针为t。2006二、 简答题：1、 列举数据逻辑结构上定义的基本运算，简述度量算法效率的方法及各自特点。2、 根据结构中数据元素之间存在的关系，比较树形结构与线性结构的异同。3、 名词术语解释： （1）循环队列 （2）十字链表 （3）线索二叉树 （4）索引顺序文件4、 说明在图的遍历中，设置访问标志数组的作用。并说明采用图的深度优先搜索模式能否完成拓扑排序的基本思路。5、 简述哈希表的设计过程以及哈希函数的构造原则，并列举常用的构造哈希函数的方法。6、 什么是串的存储密度？如果串采用块链结构存储，试分析： （1）一个节点只存储一个字符与一个节点存储4个字符两种情况下串的存储密度（字链指

32、针占用4个字节，一个字符占用1个字节）； （2）上述两种情况下，哪种存储结构的空间利用率高。三、 判断题，错误的说明理由。1、 图G的一棵最小生成树的代价未必小于G的其他任何一棵生成树的代价。（ ）2、 二维数组A的每个元素是由6个字符组成的串，其行下标i=0、1、.、8,列下标j=1、2、.、10，若A按行先存储，元素A8,5的起始地址与当A按列先存储时的元素A5,10的起始地址相同（设每个字符占一个字节）。 （ ）3、 用邻接矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查Am的第i行和第j列的元素是否为0即可。 （ ）4、 已知待排序的n个元素可以分为n/k组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为O(nlogk)。