数据结构题库(5)

(A) 6 (B) 11 (C) 5 (D) 6.5

29.用线性探测法查找闭散列上，可能要探测多个散列地址，这些位置上的键值( D )

A.一定都是同义词 B.一定都不是同义词 C.都相同 D.不一定都是同义词 30.二分查找要求被查找的表是( C )

A.键值有序的链接表 B.链接表但键值不一定有序表 C.键值有序的顺序表 D.顺序表但键值不一定有序表

31.如果要求一个线性表既能较快的查找，有能适应动态变化的要求，则可采用（A）查找法 A. 分块查找 B. 顺序查找 C. 折半查找 D. 基于属性 32.折半查找的时间复杂性为（D）

A. O (n2) B. O (n) C. O(nlogn） D. O(logn) 33.下面描述不正确的是（ D ）

A.顺序查找对表中元素存放位置无任何要求，当n较大时，效率低。 B.静态查找表中关键字有序时，可用二分查找。 C.分块查找也是一种静态查找表。

D.经常进行插入和删除操作时可以采用二分查找。 34． 二分查找要求被查找的表是（C ）

A、 键值有序的链接表 B、链接表但键值不一定有序 C、 键值有序的顺序表 D、顺序表但键值不一定有序 35.下列数据结构中，能用二分法进行查找的是( A ) A)顺序存储的有序线性表 B)线性链表 C)二叉链表 D)有序线性链表

第八章排序

1．某内排序方法的稳定性是指( D )。 A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法 D．以上都不对

2．下面给出的四种排序法中( D )排序法是不稳定性排序法。 A. 插入 B. 冒泡 C. 二路归并 D. 堆 3．下列排序算法中，其中（ D ）是稳定的。

A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 4．稳定的排序方法是（ B ）

A．直接插入排序和快速排序 B．折半插入排序和起泡排序 C．简单选择排序和四路归并排序 D．树形选择排序和shell排序

5．下列排序方法中，哪一个是稳定的排序方法？（ B ）

A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序 6．若要求尽可能快地对序列进行稳定的排序，则应选（B） A．快速排序 B．归并排序 C．冒泡排序 D.堆排序

7．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ A ）排序为宜。 A．直接插入 B．直接选择 C．堆 D．快速 E．基数

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

A. 快速排序 B. 堆排序

C. 归并排序 D. 直接插入排序

9.下面的排序算法中，不稳定的是（ D ）

A.起泡排序 B.折半插入排序 C. 基数排序 D. 堆排序

10.一组记录得关键字为（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

11在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（D ）。

A．直接插入排序 B. 气泡排序 C. 快速排序 D. 直接选择排序 12．比较次数与排序的初始状态无关的排序方法是( D )。

A．直接插入排序 B．起泡排序 C．快速排序 D．简单选择排序 13．数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的( C )的两趟排序后的结果。

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

14．数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的( A )的两趟排序后的结果。

A. 快速排序 B. 冒泡排序 C. 选择排序 D. 插入排序 15．对一组数据（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. 插入

16．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（ C ）排序。

A. 选择 B. 快速 C. 希尔 D. 冒泡 17．若上题的数据经一趟排序后的排列为{9，15，7，8，20，-1，4}，则采用的是（C ）排序。

A．选择 B. 堆 C. 直接插入 D. 冒泡

18．下列排序算法中( B )不能保证每趟排序至少能将一个元素放到其最终的位置上。 A.快速排序 B. shell排序 C. 堆排序 D.冒泡排序 19．下列排序算法中( C )排序在一趟结束后不一定能选出一个元素放在其最终位置上。 A. 选择 B. 冒泡 C. 归并 D. 堆 20.设一组初始记录关键字序列为（345，253，674，924，627），则用基数排序需要进行（A）趟的分配和回收才能使得初始关键字变成有序序列。

A、3 B、4 C、5 D、8 21.下面四种排序中（A）的空间复杂度最大。

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

22.用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下，则所采用的排序方法是（ D ）。

20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84

A.选择排序 B.希尔排序 C.归并排序 D.快速排序 23.插入排序在（ B ）情况下效率最高。

A.被排序的数据中有多个相同的数据元素 B.被排序的数据已基本有序 C.被排序的数据完全无序 D.被排序的数据中最大值和最小值相差悬殊 24.下列排序算法中，在初始数据有序时，花费的时间反而最多是（ C ）。 A.堆排序 B.冒泡排序 C.快速排序 D.希尔排序

25.从未排序序列中选择一个元素，该元素将未排序序列分成前后两个部分，前一部分中所有元素都小于等于所选元素。后一部分中所有元素都大于等于所选元素，而所选元素处在排序的最终位置。这种排序方法称为（ C ）排序法。

A.插入排序 B.希尔排序 C.快速排序 D.堆排序 26.快速排序在（ C ）情况下效率最高。

