设散列表长m=14，散列函数Hash（x)=x mod 11。表中已有4个结点：addr（15)=4，addr（38)=5，addr（61)=6，addr（84)=7，其余地址为空。若用平方探测法处理冲突，插入元素49时，其地址是_____。A．8B．3C．5D．9

假定用散列函数H1=k mod 13计算散列地址，当发生冲突时，用散列函数 H2=k mod ll+l来计算下一个探测地址的地址增量。设散列表的地址空间为0～12，在地址2、3、8中，散列表相应的内容为80，85，34。下一个被插入的关键码是42，其插入的位置是【 】。

设线性表(59，53，46，48，37，31，25)采用散列(Hash)法进行存储和查找，散列函数为H(Key)=Key MOD 7(MOD表示整除取余运算)。若用链地址法解决冲突（即将相互冲突的元素存储在同一个单链表中）构造散列表，则散列表中与哈希地址 (38) 对应的单链表最长。

A.2

B.3

C.4

D.6

设有一个用线性探测法解决冲突得到的散列表，该表共有0～10个地址单元，其中地址单元2～8中的内容依次为13，25，80，16，17，6，14。散列函数为： H(k)=k mod 11 若要查找元素14，探测(比较)的次数是( )。

A．8

B．9

C．3

D．6

设有一个用线性探测法解决冲突得到的散列表：

散列函数为H(k)=k mod 11若查找元素15，则探测的次数(比较的次数)为（ ）。

A）7

B）9

C）3

D）6

假设某文件系统的文件索引表有i-addr[0]，i-addr[1] ，...， i-addr[7]共 8个地址项，每个地址项大小为 4 字节，其中 5 个地址项 （i-addr[0]~i-addr[4] )为直接地址索引，2个地址项 (i-addr[5]~i-addr[6])是一级间接地址索引，1个地址项 (i-addr[7] )是二级间接地址索引，磁盘索引块和磁盘数据块大小均为1KB。若要访问文件的逻辑块号分别为5和518，则系统应分别采用（ ）。

A.直接地址索引和一级间接地址索引B.直接地址索引和二级间接地址索引C.一级间接地址索引和二级间接地址索引D.二级间接地址索引和一级间接地址索引

试题五 (共15 分 )

阅读以下关于嵌入式C语言编程方面的问题，回答问题1至问题3，将答案填入答题纸的对应栏内。

【说明】

嵌入式C语言编程中常涉及位运算、宏定义的问题，以及大端方式（Big-endian）、小端方式（Little-endian）的访问问题。

【 问题1 】（4 ）

嵌入式系统中常要求用户对变量或寄存器进行位操作。下面的两个函数分别为设置和清除变量 a 的第 5位。请使用下面的宏定义 BIT5 按要求对变量 a 进行相应的处理。在函数set_bit5中，用位或赋值操作（|=）设置变量a的第5位，在函数clear_bit5中，用位与赋值操作（&=）清除变量a的第5位。

define BIT5 (0x01<<5)

static int a;

void set_bit5(void)

{

① ; /* 设置变量a的第5位 */

}

void clear_bit5(void)

{

② ; /* 清除变量a的第5位 */

}

【 问题2】（5 分 ）

图5-1所示代码的设计意图是计算1～100各数的平方。 该段代码运行后，没有得到应有的结果，请说明出错原因，将答案填入答题纸的对应栏内。

”

【问题3】（6分）

某嵌入式处理器工作在大端方式 （Big-endian）下， 其中unsigned int为32位， unsigned short为16位，unsigned char为8位。仔细阅读并分析下面的C 语言代码，写出其打印输出的结果，将答案填入答题纸的对应栏内。

include "stdio.h"

include "stdlib.h"

void *MEM_ADDR;

void mem_test(void)

{

unsigned int *pint_addr = NULL;

unsigned short *pshort_addr = NULL;

unsigned char *pchar_addr = NULL;

MEM_ADDR = (void *)malloc(sizeof(int));

pint_addr = (unsigned int *)MEM_ADDR;

pshort_addr = (unsigned short *)MEM_ADDR;

pchar_addr = (unsigned char *)MEM_ADDR;

*pint_addr = 0x12345678;

printf("0x%x, 0x%x\n", *pshort_addr, *pchar_addr);

/* 第一次输出 */

pshort_addr++;

*pshort_addr = 0x5555;

printf("0x%x, 0x%x\n", *pint_addr, *pchar_addr);

/* 第二次输出 */

pchar_addr++;

*pchar_addr = 0xAA;

printf("0x%x, 0x%x\n", *pint_addr, *pshort_addr);

/* 第三次输出 */

}

●设线性表(59，53，46，48，37，31，25)采用散列(Hash)法进行存储和查找，散列函数为H(Key)=Key

MOD 7(MOD表示整除取余运算)。若用链地址法解决冲突（即将相互冲突的元素存储在同一个单链

表中）构造散列表，则散列表中与哈希地址 (37) 对应的单链表最长。

(37)

A．2

B．3

C．4

D．6

设散列表的地址空间为0到12，散列函数为h(k)=k mod 13，用线性探查法解决碰撞。现从空的散列表开始，依次插入关键码值14，95，24，61，27，82，69，则最后一个关键码69的地址为【 】。

设散列表的存储空间大小为19，所用散列函数为h(key)=key mod 19，用开放地址线性探查法解决碰撞。散列表的当前状态如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 190 194 768 559 582 93 208 现要将关键码值75插入到该散列表中，其地址应为______。

A．1

B．11

C．5

D．15

设哈希表长m=14，哈希函数H(key)=key%ll，表中已经有4个结点： addr(13)=4； addr(28)=5 addr(51)=6； addr(77)=7 如果用线性探测再与散列法处理冲突，关键字为49的结点地址为( )。

A．8

B．5

C．9

D．3

设散列表长m=14,散列函数H（K）=K％11，已知表中已有4个结点：r(15)=4;r(38)=5;r(61)=6;r(84)=7，其他地址为空，如用二次探测再散列处理冲突，关键字为49的结点地址是_____。

A.8

B.3

C.5

D.9

对于关键码序列（54，34，5，14，50，36，47，83），用链地址法（或拉链法）解决冲突构造散列表（即将冲突的元素存储在同一个单链表中，单链表的头指针存入散列地址对应的单元），设散列函数为H（Key）=Key MOD 7（MOD表示整除取余运算），则构造散列表时冲突次数最多的哈希单元的地址是（ ）。

A.0 B.1 C.5 D.6

假定用散列函数H1=k mod 13计算散列地址，当发生冲突时，用散列函数 H2=k mod 11+1来计算下一个探测地址的地址增量。设散列表的地址空间为0～12，在地址2、3、8中，散列表相应的内容为80，85，34。下一个被插入的关键码是42，其插入的位置是【 】。

设散列函数为H(k)=k mod7，一组关键码为23,14,9,6,30,12和18，散列表T的地址空间为0.6，用线性探测法解决冲突，依次将这组关键码插入T中，得到的散列表为( )

A．

B．

C．

D．