厦大数据结构习题及解答.doc

PAGE  PAGE 5 1. 数据元素 是数据的基本单位，有些情况下也称为元素、结点、顶点、记录等。 2 何谓算法?它与程序有何区别? 算法是解决某一特定类型问题的有限运算序列。程序＝数据结构＋算法 3. 算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机 运行时间 的长短和 占据空间 的大小。 4. 何谓频度、时间复杂度、空间复杂度？说明其含义。 算法中语句的重复次数称为该语句的频度。 时间复杂度是算法执行所需要的时间，也就是算法中每一个语句的执行次数乘以每一次执行所需的时间的总和。 空间复杂度是算法对空间占用的量度。（一般在考虑空间复杂度时，只估算算法所需增添的辅助空间，而对问题中原始数据所占的空间，由于与算法无关，不予考虑。） 5. 时间复杂度的计算： 语句2的频度为n-l，语句4的额度为(n-1)(2n+1)＝2n2-n-l，因此时间复杂度T(n)＝O(n2)。 语句3的频度为n，语句7的频度为n2，因此时间复杂度为T(n)＝O(n2)。 【解】语句3的频度不仅与n有关，而且和x及数组A中各分量的值有关。这时通常考虑最坏的情况，由于while循环的最大次数为n-1，因此时间复杂度为T(n)＝O(n)。 i=1; while(i=n) i=i*5; 【解】设语句“i=i*5;”的频度为x，则5x=n，x=log5n，O(log5n) i=0;s=0; while(sn) {i++; s+=i;} 【解】i=1,s=1 i=2,s=1+2 i=3,s=1+2+3, s就是对等差数列求和，因此s=i(i+1)/2n，其中i就是循环语句的频度，因此O() 6. 在一个具有n个结点的有序单链表中插入一个新结点，使得链表仍然有序，该算法的时间复杂度是( ) A.O(log2n) B.O(1) C.O(n2) D.O(n) (D) 7. 如果某线性表中最常用的操作是取第i个结点及其前驱，则采用（ ）存储方式最节省时间。 A.单链表 B.双向链表 C.单循环链表 D.顺序表 （D） 8. 写出带头结点的双向循环链表L为空表的条件（假设结点包括data, next, prior三个域）： (L==L-Next) (L==L-Prior) 注：L-Next==L-Prior不行，因为表长为1时该条件也成立。 9. 判断对错：顺序存储的线性表不可以随机存取。 （ * ） 10. 判断对错：线性表的长度是线性表所占用的存储空间的大小。 （ * ） 11. 写出带头结点的单链表和不带头结点的单链表的插入、删除算法，并比较。 /* 带头结点的插入算法。将s结点插入到数据域为x的结点之前。假设链表中存在该结点。 */ void ins(head,s,x) struct node *head, *s; int x; { struct node *p; p=head; while (p-next!=NULL) if (p-next-data==x) {s-next=p-next; p-next=s; return;} else p=p-next; } /* 不带头结点的插入算法。返回插入后的链表的头指针 */ struct node *ins(head,s,x) struct node *head, *s; int x; { struct node *p; if (head-data==x) /* 插在第一个结点之前 */ { s-next=head; return(s);} p=head; while (p-next!=NULL) if (p-next-data==x) {s-next=p-next; p-next=s; return(head);} else p=p-next; } /* 带头结点的删除算法。删除数据域为x的结点。假设链表中存在该结点。 */ void del(head,x) struct node *head; int x; { struct node *p, *q; p=head; while (p-next!=NULL) if (p-next-data==x) {q=p-next; p-next=q-next; free(q); return;} else p=p-next; } /* 不带头结点的删除算法。返回删除后的链表的头指针。 */ struct node *del(head,x) struct node *head; int x