数据结构习题及答案

9. 在分块查找中，若用于查找表的长度为n，它被等分为若干个子表，每个子表的长度均为s，则分块查找的平均查找长度为（ ）。

A）(n+s)/2 B）(n+s)/2+1 C）(s+n/s)/2+1 D）(s+n/s)/2

10. 在分块查找中，若用于查找表的长度为144，它被等分为12个子表，每个子表的长度均为12，则分块查找的平均查找长度为（ ）。

A）12 B）24 C）13 D）79

11. 在分块查找中，若用于查找表的长度为117，它被等分为9个子表，则分块查找的平均查找长度为（ ）。

A）11 B）12 C）13 D）9

12.在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为（ ）。

A）n B）log2n C）(h+1)/2 D）h

13.从具有n个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度的为（ ）。

A）O(n) B）O(1) C）O(log2n) D）O(n)

14.从具有n个结点的二叉排序树中查找一个元素，在最坏情况下的平均查找长度是（ ）。

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

15. 若对n个元素进行插入排序，在进行第i遍排序过程前，有序表中的元素个数为（ ）。

A）i B）i+1 C）i-1 D）1

16. 若对n个元素进行插入排序，在进行第i遍排序时，为寻找插入位置，最多需要进行（ ）次元素的比较（假设第0号元素放有待查元素关键字）。

A）i B）i-1 C）1 D）i+1 17. 若对n个元素进行插入排序，在进行第i遍排序时，假设元素a[i+1]的插入位置为，a[j]，则需要移动元素的次数为（ ）。

A）j-i B）i-j-1 C）i-j D）i-j+1 18. 对n个元素进行插入排序的过程中，共需要进行（ ）遍。

A）n+1 B）n C）2n D）n-1 19. 对n个元素进行插入排序的时间复杂度为（ ）。

A）O(1) B）O(n) C）O(n) D）O(log2n)

20. 在对n个元素进行冒泡排序的过程中，第一遍排序，最多需要进行（ ）对相邻元素之间的交换。

A）n-1 B）n C）n/2 D）n+1

21. 在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度的为（ ）。

A）O(1) B）O(n) C）O(n) D）O(log2n) 22. 在对n个元素进行冒泡排序的过程中，最坏情况下的时间复杂度为（ ）。

A）O(1) B）O(n) C）O(n) D）O(log2n) 23. 在对n个元素进行冒泡排序的过程中，最少需要（ ）遍完成。

222

2

29

A）1 B）n C）n-1 D）n/2

24. 在对n个元素进行快速排序的过程中，第一次划分最多需要移动（ ）次元素，包括开始把基准元素移动到临时变量中的一次。

A）n/2 B）n-1 C）n D）n+1 25. 在对n个元素进行快速排序的过程中，最好情况下需要进行（ ）遍。

A）n B）n/2 C）log2n D）2n 26. 在对n个元素进行快速排序的过程中，最坏情况下需要进行（ ）遍。

A）n B）n/2 C）log2n D）n-1 27. 在对n个元素进行快速排序的过程中，最好情况下的时间复杂度为（ ）。

A）O(1) B）O(n) C）O(nlog2n) D）O(log2n) 28. 在对n个元素进行快速排序的过程中，最坏情况下的时间复杂度为（ ）。

A）O(1) B）O(n) C）O(nlog2n) D）O(log2n)

29. 对元素序列（3，7，5，9，1）进行快速排序，在进行第一遍划分时，需要移动元素的次数为（ ），假设不包括开始把基准元素移动到临时变量的一次。

A）1 B）2 C）3 D）4

30. 在对下列四个序列进行快速排序时，各以第一个元素为基准进行第一遍划分，则在该次划分过程中，需要移动元素次数最多的序列为（ ）。

A）1，3，5，7，9 B）9，7，5，3，1 C）5，3，1，7，9 D）5，7，9，1，3

31.对元素序列（7，3，5，9，1，12，8，15）进行快速排序，在进行第一遍划分后，得到的左区间中元素的个数为（ ）。

A）2 B）3 C）4 D）5

32. 在对n个元素进行选择排序的过程中，在第i遍，需要从（ ）个元素中选择出最小值元素。

A）n-i+1 B）n-i C）i D）i+1

33. 对n个元素进行选择排序，在进行任一遍排序的过程中，为寻找最小值元素所需要的时间复杂度量级为（ ）。

A）O(1) B）O(n2)

C）O(log2n) D）O(n)

34. 若对n个元素进行归并排序，则进行归并的遍数为（ ）。

A）n B）n/2

C）?log2n? D）n-1

35. 对n个元素进行归并排序，在进行每一遍的时间复杂度量级为（ ）。

A）O(1) B）O(n2)

C）O(log2n) D）O(n)

36. 若一个元素序列基本有序，则选用（ ）方法较快。

A）插入排序 B）选择排序

30

22

C）归并排序 D）快速排序 37. 在平均情况下，速度最快的排序方法为（ ）。

A）选择排序 B）冒泡排序 C）归并排序 D）快速排序

38. 排序方法中，从未排序序列中，依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ ）。

A）归并排序 B）冒泡排序 C）插入排序 D）选择排序

39．快速排序方法在（ ）情况下，最不利于发挥其长处。

