【笔记】选择题笔记+数据结构笔记

连通分量是极大连通子图
一个连通图的生成树是一个极小连通子图

无向图的邻接表中，第i个顶点的度为第i个链表中的结点数
邻接表和邻接矩阵对不同的操作各有优势。

最短路径算法:

1. 单源最短路径
   已知图G=(V,E)，我们希望找出从某给定的源结点S∈V到V中每个节点的最短路径
   Dijkstra算法复杂度$O(n^2)$
2. 全源最短路径
   任意两个节点之间的最短路径
   Floyd算法复杂度$O(n^3)$

最小生成树Prim算法和Kruskal算法【O(mlogm)】
相关阅读资料
Prim算法通常以邻接矩阵作为储存结构。

时间复杂度在对数级别的时候，底数数字的改变对于整个时间复杂度没有影响
静态链表方便经常插入和删除

二叉排序树的中序序列才是有序的
二叉排序树左子树上的值均大于根节点的值，右子树的值均小于根节点的值【不仅仅是左孩子和右孩子】
新插入的关键字总是作为叶节点插入，叶节点不一定总是处于最底层
二叉排序树只有删除的是叶节点才能得到与原来一样的二叉排序树

2014 41

二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储，结点结构为:

其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针，请设计求T的WPL的算法，要求:（1）给出算法的基本设计思想; （2）使用C或C++语言，给出二叉树结点的数据类型定义; （3）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

方法一先序遍历

解决方法：考查二叉树的带权路径长度,二叉树的带权路径长度为每个叶子结点的深度与权值之积的总和，可以使用先序遍历或层次遍历解决问题。

（1）算法的基本设计思想基于先序递归遍历的算法思想是用一个static变量记录wpl,把每个结点的深度作为递归函数的一个参数传递，算法步骤如下:若该结点是叶子结点，那么变量wpl加上该结点的深度与权值之积，若该结点非叶子结点，那么若左子树不为空，对左子树调用递归算法，若右子树不为空，对右子树调用递归算法，深度参数均为本结点的深度参数加一；最后返回计算出的wpl即可。

（2）二叉树结点的数据类型定义如下：

#include<stdio.h>
#include<stdlib.h>typedef struct BiTiNode
{
int weight;
struct BiTiNode *lchild,*rchild;
}BiTiNode,*BiTree;
/**
二叉树数据结构定义
**/
int WPL(BiTree root){return wpl_PreOrder(root,1);
}
int wpl_PreOrder(BiTree root,int deep){static int wpl=0;//静态变量存储wpl 静态局部变量//作用域为这个函数//若为叶子结点if(root->left==NULL&& root->right==NULL)wpl+=deep*root->data;//若左子树不空，对左子树递归遍历if(root->left!=NULL)wpl_PreOrder(root->left,deep+1);//若右子树不空，对右子树进行递归遍历if(root->right!=NULL){wpl_PreOrder(root->right,deep+1);}return wpl;
}

在先序遍历的算法中，static 是一个静态变量，只在首次调用函数时声明wpl并赋值为0，以后的递归调用并不会使得wpl为0。考虑到历年真题算法答案通常都直接仅仅由一个函数构成，所以参考答案使用static而不是全局变量。

方法二

（1）算法的基本设计思想基于层次遍历的算法思想是使用队列进行层次遍历，并记录当前的层数，当遍历到叶子结点时，累计wpl;当遍历到非叶子结点时对该结点的把该结点的子树加入队列;当某结点为该层的最后一个结点时，层数自增1; 队列空时遍历结束，返回wpl。
（2）二叉树结点的数据类型定义

int wpl_LevelOrder(BiTree root){BiTree q[MaxSize];int end1,end2;//end1 头指针，end2尾指针end1=end2=0;//头指针指向队头元素，尾指针指向队尾的后要给元素int wpl=0,deep=1;//初始化wpl和深度BiTree lastNode;//lastNode用来记录当前层的最后一个结点BiTree newlastNode;//newlastNode用来记录下一层的最后一个结点lastNode=root;//lastNode初始化为根结点newlastNode=NULL;//newlastNode初始化为空q[end2++]=root;///根节点入队while(end1!=end2){//层次遍历//若队列不空则循环BiTree t = q[end1++];//拿出队列中的头一个元素if(t->lchild==NULL&&t->rchild==NULL)wpl+=deep*t->weight;//若为叶子节点，统计wplif(t->lchild!=NULL){//若非叶子节点把左节点入队q[end2++] = t->lchild;newlastNode = t->lchild;}//并设下一层的最后一个结点为该结点的左节点if(t->rchild!=NULL){q[end2++]=t->rchild;newlastNode=t->rchild;}if(t==lastNode){//结点为本层最后一个结点。更新lastNode;lastNode=newlastNode;deep+=1;}}
return wpl;
}

---