数据结构题库(8)

第七章查找

1．如果两个关键字的值不等但散列函数值相等，则称这两个关键字为同义词。（√）

2．分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。（√）

3．散列法存储的思想是由关键字值决定数据的存储地址。（√） 4．“顺序查找法”是指在顺序表上进行查找的方法。（×）

5．采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（ 对 ） 6．在散列检索中，“比较”操作一般也是不可避免的。（ 对 ） 7．Hash表的平均查找长度与处理冲突的方法无关。 （ 错 ） 8．散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。（ 对 ）

9．在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（ 对 ）

10．就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（ 错 ） 11．用单链表表示的有序表可以使用折半查找方法来提高查找速度。( 错 ) 12．折半查找方法适用于按值有序的线性链表的查找。( 错 ) 13．折半查找方法适用于按值有序的顺序表的查找。( 错 )

14．哈希表的查找效率主要取决于所选择的哈希函数与处理冲突的方法和装填因子。( 对 )

15．折半查找方法适用于按值有序的顺序链表的查找。( 错 ) 16．在顺序表中按值查找运算的复杂性为O(1)。（错误） 17．如果有序顺序表中各个元素的查找概率不相等，则折半查找的查找性能就不一定最优了。 （对）

18．散列表是一种直接计算元素存放地址的方法。 （对）

19．在静态环境下，查找结构在执行插入和删除等操作的前后部发生改变。 （对） 20．在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的 平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为 n/2 （ 错 ）。 21．设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度O(n)，在链式存储结构上实现顺序查找的平均时间复杂度为O(n)。( 对 )

22．在各种查找方法中，平均查找长度与结点个数n无关的查找方法是散列查找。（）√ 23．折半搜索与二叉搜索树的时间性能有时不相同（）。√

24．在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找（）。√ 25．折半查找只适用于有序表，包括有序的顺序表和链表。（错） 26．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用分块查找查找法。（）√

27．顺序查找适用于顺序表也适用于线性链表。（）√ 28．查找就是在数据结合中寻找满足条件的数据元素。（）√

29．当记录个数n很大时，可以采用索引结构来实现查找和存储。（）√ 30．实施查找时有两种不同的环境：静态环境，动态环境。（）√ 31．折半查找又称为二分查找，对分查找。（）√

32．为了一开始就根据给定的值直接逼近要查找的位置，可以采用插值查找（）√ 33．衡量一个查找算法的时间效率的标准是：在查找过程中关键字的平均比较次数。（）√

第八章排序

1．在待排序的元素序列基本有序的前提下，效率最高的排序方法是选择排序。（×) 2．冒泡排序算法关键字比较的次数与记录的初始排列次序无关。（×） 3．快速排序时不稳定排序。（√）

4．内部排序是指排序过程在内存中进行的排序。（√）

5．当待排序序列初始有序时，简单选择排序的时间复杂性为O(n)。（×）

6．向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（√） 7．二路归并时，被归并的两个子序列中的关键字个数一定要相等。（×） 8．堆排序所需的时间与待排序的记录个数无关。(×)

9．按某关键字对记录序列排序，若关键字相等的记录在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。(√)

10．在对一组记录(55,39,97,22,16,73,65,47,88)进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较4次。(×) 11．堆排序是一种交换排序。（×）

12．在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，称这种排序为稳定排序。(√)

13．快速排序的枢轴元素可以任意选定。（√）

14．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。（ √ ）

15．内排序要求数据一定要以顺序方式存储。 （ × ） 16．排序算法中的比较次数与初始元素序列的排列无关。（×）

17．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ × ） 18．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（ ×）

19．直接选择排序算法在最好情况下的时间复杂度为O（N）。（×） 20．两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（×） 21．在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n )。（ × ） 22．在待排数据基本有序的情况下，快速排序效果最好。（ × ）

23．当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。（ × ）

24．快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。（ 错 ） 25．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ 对 ） 26．堆排序是稳定的排序方法。（ 错 ） 27．归并排序辅助存储为O（1）。（ 错 ）

28．在分配排序时，最高位优先分配法比最低位优先分配法简单。（错 ）

29．冒泡排序和快速排序都是基于交换两个逆序元素的排序方法,冒泡排序算法的最坏时间复杂性是O(n*n),而快速排序算法的最坏时间复杂性是O(nlog2n),所以快速排序比冒泡排序算法效率更高。 （ 错 ）

30．快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n)。（错 ） 31．非空二叉排序树的任意一棵子树也是二叉排序树。( 对 ) 32．内部排序是指排序过程在内存中完成的排序。( 对 ) 33．直接插入排序的最好情况是数据元素基本有序。( 对 )

34．快速排序的最好情况是数据元素基本有序。( 错 ) 35．快速排序是稳定的排序方法。( 错 ) 36．冒泡排序是稳定的排序方法。( 对 ) 37．冒泡排序属于插入类排序。( 错 ) 38．直接插入排序是不稳定的排序方法。（错） 39．设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用归并排序 方法可以达到此目的 （ 错 ）

40．快速排序在所有排序方法中最快，而且所需附加空间也最少。（错）

三、填空题 （1）绪论

1. 数据结构的存储结构包括顺序、链接 、索引和散列等四种。 2. 在长度为n的顺序表中删除一个元素时,等概率情况下的平均移动元素的次数是(n-1)/2。

3. 结构中的数据元素存在多对多的关系称图状 （网状）结构。 4. 把数据存储到计算机中,并具体体现数据之间的逻辑结构称为物理（存储）结构。

5. 算法的时间复杂度与问题的规模 有关. 6. 在所有的数据结构中，最简单的是线性结构。

7. 数据结构包括数据的逻辑结构、存储结构和运算（或基本操作）三个方面的内容。

8. 数据项是数据中不可分割的最小单位；数据元素是数据集合中的一个“个体”，是计算机程序中加工处理的基本单位。

9. 线性结构中元素之间存在一对一关系，树形结构中元素间存在一对多关系，图形结构 中元素之间存在多对多关系。

10. 数据结构有二层结构：逻辑结构和存储结构 两种结构。 11. 描述顺序表的存储表示有两种：静态方式和动态方式。 12. 在一个长度为n的顺序表中删除第i个元素时，需向前移动n－i个元素。

（2）线性表

1. 在单链表中, 除了表头结点外, 任意结点的存储位置由其直接前驱结点的指针域的值所指示。

2. 在带有头结点的单链表L中，若要删除第一个结点，则需执行下列三条语句：U=L - > next；L->next=U->next；free(U)；

3，顺序表是线性表的连续的存储表示。

4. 在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head= p－＞next－＞next 。

5. 向一个长度为n的顺序表中揷个第i个元素（1≤i≤n）时，需向后移动n-i+1个元素。

6. 在一个单链表中删除p所指结点的后继结点时，应执行以下操作： q= p->next; p->next= q->next ;free(q ) ; 7. 线性表的顺序存储结构特点是表中逻辑关系相邻的元素在机器内的位置也是相邻的。

8. 在顺序表中插入操作时首先检查表是否满了。

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