数据结构第九章

数据结构第九章Tag内容描述：<p>1、第九章 查找 一、 选择题 1.若查找每个记录的概率均等，则在具有 n 个记录的连续顺序文件中采用顺序查找法查找 一个记录，其平均查找长度 ASL 为( )。 A (n-1)/2 B. n/2 C. (n+1)/2 D. n 2. 下面关于二分查找的叙述正确的是 ( ) A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且 只能从小到大排列 B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表 只能以顺序方式存储 3. 用二分（对半）查找表的元素的速度比用顺序法( ) A必然快 B. 必然慢 C. 相等 D. 不能确定 4. 具有 12 个关键字的有。</p><p>2、数据结构 基础数据结构应用数据结构 非线性结构线性结构 线 性 表栈 队 列串 数 组 广 义 表树 二 叉 树图 查 找 内 部 排 序 外 部 排 序 文 件 动 态 存 储 管 理 9.1 查找的基本概念 9.2 静态查找表基于线性表的查找法 9.3 动态查找表基于树表的查找法 9.4 哈希表计算式查找法 第9章 查找 l查找表 由同一类型的数据元素（记录）构成的集合。 l查找的定义 给定一个值key，在含有n个记录的表中找出关键字等于key 的记录。若找到,则查找成功，返回该记录的信息或该记录在 表中的位置；否则查找失败，返回相关的指示信息。 1. 查找的基本概。</p><p>3、第九章 习题,一、 选择题 1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。【北京航空航天大学 2000 一、8 （2分）】 A (n-1)/2 B. n/2 C. (n+1)/2 D. n 2. 下面关于二分查找的叙述正确的是 ( ) 【南京理工大学 1996 一、3 （2分）】 A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储,3. 具有12个关键字的有序表，折半查找的平均。</p><p>4、第十章 排序,排序定义将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫 排序分类 按待排序记录所在位置 内部排序：待排序记录存放在内存 外部排序：排序过程中需对外存进行访问的排序 按排序依据原则 插入排序：直接插入排序、折半插入排序、希尔排序 交换排序：冒泡排序、快速排序 选择排序：简单选择排序、堆排序 归并排序：2-路归并排序 基数排序,按排序所需工作量 简单的排序方法：T(n)=O(n) 先进的排序方法：T(n)=O(n*logn) 基数排序：T(n)=O(d*n) 排序基本操作 比较两个关键字大小 将记录从一个位置移动到。</p><p>5、数据结构 第九章 查找,本章内容 9.1 查找的基本概念 9.2 静态查找表 9.3 动态查找表 9.4 哈希表,9-3,9.1 查找的基本概念,查找表(Search Table) 查找表是由同一类型的数据元素(或记录)构成的集合。对查找表的操作主要有： 查询某个“特定的”数据元素是否在查找表中； 检索某个“特定的”数据元素的各种属性； 在查找表中插入一个数据元素； 从查找表中删去某个数据元素。 查找表分类 静态查找表 仅作查询和检索操作的查找表。 动态查找表 在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素,9-4,9.1 。</p><p>6、第九章 查找表,何谓查找表 ？,查找表是由同一类型的数据元素(或记录)构成的集合。,由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。,对查找表经常进行的操作:,1）查询某个“特定的”数据元素是否在查找表中； 2）检索某个“特定的”数据元素的各种属性； 3）在查找表中插入一个数据元素； 4）从查找表中删去某个数据元素。,仅作查询和检索操作的查找表。,静态查找表,有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中。</p><p>7、数据结构,第九章查找,主要讨论的问题：静态查找;动态查找;哈希查找.,.几个基本概念,.查找表:由同一类型的数据元素构成的集合.,.静态查找表:若只在查找表中搜索某一特定的数据元素是否存在,这类搜索过程称之为静态查找.,.动态查找表:若在查找表中搜索时插入了不存在的数据元素或删除了已存在的数据元素,这类搜索过程称之为动态查找表.,3,.关键字:是数据元素中某个数据项的值,它可以标识一个数据元素。</p><p>8、第九章 查找 一 选择题 1 若查找每个记录的概率均等 则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录 其平均查找长度ASL为 A n 1 2 B n 2 C n 1 2 D n 2 下面关于二分查找的叙述正确的是 A 表必须有序。</p><p>9、2 第9章排序 学习目标与要求 了解排序的定义 熟练掌握各种排序方法的基本思想 掌握各种排序方法时间复杂度的分析方法 并能分析各种排序方法在何种情况下使用 掌握各种排序方法的稳定性 3 9 1基本概念 排序是数据结构。</p><p>10、数据结构,第9章查找,基本概念,若表中存在特定元素，称查找成功，应输出该记录；否则，称查找不成功（也应输出失败标志或失败位置）,查找表查找查找成功查找不成功静态查找动态查找关键字主关键字次关键字,由同一类型的数据元素（或记录）构成的集合。,查询(Searching)特定元素是否在表中。,只查找，不改变集合内的数据元素。既查找，又改变（增减）集合内的数据元素。记录中某个数。</p><p>11、第九章 查找 一、 选择题 1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。 A (n-1)/2 B. n/2 C. (n+1)/2 D. n 2. 下面关于二分查找的叙述正确的是 ( ) A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列 B. 表必须有序。</p><p>12、数 据 结 构,第 9 章 查找,基本概念,若表中存在特定元素，称查找成功，应输出该记录； 否则，称查找不成功（也应输出失败标志或失败位置）,查找表 查 找 查找成功 查找不成功 静态查找 动态查找 关键字 主关键字 次关键字,由同一类型的数据元素（或记录）构成的集合。,查询(Searching)特定元素是否在表中。,只查找，不改变集合内的数据元素。 既查找，又改变（增减。</p><p>13、平衡二叉树,(AVL树),（1）它左子树和右子树都是平衡二叉树,（2）左子树和右子树的深度之差的绝对值不超过1,定义: 平衡二叉树或者是一棵空树；或者是具有下列性质的排序二叉树,平衡因子=Height(T-lchild) - Height(T-rchild),俄国数学家 G.M.Adelson-Velskii 和 E.M. Landis, 1962年,1,1,0,0,-1,1,-1,0。</p>