文件名称：数据结构自测卷集及答案
文件大小：536KB
文件格式：DOCX
更新时间：2012-01-10 18:47:16
数据结构 自测卷 习题集
第一章概论 自测题答案 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。 3. 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。 ....... 第2章 自测卷答案 一、填空 1. 【严题集2.2①】在顺序表中插入或删除一个元素，需要平均移动 表中一半元素，具体移动的元素个数与 表长和该元素在表中的位置 有关。 2. 线性表中结点的集合是 有限 的，结点间的关系是 一对一 的。 3. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 n-i+1 个元素。 4. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动 n-i 个元素。 5. 在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为 随机存取 的数据结构。 ....... 第8章 查找 自测卷 姓名 班级 一、填空题（每空1分，共10分） 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 2. 线性有序表（a1，a2，a3，…，a256）是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。 3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。解： 显然，平均查找长度＝ O（log 2 n） <5次（2 5 ）。但具体是多少次，则不应当按照公式来计算（ 即（ 21×log 2 21）/20＝4.6次并不正确！ ）。因为这是在假设 n＝2 m -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 比较大小。 .........