【复习】数据结构选择题

本是古典何须时尚 2023-06-19 11:00 11阅读 0赞

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

*  step1：取每个链表第一个元素，组成一个数组，然后对数组排序：时间复杂度：O(NlogN)
 *  step2：然后取排序后数组的第一个节点，作为新链表的第一个节点。
 *  step3：从被取出节点的某链表中取出下一个节点，插入到数组中，二叉搜索，时间复杂度O(logN)
 *  step4：依次重复2、3步骤，因为剩下(M - 1) \* N个节点，大约重复(M - 1) \* N次
    
    所以最终的时间复杂度：  
    O(NlogN) + (M - 1) \* N \* O(logN)  
    = M \* N \* O(logN)

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

*  教材上说的（也是大家记住的）求**队列公式**为：**（rear-front+Max）%Max**； 该公式中的**rear指向队尾元素的下一个位置** ，而本题中 r指向队尾元素位置
 *  (r-f+MAX+1)%MAX（因为是循环队列，假设当对头走到6，队尾走到1，MAX为10，就需要取余操作）

**3.n！后面有多少个0, `6！=1*2*3*4*5*6 = 720.720` 后面有1个0，n=10000，求n！（）。**

*  10000/5=2000 有2000个能被5整除
 *  2000/5=400 这2000个里面能被5整除有400个  
    （2000个已被5除过1次。能除第二次的有400）
 *  400/5=80
 *  同理 80个 80/5=16  
    同理 16个16/5=3余1  
    同理 3个结果**2000+400+80+16+3=2499**

**4.若一棵二叉树具有12个度为2的结点，6个度为1的结点，则度为0的结点个数是（）。**

二叉树的分支数（度）M和节点数N存在以下关系： 节点数=总度数+1；

N = M+1;设度为0的节点有X个；则：  
    M = 12*2+6*1；
    N = 12+6+x;   
    18+x = 31;   
    x=13;

**5.若将关键字1，2，3，4，5，6，7 依次插入到初始为空的平衡二叉树 T 中，则 T 中平衡因子为 0 的分支结点的个数是（ ）。**  
![计算平衡二叉树的分支节点][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTA2MDA5_size_16_color_FFFFFF_t_70]

**6.已知某个哈希表的n个关键字具有相同的哈希值，如果使用二次探测再散列法将这n个关键字存入哈希表，至少要进行\_\_\_\_次探测。**

*  问的是“**至少**”，那么设表原来为空表。
 *  第一个：直接找到坑，入坑，1次；  
    第二个：和第一个同hash，找到坑被第一个给占了，找下一个，入坑，2次；  
    第三个：第一个被占了，第二个也被占了，找第三个，入坑，3次； 。。。  
    第n个：n次；
 *  一共：（1+n）\*n / 2 次

【二次探测属于开放地址法，开放地址法（除了随机探测）都是（1+n）\*n / 2 次】

**7.下列选项中，不可能是快速排序第2趟排序结果的是 （）**

*  **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**

**四个选项都是同样的数组元素，若完全有序，应为2345679**

*  每经过一趟快排，轴点元素都必然就位，也就是说，**一趟下来至少有1个元素在其最终位置**。所以考察各个选项，看有几个元素就位即可。
 *  A：2、3、6、7、9
 *  B：2、9
 *  C：9
 *  D：5、9 第二趟至少应有2个元素就位，所以C不对。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTA2MDA5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191205214205349.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTA2MDA5,size_16,color_FFFFFF,t_70