中国科学院计算技术研究所1999年硕士生入学试题数据结构与程序设计
一、选择题(20分每空2分)1.___的遍历仍需要栈的支持。
1.前序线索树2.中序线索树3.后序线索树 2.若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为___。
1.n-12.[n/m]-13.[(n-1)/(m-1)]4.[n/(m-1)]-15.[(n 1)/(m 1)]-1 3.最优二叉树(哈夫曼树)、最优查找树均为平均查找路径长度∑wh最小的树,其中对
最优二叉树,n表示___,对最优查找树,n表示___;构造这两种树均___。
1.结点数2.叶结点数3.非叶结点数4.度为二的结点数5.需要一张n各关键字的有序
表6.需要对n个关键字进行动态插入7.需要n个关键字的查找概率表8.不许要任何前提 4.对于前序遍历与中序遍历结果相同的二叉树为___;对于前序遍历与后序遍历结果相
同的二叉树为___。
1.一般二叉树2.只有根结点的二叉树3.根结点无左孩子的二叉树4.根接点无右孩子的
二叉树5.所有结点只有左子树的二叉树6所有结点只有右子树的二叉树 5.m路B 树是一棵___,其结点中关键字最多为___个,最少为___个。
1.m路平衡查找树2.m路平衡索引树3.m路trie树4.m路键树5.m-16.m7m 18.[m/2]-1
9.[m/2]10.[m/2] 1 二、填空题(10分,每空一分)
1.对于给定的n个元素,可以构造出的逻辑结构有___,___,___,___四种。 2.具有n个关键字的B-树的查找路径长度不会大于___。 3.克鲁斯卡尔算法的时间复杂度为___,他对___图较为适合。 4.深度为k(设根的层数为1)的完全二叉树至少有___个结点,至多有___个结点,k和结点
数n之间的关系是___。 三、问答题(10分,每题5分) 1.一棵非空的有向树中恰有一个顶点入度为0，其他顶点入度为1.但一个恰有一个顶点
的入度为0，其他顶点入度为一的有向图却不一定是一棵有向树。请举例说明之。 2.若有n个元素以构成一个小根堆，那么如果增加一个元素为K(n 1)，请用文字简要说
明你如何在log2(n)的时间内将其重新调整为一个堆？ 四、阅读下述程序,指出程序的输出。(10分) voidg(int**);
main(){
intline[100],i;
int*p=line;
for(i=0;i<100;i ){
*p=i;
g(&p);
}
for(i=0;i<100;I )printf("%d\n",line[i]);
}
voidg(int**p){
(**p) ;
(*p) ;
}
五、编程题。(共50分,要求写出设计思想和程序注解) 1.设一单向链表的头指针为head,链表的记录中包含着整数类型的key域,试设计算法,将
此链表的记录按照key递增的次序进行就地排序.(10分) 2.给定一个整数数组b[0..N-1],b中连续相等元素构成的子序列称为平台.试设计算法,求出
b中最长平台的长度.(20分) 3.自由树(即无环连通图)T=(V,E)的直径是树中所有点对间最短路径长度的最大值,即T的
直径定义为MAXd(u,v)这里d(u,v)表示顶点u到顶点v的最短路径长度(路径长度为路径中
所含的边数).试写一算法求T的直径,并分析算法的时间复杂度(时间复杂度越小得分越高)
(20分) 九、(14分)设正在处理器上执行的一个进程的页表如下.页表的虚页号和物理块号是十进
制数,起始页号(块号)均为0.所有的地址均是存储器字节地址,页的大小为1024字节. A.详述在设有快表的请求分页存储管理系统中,一个虚地址转换成物理内存地址的过程. B.下列虚地址对应与什么物理地址:(1)5499;(2)2221; 虚页号状态位访问位修改位物理块号
01104
11117
2000---
31002
4000---
51010 注释:访问位---当某页被访问时,其访问位被置为1.
页:
[1]