全部习题.doc

第一章绪论求时间复杂度练习题(1)i←1;j←0whilei+j<=ndoifi>jthenj←j+1elsei←i+1endifendwhile(2)fori←1tondoforj←1tondofork←1tojdox←x+1endforendforendfor(3)fori←1tondoforj←1toidofork←1tojdox←x+1endforendforendfor(4)一个算法的执行时间为1000n,另一个算法约为2^n(2的n次方)。这两个算法的时间复杂度分别是多少?哪个高?当问题的规模n≤13时,选用哪个算法合适?(5)已知有实现同一功能的两个算法,其时间复杂度分别为O(2^n)和O(n^10),假设现实计算机可连续运行的时间约100天,又每秒可执行基本操作为10^5次。试问在此条件下,这两个算法可解决问题的规模(即n的范围)各为多少?哪个算法更合适?试说明理由。(6)给出费氏数列(i数列)前n项的递归与非递归的算法,试分析它们的算法复杂度(注:i数列);试用time或clock函数实际测试n=100时,机器的实际运行时间,并分析结果。第六章线性表习题6-,每个元素的长度为2,则第5个元素的地址是。6-(1≤i≤n+1)之前插入一个元素时,需向后移动的元素个数是。6-,逻辑上相邻的元素在物理位置上。6-,设其长度为n,在任何位置上插入或删除操作都是等概率的。插入一个元素时大约要移动表中的个元素,删除一个元素时大约要移动表中的个元素。6-。6-,且很少进行插入和删除,但要求以最快的速度存取线性表中的元素,那么若采用顺序存储结构是否合适?为什么?6-,链表可分为和;而根据指针的连接方式,链表又可分为和。6-、头结点及开始结点的区别,并说明头指针和头结点的作用。6-?(即从尾指针出发能访问到链表上任何一个结点)6-?6-。(1)head=NULL(2)head→next=NULL(3)head→next=head(4)head!=NULL6-,若指针p所指结点不是最后结点,在p之后插入指针s所指结点,则执行。(1)s→next=p;p→next=s;(2)s→next=p→next;p→next=s;(3)s→next=p→next;p=s;(4)p→next=s;s→next=p;6-。(1)p→next=s;s→prior=p;p→next→prior=s;s→next=p→next;(2)p→next=s;p→next→prior=s;s→prior=p;s→next=p→next;(3)s→prior=p;s→next=p→next;p→next=s;p→next→prior=s;(4)s→prior=p;s→next=p→next;p→next→prior=s;p→next=s;6