2017年计算机408统考真题解析.pdf

《2017年计算机408统考真题解析.pdf》由会员分享，可在线阅读，更多相关《2017年计算机408统考真题解析.pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2017年计算机学科专业基础综合试题参考答案一、单项选择题1.B 2.9.B 10.17.C 18.25.B 26.33.A 34.1.解析：sum+=+i;相当千廿i;sum=sum+i;。进行到第k趟循环，sum=(l+k)*k/2。显然需要进行O(n112)趟循环，因此这也是该函数的时间复杂度。2.解析：I的反例：计算斐波拉契数列迭代实现只需要一个循环即可实现。III的反例：入栈序列为1、2,进行如下操作PUSH、PUSH、POP、POP,出栈次序为2、1;进行如下操作PUSH、POP、PUSH、POP,出栈次序为1、2。IV,栈是一种受限的线性表，只允许在一端进行操作。因此II正确。3

2、.解析：三元组表的结点存储了行row、列col、值value三种信息，是主要用来存储稀疏矩阵的一种数据结构。十字链表将行单链表和列单链表结合起来存储稀疏矩阵。邻接矩阵空间复杂度达O(n2),不适千存储稀疏矩阵。二叉链表又名左孩子右兄弟表示法，可用千表示树或森林。因此A正确。4.解析：先序序列是先父结点，接着左子树，然后右子树。中序序列是先左子树，接着父结点，然后右子树，递归进行。如果所有非叶结点只有右子树，先序序列和中序序列都是先父结点，然后右子树，递归进行，因此B正确。5.解析：后序序列是先左子树，接着右子树，最后父结点，递归进行。根结点左子树的叶结点首先被访问，它是e。接下来是它的父结点a

3、,然后是a的父结点c。接着访问根结点的右子树。它的叶结点b首先被访问，然后是b的父结点d,再者是d的父结点g。最后是根结点f。因此d与a同层，B正确。CBBDD 3.11.19.27.35.4.12.20.28.36.5.13.21.29.37.6.14.22.30.38.7.15.23.31.39.AACBC BDDBA DABDC BCDBD BCDDA ADABB 8.16.24.32.40.6.解析：哈夫曼编码是前缀编码，各个编码的前缀各不相同，因此直接拿编码序列与哈夫曼编码一一比对即可。序列可分割为0100011 001 001 011 11 0101,译码结果是a fee f g

4、d,选项 D正确。7.解析：无向图边数的两倍等于各顶点度数的总和。由于其他顶点的度均小于3,可以设它们的度都为2,设它们的数量是X,可列出方程4x3+3x4+2x=16x2,解得x=3。4+3+3=11,B 正确。8.解析：折半查找判定树实际上 是一棵二叉排序树，它的中 序序列是一个有序序列。可以在树结点上依次填上相应的元素，符合折半查找规则的树即是所求。B选项 4、5相加除2向上取整，7、8相加除2向下取整，矛盾。C 选项，3、4相加除2向上取整，6、7相加除2向下取整，矛盾。D选项，I、10相加除2向下取整，6、7相加除2向上取整，矛盾。A符合折半查找规则，因此正确。A 6)B c 10

5、D2II 9.解析：B+树是应文件系统所需而产生的B-树的变形，前者比后者更加适用于实际应用中的操作系统的文件索引和数据库索引，因为前者磁盘读写代价更低，查询效率更加稳定。编译器中的词法分析使用有穷自动机和语法树。网络中的路由表快速查找主要靠高速缓存、路由表压缩技术和快速查找算法。系统一般使用空闲空间链表管理磁盘空闲块。所以B正确。10.解析：归并排序代码比选择插入排序更复杂，前者空间复杂度是O(n),后者是0(1)。但是前者时间复杂度是O(nlogn),后者是O(n2)。所以B正确。11.解析：插入排序、选择排序、起泡排序原本时间复杂度是O(n2),更换为链式存储 后的时间复杂度还是O(n2

6、)。希尔排序和堆排序都利用了顺序存储的随机访问特性，而链式存储不支持这种性质，所以时间复杂度会增加，因此选D。12.解析：运行时间指令数xCPI/主频。Ml的时间指令数x2/1.5,M2的时间指令数xl/1.2,两者之比为(2/1.5):(1/1.2)=1.6。故选C。13.解析：由4个DRAM芯片采用交叉编址方式构成主存可知主存地址最低二位表示该字节存储的芯片编号。double型变量占64位，8 个字节。它的主存地址804 001 AH最低二位是 10,说明 它从编号为 2 的 芯片开始存储（编号从0 开始）。一个存储周期可以对所有芯片各读取一个字节，因此需要 3轮，故选C。14.解析：时间

