数据结构(高起专)综合测试3.docx

数据结构(高起专)综合测试3 总分: 100分考试时间:分钟名词解释说明:1. 文件(5分)参考答案：是由大量性质相同的记录组成的集合，按记录类型不同可分为操作系统文件和数据库文件。解题思路：2. 哈希表(5分)参考答案：将结点的关键字Key作为自变量，通过一个确定的函数关系H计算出相应的函数值H（Key），然后以H（Key）作为该结点的存储单元地址。用这种方式建立起来的线性表称为哈希表。解题思路：3. 数据处理(5分)参考答案：指对数据进行检索、插入、删除、合并、排序、统计、简单计算、转换、输入和输出等操作过程。解题思路：4. 有向图(5分)参考答案：对于一个图G，若边集合E（G）为有向边的集合，则称该图为有向图。解题思路：5. 存储结构(5分)参考答案：数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。解题思路：简答题说明:6. 根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？(5分)参考答案：集合、线性结构、树形结构、图形或网状结构。解题思路：7. 在单链表和双向链表中，能否从当前结点出发访问到任何一个结点？(5分)参考答案：在单链表中不能从当前结点（若当前结点不是第一结点）出发访问到任何一个结点，链表只能从头指针开始，访问到链表中每个结点。在双链表中求前驱和后继都容易，从当前结点向前到第一结点，向后到最后结点，可以访问到任何一个结点。解题思路：8. 树和二叉树之间有什么样的区别与联系？(5分)参考答案：树和二叉树逻辑上都是树形结构，区别有三：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分枝的情况下，也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空。二叉树不是树的特例。解题思路：9. 如何衡量hash函数的优劣？简要叙述hash表技术中的冲突概念，并指出三种解决冲突的方法。(8分)参考答案：评价哈希函数优劣的因素有：能否将关键字均匀影射到哈希空间上，有无好的解决冲突的方法，计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。散列表存储中解决碰撞的基本方法：①开放定址法形成地址序列的公式是：Hi=（H（key）+di）%m，其中m是表长，di是增量。根据di取法不同，又分为三种：a.di =1，2，…，m-1 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。b.di =12，-12，22，-22，… ，±k2（k≤m/2）称为二次探测再散列，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3（j为整数）的素数时才有可能。c.di =伪随机数序列，称为随机探测再散列。②再散列法 Hi=RHi（key）i=1，2，…，k，是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。③链地址法将关键字为同义词的记录存储在同一链表中，散列表地址区间用H[0..m-1]表示，分量初始值为空指针。凡散列地址为i（0≤i≤m-1）的记录均插在以H[i]为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为开散列表，而①中的散列表称闭散列表，含义是元素个数受表长限制。④建立公共溢出区设H[0..m-1]为基本表，凡关键字为同义词的记录，都填入溢出区O[0..m-1]。解题思路：10. 快速排序，堆排序和希尔排序是时间性能较好的排序方法，也是稳定的排序方法。判正误并改错。(8分)参考答案：错。快速排序，堆排序和希尔排序是时间性能较好的排序方法，但都是不稳定的排序方法。解题思路：11. 对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。(8分)参考答案：初始序列：[28],07,39,10,65,14,61,17,50,21 21移动：21,07,39,10,65,14,61,17,50,[]39移动：21,07,[],10,65,14,61,17,50,39 17移动：21,07,17,10,65,14,61,[],50,3965移动：21,07,17,10,[],14,61,65,50,39 14移动：21,07,17,10,14,[28],61,65,50,39解题思路：12. 有n个结点并且高度为n的二叉树的数目是多少?(8分)参考答案：2n-1（本题等价于高度为n的满二叉树有多少叶子结点，从根结点到各叶子结点的单枝树是不同的二叉树。）解题思路：13. 已知一个稀疏矩阵如图1所示：图1 具有6行×7列的一个稀疏矩阵(1)写出它的三