当前位置：问答库＞考研试题

一、应用题

1． 一个循环队列的数据结构描述如下：

给出循环队列的队空和队满的判断条件，并且分析一下该条件对队列实际存储空间大小的影响，如果为了不损失存储空间，你如何改进循环队列的队空和队满的判断条件？

【答案】（1）队空：

（2）队满：

这种判断方法，会“牺牲一个存储单元”。为了不损失存储空间，可以通过设置标志位的方式来进行队空和队满的判断。设标记tag ，tag 等于0情况下，若删除时导致front=rear为队空; tag=l情况下，若因插入导致front=rear则为队满。

2． 在某程序中，有两个栈共享一个一维数组空间的栈底。

（1）对栈1、栈2, 试分别写出（元素x ）入栈的主要语句和出栈的主要语句。 （2）对栈1、栈2, 试分别写出栈满、栈空的条件。 【答案】（1）入栈主要语句

出栈主要语句

分别是两个栈

（2）

3． 调用下列C 函数f （n ），回答下列问题：

（1）试指出f （n ）值的大小，并写出，f （n ）值的推导过程；

（2）假定n=5，试指出，f （5）值的大小和执行，f （5）时的输出结果。 C 函数：

【答案】（1）第一层FOR 循环判断n ＋1次，往下执行n 次，第二层FOR 执行次数为（n ＋，第三层循环体受第一层循环和第二层循环的控制，其执行次数如（n －1）＋（n －2）＋... ＋1）表所示。

表 执行次数

执行次数为

（2）在n=5对，f （5）=55，执行过程中，输出结果为：

4． 文件F 由200条记录组成，记录从1开始编号，用户打开文件后，欲将内存中的一条记录插入文件F 中，作为其第30条记录，请回答下列问题，并说明理由。

（1）若文件系统为顺序分配方式，每个存储块存放一条记录，文件F 的存储区域前后均有足够空闲的存储空间，则要完成上述操作最少要访问多少存储块？ F 的文件控制区内容会有哪些改变？

（2）若文件系统为链接分配方式，每个存储块存放的一条记录和一个链接指针，则要完成上述操作最少要 访问多少存储块？若每个存储块大小为1KB ，其中4个字节存放指针，则该系统支撑文件的最大长度是多少？

【答案】（1）因为要最少访问，所以选择将前29块前移一个存储块单元，然后将要写入的记录写入到当前的第30条的位置上。由于前移都要先访问原存储块将数据读出，再访问目标存储块将数据写入，所以最少需要访问

块存储块

F 的文件区的文件长度加1，起始块号减1

（2）采用链接方式则需要顺序访问前29块存储块，然后将新纪录的存储块插入链中即可，把新的块存入磁盘要1次访存，然后修改第29

块的链接地址存回磁盘又一次访存。一共就是

次。

4个字节的指针的地址范围为

所以此系统支撑文件的最大长度为

5． 设某计算机的逻辑地址空间和物理地址空间均为64KB , 按字节编址。若某进程最多需要6页（Page ）数据存储空间，页的大小为1KB , 操作系统采用固定分配局部置换策略为此进程分配4个页框（PageFrame ）。在时刻260前的该进程访问情况如下表所示（访问位即使用位）。

当该进程执行到时刻260时，要访问的逻辑地址为17CAH 的数据，请回答下列问题： （1）该逻辑地址对应的页号是多少？

（2）若采用先进先出（FIFO ）置换算法，该逻辑地址对应的物理地址是多少? 要求给出计算过程。

（3）若采用时钟（CLOCK ）置换算法，该逻辑地址对应的物理地址是多少? 要求给出计算过程。（设搜索下一页的指针沿顺时针方向移动，且当前指向2号页框，如图所示）

图

【答案】（1）由题可知计算机的逻辑地址空间和物理地址空间均为64KB=216B, 按字节编址，并且页的大小为IK=210, 故逻辑地址和物理地址的地址格式均为：

地址17CA=0001011111001010B，故可知其逻辑页号为000101B=5。

（2）根据FIFO 算法，需要替换出最早装入的页，故需置换0号页，将5号页装入7号页框中，所以物理地址为0001111111001010B=1FCAH。

（3）根据CLOCK 算法，如果当前指针所指页框的使用位为0, 则替换该页，否则将使用位清零，并将指针指向下一个页框，继续查找。由题可知，将从2号页框开始，前4次查找页框号的顺序为2、4、7、9, 并将对应页框的使用位清零。在第5次查找中，指针指向2号页框，因2号页框的使用位已经为0, 故将2号页框的页将5号装入2号页框，并将其对应使用位设置为1, 所以对应的物理地址为0000101111001010B=0BCAH。