7、局部性是一旦一条指令被执行，则在不久的将来 它可能再次被执行。空间局部性是一旦一个存储单元被访问，那么它附近的存储单元也很快被访问。显然，这里的循环指令本身具有时间局部性，它对数组a的访问具有空间局部性，故选A。15.解析：在变址操作时，将计算机指令中的地址与变址寄存器中的地址相加，得到有效地址，指令提供数组首地址，由变址寄存器来定位数据中的各元素。所以它最适合按下标顺序访问一维数组元素，故选D。相对寻址以PC 为基地址，以指令中的地址为偏移量确定有效地址。寄存器寻址则是在指令中指出需要使用的寄存器。直接寻址是在指令的地址字段直接指出操作数的有效地址。16.解析：三地址指令有29条，所以它的操

8、作码至少为 5位。以 5位进行计算，它剩余32-29=3种操作码给二地址。而二地址另外多了6位给操作码，因此它的数量最大达3x64=192。所以指令字长最少为23位，因为计算机按字节编址，需要是8 的倍数，所以指令字长至少应该是24位，故选A。17.解析：超标量是 指在 CPU中有一条以上的流水线，并且每个时钟周期内可以完成一条以上的指令，其实质是以空间换时间。I错误，它不影响流水线功能段的处理时间；II、III正确。故选C。18.解析：主存储器就是我们通常说的主存，在CPU外，存储指令和数据，由RAM 和ROM 实现。控制存储器用来存放实现 指令系统的所有微指令，是一种只读型存储器，机器运行

9、时只读不写，在CPU的控制器内。cs按照微指令的地址访问，所以B错误。19.解析：五阶段流水线可分为取指(IF)、译码取数(I D)、执行(EXC)、存储器读(MEM)、写回(Write Back)。数字系统中，各个子系统通过数据总线连接形成的数据传送路径称为数据通路，包括程序计数器、算术逻辑运算部件、通用寄存器组、取指部件等，不包括控制部件，故选A。20.解析：多总线结构用速率高的总线连接高速设备用速率低的总线连接低速设备。一般来说，CPU是计算机的核心，是计算机中速度最快的设备之一，所以A正确。突发传送方式把多个数据单元作为一个独立传输处理，从而最大化设备的吞吐量。现实中一般用支待突发传送

10、方式的总线提高存储器的读写效率，B正确。各总线通过桥接器相连，后者起流量交换作用。PCI-Express总线都采用串行数据包传输数据，所以选D。21.解析：I/0端口又称I/0接口，是CPU与设备之间的交接面。由于主机和 I/0设备的工作方式和工作速度有很大差异，1/0端口就应运而生。在执行一条指令时，CPU使用地址总线 选择所请求的 I/0端口，使用数据总线在CPU寄存器和端口之间传输数据。所以选D。22.解析：多重中断系统在保护被中断进程现场时关中断，执行中断处理程序时开中断，B错误。CPU一般在一条指令执行结束的阶段采样 中断请求信号，查看是否存在中断请求，然后决定是否响应 中断，A、D

11、正确。中断请求一般来自CPU以外的事件，异常一般发生在 CPU内部，C正确。23.解析：先来先服务 调度算法是作业来得越早，优先级越高，因此会选择JI。短作业优先调度算法是作业运行时间越短，优先级越高，因此会选择J3。所以D正确。24.解析：执行 系统调用的过程是这样的：正在运行的进程先传递系统调用参数，然后由陷入(trap)指令负责将用户态转化为内核态，并将返回地址压入堆栈以备后用，接下来 CPU执行相应的内核态服务程 序，最后返回 用户态。所以C正确。25.解析：回收起始地址为 60K、大小为140KB的分区时，它与表中 第一个分区和第四个分区合并，成 为起始地址为20K、大小为380KB

12、的分区，剩余3个空闲分区。在回收内存后，算法 会对空闲分区链按分区大小由小到大进行 排序，表中的第二个分区排第一。所以选择B。26.解析：绝大多 数操作系统为改善磁盘访问时间，以簇为单位进行 空间分配，因此选D。27.解析：进程 切换带来系统开销，切换次数越多，开销越大，A正确。当前进程的时间片用完后，它的状态由执行态变为就绪态，B 错误。时钟中断是系统中特定的周期性时钟节拍。操作系统通过它来确定时间间隔，实现 时间的延时和任务的超时，C正确。现代操作系统为了保证性能最优，通常根据响应时间、系统开销、进程数量、进程运行时间、进程切换开销等因素确定 时间片大小，D正确。28.解析：多道程序系统通

13、过组织作业（编码或数据）使CPU总有一个作业可执行，从而提高了CPU的利用率、系统吞吐量和1/0设备利用率，I、III、IV是优点。但系统要付出额外的开销来组织作业和切换作业，II错误。所以选D。29.解析：一个新的磁盘是一个空白版，必须分成扇区以便磁盘控制器能读和写，这个过程称为低级格式化（或物理格式化）。低级格式化为磁盘的每个扇区采用特别的数据结构，包括校验码，III错误。为了使用 磁盘存储文件，操作系统还需要将其数据结构记录在磁盘上。这 分为两步。第一步是将磁盘 分为由一个或多个柱面组成的分区，每个分区可以作为一个独立的磁盘，I错误。在分区之后，第二步是逻辑格式化（创建文件系统）。在这一

