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

一、填空题

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

h 为附加头结点指针

(_____)

_____；

【答案】(1)p!＝NULL //链表未到尾就一直进行 (2)q //将当前结点作为头结点后的第一元素结点插入

2． 文件由_____组成；记录由_____组成。

【答案】记录；数据项

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

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

4． 从用户的观点看，文件的逻辑结构通常可以区分为两类:一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件; 另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____， _____和_____。B+树适用于组织_____的索引结构，m 阶B+树毎个结点至多有_____个儿子，除根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____个关键码。

【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；m ;

；2；k

5． 在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。

【答案】满；空；n ；栈底；两栈顶指针相邻(即值之差的绝对值为1)

第 2 页，共 41 页

6． 当两个栈共享一存储区时，栈利用一维数组stack(1，，1) 表示，两栈顶指针为top[l]与top[2]，则当栈1空时，top[l]为_____，栈2空时，top[2]为_____，栈满时为_____。

【答案】0；n+1；top[l]+l＝top[2]

【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。

7． 顺序栈用存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。

【答案】if(top!＝n)data[++top]＝x ；

【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。

8． 在一个具有n 个单元的顺序栈中，假定以地址高端(即下标为n 的单元) 作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top ＝_____。

【答案】top ﹣1

【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，所以top ﹣1。

9． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____, 设计出相应的_____。

【答案】逻辑结构；物理结构；操作(运算) ；算法

10．下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。

a 中存放待排序的关键字

第 3 页，共 41 页

【答案】

【解析】快速排序(quick sort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

二、解答题

11．己知n 阶下三角矩阵A(即当i ＜j 时，有序分配方式时在B 中确定元素

) ，按照压缩存储的思想，可以将其主对角线以

下所有元素(包括主对角线上元素) 依次存放于一维数组B 中，请写出从第一列开始采用列序为主

的存放位置的公式。

第1列有n 个元素，第j 列有n ﹣j ＋1个

在第j 列上的位置是为i

在一维数组B 中的存储位置k 与i 和j 的关

12．对下面的关键字集{30，15，21，40，25，26，36，37}若查找表的装填因子为平均查找长度；(4)写出将哈希表中某个数据元素删除的算法。

【答案】(1)由于装填因子为希函数，哈希函数为

(2)哈希表如表所示:

表 哈希表

(3)计算查找失败时的平均查找长度，必须计算不在表中的关键字，

当其哈希地址为

时的查找次数。本例中m=10。故查找失败和查找成功时的平均查找长度分别为:

(4)算法如下:

从哈希表h[n]中删除元素k ，若删除成功返回1，否则返回0

哈希函数用_

无关键字

第 4 页，共 41 页

【答案】2阶下三角矩阵元素

﹣j ＋1。所以n 阶下三角矩阵A 按列存储，其元素系为:

元素，第1列到第j ﹣1列是梯形，元素数为(n＋(n﹣j ＋2)(j﹣1)/2，而

，采用线性

探测再哈希方法解决冲突，做:(1)设计哈希函数；(2)画出哈希表；(3)计算查找成功和查找失败的

，关键字有8个，所以表长为。

。用除留余数法设计哈

解释成空地址

被删元素换成最大机器数的负