设计算法统计二叉树(采用二叉链存储结构)中结点值为x的结点个数_20题，算法工程师能力评估测试来啦...

试题部分

1.

class program {     static void Main(string[] args)     {         int i;         i = x(x(8));     }     static int x(int n)     {         if (n <= 3)             return 1;         else             return x(n - 2) + x(n - 4) + 1;     } }

递归算法x(x(8))需要调⽤⼏次函数x(int n)?

A.9

B.12

C.18

D.24

2.下列关于树的宽度优先搜索算法描述错误的是?

A.从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止

B.常采用先进后出的栈来实现算法

C.空间的复杂度为O(V+E)，因为所有节点都必须被储存，其中V是节点的数量，E是边的数量

D.时间复杂度为O(V+E)，因为必须寻找所有到可能节点的所有路径，其中V是节点的数量，E是边的数量

3.在有序表(12,24,36,48,60,72,84)中二分查找关键字72时所需进行的关键字比较次数是多少？

A.1

B.2

C.3

D.4

4.下面关于B-和B+树的叙述中，不正确的是?

A.B-树和B+树都是平衡的多叉树

B.B-树和B+树都可用于文件的索引结构

C.B-树和B+树都能有效地支持顺序检索

D.B-树和B+树都能有效地支持随机检索

5.具有3个结点的二叉树有几种形态？

A.4

B.5

C.6

D.7

6.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为多少？

A.DGEBFHAC

B.DGEBHFCA

C.DEGHBFCA

D.DEGBHACF

7.已知数据表A中每个元素距其最终位置不远，为节省时间排序，应采用什么方法排序?

A.堆排序

B.插入排序

C.快速排序

D.直接选择排序

8.将N条长度均为M的有序链表进行合并，合并以后的链表也保持有序，时间复杂度为?

A.O(N * M * logN)

B.O(N*M)

C.O(N)

D.O(M)

9.有2n个人排队进电影院，票价是50美分。在这2n个人当中，其中n个人只有50美分，另外n个人有1美元(纸票子)。愚蠢的电影院开始卖票时1分钱也没有。

问：有多少种排队方法 使得 每当一个拥有1美元买票时，电影院都有50美分找钱
注： 1美元=100美分拥有1美元的人，拥有的是纸币，没法破成2个50美分

A.(2n)!/[n!n!]

B.(2n)!/[n!(n+1)!]

C.(2n)!/[n!(n-1)!]

D.(2n + 1)!/[n!(n-1)!]

10.T(n) = 25T(n/5)+n^2的时间复杂度？

A.O(n^2*(lgn))

B.O(n^2)

C.O(lgn)

D.O(n*n*n)

11.连续自然数之和为1000的共有几组？(m，n都为自然数，单独1个数也算作“连续自然数”)

A.3

B.4

C.5

D.8

12.一个有序数列，序列中的每一个值都能够被2或者3或者5所整除，这个序列的初始值从1开始，但是1并不在这个数列中。求第1500个值是多少？

A.2040

B.2042

C.2045

D.2050

13.写出a*(b-c*d)+e-f/g*(h+i*j-k)的逆波兰表达式。

A.a(b-c*d)*+e-(f/g(h+i*j-k)*)

B.a(b-(cd*))*+e-(fg/(h+ij*-k)*)

C.a(bcd*-)*+e-(fg/hij*+k-*)

D.abcd*-*e+fg/hij*+k-*-

14.下列关于线性表，二叉平衡树，哈希表存储数据的优劣描述错误的是？

A.哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；

B.线性表实现相对比较简单

C.平衡二叉树的各项操作的时间复杂度为O(logn)

D.平衡二叉树的插入节点比较快

15.下面程序的功能是输出数组的全排列。请填空。

