2019年计算机考研408真题 – 哔哩哔哩(2019年计算机二级考试真题及答案)

2019年计算机考研408真题 – 哔哩哔哩(2019年计算机二级考试真题及答案)缩略图

https://hwpno1.blog.csdn.net/article/details/88634013?spm=1001.2014.3001.5502

预览:
![在这里插入图片描述](https://img-blog.csdnimg.cn/20191106220329760.png?x-oss-process=image/watermark,type_zmfuz3pozw5nagvpdgk,shadow_10,text_ahr0chm6ly9ibg9nlmnzzg4ubmv0l3dlaxhpbl80mjg1oti4ma==,size_16,color_ffffff,t_70)![在这里插入图片描述](https://img-blog.csdnimg.cn/20191106220345850.png?x-oss-process=image/watermark,type_zmfuz3pozw5nagvpdgk,shadow_10,text_ahr0chm6ly9ibg9nlmnzzg4ubmv0l3dlaxhpbl80mjg1oti4ma==,size_16,color_ffffff,t_70)
2019 年全国硕士研究生招生考试
计算机科学与技术学科联考
计算机学科专业基础综合试题
一、 单项选择题: 1~40 小题,每小题 2 分,共 80 分。下列每题给出的四个选项中,只有一个选项符合试题要求。
1.? ? ?设 n 是描述问题规模的非负整数,下列程序段的时间复杂度是
x=0 ;
while ( n>= ( x+l ) * ( x+l ))
x=x+l ;
a.? o ( log n )? ? ?b.? o ( n 1/2 )? ? ?c.? o ( n )? ? ?d.? o ( n 2 )
2.? ? ?若将一棵树 t 转化为对应的二又树 bt ,则下列对 bt 的遍历中,其遍历序列与 t 的后根遍历序列相同的是
a.? 先序遍历? ? ?b.? 中序遍历? ? ?c.? 后序遍历? ? ?d.? 按层遍历
3.? ? ?对 n 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115 个结点,则 n 的值是
a.? 56? ? b.? 57? ? c.? 58? ? d.? 60
4.? ? ?在任意一棵非空平衡二又树 ( avl 树 ) t 1 中,删除某结点 v 之后形成平衡二又树 t 2 ,再将 w 插入 t 2 形成平衡二又树 t 3 。下列关于 t 1 与 t 3 的叙述中,正确的是
i. 若 v 是 t 1 的叶结点,则 t 1 与 t 3 可能不相同
ⅱ. 若 v 不是 t 1 的叶结点,则 t 1 与 t 3 一定不相同
ⅲ. 若 v 不是 t 1 的叶结点,则 t 1 与 t 3 一定相同
a.? 仅 i? ? ? b.? 仅 i i? ? ? c.? 仅 i 、 ⅱ? ? ? d.? 仅 i 、 ⅲ
?5.? ? ?下图所示的 aoe 网表示一项包含 8 个活动的工程 。 活动 d 的最早开始时间和最迟开始时间分别是
a.? 3 和 7? ? ?b.? 12 和 12? ? ?c.? 12 和 14? ?d.? 15 和 15
6.? ? ?用有向无环图描述表达式 ( x+y ) * (( x+y ) /x ) ,需要的顶点个数至少是
a.? 5? ? ?b.? 6? ? ? ?c.? 8? ? ?d.? 9
7.? ? ?选择一个排序算法时,除算法的时空效率外,下列因素中,还需要考虑的是
i . 数据的规模? ? ? ?ⅱ. 数据的存储方式? ? ?ⅲ. 算法的稳定性? ? ?v. 数据的初始状态
a.? 仅 ⅲ? ?b.? 仅 i 、 ⅱ? ? ? ?c.? 仅 ⅱ 、 ⅲ 、 iv? ? ?d.? i 、 ⅱ 、 ⅲ 、 ⅳ
8.? ? ?现有长度为 11 且初始为空的散列表 ht ,散列函数是 h ( key ) =key%7 ,采用线性探查 ( 线性探测再散列 ) 法解决冲突将关键字序列 87 , 40 , 30 , 6 , 11 , 22 , 98 , 20 依次插入到 ht 后, ht 查找失败的平均查找长度是
a.? 4? ? ? ? ?b.? 5. 25? ? ? ? ? ?c.? 6? ? ? ? ? ?d.? 6. 29
9.? ? ?设主串 t=“abaabaabcabaabc” ,模式串 s=“abaab c ” ,采用 kmp 算法进行模式匹配,到匹配成功时为止,在匹配过程中进行的单个字符间的比较次数是
a.? 9? ? ? ? ?b.? 10? ? ? ? ? ?c.? 12? ? ? ? ? ?d.? 15
10 .? ? 排序过程中,对尚未确定最终位置的所有元素进行一遍处理称为一 “ 趟 ” 。下列序列中,不可能是快速排序第二趟结果的是
a.? 5 , 2 , 16 , 12 , 28 , 60 , 32 , 72? ? ?b.? 2 , 16 , 5 , 28 , 12 , 60 , 32 , 72
c.? 2 , 12 , 16 , 5 , 28 , 32 , 72 , 60? ? ?d.? 5 , 2 , 12 , 28 , 16 , 32 , 72 , 60
11 .? ? 设外存上有 120 个初始归并段,进行 12 路归并时,为实现最佳归并,需要补充的虚段个数是
a.? 1? b.? 2? c.? 3? d.? 4
12 .? ? 下列关于冯 · 诺依曼结构计算机基本思想的叙述中,错误的是
a.? 程序的功能都通过中央处理器执行指令实现
b.? 指令和数据都用二进制表示,形式上无差别
c.? 指令按地址访问,数据都在指令中直接给出
d.? 程序执行前,指令和数据需预先存放在存储器中
13 .? ? 考虑以下 c 语言代码:
unsigned short usi=65535 ;
short si=usi ;
执行上述程序段后, si 的值是
a.? -1? ? ? ? b.? -32767? ? ? ? c.? -32768? ? ? d.? -65535
14 .? ? 下列关于缺页处理的叙述中,错误的是
a.? 缺页是在地址转换时 cpu 检测到的一种异常
b.? 缺页处理由操作系统提供的缺页处理程序来完成
c.? 缺页处理程序根据页故障地址从外存读入所缺失的页
d.? 缺页处理完成后回到发生缺页的指令的下一条指令执行
15 .? ? 某计算机采用大端方式,按字节编址。某指令中操作数的机器数为 1234 ff00h ,该操作数采用基址寻址方式,形式地址 ( 用补码表示 ) 为 ff12h ,基址寄存器内容为 f000 0000h ,则该操作数的 lsb ( 最低有效字节 ) 所在的地址是
a.? f000 ff12h? ? ? ? b.? f000 ff15h? ? ? c.? efff ff12h? ? d.? efff ff15h
16.? ? ?下列有关处理器时钟脉冲信号的叙述中,错误的是
a.? 时钟脉冲信号由机器脉冲源发出的脉冲信号经整形和分频后形成
b.? 时钟脉冲信号的宽度称为时钟周期,时钟周期的倒数为机器主频
c.? 时钟周期以相邻状态单元间组合逻辑电路的最大延迟为基准 确定
d.? 处理器总是在每来一个时钟脉冲信号时就开始执行一条新的指令
17.? ? ?某指令功能为 r[r2] ← r[r1]+m[r[r0]] ,其两个源操作数分别采用寄存器、寄存器间接寻址方式。对于下列给定部件,该指令在取数及执行过程中需要用到的是
i. 通用寄存器组 ( gprs )? ? ? ? ? ?ⅱ. 算术逻辑单元 ( alu )
ⅲ . 存储器 ( memory )? ? ? ? ?ⅳ. 指令译码器 ( id )
a.? 仅 i 、 ⅱ? ? b.? 仅 i 、 ⅱ 、 ⅲ? ? ?c.? 仅 ⅱ 、 ⅲ 、 iv? ? d.? 仅 i 、 ⅲ 、 ⅳ
18.? ? ?在采用 “ 取指、译码 / 取数、执行、访存、写回 ”5 段流水线的处理器中,执行如下指令序列,其中 s0 、 s1 、 s2 、 s3 和 t2 表示寄存器编号。
i1 : add s2 , s1 , s0 //r[s2] ← r[s1]+r[s0]
i2 : load s3 , 0 ( t2 )? ? //r[s3] ← m[r[t2]+0]
i3 : add s2 , s2 s3 //r[s2] ← r[s2]+r[s3]
i4 : store s2 , 0 ( t 2 )? ? ? ?//m[r[t2]+0] ← r[s2]
下列指令对中,不存在数据冒险的是
a.? i1 和 i3? ? ? ? ? b.? i2 和 i3? ? ? c.? i2 和 i4? ? ? d.? i3 和 i4
19.? ? ?假定一台计算机采用 3 通道存储器总线,配套的内存条型号为 ddr3-1333 ,即内存条所接插的存储器总线的工作频率为 1333? ?mhz 、总线宽度为 64 位,则存储器总线的总带宽大约是
a. 10.? ?66 gb/s? ? ? b.? 32 gb/s? ? ? c.? 64 gb/s? ? ? d.? 96 gb/s
20.? ? ?下列关于磁盘存储器的叙述中,错误的是
a.? 磁盘的格式化容量比非格式化容量小
b.? 扇区中包含数据、地址和校验等信息
c.? 磁盘存储器的最小读写单位为一个字节
d.? 磁盘存储器由磁盘控制器、磁盘驱动器和盘片组成
21 .? ? 某设备以中断方式与 cpu 进行数据交换, cpu 主频为 1 ghz ,设备接口中的数据缓冲寄存器为 32 位,设备的数据传输率为 50kb/s 。若每次中断开销 ( 包括中断响应和中断处理 ) 为 1000 个时钟周期, 则 cpu 用于该设备输入 / 输出的时间占整个 cpu 时间的百分比最多是
a.? 1. 25%? ? ? ? ? ? ?b.? 2. 5%? ? ? ? ?c.? 5%? ? ? ? ?d.? 12.? 5%
22 .? ? 下列关于 dma 方式的叙述中,正确的是
i .? dma 传送前由设备驱动程序设置传送参数
i i . 数据传送前由 dma 控制器请求总线使用权
ⅲ. 数据传送由 dma 控制器直接控制总线完成
i v .dma 传送结束后的处理由中断服务程序完成
a.? 仅 i 、 ⅱ? ? ? ? ?b.? 仅 ⅰ 、 ⅲ 、 ⅳ? ? ?c.? 仅 ⅱ 、 ⅲ 、 i v? ? ?d.? i 、 ⅱ 、 ⅲ 、 i v
23 .? ? 下列关于线程的描述中,错误的是
a.? 内核级线程的调度由操作系统完成
b.? 操作系统为每个用户级线程建立一个线程控制块
c.? 用户级线程间的切换比内核级线程间的切换效率高
d.? 用户级线程可以在不支持内核级线程的操作系统上实现
24.? ? ?下列选项中,可能将进程唤醒的事件是
i.? ?i/ o 结束? ? ? ? ? ? ?ⅱ.? ?某进程退出临界区? ? ? ? ?ⅲ .? ?当前进程的时间片用完
a.? 仅 i? ? ? ? ? ?b.? 仅 ⅲ? ? ? ? ? ?c.? 仅 i 、 ⅱ? ? ? ?d.? i 、 ⅱ 、 ⅲ
25.? ? ?下列关于系统调用的叙述中,正确的是
i. 在执行系统调用服务程序的过程中, cpu 处于内核态
ⅱ. 操作系统通过提供系统调用避免用户程序直接访问外设
ⅲ. 不同的操作系统为应用程序提供了统一的系统调用接口
i v . 系统调用是操作系统内核为应用程序提供服务的接口
a.? 仅 i 、 iv? ? ? ? b .? 仅 ii 、 iii? ? ? ? ?c.? 仅 i 、 ⅱ 、 iv? ? ?d.? 仅 i 、 ⅲ 、 ⅳ
26.? ? ?下列选项中,可用于文件系统管理空闲磁盘块的数据结构是
i. 位图? ? ? ? ?ⅱ. 索引节点? ? ? ?ⅲ . 空闲磁盘块链? ? ?ⅳ. 文件分配表 ( fat )
a.? 仅 i 、 ⅱ? ? ? ? ?b.? 仅 ⅰ 、 ⅲ 、 ⅳ? ? ? ?c.? 仅 l 、 ⅲ? d.? 仅 ⅱ 、 ⅲ 、 ⅳ
27.? ? ?系统采用二级反馈队列调度算法进行进程调度。就绪队列 q1 采用时间片轮转调度算法,时间片为 10ms ;就绪队列 q2 采用短进程优先调度算法;系统优先调度 q1 队列中的进程,当 q1 为空时系统才会调度 q2 中的进程;新创建的进程首先进入 q1 ; q1 中的进程执行一个时间片后,若未结束,则转入 q2 。若当前 q1 、 q2 为空,系统依次创建进程 pl 、 p2 后即开始进程调度 pl 、 p2 需要的 cpu 时间分别为 30ms 和 20ms ,则进程 p1 、 p2 在系统中的平均等待时间为
a.? 25 ms? ? ? ? b.? 20 ms? ? ? ? c.? 15 ms? ? ? d.? 10 ms
28.? ? ?在分段存储管理系统中,用共享段表描述所有被共享的段。若进程 p1 和 p2 共享段 s ,下列叙述中,错误的是
a.? 在物理内存中仅保存一份段 s 的内容
b.? 段 s 在 p1 和 p2 中应该具有相同的段号
c.? p1 和 p2 共享段 s 在共享段表中的段表项
d.? p1 和 p2 都不再使用段 s 时才回收段 s 所占的内存空间
29.? ? ?某系统采用 lru 页置换算法和局部置换策略,若系统为进程 p 预分配了 4 个页框,进程 p 访问页号的序列为 0 , 1 , 2 , 7 , 0 , 5 , 3 , 5 , 0 , 2 , 7 , 6 ,则进程访问上述页的过程中,产生页置换的总次数是
a.? 3? ? ? ? ? ? b.? 4? ? ? ? ? ? c.? 5? ? ? ? ? d.? 6
30.? ? ?下列关于死锁的叙述中,正确的是
i .? ?可以通过剥夺进程资源解除死锁
i i .? ?死锁的预防方法能确保系统不发生死锁
i ii .? ?银行家算法可以判断系统是否处于死锁状态
ⅳ.? ?当系统出现死锁时,必然有两个或两个以上的进程处于阻塞态
a.? 仅 ii 、 ⅲ? ? ? ? b.? 仅 i 、 ⅱ 、 ⅳ? ? ? ?c.? 仅 i 、 ⅱ 、 ⅲ? ? d.? 仅 i 、 ⅲ 、 ⅳ
31 .? ? 某计算机主存按字节编址,采用二级分页存储管理,地址结构如下所示
页目录号 ( 10 位 )? ? ?页号 ( 10 位 )? ? ?页内偏移 ( 12 位 )
虚拟地址 2050? ?1225h 对应的页目录号、页号分别是
a.? 081h 、 101h? ? ? ?b.? 081h 、 401h? ? ? ? ?c.? 201h 、 101h? ? ?d.? 201h 、 401h
32 .? ? 在下列动态分区分配算法中,最容易产生内存碎片的是
a.? 首次适应算法? ? ? ? ?b.? 最坏适应算法? ? ? ? ?c.? 最佳适应算法? ? ? ?d.? 循环首次适应算法
33 .? ? osi 参考模型的第 5 层 ( 自下而上 ) 完成的主要功能是
a.? 差错控制? ? ? ? ?b.? 路由选择? ? ? ? ?c.? 会话管理? ? ? ?d.? 数据表示转换
34.? ? ?100baset 快速以太网使用的导向传输介质是
a.? 双绞线? ? ? ? ?b.? 单模光纤? ? ? ? ?c.? 多模光纤? ? ? ?d.? 同轴电缆
35.? ? ?对于滑动窗口协议,如果分组序号采用 3 比特编号,发送窗口大小为 5 ,则接收窗口最大是
a.? 2? ? ? ? ? ? ?b.? 3? ? ? ? ? ? ?c.? 4? ? ? ? ? ?d.? 5
36.? ? ?假设一个采用 csma/cd 协议的 100mbps 局域网,最小帧长是 128? ?b ,则在一个冲突域内两个站点之间的单向传播延时最多是
a.? 2. 56? μ s? ? ? ? ? ?b.? 5. 12? μ s? ? ? ? ? ? ?c.? 10. 24? μ s? ? ? ? ?d.? 20. 48? μ s
37.? ? ?若将 1 01.? ?2 00.? ?16.? ?0/20 划分为 5 个子网,则可能的最小子网的可分配 ip 地址数是
a.? 126? ? ? ? ? ?b.? 254? ? ? ? ? ?c.? 510? ? ? ? ?d.? 1022
?38.? ? ?某客户通过一个 tcp 连接向服务器发送数据的部分过程如题 38 图所示 。 客户在 t 0 时刻第一次收到确认序列号 ack_seq= 1 00 的段,并发送序列号 seq=100 的段,但发生丢失。若 tcp 支持快速重传,则客户重新发送 seq=100 段的时刻是
a.? t 1? ? ? ? ?b.? t 2? ? ? ? ?c.? t 3? ? ? ?d.? t 4
39.? ? ?若主机甲主动发起一个与主机乙的 tcp 连接,甲、乙选择的初始序列号分别为 2018 和 2046 ,则第三次握手 tcp 段的确认序列号是
a.? 2018? ? ? ?b.? 2019? ? ? ?c.? 2046? ? ?d.? 2047
40.? ? ?下列关于网络应用模型的叙述中,错误的是
a.? 在 p2p 模型中,结点之间具有对等关系
b.? 在客户 / 服务器 ( c/s ) 模型中,客户与客户之间可以直接通信
c.? 在 c/s 模型中,主动发起通信的是客户,被动通信的是服务器
d.? 在向多用户分发一个文件时, p2p 模型通常比 c/s 模型所需时间短
二、综合应用题: 41~47 小题,共 70 分。
41.? ?( 13 分 ) 设线性表 l= ( a1 , a2 , a… , an-2 , a-1 , a 。 ) 采用带头结点的单链表保存,链表中结点定义如下:
typedef struct node? {
int data ;
struct node*? ?next ;
}? node ;
请设计一个空间复杂度为 o ( 1 ) 且时间上尽可能高效的算法,重新排列 l 中的各结点,得到线性表 l= ( a 1 , a n , a 2 , a n-1 , a 3 , a n-2 … ) 。
要求:
( 1 )? ?给出算法的基本设计思想
( 2 )? ?根据设计思想,采用 c 或 c++ 语言描述算法,关键之处给出注释。
( 3 )? ?说明你所设计的算法的时间复杂度。
42.? ?( 10 分 ) 请设计一个队列,要求满足: ① 初始时队列为空; ② 入队时,允许增加队列占用空间; ③ 出队后,出队元素所占用的空间可重复使用,即整个队列所占用的空间只增不减; ④ 人队操作和出队操作的时间复杂度始终保持为 o ( 1 ) 。请回答下列问题:
( 1 )? ?该队列应该选择链式存储结构,还是顺序存储结构?
( 2 )? ?画出队列的初始状态,并给出判断队空和队满的条件
( 3 )? ?画出第一个元素 入 队后的队列状态。
( 4 )? ?给出入队操作和出队操作的基本过程。
43.? ?( 8 分 ) 有 n ( n≥3 ) 位哲学家围坐在一张圆桌边,每位哲学家交替地就餐和思考。在圆桌中心有 m ( m≥1 ) 个碗,每两位哲学家之间有 1 根筷子。每位哲学家必须取到一个碗和两侧的筷子之后,才能就餐,进餐完毕,将碗和筷子放回原位,并继续思考。为使尽可能多的哲学家同时就餐,且防止出现死锁现象,请使用信号量的 p 、 v 操作 ( wait () 、 signal () 操作 ) 描述上述过程中的互斥与同步,并说明所用信号量及初值的含义。
44.? ?( 7 分 ) 某计算机系统中的磁盘有 300 个柱面,每个柱面有 10 个磁道,每个磁道有 200 个扇区,扇区大小为 512b 。文件系统的每个簇包含 2 个扇区。请回答下列问题:
( 1 )? ?磁盘的容量是多少?
( 2 )? ?假设磁头在 85 号柱面上,此时有 4 个磁盘访问请求,簇号分别为: 100260 、 60005 、 101660 和 110560 。若采用最短寻道时间优先 ( sstf ) 调度算法,则系统访问簇的先后次序是什么?
( 3 )? ?第 100530 簇在磁盘上的物理地址是什么?将簇号转换成磁盘物理地址的过程是由 i/o 系统的什么程序完成的?
45.? ?( 16 分 ) 已知 f ( n ) =n ! =n × ( n-l ) × ( n-2 ) × … × 2×1 ,计算 f ( n ) 的 c 语言函数 fl 的源程序 ( 阴影部分 ) 及其在 32 位计算机 m 上的部 分机器级代码如下:
??
?
其中,机器级代码行包括行号、虚拟地址、机器指令和汇编指令,计算机 m 按字节编址, int 型数据占 32 位。请回答下列问题:
( 1 )? ?计算 f ( 10 ) 需要调用函数 f 1 多少次?执行哪条指令会递归调用 f 1 ?
( 2 )? ?上述代码中,哪条指令是条件转移指令?哪几条指令一定会使程序跳转执行?
( 3 )? ?根据第 16 行 call 指令,第 17 行指令的虚拟地址应是多少?已 知第 16 行 call 指令采用相对寻址方式,该指令中的偏移量应是多少 ( 给出计算过程 ) ?已知第 16 行 call 指令的后 4 字节为偏移量, m 采用大端还是小端方式?
( 4 )? ?f ( 13 ) =6? ?227? ?020? ?800 ,但 f 1 ( 13 ) 的返回值为 1? ?932? ?053? ?504 ,为什么两者不相等?要使 f1 ( 13 ) 能返回正确的结果,应如何修改 f 1 源程序?
( 5 )? ?第 19 行 im ul eax,ecx 表示有符号数乘法,乘数为 r [eax] 和 r[ecx] ,当乘法器输出的高、低 32 位乘积之间满足什么条件时,溢出标志 of=1 ?要使 cpu 在发生溢出时转异常处理,编译器应在 imul 指令后加一条什么指令?
46.? ?( 7 分 ) 对于题 45 ,若计算机 m 的主存地址为 32 位,采用分页存储管理方式,页大小为 4kb ,则第 1 行 push 指令和第 30 行 ret 指令是否在同一页中 ( 说明理由 ) ?若指令 cache 有 64 行,采用 4 路组相联映射方式,主存块大小为 64b ,则 32 位主存地址中,哪几位表示块内地址?哪儿位表示 cache 组号?哪几位表示标记 ( tag ) 信息?读取第 16 行 call 指令时,只可能在指令 cache 的哪一组中命中 ( 说明理由 ) ?
47.? ?( 9 分 ) 某网络拓扑如题 47 图所示,其中 r 为路由器,主机 h1~h4 的 ip 地址配置以及 r 的各接口 ip 地址配置如图中所示。现有若干台以太网交换机 ( 无 vlan 功能 ) 和路由器两类网络互连设备可供选择。
请回答下列问题:
( 1 )? ?设备 1 、设备 2 和设备 3 分别应选择什么类型网络设备?
( 2 )? ?设备 1 、设备 2 和设备 3 中,哪几个设备的接口需要配置 ip 地址?并为对应的接口配置正确的 ip 地址。
( 3 )? ?为确保主机 h1~h4 能够访问 internet , r 需要提供什么服务?
( 4 )? ?若主机 h3 发送一个目的地址为 192.168.1.127 的 ip 数据报,网络中哪几个主机会接收该数据报?

2019 年全国硕士研究生招生考试
计算机科学与技术学科联考
计算机学科专业基础综合试题参考答案

一、单项选择题
1.b? ? ?2.b? ? ?3.c? ? ?4.a? ? ?5.c
6.a? ? ?7.d? ? ?8.c? ? ?9.b? ? ?10.d
11.b? ? ?12.c? ? ?13.a? ? ?14.d? ? ?15.d
16.d? ? ?17.b? ? ?18.c? ? ?19.b? ? ?20.c
21.a? ? ?22.d? ? ?23.b? ? ?24.c? ? ?25.c
26.b? ? ?27.c? ? ?28.b? ? ?29.c? ? ?30.b
31.a? ? ?32.c? ? ?33.c? ? ?34.a? ? ?35.b
36.b? ? ?37.b? ? ?38.c? ? ?39.d? ? ?40.b
二、综合应用题
41. 【答案要点】
( 1 ) 算法的基本设计思想:
算法分 3 步完成。第 1 步,采用两个指针交替前行,找到单链表的中间结点;第 2 步,将单链表的后半段结点原地逆置;第 3 步,从单链表前后两段中依次各取一个结点,按要求重排。
( 2 ) 算法实现:
?
?
?
( 3 ) 算法的时间复杂度:
参考答案的时间复杂度为 o ( n ) 。
4 2 .? ?【答案要点】
( 1 ) 采用链式存储结构 ( 两段式单向循环链表 ) ,队头指针为 front ,队尾指针为 rear 。
( 2 ) 初始时,创建只有一个空闲结点的两段式单向循环链表,头指针 front 与尾指针 rear 均指向空闲结点。如下图所示。
?
队空的判定条件: front==rear 。
队满的判定条件: front==rear->next 。
( 3 ) 插 入 第一个元素后的队列状态:
?
( 4 ) 操作的基本过程:
?
4 3 .? ?【答案要点】
/ / 信号量
semaphore bowl ; // 用于协调哲学家对碗的使用
semaphore chopsticks[n] ; // 用于协调哲学家对筷子的使用
for ( int i=0 ; i<n ; i++ )
chopstick s[ i].value=1 ; // 设置两个哲学家之间筷子的数量
bowl.value=min ( n-1 , m ) ; //bowl.value ≤ n-1 ,确保不死锁
cobegin?
while ( true ) {? ?/ / 哲学家 i 的程序
思考;
p ( bowl ) ; / / 取碗
p ( chopsti c ks[i] ) ; / / 取左边筷子
p ( chopsticks[ ( i+l ) mod? ?n] ) ; // 取右边筷子
就餐;
v ( chopstic k s[i] ) ;
v ( chopsticks[ ( i+1 ) mod? ?n] ) ;
v ( bowl ) ;
?}
coend
44. 【答案要点】
( 1 ) 磁盘容量 = ( 300×10×200×512/1024 ) kb=3×10 5? ?k
b
( 2 ) 依次访问的簇是 100 260 、 101 660 、 110 560 、 60 005 。
( 3 ) 第 100 530 簇在磁盘上的物理地址由其所在的柱面号、磁头号、扇区号构成
其所在的柱面号为 ? 100530/ ( 10×200/2 ) ? =100 。
100530% ( 10×200/2 ) =530 ,磁头号为 ? 530/ ( 200/2 ) ? =5 。
扇区号为 ( 530×2 ) %200=60 。
将簇号转换成磁盘物理地址的过程由磁盘驱动程序完成。
45. 【答案要点】
( 1 ) 计算 f ( l0 ) 需要调用函数 f1 共 10 次执行第 16 行 call? 指令会递归调用 f1 。
( 2 ) 第 12 行 jle 指令是条件转移指令。第 16 行 call 指令、第 20 行 jmp 指令、第 30 行 ret 指令一定会使程序跳转执行。
( 3 ) 第 16 行 call 指令的下一条指令的地址为 0040 1
2019年计算机考研408真题 – 哔哩哔哩(2019年计算机二级考试真题及答案)插图
025h+5=0040 102ah ,故第 17 行指令的虚拟地址是 0040 102ah 。 call 指令采用相对寻址方式,即目标地址 = ( pc ) + 偏移量, call 指令的目标地址为 0040 1000h ,所以偏移量 = 目标地址 – ( pc ) =00401000h-0040 102ah=ffff ffd6h 。 根据第 16 行 call 指令的偏移量字段为 d6 ff ff ff ,可确定 m 采用小端方式。
( 4 ) 因为 f ( 13 ) =6? ?227? ?020? ?800 ,大于 32 位 int 型数据可表示的最大值,因而 f 1 ( 13 ) 的返回值是一个发生了溢出的结果。
为使 f 1 ( 13 ) 能返可正确结果,可将函数 f 1 的返回值类型改为 double ( 或 long long 或 long double 或 float ) 。
( 5 ) 若乘积的高 33 位为非全 0 或非全 l ,则 of=1
编译器应该在 imul 指令后加一条 “ 溢出自陷指令 ” ,使得 cpu 自动查询溢出标志 of ,当 of=1 时调出 “ 溢出异常处理程序 ” 。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

|京ICP备18012533号-370