数据结构复习题(2)

…………….……………..装……………………订………………..线…………….…………….. 课程 共 20 页，第6页，共印刷 份, — 年 月 日 考试，任课教师

105.已知一个长度为16 的顺序表L,其元素按关键字有序排列,若采用折半查找法查找一个不存在112.为提高散列（HASH）表的查找效率，可以采取的正确措施是（D） 的元素,则比较次数最多的是(B)

A.4

B.5 C.6 D.7

I．增大装填（载）因子

II．设计冲突（碰撞）少的散列函数

III．处理冲突（碰撞）时避免产生聚集（堆积）现象 A．仅I B．仅II C．仅I、II D．仅II、III 113.为实现快速排序算法，待排序序列宜采用的存储方式是（A）

A．顺序存储 B.散列存储 C.链式存储 D.索引存储

计算机与信息 学院 信息工程、计科 专业 数据结构 106.采用递归方式对顺序表进行快速排序,下列关于递归次数的叙述中,正确的是(D)

A.递归次数于初始数据的排列次数无关

B.每次划分后,先处理较长的分区可以减少递归次数 C.每次划分后,先处理较短的分区可以减少递归次数 D.递归次数与每次划分后得到的分区处理顺序无关

107.对一组数据(2,12,16,88,5,10)进行排序,若前三趟排序结果如下:

第一趟:2,12,16,5,10,88 第二趟:2,12,5,10,16,88 第三趟:2,5,10,12,16,88 则采用的排序方法可能是( A)

A.冒泡排序法 B.希尔排序法 C.归并排序法 D.基数排序法

108.对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（A）

A．95，22，91，24，94，71 B．92，20，91，34，88，35 C．21，89，77，29，36，38 D．12，25，71，68，33，34 109.下列关于图的叙述中，正确的是（C）。

I．回路是简单路径

II．存储稀疏图，用邻接矩阵比邻接表更省空间 III．若有向图中存在拓扑序列，则该图不存在回路 A．仅II B．仅I、II C．仅III D．仅I、III 110.判断有向图是否有回路，除了可以用拓扑排序外，还可以用（ ）。

A．求关键路径的方法 C．求最短路径的方法

B．广度优先遍历算法 D．深度优先遍历算法

114.已知序列25，13，10，12，9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是（B）

A．1 B.2 C.4 D. 5 115.某内排序方法的稳定性是指( D)。

A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法 D．以上都不对 116.下面给出的四种排序法中( D )排序法是不稳定性排序法。

A. 插入 B. 冒泡 C. 二路归并 D. 堆积 117.下列排序算法中，其中（ D）是稳定的。

A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序

118.若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（C ）。

A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序 119.数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的( C)的两趟排序后的结果。

A．选择排序 B.冒泡排序 C.插入排序 D.堆排序

120.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为 （1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是 ( A )。

A. 选择 B. 冒泡 C. 快速 D. 插入

121.下列排序算法中( B)不能保证每趟排序至少能将一个元素放到其最终的位置上。 A.快速排序 B. shell排序 C. 堆排序 D.冒泡排序

111.任何一个带权无向连通图的最小生成树是（ C）

A．一定是唯一的

B．一定不唯一的 D．有可能不存在的

C．有可能不唯一的

计算机与信息 学院 信息工程、计科 专业 数据结构 课程 共 20 页，第 7 页，共印刷 份, 年 月 日 考试，任课教师 …………….……………..装……………………订………………..线…………….…………….. 122.一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ C ）。

A．(38,40,46,56,79,84) B. (40,38,46,79,56,84) C．(40,38,46,56,79,84) D. (40,38,46,84,56,79) 123.在下面的排序方法中，辅助空间为O（n）的是( D) 。

A．希尔排序 B. 堆排序 C. 选择排序 D. 归并排序 124.下列排序算法中，在待排序数据已有序时，花费时间反而最多的是(C)排序。

A． 冒泡 B. 希尔 C. 快速 D. 堆

125.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ D）方法最快。

A．起泡排序 B．快速排列 C．Shell排序 D．堆排序

126.如果在构造哈希表时采用链地址法解决冲突，且啥希函数为H(key)=key MOD 8则需要建造的链表数目是（ ）

A．6

B．5

C．8

D．9

132.堆排序是一种( B )排序。

Ａ. 插入 Ｂ.选择 Ｃ. 交换 Ｄ. 归并

133.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( D )

A．k-1次 B. k次 C. k+1次 D. k（k+1）/2次 134.下列二叉排序树中，满足平衡二叉树定义的是（B）

135.下列关于无向连通图特性的叙述中，正确的是（A ）

I．所有顶点的度之和为偶数 II.边数大于顶点个数减1 III.至少有一个顶点的度为1

A.只有I B. 只有II C.I 和II D.I 和III

136.在下列所示的平衡二叉树中插入关键字48 后得到一棵新平衡二叉树,在新平衡二叉 树中,关键字37 所在结点的左、右子结点中保存的关键字分别是(C) A.13,48

B.24,48

C.24,53

D.24,90

127.下列因素中，影响排序算法稳定性关键因素是（B）。

I．待排元素个数的多少

II.排序过程中是否发生了不相邻元素的交换 III.是否有关键码相同的元素 IV.排序算法是否采用递归方式实现

A．仅I B．仅II C．I和III D．I和IV

128.用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（ C）。

A． 94,32,40,90,80,46,21,69 B． 32,40,21,46,69,94,90,80

129.对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l，4，137.用序列｛12，13，11，18，60，15，7，18，25，84｝构建初始堆，必须从关键字为（ ）8，20，9，7}则该次采用的增量是 ( B ) 的结点开始。

A. l B. 4 C. 3 D. 2 130.下列四个序列中，哪一个是堆（ C）。

A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15 C. 75,45,65,30,15,25,20,10 D. 75,45,65,1 …… 此处隐藏：8041字，全部文档内容请下载后查看。喜欢就下载吧 ……