下载文档原格式
王道2013年最后8套模拟试题（四）一、单项选择题：第1～40小题，每小题2分，共80分。
下列每题给出的四个选项中，只有一个选项最符合试题要求。
1．设n是描述问题规模的正整数，下列程序片段的时间复杂度是（）。
i=n*n;while(i!=1)i=i/2;A．O(log2n2) B．O(n) C．O(log2n) D．O(n2)2．执行完下列语句段后，i值为（）。
int f(int x){ return ((x>0)? x*f(x-1):2);}int i;i=f(f(1));A．2 B．4 C．8 D．无限递归3. 循环队列用数组A[0…m-1]存放其元素值，头尾指针分别为front 和rear，front指向队头元素，rear指向队尾元素的下一个元素，则当前队列中的元素个数是（）。
A．(rear-front+m)%m B．(rear-front+1)%mC．read-front-1 D．read-front4．有关二叉树下列说法正确的是（）。
A．二叉树的度为2 B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2 D．二叉树就是度为2的有序树5．一般说来，若深度为k的n个结点的二叉树具有最小路径长度时，第k层（根为第1层）上的结点数为（）。
A．n-2k-2+1 B．n-2k-1+1 C．n-2k+n D．n-2k-16．一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。
A．107 B．108 C．214 D．2157. 设无向图G=(V,E)和G’=(V’,E’)，如果G’是G的生成树，则下面说法错误的是（）。
A．G’是G的子图B．G’是G的连通分量C．G’是G的极小连通子图且V=V’D．G’是G的一个无环子图8. 在具有n个顶点的图G中，若最小生成树不唯一，则（）。
A．G的边数一定大于n-1 B．G的权值最小的边一定有多条C．G的最小生成树代价不一定相等D．上述选项都不对9．从二叉树的任一结点出发到根的路径上，所经过的结点序列必按其关键字降序排列的是（）。
王道2013 年最后8套模拟试题（五）一、单项选择题：第1～40 小题，每小题2 分，共80 分。
下列每题给出的四个选项中，只有一个选项最符合试题要求。
1．栈和队列的主要区别在于( )。
A．逻辑结构不一样B．存储结构不一样C．所包含的运算不一样D．插入和删除运算的限定不一样2．假设栈的容量为3，入栈的序列为1,2,3,4,5，则出栈的序列可能为( )。
A．3,2,1,5,4B．1,5,4,3,2 C．5,4,3,2,1 D．4,3,2,1,53．将中缀表达式转换为等价的后缀表达式的过程中要利用堆栈保存运算符。
对于中缀表达式A-(B+C/D)×E，当扫描读到操作数E 时，堆栈中保存的运算符依次是( )。
A．-×B．-（×C．- + D．-（+4．前序遍历和中序遍历结果相同的二叉树为( )。
Ⅰ．只有根结点的二叉树Ⅱ．根结点无右孩子的二叉树Ⅲ．所有结点只有左子树的二叉树Ⅳ．所有结点只有右子树的二叉树A．仅有ⅠB．Ⅰ、Ⅱ和ⅣC．Ⅰ和ⅢD．Ⅰ和Ⅳ5．在含有15 个结点的平衡二叉树上，查找关键字为28（存在该结点）的结点，则依次比较的关键字有可能是( )。
A．30,36 B．38,48,28 C．48,18,38,28 D．60,20,50,40,38,286．若一棵深度为6 的完全二叉树的第6 层有3 个叶子结点，则该二叉树共有( )个叶子结点。
A．17 B．18 C．19 D．207．若G 是一个具有36 条边的非连通无向图（不含自回路和多重边），则图G 的结点数至少是( )。
A．11 B．10 C．9 D．88. 在有向图G的拓扑序列中，若顶点V i 在顶点V j 之前，则下列情形不可能出现的是( )。
A．G 中有弧<V i，V j> B．G 中有一条从V i 到V j 的路径C．G 中没有弧< V i，V j> D．G 中有一条从V j 到V i 的路径9. 散列表的地址范围为0-17，散列函数为H(k)=k mod 17。
王道模拟试题（五）答案一、单项选择题1．D。
【解析】考查栈和队列的区别。
栈和队列的逻辑结构都是线性的，都有顺序存储和链式存储，有可能包含的运算不一样，但不是主要区别，任何数据结构在针对具体问题时所包含的运算都可能不同。
插入和删除运算的限定不一样才是栈和队列的最主要区别。
2．A。
【解析】考查出入栈序列和栈深的关系。
由于栈的最大深度不能超过3。
故第一个出栈元素不能是5或4，第二个出栈的元素不能是5，由此可以排除B、C、D。
3．A。
扫描到E时，运算符栈中的内容依次是“-×”，因此选A。
4．D。
【解析】考查二叉树的遍历。
对于I，显然任何遍历都相同。
对于II，根结点无右孩子，此时前序遍历先遍历根结点，中序遍历最后遍历根结点，所以不相同。
对于III，是一棵左单支树，前序遍历和后序遍历的序列相反。
对于IV，所有结点只有右子树的右单支树，前序遍历和中序遍历的序列相同。
选D。
5．C。
【解析】考查平衡二叉树的性质与查找操作。
设N h表示深度为h的平衡二叉树中含有的最少结点数，有：N0=0，N1=1，N2=2，…，N h=N h-1+N h-2+1，N3=4，N4=7，N5=12，N6=20>15（考『151』生应能画出图形）。
也就是说，高度为6的平衡二叉树最少有20个结点，因此15个结点的平衡二叉树的高度为5，而最小叶子结点的层数为3，所以选项D错误。
选项B的查找过程不能构成二叉排序树，错误。
选项A根本就不包含28这个值，错误。
6．A。
【解析】考查完全二叉树性质。
完全二叉树第5层共有24=16个结点。
第6层最左边有3个叶子结点，对应第5层最左边2个结点，所以第5层右边有16-2=14个叶子结点，因此共有17个叶子结点。
【另解】画出草图的片段部分进行求解，比较形象且不易出错。
7．B。
【解析】考查无向完全图的性质。
n个结点的无向完全图共有n(n-1)/2条边。
对于n+1个结点和n(n-1)/2边构成的非连通图，仅当n个顶点构成完全图、第n+1个顶点构成一个孤立顶点的图；若再增加一条边，则在任何情况下都是连通的。
统考计算机应用基础考试大纲及答案（2013年修订版）（20200920025847）百度文库-让每个人平等地提升自我《计算机应用基础》考试大纲试题结构与题型试题分为选择题和操作题两大类，其中选择题约占40%操作题约占60%试题内容比例为：计算机基础知识和操作系统及其应用约占30%文字编辑、电子表格和电子演示文稿约占35%计算机网络基础和In ternet应用约占25% 信息安全和多媒体基本应用约占10%试卷分数满分为100分。
考试方式与时间考试方式：机考。
考试时间：90分钟。
考试样卷、单选题1. 世界上第一台电子数字计算机采用的电子器件是 __________ 。
A .大规模集成电路B.集成电路C.晶体管 D ?电子管2. 将计算机分为巨型机、大中型机、小型机、微型机、工作站等五类的分类标准是A ?计算机处理数据的方式B ?计算机使用范围百度文库-让每个人平等地提升自我C.机器的规模和处理能力 D ?计算机使用的电子器件3. 下列描述不属于计算机的主要特点的是A.通用性强C.晶体管4. 在课堂教学中利用计算机软件给学生演示实验。
B .具有自动控制能力D .无逻辑判断能力过程。
计算机的这种应用属于A.辅助教学领域 B .自动控制领域C.数字计算领域 D .辅助设计领域5.所谓的信息是指。
A.基本素材 B .非数值数据C.数值数据 D .处理后的数据6.组成计算机系统的两大部分是。
A.系统软件和应用软件 B .主机和外部设备C.硬件系统和软件系统 D .输入设备和输出设备7.时至今日，计算机仍采用程序内存或称存储程序原理，原理的提出者是_A .莫尔B .比尔?盖茨C.冯?诺依曼 D .科得(E. F. Codd)8?计算机的存储器由千千万万个小单元组成，每个小单元存放______________ 。
A . 8位二进制数B. 1位二进制数C. 1位十六进制数D. 2位八进制数9. 下列4种软件中属于系统软件的是_______ 。
王道2013年最后8套模拟试题（七）一、单项选择题：第1～40小题，每小题2分，共80分。
下列每题给出的四个选项中，只有一个选项最符合试题要求。
1. 执行（）操作时，需要使用队列作为辅助存储空间。
A．查找哈希表B．广度优先搜索图C．前序（根）遍历二叉树D．深度优先搜索图2. 若已知一个栈的入栈序列是1,2,3,4。
其出栈序列为p1,p2,p3,p4，则p2,p4不可能是（）。
A．2、4 B．2、1 C．4、3 D．3、43. 在常用的描述二叉排序树的存储结构中，关键字值最大的结点是（）。
A．左指针一定为空B．右指针一定为空C．左右指针均为空D．左右指针均不为空4. 由4棵树组成的森林中，第一、第二、第三和第四棵树中的结点数分别为30、10、20、5，当把森林转换成二叉树后，对应二叉树中根结点的右子树的左子树的结点数为（）。
A．29 B．9 C．25 D．195．在下列遍历算法中，在遍历序列中叶结点之间的次序可能与其他算法不同的算法是（）。
A．先序遍历算法B．中序遍历算法C．后序遍历算法D．层次遍历算法6．在一棵非空二叉树的中序遍历序列中，根结点的右边（）。
A．只有右子树上的所有结点B．只有右子树上的部分结点C．只有左子树上的部分结点D．只有左子树上的所有结点7. 如果具有n个顶点的图是一个环，则它有（）棵生成树。
A．n2B．n C．n-1 D．18. 具有12个关键字的有序表中，对每个关键字的查找概率相同，折半查找查找成功和查找失败的平均查找长度依次为（）。
A．37/12,49/13 B．35/12,39/13 C．37/13,49/13 D．37/12,49/129. 在一棵含有n个关键字的m阶B-树中进行查找，至多需要读盘（）次（假设读一次盘就能将整个结点取出）。
A．log2n B．1+log2nC．1+lo g m/2[(n+1)/2] D．1+lo g n/2[(m+1)/2]10. 对一组数据（25,84,21,47,15,27,68,35,20）进行排序，前三趟的排序结果如下：第一趟：20,15,21,25,47,27,68,35,84第二趟：15,20,21,25,35,27,47,68,84第三趟：15,20,21,25,27,35,47,68,84则所采用的排序方法是（）。
考研专业课复习是考研备考中至关重要的一环，真题是必不可少的备考资料。
中公考研为大家整理了2013年计算机考研专业课真题及答案，供大家下载使用，并且提供计算机考研专业课辅导，更多真题敬请关注中公考研网！2013年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：1~40小题，每小题2分，共80分。
下列每题给出的四个选项中，只有一个选项符合试题要求。
1.已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是A.()OnB. ()OmnC. (min(,))OmnD. (max(,))Omn2.一个栈的入栈序列为1,2,3, ,n，其出栈序列是123,,, ,npppp。
若23p，则3p可能取值的个数是A. 3nB. 2nC. 1nD. 无法确定3.若将关键字1，2，3，4，5，6，7依次插入到初始为空的平衡二叉树T中，则T中平衡因子为0的分支结点的个数是A. 0B. 1C. 2D. 34.已知三叉树T中6个叶结点的权分别是2，3，4，5，6，7，T的带权（外部）路径长度最小是A. 27B. 46C. 54D. 565.若X是后序线索二叉树中的叶结点，且X存在左兄弟结点Y，则X的右线索指向的是A.X的父结点B. 以Y为根的子树的最左下结点C. X的左兄弟结点YD. 以Y为根的子树的最右下结点6.在任意一棵非空二叉排序树T1中，删除某结点v之后形成二叉排序树T2，再将v插入T2形成二叉排序树T3。
下列关于T1与T3的叙述中，正确的是I. 若v是T1的叶结点，则T1与T3不同II. 若v是T1的叶结点，则T1与T3相同III. 若v不是T1的叶结点，则T1与T3不同IV. 若v不是T1的叶结点，则T1与T3相同A.仅I、IIIB. 仅I、IVC. 仅II、IIID. 仅II、IV7.设图的邻接矩阵A如下所示。
各顶点的度依次是0101001101001000AA. 1，2，1，2B. 2，2，1，1C. 3，4，2，3D. 4，4，2，28.若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是A.h，c，a，b，d，e，g，fB. e，a，f，g，b，h，c，dB.C. d，b，c，a，h，e，f，g D. a，b，c，d，h，e，f，g9.下列AOE网表示一项包含8个活动的工程。
王道2013年最后8套模拟试题（八）一、单项选择题：第1～40小题，每小题2分，共80分。
下列每题给出的四个选项中，只有一个选项最符合试题要求。
1．若一个栈以向量V[1…n]存储，初始栈顶指针top为n+1，则x进栈的正确操作是( )。
A．top=top+1; V[top]=x B．V[top]=x; top=top+1C．top=top-1; V[top]=x D．V[top]=x; top=top-12．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为( )。
A．1和5 B．2和4 C．4和2 D．5和13．下图所示的二叉树是( )。
A．二叉判定树B．二叉排序树C．二叉平衡树D．堆4. 由某种序列可以唯一的确定一棵二叉树，不能唯一的确定一棵二叉树是( )。
A．先序序列和中序序列B．后序序列和中序序列C．中序序列和层序序列D．先序序列和层序序列5. 利用逐点插入建立序列（50,72,43,85,75,20,35,45,65,30）对应的二叉排序树后，要查找元素30要进行元素间的比较次数是( )。
A．4 B．5 C．6 D．76. 一个有n个顶点和n条边的无向图一定是( )。
A．连通的B．不连通的C．无环的D．有环的7. 已知一个有向图的邻接表存储结构如下图所示，根据有向图的深度优先遍历算法，从顶点1出发，所得到的顶点序列是( )。
A．1,2,3,5,4 B．1,2,3,4,5C．1,3,4,5,2 D．1,4,3,5,2量级相当。
A．顺序查找B．折半查找C．分块查找D．散列查找9. 对关键字序列{23,17,72,60,25,8,68,71,52}进行堆排序，输出两个最小关键字后的剩余堆是( )。
A．{23,72,60,25,68,71,52} B．{23,25,52,60,71,72,68}C．{71,25,23,52,60,72,68} D．{23,25,68,52,60,72,71}10．对关键码序列28,16,32,12,60,2,5,72快速排序，从小到大一次划分结果为( )。
2013年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：第1～40小题，每小题2分，共80分。
下列每题给出的四个选项中，只有一个选项最符合试题要求。
1．已知两个长度分别为m 和n 的升序链表，若将它们合并为一个长度为m +n 的降序链表，则最坏情况下的时间复杂度是（ ）。
A ．()O n B ．()O m n ⨯ C ．(min(,))O m n D ．(max(,))O m n 2．一个栈的入栈序列为1,2,3,,n ，其出栈序列是123,,,,n p p p p 。
若23p =，则3p 可能取值的个数是（ ）。
A ．3n -B ．2n -C ．1n -D ．无法确定3．若将关键字1，2，3，4，5，6，7依次插入到初始为空的平衡二叉树T 中，则T 中平衡因子为0的分支结点的个数是（ ）。
A ．0B ．1C ．2D ．34．已知三叉树T 中6个叶结点的权分别是2，3，4，5，6，7，T 的带权（外部）路径长度最小是（ ）。
A ．27B ．46C ．54D ．565．若X 是后序线索二叉树中的叶结点，且X 存在左兄弟结点Y ，则X 的右线索指向的是（ ）。
A ．X 的父结点B ．以Y 为根的子树的最左下结点C ．X 的左兄弟结点YD ．以Y 为根的子树的最右下结点6．在任意一棵非空二叉排序树T 1中，删除某结点v 之后形成二叉排序树T 2，再将v 插入T 2形成二叉排序树T 3。
下列关于T 1与T 3的叙述中，正确的是（ ）。
I ．若v 是T 1的叶结点，则T 1与T 3不同II ． 若v 是T 1的叶结点，则T 1与T 3相同III ．若v 不是T 1的叶结点，则T 1与T 3不同IV ．若v 不是T 1的叶结点，则T 1与T 3相同A ．仅I 、IIIB ．仅I 、IVC ．仅II 、IIID ．仅II 、IV7．设图的邻接矩阵A 如下所示。
各顶点的度依次是（ ）。
数最少为（ ）。
A ．100 B ．201 C ．199 D ．200王道 2013 年最后 8 套模拟试题（一）一、单项选择题：第 1～40 小题，每小题 2 分，共 80 分。
下列每题给出的四个选项中，只有一个选项最符合试题要求。
1． 设 n 是描述问题规模的正整数，下列程序片段的时间复杂度是（）。
y=0;while(n>=(y+1)*(y+1)) y++;A ．O(log 2n)B ．O(n)C ．O(nlog 2n)D ．)2． 利用栈求表达式的值时，设立运算数栈 O PEN 。
假设 O PEN 只有两个存储单元，则在下 列表达式中，不会发生溢出的是（ ）。
A ．A-B*(C-D)B ．(A-B)*C-DC ．(A-B*C)-D D ．(A-B)*(C-D)3． 将 5 个字母”oo ops ”按此顺序进栈，则有（ ）种不同的出栈顺序可以仍然得到”ooops ”。
A ．1B ．3C ．5D ．64． 以下关于二叉排序树的说法中，错误的有（ ）个。
Ⅰ．对一棵二叉排序树按前序遍历得出的结点序列是从小到大的序列 Ⅱ．每个结点的值都比它左孩子的值大、比它右孩子结点的值小，则这样的一棵二叉树就是二叉排序树Ⅲ．在二叉排序树中，新插入的关键字总是处于最底层 Ⅳ．删除二叉排序树中的一个结点再重新插入，得到的二叉排序树和原来的相同A ．1B ．2C ．3D ．45． 如右图所示为一棵平衡二叉树（字母不是关键字），在结点 D 的右子树 上插入结点 F 后，会导致该平衡二叉树失去平衡，则调整后的平衡二叉 树应为（ ）。
6． 在下列二叉树中，（）的所有非叶结点的度均为 2。
Ⅰ．完全二叉树Ⅳ．哈夫曼树A ．Ⅱ和Ⅳ Ⅱ．满二叉树 Ⅴ．二叉排序树 C ．Ⅰ和Ⅲ Ⅲ．平衡二叉树C ．Ⅱ、Ⅳ和ⅤD ．Ⅱ、Ⅲ和Ⅳ7． 设高度为 100 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点 8． 已知有向图 G =(V ，A)，其中 V ={a,b,c,d,e}，A={<a,b>，<a,c>，<d,c>，<d,e>，<b,e>， <c,e>}，对该图进行拓扑排序，下面序列中不是拓扑排序的是（ ）。
