中科院计算所历年考研试题
中科院计算所1999 i[e+C td4
一. 选择题. E&J$fJbW
1.____的遍历仍需要栈的支持. gL&O4 g
(1) 前续线索树(2)中序线索树 (3)后序线索树 S~2J>;.
2.若度为m的哈夫曼树中，其叶结点个数为n,则非叶结点的个数为＿＿＿． [;8BYAH
（１）n-1 (2)|_n/m_|-1 (3)上取整 (n-1)/(m-1)4)[上取整n/(m-1)]-1 (5)[上取整(n+1)/(m+1 )]-1 ?r?4 FDc"L
3.最优二叉树（哈夫曼树），最优查找树均为平均查找路径长度 wihi最小的树,其中对最优二叉树,n表示___,对最优查找树,n表示 ____;构造这两种树均为——。*（1）结点数（2）叶结点数 （3）非叶结点数 （4）度为2的结点数 （5）需要一张N个关键字的有序表 （6）需要对N个关键字进行动态插入（7）需要N个关键字的查找概率表（8）不需要任何前提。 (ar>Zm
4.对于前序遍历与中序遍历结果相同的二叉树为_____;对于前遍历和后序遍历 结果相同的二叉为_____. !87iie5d
(1) 一般二叉树 (2) 只有根结点的二叉树 (3)根结点无左孩子的二叉树 (4)根结点无右孩子的二叉树 (5)所有结点只有左子数的二叉树 (6)所有结点只有右子树的二叉树. C`k$SA<M]
5.M路B+树是一棵_____,其结点中关键字最多为___个,最少为___个.. Gl$6@ 9s
(1) M路平衡查找树 (2)M路平衡索引树 (3) M路TRIE 树 (4)M路键树(5)M-1 bdW&gc>
(6)M (7)M+1 (8)上取整(M/2)-1 (9) 上取整(M/2) (10) 上取整(M/2)+1 S_h } xU
二. 填空题 }A!]X:sZ
1. 对于给定的N个元素,可以构造出的逻辑结构有___._____. _____.. ____四种. 6] _}
2. 具有N个关键字的B-树的查找路径长度不会大于________., fm<C~ $ (
3. 克鲁司卡尔算法的时间复杂度为_____,它对_____图较为适合. 3_fM ,:8"
4. 深度为可（设根的层数为一）的完全二叉树至少有______个结点,至多有_____个结点,K和结点数N之间的关系是_____. XR'0Yh/qqm
三. 问答题 o=go}WqXR
1.一棵非空的有向数中恰有一个顶点入度为0, 其他顶点入度为一, 但一个恰有一个顶点入度为0, 其他顶点入度为一的有向图却不一定是一棵有向数,请举例说明. avw(S OB
2.若有N个元素已构成一个小根堆, 那么如果增加一个元素为Kn+1,请用文字简要说明你如何在LG(N)/LG(2) 的时间内将其重新调整为一个堆? [6_?* Y
四. 指出程序输出 >;5L4{J
void g(int**); f%3i/wd$C
main() { f:)NJMD
int line[100],i; D.@~Nr)$
int *p=line; I<Jh5
for (i=0; i<100;i++) { !Z EL1u
*p=i; si ['A T
g(&p); N6 s\@-0
} >IC2FUa
for(i=0; i<100;i+1) printf(“%d/n”,line); EMw9@j,15
} yK9-ui%SK
void g(int**p) { b5&)bW7EY
(**p)++; kN=r[nn #
(**p)++; 7`%|lP"3:
} y&"e j(]o
五 .编程题 `8$Y2Rp-
1. 设一单向链表的 头指针为HEAD,链表的记录中包含着整数类型的KEY 域,试设计算法,将此链表的记录按照KEY递增的次序进行就地排序. 4+\eltiZ
2. 给定一个整数叔数组b[0..n-1].,b中连续的相等元素构成的子序列称为平台.试设计算法,求出B中最长平台的长度.[ u{U*aL;?
3. 自由树(即无环连通图)T=(V,E)的直径是树中所有点对间最短路径长度的最大值,即T的 直径定义为MAX D(u,v) ,这里D(u,v)表示顶点U到顶点V的最短 [/upQKRW
u,v∈V ]* ;C(D
路径长度(路径长度为路径中所包含的边数). 写一算法求T的直径,并分析算法的时间复杂度(时间复杂度越小得分越高). |
收藏
点赞!
反对!