《厦大数据结构习题及解答》由会员分享，可在线阅读，更多相关《厦大数据结构习题及解答（5页珍藏版）》请在金锄头文库上搜索。
1、11. 数据元素 是数据的基本单位，有些情况下也称为元素、结点、顶点、记录等。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)。2i=1; while(iNext) int x; struct node *p;p=head; while (p-next!=NULL)if (p-ne
3、xt-data=x)3s-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)
4、;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
5、x; struct node *p, *q;if (head-data=x) 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);else p=p-next;412. 已知线性表(al，a2，an)中的元素值按递增有序排列，选用顺序表结构存放，试编 写算法删除线性表中的值介于 c 与 d (c
6、d)之间的元素。13. 设计算法，求带头结点的循环链表的长度，如下图所示。带头结点的循环链表14. 设计算法，在带头结点的单循环链表的第 i 个结点前插入元素值为 x 的结点。15. 设计算法，删除带头结点的单循环链表的第 i 个结点。516. 设计算法，将不带头结点的单链表(a1, a2, ., an)中的元素逆置。算法思想：另建一链表 p（初值为空） ，依次删除原链表头指针 head 所指点结点插入到 p 表表头。17. 循环队列首尾相连的状态是通过 取模 运算来实现的。18. 已知栈的输入序列为 1,2,3,n，输出序列为 a1, a2, , an, 符合 a2=n 的输出序列共有 n-
7、 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无
