南辕北辙 沧海桑田

压力越来越大，因为每个计划周都有完不成的任务，事实上这周学习的内容依然属于七月份的计划。

造成计划拖欠的原因，一方面确实来源于人性的脆弱——缺乏意志，直接表现在6000个单词直到这周才可能完全完成，而按照计划，8月份应该拓展到GRE词汇，尽量提高英语，至少考不上，也学了点实在的东西；当然计划的打乱，也来自于不可预计的突发事件和不可估量的任务量，单计算机原理一门课，我已经看了整整2000页的书了，而且还没有真正的接触参考书，只能说制定粗的总计划时，并不了解这门课程，如果将来考上，可以指点别人的时候，会多出很多经验。

不过有一点还是令人高兴的，终于感觉进入状态了，无论是记忆力还是意志力都在恢复。这周的计划比较单纯，只是看《计算机设计与组成》的郑纬民翻译版，以及最后的2000个单词，目前看来这周完成这些任务还是比较乐观的。八月份的主要任务是概率论和数理统计，操作系统和词汇，以及打算新加入的英语阅读训练和高数基础的巩固(尽管sam认为高数辅导应该给本科生准备期末考试用的，我还是打算充分利用它来作为一个基础的巩固，再高的楼离开稳固厚实的地基都是空中楼阁)，其中《操作系统概念》因为是英文版，所以必须至少延迟一周，等英语词汇巩固一遍，下面安排接下来三周的具体任务。

第二周
《概率论与数理统计》1-8章 包括习题；
巩固刘毅10000及考研单词，保持每天2个小时单词背诵。
六级考试的英语卷子，做了它！

第三周
《操作系统概念》每天保持8个小时左右，才有可能在6天内看完，不过我对操作系统的周边还是了解比较多，应该不难；
做一些线性代数的习题。一个小时差不多。
利用奇迹英语背 GRE核心词汇。同时每天还是巩固考研单词一组。

第四周
考试虫的《阅读基本功》，为做阅读训练准备；
《高等数学辅导》
GRE核心词汇。

八月份过后，数学基本上算完成了全新的学习，专业课，学习了一半，压力啊，很多人都已经在这个时候完成了第一遍的复习，开始做题了。加油！

8-4 用邻接矩阵表示图，若图中有1000个顶点，1000条边，则形成的邻接矩阵有多少矩阵元素？有多少非零元素？是否稀疏矩阵？


形成的邻接矩阵有10^6个元素；如果是有向图则拥有1000个非零元素，若是无向图则有1000×2=2000个非零元素；是稀疏矩阵。


8-5 用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？

矩阵元素的个数与顶点个数相关。非零元素与边的条数相关。


8-6 有n个顶点的无向连通图至少有多少条边？有n个顶点的有向强连通图至少有多少条边？试举例说明。

n个顶点连通，如果将n个顶点排成一直线，则很容易知道，至少需要n-1条边才能把它连通。
还是和刚才一样，只不过多一条边，将首尾连起来，使得从每个定点开始都可以回到该顶点。
例子已举。


8-7 对于有n个顶点的无向图，采用邻接矩阵表示，如何判断以下问题：图中有多少条边？任意两个顶点i和j之间是否有边相连？任意一个顶点的度是多少？

图中的边数等于邻接矩阵中非零元素的一半；查看矩阵中E[i][j]或者E[j][i]是否等于零，零的话不联通，反之连通；假设要观察顶点i的度，只要查看i行有多少个非零元素，即为i的度（如果查看i列也一样，因为无向图的邻接矩阵是行列对称的）。


8-9 试扩充深度优先搜索算法，在遍历图的过程中建立生成森林的左子女——右兄弟链表。算法的首部为
Void Graph::DFS(const int v, int visited[], TreeNode< int > *t)
其中，指针t指向生成森林上具有图顶点v信息的根结点。

答案建立生成森林的主函数里的q，定义很奇怪。还是老老实实按照书中DFS的定义来写。
声明：不写模板了。可以直接修改TreeNode的指针.

void Graph::DFS(){   //主过程
  int* visited=new int[n];   //n为图中顶点的个数 
  for(int i=0;i< n;i++)visited[i]=0;  //初始化辅助数组 
  Tree< int > &T;        //这里要不要写成 Tree T？ 还是迷糊 
  DFS(0,visited,T.root);  //从顶点0开始构建生成森林
  delete[] visited;
}

void Graph::DFS(const int v, int visited[], TreeNode< int > *t){
  t.SetData(GetValue(v));     //访问该顶点，拷贝值到相应森林结点。
  visited[v]=1;               //修改为已访问
  int w=GetFirstNeighbor(v);  //找到顶点v的第一个邻接顶点w
  t=t->FirstChild;            //t指向t的左子女
  while(w!=1){                //有邻接顶点
    if(!visited[w])           //如果没有访问过
      DFS(w,visited,t);       //从该顶点开始建立生成森林
    w=GetNextNeighbor(v,w);   //找到v的下一个邻接顶点
    t=t->NextSibling;         //同时把t指向t的右兄弟
  }
}

8-10 用邻接表表示图时，顶点个数设为n，边的条数设为e，在邻接表上执行有关图的遍历操作时，时间代价是O(n*e)?还是O(n+e)?或者是O(max(n,e))?

必须要顺邻接表的顶点表挨个检查，并且沿着每条边向下遍历，所以时间代价为O(n+e)。


8-16 试证明在一个有n个顶点的完全图中，生成树的数目至少有2^(n-1)-1

这题有如下疑问
首先生成树的根固定么？如果不固定的话，就相当于将这n个顶点得到一个排序序列，就是生成树了。p（n）显然是答案，当然p(n)永远都大于2^(n-1)-1.这样的解答貌似太简单了。
然后我们假设必须从某个顶点开始，作为生成树的根，那么问题就变成剩下的n-1个顶点，做一个排序序列，那么显然就是比较p(n-1)与2^(n-1)-1。而这个显然必须在n>=5时才能成立，好像又不对。
迷惑中。


8-18 利用Dijkstra算法的思想，设计一个求最小生成树的算法。

计算连通网络的最小生成树的dijkstra算法可描述如下：将连通网络中所有的边以方便的次序逐步加入到初始为空的生成树的边集合T中。每次选择并加入一条边后，需要判断它是否会与先前加入T的边构成回路。如果构成了回路，则从这个回路中将权值最大的边退选。

具体的实现，答案的程序看不太懂。并且从这里开始暂时不把数据结构的答案放到网上了。因为迷糊的东西太多了。