void perm(int list[], int k, int m){    if (k==m)    {        copy(list,list+m,ostream_iterator<int>(cout," "));        cout<<endl;        return;    }    for (int i=k; i    {        swap(list[k],list[i]);        perm(list,k+1,m);        swap(list[k],list[i]);    }}

A.k!=m 和 perm(list，k+1，m)

B.k==m 和 perm(list，k+1，m)

C.k!=m 和 perm(list，k，m)

D.k==m 和 perm(list，k，m)

16.已知的一个无向图(边为正数)中顶点A,B的一条最短路P，如果把各个边的权重(即相邻两个顶点的距离)变为原来的2倍，那么在新图中，P仍然是A,B之间的最短路，以上说法是:

A.错误

B.正确

17.如果一个堆栈的入栈序列是A,B,C,D,E,则堆栈的不可能输出顺序是(  )。

A.EDCBA

B.DECBA

C.DCEAB

D.ABCDE

18.若以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是(   )。

A.24

B.30

C.53

D.69

19.用某种排序方法对关键字序列(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
请问采用的是以下哪种排序算法(   )

A.选择排序

B.希尔排序

C.归并排序

D.快速排序

20.某颗二叉树中有360个结点，则该二叉树的最小高度是？(包括根节点)

A.10

B.9

C.8

D.7

答案部分

1.正确答案：C

根据题意，易得x(3) = x(2) = x(1) = x(0) = 1

x(8) = x(6) +x(4) +1

       = x(4) + x(2) +1 + x(2) + x(0) +1 + 1

        = x(2) + x(0) +1 + 1 + 1 +1 + 1 +1 + 1

       = 9

x(8)  这个就调用了9次函数x(int n)

同理可得x(9)也是调用了9次函数x(int n)

所以总共18次。

2.正确答案: B  

宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Prim最小生成树算法采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。B应该是采用先进先出的队列。

3.正确答案: B

正确的二分查找应该是一次折半后，high=middle-1 或者 low=middle+1；

所以第一次查找时 high=6,low=0; middle= 0+6/2 = 3,即48；

第二次查找时 high=6, low =3+1; middle = 4+(6-4)/2 = 5,即72，查出所找关键字，故答案为B、2次

4.正确答案: C

B- 树

        是一种多路搜索树(并不是二叉的)：

       1. 定义任意非叶子结点最多只有 M 个儿子；且 M>2 ；

       2. 根结点的儿子数为 [2, M] ；

       3. 除根结点以外的非叶子结点的儿子数为 [M/2, M] ；

       4. 每个结点存放至少 M/2-1 (取上整)和至多 M-1 个关键字；(至少 2 个关键字)

       5. 非叶子结点的关键字个数 = 指向儿子的指针个数 -1 ；

       6. 非叶子结点的关键字：K[1], K[2], …, K[M-1] ；且 K[i] < K[i+1] ；

       7. 非叶子结点的指针：P[1], P[2], …, P[M] ；其中 P[1] 指向关键字小于 K[1] 的子树， P[M] 指向关键字大于 K[M-1] 的子树，其它 P[i] 指向关键字属于 (K[i-1], K[i]) 的子树；

       8. 所有叶子结点位于同一层；

        如：( M=3 )

      ‍ 

       B- 树的搜索，从根结点开始，对结点内的关键字(有序)序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；

B- 树的特性：

       1. 关键字集合分布在整颗树中；

       2. 任何一个关键字出现且只出现在一个结点中；

       3. 搜索有可能在非叶子结点结束；

       4. 其搜索性能等价于在关键字全集内做一次二分查找；

       5. 自动层次控制；

        由于限制了除根结点以外的非叶子结点，至少含有 M/2 个儿子，确保了结点的至少利用率，其最底搜索性能为：

              ‍

        其中， M 为设定的非叶子结点最多子树个数， N 为关键字总数；

        所以 B- 树的性能总是等价于二分查找(与 M 值无关)，也就没有 B 树平衡的问题；

        由于 M/2 的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占 M/2 的结点；删除结点时，需将两个不足 M/2 的兄弟结点合并；

B+ 树

       B+ 树是 B- 树的变体，也是一种多路搜索树：

       1. 其定义基本与 B- 树同，除了：

       2. 非叶子结点的子树指针与关键字个数相同；

       3. 非叶子结点的子树指针 P[i] ，指向关键字值属于 [K[i], K[i+1]) 的子树( B- 树是开区间)；

       5. 为所有叶子结点增加一个链指针；

       6. 所有关键字都在叶子结点出现；

        如：( M=3 )

      ‍ 

    B+ 的搜索与 B- 树也基本相同，区别是 B+ 树只有达到叶子结点才命中( B- 树可以在非叶子结点命中)，其性能也等价于在关键字全集做一次二分查找；

       B+ 的特性：

       1. 所有关键字都出现在叶子结点的链表中(稠密索引)，且链表中的关键字恰好是有序的；

       2. 不可能在非叶子结点命中；

       3. 非叶子结点相当于是叶子结点的索引(稀疏索引)，叶子结点相当于是存储(关键字)数据的数据层；

       4. 更适合文件索引系统；

B* 树

        是 B+ 树的变体，在 B+ 树的非根和非叶子结点再增加指向兄弟的指针；

      ‍ 

    B* 树定义了非叶子结点关键字个数至少为 (2/3)*M ，即块的最低使用率为 2/3 (代替 B+ 树的 1/2 )；

       B+ 树的分裂：当一个结点满时，分配一个新的结点，并将原结点中 1/2 的数据复制到新结点，最后在父结点中增加新结点的指针；B+ 树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；

       B* 树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了)；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制 1/3 的数据到新结点，最后在父结点增加新结点的指针；

        所以， B* 树分配新结点的概率比 B+ 树要低，空间使用率更高；

5.正确答案: B 

Catalan数，h(n)=C(2n,n)/(n+1)

C(2n,n)即常见组合问题，从2n个数中随机抽取n个

此处n=3,h(3)=C(6,3)/(3+1)=20/4=5

6.正确答案: B  

前序遍历特点：访问根节点-》前序访问左树-》前序访问右树---确定根节点为A

中序遍历特点：中序遍历左树-》访问根节点-》中序访问右树---确定A的左边都是左树，右边都是右树，根据前序访问规则和中序访问规则可以知道B是左树的根节点，根据前序遍历“ABDEGCFH”知道C是右树根节点，左树右树节点的排列顺序可以根据前序中序的遍历特点得出，结果如下

                               A

                 B       E          C

             D        G             F    H  

7.正确答案: B  

插入排序：如果平均每个元素离最终位置相距c个元素，则其复杂度为O(cn)，一共n趟，每次比较c次；

快速排序：最好的、平均的复杂度都是O(nlog(n))，如果每次选择的中间数都最小或最大，那就是最坏的情况，复杂度是O(n*n)；所以快速排序和元素的位置没有关系，跟选择的中间数有关。

堆排序：复杂度一直是O(nlog(n));

直接选择排序：跟元素位置没有关系，都要遍历n遍，每遍找出最小或最大数来，复杂度是O(n*n)；

答案是插入排序。

8.正确答案: A  

算法不同结果也不一样。

1、两两合并链表。合并链表复杂度 * 一次合并次数 * 所有合并次数。两两合并的复杂度会指数递增，合并数会指数递减。一共应该是log(N)次。前面的合并复杂度较高。所以一般不采用该方法来合并链表。

2、利用堆来合并，( O(N) + O(log N * N )) * M。

  先利用最链表第一个数，N个数建立堆，复杂度 O (N)

  重构堆，并排序，复杂度 O(logN * N )

  每个链表M个数，上述两步重复M次。结果为  M * (O(N) + O(logN * N))= O (M * N * logN)

9.正确答案: B 

 最最简单的方法，假设法：1.假设有4个人。那么n=2，此时有

A.6

B.2

C.12

D.60.

很显然，如果4个人。模拟一下。逆推一下。

1.最后一个是50美分，前面是1美元(1)或50美分(1)。只有这两种情况。

10.正确答案: A  

T(n) = 25T(n/5)+n^2 = 25(25T(n/25)+n^2/25)+n^2

= 625T(n/25)+n^2+n^2 = 625T(n/25) + 2n^2
= 25^2 * T( n/ ( 5^2 ) ) + 2 * n*n
= 625(25T(n/125)+n^2/625) + 2n^2
= 625*25*T(n/125) + 3n^2
= 25^3 * T( n/ ( 5^3 ) ) + 3 * n*n
= 25 ^ x * T( n / 5^x ) + x * n^2

T(n) = 25T(n/5)+n^2
T(0) = 25T(0) + n^2 ==> T(0) = 0
T(1) = 25T(0)+n^2 ==> T(1) = 1

x = lg 5 n
25 ^ x * T( n / 5^x ) + x * n^2
= n^2 * 1 + lg 5 n * n^2
= n^2*(lgn)

11.正确答案: B

求和的通项公式为 S = (m+n)(n-m+1) = 2000,

假设两个乘数都为偶数，则其和也为偶数，即 (m+n)+(n-m+1) = 2m+1 为偶数，显然是不成立的，而两个奇数相乘一定为奇数，所以两个乘数肯定为一奇一偶。

又因为2000 = 2*2*2*2*5*5*5；

所以取值情况为：奇数可取1，5，25，125四种情况。

12.正确答案: C 

在区间 [1, 30] 中，

能被2整除的数有 30 / 2 = 15 个，

能被3整除的数有 30 / 3 = 10 个，

能被5整除的数有 30 / 5 = 6 个，

能被2整除也能被3整除的数有 30 / 6 = 5 个，

能被2整除也能被5整除的数有 30 / 10 = 3 个，

能被3整除也能被5整除的数有 30 / 15 = 2 个，

能被2整除、能被3整除也能被5整除的数有 30 / 30 = 1 个，

根据集合的容斥定律可知：A∪B∪C = A + B + C - A ∩ B - B ∩ C - A ∩ C + A ∩ B ∩ C，

因此，能被2整除或能被3整除或能被5整除的数的个数(不重复)为：15 + 10 + 6 - 5 - 3 - 2 + 1 = 22

1500 / 22 = 68 ··· 4，[ 1, 30] 中，第4个满足条件的数是 5 ，而 68 * 30 = 2040， 因此第1500个数为:2040 + 5 = 2045

13.正确答案: D     根据运算符优先级添加括号。

    a*(b-c*d)+e-f/g*(h+i*j-k)

=  a * (b - (c * d)) + e - (f / g) * (h + (i * j) - k)

=  a * (b - (cd*)) + e - (fg/) * (h + (ij*) - k)

=  a * (bcd*-) + e - (fg/) * ((hij*+) - k)

=  (abcd*-*) + e - (fg/) * (hij*+k-)

=  (abcd*-*e+) - (fg/hij*+k-*)

=  (abcd*-*e+fg/hij*+k-*-)

14.正确答案：D

哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。

在平衡二叉树中插入结点要随时保证插入后整棵二叉树是平衡的，所以可能需要通过一次或多次树旋转来重新平衡这个树。

15.正确答案：B
为方便起见，用123来示例下。123的全排列有123、132、213、231、312、321这六种。 首先考虑213和321这二个数是如何得出的。显然这二个都是123中的1与后面两数交换得到的。 然后可以将123的第二个数和每三个数交换得到132。同理可以根据213和321来得231和312。因此可以知道——      全排列就是从第一个数字起每个数分别与它后面的数字交换。   找到这个规律后，递归的代码就很容易写出来了：

//全排列的递归实现 #include #include void Swap(char *a, char *b) {     char t = *a;     *a = *b;     *b = t; } //k表示当前选取到第几个数,m表示共有多少数. void AllRange(char *pszStr, int k, int m) {     if (k == m)     {         static int s_i = 1;         printf("  第%3d个排列\t%s\n", s_i++, pszStr);     }     else     {         for (int i = k; i <= m; i++) //第i个数分别与它后面的数字交换就能得到新的排列         {             Swap(pszStr + k, pszStr + i);             AllRange(pszStr, k + 1, m);             Swap(pszStr + k, pszStr + i);         }     } } void Foo(char *pszStr) {     AllRange(pszStr, 0, strlen(pszStr) - 1); } int main() {     printf("         全排列的递归实现\n");     printf("  --by MoreWindows( http://blog.csdn.net/MoreWindows )--\n\n");     char szTextStr[] = "123";     printf("%s的全排列如下:\n", szTextStr);     Foo(szTextStr);     return 0; }

16.正确答案：B如果将各条边的权值按从小到大排序的话，权值乘以2之后的排序不变，也就是权重的相对关系不变，p仍是最短路径。

17.正确答案：C  

对于降序压栈的话，输出序列中的任意一个数的右侧小于它的数是降序排列的(刚压入的数要大于栈内的已经有的数)。对于C 选项E后面小于E的数是升序的，可判断  C   选项是错误的。

18.正确答案：D

19.正确答案: D  

25,84,21,47,15,27,68,35,20

选择排序 第一次应该为25,20,21,47,15,27,68,35,84

希尔排序，没告诉增量，猜的范围太大

归并排序    25 84 21 47

                  15  27 68  35 20 

                  15 25 27 68 35 20 84 21 47 很显然不对啊

快速排序    需要根据题目提示额 20,15,21,25,47,27,68,35,84 中枢选为 25;15,20,21, 中枢为20;35,27,47,68,84  中枢元为  47,15,  21 ,25,27,35, 中枢为27 ,68  84

20.正确答案：B   

深度为h的二叉树最多有2^h-1个节点，因此h最小取9