14、步，操作系统将初始的文件系统数据结构存储到磁盘上。这些数据结构 包括空闲和已分配的空间和一个初始 为空的目录，II、IV正确。所以选B。30.解析：可以把用户访问权限抽象为一个矩阵，行代表用户，列代表访问权限。这个矩阵有4行 5列，1代表true,0代表false,所以需要20位，选D。31.解析：硬链接指通过索引结点进行连接。一个文件在物理存储器上有一个索引节点号。存在多个文件名指向同一个索引节点，II正确。两个进程各自维护自己的文件描述符，III正确，I错误。所以选择B。32.解析：在开始 DMA 传输时，主机向内存写入DMA命令块，向 DMA控制器写入该命令块的 地址，启动1/0设备。然

15、后，CP U继续其他工作，DMA控制器则继续下去直接操作内存总线，将地址放到总线上 开始传输。当整个传输完成后，DMA控制器中断CPU。因此执行顺序是2,3,l,4,选B。33.解析：OSI参考模型共7层，除去物理层和应用 层，剩五层。它们会向PD U引入20Bx5=lOOB的额外开销。应用层是最顶层，所以它 的数据传输效率为400B/500B=80%,选A。34.解析：可用奈奎斯特采样定理计算无噪声情况下的极限数据传输速率，用香农第二定理计算有噪信道极限数据传输速率。2叭og2N叭og2(1+SIN),W是信道带宽，N是信号状态数，SIN是信噪比，将数据代入计算可得N32,选D。分贝数=IO

16、log心IN。35.解析：IEEE 802.11 数据帧有四种子类型，分别是IBSS、FromAP、ToAP、WDS。这里的数据帧 F是从笔记本电脑发送往访问接入点CAP),所以属于ToAP子类型。这种帧地址l是RA(BSSID),地址 2是SA,地址 3是DA。RA是ReceiverAddress的缩写，BSSID是basic service set identifier 的缩写，SA是source address的缩写，DA是destination address的缩写。因此地址 l是AP的MAC,地址2是H的MAC,地址3是R的MAC,选B。36.解析：根据 RFC文档描述，0.0.0.

17、0/32 可以作为本主机在本网络上的源地址。127.0.0.1是回送地址，以它 为目的IP地址的数据将被立即返回到本机。200.10.10.3是C类IP地址。255.255.255.255是广播地址。37.解析：RIP是一种分布式的基于距离向量的路由选择协议，通过广播 U DP报文来交换路由信息。OSPF是一个内部网关协议，不使用 传输协议，如UDP或TCP,而是直接用IP包封装它的数据。BGP 是一个外部网关协议，用TCP封装它的数据。因此选D。38.解析：这个网络有16位的主机号，平均分成128个规模相同的子网，每个子网有7位的子网号，9位的主机号。除去一个网络地址和广播地址，可分配的最大

18、1P地址个数是29-2=512-2=510,故选C。39.解析：按照慢开始算法，发送窗口=min拥塞窗口，接收窗口，初始的拥塞窗口为最大报文段长度1KB海经过一个RTT,拥塞窗口翻倍，因此需至少经过5个RTT,发送窗口才能达到32KB,所以选A。这里假定乙能及时处理接收到的数据，空闲的接收缓存32KB。40.解析：FTP协议使用控制连接和数据连接，控制连接存在于整个FTP会话过程中，数据连接在每次文件传输时才建立，传输结束就关闭，A 和B是正确的。默认情况下 FTP协议使用TCP 20 端口进行 数据连接，TCP 21端口进行控制连接。但是 是否使用TCP 20端口建立数据连接与传输模式 有关

