1、数据结构导论自考题模拟 13 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.若一顺序表长度为 n，则其每个元素的平均查找长度是_（分数：2.00）AnB.(n-1)/2C.n/2D.(n+1)/22.对一个二叉排序树采用中序遍历进行输出的数据一定是_（分数：2.00）A.递增的B.递减的C.无序的D.递增或递减3.二分查找算法的时间复杂度是_ A.O(nlog2n) B.O(log2n) C.O(n2) D.O(n)（分数：2.00）A.B.C.D.4.分块查找的时间性能_（分数：2.00）A.高于二分查找B.低于顺序查找高于二分查找
2、C.高于顺序查找低于二分查找D.低于顺序查找5.静态查找表的查找方法包括_（分数：2.00）A.二分查找、二叉排序树查找B.二分查找、索引顺序表查找C.二叉排序树查找、索引顺序表查找D.二叉排序树查找、散列法查找6.依次输入键值序列 50，72，45，85，75，20，35，45，65，30，建立对应的二叉排序树后，查找元素35，要进行多少次元素间的比较_（分数：2.00）A.4B.5C.7D.107.对有序表(18，20，25，34，48，62，74，85)用二分查找法查找 20 所需的比较次数为_（分数：2.00）A.1 次B.2 次C.3 次D.4 次8.要解决散列引起的冲突问题，通常采
3、用的方法有_（分数：2.00）A.数字分析法、平方取中法B.二次探测法、平方取中法C.二次探测法、链地址法D.数字分析法、线性探测法9.从未排序序列中依次取出一个元素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置，该排序方法称为什么排序法_（分数：2.00）A.直接插入B.直接选择C.二路归并D.快速10.以下 4 种排序法中，不稳定的排序方法是_（分数：2.00）A.插入B.二路归并C.冒泡D堆11.外部排序是指在排序的整个过程中，全部数据在计算机的哪个中完成的排序_（分数：2.00）A.内存储器B.外存储器C.寄存器D.内存储器和外存储器12.在下述的排序方法中，属于外部排
4、序方法的是_（分数：2.00）A.拓扑排序法B.选择排序法C.插入排序法D.归并排序法13.下列序列中，符合堆定义的是_（分数：2.00）A.(100，80，55，60，50，40，58，35，20)B.(100，80，55，58，50，40，60，35，20)C.(100，80，55，60，50，40，35，58，20)D.(100，70，55，60，50，40，58，35，20)14.一组记录的关键字为(46，79，56，38，40，84)，则利用快速排序的方法，第一趟排序的结果为_（分数：2.00）A.40，38，46，56，79，84B.38，40，46，56，79，84C.40，38
5、，46，84，56，79D.40，38，46，79，56，8415.若用冒泡排序法对序列 19，14，6，27，8，12，17，52，10，26，47，29，42，25 从小到大进行排序，需要进行比较的次数是_（分数：2.00）A.33B.91C.70D.45二、填空题(总题数：13，分数：26.00)16.动态查找表以集合为逻辑结构，包括 5 种基本运算： 1、 2、 3、 4、 5。 （分数：2.00）17.索引顺序表由 1 和 2 两部分组成。 （分数：2.00）18.在顺序查找、二分查找、索引顺序查找和散列查找 4 种查找方法中，平均查找长度与元素个数没关系的查找方法是 1。 （分数：
6、2.00）19.根据给定的某个值，在查找表中寻找一个其键值等于给定值的数据元素。若找到一个这样的数据元素，则称 1，此时的运算结果为该数据元素在查找表中的位置。 （分数：2.00）20.两个不同的元素存入同一个散列表，当这两个元素的散列函数值相同时，称为 1。 （分数：2.00）21.直接插入排序需要 1 个记录的辅助空间。 （分数：2.00）22.设有一个已按各元素的值排好序的线性表，长度为 130，对给定的 k 值，用二分法查找与 k 相等的元素，若查找成功，则至少需要比较 1 次，至多需比较 2 次。 （分数：2.00）23.常用的插入排序方法有 1、 2、 3 和 4。 （分数：2.0
7、0）24.在排序算法中，分析算法时间复杂度时，通常以 1 和 2 为标准操作。评价排序的另一个主要标准是执行算法所需要的 3。 （分数：2.00）25.记录数为 n，冒泡排序算法在最好情况下所作的比较次数为 1。 （分数：2.00）26.对 n 个记录的集合进行快速排序，其最坏情况下所需的时间复杂度是 1，就平均性能而言，快速排序方法最佳，其时间复杂度为 2。 （分数：2.00）27.堆排序中，当在这棵二叉树中，任一结点的值都不大于它的两个孩子的值(若存在孩子的话)，则此堆称为 1 堆。 （分数：2.00）28.堆排序算法的时间复杂度为 1。 （分数：2.00）三、应用题(总题数：5，分数：3
8、0.00)29.给定有序表 A=6，87，155，188，220，465，505，508，511，586，656，670，700，766，用二分查找法在 A 中查找 511，试给出查找过程。 （分数：6.00）30.给定表(18，15，23，1，65，20，84，28，54，14，11)，试按元素在表中的次序将它们依次插入一个初始时为空的二叉排序树，画出插入完成后的二叉排序树。 （分数：6.00）31.对于一组数据(24，12，22，34，5，44，76，61，100，3，1，120)，写出该数据采用归并算法的排序过程和排序结果。 （分数：6.00）32.试写出一组键值(46，58，15，45
9、，90，18，10，62)应用直接插入排序算法从小到大排序后各趟的结果。 （分数：6.00）33.对于下列一组关键字(47，59，15，45，90，18，10，62)，试写出快速排序每一趟的排序结果，并标出第一趟中各元素的移动方向。 （分数：6.00）四、算法设计题(总题数：2，分数：14.00)34.试写出非递归调用的快速排序算法。 （分数：7.00）_35.试写出直接插入排序算法。 （分数：7.00）_数据结构导论自考题模拟 13 答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.若一顺序表长度为 n，则其每个元素的平均查找长度是_（分
10、数：2.00）AnB.(n-1)/2C.n/2D.(n+1)/2 解析：考点 顺序表查找算法的平均查找长度 解析 2.对一个二叉排序树采用中序遍历进行输出的数据一定是_（分数：2.00）A.递增的 B.递减的C.无序的D.递增或递减解析：考点 二叉排序树 解析 根据二叉排序树的定义可知，按照中序遍历方法可得到递增序列。3.二分查找算法的时间复杂度是_ A.O(nlog2n) B.O(log2n) C.O(n2) D.O(n)（分数：2.00）A.B. C.D.解析：考点 二分查找算法的时间复杂度 解析 二分查找算法的平均查找长度为 4.分块查找的时间性能_（分数：2.00）A.高于二分查找B.
11、低于顺序查找高于二分查找C.高于顺序查找低于二分查找 D.低于顺序查找解析：考点 分块查找的时间性能 解析 分块查找的时间性能高于顺序查找，低于二分查找。5.静态查找表的查找方法包括_（分数：2.00）A.二分查找、二叉排序树查找B.二分查找、索引顺序表查找 C.二叉排序树查找、索引顺序表查找D.二叉排序树查找、散列法查找解析：考点 静态查表的查找方法 解析 静态查找表的查找方法包括顺序查找、二分查找和索引顺序表查找。6.依次输入键值序列 50，72，45，85，75，20，35，45，65，30，建立对应的二叉排序树后，查找元素35，要进行多少次元素间的比较_（分数：2.00）A.4 B.5
12、C.7D.10解析：考点 二叉排序树的建立及元素查找 解析 由序列可得二叉排序树如下，共需进行 4 次元素间的比较，过程如下图： 7.对有序表(18，20，25，34，48，62，74，85)用二分查找法查找 20 所需的比较次数为_（分数：2.00）A.1 次B.2 次 C.3 次D.4 次解析：考点 二分查找法 解析 过程如下： 8.要解决散列引起的冲突问题，通常采用的方法有_（分数：2.00）A.数字分析法、平方取中法B.二次探测法、平方取中法C.二次探测法、链地址法 D.数字分析法、线性探测法解析：考点 解决散列引起的冲突问题的方法 解析 解决散列引起的冲突问题的方法有：线性探测法、二
13、次探测法、链地址法、多重散列法和公共溢出区法。9.从未排序序列中依次取出一个元素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置，该排序方法称为什么排序法_（分数：2.00）A.直接插入 B.直接选择C.二路归并D.快速解析：考点 直接插入排序的定义 解析 从未排序序列中依次取出一个元素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置，该排序方法称为直接插入排序法。10.以下 4 种排序法中，不稳定的排序方法是_（分数：2.00）A.插入B.二路归并C.冒泡D堆 解析：考点 排序法的稳定性 解析 堆排序是不稳定的。11.外部排序是指在排序的整个过程中，全部数据在计算
14、机的哪个中完成的排序_（分数：2.00）A.内存储器B.外存储器C.寄存器D.内存储器和外存储器 解析：考点 内部排序和外部排序的区别 解析 外部排序是指在排序的整个过程中，全部数据在计算机的内存储器和外存储器中完成的排序。内部排序仅在内存储器中进行。12.在下述的排序方法中，属于外部排序方法的是_（分数：2.00）A.拓扑排序法 B.选择排序法C.插入排序法D.归并排序法解析：考点 外部排序方法 解析 只有拓扑排序是对图中结点进行排序的方法，属于外部排序，其他 3 种都是内部排序。13.下列序列中，符合堆定义的是_（分数：2.00）A.(100，80，55，60，50，40，58，35，20
15、)B.(100，80，55，58，50，40，60，35，20)C.(100，80，55，60，50，40，35，58，20) D.(100，70，55，60，50，40，58，35，20)解析：考点 堆的定义 解析 根据堆的定义以及 4 个选项可知其是最大堆，根据最大堆的特性，这棵二叉树中任意一结点的值都不小于它的两个孩子的值(若存在孩子的话)，只有 C 选项符合。14.一组记录的关键字为(46，79，56，38，40，84)，则利用快速排序的方法，第一趟排序的结果为_（分数：2.00）A.40，38，46，56，79，84 B.38，40，46，56，79，84C.40，38，46，84，
16、56，79D.40，38，46，79，56，84解析：考点 本题主要考查的知识点为快速排序 解析 快速排序完成一趟的过程如下图所示，可知正确答案为 A。 15.若用冒泡排序法对序列 19，14，6，27，8，12，17，52，10，26，47，29，42，25 从小到大进行排序，需要进行比较的次数是_（分数：2.00）A.33B.91 C.70D.45解析：考点 冒泡排序法 解析 冒泡排序法总的比较次数为 n(n-1)/2 次，n 为待排序列元素个数。二、填空题(总题数：13，分数：26.00)16.动态查找表以集合为逻辑结构，包括 5 种基本运算： 1、 2、 3、 4、 5。 （分数：2.
17、00）解析：初始化 查找 读表中元素 插入 删除 考点 动态查找表 解析 动态查找表以集合为逻辑结构，包括 5 种基本运算：初始化、查找、读表中元素、插入、删除。17.索引顺序表由 1 和 2 两部分组成。 （分数：2.00）解析：一个索引表 一个顺序表 考点 索引顺序表 解析 索引顺序表由两部分组成：一个索引表和一个顺序表。18.在顺序查找、二分查找、索引顺序查找和散列查找 4 种查找方法中，平均查找长度与元素个数没关系的查找方法是 1。 （分数：2.00）解析：散列查找 考点 查找方法的特点 解析 在顺序查找、二分查找、索引顺序查找和散列查找四种查找方法中，平均查找长度与元素个数没关系的查
18、找方法是散列查找。19.根据给定的某个值，在查找表中寻找一个其键值等于给定值的数据元素。若找到一个这样的数据元素，则称 1，此时的运算结果为该数据元素在查找表中的位置。 （分数：2.00）解析：查找成功 考点 查找成功的定义 解析 给定某个值，在查找表中寻找一个其键值等于给定值的数据元素，若找到一个这样的数据元素，则称查找成功。20.两个不同的元素存入同一个散列表，当这两个元素的散列函数值相同时，称为 1。 （分数：2.00）解析：冲突 考点 散列表所涉及的概念 解析 两个不同的元素存入同一个散列表，当这两个元素的散列函数值相同时，称为冲突。21.直接插入排序需要 1 个记录的辅助空间。 （分
19、数：2.00）解析：1 考点 直接插入排序算法 解析 直接插入排序需要 1 个记录的辅助空间。22.设有一个已按各元素的值排好序的线性表，长度为 130，对给定的 k 值，用二分法查找与 k 相等的元素，若查找成功，则至少需要比较 1 次，至多需比较 2 次。 （分数：2.00）解析：1 8 考点 二分查找的比较次数 解析 二分查找至少比较 1 次，至多不超过(log 2 n)+1=(log 2 130)+1=8 次。23.常用的插入排序方法有 1、 2、 3 和 4。 （分数：2.00）解析：直接插入排序 折半插入排序 表插入排序 希尔排序 考点 常用的插入排序方法 解析 常用的插入排序方法
20、有直接插入排序、折半插入排序、表插入排序和希尔排序。24.在排序算法中，分析算法时间复杂度时，通常以 1 和 2 为标准操作。评价排序的另一个主要标准是执行算法所需要的 3。 （分数：2.00）解析：键值比较 记录移动 附加空间 考点 排序算法中的时间复杂度 解析 在排序算法中，分析算法时间复杂度时，通常以键值比较和记录移动为标准操作。评价排序的另一个主要标准是执行算法所需要的附加空间。25.记录数为 n，冒泡排序算法在最好情况下所作的比较次数为 1。 （分数：2.00）解析：n-1 考点 冒泡排序算法 解析 记录数为 n，冒泡排序算法在最好情况下所作的比较次数为 n-1。26.对 n 个记录
21、的集合进行快速排序，其最坏情况下所需的时间复杂度是 1，就平均性能而言，快速排序方法最佳，其时间复杂度为 2。 （分数：2.00）解析：O(n 2 ) O(nlog 2 n) 考点 快速排序算法 解析 快速排序算法最坏情况下的时间复杂度是 O(n 2 )，就平均性能而言，快速排序算法最佳，时间复杂度为 O(nlog 2 n)。27.堆排序中，当在这棵二叉树中，任一结点的值都不大于它的两个孩子的值(若存在孩子的话)，则此堆称为 1 堆。 （分数：2.00）解析：最小 考点 最小堆 解析 最小堆的任意结点的值都不大于它的两个孩子的值(若存在孩子的话)。28.堆排序算法的时间复杂度为 1。 （分数：
22、2.00）解析：O(log 2 n) 考点 堆排序算法的时间复杂度 解析 堆排序算法的时间复杂度为 O(log 2 n)。三、应用题(总题数：5，分数：30.00)29.给定有序表 A=6，87，155，188，220，465，505，508，511，586，656，670，700，766，用二分查找法在 A 中查找 511，试给出查找过程。 （分数：6.00）解析：考点 二分查找算法30.给定表(18，15，23，1，65，20，84，28，54，14，11)，试按元素在表中的次序将它们依次插入一个初始时为空的二叉排序树，画出插入完成后的二叉排序树。 （分数：6.00）解析：结果如下： 31
23、.对于一组数据(24，12，22，34，5，44，76，61，100，3，1，120)，写出该数据采用归并算法的排序过程和排序结果。 （分数：6.00）解析：24122234544766110031120 12 2422 345 4461 763 1001 120 12 22 24 345 44 61 761 3 100 120 5 12 22 24 34 44 61 761 3 100 120 1 3 5 12 22 24 34 44 61 76 100 120 考点 归并排序算法32.试写出一组键值(46，58，15，45，90，18，10，62)应用直接插入排序算法从小到大排序后各趟的结
24、果。 （分数：6.00）解析：初始序列：46,58,15,45,90,18,10,62 第一趟：46,58,15,45,90,18,10,62 第二趟：15,46,58,45,90,18,10,62 第三趟：15,45,46,58,90,18,10,62 第四趟：15,45,46,58,90,18,10,62 第五趟：15,18,45,46,58,90,10,62 第六趟：10,15,18,45,46,58,90,62 第七趟：10,15,18,45,46,58,62,90 考点 直接插入排序算法33.对于下列一组关键字(47，59，15，45，90，18，10，62)，试写出快速排序每一趟的
25、排序结果，并标出第一趟中各元素的移动方向。 （分数：6.00）解析：四、算法设计题(总题数：2，分数：14.00)34.试写出非递归调用的快速排序算法。 （分数：7.00）_正确答案：()解析：int Partition(RedType /用子表的第一个记录作枢轴记录 while(lowhigh) /从表的两端交替地向中间扫描 while(lowhigh /将比枢轴记录小的记录交换到低端 Rlow Rhigh; while(lowhigh /将比枢轴记录大的记录交换到高端 Rlow 35.试写出直接插入排序算法。 （分数：7.00）_正确答案：()解析：void InsertionSort(SqList i=L.1ength;+i) if(L.ri.keyL.ri-1.key) L.r0=L.ri; /复制为监视哨 for(j=i-1;L.r0.keyL.rj.key;-j) L.rj+1=L.rj; /记录后移 L.rj+1=L.r0; /插入到正确位置 /InsertSort 考点 直接插入排序算法实现
