数据结构 队列

Question

1． 请编写一个算法，把一个队列逆置，在算法中可以使用栈，可以调用栈和队列的基本操作，但不允许直接处理栈和队列中的元素。
2． 对于循环队列，
（1） 试写出求队列长度的算法；
（2） 试写出判断队列是否为空的算法。
要代码啊

Answer 1

作业
第一章
1． 编写一个算法，判断浮点数数组a[]中是否有值大于1000的成员。若有，则给出大于1000的成员中下标最小那个成员的下标。指出算法中的基本操作和关键操作，分析你的算法的时间复杂性，并用大O记法表示之。
2． 斐波那契数列定义为： 给出一个计算第 个斐波那契数的非递归的算法，指出算法中的基本操作，分析你的算法的时间复杂性并用大O记法表示之。
第二章
1． 对线性表（18，8，21，7，3），画出相应的带表头结点的双向循环链表。
2． 编写一个算法，在带表头结点的有序单链表中，插入值为 的结点，并使新的链表仍然有序。
第三章
1． 请编写一个算法，把一个队列逆置，在算法中可以使用栈，可以调用栈和队列的基本操作，但不允许直接处理栈和队列中的元素。
2． 对于循环队列，
（1） 试写出求队列长度的算法；
（2） 试写出判断队列是否为空的算法。
第四章
1． 假设3维数组 以列序为主序的方式顺序存储，请为它推导出地址计算公式。
2． 编写一个算法，计算子串S2在串S1中的出现次数。

第五章
1． 请给出下图所示的树的前序、后序和层次遍历序列。

2． 已知某二叉树的前序序列和中序序列分别是ABDECFGH和DBEAGFHC，请画出该二叉树，并写出其后序序列。
3． 给定一棵以二叉链表形式存储的二叉树，root指向其根。请编写算法求二叉树的高度。
4． 给定一棵以二叉链表形式存储的二叉树，root指向其根。请编写算法求出二叉树中值为x的结点的数目。
5． 已知下图所示的二叉树是由某森林转换而来的。请给出原森林。

6． 假定有八个字符，它们出现的概率分别为：0.07、0.09、0.14、0.19、0.23、0.44、0.58和0.77。
（1）请给出这8个字符的哈夫曼树和哈夫曼编码；
（2）编码树的WPL的实际意义是什么？
第六章
1． 对于如下图所示的有向图，请给出
(1) 各顶点的入度和出度
(2) 强连通分量和弱连通分量
(3) 邻接矩阵
(4) 邻接表和逆邻接表

2． 假设有向图存储为邻接矩阵，请编写一个算法，求出指定顶点的入度和出度。
3． 对于如下图所示的无向图，分别画出其深度优先搜索和广度优先搜索生成的树。

4． 对下面的无向带权图应用求最短路经的Floyd算法，求出每对顶点之间的最短路径，并写出在算法的执行过程中所求得的各个矩阵。

5． 对如下图所示的无向带权图，按照Kruskal算法求出最小生成树，并画出每一步所得到的中间结果。

第七章
1． 试比较顺序查找算法和二分查找算法的特点、优缺点。
2． 请编写一个递归的二分查找算法。
3． 从一棵空的查找树开始，依次插入键值71，32，103，66，135，82，57，91，画出每次插入后所得到的查找树，再依次删除57、82、71，画出每次删除后所得到的查找树，并对最终得到的查找树求出等概率情况下的平均成功查找长度。
4． 请编写一个判断二叉树T是否为查找树的算法，假定二叉树T是以标准形式存贮的。
5． 从一个空的散列表开始，依次为插入关键字Jan、Feb、Mar、Apr、May、Jun、Jul、Aug、Sep、Oct、Nov、Dec，散列函数为 为关键字key第一个字母的序号，如 散列表长度为17。分别使用
（1） 线性探测法
（2） 链地址法
建立散列表。请分别画出散列表，并求出等概率情况下的平均成功查找长度。

第八章
1． 分别用下列排序算法对关键字序列（49，7，50，5，94，16，90，29，71）进行排序，写出每一趟排序所得到的中间结果。
（1） 直接插入排序
（2） 希尔排序
（3） 改进的冒泡排序
（4） 快速排序
（5） 直接选择排序
（6） 堆排序
（7） 合并排序
2． 一种冒泡排序算法是所谓“上浮式的”，即每趟排序都把较小的关键字“浮”到上面（数组下标较小的那一边）去。请编写一个改进的“下沉式的”冒泡排序算法。
3． 举例说明直接选择排序算法、快速排序算法和堆排序算法不是稳定的。

Answer 2

1，把队首指针和队尾指针互换

2（1）设置一个临时指针，指向队首元素，然后遍历整个队列并计数，直到临时指针指向队尾为止。
（2）若队首指针等于队尾指针则队列为空。

Answer 3

我不会做上面的题目，哪位高手能帮忙解决吗？多谢啦