2017年南开大学计算机技术、软件工程专业综合基础微机测试之数据结构考研复试核心题库
● 摘要
一、应用题
1． 设散列表为数分别为
：
注：％是求余数运算
中，函数
码序列为
（2）计算搜索成功的平均搜索长度表示颠倒十进制数x 的各位，如 即表的大小为 其等。若插入的关键
，现采用双散列法解决冲突。散列函数和再哈希函（1）试画出插入这8个关键码后的哈希表；
【答案】（1）插入这8个关键码后的哈希表如表所示：
表 插入关键字后的哈希表
（2）
2． 线性表有两种存储结构：一是顺序表，二是链表。试问：
（1）如果有，2个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构? 为什么？
（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构? 为什么？
【答案】（1）应选择链式存储结构。因为它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O （1）。
（2）应选择顺序存储结构。因为顺序表可以随机存取，时间复杂度为O （1）。
3． 设内存中可利用空间已连成一个单链表，对用户的存储空间需求，一般有哪三种分配策略？
【答案】（1）首次适配法
从链表头指针开始查找，找到第一个大于等于所需空间的结点即分配。首次适配法适合事先不知道请求分配和释放信息的情况，分配时需查询，释放时插在表头。
（2）最佳适配法
链表结点大小增序排列，找到第一个大于等于所需空间的结点即分配。最佳适配法适用于请求分配内存大小范围较宽的系统，释放时容易产生存储量很小难以利用的内存碎片，同时保留那
些很大的内存块以备将来可能发生的大内存量的需求，分配与回收均需查询。
（3）最差适配法
链表结点大小逆序排列，总从第一个结点开始分配，将分配后结点所剩空间插入到链表适当位置。最差适配法适合请求分配内存大小范围较窄的系统，分配时不查询，回收时查询，以便插入适当位置。
4．
某局域网采用
程。
（1）若主机甲和主机乙发送数据时发生冲突，则从开始发送数据时刻起，到两台主机均检测到冲突时刻止，最短需经过多长时间? 最长需经过多长时间？（假设主机甲和主机乙发送数据过程中，其他主机不发送数据）
（2）若网络不存在任何冲突与差错，主机甲总是以标准的最长以太网数据帧（1518字节）向主机乙发送数据，主机乙每成功收到一个数据帧后立即向主机甲发送一个64字节的确认帧，主机甲收到确认帧后方可发送下一个数据帧，此时主机甲的有效数据传输速率是多少？（不考虑以太网帧的前导码）
【答案】（1）当甲乙两台主机同时向对方发送数据时，两台主机均检测到冲突的时间最短
：=
（lkm/200000km/s）×2=10j×s ; 当一台主机发送的数据就要到达另一台主机时，另一台主机才发送数据，两台主机均检测到冲突的时间最长：
=1500B=1500×8bit=12000bit; 发送1518B 的发送时间=1518×8/10Mbps=
间=2km/200000km/s
=确认帧的发送时间=64×
8/10Mbps=; 确认帧的传播时间
=2km/200000km/s=; 发送1518B 所用的总时间为主机甲的有效数据传输率为12000bit ／1285.6μs=9.33Mbps。
5． 在多关键字排序时，LSD 和MSD 两种方法的特点是什么？
【答案】（1）最高位优先（MSD ）法 先对最高位关键字进行排序，将序列分成若干子序列，
每个子序列中的记录都具有相同的值，然后，分别就每个子序列对关键字
列。
（2）最低位优先
先对最低位关键字法 进行排序，然后对高一级关键字
协议实现介质访问控制，
数据传输率为主机甲和主机乙之间的距离为2km ，信号传播速度是200000km/S。请回答下列问题，要求说明理由或写出计算过 数据帧的传播时（2）有效数据传输速率=发送的有效数据/发送有效数据所用的总时间。发送的有效数据进行排序，按值不同再分成若干更小的子序列，依次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序进行排序，依次重复，直至对最高
位关键字排序后便成为一个有序序列。进行排序时，不必分成子序列，对每个关键字都是整个
排序时，只能用稳定的排序方法。另一方面，按LSD 进行排序序列参加排序，
但对
时，可以不通过关键字比较实现排序，而是通过若干次“分配”和“收集”来实现排序。
6． 设五个字符的编码分别为1，2，3，4，5，并设标识符依以下次序出现
：
要求用哈希（Hash ）方法将它们存入具有10个位置的表
中。
（1）将上述关键字（标识符）构造一个哈希函数，使得发生冲突尽可能地少；
（2）线性探测再散列法解决冲突。写出上述各关键字在表中位置。
【答案】（1）构造的哈希函数为：哈希函数（2）关键字在表中的位置如表所示：
表 关键字在表中的位置
7． 某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次 创建新文件。请回答如下问题。
（1）在连续、链式、索引三种文件的数据块组织方式中，哪种更合适? 要求说明理由。为定位文件数据块。需要在FCB 中设计哪些相关描述字段？
（2）为快速找到文件，对于FCB ，是集中存储好，还是与对应的文件数据块连续存储好? 要求说明理由。
【答案】根据题目所给条件，文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但是可以多次创建新文件，我们得知该文件系统是不能修改原文件的，只能将修改后的文件按新文件来存储，这与一次刻录光盘的存储方式相似。对于这样的系统，因为不需要随时添加或删除文件的内容，所以一次写入的文 件的大小是固定不变的，也是可预知的，而连续存放文件的方式就有其优点。这种方式只需要知道文件的起始地 址和文件的大小，便可以通过计算的方法找到文件的任何位置。文件若需要修改，则原文件作废，修改以后的文 件以新文件的形式重新写入，不会产生存储碎片，高效，高利用率。所以，如下作答。
（1）连续的数据块组织方式更合适，因为文件的数据一次性写入磁盘，已写入的文件不可修改，但是可以 多次创建新文件，我们得知该文件系统是不能修改原文件的，只能将修改后的文件按新文件来存储。不需要随时添加或删除文件的内容，所以一次写入的文件的大小是固定不变的，也是可预知的。这样，只需要知道文件的起 始地址和文件的大小，便可以通过计算的方法访问文件的任意位置。
为定位文件数据块。需要在FCB 中设计相关描述字段有： <起始块号，块数>或者〈起始块号，结束块号>。
（关键字各字符编码之和）
相关内容
相关标签