北师大数据结构考研历年真题总结.docx
《北师大数据结构考研历年真题总结.docx》由会员分享,可在线阅读,更多相关《北师大数据结构考研历年真题总结.docx(39页珍藏版)》请在沃文网上搜索。
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
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
20 积分
下载 | 加入VIP,下载更划算! |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 北师大 数据结构 考研 历年 总结