2005年北京交通大学计算机专业考研辅导班笔记
        （05年有好多内容和04年一样，04年有不同我会特别用蓝色注明）
第一章：概论（05年）
1. 设有两个算法在同一机器上运行，其执行时间分别为100*n**2和2**n，要是前者快于后者，n至少要多大？
        求不等式 100n**2<2**n,  n>=15
2. 算法的时间复杂度仅与问题的规模相关吗？
事实上，时间复杂度不仅与问题的规模有关，还与问题的初始状态相关，如起泡排序里时间复杂度就与排序的初始状态有关。
3. 若所需额外空间相对于输入数据量是常数，则称算法为原地工作！（掌握概念）
有可能出这样的题：给你个算法让你判断它是否是原地工作。 如：简单排序，起泡排序等！
   总结：第一章考的内容不多，主要是复杂度问题
概论（04年）
   强调的内容和05年差不多，但着重讲了算法复杂度的计算。如下：
1. （1）x=0; y=0;  1次
(2)  for (k=1;k<=n;k++)   n+1次
(3)  x++;                n次
(4) for(k=1;k<=n;k++)  n+1次
(5)  for(j=1;j<=n; j++)  n(n+1)次
(6)    y++            n**2次
   2.  x=1                    1次
for(k=1;k<=n;k++)        n+1 次
  for(j=1;j<=i; j++)     ∑(i+1) (求和下限i=1,上限n+1)
    for(k=1; k<==j;k++)
      x++;            ∑∑j(第一个求和下限i=1,上限n；第二个求和下限j=1,上限为i )
                    =∑(i+1)/2 (求和下限i=1,上限 n)
                    =(n(n+1)(2n+1))/12+(n(n+1))/4
3.简单选择排序和起泡排序的比较次数
第二章： 线性表（05年）
1. 熟悉线性表的逻辑结构及其性质（书上有）
2. 理解插入，删除，定位这三个算法及过程（顺序表，各种链表应熟悉）
3. 循环链表的用法（约瑟夫环，猴子选大王（参看04年填程序第二题）自己编一下程序）
4. 双向循环链表判空（head->next=head或 head->pre=head 带头结点），判满的条件
以及它的插入和删除结点的操作。
   5．在顺序表中插入或删除一个结点需平均移动多少个结点？具体的移动次数取决于哪两个因素？
      答：参看书P25
          取决于顺序表的长度n，和需要插入和删除的位置i (i越接近n需要移动的结点越少)
5. 为什么在单循环链表中设尾指针比设头指针好？
答：用尾指针可以使得查找链表的开始结点和终端结点都很方便。设一带头结点的单循环链表，其尾指针为 rear 则开始结点和终端结点的位置分别rear->next->next 和 rear.查找时间都是O(1). 若用头结点表示则查找终端结点的时间是O(n);
6. 在单链表，双链表和单循环链表中，若只知道指针p指向某结点，不知道头指针，能否将结点*p从中删除？
答： 单链表      不行
双链表      可以 O(1)
单循环      可以O(n) 从p开始往后，总可以找到p前面的一个结点。
7. 下述算法的功能是什么？
Linklist Demo(linklist L)
 {  //L是头结点
   listNode  *q, *p;
   if (L&&L->next)  //保证有两个结点
{ q=L; L=L->next; p=L;
  while (p->next) p=p->next;
  p->next=q; q->next=Null;
}   return L;
}//该程序是把第一个结点挪到最后，第二个结点变为第一，返回的L为新链表的头指针
答：若L指向的单链表至少有两个结点，将第一个结点移到终端结点之后成为新的终端结点。而L指向原来的第二个结点，使其成为新的开始结点，并返回新链表的头指针；否则直接返回L值不作任何变动
   （老师强调了在做阅读程序的题目时，一定要把其描写得具体些，这样才能保证多拿分）
8. 试分别用顺序表和单链表作为存储结构，写程序对其就地逆置，要求辅助空间为O(1).
9. 顺序表L是递增（或递减）有序表，将x插入后，使其仍然有序。
10. 已知L1,L2分别指向两个单链表的头结点，试写一算法将两个链表连接在一起，并分析算法的时间复杂度（min(m,n)短的放前面， 把第二个链表的头结点去掉。从短的头结点开始一直找到尾部，并让尾结点指向长链表（last->next=L2->next））
11. 设 A,B两个单链表，其表中元素递增有序。试写一算法将A,B归并成一个递减的C，要求辅助空间为O(1),并求时间复杂度 （参看P21）
12. 约瑟夫环应用
   以上题目希望大家能自己动手做做
第三章 栈和队列(05年)
1. 栈和队列：受限的线性表。
一般的线性表有： 插入点n+1个，删除点n个
栈，队列：       插入点1个，  删除点1个
2. 入栈，出栈，入队，删除队头的操作均应掌握（包括算法）
3. 掌握循环队列
4. 例题 P48 数制转换
5. 括号匹配  知道是怎么回事就行
6. 迷宫求解  录音里有老师详细讲解
7. 回文游戏  顺读与逆读字符串一样（不含空格）
（1） 读入字符串  （2）去空格  （3） 压入栈  （4）依次出栈与原字符串比较
 若不等则非回文，若直到栈空都相等则为回文。
      考虑另一种方法：若字符串的长度为奇数，则不需比较为非回文。否则可先读入一半字符入栈，然后依次出栈和剩下的字符比较！自己可用这种方法编写一下。
8. 地图四染色问题（未考过）
使地图中相邻的不重色，最少用4种颜色可以实现。利用栈回溯。
设一个邻接矩阵R[][]，主对角线上的元素均为零。其于元素如R1,3, 如果第一个区域和第三个区域相邻的话则R1,3为1，否则为0。再使用一个工作数组S[]用来存放已填色区域的号码。
Void  mapcolor (int R[][], int n, int S[])  // n表示地图共有n个区
  { S[1]=1;  //1 号区填1号色
a=2;j=1;  //a为区号，j为色号
while (a<=n)  //a>n表示填色完成
  { while ((j<=4)&&(a<=n))
        { k=1;     //k表示已填色的区域
          while ((k<a)&&(s[k]*R[a-1][k-1]!=j))  k=k+1;
            //若不邻，或相邻且不重色，对下一个区进行判断
           if (k<a) j=j+1;  //相邻且重色，色号加1
           else { s[a]=j; a=a+1; j=1;} //相邻不重色，又从1号区着色
        }
     if (j>4) { a=a-1; j=s[a]+1;} //对当前需着色区域a 来说，1-4种颜色都不行，则说明上一个错了，对上一个进行重填
         }
9. 四皇后问题
#include<stdio.h>
#define  n  4   // n是皇后的个数
int m=0, a[n]; //a[i]存放第i 个皇后放置的行号 
int ok(int i, int j)   //检查(i,j)能否放棋子
 { int j1, i1,ok1;
   j1=j; i1=i; ok1=1;
   while ((j1>1)&&ok1)  {j1--;  ok1=a[j1]!i;} //查左边那列该行是否有皇后
   j1=j; i1=i;  //检查对角线上能否放
   while((j1>1)&&(i1>1)&&ok1)   {j1--;  i1--; ok1=a[j1]!i1 ;}
   j1=j; i1=i; //检查另一对角线能否放
          while ((j1>1)&&(i1<n)&&ok1)   {j1--;  i1++; ok1=a[j1]!i1 ;}
          return  ok1;
         }
        void  queen(int j) //从第j列开始试探
          {  int i;
if (j>n) //放完了，打印摆法计数
  { m++;  printf(“m=%d   “, m);