在地址空间为0-16的散列区中，对以下关键字序列(Jan,Feb,Mar,Apr,May, June,July,Aug,Sep,Oct,Nov,Dec)按线性探测开放定址法处理冲突构造散列表，设散列函数H(x)=i/2,其中i为关键字中第一个字母在字母表中的序号。画出该散列表并求在等概率情况下查找成功时的平均查找长度。

已知某二叉树先序序列 { EBADCFHGIKJ } 和中序序列 { ABCDEFGHIJK }, 画出该二叉树。

假设表达式中包含3种括号，例如小括号、中括号和大括号，它们可互相嵌套。设计一个算法检验顺序表存储的表达式中的括号是否匹配（如“[({[]})]”是匹配的，而“[{]}([)]”不匹配）。

假设将循环队列定义为：以整型域变量front和length分别指示循环队列中队头元素位置和队列中元素个数，指针elem指示存放队列元素的连续空间的首地址，写出相应的出队列的算法

若希望循环队列中的元素都能利用，需设一个标志域tag,并以tag的值为0或1来区分头、尾指针相同时队列的状态是“空”还是“满”。试编写与此结构相应的出队列的算法。

假设将循环队列定义为：以整型域变量rear和length分别指示循环队列中队尾元素位置和队列中元素个数，指针elem指示存放队列元素的连续空间的首地址，写出相应的出队列的算法。

依次读入以@为结束符的字符序列，判断它是否为quot;序列1amp;序列2quot;模式的字符序列.其中序列1和序列2都不含quot;amp;quot;,且序列2是序列1的逆序列。

假设二叉排序树（t为指向根结点的指针）中各元素值均不相同，设计一个递归算法按递减顺序输出树上各元素值。

设带头结点的单链表(L为头指针)中的数据元素递增有序。设计算法，将x插入到链表的适当位置上，并仍保持该表的有序性。

设顺序表va中的数据元素递增有序。设计算法，将x插入到顺序表的适当位置上，并仍保持该表的有序性。

设计算法，实现单链表的就地逆置，即利用原表的存储空间将线性表（a₁,a₂,…,a_n）逆置为（a_n ,a_n-1,…,a₁）。

设计算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a₁,a₂,…,a_n）逆置为（a_n ,a_n-1,…,a₁）。

描述以下3个关于单链表的术语的区别：头指针、头结点、首元结点。

若线性表要求以最快的速度存取而表中元素变动不大，则应采取什么存储结构（顺序或链式结构）？为什么？

若线性表经常做插入/删除操作，则应采取什么存储结构（顺序或链式结构）？为什么？

写出在循环链表中设立尾指针而非头指针的好处。

在单链表中设置头结点有什么作用？

假设将循环队列定义为：以整型域变量front和length分别指示循环队列中队头元素位置和队列中元素个数，指针elem指示存放队列元素的连续空间的首地址，写出相应的入队列的算法。

依次读入以#为结束符的字符序列，判断它是否为quot;序列1+序列2quot;模式的字符序列.其中序列1和序列2都不含quot;+quot;,且序列2是序列1的逆序列。

若希望循环队列中的元素都能利用，需设一个标志域tag,并以tag的值为0或1来区分头、尾指针相同时队列的状态是“空”还是“满”。试编写与此结构相应的入队列的算法。

假设将循环队列定义为：以整型域变量rear和length分别指示循环队列中队尾元素位置和队列中元素个数，指针elem指示存放队列元素的连续空间的首地址，写出相应的入队列的算法。

对于一个栈，若输入序列依次为{A,B,C}, 试给出所有可能的输出序列。

假设表达式中包含2种括号，例如中括号和大括号，它们可互相嵌套。设计一个算法检验顺序表存储的表达式中的括号是否匹配（如“[{[]}]”是匹配的，而“[{]}[]”不匹配）。

设s=quot;I AM A WORKERquot;，t=quot; GOODquot;，q=quot; WORKERquot;。求：StrLength(s)，StrLength(t) ，SubString(s,8,6) ，Index(s,q,1) 。

证明：任何一棵满二叉树中的分支数B满足B=2(n₀－1)，其中n₀为叶子结点个数。