A）要排序的数据量太大 B）要排序的数据中含有多个相同值 C）要排序的数据已基本有序 D）要排序的数据个数为奇数

40. 用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，若元素序列的变化情况如下：

1）25，84，21，47，15，27，68，35，20 2）20，15，21，25，47，27，68，35，84 3）15，20，21，25，35，27，47，68，84 4）15，20，21，25，27，35，47，68，84 则所采用的排序方法是（ ）。

A）选择排序 B）冒泡排序 C）归并排序 D）快速排序

二. 填空题

1. 查找是指在一个给定的数据结构中，查找某个 。

2. 在查找算法中，使用关键字这个术语。关键字是指数据元素（或记录）中某个数据项的值，用它可以 一个数据元素（或记录）。

3. 顺序查找方法既适用于线性表的 ，也适用于线性表的 。 4. 以顺序查找法从长度为n的顺序表中，成功查找一个元素时，平均查找长度为 ，时间复杂度的量级为 。

5. 以顺序查找法从长度为n的顺序表中，查找第i个元素的概率为pi，查找长度为ci，则在查找成功情况下的平均查找长度的计算公式为 。

6. 顺序查找长度为40的线性表，设查找每个元素的概率都相同，则在查找成功情况下的平均查找长度为 ，在查找不成功情况下的平均查找长度为 。

7. 查找要求查找表采用顺序存储结构，且表中记录按关键字大小次序排列。 8. 以折半查找法，从长度为50的有序表中查找一个元素时，其查找长度不超过 。 9. 从有序表（12，18，30，43，56，78，82，95）中，分别折半查找43和56两个元素时，其查找长度分别为 和 。

10. 折半查找所对应的判定树，是一棵 树 。

11. 设长度n=50的有序表进行折半查找，在对应的判定树高度为 ，最后一层的结点数为 。

12. 折半查找中，每进行一次，或者查找成功，或者查找 ，不像顺序查找，需要对表中记录逐一进行比较。折半查找的效率比顺序查找 。

13. 若在分块查找中，查找表长度为n，被等分的每个子表的长度为s，则进行成功查找的平均查找长度为 。

14. 在分块查找中，若查找表的长度为96，被等分为8个子表，则进行分块查找的平

31

均查找长度为 。

15. 在分块查找中，若查找表的长度为n，被等分的每个子表的长度为n，则进行成功查找的平均查找长度为 ，平均查找的时间复杂度的量级为 。

16. 在一棵二叉排序树中，每个分支结点的左子树上所有结点的值一定 该结点的值，右子树上所有结点的值一定 该结点的值。

17. 对一棵二叉排序树进行中序遍历时，得到的中序遍历序列是一个 。 18. 从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明 ，若元素的值小于根结点的值，则继续向 查找，若元素值大于根结点的值，则继续向 查找。

19. 在向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则接着向根结点的 插入，若元素的值大于根结点的值，则接着向根结点的 插入。

20. 在生成二叉排序树时，对于同样一组结点，由于结点 ，所生成的二叉排序树的形态和深度可能不同。

21. 从一棵具有n个结点的二叉排序树中，查找元素的平均时间复杂度的为 。 22. 从一棵具有n个结点的二叉排序树中，插入元素的平均时间复杂度为 。 23. 排序又称分类，是指将一个无序序列整理成 递增（或递减）的有序序列的处理过程。

24. 根据排序过程中所涉及的存储器不同，可将排序方法分为两类： 和 。 25. 冒泡排序在最坏情况下记录的原始排列为反序，要经过n-1遍排序，第1遍比较n-1次，第2遍比较n-2次，依次类推。所以，算法所需总的比较次数最多为 。

26. 冒泡排序是稳定的。冒泡排序的时间复杂度为 。

27. 按查找方式的不同，插入排序又可以分为，直接插入排序和折半插入排序，前者使用 ，后者使用 。

28. 在进行选择排序的第i遍排序时，从余下的 个记录中进行n - i次关键字的比较，选出 的记录作为有序序列中第i个记录，

29. 每次从无序子表中，取出一个元素，把它插入到有序子表中的适当位置，此种排序方法叫做 排序；每次从无序子表中挑选出一个最小元素，把它交换到有序表的一端，此种排序方法叫做 排序。

30. 每次直接或通过基准元素间接比较两个元素，若出现逆序排列时，交换它们的位置，此种排序方法叫做 排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做 排序。

31. 在直接选择排序中，记录比较次数的时间复杂度为 ，记录移动次数的时间复杂度为 。

32. 对n个记录进行冒泡排序时，最少的比较次数为 ，最少的遍数为 。 33. 快速排序在平均情况下的时间复杂度为 ，在最坏情况下的时间复杂度为 。

34. 在二路归并排序中，对n个记录进行归并的遍数为 。 35. 在归并排序中，进行一遍归并的时间复杂度为 ，整个排序过程的时间复杂度为 。

36. 对20个记录进行归并排序时，共需要进行 遍归并，在第三遍归并时，是把长度为 的有序表两两归并为长度为 的有序表。

37. 若对一组记录（46，79，56，38，40，80，35，50，74）进行直接插入排序，当把第8个记录插入到前面已排序的有序表时，为寻找插入位置需比较 次。

32