计算机学科专业基础考研综合模拟试题及详细解析..docxVIP

计算机科学与技术学科联考计算机学科专业基础模拟试题（第一套）一、单项选择题：第 1～40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中， 只有一个选项最符合试题要求。1．假设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度为（）。void fun(int n){ int i,j,k;for(i=1;i=n;i++) for(j=1;j=n;j++){k=1;while(k=n) k=5*k;}}A．O(n2log2n) C．O(n2log5n)B．O(nlog5n) D．O(n3)2．以下说法正确的是（）。Ⅰ．带头结点的循环双链表 L 为空的条件是：L-prior==LL-next==LⅡ．线性表的插入和删除总是伴随着大量数据的移动 Ⅲ．只有删除静态链表的尾结点才不需要移动元素 Ⅳ．若线性表采用链式存储结构，要求内存中可用存储单元的地址必须不连续 A．仅ⅠB．仅Ⅰ、ⅡC．仅Ⅱ、ⅢD．Ⅰ、Ⅱ、Ⅲ和Ⅳ3．循环队列用数组 A[0….m-1]存放其元素值，已知其头尾指针分别是 front 和 rear（且队 尾指针 rear 指向队尾元素的下一个元素），则当前队列中的元素个数是（）。A．(rear-front+m)%mB．(rear-front+1)%mC．rear-front-1D．rear-front 4．下列关于二叉树的叙述中正确的是（）。 Ⅰ．对于任何一棵二叉树，叶子结点数都是度为 2 的结点数加 1 Ⅱ．二叉树的左右子树不可以任意地交换Ⅲ．二叉树只适合使用链式结构存储，不可能用顺序结构存储 Ⅳ．结点按层序编号的二叉树，第 i 个结点的左孩子（假设存在）的编号为 2i A．仅Ⅰ、ⅡB．仅ⅡC．仅Ⅱ、ⅣD．仅Ⅱ、Ⅲ5．已知一棵深度为 k 的平衡二叉树，其每个非叶子结点的平衡因子均为 0，则该树共有结 点总数为（）。A．2k1-1B．2k1+1C．2k-1D．2k+16．根据使用频率为 5 个字符设计的赫夫曼编码不可能是（ ）。 A．000，001，010，011，1B．0000，0001，001，01，1 C．000，001，01，10，11D．00，100，101，110，1117．在具有 n 个顶点的图 G 中，若最小生成树不唯一，则（）。 Ⅰ．G 的边数一定大于 n-1Ⅱ．G 的权值最小的边一定有多条 Ⅲ．G 的最小生成树代价不一定相等A．仅ⅠB．仅Ⅰ、ⅢC．仅Ⅰ、ⅡD．仅Ⅲ8．以下哪些方法可以判断出一个有向图是否有环（）。 Ⅰ．深度优先遍历Ⅱ．求最短路径Ⅲ．拓扑排序Ⅳ．求关键路径A．仅Ⅰ、ⅢB．仅Ⅰ、Ⅲ、ⅣC．仅Ⅰ、Ⅱ、ⅢD．Ⅰ、Ⅱ、Ⅲ和Ⅳ 9．在一棵二叉排序树上，查找关键字为 35 的结点，依次比较的关键字有可能是（）。 A．28，36，18，46，35B．18，36，28，46，35C．46，28，18，36，35D．46，36，18，28，35 10．排序趟数与序列的原始状态无关的排序方法是（ ）。 Ⅰ．直接插入排序Ⅱ．简单选择排序Ⅲ．冒泡排序Ⅳ．基数排序A．仅Ⅰ、ⅢB．仅Ⅰ、Ⅱ、ⅣC．仅Ⅰ、Ⅱ、ⅢD．仅Ⅰ、Ⅳ 11．下列关于外部排序说法正确的是（）。 A．内存与外设交换信息的时间只是外排序总时间的一小部分 B．外部排序就是在外存上进行排序，无需内存参与 C．败者树是一棵完全二叉树D．置换-选择排序得到的初始归并段长度一定相等12．图 1-1 中计算机硬件系统基本组成部件①、②、③、④和⑤的名称分别是（）。A．①控制器、②运算器、③存储器、④输入设备、⑤输出设备B．①运算器、②控制器、③存储器、④输入设备、⑤输出设备 C．①运算器、②存储器、③控制器、④输入设备、⑤输出设备 D．①运算器、②控制器、③存储器、④输出设备、⑤输入设备图 1-1 计算机硬件系统基本组成部件13．已知小写英文字母“a”的 ASCII 码值为 61H，现字母“g”被存放在某个存储单元中， 若采用偶校验（假设最高位作为校验位），则该存储单元中存放的十六进制数是（）。A．167HB．E6HC．67HD．E7H14．页式存储系统的逻辑地址是由页号和页内地址两部分组成的。假定页面的大小为 4KB， 地址变换过程如图 1-2 所示，图中逻辑地址用十进制数表示。逻辑地址经过变换后，十进制数 物理地址 a 应为（）。A．33220B．8644C．4548D．2500图 1-2 页式存储系统的逻辑地址变换过程15．下列关于ROM和RAM的说法中，正确的是（）。 Ⅰ．CD-ROM 与EPROM都采用随机存储方式 Ⅱ．SRAM读后不需要刷新，而DRAM读后需要刷新 Ⅲ．Cache可以由ROM或者RAM组成A．Ⅰ、Ⅱ和ⅢB．仅Ⅱ和ⅢC．仅ⅢD．仅Ⅱ16．下列关于 Flash 存储器的说法正确的是（）。A．Flash 存储