【选择题】 (D24 0522)

1、将N条长度均为M的有序链表进行合并，合并以后的链表也保持有序，时间复杂度为 ( A )

  A O(N * M * logN)
  B O(N*M)
  C O(N)
  D O(M)

---

2、下设栈S的初始状态为空，元素a,b,c,d,e,f依次入栈S，出栈的序列为b,d,c,f,e,a则栈S的容量至少为（ D ）

  A 6
  B 5
  C 4
  D 3

---

3、大小为MAX的循环队列中，f为当前对头元素位置，r为当前队尾元素位置(最后一个元素的位置)，则任意时刻，队列中的元素个数为 ( B )

  A r-f
  B (r-f+MAX+1)%MAX
  C r-f+1
  D (r-f+MAX)%MAX

---

4、n！后面有多少个0，比如6！= 1 * 2 * 3 * 4 * 5 * 6 = 720，720 后面有1个0，n=10000，求n！( B )

  A 2498
  B 2499
  C 2450
  D 2451

  分析：

    1-10000中能够分解成 5 * k 的形式的数字个数有10000 / 5=2000个
    把这2000个数字除以5还能写成 5 * k 的形式的数字有 2000 / 5 = 400个
    把这400个数字除以5还能写成 5 * k 的形式的数字有 400 / 5 = 80个
    把这80个数字除以5还能写成 5 * k 的形式的数字有 80 / 5 = 16个
    把这16个数字除以5还能写成 5 * k 的形式的数字有 16 / 5 = 3个
    所以共含有2000+400+80+16+3=2499个5，即10000！末尾有2499个0

---

5、若一棵二叉树具有12个度为2的结点，6个度为1的结点，则度为0的结点个数是（ C ）

  A 10
  B 11
  C 13
  D 不确定

---

6、若将关键字1，2，3，4，5，6，7 依次插入到初始为空的平衡二叉树 T 中，则 T 中平衡因子为 0 的分支结点的个数是（ D ）

  A 0
  B 1
  C 2
  D 3

---

7、已知小根堆为8,15,10,21,34,16,12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是（ C ）

  A 1
  B 2
  C 3
  D 4

---

8、已知某个哈希表的n个关键字具有相同的哈希值，如果使用二次探测再散列法将这n个关键字存入哈希表，至少要进行次探测 ( E )

  A n-1
  B n
  C n+1
  D n(n+1)
  E n(n+1)/2
  F 1+n(n+1)/2

---

9、下列选项中，不可能是快速排序第2趟排序结果的是 （ C ）

  A 2,3,5,4,6,7,9
  B 2,7,5,6,4,3,9
  ​ C 3,2,5,4,7,6,9
  D 4,2,3,5,7,6,9

---

10、设有向图G=(V,E)，顶点集 V={V0,V1,V2,V3}，边集 E={，，，}。若从顶点 V0 开始对图进行深度优先遍历，则可能得到的不同 遍历序列个数是 （ D ）

  A 2
  B 3
  C 4
  D 5

---