2017数据结构

选择：

非常简单，最基础的证明。

最难的一道：n层的整二叉树两个节点的最远距离是多少？

分析：
    最大距离可能一个在左子树，一个在右子树中，通过根节点；也可能出现在左/右子树中，不经过根节点。通过根节点的最大距离为左右子树深度的和加1；所以可以同时计算树的深度和最大距离。

void FindMaxDis(BSTreeNode *pNode, int &deepth, int &maxdis)
{
    if (pNode==NULL)
    {
        deepth=0;maxdis=0;
        return;
    }
    int l_deepth=0,r_deepth=0;
    int l_maxdis=0,r_maxdis=0;
 
    if (pNode->m_pleft)
        FindMaxDis(pNode->m_pleft,l_deepth,l_maxdis);
    if (pNode->m_pright)
        FindMaxDis(pNode->m_pright,r_deepth,r_maxdis);
 
    deepth = (l_deepth > r_deepth ? l_deepth : r_deepth) + 1;
 
    maxdis = l_maxdis > r_maxdis ? l_maxdis : r_maxdis ;
 
    maxdis = (l_deepth+r_deepth) > maxdis ? (l_deepth+r_deepth) : maxdis;
 
}
int FindMaxDis(BSTreeNode *pNode)
{
    int deepth, maxdis;
    FindMaxDis(pNode,deepth,maxdis);
 
    return maxdis;
}

---

填空：

考了一组二叉树的性质，折半二叉树的构造。
分析：
    折半查找：只适用于有序表，且限于顺序存储结构(线性链表无法进行折半查找)
(1)思想：又称二分查找，对于已经按照一定顺序排列好的列表，每次都用关键字和中间的元素对比，然后判断是在前部分还是后部分还是就是中间的元素，然后继续用关键字和中间的元素对比。
(2)时间复杂度：T(n) =O(logn)。具有n 个结点的完全二叉树的深度为，在这里尽管折半查找判定二叉树并不是完全二叉树，但同样相同的推导可以得出，最坏情况是查找到关键字或查找失败的次数也如此。其时间复杂度远好于顺序查找的时间复杂度O(n)了。

(3)程序：
Int BinSrch(RecordList l, KeyType k)  
    {  
             low = 1;  
             high = l.length;  
             while(low <= high)  
             {  
                  mid = (low + high) / 2;  
                  if(k == l.r[mid].key)  
                       return mid;  
                  else if(k < l.r[mid].key)  
                       high = mid -1;  
                  else  
                       low = mid + 1;  
             }  
             return 0;  
    }  

(4)小结：由于折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找比较适合。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，则不建议使用。

---

判断：

依然很简单。

---

简答：

1.如何将一个顺序的单链表逆序？
2.20个结点折半二叉树，叶子节点都是哪几个。
3.给你几行数列，问这是什么排序方法。
4.构造哈夫曼树，求平均路径。
5.普里姆算法求最小生成树的构造。

---

编程：

1.在一个有序链表中插入一个数字，让它依然有序。
2.在不考虑空间的情况下，将链表中大于第一个结点的结点放到左边，小于这个结点的放到右边。（类似于火车调度算法）