数据结构第11章

第十一章文件一、选择题1.散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（）方法是散列文件的关键。【哈尔滨工业大学2001二、5（2分）】A.散列函数B.除余法中的质数C.冲突处理D.散列函数和冲突处理2.顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用（）的方法可降低所需的代价。【北京邮电大学2000二、8（20/8分）】A.附加文件B.按关键字大小排序C.按记录输入先后排序D.连续排序3.用ISAM组织文件适合于（）。【中科院软件所1998】A．磁带B．磁盘4．下述文件中适合于磁带存储的是（）。【中科院计算所2000一、7（2分）】A.顺序文件B.索引文件C.散列文件D.多关键字文件5.用ISAM和VSAM组织文件属于（）。A.顺序文件B.索引文件C.散列文件【中国科技大学1998二、5（2分）中科院计算所1998二、5（2分）】6.ISAM文件和VASM文件属于（）。【山东大学2001二、5(1分)】A.索引非顺序文件B.索引顺序文件C.顺序文件D.散列文件7.B+树应用在（）文件系统中。【北京邮电大学2001一、1（2分）】A.ISAMB.VSAM二、判断题1.文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。【长沙铁道学院1998一、5(1分)】2.倒排文件是对次关键字建立索引。【南京航空航天大学1997一、10（1分）】3.倒排序文件的优点是维护简单。【南京航空航天大学1995五、10（1分）】4.倒排文件与多重表文件的次关键字索引结构是不同的。【西安交通大学1996二、6(3分)】5.Hash表与Hash文件的唯一区别是Hash文件引入了‘桶’的概念。【南京航空航天大学1996六10(1分）】6.文件系统采用索引结构是为了节省存储空间。【北京邮电大学2000一、10（1分）】7.对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。【东南大学2001一、1-10（1分）】8.对磁带机而言，ISAM是一种方便的稳健组织方法。【中科院软件所1997一、10（1分）】9.直接访问文件也能顺序访问，只是一般效率不高。【北京邮电大学2002一、10（1分）】10.存放在磁盘，磁带上的文件，即可以是顺序文件，也可以是索引结构或其他结构类型的文件。【山东大学2001一、7(1分)】11.检索出文件中的关键码值落在某个连续的范围内的全部记录，这种操作称为范围检索。对经常需要做范围检索的文件进行组织，采用散列法优于顺序检索法。【中山大学1994一、5（2分）】三、填空题1.文件可按其记录的类型不同而分成两类，即______和______文件。【西安电子科技大学1998二、6（3分）】2.数据库文件按记录中关键字的多少可分成______和______两种文件。【燕山大学1998一、10（2分）】3.从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如dBASE中数据库文件那样的文件组织结构，称为_(1)_文件；另一种是诸如用各种文字处理软件编辑成的文本文件，称为__(2)_文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_(3)_，_(4)_和_(5)_。B+树适用于组织_(6)_的索引结构，m阶B+树每个结点至多有_(7)_个儿子，除根结点外每个结点至少有(8)个儿子，根结点至少有_(9)_个儿子，有k个儿子的结点必有_(10)个关键码。【山东工业大学1996一、4（5分）】4.文件由______组成；记录由______组成。【大连海事大学1996(２分)】5.物理记录之间的次序由指针相链表示的顺序文件称为______。【燕山大学1998一、11（1分）】6.顺序文件中，要存取第I个记录，必须先存取______个记录。【哈尔滨工业大学2001一、4（2分）】7.索引顺序文件既可以顺序存取，也可以______存取。【武汉大学2000一、10】8.建立索引文件的目的是______。【中山大学1998一、12（1分）】9.索引顺序文件是最常用的文件组织之一，通常用____结构来组织索引。【长沙铁道学院1998二、6(2分)】10.倒排序文件的主要优点在于______。【山东工业大学1995一、3（1分）】11.检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按______检索，也可以按______检索；按______检索又可以有_________检索和_________检索。【山东大学1999一、1(5分)】12.散列检索技术的关键是______和______。【山东工业大学1995一、2（2分）】13.VSAM系统是由______、______、______构成的。【北京科技大学1997一、9】14.VSAM(虚拟存储存取方法)文件的优点是：动态地______，不需要文件进行______，并能较快地______进行查找。【山东大学2001三、4(2分)】四、应用题1.文件【山东工业大学1998一、1-1（2分）】2.文件存储结构的基本形式有哪些？一个文件采用何种存储结构应考虑哪些因素？【燕山大学1999二、4(4分）】3．名词解释：索引文件【哈尔滨工业大学2000一、4（3分）】4.什么是索引顺序文件？【哈尔滨工业大学2001三、5（3分）】【山东工业大学1998一、1-2（2分）】5．索引顺序存取方法（ISAM）中，主文件已按关键字排序，为何还需要主关键字索引？【东南大学1995四（6分）】6．分析ISAM文件（INDEXEDSEQUENTIALACCESSMETHORD）和VSAM文件（VIRTUALSTORAGEACCESSMETHORD）的应用场合、优缺点等。【华南理工大学2001一、4（4分）】7.一个ISAM文件除了主索引外，还包括哪两级索引？【北京科技大学1999一、8（2分）】8.倒排文件【山东工业大学1998一、1-3（2分）】9.为什么在倒排文件(invertedfiles)组织中，实际记录中的关键字域(keyfields)可删除以节约空间？而在多表(multilists)结构中这样做为什么要牺牲性能？【东南大学1997一、4（8分）】10.简单比较文件的多重表和倒排表组织方式各自特点。【东南大学2000一、2（6分）】11.组织待检索文件的倒排表的优点是什么？【北京科技大学2001一、10（2分）】12.为什么文件的倒排表比多重表组织方式节省空间？【东南大学2001一、2（1分）】13.试比较顺序文件，索引非顺序文件，索引顺序文件，散列文件的存储代价，检索，插入，删除记录时的优点和缺点。【西北工业大学1999四(8分)】14.已知两个各包含N和M个记录的排好序的文件能在O（N+M）时间内合并为一个包含N+M个记录的排好序的文件。当有多于两个排好序的文件要被合并在一起时，只需重复成对地合并便可完成。合并的步骤不同，所需花费的记录移动次数也不同。现有文件F1，F2，F3，F4，F5，各有记录数为20，30，10，5和30，试找出记录移动次数最少的合并步骤。【重庆大学2000二、3】15．已知职工文件中包括职工号、职工姓名、职务和职称4个数据项（见下表）。职务有校长、系主任、室主任和教员；校长领导所有系主任，系主任领导他所在系的所有室主任，室主任领导他所在室的全体教员；职称有教授、副教授和讲师3种。请在职工文件的数据结构中设置若干指针和索引，以满足下列两种查找的需要：（1）能够检索出全体职工间领导与被领导的情况；（2）能够分别检索出全体教授、全体副教授、全体讲师。要求指针数量尽可能少，给出各指针项索引的名称及含义即可。表职工文件职工号职工姓名职务职称001002003004005张军沈灵叶明张莲叶宏教员系主任校长室主任系主任讲师教授教授副教授教授006007008009010…周芳刘光黄兵李民赵松…教员系主任教员室主任教员…教授教授讲师教授副教授…【北京航空航天大学1996】参考文献[1]严蔚敏等。数据结构。北京：清华大学出版社，1997.4[2]殷人昆。数据结构。北京：清华大学出版社，2001.3[3]范策等。算法与数据结构。北京：机械工业出版社，2004.？[4]胡学刚。数据结构算法设计指导。北京：清华大学出版社，1999.2[5]黄水松等。数据结构与算法习题解析。北京：电子工业出版社，1996.8[6]蒋盛益等。《数据结构》学习指导与训练。北京：中国水利水电出版社，2003.8[7]前沿考试研究室。计算机专业研究生入学考试全真题解----数据结构与程序设计分册。北京：人民邮电出版社，2003.6[8]何军等。数据结构500题。北京：人民邮电出版社，2003.4[9]何军等。数据结构课程辅导与习题解析。北京：人民邮电出版社，2003.3[10]徐孝凯。数据结构辅导与提高。北京：清华大学出版社，2003.12[11]薛晓燕等。数据结构习题集与解题指导。北京：科学技术文献出版社，1995.7第十一章文件一．选择题1.D2.A3.B4.A5.B6.B7.B二.判断题1.√2.√3.×4.√5.×6.×7.×8.×9.×10.×11.√三．填空题1．操作系统文件数据库2．单关键字文件多关键字文件3．（1）数据库（2）文本（3）顺序组织（4）随机组织（5）链组织（6）随机组织（7）m（8）m/2（9）2（10）k4．记录数据项5．串联文件6．第I-17．随机8．提高查找速度9．树10．检索记录快11．（1）关键字（2）记录号（3）记录号（4）顺序（5）直接12．构造散列函数解决冲突的方法13．索引集顺序集数据集14．分配和释放存储空间重组对插入的记录四．应用题1．文件是由大量性质相同的记录组成的集合，按记录类型不同可分为操作系统文件和数据库文件。2．文件的基本组织方式有顺序组织、索引组织、散列组织和链组织。文件的存储结构可以采用将基本组织结合的方法，常用的结构有顺序结构、索引结构、散列结构。（1）顺序结构，相应文件为顺序文件，其记录按存入文件的先后次序顺序存放。顺序文件本质上就是顺序表。若逻辑上相邻的两个记录在存储位置上相邻，则为连续文件；若记录之间以指针相链接，则称为串联文件。顺序文件只能顺序存取，要更新某个记录，必须复制整个文件。顺序文件连续存取的速度快，主要适用于顺序存取，批量修改的情况。（2）带索引的结构，相应文件为索引文件。索引文件包括索引表和数据表，索引表中的索引项包括数据表中数据的关键字和相应地址，索引表有序，其物理顺序体现了文件的逻辑次序，实现了文件的线性结构。索引文件只能是磁盘文件，既能顺序存取，又能隋机存取。（3）散列结构，也称计算寻址结构，相应文件称为散列文件，其记录是根据关键字值经散列函数计算确定其地址，存取速度快，不需索引，节省存储空间。不能顺序存取，只能随机存取。其它文件均由以上文件派生而得。文件采用何种存储结构应综合考虑各种因素，如：存储介质类型、记录的类型、大小和关键字的数目以及对文件作何种操作。3．在主文件外，再建立索引表指示关键字及其物理记录的地址间一一对应关系。这种由索引表和主文件一起构成的文件称为索引文件。索引表依关键字有序。主文件若按关键字有序称为索引顺序文件，否则称为索引非顺序文件（通常简称索引文件）。索引顺序文件因主文件有序，一般用稀疏索引，占用空间较少。常用索引顺序文件有ISAM和VSAM。ISAM采用静态索引结构，而VSAM采用B+树的动态索引结构。索引文件既能顺序存取，也能随机存取。4．在索引文件中，若（数据区）主文件中关键字有序，则文件称为索引顺序文件，参见上题3。5．ISAM是专为磁盘存取设计的文件组织方式。即使主文件关键字有序，但因磁盘是以盘组、柱面和磁道（盘面）三级地址存取的设备，因此通常对磁盘上的数据文件建立盘组、柱面和磁道（盘面）三级索引。在ISAM文件上检索记录时，先从主索引（柱面索引的索引）找到相应柱面索引。再从柱面索引找到记录