19、，主动方式使用TCP20端口，被动方式由服务器和客户端自行协商决定，C错，D对。所以选C。二、综合应用题41.解答：(I)算法的基本设计思想表达式树的中序序列加上必要的括号即为等价的中缀表达式。可以基于二叉树的中序遍历策略得到所需的表达式。(3分）表达式树中分支结点所对应的子表达式的计算次序，由该分支结点所处的位置决定。为得到正确的中缀表达式，需要在生成遍历序列的同时，在适当位置增加必要的括号。显然，表达式的最外层（对应根结点）及操作数（对应叶结点）不需要添加括号。(2分）(2)算法实现(IQ分）将二叉树的中序遍历递归算法稍加改造即可得本题答案。除根结点和叶结点外，遍历到其他结点时在遍历其左子

20、树之前加上左括号，在遍历完右子树后加上右括号。void B七reeToE(BTree*root BtreeToExp(root,1);根的高度为1void.13七reeToE:xp(BTree*roqt,int deep)空结点返回if(root=NULL)return;else if(root-left=NULL&rot今right=NULL)!/若为叶结点printf(%s,root-data);/输出操作数，不加括号else if(deepl)printf();/若有子表达式则加1层括号BtreeToExp(root-left,deep+l);printf(%s,root-da七a);/

21、输出操作符Btree16Exp(roo七一right,.ieep+l l;if(deepl)printf();/若有子表达式则加1层括号【评分说明】CD若考生设计的算法满足题目的功能要求，则(1)、(2)根据所实现算法的策略及输出结果给分，评分标准见下表。分数15 14 II 9:,;7 备注采用中序遍历算法且正确，括号嵌套正确，层数适当采用中序遍历算法且正确，括号嵌套正确，但括号嵌套层数过多。例如，表达式最外层加上括号，或操作数加括号，如(a)采用中序遍历算法，但括号嵌套层数不完全正确。例如，左右括号数量不匹配采用中序遍历算法，但没有考虑括号其他若考生采用其他方法得到正确结果，可参照的评分标

22、准给分。如果程序中使用了求结点深度等辅助函数，但没有给出相应的实现过程，只要考生进行了必要的说明，可不扣分。若在算法的基本设计思想描述中因文字表达没有清晰反映出算法思路，但在算法实现中能够表达出算法思想且正确的，则可参照心的标准给分。若算法的基本设计思想描述或算法实现中部分正确，可参照中各种情况的相应给分标准酌情给分。参考答案中只给出了使用C 语言的版本，使用C+语言的答案参照以上评分标准。42.解答：(1)Prim算法属于贪心策略。算法从一个任意的顶点开始，一直长大到覆盖图中所有顶点为止。算法每一步在连接树集合S 中顶点和 其他顶点的边中，选择一条使得树 的总权重增加最小的边 加入集合S。当

23、算法终止时，S 就是最小生成树。CD s中顶点为A,候选边为(A,D),(A,B),(A,E),选择(A,D)加入S。s中顶点为A,D,候选边为(A,B),(A,E),(D,E),(C,D),选择(D,E),加入S。s中顶点为A,D,E,候选边为(A,B),(C,D),(C,E),选择(C,E)加入S。s中顶点为A,D,E,C,候选边为(A,B),(B,C),选择(B,C)加入S。s就是最小生成树。依次选 出的边为(A,D),(D,E),(C,E),(B,C)(4分）【评分说明】每正确选对一条边且次序正确，给 1 分。若考生选择的边正确，但次序不完全正确，酌情给分。(2)图G的MST是唯一的。

24、(2分）第一小题的最小生成树包括了图中权值最小 的四条边，其他边都比这四条边大，所以此图的MST唯一。(3)当带权连通图 的 任意一个环 中所包含的边的权值均不 相同时，其MST 是唯一的。(2分）此 题不要求回答充分必要条件，所以回答一个限制边 权值的充分条件即可。【评分说明】若考生答案中给出的 是其他充分条件，例如“带权连通图的所有边的权值均不相同”，同样给分。若考生给出的充分条件对图的顶点数 和边数做了某些限制，例如，限制 了图中顶点的个数（顶点 个数少于3个）、限制了图的形状（图中没有环）等，则最高给l 分。答案部分 正确，酌情给分。43.解答：(1)由于i和n是unsigned 型，

25、故i=n-1是无符号 数比较，n=O时，n-1 的机器数为全1,值是232_ 1,为unsigned型可 表示的 最大数，条件i=n-1永真，因此出现死循环。(2分）若i 和n改为int类型，则不会出现死循环。(1分）因为i=n-1是带符号整数比较，n=O时，n-1 的值是-1,当i=0 时条件i 发送窗口+1,所以这里发送窗口最大为 7。此时已发送了s3,o和s4,1,所以最多还可以发送5个帧。(3)甲方需要重发3个数据帧(1分），重发的第一个帧是S2,3 C 1分）。在GBN协议中，接收方发送了N帧后，检测出错，则需要发送出错帧及其之后的帧。S2,0超时，所以重发的第一帧是S2。已收到乙的R2$.贞，所以确认号应为3。(4)甲方可以达到的最大信道利用率是8x1000 7x 100 x106 8xl000 0.96x10-3+2x 100 x106 X 100%=50%(2分）U=发送数据的时间从开始发送第一帧到收到第一个确认帧的时间=Nfd/(Td+RTT+Ta)U是信道利用率，N是发送窗口的最大值，Td是发送一数据帧的时间，RTT 是往返时间，Ta 是发送一确认帧的时间。这里采用捎带确认，Td=Ta。【评分说明】答案部分正确，酌情给分。