2018年武汉纺织大学数学与计算机学院848数据结构考研基础五套测试题
● 摘要
一、填空题
1． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。 【答案】
的次数最小。总次数为
2． 设数组 。 数组中任一元素A[i，j]均占内存48个二进制位，从首地址2000开【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测始连续存放在主内存里，主内存字长为16位，那么
(1)存放该数组至少需要的单元数是_____；
(2)存放数组的第8列的所有元素至少需要的单元数_____；
(3)数组按列存储时，元素A[5，8]的起始地址是_____。
【答案】270；27；2204
【解析】数组的元素个数为9*10＝90，因为每个元素占内存48个二进制位，即6个字节。故总需要90*6＝540个字节，因为主内存字长为16位，即2个字节，所以至少需要540/2＝270个单元数。第8列有9个元素，共占9*6＝54个字节，因此至少需要54/2＝27个单元数。由题知，每个元素占3个单元。按列存储时，A[5，8]的起始地址为2000＋[(8﹣1)*9＋(5﹣0)]*3＝2204。
3． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
4． 从用户的观点看，文件的逻辑结构通常可以区分为两类:一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件; 另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____， _____和_____。B+树适用于组织_____的索引结构，m 阶B+树毎个结点至多有_____个儿子，除根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____个关键码。
【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；m ;
；2；k
5． 设数组
址为_____。
【答案】9174；8788 的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45，68]的存储地址为_____；若以列序为主序顺序存储，则元素a[45，68]的存储地
【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，则它的存储地址为2000＋((i﹣l)*80＋j ﹣
1) 2。若以列序为主存储顺序，则它的存储地址为2000＋((j﹣l)*50＋i ﹣l)*2。
6． 文件可按其记录的类型不同而分成两类，即 _____和_____文件。
【答案】操作系统文件；数据库
7．
线性表
【答案】(n﹣1)/2
【解析】删除第一个元素需要移动n ﹣1次，以此类推，删除最后一个元素需要移动0次。平均次数为(n﹣l)*n/n/2＝(n﹣l)/2。
8． 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。 【答案】
【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺序查找效率一样为。
9． 设有两个算法在同一机器上运行，其执行时闻分别为100n 2和2n ，要使前者快于后者，n 至少为_____。
【答案】15
2n 【解析】当时，100n2>2n，而，时，100n ＜2
10． 设有一个10阶对称矩阵A 采用压缩存储方式(以行为主序存储:a 11＝l) ，则a 85的地址为_____。用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____。
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若i ＞＝j ，则
＝i(i﹣l)/2＋j 。若i ＜j 。则
的地址为l ＋2＋... ＋i ﹣l ＋j 的地址为j(j﹣l)/2＋i 。将i ＝8，j ＝5代入得33。
二、解答题
11．某文件系统空间的最大容量为, 以磁盘块为基本分配单位, 磁盘块大小为1KB 。文件控制块(FCB)包含一个512B 的索引表区。请回答下列问题。
(1)假设索引表区仅采用直接索引结构, 索引表区存放文件占用的磁盘块号。索引表项中块号最少占多少字节? 可支持的单个文件最大长度是多少字节？
(2)假设索引表区采用如下结构:第0〜7字节采用<起始块号, 块数>格式表示文件创建时预分配的连续存储空间, 其中起始块号占6B , 块数占2B ; 剩余504字节采用直接索引结构, 一个索引项占6B , 则可支持的单个文件最大长度是多少字节? 为了使单个文件的长度达到最大, 请指出起始块号和块数分别所占字节数的合理值并说明理由。
【答案】(1)文件系统存储空间共有块数
为表示个块号, 索引表项占
每个索引项对应一个磁盘块, 故最大文件长度:
(2)块号占6字节, 块数占2字节的情形下, 最大文件长度:
。 合理的起始块号和块数所占字节数分别为(
或或或或) 。理由:块数占4B 或以上, 就可表示4TB 大小的文件长度, 达到文件系统的空间上限。
12．证明:在二叉树的三种遍历序列中，所有叶结点间的先后关系都是相同的。要求每步论断都指出根据。
【答案】前序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。若将“根”去掉，三种遍历就剩“左右”。三种遍历中的差别就是访问根结点的时机不同。二叉树是递归定义的，对左右子树均是按左右顺序来遍历的，因此所有叶结点间的先后关系都是相同的。
13．用一个数组S(设大小为MAX) 作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的判断条件，并用C 语言或PASCAL 语言设计公用的入栈操作push(i，x) ，其中i 为0或1，用于表示栈号，x 为入栈值。
【答案】两栈共享一向量空间(一维数组) ，栈底设在数组的两端，两栈顶相邻时为栈满。设共享数组为S[MAX]，则一个栈顶指针为﹣1，另一个栈顶指针为MAX 时，栈为空。用C 语言写的入栈操作push(i，x) 如下:
＝共享栈可能达到的最大容量
//ds为容量有MAX 个类型为elemtype 的元素的一维数组，由两个栈共享其空间。I 的值为0或1
//x为类型为elemtype 的元素。本算法将x 压入栈中。如压栈成功，返回1; 否则，返回
。 , 512B 可存放个索引项, 。