北师大教育技术数据结构考研历年真题总结Word格式文档下载.docx
《北师大教育技术数据结构考研历年真题总结Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《北师大教育技术数据结构考研历年真题总结Word格式文档下载.docx（58页珍藏版）》请在冰点文库上搜索。
D
0.04
5、若下方为某有向图的邻接矩阵：
A0567∞
B∞04∞3
C8∞05∞
D∞∞502
E9∞∞40
则有A至E的最短路径为_______，其长度为________；
而E至A的最短路径为________，长度为________。
4、读程序，写输出：
1、programtest41;
Proceduretry（x:
integer）;
Vary:
0...4
Beginy:
=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;
=HALF;
WHILE①、②DO
BEGIN
I:
=I+1;
①ONE<
ONE+F时输出为：
_________
=F*HALF
END;
WRITELN（‘I:
’,I:
3）②F<
0时输出为：
END.
（此题无需填具体值）
五、编写程序或子程序：
1、请编写程序读取文件DATA.TXT中的数据，存入数组。
该文件是由字处理程序准备好的，上面是多次对同一样本测得的值，数值数目小鱼200个。
再求这些值的均值和标准差
（），并剔除与均值距离超过3倍标准差的可疑数据复算均值，直到没有可剔除数据为止。
2、使用二叉链接树时，请编写Pascal函数，以使在调用时，指定某个树的根指针时，可求出该树内结点的总数。
6、top为栈顶指针，各元素皆为记录型，其中key字段类型为INFO;
next字段类型为LINK。
请改正进栈与退栈过程中的错误。
1999
1、请译为中文：
1、Breadth-firstsearch
2、Discreteeventsimulation
3、Enumeratedmethod
4、Functionaldesignator
5、Huffmancoding
6、Linerlinkedlists
7、Radixsorting
8、Recursiveroutine
9、Spanningtree
10、Undirectedgraph
2、填空：
1、使用关键路径方法安排施工计划时，通常图中各个顶点代表______________，边代表________________，边长表示____________。
这类图又称作_________________网。
2、B树是一种__________树，但在其所有叶子结点内都没有____________；
B﹢树是___________树，在其诸叶子结点中有____________，没有___________。
3、Pascal源程序在____________时能发现语法错，修改后应____________；
如果通过编译后再运行时出错则为错，这时应在编辑窗口中__________并__________与运行。
4、哈夫曼编码的目的是_______________________。
为此在已知各事件出现几率时，要用___________的码组表示几率最大的事件，且任一个码组都不能称为其它码组的________。
5、已经定义好了某数组类型，其下标类型为index=0..n{n为常量标识符}，a为该数组类型的变量，在a[1]到a[n]中有类型为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字节整数的范围。
2001
1、adjacencymatrix
2、binarysearch
3、completegraph
4、enumeratedscalar
5、heapsorting
6、linearlinkedlist
7、minimalspanningtree
8、optimalmergetree
9、patternmatching
10、postfixnotation
11、preordertraversal
12、refinementapproach
13、shortestpathfirst
14、threadedfile
2、简答题：
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为原始序列，请填出用直接插入法按升序排序时，每趟处理后的情况：
_______________________;
_______________________;
_______________________。
6、结合你对计算机运算器的理解完成本题填空，使程序运行时的输出正确无误。
5、请按要求编程序：
1、根据公式：
编写求e值到尽可能精确，并将结果输出的程序。
2、某系统选拨优秀毕业生，要求对近200名毕业班学生的成绩进行统计排序。
设已将课程分成公共基础课和专业课两类，每个学生分类计算的两个平均分也已经存入了名为‘LIST.TXT’的文件，该文件是用写字板编辑成的，文件内每行存入一个学生的信息，最左方是学号，随后先是公共基础课平均分，后是专业课平均分，最右方是学生姓名，各项之间有一个或多个空格。
学号是8位的数码字符串；
两个平均分皆为带两位小数的实数；
学生姓名为最多10位的字符串。
请编写程序，按公共基础课占4成，专业课占6成计算出综合成绩，并给出最终排好序的选拨名单。
排队的规则是先分两档，进入第1档的条件是两类课程平均分都不低于90分，然后在每档内按照综合成绩的高低排序。
排好序的结构嬴荡记入一个名为‘SORTED.TXT’文本文件，且将钱20名的情况送往屏幕。
文件及屏幕上数据的格式是：
名次姓名学号档次综合成绩公共课成绩专业课成绩
2003
1、请翻译成中文：
1、allocationstrategy
2、boundarytagmethod
3、mergeinsertionsort
4、patternmatching
5、threadedbinarytrees
6、adjacencymultilists
7、asymptotictimecomplexity
8、indexedsequentialsearch
9、implementinglinkedlistsusingarray
10、quadraticprobing
11、circularlinkedlist
12、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]=_____________;
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（____________）{
Visited[p->
adjvex]）
DFS（G,p->
adjvex）;
P=___________;
}
1、以下给出在链栈中实现插入操作的算法Push，其类型和算法说明如下（2处错误）：
typedefstructstacknode
{
DataTypedata;
structstacknode*next;
}StackNode;
typedefStacknODE*ListStack;
VoidPush（LinkStackls,DataTypex）
{//将元素x插入链栈头部
p=（StackNode*）malloc（sizeof（StackNode））;
p->
number=x;
next=ls;
ls=p->
data;
}
2、以环形顺序队列的存储方式实现队列的基本算法如下（3处错误）：
#include<
iostream.h>
#defineMaxLen20
typedefcharelemtype;
typedefstruct
elemtypedata[MaxLen];
intfront,rear;
}queue;
//front为队头指针，rear为队尾指针。
voidinit（queue*sq）//初始化队列
sq->
front=0;
rear=0;
intinqueue（queue*sq,elemtypex）//入队列
if（（sq->
rear+1）%MaxLen==sq->
front）//队列上溢出
return0;
else
rear=（sq->
rear+1）%MaxLen;
data（sq->
rear+1）=x;
return1;
intoutqueue（queue*sq,elemtype*x）//出队列
front）==sq->
rear）//队列下溢出
front=（sq->
front+1）%MaxLen;
*x=sq->
data[sq->
front+1];
intempty（queue*sq）//判断队列是否为空队
rear）==sq->
front）
intgethead（queue*sq,elemtype*x）//取队头
front）
//队列下溢出
front）%MaxLen];
}
5、请按要求编写程序：
1、已知函数M（x）定义如下：
（1）编写一个非递归函数计算给定x的M（x）值；
（2）编写一个递归函数计算给定x的M（x）值。
2、设计一种算法用于判定一棵给定的二叉树是否为完全二叉树。
3、设有文件“PERSONEL.TXT”存放职工的数据，该文件是用写字板编辑成的，其内容包括：
职工号、姓名、性别、年龄、职称、基本工资、津贴、奖金、扣款、实发工资等（假设没有重复的职工号）。
编写实现如下功能的函数：
（1）在PERSONEL.TXT文件末尾追加职工记录，其中基本工资、津贴、奖金、扣款由用户输入，而实发工资由计算机自动计算，即实发工资=基本工资+津贴+奖金-扣款；
（2）根据用户输入的职工号和对应的数据修改该职工的数据；
（3）根据用户输入的职工号删除该职工的数据；
（4）根据用户输入的工资数，显示实发工资数额大于该工资数的职工的所有信息，并送往屏幕，其显示格式为：
职工号姓名性别年龄职称基本工资津贴奖金扣款实发工资
2004
1、请翻译成中文:
1、randomnumbermethod
2、sparsematrix
3、replacementselectionsort
4、Huffmancodes
5、minimalspanningtree
6、threadedlinkedlists
7、IndexedSequentialAccessMethod
8、DynamicSearchTable
9、polymorphicdatetype
10、garbagecollection
11、foldingattheboundaries
12、orthogonallist
1、简述数据结构的四种基本关系并画出它们的关系图。
2、何谓队列的上溢现象和假溢现象？
解决它们有哪些方法？
3、回答下列问题：
（1）什么叫Huffman树？
（2）什么叫B树？
（3）什么是图的生成树？
（4）什么是最小-最大堆？
4、简述无向图和有向图有哪几种存储结构，并说明各种结构在图中的不同操作（图的遍历，有向图的拓扑排序等）中有什么样的优越性?
5、评价一个算法一般从哪些方面进行？
和算法执行时间相关的因素有哪些？
6、指出对象和类的区别，使用矩形类说明对象和类的区别。
3、判断题，错误的请说明理由。
1、栈的输入序列为123...n，输出序列为a1a2...an,若ai=n（1≤i<
n-1）,则ai>
ai+1>
an。
（）
2、无向图的邻接矩阵一定是对称矩阵，且有向图的邻接矩阵一定是非对称矩阵。
3、哈希表的查找效率主要取决于哈希建表时所选取的哈希函数和处理冲突的方法。
4、一个稀疏矩阵Am*n采用三元组形式表示。
若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。
4、填空：
1、表长为n的顺序表中，若在第i个数据元素（1≤i≤n+1）之前插入一个数据元素，需要向后移动________个数据元素；
删除第i个元素需要向前移动______个数据元素；
在等概率的情况下，插入一个数据元素平均需要移动_____个数据元素，删除一个数据元素平均需要移动_______个数据元素。
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网中，结点表示_________，边表示_________，从源点到汇点路径上各活动的时间总和最长的路径称为____________。
升级会员 