2017年宁波大学计算机网络之数据结构(C语言版)复试仿真模拟三套题
● 摘要
一、应用题
1． 组织待检索文件的倒排表的优点是什么？
【答案】倒排表作为索引的优点是索引记录快，因为从次关键字值直接找到各相关记录的物理记录号，倒排因此而得名（因通常的查询是从关键字查到记录）。在插入和删除记录时，倒排表随之修改，倒排表中具有相同次关键字的记录号是有序的。
2． （1）如果G1是一个具有n 个顶点的连通无向图，那么G1最多有多少条边?G1最少有多少条边？
（2）如果G2是一个具有n 个顶点的强连通有向图，那么G2最多有多少条边?G2最少有多少条边？
（3）如果G3是一个具有n 个顶点的弱连通有向图，那么G3最多有多少条边?G3最少有多少条边？
1）G1最多n （n-l ）/2条边，最少n-1条边。 【答案】（
（2）G2最多n （n-l ）条边，最少n 条边。
（3）G3最多n （n-l ）条边，最少n-1条边。
3． 文件存储结构的基本形式有哪些? 一个文件采用何种存储结构应考虑哪些因素？
【答案】文件的基本组织方式有顺序组织、索引组织、散列组织和链组织，常用的结构有顺序结构、索引结构、散列结构。
（1）顺序结构，相应文件为顺序文件，其记录按存入文件的先后次序顺序存放。顺序文传本质上就是顺序表。若逻辑上相邻的两个记录在存储位置上相邻，则为连续文件；若记录之间以指针相链接，则称为串联文件。顺序文件只能顺序存取，要更新某个记录，必须复制整个文件。顺序文件连续存取的速度快，主要适用于顺序存取，批量修改的情况。
（2）带索引的结构，相应文件为索引文件。索引文件包括索引表和数据表，索引表中的索引项包括数据表中数据的关键字和相应地址，索引表有序，其物理顺序体现了文件的逻辑次序，实现了文件的线性结构。索引文件只能是磁盘文件，既能顺序存取，又能随机存取。
（3）散列结构，也称计算寻址结构，相应文件称为散列文件，其记录是根据关键字值经哈希函数计算确定其地址，存取速度快，不需索引，节省存储空间。不能顺序存取，只能随机存取。
文件采用何种存储结构应综合考虑各种因素，如：存储介质类型、记录的类型、大小和关键字的数目以及对文件作何种操作。
4． 画出对算术表达式求值时操作数栈和运算符栈的变化过程。
求值，过程如
第 2 页，共 21 页 【答案】设操作数栈是opnd ，运算符栈是optr ，对算术表达式
表所示。
表 操作数栈和运算符找的变化过程
5． 请写出应填入下列叙述中（ ）内的正确答案。
排序有各种方法，如插入排序、快速排序、堆排序等。
设一数组中原有数据如下：15，13，20，18，12，60。下面是一组用不同排序方法进行一遍排序后的结果。
（ ）排序的结果为：12，13，15，18，20，60
（ ）排序的结果为：13，15，18，12，20，60
（ ）排序的结果为：13，15，20，18，12，60
（ ）排序的结果为：12，13，20，18，15，60
【答案】①快速排序②起泡排序③直接插入排序④堆排序
6． 设散列表为数分别为
：
注：％是求余数运算
中，函数
码序列为表示颠倒十进制数x 的各位，如 即表的大小为 其等。若插入的关键
，现采用双散列法解决冲突。散列函数和再哈希函
（1）试画出插入这8个关键码后的哈希表；
第 3 页，共 21 页
（2）计算搜索成功的平均搜索长度
【答案】（1）插入这8个关键码后的哈希表如表所示：
表 插入关键字后的哈希表
（2）
7． 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading ”和“being ”的存储映像如图所示。
图 存储映像7K 意图
设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为
符i 所在结点的位置p ）。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C 或
【答案】
（1）算法的基本设计思想：
①分别求出strl 和str2所指的两个链表的长度m 和n ;
②将两个链表以表尾对齐：令指针p 、q 分别指向strl 和str2的头结点，若
表中的第个结点；若则使q 指向链表中的第
表尾的长度相等。
③反复将指针p 和q 同步向后移动，并判断它们是否指向同一结点。若p 和q 指向同一结点，则该点即为所 求的共同后缀的起始位置。
（2）用C 语言算法描述如下：
两个指针同步向后移动
第 4 页，共 21 页 请设计一个时间上尽可能高效的算法，找出由strl 和str2所指的两个链表共同后缀的起始位置（如图中字或JA V A 语言描述算法，关键之处给出注释。 （3）说明你所设计算法的时间复杂度。 则使p 指向链个结点，即使指针p 和q 所指的结点到
相关内容
相关标签