编写算法，判断二叉链表表示的两棵二叉树T1和T2是否相等。

若两棵二叉树B1和B2皆为空，或者皆不空并且B1的左、右子树和B2的左、右子树分别相似，则称二叉树B1和B2相似。编写算法，判定给定的两棵二叉树是否相似。

编写算法，求二叉链表表示的二叉树T的高度。

编写递归算法，求二叉链表表示的二叉树T的结点个数。

编写递归算法，求二叉链表表示的二叉树T的叶子结点个数。

编写递归算法，求二叉链表表示的二叉树T的度为1的结点个数。

编写递归算法，求二叉链表表示的二叉树T的度为2的结点个数。

编写递归算法, 交换二叉链表存储的二叉树中每个结点的左、右子树。

编写递归算法, 按中序顺序输出二叉链表存储的二叉树中所有度为1的结点。

编写递归算法, 按先序顺序输出二叉链表存储的二叉树中所有度为2的结点。

编写递归算法, 按后序顺序输出二叉链表存储的二叉树中所有的叶子结点。

编写算法，判定给定的二叉树是否是完全二叉树。

假设二叉排序树（t为指向根结点的指针）中各元素值均不相同，设计一个递归算法按递增顺序输出树上各元素值。

已知某二叉树的先序序列为 { ABHFDECKG }，中序序列为 { HBDFAEKCG }, 画出该二叉树。

写出二叉链表表示的二叉树的层序遍历算法。

在结点个数为n(ngt;1)的各棵树中，高度最大的树的高度是多少？它有多少叶结点？多少分支结点？

在结点个数为n(ngt;1)的各棵树中，高度最小的树的高度是多少？它有多少叶结点？多少分支结点？

已知一组权值分别是3、12、7、4、2、8、11，画出叶子分别对应这些权值的Huffman树，并求其带权路径长度。

设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10，试为这8个字母设计Huffman编码。

已知某二叉树中序序列为 { DCBGEAHFIJK } ，后序序列为 { DCEGBFHKJIA }, 画出该二叉树。

证明：对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1。

证明：深度为k的二叉树至多有2^k－1个结点(k≥1)。

证明：在二叉树的第i层上至多有2^i-1个结点(i≥1)。

假设一个有向图的顶点集合V={c1,c2,c3,c4,c5},弧集S={lt;c1,c2gt;,lt;c1,c3gt;,lt;c2,c5gt;,lt;c3,c2gt;,lt;c3,c4gt;,lt;c5,c4gt;},(1)试根据上述关系，画出该有向图；（2）该图有环吗？若无环，则写出它的一个拓扑有序序列；若有环，请写出组成环的顶点序列。

假设一个有向图的顶点集合V={c1,c2,c3,c4,c5},弧集S={lt;c1,c2gt;,lt;c1,c3gt;,lt;c2,c5gt;,lt;c3,c2gt;,lt;c3,c4gt;,lt;c5,c4gt;},(1)试根据上述关系，画出该有向图；（2）写出该图从 c1出发的一个广度优先遍历序列。

假设一个有向图的顶点集合V={c1,c2,c3,c4,c5},弧集S={lt;c1,c2gt;,lt;c1,c3gt;,lt;c2,c5gt;,lt;c3,c2gt;,lt;c3,c4gt;,lt;c5,c4gt;},(1)试根据上述关系，画出该有向图；（2）写出该图从 c1出发的一个深度优先遍历序列。

基于图的广度优先遍历策略写一算法，判断以邻接表方式存储的无向图中连通分量的个数。

基于图的深度优先遍历策略写一算法，判断以邻接表方式存储的无向图中从顶点vi到顶点vj是否有路径存在。

基于图的深度优先遍历策略写一算法，判断以邻接表方式存储的无向图中连通分量的个数。

假设有5项活动C1～C5，每项活动要求的前驱活动如下： C1：无； C2：C1，C3； C3：C1； C4：C3，C5 C5：C2； 试根据上述关系，画出相应的有向图，再写出一个拓扑排序序列。

基于图的广度优先遍历策略写一算法，判断以邻接表方式存储的无向图中从顶点vi到顶点vj是否有路径存在。

