数据结构期末考经典易错题_设一棵m叉树的结点数为n,用多重链表表示

4．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（ 1）

5．设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（ 0）

6．层次遍历初始堆可以得到一个有序的序列。（0）

2．当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（  1）

8.  不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。（ 1 ）

14.设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（  ）。

   (A)O(n)         (B) O(n2)       (C) O(nlog2n)   (D) O(1og2n)

 

10.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（  ）。

解：n个结点的的判定树的深度与完全二叉树深度同  log2n+1

   (A)log2n+1      (B) log2n-1     (C) log2n       (D) log2(n+1)

9. 设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做（  ）次线性探测。

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

11.设一组初始记录关键字的长度为8，则最多经过（  ）趟插入排序可以得到有序序列。

   (A)6            (B) 7           (C) 8           (D) 9

1.  设需要对5个不同的记录关键字进行排序，则至少需要比较___ _ 4 __________次，至多需要比较_____ _10_______次。

n-1

1+2+3+。。。+n-1

解：首先随便选择一个数为基数，再选择一个数和它比较就是1次，选择第三个数最多比较2次就可以确定它的位置，选择第四个数最多比较3次也就能够确定它的位置，最后一个数最多 比较4次同样可以确定它的位置了。1+2+3+4=10.

5.  设一棵m叉树脂的结点数为n，用多重链表表示其存储结构，则该树中有___ n(m-1)+1 ____个空指针域。

8.  设无向图G中有n个顶点e条边，则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为_ O(n2) ______；用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为__ O(n+e) _______。

11.设顺序表的长度为n，则顺序查找的平均比较次数为（  ）。

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

 

2．  设某棵完全二叉树中有100个结点，则该二叉树中有____50_________个叶子结点。100-1=99  50=49+1

6.  设一棵完全二叉树有128个结点，则该完全二叉树的深度为__8______，有______64____个叶子结点。

10.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（  ）。

解：n个结点的的判定树的深度与完全二叉树深度同  log2n+1

   (A)log2n+1      (B) log2n-1     (C) log2n       (D) log2(n+1)

8.  设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较_7______次就可以断定数据元素X是否在查找表中。2^7=128

log2n+1  取整

1个元素的时候比较1次
2~3个元素比较2次
4~7个元素比较3次
8~15 4
16~31 5
32~63 6
64~127 7
128~255 8
256~511 9
512~1023 10

3．  设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储_____ m-1__队列元素。

5.  在二叉排序树中插入一个关键字值的平均时间复杂度为（  ）。

在二叉排序树中插入一个结点的时间复杂度为（O(n) 最差 ）

    (A)O(n)        (B) O(1og2n)    (C) O(nlog2n)   (D) O(n2)

 

8. 设某强连通图中有n个顶点，则该强连通图中至少有（  ）条边。

解：有向图 环

   (A)n(n-1)       (B) n+1         (C) n           (D)n(n+1)

4.  设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（  ）。

解：实践 证明，当P取小于哈希表长的最大质数时，产生的哈希函数较好

    (A)99          (B) 97          (C) 91          (D) 93

 

8．下列四种排序中（  ）的空间复杂度最大。

   (A)快速排序     (B) 冒泡排序    (C) 希尔排序    (D) 堆

7．设用链表作为栈的存储结构则退栈操作（  ）。

   (A) 必须判别栈是否为满           (B) 必须判别栈是否为空

   (C)判别栈元素的类型             (D) 对栈不作任何判别

5．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（  ）。

解： DLR   LRD

   (A)空或只有一个结点             (B) 高度等于其结点数

   (C)任一结点无左孩子             (D) 任一结点无右孩子

3．设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（   ）。

解：二叉树到森林 去掉左孩子的右孩子，右孩子的右孩子，于左孩子的双亲相连，T1为二叉树剩余的左孩子和根结点，N1-1即为左子树的结点数

   (A) N1-1         (B) N2-1        (C) N2+N3       (D) N1+N3