【复习】数据结构选择题

本是古典 何须时尚 2023-06-19 11:00 7阅读 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;

  1. N = M+1;设度为0的节点有X个;则:
  2. M = 12*2+6*1
  3. N = 12+6+x;
  4. 18+x = 31;
  5. x=13;

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

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不对。

发表评论

表情:
评论列表 (有 0 条评论,7人围观)

还没有评论,来说两句吧...

相关阅读

    相关 数据结构选择题

    1.【问题】采用邻接表存储的图的广度优先遍历算法类似于二叉树的 \_ 。 A.先序遍历 B.中序遍历 C.后序遍历 D.按层遍历 【答案】D 2.【问题】