当前位置：问答库＞考研试题

08年北京大学真题

计算机软件基础

一。填空题 共15分。

1.散列表。散列函数home=key%13.散列表有13项，冲突解决方法双散列，

probe函数为p(key,i)=(key%13+i*key%11)%13. 依次将以下几个关键码插入散列表 ，。。。。（记不住了）画出散列表插入后的状态，并计算等概率查找这几个关键

码时的ASL。

2.一系统存储管理采用虚拟页式存储管理方案，一程序共有10个内存块，拥有6个缓冲 区，一个缓冲区可缓存一块，缓冲区淘汰算法为LRU，缓冲区采用链接结构，尾缓冲 区的指针可以重用，假定此程序内存块调用顺序依次为。。。。（记不住了），则 最后缓冲区链上留下的页块依次为什么，在此过程中对缓冲区共写入多少次。

3.5阶4层B 树，最多可以索引多少个关键码，最少呢？

二。辨析 20分。

1.红黑树是具有下面一些性质的数据结构：

(列出红黑树的五个性质）

请回答以下问题：

（1）颜色有什么作用？

（2）n个内部结点的红黑树，请估算高度最大为多少，并给出证明。

2.按字典序依次插入以下关键词

RAT OX TIGER RABBIT DRAGON SNAKE HORSE GOAT MONKEY ROOSTER DOG

PIG

组成AVL 树。

（1）画出这颗AVL 树。

（2）不考虑AVL 树对高度的平衡，将此树看作半伸展树，画出查找一次PIG 后此半伸

展树的形态。

三。程序改错（10分）

1.以下程序的功能是把一个输入字符串倒序输出，请找出并改正其中的错误。

void reverse(char *s)

{ int len=strlen(s);

char *dest=new char[len];

int i=0;

while(len--!=0)

{