3）在邻接矩阵存储上，写出以顶点1作为源点的广度优先遍历序列。（3分） 1 3 2 8 5 6 4 7 二、 程序设计 1、 有向连通图采用邻接表存储结构，写一个根据给定值进行查找的算法（基于遍历做）。（10分） 2、 写一个在单链表上查找最大值的算法。（10分） 3、 写一个求单链表长度的算法（10分）。 4、写出建立无向图的邻接矩阵存储的算法 (10分)。
练习题2
一、应用题
1、请对下图的无向带权图：
（1） 写出它的邻接矩阵，并按普里姆算法求其最小生成树； （2） 写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。
2.【类似严题集6.27③】给定二叉树的两种遍历序列，分别是：
前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F，
试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。
3、把如图所示的树转化成二叉树。
4.【严题集6.21②】画出和下列二叉树相应的森林。
5．假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
（1） 画出描述折半查找过程的判定树； （2） 若查找元素54，需依次与哪些元素比较？ （3） 若查找元素90，需依次与哪些元素比较？
（4） 假定每个元素的查找概率相等，求查找成功时的平均查找长度。
二、算法设计
1、写出循环队列初始化、入队和出队操作，并用存储示意图描述每一种操作的变化。
2、写出带头结点单链表的逆置算法。
3、写一个求二叉树叶子结点个数的算法。注：二叉树采用二叉链表存储。
习题3
一 应用分析题.
1、给定一组关键字序列{36，75，83，54，12，67，60，40，92，72}，按照关键字顺序构造一个平衡二叉树AVL，并求等概率情况下查找成功的平均查找长度ASL。（10分）
3、设有一组关键字（32，75，29，63，48，94，25，46，18，70），采用哈希函数：H(key)=key。采用链地址法处理冲突，设计出链表结构，并计算查找成功时的平均查找长度。（10分）
4、已知一组关键字为{46，74，16，53，14，26，40，38，86，65，27，34}，利用希尔排序的方法写出增量d每取一个值后所得到的排列结果，假定d依次取5，3，1（5分）
二 程序设计
1、写一个建立有向图邻接表存储结构的算法。（10分） 2、写一个带岗哨的顺序查找算法。（10分）
习题4
一、分析设计题。
1. 设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 17。
K为关键字，用线性探测再散列法处理冲突，输入关键字序列： （10，24，32，17，31，30，46，47，40，63，49） 造出Hash表，试回答下列问题： （1） 画出哈希表的示意图；
（2） 若查找关键字63，需要依次与哪些关键字进行比较？ （3） 若查找关键字60，需要依次与哪些关键字比较？
（4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 （5）
2. 【严题集9.3②】画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。
3. 在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉平衡树，并求ASL.
4、选取散列函数H（key）=（3*key），用线性探测法和链地址法两种方法处理冲突，分别对下列关键码序列构造一个散列地址空间为0～10，表长为11的散列表，{22，41，53，08，46，30，01，31，66}。并求各自的ASL
5、关键字序列为(7,4,5,9,1,2,8,10,6,5)，写出一趟快速排序，画出排序中比较交换的过程。
6、关键字序列49 38 65 97 76 13 27 49 55 04 10，画出一趟希尔排序的过程。d1=5 二、算法
1、写一个单链表求长度的算法。
2、写一个根据给定值在二叉树中进行查找的算法。二叉树采用二叉链表存储结构。
3、【严题集7.14③】编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。
习题5
(1)
Jan Feb Mar Apr June May Aug July Sep Dec Oct Nov ASL=(1+2*2+3*3+4*3+5*2+6)/12= 42/12
(2)判定树如下：
6 3 9 1 4 7 11 2 5 8 10 12 ASL=(1+2*2+3*4+4*5)/12=37/12
（3）