2017年沈阳航空航天大学数据结构复试仿真模拟三套题
● 摘要
一、应用题
1． 画出对算术表达式
表所示。
表 操作数栈和运算符找的变化过程
求值时操作数栈和运算符栈的变化过程。 求值，过程如【答案】设操作数栈是opnd ，运算符栈是optr ，对算术表达式
2． 三维数组
的存储首地址。 的每个元素的长度为4个字节，试问该数组要占多少个字节的存储空间? 如果数组元素以行优先的顺序存储，设第一个元素的首地址是100，试求元素
【答案】数组占的存储字节
数
3． 请写出应填入下列叙述中（ ）内的正确答案。
排序有各种方法，如插入排序、快速排序、堆排序等。
设一数组中原有数据如下：15，13，20，18，12，60。下面是一组用不同排序方法进行一遍排序后的结果。
第 2 页，共 22 页 的存储地
址
（ ）排序的结果为：12，13，15，18，20，60
（ ）排序的结果为：13，15，18，12，20，60
（ ）排序的结果为：13，15，20，18，12，60
（ ）排序的结果为：12，13，20，18，15，60
【答案】①快速排序②起泡排序③直接插入排序④堆排序
4． 将关键字序列（7, 8, 30，11，18, 9，14）散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组。散列函数是：
列法，要求装填（载）因子为0.7。
（1）请画出所构造的散列表。
（2）分别计算等概率情况下查找成功和查找不成功的平均查找长度。
【答案】（1）要求装填因子为0.7, 数组的长度应该为7/0.7=10, 数组下标为0〜9。各关键字的散列函数值如下表：
采用线性探测法再散列法处理冲突，所构造的散列表为：
（2）查找成功时，在等概率情况下，查找表中每个元素的概率是相等的，因此是根据表中元素个数来计算平均查找长度，各关键字的比较次数如下表所示：
故查找成功的平均查找长度为（1+1+1+1+3+3+2）/7=12/7。
在不成功的情况下，由于任意关键字key , H （key ）的值只能是0〜6之间，H （key ）为0需要比较3次，H （key ）为1需要比较2次，H （key ）为2需要比较1次，H （key ）为3需要比较2次，H （key ）为4需要比较1次，H （key ）为5需要比较5次，H （key ）为6需要比较4次，共7种情况，如下表所示：
所以，在等概率下，查找失败的平均查找长度为：（3+2+1+2+1+5+4）/7=18/7。
处理冲突采用线性探测再散
第 3 页，共 22 页
5． 某请求分页系统的局部页面置换策略如下：系统从0时刻开始扫描，每隔5个时间单位扫描
，本轮没有被访问过的页框将被系统回收，并放入到空闲页框链一轮驻留集（扫描时间忽略不计）
尾，其中内容在下一次被分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。假设不考虑其他进程的影响和系统开销，初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程
（1）访问
（2）访问
（3）访问
【答案】
（1）页框号为21。因为起始驻留集为空，而0页对应的页框为空闲链表中的第三个空闲页框，其对应的页框号为21。
（2）页框号为32。理由：因11>10故发生第三轮扫描，页号为1、3的页框32、15在第二轮已处于空闲页框链表中，此刻1页又被重新访问，因此应被重新放回到驻留集中。其页框号为32。
（3）页框号为41。理由：因为第2页从来没有被访问过，它不在驻留集中，因此从空闲页框链表中取出链表头的页框41，页框号为41。
（4）适合。理由：如果程序的时间局部性越好，从空闲页框链表中重新取回的机会越大，该策略的优势越明显。
6． （1）判定起泡排序的结束条件是什么？
（2）请简单叙述希尔排序的基本思想。
（3）将下列序列调整成堆（堆顶为最小值）。
（4）在16个关键字中选出最小的关键字至少要进行多少次比较? 再选出次小的关键字至少要进行多少次比较? 请简要说明选择的方法和过程。
【答案】（1）至多进行n-1趟起泡排序，或一趟起泡排序中未发生交换（即已有序）时，结束排序。
（2）希尔排序是对直接插入排序算法的改进，它从“记录个数少”和“基本有序”出发，将
，从而减少参与直接插入排序的数据量，当经过几次分待排序的记录划分成几组（缩小增量分组）
组排序后，记录的排列已经基本有序，这个时候再对所有的记录实施直接插入排序。
（3）13，24，33，65，70，56，48，92，80，112
（4）采用树形锦标赛排序选出最小关键字至少要15次比较。再选出次小关键字比较4次（两
第 4 页，共 22 页 P 依次访问的<虚拟页号，访问时刻>是
：请回答下列问题。 时，对应的页框号是什么？ 时，对应的页框号是什么? 说明理由。 . 时，对应的页框号是什么? 说明理由。 （4）该策略是否适合于时间局部性好的程序? 说明理由。
相关内容
相关标签