元素平均需要移动元素的个数是( )。
应用题
1 设数据集合d= {1，12，5，8，3，10，7，13，9}，完成下列各题：
1) 依次取d中各数据，构造一棵二叉排序树bt。 2) 如何依据此二叉树bt得到d的一个有序序列？ 3) 画出在二叉树bt中删除“12”后的树结构
2 已知一棵二叉数的前序遍历为ABDECFG中序遍历为DBEAFGC，画出该二叉树，并写出它的后序序列。
3 关键码集为{36,18,22,11,48,59,19,14,70},哈希表表长为11，hash(key)=key,用线性探测法处理冲突，并求出查找成功时的平均查找长度(给出步骤)
4 设一数组中原有数据如下：15，13，20，18，12，60。下面是一组由不同排序方法进行一遍排序后的结果。
（ ）排序的结果为：12，13，15，18，20，60 （ ）排序的结果为：13，15，18，12，20，60 （ ）排序的结果为：13，15，20，18，12，60 （ ）排序的结果为：12，13，20，18，15，60 5 有如图所示的带权有向图G，试回答以下的问题。(给出步骤)
1) 给出从顶点1出发的深度优先遍历序列和广度优先遍历序列。 2) 给出下图的一个拓扑序列。 3) 给出从顶点1到顶点8的关键路径。
6 4 4 5 1 3 3 6 4 7 4 9 6 2 5 8 2 5 4 2 12 7 3 3 6 给出一组关键字T={12，2，16，30，8，28，4，10，20，6，18}，写出用下列算法从小到大排序时第一趟结束时的序列
1） 希尔排序（第一趟排序的增量为5） 2） 快速排序（选第一个记录为枢轴）
7 已知一棵二叉树的先序遍历序列为：AEFBGCDHIKJ，中序遍历序列为：EFAGBCHKIJD。试写出此二叉树的后序遍历序列，并用图画出它的后序线索二叉树。
8 现有如下的稀疏矩阵A如图所示，要求用三元组表示A和它的转置矩阵。
?15?0??0??0(1)画出该有向图； (2)画出邻接表；
01300022?30?? 0?6??00?9 对给定的有7个顶点的有向图的邻接矩阵如下：
(3)若将图看成AOE－网，列出其关键活动及相应的有向边，关键路径长度是多少？
??????????????????253?2???1?????????????????7???35???5??? ?37????5??????10设用于通讯的电文由8个字母A、B、C、D、E、F、G、H组成，字母在电文中出现的频率分别为：7、19、2、6、32、3、21、10。试为这8个字母设计哈夫曼编码。
11设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=1,2,3,?,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。 12一棵非空的二叉树其先序序列和后序序列正好相反，画出这棵二叉树的形状。
13有关键字集合K={15，22，50，13，20，36，28，48，35，31，41，18}采用散列存取，散列表长为15，设散列函数H（K）=K MOD 13，解决冲突采用开放地址法中的二次探测再散列的方法，试将K值填入表中，并计算查找成功时的平均查找长度。
14假设一棵二叉树的层次次序（按层次递增顺序排列，同一层次自左向右）为ABECFGDHI,中序序列为BCDAFEHIG。请画出该二叉树，并将其转换为对应的森林。
15有一随机数组(25,84,21,46,13,27,68,35,20),现采用某种方法对它们进行排序,其每趟排序结果如下, 则该排序方法是什么?
初 始:25,84,21,46,13,27,68,35,20 第一趟:20,13,21,25,46,27,68,35,84 第二趟:13,20,21,25,35,27,46,68,84 第三趟:13,20,21,25,27,35,46,68,84 16 判断序列（12，70，33，65，24，56，48，92，86，33）是否为堆，如果不是，则把它调整为小堆。
17设一棵二叉树的先序、中序遍历序列分别为；先序遍历序列： A B D F C E G H 中序
2
2
2
遍历序列： B F D A G E H C
（1）画出这棵二叉树。
（2）画出这棵二叉树的后序线索树。 （3）将这棵二叉树转换成对应的树（或森林）。
18 已知含有8个结点的一棵二叉树，按先序、中序、后序进行遍历后，有些结点序号不清楚如下图示。要求构造出一棵符合条件的二叉树。 先根序遍历 _ 2 3 _ 5 _ 7 8 中根序遍历 3 _ 4 1 _ 7 8 6 后根序遍历 _ 4 2 _ _ 6 5 1
19 对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。
20 有向图 G=
(1) 画出插入(18)的3阶B-树。
(2) 画出在插入(18)后的3阶B-树中删除(78) 后的3阶B-树
22设有下列带权无向图： (1) 请画出该图的邻接表。
(2) 列出深度优先遍历该图所得到的一个顶点序列。 (3) 请画出该图的一棵最小生成树。
23已知二叉树T的先序遍历序列为ABCDEFGHIJKL，中序遍历序列为CBEFDJIKLHGA。请画出T的后序线索树。
24判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）。 （1）100，85，98，77，80，60，82，40，20，10，66 （2）100，98，85，82，80，77，66，60，40，20，10 （3）100，85，40，77，80，60，66，98，82，10，20
（4）10，20，40，60，66，77，80， 82，85，98，100
25一个深度为L的满K叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树，如果按层次顺序从1开始对全部结点进行编号，求： 1）各层的结点的数目是多少？
2）编号为n的结点的双亲结点（若存在）的编号是多少？ 3）编号为n的结点的第i 个孩子结点（若存在）的编号是多少？
4）编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？
26给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18),写出用下列算法从小到大排序时第一趟结束时的序列；
(1) 希尔排序（第一趟排序的增量为5） (2) 快速排序（选第一个记录为枢轴（分隔）
算法设计
1一个单链表（不同结点的数据域值可能相同），其头指针为head，编写一个函数计算数据域为x 的结点个数。
2设计算法，求二叉树的深度。 3计一个算法判断一个字符串是否对称
4有一棵二叉树BT以二叉链表为存储结构，请按照要求写出如下算法。 求BT中所有叶子结点数目。
5设计算法，按从根结点到叶子结点，从左子结点到右子结点的次序输出二叉树的所有结点。 6 写出先序遍历二叉树的非递归算法
7设计算法，在无头结点链表L的第i个元素之前插入元素 8设计一算法判别表达式中小括号是否匹配
9设计一算法，求二叉树中以值为x的结点为根的子树深度
10试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法
11设L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。
12设有一个带头结点的单向链表，数据项递减有序。写一算法，重新排列链表，使数据项递增有序，要求算法时间复杂度为O（n）
13有一个单链表L（至少有1个结点），其头结点指针为head，编写一个过程将L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。 14假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，请写出相应的入队列和出队列算法。
15设一棵二叉树以二叉链表为存贮结构，结点结构为(lchild, data,rchild)，设计一个算法将二叉树中所有结点的左，右子树相互交换。
16一棵二叉树以二叉链表来表示，求其指定的某一层k(k>1)上的叶子结点的个数。