2017年南京信息工程大学F18数据结构复试仿真模拟三套题一、应用题1 试比较顺序文件、索引非顺序文件、索引顺序文件、哈希文件的存储代价，检索、插入、删除记录时的优点和缺点。【答案】（1）顺序文件只能顺序查找，优点是批量检索速度快，不适于单个记录的检索。顺序文件不能像顺序表那样插入、删除和修改，因文件中的记录不能象向量空间中的元素那样“移动”，只能通过复制整个文件实现上述操作。（2）索引非顺序文件适合随机存取，不适合顺序存取，因主关键字未排序，若顺序存取会引起磁头频繁移动。索引顺序文件是最常用的文件组织，因主文件有序，既可顺序存取也可随机存取。索引非顺序文件是稠密索引，可以“预查找”，索引顺序文件是稀疏索引，不能“预查找”，但由于索引占空间较少，管理要求低，提高了索引的查找速度。（3）散列文件也称直接存取文件，根据关键字的哈希函数值和处理冲突的方法，将记录散列到外存上。这种文件组织只适用于像磁盘那样的直接存取设备，其优点是文件随机存放，记录不必排序，插入、删除方便，存取速度快，无需索引区，节省存储空间。缺点是散列文件不能顺序存取，且只限于简单查询。经多次插入、删除后，文件结构不合理，需重组文件，这很费时。2 用单链表保存m 个整数，节点的结构为（data , link ）, 且（n 为正整数）。现要求设计一个时间复杂度尽可能高效地算法，对于链表中绝对值相等的节点，仅保留第一次出现的节点而删除其余绝对值相等的节点。例如若给定的单链表head 如下 删除节点后的head 为 要求（1）给出算法的基本思想 （2）使用c 或语言，给出单链表节点的数据类型定义。语言描述算法，关键之处给出注释。（3）根据设计思想，采用c 或【答案】（1）算法思想：定义一个大小为n 的布尔数组flag ，初始时所有的元素都赋值为false , 用来标识遍历过程中是（4）说明所涉及算法的时间复杂度和空间复杂度。否出现元素绝对值为flag 的节点。然后遍历链表，遍历过程中，每一个当前结点data 域的绝对值，则将flag 位置为真（true ）所对应的flag 位：若为真，则删除该结点；若为假（false ）。（2）节点的数据结构定义如下： （3）全局数组标志节点的绝对值是否出现过 如果此绝对值已经在节点值的绝对值中出现过则删除该节点 否则，将flag 中对应的位置置为true ，并将指针指向下一个元素 ，申请大小（4）只遍历一次链表，所以时间复杂度为0 （m ） （m 为单链表中元素的个数）为n 的数组，所以空间复杂度为0 （n ） （n 为节点绝对值的最大值）。 3 如果两个串含有相等的字符，能否说它们相等？【答案】仅从两串含有相等的字符，不能判定两串是否相等，两串相等的充分必要条件是两串长度相等且对应位置上的字符相同（即两串串值相等）。4 将下列出三棵树组成的森林转换为二叉树（只要求给出转换结果）。 图1【答案】森林转换为二叉树分以下三步：（1）连线（将兄弟结点相连，各树的根看作兄弟）。（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）。 （3）旋转（以最左边树的根为轴. 顺时针向下旋转45度）。 所以由上面三棵树转换得到的二叉树如图2所示： 图2 5 请写出应填入下列叙述中（ ）内的正确答案。某一工程作业的网络图如图1所示，其中箭头表示作业，箭头边的数字表示完成作业所需的天 数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列（例如0-2-7-9-11）表示进行作业的路径。完成此工程的关键路径是（A ）完成此工程所需的最少天数为（B ）天，此工程中具有最大充，充裕天数是（D ）裕天数的事件是（C ）。关键路径上的事件的充裕天数是（E ）。 图1【答案】A. 0-2-6-9-11; B. 20; C.事件顶点1、5和7各充裕两天；D. 4天；E. 0 6 已知一个大小为512个字长的存储，假设先后有6个用户申请大小分别为23，45，52，100，11和19的存储空间，然后再顺序释放大小为45，52，11的占用块。假设以伙伴系统实现态存储管理。（1）画出可利用空间表的初始状态。一、应用题考研试题