几个数据结构问题

1 假设序列有n个关键字不同的记录构成，要求不经排序从中选出关键字从大到小的前k（k《n）个记录，试问如何进行才能使所作的关键字比较次数达到最小？？？？
2 {k1,k2,......kn,k(n+1)}序列中，{k1,k2,......kn}已经构成堆，问如何将{k1,k2,......kn,k(n+1)}调整为堆，最坏情况下，要进行几次关键字的比较，举一个n=6的序列说明。
3 以深度优先搜索为策略，在有向图g的邻接表中，求顶点Vi到顶点Vj（i！=j）的路径，存放在数组Path[n]中（n为图g 的顶点数），编写算法。
4 设二叉树bt以二叉链表为存储结构，试编写利用栈极其操作求二叉树bt高度的非递归算法depth（bt）。

5 个解决方案

#1

顶!!!!!!!!!!!!!!!!!!111

#2

学习楼上的

顶!!!!!!!!!!!!!!!!!!111

^_^

#3

1.
先取k数并对这k个数排序,排序过程需要比较(k-1)!(!是阶乘)次.
对余下的n-k个数,依次加进已序队列。对每个数,需比较log2(k)(2的底的对数)次.插入完成后清最小的数(不需比较,位于队列尾).
合计:(k-1)!+(n-k)*log2(k) ;
2.logN

#4

1:使用堆排序

#5

使用堆排序，具体要怎么做啊
  谢谢！！