天勤论坛_《2014版高分笔记八套模拟卷》试读版.pdf

计算机科学与技术学科联考 计算机学科专业基础模拟试题 （第一套） 一、单项选择题：第 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; } } 2 A ．O(n log n) B ．O(nlog n) 2 5 2 3 C ．O(n log n) D ．O(n ) 5 2 ．以下说法正确的是（ ）。 Ⅰ．带头结点的循环双链表L 为空的条件是：L-prior==LL-next==L Ⅱ．线性表的插入和删除总是伴随着大量数据的移动 Ⅲ．只有删除静态链表的尾结点才不需要移动元素 Ⅳ．若线性表采用链式存储结构，要求内存中可用存储单元的地址必须不连续 A ．仅Ⅰ B ．仅Ⅰ、Ⅱ C ．仅Ⅱ、Ⅲ D ．Ⅰ、Ⅱ、Ⅲ和Ⅳ 3 ．循环队列用数组A[0 ….m-1]存放其元素值，已知其头尾指针分别是front 和rear （且队 尾指针rear 指向队尾元素的下一个元素），则当前队列中的元素个数是（ ）。 A ．(rear-front+m)%m B ．(rear-front+1)%m C ．rear-front-1 D ．rear-front 4 ．下列关于二叉树的叙述中正确的是（ ）。 Ⅰ．对于任何一棵二叉树，叶子结点数都是度为2 的结点数加1 Ⅱ．二叉树的左右子树不可以任意地交换 模拟试题（第一套） 第1 页（共32 页） Ⅲ．二叉树只适合使用链式结构存储，不可能用顺序结构存储 Ⅳ．结点按层序编号的二叉树，第i 个结点的左孩子（假设存在）的编号为2i A ．仅Ⅰ、Ⅱ B ．仅Ⅱ C ．仅Ⅱ、Ⅳ D ．仅Ⅱ、Ⅲ 5 ．已知一棵深度为k 的平衡二叉树，其每个非叶子结点的平衡因子均为0，则该树共有结 点总数为（ ）。 k1 k1 A ．2 -1 B ．2 +1 k k C ．2 -1 D ．2 +1 6 ．根据使用频率为5 个字符设计的赫夫曼编码不可能是（ ）。 A ．000 ，001，010 ，011 ，1 B ．0000 ，0001 ，001 ，01，1 C ．000 ，001 ，01，10，11 D ．00 ，100，101，110，111 7 ．在具有n 个顶点的图G 中，若最小生成树不唯一，则（ ）。 Ⅰ．G 的边数一定大于n- 1 Ⅱ．G 的权值最小的边一定有多条 Ⅲ．G 的最小生成树代价不一定相等 A ．仅