学海网

《数据结构》各章自测题（部分带答案）
第1章绪论
第2章线性表
第3章栈与队列
第6章二叉树
第7章图
第9章查找
第10章排序

第一章 绪论 自测题
一、填空题
1．数据结构是一门研究非数值计算的程序设计问题中计算机的             以及它们之间的           和运算等的学科。
2．数据结构被形式地定义为（D, S），其中D是            的有限集合，S是D上的            有限集合。
3．数据结构包括数据的             、数据的            和数据的             这三个方面的内容。
4．数据结构按逻辑结构可分为两大类，它们分别是            和            。
5．线性结构中元素之间存在           关系，树形结构中元素之间存在          关系，图形结构中元素之间存在          关系。
6．在线性结构中，第一个结点         前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点后续结点，其余每个结点有且只有1个后续结点。
7．在树形结构中，树根结点没有         结点，其余每个结点有且只有        个前驱结点；叶子结点没有         结点，其余每个结点的后续结点数可以              。
8．在图形结构中，每个结点的前驱结点数和后续结点数可以             。
9．数据的存储结构可用四种基本的存储方法表示，它们分别是                             。
10．数据的运算最常用的有5种，它们分别是                                              。
11．一个算法的效率可分为            效率和                效率。
二、单项选择题
（     ）1．非线性结构是数据元素之间存在一种：
A）一对多关系 B）多对多关系 C）多对一关系 D）一对一关系
（     ）2．数据结构中，与所使用的计算机无关的是数据的        结构；
A）存储 B）物理 C）逻辑 D）物理和存储
（     ）3．算法分析的目的是：
A）找出数据结构的合理性 B）研究算法中的输入和输出的关系
C）分析算法的效率以求改进 D）分析算法的易懂性和文档性
（     ）4．算法分析的两个主要方面是：
A）空间复杂性和时间复杂性 B）正确性和简明性
C）可读性和文档性 D）数据复杂性和程序复杂性
（     ）5．计算机算法指的是：
A）计算方法 B）排序方法 C）解决问题的有限运算序列 D）调度方法
（     ）6．计算机算法必须具备输入、输出和       等5个特性。
A）可行性、可移植性和可扩充性 B）可行性、确定性和有穷性
C）确定性、有穷性和稳定性 D）易读性、稳定性和安全性
三、简答题

第9章 查找 自测卷答案

一、填空题
1、在数据的存放无规律而言的线性表中进行检索的最佳方法是   顺序查找（线性查找）   。
2、线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索   8   次。设有100个结点，用二分法查找时，最大比较次数是   7   。
3、假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为   2   ；比较四次查找成功的结点数为   8   ；平均查找长度为   3.7   。
解：显然，平均查找长度＝O（log2n）<5次（25）。但具体是多少次，则不应当按照公式
来计算（即（21×log221）/20＝4.6次并不正确！）。因为这是在假设n＝2m-1的情况下推导出来的公式。应当用穷举法罗列：
全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7  ！！！
4、折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素   28，6，12，20   比较大小。
5、在各种查找方法中，平均查找长度与结点个数n无关的查找方法是   散列查找   。
6、散列法存储的基本思想是由   关键字的值   决