数据结构专业考研辅导

《数据结构专业考研辅导》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、2005年北京交通大学计算机专业考研辅导班笔记（05年有好多内容和04年一样，04年有不同我会特别川蓝色注明）第一章：概论（05年）1.设有两个算法在同一机器上运行，英执行时间分别为100切和2和2**n,要是前者快于后者，n至少要多大？求不等式100n**2v2**n,n>=152.算法的吋间复杂度仅与问题的规模相关吗？事实上，吋间复杂度不仅与问题的规模有关，还与问题的初始状态相关，如起泡排序里时间复杂度就与排序的初始状态有关。3.若所需额外空间相对于输入数据量是常数，则称算法为原地工作！（掌握概念）有可能出这样的题：给你个算法让你判断它是否

2、是原地工作。如：简单排序，起泡排序等！总结：第一章考的内容不多，主要是复杂度问题概论（04年）强调的内容和05年差不多，但着重讲了算法复杂度的汁算。如下：1.(1)x=0;y=0;1次(2)for(k=1;kv=n;k++)n+l次(3)X++；n次(4)for(k=l;k<=n;k++)n+l次(5)for(j=l;j<=n;j++)n(n+l)次(6)y++n**2次2.x=l1次for(k=1;k<=n;k++)n+l次for（j=l;j<=i;j++）E（i+1）（求和卜限i=l,上限n+l）for（k=1;kv==j;k++）x++;

3、EEj（第一个求和下限i二1,上限n；第二个求和下限j=l,上限为i）=E（i+l）/2（求和下限21,上限n）=（n（n+l）（2n+l））/12+（n（n+l））/43.简单选择排序和起泡排序的比较次数第二章：线性表（05年）1.熟悉线性表的逻辑结构及其性质（书上有）2.理解插入，删除，定位这三个算法及过程（顺序表，各种链表应熟悉）3.循环链表的用法（约瑟夫环，猴子选大王（参看04年填程序第二题）向己编一下程序）4.双向循环链表判空（head->next=head或head->pre=head带头结点），判满的条件以及它的插入和删除结点的操

4、作。5.在顺序表中插入或删除一个结点需平均移动多少个结点？具体的移动次数取决于哪两个因素？答：参看书P25取决于顺序表的长度n,和需耍插入和删除的位置i（i越接近n需耍移动的结点越少）5.为什么亦单循环链表屮设尾指针比设头指针好？答：川尾指针可以使得查找链表的开始结点和终端结点都很方便。设一带头结点的单循环链农，其尾指针为rear则开始结点和终端结点的位置分别rear->next->next和rear.査找时间都是0(1).若用头结点表示则査找终端结点的时间是0(n);5.在单链表，双链表和单循环链表中，若只知道指针P指向某结点，不知道头指针，

5、能否将结点*P从中删除？答：单链表不行双链农可以0(1)单循环可以0(n)从p开始往后，总可以找到p前而的一个结点。6.下述算法的功能是什么？LinklistDemo(linklistL){〃L是头结点1istNode*q,*p;if(L&&L-〉next)//保证有两个结点{q=L;L=L->next;p=L;whi1e(p->next)p=p->next;p->next二q;q->next=Null;}returnL;}//该程序是把第一个结点挪到最后，第二个结点变为第一，返冋的L为新链表的头指针答：若L指向的单链表至少有两个结点，将第一个

6、结点移到终端结点Z后成为新的终端结点。而L指向原来的第二个结点，使其成为新的开始结点，并返回新链表的头指针；否则直接返冋L值不作任何变动(老师强调了在做阅读程序的题目吋，一定要把其描写得具体些，这样才能保证多拿分)7.试分别用顺序表和单链表作为存储结构，写程序对其就地逆置，要求辅助空间为0(1).8.顺序衣L是递增(或递减)有序表，将x插入后，使其仍然有序。9.已知L1,L2分别指向两个单链表的头结点，试写一算法将两个链表连接在一起，并分析算法的时间复杂度(min(m,n)短的放前面，把第二个链表的头结点去掉。从短的头结点开始一直找到尾部，并让

7、尾结点指向长链表(last->next=L2->next))10.设A,B两个单-链表，其表中元素递增有序。试写一算法将A,B归并成一个递减的C,要求辅助空间为0(1),并求时间复杂度(参看P21)11.约瑟夫环应用以上题目希望人家能自己动手做做第三章栈和队列(05年)1.栈和队列：受限的线性表。-般的线性表有：插入点n+1个，删除点n个栈，队列：插入点1个，删除点1个2.入栈，出栈，入队，删除队头的操作均应掌握(包括算法)3.掌握循环队列4.例题P48数制转换5.括号匹配知道是怎么冋事就行6.迷宫求解录音里有老师详细讲解(1)读入字符串(2)

8、去空格(3)压入栈(4)依次出栈与原字符串比较若不等则非回文，若直到栈空都相等则为回文。考虑另一种方法：若字符串的长度为奇数，则不需比较为非回文。否则