第8章习题参考解答

–184–第八章习题解答1．什么是文件？什么是文件系统？答：文件是一种抽象的机制，是具有某个特定符号名的相关数据的集合。文件系统是一个负责存取和管理辅助存储器上文件信息的机构，通常用目录组织文件。2．列举一些常用的文件扩展名。答：常见文件扩展名扩展名意义.Bak备份文件.BasBasic源程序.CC源程序.Dat数据文件.Obj目标文件（编译输出但未链接）.mpg用MPEG标准编码的影像文件.txt一般文本文件.html．在你熟悉的操作系统中列举一些常见的文件属性。答：在windows系统中比较常见的文件属性有：1）文件名（包括扩展名）；2）文件大小，占用空间；3）文件类型；4）创建时间，修改时间，访问时间；5）文件的访问属性（隐藏，只读）。6）文件位置；7）打开方式。4．假设一个顺序文件包含有2000个记录，如果在一个很长的时期内，有不同的记录从文件中检索出来，那么试估计每一次检索时平均得到的记录数目是多少？并解释答案。答：顺序文件是只能按照从头到尾的顺序以一定的数据单元对其进行存取操作的文件。所以在进行检索时，如果记录是第一条，那么访问记录数为1，如果是第二条，访问记录数为2，依次类推。又由于是在一个很长的时期内进行统计，那么每个记录被检索的概率可以认为是相等的为1/2000.则平均记录数目=1/2000*(1+2+…+2000)=2001/25．在UNIX文件系统中文件分成哪几种？答：在许多如UNIX的计算机操作系统中支持将文件分成普通文件、目录文件和特殊文件3种。普通文件中包含的是用户的信息，或者是一个用户应用程序，或者是一个系统的应用程序。目录文件是关于一些文件目录的列表。实际上目录文件也是普通文件，只是它具有专门–185–的写保护特权，只能由文件系统对它们进行写入修改操作，用户程序只能对目录文件进行读操作。UNIX把外部设备均看成是文件，称为特殊文件。特殊文件分为两大类：块特殊文件（如磁盘等）和字符特殊文件（如打印机、网络等）。6．通常文件有哪几种存取方式？答：两种。顺序存取和随机存取。7．典型的文件结构有哪几种？答：三种：顺序文件，索引文件和散列文件。8．索引文件可否使用顺序存取来实现访问，试说明理由。答：不行。索引文件由数据文件和索引组成，当进行文件检索时，一般的存取是首先进行索引的检索，再通过索引中保存的指向相应的数据文件的指针来找到文件。而当进行顺序存取时，如果按照索引的顺序来进行查找，由于有序的索引对应的数据文件的存放位置是无序的（也就是说下一位的索引对应的数据的位置可能在上一位的前面），而顺序存取要求的却是有序的从头到尾的查找，因此索引文件不可用顺序存取来实现访问。9．在索引文件中数据文件和索引是怎样关联的？答：索引文件由数据文件和索引组成。索引包括一系列被称作关键字的值，每个值代表相关存储结构中的一个信息单元（数据文件），索引中和每一个关键字相对应的都有一个表项，保存指向对应的信息单元存储位置的指针。因此，为了寻找特定的信息单元（数据文件），只需要在索引中找到特定的关键字，然后按照关键字所指向的位置检索信息单元就可以了。10．被索引的文件相对散列文件有什么优势？答：被索引文件的插入删除很方便只需简单修改记录就可以了。而散列文件虽然也可以通过这种方法来进行插入，删除，但当操作过多后，会造成文件结构不合理，即溢出桶满，基桶内多数为被删除的记录，需要重新组织文件。11．什么是冲突？试给出3种解决冲突的方法？答：冲突是指两个或两个以上的关键字经过散列后得到相同的值的情况。可以用以下的方法解决冲突：1）开放寻址法，当冲突发生时，系统将查找开放的或者是空闲的记录来存放新的数据；2）链表解决法，每一条记录都包含了下一条记录的指针。这样，当记录哈希后得到的地址产生冲突时，则将新记录存储在发生冲突记录的链表中。3）桶哈希法，另外一种解决冲突的方法是通过将数据存储空间划分为若干部分，每一个部分称为桶，每个桶可以容纳多个记录。根据一定的运算法则将各个数据记录关键字的值转换为相应的桶号，并将数据存放在对应的桶中。12．举一个随机存取文件的例子。–186–答：软盘、硬盘等，他们往上写数据时是由磁头和伺服电机自动控制随机往盘上写的。13．举一个顺序存取文件的例子。答：如早期的穿孔纸带、大型计算机上用的磁带等，他们必须从磁道的开始位置按顺序往上写数据，读取也是按顺序进行的。14．假设一个散列文件包含有美国一个当地社区的居民信息，如果这个文件的关键字段包含有7位的电话号码，为什么用它的前3位数字作为散列算法的基础并不是一个好的想法呢？答：由于关键字段含有7位，如果采用前3位数字（有1000种可能）作为散列算法的基础，那么即使是采用1000个记录时（此时每个记录里可能的键最少），每个记录里可能的键数仍然有10000个（即10000000/1000），这样建成的哈希列表的冲突非常多，所以不是一个好的想法。15．为什么一个公司职员的证件号码比他的名字更适合作为关键字？答：关键字是指能够唯一地将该条记录与其他记录进行区分的字段。在一个公司职员的信息中，名字可能与其他人重复，不唯一，而证件号码却是唯一的，所以证件号码更适合做关键字。16．在下面的例子中，描述一下你推荐的文件结构，并给出你的看法：（1）一个演讲的大致草稿；（2）一个牙医的病例；（3）一个邮件列表；（4）一个含有50000个词的参考书目和它们的解说。答：（1）顺序文件。演讲稿是按从头到尾进行的。（2）散列文件。由于牙医的病例需要随机存取，不采用顺序文件。而且不会进行过多的删除，这样为了避免索引文件带来的额外开销，可以使用散列文件。（3）索引文件。由于邮件会进行随机存取，不采用顺序文件。同时邮件列表会频繁的插入，删除，如果采用散列结构会导致文件结构的不合理，需要不时的整理散列文件结构，所以应该采用索引文件。（4）索引文件。由于词要进行随机读取，所以顺序文件不采用。而如果采用散列文件由于词的数量比较大，造成的冲突会很多，效率不高。所以采用索引文件。17．如果一个散列文件的文件列表长度为10，则3个任意记录中至少有两个记录散列到同一个位置的可能性有多大？文件中必须存放多少条记录才会使得发生冲突的可能性大于不发生冲突的可能性。答：3个任意记录中至少有两个记录散列到同一位置的可能性为：1-（10*9*8）/10*10*10=0.28。要求存放多少条记录才使发生冲突的可能性大于不冲突的可能性，即求至少存放多少条–187–时使得不冲突的可能性低于50%。又由存放一条不冲突概率为10/10,两条(10/10)*(9/10)，依次类推得：(10/10)(9/10)(8/10)(7/10)(6/10)=0.3024时，即存放了5条记录时成立。18．如果文件列表长度为23，系统采用求模法以及开放寻址方法解决冲突，则对于关键字为124、152、239、354和862的记录，将被存到哪一个位置？答：求模法：H（key）=key％list_size+1，其中list_size是文件列表的大小。开放寻址法，采用最简单的方法，将新记录存放到冲突地址的下一个地址中。1）H（124）=124%23+1=10，不冲突；2）H（152）=152%23+1=15，不冲突；3）H（239）=239%23+1=10，与124冲突；H2（239）=10+1=11，不冲突。4）H（354）=354%23+1=10，与124冲突；H2（354）=10+1=11，与239冲突；H3（354）=12，不冲突；5）H（862）=862%23+1=12，与354冲突。H2（862）=12+1=13，不冲突。