清华大学《数据结构与算法》(2)

49. 下面关于二分查找的叙述正确的是 ( D )

A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列

B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储

50. 二叉查找树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。

CC

51. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（ B ）

A)深度优先搜索算法 B)广度优先搜索算法

C)求最小生成树的prim算法

D)拓扑排序算法

52. 既希望较快的查找又便于线性表动态变化的查找方法是 ( C ) A．顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法查找

53. 对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为( C )

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

54. 对于哈希函数H(key)=key,被称为同义词的关键字是( D )

A)35和41 B)23和39

C)15和44 D)25和51

55. 某内排序方法的稳定性是指( D)。

A．该排序算法不允许有相同的关键字记录

B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法 D．以上都不对

56. 下列内部排序算法中：

A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序

（1） 其比较次数与序列初态无关的算法是（ ） （2）不稳定的排序算法是（ ） （3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<

（4）排序的平均时间复杂度为O(n?logn)的算法是（ ）为O(n?n)的算法是（ ） 1 DC 2 ADF 应是AF 3 B 4 ACF BDE

57. 下列排序算法中(C )排序在一趟结束后不一定能选出一个元素放在其最终位置上。

A. 选择 B. 冒泡 C. 归并 D. 堆

58. 栈和队列都是（ A ）

A)限制存取位置的线性结构 C)顺序存储的线性结构

B)链式存储的非线性结构 D)限制存取位置的非线性结构

59. 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ B ）。

A. (2,5,12,16)26(60,32,72) B. (5,16,2,12)28(60,32,72)

C. (2,16,12,5)28(60,32,72) D. (5,16,2,12)28(32,60,72)

60. 一棵含有n个节点的k叉树，可能达到的最小深度为多少？（ C ） A) n-k B) n-k+1 C) |logkn|+1 D) |logkn| 其中|k|表示下取整

61. 下列序列中( B )不是堆。

A) 12 36 53 68 48 60 75 B) 12 48 53 68 36 60 75 C) 12 48 36 60 75 68 53 D) 12 36 60 53 48 68 75

62. 在下列内排序方法中，( C )的平均时间复杂性是O(nlogn)。

A) 直接插入排序 B) 简单选择排序 C) 快速排序 D) 希尔排序

63. 设顺序栈s非空，则语句段( C )可实现栈s的出栈操作，其中s.top为栈顶指针，s.elem为栈空间，出栈的元素存放在x中。

A) s.top:=s.top+1; B) x:=s.elem[s.top]; x:=s.elem[s.top]; s.top:=s.top+1;

C) s.top:=s.top-1; D) x:=s.elem[s.top];

x:=s.elem[s.top]; s.top:=s.top-1;

64. 有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为 （ C ）

A．-1，4，8，9，20，7，15，7 B．-1，7，15，7，4，8，20，9

C．-1，4，7，8，20，15，7，9 D．A，B，C均不对。

65. 下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ D ）。 A)二叉排序树 B)哈夫曼树

C)AVL树 D)堆

66. 下面给出的四种排序法中( D )排序法是不稳定性排序法。

A) 插入 B) 冒泡 C) 二路归并 D) 快速排序

67. 算法的时间复杂度取决于（ A ）

A．问题的规模 B. 待处理数据的初态 C. A和B D. 计算机cpu

68. 有关静态链表的叙述：(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（ B ）

A．（1），（2） B．（1） C．（1），（2）,(3) D.（2）

69．一个栈的输入序列为123?n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ B ）。

A. 不确定 B. n-i+1 C. i D. n-i

70．下面关于串的的叙述中，哪一个是不正确的？（ B ）

A．串是字符的有限序列 B．空串是由空格构成的串

C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储

71. 关于二叉树的叙述：①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。正确的是（ D ）

A．①②③ B．②③④ C．②④ D．①④

72．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( A )。

A．逆拓扑有序 B．拓扑有序 C．无序的

73. 对n个关键字的序列进行快速排序，平均情况下的空间复杂度为( B ) A.O(1) B.O(logn) C.O(n) D.O(n logn)

二 填空题

1、在单链表L中，指针p所指结点有后继结点的条件是：

p->next!=null

2、n（n大于1）个结点的各棵树中，其深度最小的那棵树的深度是_(1)__。它共有_(2)__个叶子结点和_(3)__个非叶子结点，其中深度最大的那棵树的深度是_(4)__，它共有_(5)__个叶子结点和_(6)__个非叶子结点。

(1)2 (2) n-1 (3) 1 (4) n (5) 1 (6) n-1

3、深度为9的完全二叉树最多有 个结点

256 应是 511

4、二叉树由_(1)__，__(2)_，_(3)__三个基本单元组成。 .(1)根结点(2)左子树(3)右子树

5、先根遍历树林正好等同于按__ _遍历对应的二叉树. 先序

6、设只含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为______,最小结点数为______。

(1) 2-1 (2) k+1

7、在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素， …… 此处隐藏：4546字，全部文档内容请下载后查看。喜欢就下载吧 ……