奥鹏2014秋大连理工大学《数据结构》在线作业3答案

大工14秋《数据结构》在线作业3
一、单选题(共10道试题,共50分。)
V
1.下列排序算法中(B)不能保证每趟排序至少能将一个元素放到其最终的位置上。
A.快速排序
B.shell排序
C.堆排序
D.冒泡排序
满分:5分
2.一组记录的关键码为(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)
满分:5分
3.将10个元素散列到100000个单元的哈希表中,则(C)产生冲突。
A.一定会
B.一定不会
C.仍可能会
D.以上都不对
满分:5分
4.快速排序方法在(D)情况下最不利于发挥其长处。
A.要排序的数据量太大
B.要排序的数据中含有多个相同值
C.要排序的数据个数为奇数
D.要排序的数据已基本有序
满分:5分
5.若查找每个记录的概率均等,则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录,对成功的查找,其平均查找长度为(C)。
A.(n-1)/2
B.n/2
C.(n+1)/2
D.n
满分:5分
6.散列表的地址区间为0-17,散列函数为H(K)=Kmod17。采用线性探测法处理冲突,并将关键字序列26,25,72,38,8,18,59依次存储到散列表中。存放元素59需要搜索的次数是(C)。
A.2
B.3
C.4
D.5
满分:5分
7.运用直接插入排序方法对下面四个序列进行从小到大排序,元素比较次数最少的是(D)。
A.90,69,80,46,21,40
B.40,21,46,69,90,80
C.90,80,69,46,40,21
D.21,40,46,69,80,90
满分:5分
8.二分法查找,要求线性表一定是(C)。
A.顺序存储的无序表
B.链式存储的无序表
C.顺序存储的有序表
D.链式存储的有序表
满分:5分
9.若要求排序是稳定的,且关键字为实数,则在下列排序方法中应选(A)排序为宜。
A.直接插入
B.直接选择
C.堆
D.快速
满分:5分
10.采用简单选择排序,比较次数与移动次数分别为(C)。
A.O(n),O(logn)
B.O(logn),0(n*n)
C.0(n*n),0(n)
D.0(nlogn),0(n)
二、判断题(共10道试题,共50分。)
V
1.直接插入排序是不稳定性排序法。(A)
A.错误
B.正确
满分:5分
2.快速排序是稳定的排序方法。(A)
A.错误
B.正确
满分:5分
3.堆是完全二叉树。(B)
A.错误
B.正确
满分:5分
4.从未排序序列中挑选元素,并将其依次放入已排序序列(初始时为空)一端的方法,称为希尔排序。(A)
A.错误
B.正确
满分:5分
5.合并排序是利用“合并”方法来进行排序。合并是将两个或多个有序表进行合并,得到一个有序表。(B)
A.错误
B.正确
满分:5分
6.存储在磁带上的顺序文件的查找只能用顺序查找。(B)
A.错误
B.正确
满分:5分
7.散列文件的基本存储单位是页块。(A)
A.错误
B.正确
满分:5分
8.交换排序的基本思想是两两比较待排序记录的排序码,并交换不满足顺序要求的那些偶对,直到全部满足顺序要求为止。(B)
A.错误
B.正确
满分:5分
9.用冒泡排序的方法对n个数据进行排序,第一趟共比较n-1对元素。(B)
A.错误
B.正确
满分:5分
10.通常,磁带只适合于存储散列文件。(A)
A.错误
B.正确