数据结构设计实验
1. 求二叉树中节点的最大距离.如果我们把二叉树看成一个图，父
子节点之间的连线看成是双向的，我们姑且定义\"距离\"为两节点之间边的个数。写一个程序，求一棵二叉树中相距最远的两个节点之间的距离。
2. 在二元树中找出和为某一值的所有路径题目：输入一个整数和
一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。例如 输入整数22和如下二元树 10 / \\ 5 12 / \\ 4 7
则打印出两条路径：10, 12和10, 5, 7。 二元树节点的数据结构定义为：
struct BinaryTreeNode // a node in the binary tree{int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of nodeBinaryTreeNode *m_pRight; // right child of node};3. 在一个字符串中找到第一个只出现一次的字符。如输入
abaccdeff，则输出b。
4. n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始，每次从
这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。当一个数字删除后，从被删除数字的下一个继续删除第m个数字。求出在这个圆圈中剩下的最后一个数字。5. 跳台阶问题
题目：一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。
求总共有多少总跳法，并分析算法的时间复杂度。6. 求一个矩阵中最大的二维矩阵(元素和最大).如:
1 2 0 3 42 3 4 5 11 1 5 3 0中最大的是:4 55 3
要求:(1)写出算法;(2)分析时间复杂度;(3)用C写出关键代码
7.
8.
9. 输入一个整数数组，调整数组中数字的顺序，使得所有奇数位
于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
10. 最长公共字串。题目：如果字符串一的所有字符按其在字符串
中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子串，则输出它们的长度4，并打印任意一个子串。11. 数组中有一个数字出现的次数超过了数组长度的一半，找出这
个数字。
12. 找出二叉树两个结点的最低共同父祖先
13. 复杂链表的复制题目：有一个复杂链表，其结点除了有一个
m_pNext指针指向下一个结点外，
还有一个m_pSibling指向链表中的任一结点或者NULL。其结点的C++定义如下： struct ComplexNode{
int m_nValue;
ComplexNode* m_pNext; ComplexNode* m_pSibling;};
14. 12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第
二排比对应的第一排的人高,问排列方式有多少种?
15. 在一个int数组里查找这样的数，它大于等于左侧所有数，小于
等于右侧所有数。
16. 系统有很多任务，任务之间有依赖，比如B依赖于A，则A执行完
后B才能执行
，设计一个函数（不考虑并行度），最快的方法完成所有任务。
17. 设计相应的数据结构和算法，尽量高效的统计一片英文文章
（总单词数目）里出现的所有英文单词，按照在文章中首次出现的顺序打印输出该单词和它的出现次数。18. 完成图的深度优先遍历
19. 建立一个先序线索二叉树，完成对它的遍历20. 迷宫问题
21. 找出海量数据中最大的n个数据。
22. 编制一个算法将二叉树的左右子树交换23. 多项式加法
24. 图的深度优先遍历
25. 利用一个已知的中序序列和一个已知的先序序列创建这个二叉
树
26. 利用一个已知的后序序列和一个已知的先序序列创建这个二叉
树
27. 判断两个单链表是否相交，如果相交，给出相交的第一个点
（两个链表都不存在环）。
28. 设计一个算法判断一个二叉树是否为平衡二叉树。29. 设计一个算法判断一个图中是否有环
30. 设计一个算法将一个顺序存储的二叉树转化为二叉链
表存储的二叉树。
31. 求二叉树第k层上的叶子结点数。32. 判断一个二叉树是否为完全二叉树
33. 设计一个算法，求出二叉排序树中指定结点的层数34. 设计一个算法，求出二叉树的宽度
35. 删除二叉排序树中的一个结点，使该二叉排序树仍为二叉排序
树。
各班同学在上述题目中选一道题，不同同学题目不可相同。实验报告要求提交源程序和纸质报告。在报告中需要详细说明编程的思想。
