【学历类职业资格】数据结构导论自考题模拟13及答案解析.doc
《【学历类职业资格】数据结构导论自考题模拟13及答案解析.doc》由会员分享,可在线阅读,更多相关《【学历类职业资格】数据结构导论自考题模拟13及答案解析.doc(10页珍藏版)》请在麦多课文档分享上搜索。
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.数字分析法、线性探测法解析:考点 解决散列引起的冲突问题的方法 解析 解决散列引起的冲突问题的方法有:线性探测法、二
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
5000 积分 0人已下载
下载 | 加入VIP,交流精品资源 |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 学历 职业资格 数据结构 导论 考题 模拟 13 答案 解析 DOC