A.被排序的数据中有多个相同的数据元素 B.被排序的数据已基本有序 C.被排序的数据完全无序 D.被排序的数据中最大值和最小值相差悬殊 27.在下列方法中，排序所花时间不受初始数据排列特征影响的算法是（ B ）。 A.直接插入排序 B.简单选择排序 C.快速排序 D.都不是 28.直接插入排序的算法复杂性是（ A ）。

A.O（n2） B.O（nlogn） C.O(n) D.O(logn) 29.若一组记录的排序码为（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 30.置换选择排序的功能是（C）。（置换选择排序＝简单选择排序？）

A.选出最大的元素 B.产生初始归并段 C.产生有序文件 D.置换某个记录

31.将5个不同的数据进行排序，至少需要比较（A）次。 A. 4 B. 5 C.6 D. 7

32.下列排序算法中，占用辅助空间最多的是：( A )

A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序 33. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（ C ）次比较。

A. 3 B. 10 C. 15 D. 25

34.设哈希表长为14，哈希函数是H(key)=key,表中已有数据的关键字为15，38，61，84共四个现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )。D A．8 B．3 C．5 D．9

35.假定哈希查找中k个关键字具有同一哈希值，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( )D

A．k-1次 B. k次 C. k+1次 D. k（k+1）/2次 36.好的哈希函数有一个共同的性质，即函数值应当以( )取其值域的每个值。D A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率

37. 将10个元素散列到100000个单元的哈希表中，则（ ）产生冲突。C A. 一定会 B. 一定不会 C. 仍可能会 38．从末排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为（）排序法。A A.插入 B.选择 C.希尔 D.二路归并

39．下面各种排序方法中，最好情况下时间复杂度为O(n)的是( )B A.快速排序 B.直接插入排序 C.堆排序 D.归并排序

40．排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为( C ) 。

A．希尔排序 B。冒泡排序 C插入排序 D。选择排序. 41.堆排序是一种（B）排序。

A 插入 B 选择 C 交换 D 归并

42.下列排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关？（B） A．直接插入排序 B．直接选择排序 C. 快速排序 D.起泡排序

第一章绪论

1．线性表在物理存储空间中也一定是连续的。（×）

2．算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。（×） 3．数据的逻辑结构与数据元素本身的内容和形式无关。（√）

4．一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（√） 5．数据元素是数据的最小单位。（√）

6．数据的逻辑结构和数据的存储结构是相同的。（×）

7．从逻辑关系上讲，数据结构主要分为线性结构和非线性结构。（√）

8．数据是信息的载体，是描述客观事物的数、字符以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。（√）

9．递归过程简单、易编。易懂，然而，递归过程效率低，重复次数多。（√） 10．算法的时间复杂度是指执行算法所需要的计算工作量（√） 11．数据结构的物理结构是指数据在计算机内的实际存储形式（√）

12．一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率（×） 13．算法的效率只与问题的规模有关，而与数据的存储结构无关.（×）

14．每一次递归调用，需要为过程中使用的参数、局部变量等另外分配存储空间，每个过程的工作空间互不干扰，回到上层还可恢复上层原来的值.（√）

15．同一种逻辑结构才用不同的存储方式，可以得到相同的存储结构（×） 16．插入是指把新元素按照指定位置插入到数据结构的一个实例内，并保持数据结构的原有性质。（√）

17．指针型变量储存的是数据元素的内容，而不是数据元素的地址。（╳） 18．递推法的基本思想是从前面的一些量推出后面的一些量。（√） 19．一旦数据空间占满，再加入新的数据就将产生溢出，此时储存空间一定可以扩充。（╳） 20．算法可以没有输入，但是必须有输出。(√）

21．在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法。（×） 22．每种数据结构都应具备三种基本运算：插入、删除、搜索。（×）

23．同一种逻辑结构采用不同的存储方式，可以得到相同的存储结构（×） 24．任何一个递归过程都可以转换成非递归过程。(√） 25．数据的逻辑结构与数据元素本身的类容和形式无关。（√） 26．算法可以没有输入，但必须有输出。（√） 27．递归程序转换为非递归程序必须用到栈。(×)

28．在决定选取何种存储结构时，一般不考虑各结点的值如何。（√）

29．抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。（√） 30．抽象数据类型与计算机内部表示和实现无关。（√）

31．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（×） 32．对任何数据结构链式存储结构一定优于顺序存储结构。（×） 33．顺序存储方式只能用于存储线性结构。（×） 34．集合与线性表的区别在于是否按关键字排序。（×）

35．数据的逻辑结构是指数据的各数据项之间的逻辑关系?（×）

36．数据结构涉及数据的逻辑结构、存储结构和施加其上的操作共三个方面。（√） 37．数据结构的操作的实现与存储结构有关。（√）

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构题库(5)在线全文阅读。