数据结构第二十讲.ppt

第三十页，共四十六页，2022年，8月28日 2-路插入排序只能减少移动记录的次数，而不能绝对避免移动记录。当L.r[1]的待排序记录中关键字最小或最大的记录时， 2-路插入排序就完全失去它的优越性。 因此，若希望在排序过程中不移动记录，只有改变存储结构，进行表插入排序 3.表插入排序 #define SIZE 100 //静态链表容量 Typedef struct { RcdType rc; //记录项 int next; //指针项 }SLNode; //表结点类型 第三十一页，共四十六页，2022年，8月28日 typedef struct{ SLNode r[SIZE]; //0号单元为表头结点 int length; //链表当前长度； }SLinkListType; //静态链表类型 设数组下标为“0”的分量为表头结点，并令表头结点记录的关键字区最大整数MAXINT。 表插入排序的过程描述如下：首先将静态链表中数组下标为“1”的分量（结点）和表头结点构成一个循环链表，然后依次将下标为“2”至“n”的分量（结点）按记录关键字非递减有序插入到循环链表中 第三十二页，共四十六页，2022年，8月28日 第三十三页，共四十六页，2022年，8月28日 * 第一页，共四十六页，2022年，8月28日 19. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。 LL B. LR C. RL D. RR 27. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ ）个记录。 A．1 B. 2 C. 3 D. 4 31. 设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( ) A．8 B．3 C．5 D．9 32. 假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( ) A．k-1次 B. k次 C. k+1次 D. k（k+1）/2次 C D D D 第二页，共四十六页，2022年，8月28日 34. 散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 35. 散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。 （ ）元素59存放在散列表中的 A． 8 B. 9 C. 10 D. 11 （2）存放元素59需要搜索的次数是（ ）。 A． 2 B. 3 C. 4 D. 5 36. 将10个元素散列到100000个单元的哈希表中，则（ ）产生冲突。 A. 一定会 B. 一定不会 C. 仍可能会 D D C C 第三页，共四十六页，2022年，8月28日 第10章 排序 排序的概念及种类 插入法排序的各种具体实现方法及算法分析 选择法排序的各种具体方法的实现及时间性能分析 交换法排序的具体实现及性能分析 归并排序和基数排序的各自实现算法 第四页，共四十六页，2022年，8月28日 本章导读 排序是日常工作和软件设计中常用的运算之一。为了提高查询速度需要将无序序列按照一定的顺序组织成有序序列。由于需要排序的数据表的基本特性可能存在差异，使得排序方法也不同。如何合理地组织数据的逻辑顺序，按照何种方式排出的序列最有效？这是本章要讨论的主题。本章主要介绍排序的概念及几种最常见的排序方法，讨论其性能和特点，并在此基础上进一步讨论各种方法的适用场合，以便在实际应用中能根据具体的问题选择合适的排序方法。 第五页，共四十六页，2022年，8月28日