2017年计算机学科专业基础综合试题参考答案一、单项选择题1.B2.9.B10.17.C18.25.B26.33.A34.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.解析：三元组表的结点存储了行row、列col、值value三种信息，是主要用来存储稀疏矩阵的一种数据结构。十字链表将行单链表和列单链表结合起来存储稀疏矩阵。邻接矩阵空间复杂度达O(n2),不适千存储稀疏矩阵。二叉链表又名左孩子右兄弟表示法，可用千表示树或森林。因此A正确。4.解析：先序序列是先父结点，接着左子树，然后右子树。中序序列是先左子树，接着父结点，然后右子树，递归进行。如果所有非叶结点只有右子树，先序序列和中序序列都是先父结点，然后右子树，递归进行，因此B正确。5.解析：后序序列是先左子树，接着右子树，最后父结点，递归进行。根结点左子树的叶结点首先被访问，它是e。接下来是它的父结点a,然后是a的父结点c。接着访问根结点的右子树。它的叶结点b首先被访问，然后是b的父结点d,再者是d的父结点g。最后是根结点f。因此d与a同层，B正确。CBBDD3.11.19.27.35.4.12.20.28.36.5.13.21.29.37.6.14.22.30.38.7.15.23.31.39.AACBCBDDBADABDCBCDBDBCDDAADABB8.16.24.32.40.6.解析：哈夫曼编码是前缀编码，各个编码的前缀各不相同，因此直接拿编码序列与哈夫曼编码一一比对即可。序列可分割为0100011001001011110101,译码结果是afeefgd,选项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)Bc10D2II9.解析：B+树是应文件系统所需而产生的B-树的变形，前者比后者更加适用于实际应用中的操作系统的文件索引和数据库索引，因为前者磁盘读写代价更低，查询效率更加稳定。编译器中的词法分析使用有穷自动机和语法树。网络中的路由表快速查找主要靠高速缓存、路由表压缩技术和快速查找算法。系统一般使用空闲空间链表管理磁盘空闲块。所以B正确。10.解析：归并排序代码比选择插入排序更复杂，前者空间复杂度是O(n),后者是0(1)。但是前者时间复杂度是O(nlogn),后者是O(n2)。所以B正确。11.解析：插入排序、选择排序、起泡排序原本时间复杂度是O(n2),更换为链式存储后的时间复杂度还是O(n2)。希尔排序和堆排序都利用了顺序存储的随机访问特性，而链式存储不支持这种性质，所以时间复杂度会增加，因此选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个字节。它的主存地址804001AH最低二位是10,说明它从编号为2的芯片开始存储（编号从0开始）。一个存储周期可以对所有芯片各读取一个字节，因此需要3轮，故选C。14.解析：时间局部性是一旦一条指令被执行，则在不久的将来它可能再次被执行。空间局部性是一旦一个存储单元被访问，那么它附近的存储单元也很快被访问。显然，这里的循环指令本身具有时间局部性，它对数组a的访问具有空间局部性，故选A。15.解析：在变址操作时，将计算机指令中的地址与变址寄存器中的地址相加，得到有效地址，指令提供数组首地址，由变址寄存器来定位数...
