一、填空题

1． 在哈希函数

中，P 值最好取_____。

【答案】小于等于表长的最大素数或不包含小于20的质因子的合数

【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。

2． 深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。

【答案】

3． 索引顺序文件既可以顺序存取，也可以_____存取。

【答案】随机

4． 高度为h 的堆中，最多有_____元素，最少有_____个元素。

【答案】

当最后一层只有

【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为一个元素时，此时堆的元素个数最少，元素个数为

5． 完善算法：求KMP 算法.next 数组。

END ； 【答案】

6． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。

【答案】(1)(2)

链表未到尾就一直进行

将当前结点作为头结点后的第一元素结点插入

7． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。

【答案】

【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉 树。故结点个数为

8． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长(也称 增量序列)依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。

【答案】3; (10，7，-9，0，47，23，1，8，98，36)

9． 二进制地址为011011110000，大小为

【答案】011011110100；011011100000

011011110000是块的起始地址，

【解析】大小分别为式如下：

当大小为4时，起始地址

为

10．在单链表中设置头结点的作用是_____。

【答案】方便运算

当大小为16时，起始地址为

：和

其伙伴块的起始地址计算公

和

块的伙伴地址分别为：_____

二、选择题

11．

某系统正在执行三个进程

例如下表所示。

和

各进程的计算(CPUCPUCPU )时间和

时间比

为提高系统资源利用率，合理的进程优先级设置应( ) A. B. C. D. 【答案】B

【解析】为了合理地设置进程优先级，应该将进程的CPU 利用时间和故答案选B 。

时间做综合考虑，

12．假定主存地址为32位，按字节编址，主存和Cache 之间采用直接映射方式，主存块大小为4个字，每字32位，采用回写(WriteBack )方式，则能存放4K 字数据的Cache 的总容量的位数至少是( )。

A.146k B.147K C.148K D.158K 【答案】B

【解析】Cache 和主存直接映射方式的规则为：主存储器分为若干区，每个区与缓存容量相同；每个区分为若干数据块，每个块和缓存块容量相同；主存中某块只能映象到Cache 的一个特定的块中。本题中，Cache 总共存放4K 字数据，块大小为4个字，因此cache 被分为4K/4 = 1K 个块，由10位表示。块内共16字节，所以由4位表示，于是标记位为32-10-14= 18位。所以，Cache 的每一行需要包含所存的数据4个字，每个字32位，18位标记位和一个有效位，因此总容=147K。 量为：

13．要连通具有n 个顶点的有向图，至少需要( )条边。

A.n-1 B.n C.n+1 D.2n

【答案】B

【解析】对于有向图来说，两个顶点之间的边是具有方向的。如果是构成连通的无向图，需要n-1条边，而对于有向图来说，只需要再加上第一个顶点和最后一个顶点加上一条边，让其构成环状的图即可，因此最少需要n 条边。

14．将森林F 转换为对应的二叉树T , F中叶结点的个数等于( )

A.T 中叶结点的个数 B.T 中度为1的结点个数 C.T 中左孩子指针为空的结点个数 D.T 中右孩子指针为空的结点个数 【答案】C

【解析】森林转化为对应的二叉树是‘孩子-兄弟’存储的，即左孩子指针指向当前节点的孩子节点，右孩 子指针指向当前节点的兄弟节点，所以在T 中左孩子指针为空则代表它在森林中并没有孩子即为叶结点。所以 选C

15．下列不是设计一个“好”的算法应考虑达到的目标是( )。

A. 可行的 B. 健壮的 C. 无二义性的