logo资料库

408专业课2019年 无水印版本.pdf

发布时间：2022-06-05 发布人：admin 分类：说明书 资料大小：1.76M 资料格式：pdf 举报 版权申诉
第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
资料共9页，剩余部分请下载后查看
    组合 1
    Scan0001
    Scan0002
    Scan0003
    Scan0004
    Scan0005
    Scan0006
    Scan0007
    Scan0007
    Scan0008
    Scan0009
    2019年全同硕士研究生招生考试 计算机科学与技术学科联考 计算机学科专业基础综介试题 吧项选择题：1～ 40小题， 每小腿 2分， 共 80分。 F列 每题输出的四个�项巾， 只,fj一 个选项符介i.i:t题要求。 I.设凡是描述问题规模的�七负整数，下列程序段的时间组杂度 是 X = O; while ( n >= (x+l) * (x+l) ) X = x+ { j A.0 ( log n) D.0 ( n 2 ) 2.若 将 一 棵树 T转化为对应的二叉树 BT，则下列对 BT的遍历巾，其 B.0 ( n 112 ) C.0 ( n) 遍历序列与T的后根遍历序列相同的是 A.先序遍历 B.中序遍历 C.后序遍历 D.按层遍历 3.对 n个互 不相同的符号进行阶犬虽编码。 若生成的哈夫曼树共有 115个结点，则 n的值 是 A.56 B.57 C. 58 D.60 4.在任意 一 棵iF？：平衡二叉树（AVL树）Ti中，删除某结点u之后形成 平衡二叉树T z，再将u插入T z形成平衡二叉树T ］。 下列关于T i与 飞的叙述中，正确的是 I .若u是 Ti的叶结点，则Ti与T ］可能不相同 II .若u不是Ti的叶结点 ，则Ti与T 3 田．若v 不是T i的叶结点，则T i与T ］ A.仅 I － 定不相同 一 定相同 C 仅 I , II D.仅 I、田 B.仅 H 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.选 择一个排序算法时，除算法的时 空效率外，下列队l亲巾，压芮要考 虑 的 是 I .数据的规樵 皿.n法的稳定性 A.仅皿 C.仅E TV 皿 II .数据的在储方式 IV.数据的初始状态 B.仅I、H D.1 H W 皿 、 、 、 8.现有｜乏度为ll且初始为空的散列在H T， 散列的数是 H (key)= key 、 、 %7，采用线性探街（线忡，探测再散列）法解决冲突 将关键字序列 87 , 40 , 30 , 6 , II , 22，饵，20依次插入到HT后， HT 奇找失败的平均冕 战长度是 A. 4 D. 6.29 ”，采用 KMP"J+法 进行 模式匹 配，到匹配成 功111为止，在匹配过程中进行的单个于符 间的比较次数是 A.9 ”，模式 申 S＝“ abaabaal】ca 8. 5.25 C. 6 abaabc B. 10 D. 15 C. 12 baa be 9.设主申 T＝“ 10.排厅，过秤，巾，对尚未确定最终位置的所有元东进行 一 遍处理称为 一“跑”。下列序列巾，不11J能是快速排印第二趟结果的是 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 门．设外存立有 120个初始归并段 ，进行 12路H l并时，为实现最 佳归 井，简要补充的虚段个数是 A.I D.4 12.下列关于冯·诺依曼结构计算机基本思想的叙述中，错误的是 B. 2 C.3 A.程序 的功能都通过中央处理器执行指令 实现 B.指令和 数据部用二迸制表示， 形式 上无差别 C.指令按地址访问， 数据都在指令中直接给出 D.程序执行前，指令和 数据'J;j预先存放在在储器中 13.考虑以下 C 语言代码 ： short usi = 65535; unsigned short si = usi; 执行上述 程序段后，si的值是 A. -I B. -32767 C. -32768 D. -65535 14.下列关于缺页处用的叙述巾，错误的是 A.缺页是在地.bl：转换时CPU检测到的－种异常 B.缺贞处理由操作 系统提供的缺页处理程序米完成 C.缺页处理程序根据页故障地址从外仔读入所 缺失的页 D.缺贞处理完成后l叶剑发生缺贞 的指令 的下一条指令执行 15.某计算机采用大端方式，战？节编址。 某指令中操作数的 机器 数 为 1234FFOOH，眩操作数采 用基址寻址方式， 形式 地址（用补码占 尽）为 FFl2H， 基址寄存器 内容 为 FOOOOOOOH，则该操作数的 LSB （扯低有效宁节）所在的地址是 A. FOOO FFl2H C. EFFF FF12H B. FOOO FF15日 D. EFFF FFl5H 16.下列有关处理器 时钟脉冲的号 的叙述中，错误的是 A. n,J钟脉冲信号 111机器 脉冲源发出的脉冲信号经整形 和 分频后 形成 B.时钟 脉冲信号 的宽度称为时 钟周期，M钟周期 的倒数为机器 主频 C. Hf钟周 期以相邻状态单元间组合逻辑rl!路的故大延迟为基准
    确定 D.处理器总 是在每来一个时 钟脉冲信号时就开始执行 一 条新的 指令 17.某指令功能为 R[r2］←R[rl]+M[R[rO］］，其两个源操作数分别采 用寄存器、寄存器间接寻址方式 。 对于下列给定部件，该指 令在取 数及执行过程中需要用到的是 I .通用寄再器组（ GPRs) 皿 ．存储器 （Memory) A.仅I、E C.仅E、皿、W Il.算术逻辑单元（ ALU) N.指令译码器（ JD) B.仅l, TT、田 D仅I、田、W 18.在采用 “取指、译码／取数、执行 、访在、写回”5段流水 线的处 理器 中，执行如下指令序列 ，其中sO、sl、s2、s3和 t2-1曼示寄再器编号。 IL: adds2,sl,s0 12 : load s3 , 0 ( t2) I3 : add s2 , s2 s3 14: store s2, 0( L2) 下列指令对中，不存在数据冒险的是 A.II和 I3 //R[s2］←R [ s I ] + R [ sO ] I I R [ s3 ］←M[ R[ t2] + 0] / I R[ s2］←R [ s2] + R [ s3 ] I I M [ R [ t2 ] + 0 ］←R[ s2] C.12和 14 D.I3和 14 B.12和 I3 19.假定一台计算机采 用3通道存 储器总 线，配套的内存条型号为 DDR3-l333，即内存条所 接插的 存储器 总线的 工作频率为 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主频为 IGHz，设备 接口中的数据缓冲寄存器为 32位，设备的数据传 输率为 50kB/s。 若每次中断开销 （包括中断响应 和中断处理）为 l000个时钟周期， 则 CPU用于该设备输入／输出的时间占整个 CPU时间的百分比最 多是 A.1.25% B.2.5% C.5% D.12.5% 22.下列关于 DMA方式的叙述中，正确的是 I DMA传送前由 设备驱动程序设置传送参数 1数据传送前由 DMA控制器请求总线使用权 m.数据传送由 DMA控制器直接控制总线完成 N. DMA传送结束后的处理由中断服务程序完成 A.仅I、H C.仅E、皿、W B.仅I 、E 、W D. I、E、E、W 23.下列关于线程的描述中，错误的是 A.内核级线程的调度由操作系统完成 B.操作系统为每个用户级线程建立一个线 程控制 块 C.用户级线程间的切换比内核级线程间的切换效率高 D.用户级线程可以在不支持内核级线程的操作系统上实现 C.仅I、E D. I、E、E B.仅E 24.下列选项中，可能将进程唤醒的事件是 25.下列关于系统调用的叙述中，正确的是 I.110结束 n.某进程退出临界区 皿 ．当前进程的时间片用完 A.仅I I .在执行系统调用服务程序的过程中， CPU处于内核态 n.操作系统通过提供系统调用避免用户程序直接访问外设 皿．不同的操作系统为应用程序提供了统一的系统调用接口 N.系统调用是操作 系统内核为应用程序提供服务的接口 A.仅I、W C 仅I、E、W I.位图 皿 ．空闲磁盘块链 A.仅 I、E B.仅E、E D.仅I、皿、W 26.下列选项中，可用于文件系统管理空闲磁盘块的数据结构是 n.索引节点 N.文件分 配表（FAT) B.仅I 、E 、W
    C.仅 I、皿 D仅 E、田、W 27.系统采用二级反馈队列 调度算法进 行进程调 度。 就绪队列 QI采 用时间片轮转调度算法，时间片为 10ms；就绪队列 Q2采用短进程 优先调度算法；系统优先调度 QI队列 中的进程，当 Ql为空时系统 才会调度 Q2中的进程；新创建的进程首先 进入 Ql; Ql中的进程 执行 一 个时间片后，若未结束，则转入 Q2。 若：当前。 l、Q2为空，系 统依次创建进程 Pl、P2后’即开始 进程调度 Pl、四百要 的 CPU时 间分别 为 30ms和 20ms，则进程Pl、P2在系 统中的平均等待时 间为 A.25 ms C.15 ms B.20 ms D.10 ms 28.在分段再储 管理系统中，用共学段在描述所有被共字 的段。 丰午进 程 Pl和 P2共字段 S，下列叙述1p，错误的是 A.在物理内存中 仅 保在一份段S的内容 B.段 S在 Pl和 P2rj1应该具有相同的段号 C.Pl J和 P2共享段 S在共字段友小的段丘项 D.Pl和 P2都不再使 用段 SJlf才 i口l收段 S所山的内行空间 29.某系统采用 LRU页页换 n法和 局部lm换策略，拧系统为迸程P 1�！ 分配了 4个页框，进程 P访问页号的 rr-列为 0,1,2,7,0,5,3,5,0, 2,7,6，则进程访问上述页的过程中，产生Jj{.'i1换的总次数是 A.3 B. 4 C.5 D.6 30.下夕lj关于死锁的叙述巾，正确的是 I . i可以边过剥夺进程资源解除死锁 I].夕E锁的预防方法能确 保系统不友生死锁 皿．银行家算法可以判断系统是否处于死锁状态 N.、可系统出现死锁时，必然有两个旦旦两个以 i二的迸程处于fl[l束态 A.仅H、皿 C.仅 I、H、皿 B.仅 I、H、W D.仅 I、皿、W 3 1.某计算机主仔按宁节编址，采用二级分贞在储管理，地址结构如下 所示 JJi:I I求＼）·( IO f,'i.) 到1号（IOfiL) JJ£内偏移（12位） 应拟 地址 20501225H对州的贞口录号、反号分 别是 A.081 H、101H C.201 H、l01 H B.081 H、401H D.201 H、40111 32.在下 列动态分区分配算法巾，直言容劫产生内在碎片的是 A.首次适应11=法 C.M H适应算法 B.最坏适j也算法 D.循 环芮次适！但1'}；法 33.OSI参考模咽的第5层（白下而t.）完成的主要功能是 J\. »铺控制 C.会iZ·管理 B.路Lli滥炸 D.数 据-Uift.转换 34.I OOBaseT快速以太网使用 的导向传输介质是 八．双 绞线 B.单悦光纤 C.多快Jt纤 D. f,d都[f电缆 35.对 于滑动窗口协议，如果分mrr-号采用 3比特编号，发送窗口大小 为5，则接收窗口届大是 A.2 B.3 C.4 D.5 36.假设 一 个 采用 CSMA/CD协议的 100Mhps局域网，段小帧 i乏足 128 B，则在一 个冲突域内两个站点之间的机 A.2.56 µs 37.行将 l01.200.16.0/20 B.5.12 µs 划分为 5个子网，则可能的最小 子网的可分 C.10.24 µsD.20.48 µs 1,1传播延时监多是 ， IYc IP地址数是 A.126 B.254 C.510 D.1022 38.；占有：尸通过 一 个 TCP连接向服务器发送数据的部分过程如题 38 图所示 客户在 lo时刻第一 次收到确认 rr:列号 ack_seq= I 00的段， 并发送序列号 seq=100的段，但发哇丢失。 .t:TCP支持快速重传， 则客户屯新发送 seq= 100段的时刻是 A.t1 C. t3 D. t4 RU 39.店主机可1主动发起 一 个与主机乙的 TCP连接，可1、乙选择的初始［f 2 列号分 别为 2018和 2046，则第二次握子 TCP段的确认序列号是 A.2018 D.2047 C.2046 B.2019 40.下列关于网络应用模型的叙述中，错误的是 A.在 P2P模型中，结点之间具有对等关系
    服务器 客户 � to !3 !4 时间 题38囱 B.在客户／服务器（C/S）模型巾，客户与客户之间可以直接通信 C.在C/S模型中，主动发起通信的是客户，被动通信的是服务器 0.在向多用户分发一个文件时，P2P模型通常比C/S模型所市时 间短 二、 综合应用题：“～47小题， 其70分。 41.( 13分）设线性表L = ( a1 ,a2，句，…，a.-2,an-I ,a n）采用带头结点的 单链表保存，链表中结点定义如下 ： struct node typedef I int data; struct node * next; I NODE; 谙设计一个空间复杂度为 O(I）且时间上尽可能高效的算法，E新 排列L中的各结点，得到线性表L ’＝ ( a1，气，鸟，a.-1，鸟，a.-2，…）。 要求： ( I ）给出算 法的基本 设计思想 ( 2）根据设计思想，采用C或C＋＋语言描述算法，关键之处 给 出 注释。 (3）说明你所设计的算法的时间复杂度。 42.( 10分)i.j设计一个队列，要求满足：①初始时队列为空；②入队时， 允许增加队列占用 空间；③出队后，出队元素所占用的宅｜时可重复 使用，即整个队列所占用的空间只增不减；④入队操 作和出队操作 的时间复杂度始终保持为 0(I）。请回答下列问题： ( 1 ）该队列应该选拇链式存储结构 ，近是顺序在储结构？ (2）画出队列的初始状态，并给出判断队空和l队满的条件 (3）刚出第一个元亲人队后的队列状态。 (4）给出入队操作和l出队操作的基本过程。 43.( 8分）有n(n注 3）位哲学家用坐在一张圆桌边，创位哲学家交替 地 就餐和l思考。在国桌中心有 m(m;;:,,I）个碗， 每两位哲学家之间有 l根筷子。每位哲学家必须取到一个碗和两侧的筷F之 餐，进餐完毕，将碗和l筷子放回原位，并继续思考。 为使尽可能多 的哲学家同时 就餐，且防止出现死锁现象，请使用信号茸的 P、V操 作（wait（）、signal（）操作）描述上述过程中 的互斥与向步，并说明 所用信号盐及初值的含义。 后，才能就 44.( 7分）某计算机系统中的磁盘有300个柱而，每个柱面有 10个磁 道，每个磁道有200个扇区 ，扇区大小为 512B。文件系统的每个 簇包含2个扇区。h'f回答下列问题： ( 1 ）磁盘的容业是多少？ ( 2）假设磁头在 85号桂面上，此时有4 个磁盘访问请求 ，簇号分别 为 ：100260 、60005、101660 和l 10 560。 若采用最短寻道时间 优先（SSTF）调度算法，则系统访问簇的先后次序是什么？ (3）第 100530簇在磁 盘上的物理 地址是什么？ 将簇号转换成磁 盘物理地址的过程是由I /0系统的什么程序完成的？ 45. ( 16分）己知 f( n ) = n ! = n x ( n -I ) X ( n - 2 ) x…x2xl ，计算J（川 的
    C语言函数门的源程序（阴影部分）及其在 32位计算机Mt的部 分机器级代码如下： int fl ( int n ) I 1 00401000 55 push ebp if( n>l) 11 00401018 83 7D 08 0 I cmp dword plr [ ebp+8] , I 12 0040101C 7E 17 jle f1+35h (00401035) return n * fl ( n-1 ) ; 13 0040101E 8B 45 08 14 00401021 83 E8 01 15 00401024 50 16 0040 I 025 E8 D6 FF FF FF mov e缸，dwordptr [ ebp+8] sub eax, l push eax call fl ( 0040 I 000) 19 00401030 OF AF Cl imul eax, ecx 20 00401033 EB 05 jmp fl+3Ah (0040103a) else return I ; 21 00401035 B8 01 00 00 00 mov eax, l 26 00401040 38 EC cmp ebp ,esp 30 0040104A C3 rel 其中，机器级代码行包插行号、虚拟地址、 机器指令和汇编指令，计 算机 M披字节编址，int型数据占 32位。 请回答下列问题： (1）计算 ！（10）荷要调用函数 fl多少次？ 执行哪条指令会递lj I调 用 fl? 知第 16行 call指令采用相对寻址方式 ，该指令中的偏移量应 是多少（给出计算过程 ）？已知第 16行 call指令的后 4字节 为 偏格茧，M 采用大端还是小端方式？ ( 4)f ( 13) = 6 227 020 800，但fl(l3）的返回值 为 l932 053 504，为 什么两者不相等？要使 f1(13）能返回正确的结果，应如何修 改门源程序？ ( 5） 第19行 1『Y R [ ecx］，吁乘法器输出的l二5 、低32位乘积之问满足什么条件 HJ，溢出标志OF= 1？要使 CPUJ巨友生溢出时转｝非常处理， 编译器应在 imul揣令后)Ju一条什么指令？ 46.(7分）对于题 45，若计算机M的主存地址为 32位，采用分页存储 管理方式，页大小为 4KB，则第l行 push指令和 第 30行 rel指令 是否在同 一 页中（说明理由）？行指令 Cache有 64行，采用 4路组 相联映射方式，主仔块大小为 64B，则32位主 存地址巾，哪几位表 示块内地址？哪儿位在示 Cache组号？哪几位表示标记（ lag）信 息？读取第 16行 call指令时，只可能在指令 Cache的哪 一 组中命 中（说明理由）？ 47. (9分）某网络拓扑如题 47图所示，只中 R为路由器 ，主机 H1～H4 的 IP地址配置以及R的各接 fl IP地址配置如图中所示。 现有若 F台以太网交换机（无VLAN功能）和路由器两类网络互连设备可 供选择。 请回答下列问题： ( l ）设备 l、设备2和设备 3分别应选择什么类型网络设备？ ( 2）设备l、设备2和设备 3巾，哪几个设备的接 口 需要配置 IP地 址？并为对应的接口配置正确的 IP地址。 (3） 为确保 主机 Hl～H4能够的 问 Internet,R需要 提供什么服务？ (4） 若主机 H3发送 一 个口 的地址为 192.168.1.127的 IP数据报， ( 2）上述代码 中，哪条指令是 条件转移指令？哪几条指令 一 定会 网络 中哪几个 主机会接收该数据报？ 使程序跳转执行？ (3）根据第 16行 call指令，第门行指令的虚拟地址应是多少？巳
    101.1.2.10 ‘…· !Fl IP地址·192.168.1.2/26 默认网关：192.168.1.1 IP地址：192.168.1.3/26 默认网关：192.168.1.1 备�14 年：设 IP地址：l 92.168.1.66/26 默认例关：192.168.1.65 IP地.l!f::192.168.1.67/26 默认闷关192.168.1.65 题47图 2019年全国硕士研究生招生考试 计算机科学与技术学科联考 计算机学科专业基础综合试题参考答案 单项选择题 2. B 7. D 12. C 17. B 22. D 27. C 32. C 37. B 3. C 8. C 13. A 18. C 23. B 28. B 33. C 38. C I. B 6. A 11. B 16. D 21. A 26. B 31. A 36. B －－、 综合应用题 41. ［答案要点］ ( 1 ）算法的基本设计思想： 4. A 9. B 14. D 19. B 24. C 29. C 34. A 39. D 5. C 10. D 15. D 20. C 25. C 30. B 35. B 40. B 算法分3步完成 第l步，采用两个指针交替前行，找到守主链 表的中间结点；第2步，将单链表的后半段结点原地逆置；第3 步，从单链表前后两段中依次各取一个结点，按要求重排。 (2）算法实现： void change_list( NODE * h ) NODE * p, * q, * r, * s; p = q = h; while ( q->next ! = NULL ) ／／寻找中间结点
    II p走一步 p = p->next; q = q->nexl; if ( q->next ! = NULL ) q = q ->next; I I q走阔步’ q二p->next;I I p所指 结点为巾问结点， q为后 、卡段链点 p->next = NULL; while ( q ! = NULL )II将 链在盯 、卡段逆 E I r = q->next; 的计结点 q->nrxt = p->next; p->next = q; q = r; [,!JJ插入点 一 个数如结点， 吕＝ h->next; II s指向前中段的第 q = p->next; II q指向后平段的第一个数据结点 p->next = NULL; while ( q ! = NULL ) ／／将 链在后、长段的结点插入 r = q->next; I I r指向后 、｜毛段的下一个结点 q->next = s->nexl; ／／将q所指结点插入到 s->next = q; s = q->next; II s指向前半段的下 一 个插入点 s所指 到指定位置 结点之后 ( I ）采用链式仔储结构（ 两段式单向循环链在） ，队头指针为 front, (2）初始时，创建只有 一 个空闲结点的两段式单向循环链表，头指 如1下图所示。 队尾指针为 rear 针f ront与 尾指针陀 ar均捐／oJ空 闲结点 二里二 队空的判定条件：f ront= = rear。 队满的判定条件：front= = rear->next。 ( 3）插入第二个元素后的队列状态： front = = rear->nexl) 则在 rear!Ci面恼人一个新的空闲结点； (4）操作的基本过程： 人队操作： {',: ( ／／队满 人队JGi号保存到 rear所指纣点小；rear= rear->next；返问 Ill队操作： 导干 ( front = = rear) ／／队空 则111队失败，返＇＂＇； J:lil front所指纺点巾的元才f e;front ；返回e。 = front->neλ1 q = r; ( 3）算法的时间复杂度： 参考答案的时间复杂度为0( 42.［答案要点］ n) 43.［答案要点］ ／／信号 iJ:semaphore bowl ; semapl阳echopsticks[ n ] ; for( inti= O; i
    分享到：
    赞 收藏

    相关推荐

    资料库

    考试认证

    共收录20637份资料，累计11个分类，关注成员有19位，主要包括：真题,美赛,软考,PMP,Linux/Unix认证,思科认证,微软认证,Oracle认证,华为认证,软考等考,其它

    热门标签

    真题 美赛 软考 PMP Linux/Unix认证 思科认证 微软认证 Oracle认证 华为认证 软考等考 其它

    最新资料