2017年中国传媒大学计算机软件与理论9066程序设计复试之数据结构(C语言版)复试实战预测五套卷
● 摘要
一、应用题
1． 设LS 是一个线性表，
若采用顺序存储结构，则在等概率的前提下，插
与
之间
的概率
为
入一个元素需要平均移动的元素个数是多少? 若元素插
在
【答案】需要分两种情况讨论：
，插入位置0..n ，则平均移动个数为（1）等概率（后插）
（2）若不等概率，则平均移动的元素个数为
2． 在多关键字排序时，LSD 和MSD 两种方法的特点是什么？
【答案】（1）最高位优先（MSD ）法
先对最高位关键字进行排序，将序列分成若干子序列，
每个子序列中的记录都具有相同的值，然后，分别就每个子序列对关键字列。
（2）最低位优先先对最低位关键字位关键字
序列参加排序，
但对
法
进行排序，然后对高一级关键字
进行排序，依次重复，直至对最高
进行排序，按值不同再分成若干更小的子序列，依
次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序
则插入一个元素需要平均移动的元素个数又是多少？
排序后便成为一个有序序列。进行排序时，不必分成子序列，对每个关键字都是整个
排序时，只能用稳定的排序方法。另一方面，按LSD 进行排序
时，可以不通过关键字比较实现排序，而是通过若干次“分配”和“收集”来实现排序。
3． 写出下面算法中带标号语句的频度。
设k 的初值等于1。
【答案】（1）这是一个递归调用，因k 初值为1，由语句（6）知，每次调用k 增1，故第（1）语句执行n 次，所以频度是n 。
（2）这是FOR 循环语句，在满足（1）的条件下执行，该语句进入循环体（3）n 次，加上最后一次判断出界，故执彳丁了n ＋1次，所以频度是n ＋1。
（3）这是循环体语句，共执行了n 次，所以频度是n 。
，k=2时判断n 次，最后（4）这是循环语句，当k=l时判断n ＋1次（进入循环体（5）n 次）
一次k=n－l 时判断3次，故执行次数是（n ＋1）＋n ＋... ＋3=（n ＋4）（n －1）/2次，所以频度是（n ＋4）（n －1）/2。
（5）语句（5）是（4）的循环体，每次比（4）少一次判断，故执行次数是n ＋（n －1）＋... ＋2=（n ＋2）（n －1）/2次，所以频度是（n ＋2）（n －1）/2。
（6）这是循环体语句，共执行了n －1次，所以频度是n －1。
4． 输入一个正整数序列（53，17，12，66，58，70，87，25，56，60），试完成下列各题。
（1）按次序构造一棵二叉排序树BS 。
（2）依此二叉排序树，如何得到一个从大到小的有序序列？ （3）画出在此二叉排序树中删除“66”后的树结构。 【答案】（1）构造的二叉排序树如图1所示：
图1 二叉排序树
（2）若二叉树非空，要得到一个从大到小的有序序列可以先中序遍历右子树；再访问根结点；最后中序遍历左子树。
（3）如图2所示：
图2
5． 设某文件经内排序后得到100个初始归并段（初始顺串），若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少？
【答案】设归并路数为k ，归并趟数为s ，则最少5-路归并完成排序。
6． 请阅读下列算法，回答问题。
问题一：这是什么类型的排序算法，该排序算法稳定吗？ 问题二：设置
|的作用是什么? 若将WHILE--DO 语句中判断条件改为
该
算法将会有什么变化，是否还能正确工作？
【答案】问题一：此为直接插入排序算法，该算法稳定。 问题二：采用
的作用是监视哨，免去每次检测文件是否到尾，提高了排序效率。
描述算法后，算法变为不稳定排序，但能正常工作。
因
且k 为整数，故k=5，即
7． 文件F 由200条记录组成，记录从1开始编号，用户打开文件后，欲将内存中的一条记录插入文件F 中，作为其第30条记录，请回答下列问题，并说明理由。
（1）若文件系统为顺序分配方式，每个存储块存放一条记录，文件F 的存储区域前后均有足够空闲的存储空间，则要完成上述操作最少要访问多少存储块？ F 的文件控制区内容会有哪些改变？
（2）若文件系统为链接分配方式，每个存储块存放的一条记录和一个链接指针，则要完成上述操作最少要 访问多少存储块？若每个存储块大小为1KB ，其中4个字节存放指针，则该系统支撑文件的最大长度是多少？
【答案】（1）因为要最少访问，所以选择将前29块前移一个存储块单元，然后将要写入的记录写入到当前的第30条的位置上。由于前移都要先访问原存储块将数据读出，再访问目标存储块将数据写入，所以最少需要访问
块存储块
F 的文件区的文件长度加1，起始块号减1
（2）采用链接方式则需要顺序访问前29块存储块，然后将新纪录的存储块插入链中即可，把新的块存入磁盘要1次访存，然后修改第29块的链接地址存回磁盘又一次访存。一共就是
相关内容
相关标签