1、2017年计算机学科专业基础综合试题参考答案一、单项选择题1.B2.c3.A4.B5.B6.D7.B8.A9.B10.B11.D12.C13.C14.A15.D16.A17.C18.B19.A20.D21.D22.B23.D24.C25.B26.D27.B28.D29.B30.D31.B32.B33.A34.D35.B36.A37.D38.C39.A40.C1.解析：Sum+=+i;相当于+i;sum=sum+i;。进行到第k趟循环，sum=(1+k)k/2。显然需要进行O(n12)趟循环，因此这也是该函数的时间复杂度。2.解析：I的反例：计算斐波拉契数列迭代实现只需要一个循环即可实现。的反例
2、：入栈序列为1、2,进行如下操作PUSH、PUSH、POP、POP,出栈次序为2、1；进行如下操作PUSH、POP、PUSH、POP,出栈次序为1、2。V,栈是一种受限的线性表，只允许在一端进行操作。正确。3.解析：三元组表的结点存储了行row、列col、值value三种信息，是主要用来存储稀疏矩阵的一种数据结构。十字链表将行单链表和列单链表结合起来存储稀疏矩阵。邻接矩阵空间复杂度达O(,不适于存储稀疏矩阵。二叉链表又名左孩子右兄弟表示法，可用于表示树或森林。因此A正确。4.解析：先序序列是先父结点，接着左子树，然后右子树。中序序列是先左子树，接着父结点，然后右子树，递归进行。如果所有非叶结点
3、只有右子树，先序序列和中序序列都是先父结点，然后右子树，递归进行，因此B正确。5.解析：后序序列是先左子树，接着右子树，最后父结点，递归进行。根结点左子树的叶结点首先被访问，它是e。接下来是它的父结点a,然后是a的父节点c。接着访问根结点的右子树。它的叶结点b首先被访问，然后是b的父结点d,再者是d的父结点g。最后是根结点f。因此d与a同层，B正确。6.解析：哈夫曼编码是前缀编码，各个编码的前缀各不相同，因此直接拿编码序列与哈夫曼编码009。比对即可。序列可分割为0100011001001011110101，译码结果是afeefgd,选项D正确。7.解析：无向图边数的两倍等于各顶点度数的总和。
4、由于其他顶点的度均小于3，可以设它们的度都为2，设它们的数量是x,可列出这样的方程4*3+3*4+2*x=16*2,解得x=3.4+3+3=11,B正确。8.解析：折半查找判定树实际上是一棵二叉排序树，它的中序序列是一个有序序列。可以在树结点上依次填上相应的元素，符合折半查找规则的树即是所求。B选项4、5相加除二向上取整，7、8相加除二向下取整，矛盾。C选项，3、4相加除二向上取整，6、7相加除二向下取整，矛盾。D选项，1、10相加除二向下取整，6、7相加除二向上取整，矛盾。A符合折半查找规则，正确。AB10510699.解析：B+树是应文件系统所需而产生的B树的变形，前者比后者更加适用于实际
5、应用中的操作系统的文件索引和数据库索引，因为前者磁盘读写代价更低，查询效率更加稳定。编译器中的词法分析使用有穷自动机和语法树。网络中的路由表快速查找主要靠高速缓存、路由表压缩技术和快速查找算法。系统一般使用空闲空间链表管理磁盘空闲块。所以B正确。10.解析：归并排序代码比选择插入排序更复杂，前者空间复杂度是O),后者是O(1)。但是前者时间复杂度是O(nlogn),后者是O(n)。所以B正确。11.解析：插入排序、选择排序、起泡排序原本时间复杂度是O),更换为链式存储后的时间复杂度还是O()。希尔排序和堆排序都利用了顺序存储的随机访问特性，而链式存储不支持这种性质，所以时间复杂度会增加，因此选
6、D。12.解析：运行时间=指令数*CPI/主频。M1的时间=指令数*2/1.5，M2的时间=指令数*1/1.2，两者之比为(2/1.5)：(1/1.2)=1.6。故选C。13.解析：由4个DRAM芯片采用交叉编址方式构成主存可知主存地址最低二位表示该字节存储的芯片编号。double型变量占64位，8个字节。它的主存地址804001AH最低二位是10，说明它从编号为2的芯片开始存储（编号从0开始）。一个存储周期可以对所有芯片各读取一个字节，因。010选B。33.解析：OSI参考模型共7层，除去物理层和应用层，剩五层。它们会向PDU引入20B*5=100B的额外开销。应用层是最顶层，所以它的数据传
7、输效率为400B/500B=80%,选A。34.解析：可用奈奎斯特采样定理计算无噪声情况下的极限数据传输速率，用香农第二定理计算有噪信道极限数据传输速率。2W1og2NWIog2(1+S),W是信道带宽，N是信号状态数，S/N是信噪比，将数据带入计算可得N32，选D。分贝数=10log1oSN。35.解析：IEEE802.11数据帧有四种子类型，分别是BSS、From AP、ToAP、WDS。这里的数据帧F是从笔记本电脑发送往访问接入点(AP),所以属于ToAP子类型。这种帧地址1是RA(BSSID),地址2是SA,地址3是DA。RA是receiver address的缩写，BSSID是bas
8、ic service set identifier的缩写，SA是source address的缩写，DA是destination address的缩写。因此地址1是AP的MAC,地址2是H的MAC,地址3是R的MAC,选B。36.解析：根据RF文档描述，0.0.0.0/32可以作为本主机在本网络上的源地址。127.0.0.1是回送地址，以它为目的IP地址的数据将被立即返回到本机。200.10.10.3是C类P地址。255.255.255.255是广播地址。37.解析：RP是一种分布式的基于距离向量的路由选择协议，通过广播UDP报文来交换路由信息。OSPF是一个内部网关协议，不使用传输协议，如U
9、DP或TCP,而是直接用P包封装它的数据。BGP是一个外部网关协议，用TCP封装它的数据。因此，选D。38.解析：这个网络有16位的主机号，平均分成128个规模相同的子网，每个子网有7位的子网号，9位的主机号。除去一个网络地址和广播地址，可分配的最大IP地址个数是29-2=512-2=510，选C。39.解析：按照慢开始算法，发送窗口=mi拥塞窗口，接收窗口，初始的拥塞窗口为最大报文段长度1KB。每经过二个RTT,拥塞窗口翻倍，因此需至少经过5个RTT,发送窗口才能达到32KB,所以选A。这里假定乙能及时处理接收到的数据，空闲的接收缓存32KB。40.解析：FTP协议使用控制连接和数据连接，控制连接存在于整个FTP会话过程中，数据连接在每次文件传输时才建立，传输结束就关闭，A对，B对。默认情况下FTP协议使用TCP20端口进行数据连接，TCP21端口进行控制连接。但是是否使用TCP20端口建立数据连接与传输模式有关，主动方式使用TCP20端口，被动方式由服务器和客户端自行协商决定，C错，D对。所以选C。二、综合应用题41.解答：(1)算法的基本设计思想表达式树的中序序列加上必要的括号即为等价的中缀表达式。可以基于二叉树的中序遍历策略得到所需的表达式。(3分)013