中南大学《数据结构》课程作业在线作业三及参考答案Word文件下载.docx
《中南大学《数据结构》课程作业在线作业三及参考答案Word文件下载.docx》由会员分享，可在线阅读，更多相关《中南大学《数据结构》课程作业在线作业三及参考答案Word文件下载.docx（23页珍藏版）》请在冰点文库上搜索。
将5个不同的数据进行排序，至多需要比较（）次。
（A）8（B）9（C）10（D）25
5.
快速排序在下列哪种情况下最易发挥其长处（）。
（A）被排序的数据中含有多个相同排序码
（B）被排序的数据已基本有序
（C）被排序的数据完全无序
（D）被排序的数据中的最大值和最小值相差悬殊
6.
能进行二分查找的线性表,必须以（）。
（A）顺序方式存储，且元素按关键字有序
（B）链式方式存储，且元素按关键字有序
（C）顺序方式存储，且元素按关键字分块有序
（D）链式方式存储，且元素按关键字分块有序
（A）
7.
为使平均查找长度达到最小,当由关键字集合构建二叉排序树时,第一个插入的关键字应为（）。
（A）5（B）37（C）41（D）62
8.
对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为（）。
（B）n
9.
对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是（）。
10.
堆的形状是一棵（）。
（A）二叉排序树（B）满二叉树（C）完全二叉树（D）平衡二叉树
11.
快速排序在最坏情况下的时间复杂度是（）。
（A）
12.
由同一组关键字集合构造的各棵二叉排序树（）。
（A）其形态不一定相同，但平均查找长度相同
（B）其形态不一定相同，平均查找长度也不一定相同
（C）其形态均相同，但平均查找长度不一定相同
（D）其形态均相同，平均查找长度也都相同
13.
采用顺序搜索方法查找长度为n的顺序表示，搜索成功的平均搜索长度为（）。
（A）n
14.
若一组记录的排序码为（46,79,56,38,40,84），则利用堆排序的方法建立的初始堆为（）。
（A）79,46,56,38,40,84
（B）84,79,56,38,40,46
（C）84,79,56,46,40,38
（D）84,56,79,40,46,38
15.
对关键字序列（56,23,78,92,88,67,19,34）进行增量为3的一趟希尔排序的结果为（）。
（A）（19,23,56,34,78,67,88,92）
（B）（23,56,78,66,88,92,19,34）
（C）（19,23,34,56,67,78,88,92）
（D）（19,23,67,56,34,78,92,88）
16.
下述几种排序方法中，要求内存最大的是（）。
（A）插入排序（B）快速排序（C）归并排序（D）选择排序
17.
下列关键字序列中，（）是堆。
（A）16,72,31,23,94,53
（B）94,23,31,72,16,53
（C）16,53,23,94，31,72
（D）16,23,53,31,94,72
18.
一组记录的排序码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的第一次划分结果为（）。
（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
19.
在分析折半查找的性能时常常加入失败节点，即外节点，从而形成扩充的二叉树。
若设失败节点i所在层次为Li，那么查找失败到达失败点时所做的数据比较次数是（）。
（D）Li
20.
排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（）。
（A）选择排序（B）快速排序（C）冒泡排序（D）插入排序
21.
已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90的元素时，检索成功需比较的次数是（）。
（A）1（B）2（C）3（D）4
22.
排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）。
（A）希尔排序（B）冒泡排序（C）插入排序（D）选择排序
23.
若一组记录的排序码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。
（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
24.
对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列进行同样的排序操作，直到子序列为空或只剩下一个元素为止。
这样的排序方法是（）。
（A）直接选择排序（B）直接插入排序（C）快速排序（D）冒泡排序
25.
衡量查找算法效率的主要标准是（）。
（A）元素的个数（B）所需的存储量（C）平均查找长度（D）算法难易程度
26.
从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为（）。
（A）希尔排序（B）归并排序（C）插入排序（D）选择排序
27.
有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为（）。
（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均不对
28.
对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多（）。
（A）从小到大排列好的（B）从大到小排列好的（C）元素无序（D）元素基本有序
29.
下列排序算法中不稳定的是（）。
（A）归并排序（B）折半插入排序（C）冒泡排序（D）快速排序
30.
向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动（）个元素。
（A）8（B）63.5（C）63（D）7
（二）多选题
序列路归并排序过程的第一趟、第二趟、第三趟结果依次是（）。
（A）38496597137627（B）38496597132776（C）13273849657697（D）49386576971327（E）38496576132797
（ABC）
在各种查找方法中，平均查找长度与表长有关的查找方法是（）。
（A）哈希表查找（B）顺序查找（C）折半查找（D）排序树查找
（BCD）
对于10个元素的有序表进行折半查找，须比较3次方可查找成功的元素在表中的位置有（）。
（A）1（B）2（C）3（D）4（E）6（F）7（G）8（H）9
（ACEH）
排序趟数与序列的原始状态有关的排序方法是（）排序法。
（A）插入（B）选择（C）冒泡（D）快速
（CD）
下列关于n个结点的m阶B树的说法中，正确的是（）。
（A）树中每个结点最多有m个关键字
（B）树中叶子结点的个数为
（C）在B树上进行查找的过程是顺指针找结点和在结点内找关键字交叉进行的过程。
（D）树中所有叶子结点都在同一层，并且不带任何信息
构造哈希表时若要避免现象，则可采用（）解决冲突。
（A）线性探测再散列法（B）二次探测再散列法（C）建立公共溢出区（D）链地址法（E）再哈希法
（BCDE）
对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是（）。
（A）直接插入（B）二分法插入（C）快速排序（D）归并排序
（BD）
根据排序方法的稳定性定义,下列排序方法中（）是稳定的排序。
（A）直接插入排序（B）希尔排序（C）快速排序（D）堆排序（E）归并排序
（AE）
下列叙述正确的是（）。
（A）直接插入排序基本操作是将一个记录插入到已经排好序的有序表中。
（B）希尔排序的基本思想是将整个待排记录序列分割成为若干个子序列分别进行直接插入排序。
（C）快速排序是对起泡排序的改进，通过一趟排序将待排序记录分割成两部分。
（D）路归并排序是将两个有序表合成一个。
（E）基数排序是通过若干次分配和收集来实现排序的。
（BCE）
（三）判断题
冒泡排序和快速排序都是基于交换两个逆序元素的排序方法。
（A）对（B）错
在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。
排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。
排序算法中的比较次数与初始元素序列的排列无关。
直接选择排序算法在最好情况下的时间复杂度为O（N），N是数据元素的个数。
当采用分快查找时，数据的组织方式为数据分成若干块，每块内数据有序。
闭散列法通常比开散列法时间效率更高。
在任何情况下，归并排序都比简单插入排序快。
散列函数越复杂越好，因为这样随机性好，冲突概率小。
在排序过程中，主要进行的两种基本操作是关键字的比较和记录的移动。
适用于折半查找的表的存储方式及元素排列要求是：
链接方式存储，元素无序。
负载因子（装填因子）是散列表的一个重要参数，它反映散列表的装满程度。
对于两棵具有相同记录集合而具有不同形态的二叉搜索树，按中序遍历得到的结点序列是相同的。
字符串通常采用散列存储和索引存储两种存储方式。
AVL树（平衡二叉搜索树）的所有叶结点不一定在同一层次上，同样，平衡m路搜索树的叶结点也不一定在同一层次上。
Hash表的平均查找长度与处理冲突的方法无关。
影响外排序的时间因素主要是内存与外设交换信息的总次数。
就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。
在用散列表存储关键码集合时，可以用双散列法寻找下一个空位置。
在设计再散列函数时，要求计算出的值与表的大小m互质。
快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。
采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。
哈希表的结点中只包含数据元素自身的信息，不包含任何指针。
升级会员 