数据结构的习题1-3章.doc

《数据结构的习题1-3章.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章绪论1-1简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。1-2设三个函数f,g,h分别为f(n)=100n3+n2+1000,g(n)=25n3+5000n2,h(n)=n1.5+5000nlgn请判断下列关系是否成立：(1)f(n)=O(g(n)) (2)g(n)=O(f(n)) (3)h(n)=O(n1.5)(4)h(n)=O(nlgn)1-3设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。(1)i=1;k=0; 　　while(i

2、n-1∴T(n)=O(n)◇这个函数是按线性阶递增的(2)i=0;k=0;　　do{　　　　k=k+10*i;i++; 　　　}　　while(ij)j++;　　　　elsei++;　　　}◆T(n)=n/2∴T(n)=O(n)◇虽然时间函数是n/2,但其数量级仍是按线性阶递增的。(4)x=n;//n>1 　while(x>=(y+1)*(y+1))　　y++;◆T(n)=n1/2∴T(n)=O(n1/2)◇最坏的情况是y=

3、0，那么循环的次数是n1/2次，这是一个按平方根阶递增的函数。(5)x=91;y=100; while(y>0)　　　　if(x>100)　　　　　{x=x-10;y--;}　　　　elsex++;◆T(n)=O(1)◇这个程序看起来有点吓人，总共循环运行了1000次，但是我们看到n没有?没。这段程序的运行是和n无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数。1-4按增长率由小至大的顺序排列下列各函数：2100,(3/2)n，(2/3)n，nn,n0.5,n!，2n，lgn,nlgn,n(3/2)(2/3)^n<2^100

4、>real>>imag;assign(c1,real,imag);cout<<”生成的复数是：”;print(c

5、1);......;cout<<”c1+c2的结果是：”;print(cplus(c1,c2));cout<0和n0>=0，对一切n>n0均有

6、g(n)

7、<=c

8、f(n)

9、成立，也称函数g(n)以f(n)为界或者称g(n)囿于f(n)。记作g(n)=O(f(n))。定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”。　

10、　我们常用大O表示法表示时间复杂度，注意它是某一个算法的时间复杂度。大O表示只是说有上界，由定义如果f(n)=O(n)，那显然成立f(n)=O(n^2)，它给你一个上界，但并不是上确界，但人们在表示的时候一般都习惯表示前者。此外，一个问题本身也有它的复杂度，如果某个算法的复杂度到达了这个问题复杂度的下界，那就称这样的算法是最佳算法。常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。第二章线性表2-1试描述头指针

11、、头结点、开始结点的区别、并说明头指针和头结点的作用。2-2何时选用顺序表、何时选用链表作为线性表的存储结构为宜?2-3在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?2-5在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?2-6下述算法的功能是什么?LinkListDemo(LinkListL){//L是无头结点单链表 ListNode*Q,*P; if(L&&L->next){   Q=L;L=L->next;P=L;   wh