Question

高分解答数据结构题目

这里有十个很好的题目，请高手给予尽可能多的解答，给出算法和数据结构，C++语言实现 答的好的我会追加分数！谢谢！
1. 判断一个链表是否有循环, 打印一个可能带环的链表中所有元素各一次。
2. 寻找链表中倒数第m个元素。
3. 判断一个ASCII字符串中是否有重复字符。
4. 判断两个链表是否相交，寻找相交节点。
5. 定义二叉树两个结点的最小距离为这两个结点的最近公共祖先分别到这两个结点的路径长度之和。请设计一种方法，找出给定二叉树中任意两个结点的最小距离，可以考虑以图形显示之。
6. 设计一个程序实线二叉树的层次遍历，要求每层之间的数据用一个空格分开。二叉树采用二叉链表方式进行存储。
7. 利用大顶堆实现一个优先队列。对于队列的操作应该至少支持下列几种指令：
Void enqueue(int ObjectID, int Priority);
Int dequeue();
Void changeweight(int ObjectID, int newPriority);
函数enqueue向优先队列中插入一个ID号为ObjectID,优先级为priority的新对象。函数dequeue从优先队列中删除优先级最高的对象，并返回该对象的ID号。函数changeweight将ID号为ObjectID的对象的优先级改为newPriority。你需要一种机制，以便获取所需要对象在堆中的位置。你还需要对堆的实现进行修改，以存储对象在数组中的位置，使得堆中对象的修改可以在辅助数组结构中记录下来。

8. 套汇是指利用汇率差异将一单位的货币转换为大于一单位的同种货币。例如，假设1美元兑换8.8人民币，1人民币兑换0.1英镑，1英镑兑换1.5美元，那么，如果一个人拿着1美元先兑换成人民币，再把人民币兑换成英镑，最后将英镑兑换成美元，最后他能得到1*8.8*0.1*1.5=1.32美元，从而获得了利润，这就是套汇。假设有n种货币v1,v2,…,vn和有关汇率的n*n矩阵，其中A[I,j]是指一单位货币vi兑换成货币vj的单位数，要求设计一个程序判断是否存在一个货币序列vi1,vi2,…,vik使得A[i1，i2]*A[i2,i3]*…*A[ik,i1]>1,如果存在，则输出所有这样的货币序列，如果不存在则输出空，并确定算法的时间代价。
9. 假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场，设计一个有效的贪心算法进行安排。
10. 设有n种不同面值的硬币，各硬币的面值存在于数足T[n]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[n]中。对任意钱数0<=m<=20009，设计一个用最少硬币找钱m的方法。
三楼的能否再详细些 我的qq 869287791 之后答应给你追加一百分，我需要比较完善的参考，3q!

Answer 1

1. 判断一个链表是否有循环, 打印一个可能带环的链表中所有元素各一次。
任取链表一个节点开始遍历链表是否有节点又为此节点， 后一问题雷同
2. 寻找链表中倒数第m个元素。
给出两个指示指针分别指向当前遍历的元素和当前m个元素的指针，当遍历时，两个指针都往前移动一个位置。
3. 判断一个ASCII字符串中是否有重复字符。
建立一个128长度的数组分别保持ascii每个字符的出现次数。
4. 判断两个链表是否相交，寻找相交节点。
把第二个链表连接进第一个链表，如果出现环，就说明相交
5. 定义二叉树两个结点的最小距离为这两个结点的最近公共祖先分别到这两个结点的路径长度之和。请设计一种方法，找出给定二叉树中任意两个结点的最小距离，可以考虑以图形显示之。
把两个节点所有的父指针连接分别形成两个链表，它们必然相交，后面的思路类似上题。
6. 设计一个程序实线二叉树的层次遍历，要求每层之间的数据用一个空格分开。二叉树采用二叉链表方式进行存储。
呵呵，小样的不要以为你穿个马甲我就认不出来了。。。。二叉树层次遍历，典型的用链表实现，这题不过是让链表的节点保存内容除了树节点指针外，还有层次此节点层次信息。
7. 利用大顶堆实现一个优先队列。对于队列的操作应该至少支持下列几种指令：
Void enqueue(int ObjectID, int Priority);
Int dequeue();
Void changeweight(int ObjectID, int newPriority);
函数enqueue向优先队列中插入一个ID号为ObjectID,优先级为priority的新对象。函数dequeue从优先队列中删除优先级最高的对象，并返回该对象的ID号。函数changeweight将ID号为ObjectID的对象的优先级改为newPriority。你需要一种机制，以便获取所需要对象在堆中的位置。你还需要对堆的实现进行修改，以存储对象在数组中的位置，使得堆中对象的修改可以在辅助数组结构中记录下来。
一般的编程问题......不大会了。。。。

8. 套汇是指利用汇率差异将一单位的货币转换为大于一单位的同种货币。例如，假设1美元兑换8.8人民币，1人民币兑换0.1英镑，1英镑兑换1.5美元，那么，如果一个人拿着1美元先兑换成人民币，再把人民币兑换成英镑，最后将英镑兑换成美元，最后他能得到1*8.8*0.1*1.5=1.32美元，从而获得了利润，这就是套汇。假设有n种货币v1,v2,…,vn和有关汇率的n*n矩阵，其中A[I,j]是指一单位货币vi兑换成货币vj的单位数，要求设计一个程序判断是否存在一个货币序列vi1,vi2,…,vik使得A[i1，i2]*A[i2,i3]*…*A[ik,i1]>1,如果存在，则输出所有这样的货币序列，如果不存在则输出空，并确定算法的时间代价。
题目太长了。。
9. 假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场，设计一个有效的贪心算法进行安排。

？？？？跟贪心有关系吗？就是一个线程池的模拟，
10. 设有n种不同面值的硬币，各硬币的面值存在于数足T[n]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[n]中。对任意钱数0<=m<=20009，设计一个用最少硬币找钱m的方法。
递归求解，或者转化为简单的数学进制模型，这个问题首先要求出解，然后在所有的解里找到最少的那个，easy。

Answer 2

不细说了，也没那么多时间，提供前几个的基本思路，然后再网上一搜就差不多了
1. 不同步长指针追赶算法，有环的话快的会追上慢的。
2. 两个指针，先让一个停在开头另一个后移m个，然后两个指针整体移动，直至后面的那个指针到达链表尾部。
3. 用一个256大小的bool数组，初始化为0，出现过的字符标为1，遇到重复就有了。
4. 相交链表最后一段是重叠的，把两个链表指针都移到尾部，指针值相等则说明相交。然后通过先移差量再同步移动比较的方法找出交点。
5. 深度遍历二叉树，把访问序列存起来，比较两个节点的访问序列，第一个不同的就是最近的公共祖先。

Answer 3

4 判断两个链表是否相交，只要判断最后一个节点是否相同就可以了。。。。不需要麻烦的。。

Answer 4

答案我发你的邮箱里了，给我分加分

Answer 5

我先声明,这些问题我不懂,但我想问你能否详细介绍这些问题的实践意义?