计算机#2010年计算机考研究生专业课答案

类目：三人行考研网>计算机>正文

时间：2017-08-3000:56:27

第一题：选择题答案：

1-5DCBCB

6-10AABAD

11-15ADCBD

16-20ADBAD

21-25ADACB

26-30AABBC

31-35CBCAA

36-40CBCAA

第二题：综合题答案

41 、

(1)因为装填因子为0.7，数据总数为7 ，所以存储空间长度为

L=7/0.7=10

因此可选T=10
，构造的散列函数为

H(key)=(key3)MOD10

线性探测再散列函数为：

Hi=(H(key)+di)MOD10,(di=1,2,3...9)

因此，各数据的下标为

H(7)=(73)MOD10=1

H(8)=(83)MOD10=4

H(30)=(303)MOD10=0

H(11)=(113)MOD10=3

H(18)=(183)MOD10=4

H1=(H(18)+1)MOD10=5

H(9)=(93)MOD10=7

H(14)=(143)MOD10=2

所构造的散列表如下：

0123456789

307********

(2)查找成功的平均查找长度为：

ASL1=(1+1+1+1+2+1+1)/7=8/7

查找不成功的平均查找长度为：

ASL2=(7+6+5+4+3+2+1+2+1+1)=3.2

42
、

(1)建立一个可以放下p个整数的辅助队列 ，将数组R中的前p个整数依次进入辅助队列，将R中后面的n-p个整数依次前移p个位置
，将辅助队列中的数据依次出队，依次放入R中第n-p个整数开始的位置。

(2)使用c语言描述算法如下：

voidShift(intpR,intn,intp)//pR是指向数组R的指针 ，n为存放的整数个数
，

//p为循环左移的个数

inttemp[p]//辅助数组，存放要移出的整数 。

inti=0

while(i

temp[i]=pR[i]

i++

i=0

while(i