北京交通大学计算机专业考研辅导班笔记
        （有不同我会特别用蓝色注明）
第一章：概论（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.    为什么在单循环链表中设尾指针比设头指针好？
答：用尾指针可以使得查找链表的开始结点和终端结点都很方便。设一带头结点的
 

1.下载地址 120.50 KB (需下载币0个)