数据结构相关难点
问题：对链表设置头结点的作用是什么？
解答：
其好处有:
(1) 对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些。
(2) 对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。
问题：何为队列上溢现象？何为假溢现象？有哪些解决方法？并分别简述其工作原理。
解答：
在队列的顺序存储结构中，设队头指针为front,队尾指针为rear,队的容量为MaxSize。当有元素要加入队列时，若rear=MaxSize（初始时rear=0），则发生队列的上溢现象，该元素不能加入队列。
队列的假溢出现象是指队列中还有空余的空间，但元素不能进队列。造成这种现象的原因是由于队列的操作方式所致。
解决队列假溢出的方法如下：
（1）建立一个足够大的存储空间，但这样做会造成空间浪费。
（2）采用环形队列方式。
（3）采用平移元素的方法，当删除一个对头元素时，依次移动队中的元素，始终使front指向队列中的第一个位置。
问题：若使用循环链表来表示队列,p是链表中的一个指针.试基于此结构给出队列的插入(enqueue)和删除(dequeue)算法,并给出p为何值时队列空.
解答：
链式队列的类定义
template class Queue; //链式队列类的前视定义
template class QueueNode { //链式队列结点类定义
friend class Queue;
private:
Type data; //数据域
QueueNode *link; //链域
QueueNode ( Type d = 0, QueueNode *l = NULL ) : data (d), link (l) { } //构造函数
};
template class Queue { //链式队列类定义
public:
Queue ( ) : p ( NULL ) { } //构造函数
~Queue ( ); //析构函数
void EnQueue ( const Type & item ); //将item加入到队列中
Type DeQueue ( ); //删除并返回队头元素
Type GetFront ( ); //查看队头元素的值
void MakeEmpty ( ); //置空队列,实现与~Queue ( ) 相同
int IsEmpty ( ) const { return p == NULL; } //判队列空否
private:
QueueNode *p; //队尾指针(在循环链表中)
};
template Queue::~Queue ( ) { //队列的析构函数
QueueNode *s;
while ( p != NULL ) { s = p; p = p→link; delete s; } //逐个删除队列中的结点
}
//队列的插入函数
template void Queue::EnQueue ( const Type & item ) {
if ( p == NULL ) { //队列空, 新结点成为第一个结点
p = new QueueNode ( item, NULL ); p→link = p;
}
el
se { //队列不空, 新结点链入p之后
QueueNode *s = new QueueNode ( item, NULL );
s→link = p→link; p = p→link = s; //结点p指向新的队尾
}
}
//队列的删除函数
template Type Queue::DeQueue ( ) {
if ( p == NULL ) { cout << "队列空, 不能删除!" << endl; return 0; }
QueueNode *s = p; //队头结点为p后一个结点
p→link = s→link; //重新链接, 将结点s从链中摘下
Type retvalue = s→data; delete s; //保存原队头结点中的值, 释放原队头结点
return retvalue; //返回数据存放地址
}
问题：二叉排序树的删除
解答：
二叉排序树在删除时分三种情况：删除叶子、删除度为1的节点和删除度为2的节点。删除叶子，比较简单，直接删除就可以了。关键删除度为1的节点，要很清楚由其儿子节点代替。一般来说，初学者会认为删除度为2的点较难掌握，其实，只要掌握删除度为1的做法，删除度为2的可以转化为删除度为1的情况。我们在讲义中提到“替身”的概念。用替身替代被删除点，就可以转化为删除度为1的情况了。
问题：哈希的平均查找长度
解答：
查找成功的平均查找长度:
成功地找到某一个 key 所需要的探测次数恰等于将这个 key 插入到散列表中所需要的探测次数。
问题：快速排序算法的程序实现
解答：
教材在实现快速排序时，首先选择一个关键字作为界点（第一个元素、中间位置元素和最后元素选择中间值元素作为界点）,防止出现算法的最坏情况。
程序中，算法的关键在于
while ( arr[++k]
while ( arr[--j]>milestone );//从右开始寻找小于界点的元素
if (k
另外，快速排序算法还有其他的实现方法，比如清华严蔚敏教材的实现方法通常称为填空穴的方法。不同的方法实现的中间结果序列可能不同，但是，时间和空间性能是相同的。
问题：堆排序时间复杂性分析
解答：
分成两个部分，即初始化部分和排序部分。
在初始化的时间部分：
第 i 层上小堆的个数＝第 i 层上结点的个数 ＝ 最多 2i-1
第 i 层上小堆的高度 ＝ h-i+1
建第 i 层上每个小堆最多所需的比较次数 ＝ 2×（h-i）次
（1）∑j/2j< 2
（2）log(n-1)!与nlogn 同数量级有所了解。
问题：Dijktra 算法的时间复杂性的推导
在采用最小化堆挑选最短边的情况下。时间复杂性的级别 O((n+e) logn)正确吗？
解答：
1.建堆代价：O(n)
2.堆中的所有结点，都将会输出。输出一个，堆都会进行调整。代价为： O(nLogn)
3.见 NO. 41 第 7 行
，某个d[i] 的值可能变小，如何进行调整，使堆仍为最小化堆？由此可推出 Dijktra 算法的时间复杂性为：O((n+e)Logn)
4.Prim 算法如用最小化堆实现，问题类似。
5.相关问题：如最小化堆中的结点变大或变小，如何修改，使其仍能为最小化堆。
问题：深度优先判断有向图G中顶点i到顶点j是否有路径
解答：
int visited[MAXSIZE]; //指示顶点是否在当前路径上
int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0
{
if(i==j) return 1; //i就是j
else
{
visited[i]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径
}//for
}//else
}//exist_path_DFS
问题：非递归遍历强连通图G
解答：
分析:本算法的基本思想与二叉树的先序遍历非递归算法相同,由于是强连通图,所以从第一个结点出发一定能够访问到所有结点.
void STraverse_Nonrecursive(Graph G)
{
int visited[MAXSIZE];
InitStack(S);
Push(S,GetVex(S,1)); //将第一个顶点入栈
visit(1);
visited=1;
while(!StackEmpty(S))
{
while(Gettop(S,i)&&i)
{
j=FirstAdjVex(G,i);
if(j&&!visited[j])
{
visit(j);
visited[j]=1;
Push(S,j); //向左走到尽头
}
}//while
if(!StackEmpty(S))
{
Pop(S,j);
Gettop(S,i);
k=NextAdjVex(G,i,j); //向右走一步
if(k&&!visited[k])
{
visit(k);
visited[k]=1;
Push(S,k);
}
}//if
}//while
}//Straverse_Nonrecursive
问题：判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径
解答：
int visited[MAXSIZE];
int exist_path_len(ALGraph G,int i,int j,int k)//
{
if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求
else if(k>0)
{
visited[i]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
l=p->adjvex;
if(!visited[l])
if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一
}//for
visited[i]=0; //本题允许曾经被访问过的结
点出现在另一条路径中
}//else
return 0; //没找到
}//exist_path_len
//队空条件 p == NULL.