设有一组关键字序列{19，1，23，14，55，20，84，27，68，11，40}， 按表中元素顺序构造一棵二叉排序树，画出这棵树，并求其在等概率情况下查找成功时的平均查找长度。

画出对12个关键字的有序表进行折半查找的判定树，并求等概率情况下折半查找成功时的平均查找长度。

设有一组关键字序列{19，1，23，14，55，20，84，27，68，11}，从空树开始，按表中元素顺序构造一棵2_3树(3阶B_树)，若此后再删除55，84，画出每一步执行后2_3树的状态。

从空树开始，画出按以下次序向2_3树中插入关键字的建树过程：20，30，50，52，60，68，70。画出每一步执行后的树的状态。

设哈希函数H(key)=key MOD 13,用线性探测再散列法解决冲突。对关键字序列{ 55，19，01，68，23，27，20，84 }在地址空间为0-10的散列区中建哈希表，画出此表，并求等概率情况下查找成功时的平均查找长度。

设散列函数H(key)=key MOD 11,用链地址法解决冲突。对关键字序列{ 22、41、53、46、30、13、01、67}在地址空间为0-10的散列区中建散列表，画出此表，并求等概率情况下查找成功时的平均查找长度。

设关键字序列为{2，25，72，36，11，20，17，13，24，32}。h (key) = key mod 7,用链地址法处理冲突在地址空间为0-6的散列区中建散列表，画出此表，并求等概率情况下查找成功时的平均查找长度。

设散列函数H(key)=key MOD 11,用线性探测再散列法解决冲突。对关键字序列{ 13，28，72，5，16，18，7，11，24 }在地址空间为0-10的散列区中建散列表，画出此表，并求等概率情况下查找成功时的平均查找长度。

设散列函数H(key)=key MOD 7,用线性探测再散列法解决冲突。对关键字序列{ 13，28，72，5，16，8，7，11 }在地址空间为0-10的散列区中建散列表，画出此表，并求等概率情况下查找成功时的平均查找长度。

在地址空间为0-16的散列区中，对以下关键字序列(Jan,Feb,Mar,Apr,May, June,July,Aug,Sep,Oct,Nov,Dec)按链地址法处理冲突构造散列表，设散列函数H(x)=i/2,其中i为关键字中第一个字母在字母表中的序号。画出该散列表并求在等概率情况下查找成功时的平均查找长度。

写一个算法判定给定的二叉树是否是二叉排序树。设此二叉树以二叉链表作存储结构，且表中结点的关键字均不同。

写算法在一个整数数组A[0..n-1]中使用顺序查找方法查找给定的某整数x。

设关键字集合为{10，2，14，8，12，13}，现对其从小到大排序，写出简单选择排序每一趟结束时的关键字状态。

已知关键字序列{70，83，100，65，10，9，7，32}，现对其从小到大排序，写出快速排序每一趟结束时的关键字状态。

使用冒泡排序或快速排序两种基于交换的内部排序方法对一组关键字序列进行排序，如果从节省时间的角度来考虑最好选择哪种排序方法？如果从节省存储空间的角度来考虑最好选择哪种排序方法？如果从排序稳定性的角度考虑最好选择哪种排序方法？分别回答并说明理由。

设关键字集合为{10，2，14，8，12，6}，现对其从小到大排序，写出冒泡排序每一趟结束时的关键字状态。

设关键字集合为{10，2，14，8，12，13}，用堆排序方法对其从小到大排序，写出堆排序的初态、建堆和排序过程中重建堆的过程。

设关键字集合为{10，2，14，8，12，13}，写出用希尔排序方法对序列进行从小到大排序排序时每一趟结束时的关键字状态（设增量序列为3，2，1）。

已知关键字序列{70，83，100，65，10，9，7，32}，现对其从小到大排序，写出直接插入排序每一趟结束时的关键字状态。

判断序列{ 26，33，35，29，19，12，22 }是否是堆，若不是，把它调整为堆（要求记录交换次数最少），写出调整后的序列。若是，写出判断的理由。

在快速排序过程中，通常取序列中的第1个记录作为枢轴，以它为“分界线”重排其余记录。但当初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，为改进之，应如何选取枢轴记录？