《厦大数据结构习题及解答.doc》由会员分享，可在线阅读，更多相关《厦大数据结构习题及解答.doc（5页珍藏版）》请在三一文库上搜索。
1、1. 数据元素 是数据的基本单位，有些情况下也称为元素、结点、顶点、记录等。2 何谓算法?它与程序有何区别?算法是解决某一特定类型问题的有限运算序列。程序数据结构算法3. 算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机 运行时间 的长短和 占据空间 的大小。4. 何谓频度、时间复杂度、空间复杂度？说明其含义。算法中语句的重复次数称为该语句的频度。时间复杂度是算法执行所需要的时间，也就是算法中每一个语句的执行次数乘以每一次执行所需的时间的总和。空间复杂度是算法对空间占用的量度。（一般在考虑空间复杂度时，只估算算法所需增添的辅助空间，而对问题中原始数据所占的空间，由于与算法无关，不予
2、考虑。）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、=3,s=1+2+3,s就是对等差数列求和，因此s=i(i+1)/2Next) & (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
4、=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-ne
5、xt=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(he
6、ad,x)struct node *head;int x; struct node *p, *q; if (head-data=x)&(head-next=NULL) /* 在仅有一个结点的表中删第一个结点 */ free(head); return(NULL); if(head-data=x) /* 在不只一个结点的表中删第一个结点 */ q=head-next; free(head); return(q); p=head; while (p-next!=NULL) if (p-next-data=x)q=p-next; p-next=q-next; free(q); return(head
7、); else p=p-next;12. 已知线性表(al，a2，an)中的元素值按递增有序排列，选用顺序表结构存放，试编写算法删除线性表中的值介于c与d (cd)之间的元素。13. 设计算法，求带头结点的循环链表的长度，如下图所示。带头结点的循环链表14. 设计算法，在带头结点的单循环链表的第i个结点前插入元素值为x的结点。15. 设计算法，删除带头结点的单循环链表的第i个结点。16. 设计算法，将不带头结点的单链表(a1, a2, ., an)中的元素逆置。算法思想：另建一链表p（初值为空），依次删除原链表头指针head所指点结点插入到p表表头。17. 循环队列首尾相连的状态是通过 取模
8、运算来实现的。18. 已知栈的输入序列为1,2,3,n，输出序列为a1, a2, , an, 符合a2=n的输出序列共有 n-1 种。a1可能是1，2，n-1，每个a1对应一个输出序列，故共有n-1种输出序列。19. 已知循环队列用数组data1n存储元素值（没有data0），用f,r分别作为头尾指针，则当前元素个数为 (n+r-f)mod n 。考虑rf和rf两种情形。20. 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（ ）结构。A.栈 B.队 C.数组 D.线性表（B）21. 总结各种栈、队（顺序栈、链栈、循环队、链队）的判空、判满条件。判空判满顺序栈top=-1top=m-1链栈top=NULL无循环队front=rear(rear+1)%m=front链队（带头结点）front=rear无5