2017计算机考研408真题.pdfVIP

2017年全国硕士研究生招生考试 计算机科学与技术学科联考 计算机学科专业基础综合试题 一、单项选择题：1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一 个选项符合题目要求。 1．下列函数的时间复杂度是 int func ( int n) { int i=0, sum=0; while(sum n) sum += ++ i; return i ; { A. O(log n) B. O(n1/2) C. O(n) D. O(nlog n) 2 ．下列关于栈的叙述中，错误的是 ．． Ⅰ．采用非递归方式重写递归程序时必须使用栈 Ⅱ．函数调用时，系统要用栈保存必要的信息 Ⅲ．只要确定了入栈次序，即可确定出栈次序 Ⅳ．栈是一种受限的线性表，允许在其两端进行操作 A ．仅Ⅰ B ．仅Ⅰ、Ⅱ、Ⅲ C ．仅Ⅰ、Ⅲ、Ⅳ D ．仅Ⅱ、Ⅲ、Ⅳ 3．适用于压缩存储稀疏矩阵的两种存储结构是 A ．三元组表和十字链表 B ．三元组表和邻接矩阵 C ．十字链表和二叉链表 D ．邻接矩阵和十字链表 4 ．要使一棵非空二叉树的先序序列与中序序列相同，其所有非叶结点须满足的条件是 A ．只有左子树 B ．只有右子树 C ．结点的度均为1 D．结点的度均为2 5．已知一棵二叉树的树形如下图所示，其后序序列为e，a，c，b ，d，g，f，树中与结点a 同层的结点是 A ．c B ．d C ．f D ．g 6．已知字符集{a，b ，c，d，e，f，g，h} ，若各字符的哈夫曼编码依次是 0100，10，0000，0101，001，011，11，0001，则编码序列 0100011001001011110101 的译码结果是 A ．a c g a b f h B ．a d b a g b b C ．a f b e a g d D ．a f e e f g d 7 ．已知无向图G含有16条边，其中度为4 的顶点个数为3，度为3的顶点个数为4 ，其他顶点 的度均小于3 。图G所含的顶点个数至少是 A ．10 B．11 C．13 D．15 8．下列二叉树中，可能成为折半查找判定树(不含外部结点) 的是 9．下列应用中，适合使用B+树的是 A ．编译器中的词法分析 B ．关系数据库系统中的索引 C ．网络中的路由表快速查找 D ．操作系统的磁盘空闲块管理 10．在内部排序时，若选择了归并排序而没有选择插入排序，则可能的理由是 Ⅰ．归并排序的程序代码更短 Ⅱ．归并排序的占用空间更少 Ⅲ．归并排序的运行效率更高 A ．仅Ⅱ B ．仅Ⅲ C ．仅Ⅰ、Ⅱ D ．仅Ⅰ、Ⅲ 11．下列排序方法中，若将顺序存储更换为链式存储，则算法的时间效率会降低的是 Ⅰ. 插入排序 Ⅱ．选择排序 Ⅲ．起泡排序 Ⅳ．希尔排序 Ⅴ．堆排序 A ．仅Ⅰ、Ⅱ B ．仅Ⅱ、Ⅲ C ．仅Ⅲ、Ⅳ D ．仅Ⅳ、Ⅴ 12．假定计算机M1和M2具有相同的指令集体系结构( ⅠSA)，主频分别为1.5 GHz和1.2 GHz 。 在M1和M2上运行某基准程序P ，平均CP Ⅰ分别为2和1，则程序P在M1和M2上运行时问的比值 是 A ．0.4 B ．0.625 C．1.6 D．2.5 13．某计算机主存按字节编址，由4个64M×8位的DRAM芯片采用交叉编址方式构成，并与 宽度为32位的存储器总线相连，主存每次最多读写32位数据。若double型变量x 的主存地址为804 001AH，则读取x需要的存储周期数是 A ．1 B．2 C ．3 D ．4 14．某C语言程序段如下： for(i=0；i=9 ；i++) { temp=1； for(j=0；j=i ；j++)temp