2017年计算机408统考考研真题及答案解析.pdf

返回 相似
第1页 / 共13页
第2页 / 共13页
第3页 / 共13页
第4页 / 共13页
第5页 / 共13页
点击查看更多>>
资源描述:
2017年全国硕士研究生招生考试 计算机科学与技术学科联考 计算机学科专业基础综合试题 一、单项选择题1~40小题,每小题2分,共80分。下列每题给出的四个选项中,只有一 个选项符合题目要求。 1.下列函数的时间复杂度是 int func int n { int i0, sum0; whilesumleft NULL root-right NULL //若为叶结点 printf“%s”,root-data; //输出操作数 else { ifdeep1 printf“”;//若有子表达式则加1层括号 BtreeToExproot-left,deep1; printf“%s”,root-data; //输出操作符 BtreeToExproot-right,deep1; ifdeep1 printf“”;//若有子表达式则加1层括号 } } 【评分说明】 ①若考生设计的算法满足题目的功能要求,则1、2根据所实现算法的策略及输出结果给 分,细则见下表。 分数 备注 15 采用中序遍历算法且正确,括号嵌套正确,层数适当。 14 采用中序遍历算法且正确,括号嵌套正确,但括号嵌套层数过多。例如,表达式 最外层加上括号,或操作数加括号如a。 11 采用中序遍历算法,但括号嵌套层数不完全正确。例如,左右括号数量不匹配。 9 采用中序遍历算法,但没有考虑括号。 ≤7 其他 ②若考生采用其他方法得到正确结果,可参照①的评分标准给分。 ③如果程序中使用了求结点深度等辅助函数,但没有给出相应的实现过程,只要考生进行 了必要的说明,可不扣分。 ④若在算法的基本设计思想描述中因文字表达没有清晰反映出算法思路,但在算法实现中 能够表达出算法思想且正确的,可参照①的标准给分。 ⑤若算法的基本设计思想描述或算法实现中部分正确,可参照①中各种情况的相应给分标 准酌情给分。 ⑥参考答案中只给出了使用C语言的版本,使用C语言的答案参照以上评分标准。 42.【答案要点】 1依次选出的边为 A,D,D,E,C,E,B,C4分 【评分说明】每正确选对一条边且次序正确,给1分。若考生选择的边正确,但次序不完全 正确,酌情给分。 2图G的MST是唯一的。2分 3当带权连通图的任意一个环中所包含的边的权值均不相同时,其MST是唯一的。2分 【评分说明】 ①若考生答案中给出的是其他充分条件,例如“带权连通图的所有边的权值均不相同”,同 样给分。 ②若考生给出的充分条件对图的顶点数和边数做了某些限制,例如,限制了图中顶点的个 数顶点个数少于3个、限制了图的形状图中没有环等,则最高给1分。 ③答案部分正确,酌情给分。 43.【答案要点】 1由于i和n是unsigned型,故“in-1”是无符号数比较,n0时,n-1的机器数为全1,值是2 32 -1, 为unsigned型可表示的最大数,条件“in-1”永真,因此出现死循环。2分 若i和n改为int类型,则不会出现死循环。1分 因为“in-1”是带符号整数比较,n0时,n-1的值是-1,当i0时条件“in-1”不成立,此时 退出for循环。1分 2f123与f223的返回值相等。1分 f123的机器数是OOFF FFFFH,1分 f223的机器数是4B7F FFFFH。1分 3当n24时,f241 1111 1111 1111 1111 1111 1111 B,而float型数只有24位有效位,舍入 后数值增大,所以f224比f124大1。1分 【评分说明】只要说明f224需舍入处理即可给分。 4显然f31已超出了int型数据的表示范围,用f131实现时得到的机器数为32个1,作为int 型数解释时其值为-1,即f131的返回值为-1。1分 因为int型最大可表示数是0后面加31个1,故使f1n的返回值与fn相等的最大n值是30。1 分 【评分说明】对于第二问,只要给出n30即可给分。 5IEEE 754标准用“阶码全1、尾数全0”表示无穷大。f2返回值为float型,机器数7F80 0000H 对应的值是∞。1分 当n126时,f1262 217 -11.112 126 ,对应阶码为127126253,尾数部分舍入后阶码加1, 最终阶码为254,是IEEE754单精度格式表示的最大阶码。故使f2结果不溢出的最大n值为126。 1分 当n23时,f23为24位1,float型数有24位有效位,所以不需舍入,结果精确。故使f2获得 精确结果的最大n值为23。 1分 【评分说明】对于第二问,只要给出n23,即可给分。对于第三问,只要给出n126,即可 给分。 44.【答案要点】 1M为CISC。1分 M的指令长短不一,不符合RISC指令系统特点。1分 2f1的机器代码占96 B。1分 因为f1的第一条指令“push ebp”所在的虚拟地址为00401020H,最后一条指令“ret”所在的虚 拟地址为0040 107FH,所以,f1的机器指令代码长度为0040 107FH-0040 1020H160H96个字 节。1分 3CF1。1分 cmp指令实现i与n-1的比较功能,进行的是减法运算。在执行f10过程中,n0,当i0时, i0000 0000H,并且n-1FFFF FFFFH。因此,当执行第20条指令时,在补码加/减运算器中执行 “0减FFFF FFFFH”的操作,即0000 0000H00000000H10000 0001H,此时,进位输出C0,减 法运算时的借位标志CFC 11。2分 4f2中不能用sh1指令实现power*2。1分 因为sh1指令用来将一个整数的所有有效数位作为一个整体左移;而f2中的变量power是float 型,其机器数中不包含最高有效数位,但包含了阶码部分,将其作为一个整体左移时并不能实 现“乘2”的功能,因而f2中不能用sh1指令实现power*2。2分 45.【答案要点】 1函数f1的代码段中所有指令的虚拟地址的高20位相同,因此f1的机器指令代码在同一页 中,仅占用1页。1分 2push ebp指令的虚拟地址的最高10位页目录号为00 00000001,中间10位页表索引为00 0000 0001,所以,取该指令时访问了页目录的第1个表项,1分在对应的页表中访问了第1个表 项。1分 3在执行scanf 的过程中,进程P因等待输入而从执行态变为阻塞态。1分输入结束时,P 被中断处理程序唤醒,变为就绪态。1分P被调度程序调度,变为运行态。1分CPU状态会从 用户态变为内核态。1分 46.【答案要点】 semaphore mutex_y11;//mutex_y1用于thread1与thread3对变量y的互斥访问。1分 semaphore mutex_y21;//mutex_y2用于thread2与thread3对变量y的互斥访问。1分 semaphore mutex_z1; //mutex_z用于变量z的互斥访问。1分互斥代码如下5分 thread1 { cnum w; waitmutex_y1; waddx,y; signalmutex_y1; } thread2 { cnum w waitmutex_y2 waitmutex_z; waddy,z; signalmutex_z; signalmutex_y2; } thread3 { cnum w; w.a1; w.b1; waitmutex_z; zaddz,w; signalmutex_z; waitmutex_y1; waitmutex_y2; yaddy,w; signalmutex_y1; signalmutex_y2; } 【评分说明】 ①各线程与变量之间的互斥、并发情况及相应评分见下表。 线程对 变量 thread1和thread2 thread2和thread3 thread1和thread3 给分 x 不共享 不共享 不共享 1分 y 同时读 读写互斥 读写互斥 3分 z 不共享 读写互斥 不共享 1分 ②若考生仅使用一个互斥信号量,互斥代码部分的得分最多给2分。 ③答案部分正确,酌情给分。 47.【答案要点】 1t 0 时刻到t 1 时刻期间,甲方可以断定乙方已正确接收了3个数据帧,1分分别是S0,0、 S1,0、S2,0。1分 2从t 1 时刻起,甲方最多还可以发送5个数据帧,1分其中第一个帧是S5,2,1分最后一 个数据帧是S1,2。1分 3甲方需要重发3个数据帧,1分重发的第一个帧是S2,3。1分 4甲方可以达到的最大信道利用率是 【评分说明】 答案部分正确,酌情给分。
展开阅读全文

copyright@ 2018-2019 考拉文库网站版权所有
经营许可证编号:陕ICP备18022950号-1