北京交通大学计算机专业考研辅导班笔记（数据结构）
2005年北京交通大学计算机专业考研辅导班笔记(05年有好多内容和04年一样，04年有不同我会特别用蓝色注明)
第一章：概论(05年)
1. 设有两个算法在同一机器上运行，其执行时间分别为100*n**2和2**n，要是前者快于后者，n至少要多大?
求不等式 100n**2=15
2. 算法的时间复杂度仅与问题的规模相关吗?
事实上，时间复杂度不仅与问题的规模有关，还与问题的初始状态相关，如起泡排序里时间复杂度就与排序的初始状态有关。
3. 若所需额外空间相对于输入数据量是常数，则称算法为原地工作!(掌握概念)
有可能出这样的题：给你个算法让你判断它是否是原地工作。 如：简单排序，起泡排序等!
总结：第一章考的内容不多，主要是复杂度问题
概论(04年)
强调的内容和05年差不多，但着重讲了算法复杂度的计算。如下：
1. (1)x=0; y=0; 1次
(2) for (k=1;k
(3) x++; n次
(4) for(k=1;k
(5) for(j=1;j
(6) y++ n**2次
2. x=1 1次
for(k=1;k
for(j=1;j
for(k=1; 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为新链表的头指针 (责任编辑：tq2013)
页:
[1]