『37』 王道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)%m C．read-front-1 D．read-front 4． 有关二叉树下列说法正确的是（ ）。 A．二叉树的度为2 B．一棵二叉树的度可以小于 2 C．二叉树中至少有一个结点的度为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-1 6． 一棵哈夫曼树共有 215 个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。 A．107 B．108 C．214 D．215 7. 设无向图 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． 从二叉树的任一结点出发到根的路径上，所经过的结点序列必按其关键字降序排列的是（ ）。 A．二叉排序树 B．大顶堆 C．小顶堆 D．平衡二叉树 10．若对 29 个记录只进行三趟多路平衡归并，则选取的归并路数至少是（ ）。 [王道考研]2013 年最后8 套模拟题 『38』 A．2 B．3 C．4 D．5 11． 设线性表中每个元素有两个数据项k1 和k2，现对线性表按以下规则进行排序：先看数据项k1，k1 值小的元素在前，大的在后；在k1 值相同的情况下，再看k2，k2 值小的在前，大的在后。满足这种要求的排序方法是（ ）。 A．先按k1 进行直接...
