已选分类
工学计算机科学与技术
问答题在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(log n)的算法，确定树中第k个结点的位置。
问答题磁盘机由6个盘片组成，其中专设1个盘面为伺服面，其他的盘面作为记录数据的盘面。盘存储区域内直径为6.1cm，外直径为12.9cm，道密度为22TPM，位密度为6000bpm，平均寻道时间为10ms，磁盘转速为7200RPM。假定π=3，试计算：
问答题假定某采用页式虚拟存储管理的计算机系统中，主存储器容量为1GB，被分为262144块物理块，物理块号为0，1，2，…，262143。某进程的地址空间占4页，逻辑页号为0，1，2，3，被分配到主存储器的第20，45，101，58号物理块中。回答：
问答题某工厂有一个仓库可以存放甲、乙两种零部件，甲零件可以存放m件，乙零件可以存放n件，车间A专门生产甲零件，每次1件，每生产1件存放进仓库1件；车间B专门生产零件乙，每次1件，每生产1件存放进仓库1件。总装车间每次从仓库取出2件甲零件、1件乙零件组装成成品，车间A、B和总装车间必须互斥进入仓库。当仓库内甲、乙零件分别达到m、n件时，车间A、B分别停止生产。而仓库内任何一种零件为0时，总装车间停产。根据上述规则，请利用信号量机制，设计一个可以让车间A、B和总装车间协调运转的程序，并说明各个信号量的意义，用类C语言写出整个过程。
问答题某银行的营业厅有多个柜员窗口，可以同时办理业务。银行的营业厅中安排有n张座椅供储户休息等候。每个储户在进入营业厅时会在排队机上取得一个号码，若此前没有客户，则排队机就会唤醒一个柜员为储户服务，当没有储户时柜员便可以休息。若储户较多，则所有柜员均会参与服务，当排队储户数超过柜员数时，没有被服务的储户便会在座椅上休息，并等候叫号。当座位满时，再进入营业厅的储户不再从排队机上获取号码，会离开去找另外的营业厅。若将银行的柜员和储户的行为看成是不同类型的进程，请设计一个程序，利用信号量来完成上述操作，用C语言写出程序。
问答题
问答题下图是某存储芯片的引脚图，请回答：
问答题线性表(a1，a2，a3，…，an)中元素值递增有序(没有重复元素)且按顺序存储于计算机内。如果想在当前的线性表中查找数值为x的元素，请设计一个时间复杂度最低的算法。找到x后，将其与后继元素位置相交换。如果线性表中没有x，将其插入表中并使表中元素仍递增有序。请回答下列问题：
问答题已知线性表(a
1
，a
2
，a
3
，…，a
n
)存放在一维数组A中。试设计一个在时间和空间两方面都尽可能高效的算法，将所有奇数号元素移到所有偶数号元素前，并且不得改变奇数号(或偶数号)元素之间的相对顺序，要求：
问答题系统中有5个进程，每个进程的运行时间(单位：ms)、优先级和到达时刻，如下表所示： 进 程 P1 P2 P3 P4 P5 运行时间 10 2 2 1 5 优先级 4 6 2 3 6 到达时刻 0 1 2 3 4 请给出当系统分别采用时间片轮转算法(时间片为Ires)、不可抢占优先级调度算法和抢占式优先级调度算法时，各进程的执行情况。
问答题假定某采用页式虚拟存储管理的计算机系统中，主存储器容量为1GB，被分为262144块物理块，物理块号为0，1，2，……，262143。某进程的地址空间占4页，逻辑页号为0，1，2，3，被分配到主存储器的第20，45，101，58号物理块中。回答： (1)内存物理地址至少应该用多少位字长来表示? (2)进程每一页的长度为多少字节?逻辑地址中的页内地址应占用多少位字长? (3)把进程中每一页在分到的主存物理块中的起始地址和结束地址填入下表： 逻辑页号 物理起始地址 物理结束地址 0 1 2 3
问答题假设有8个记录A、B，C、D、E、F、G、H存放在磁盘里，每个磁道有8个扇区，正好可以存放8个记录。假设磁盘旋转速度为20ms/转，处理程序每读出一个记录后，用2ms的时间进行处理，请问： (1)当记录A、B、C、D、E、F、G、H按顺序放在磁道上时，顺序处理这5个记录花费的总时间是多少?假设启动时的位置正好在A扇区的起点。 (2)如何采取优化方法，使处理这些记录所花费的总时间最短?求出该最短时间。
问答题表中，a～n分别对应14种不同的微命令，假设一条微命令长20位，其中操作控制字段为8位，控存容量为1K×20位。要求：1．采用“不译法”与“分段直接编码法”混合设计此机微指令的操作控制字段格式，并为每个微命令分配编码；2．采用“增量”与“下址字段”相结合的方式设计此机微指令的顺序控制字段格式，若要使微程序可在整个控存空间实现转移，则该微指令的顺序控制字段可直接表示出几个转移条件?3．画出此机微指令的完整格式图，并标出每个具体字段所需的二进制位数。
问答题有一个仓库，可以存放A和B两种产品，但要求：
(1) 每次只能存入一种产品(A或B)；
(2) -N＜A产品的数量-B产品的数量＜M。
其中，N和M是正整数。试用P，V操作描述产品A与产品B的入库过程。
问答题设记录的关键字(key)集合：K={24，15，39，26，18，31，05，22}，请回答：
依次取K中各值，构造一棵二叉排序树(不要求平衡)，并写出该树的前序、中序和后序遍历序列。
设Hash表表长m=16，Hash函数H(key)=(key)%13，处理冲突方法为“二次探测法”，请依次取K中各值，构造出满足所给条件的Hash表；并求出等概率条件下查找成功时的平均查找长度。
将给定的K调整成一个堆顶元素取最大值的堆(即大根堆)。
问答题设有带头结点的循环双链表表示的线性表L=(a1，a2，……，an-1，an)。设计在时 间和空间上都尽可能高效的算法，将L改造成L=(a1，a3，……，an,……a4，a2)。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。
问答题一个进程分配给4个页帧(下面的所有数字均为十进制数，每一项都是从0开始计数的)。最后一次把一页装入到一个页帧的时间、最后一次访问页帧中的页的时间、每个页帧中的虚页号以及每个页帧的访问位(R)和修改位(M)如下表所示(时间均为从进程开始到该事件之前的时钟值，而不是从事件发生到当前的时钟值)。
虚页号
页帧
加载时间
访问时间
R位
M位
2
1
0
3
0
1
2
3
60
130
26
20
161
160
162
163
0
0
1
1
1
0
0
1
当虚页4发生缺页时，使用下列存储器管理策略，哪一个页帧将用于置换?解释每种情况的原因。
问答题为什么外围设备要通过接口与CPU相连?接口有哪些功能?
问答题设某计算机有四级中断A、B、C、D，其硬件排队优先级次序为A＞B＞C＞D。 下表列出了执行每级中断服务程序所需的时间。 中断服务程序 所需时间 A 5μs B 15μs C 3μs D 12μs 如果以执行中断服务程序的时间作为确定中断优先级的尺度，时间越短优先级越高。 (1)请指出如何为各级中断服务程序设置屏蔽码? (2)如果A、B、C、D分别在6μs、8μs、10μs、0μs时刻发出中断请求，请画出CPU执行中断服务程序的序列。 (3)基于上题，请计算上述四个中断服务程序的平均执行时间。
问答题假定AX和BX中的内容为带符号数，CX和DX中的内容为无符号数，试用比较指令和条件转移指令实现以下判断： (1)若DX的值超过CX的值，则转去执行EXCEED。 (2)若BX的值大于AX的值，则转去执行EXCEED。 (3)CX中的值为0吗?若是则转去执行ZERO。 (4)BX的值与Ax的值相减，会产生溢出吗?若溢出则转去执行OVERFLOW。 (5)若BX的值小于AX的值，则转去执行EQ—SMA。 (6)若DX的值低于CX的值，则转去执行EQ___SMA。