参考书中的解答是:基本操作是语句i=i*2,设其频度为T(n),则有:2的T(n)次方<=n,即T(n)<=log2n=O(log2n)(2太大了,我打不出来,它是底数) 我的疑问是:红线部分看不懂,为什么是这个式子呢?怎么理解? 解答：设循环体语句i=i*2频度为m，则2的m次方<=n（因为循环条件i<=n），循环体中i的值不就是2的m次方嘛，两边取对数得：m<=log2n，这里m不就是我们要求的T(n)吗？
第二章:
1.设有两个长度为n的单链表,结点类型相同.若以h1为表头指针的链表是非循环的,以h2为表头指针的链表是循环的,则______.
A.对于两个链表来说,删除第一个结点的操作,其时间复杂度都是O(1) B.对于两个链表来说,删除最后一个结点的操作,其时间复杂度都是O(n)
答案选的是B.我个人认为A也对.因为表头指针指的是头结点,而头结点指的是第一个元素的指针,时间复杂度是O(1). 解答：因为题目没有说单链表带头节点呀，不带头节点时删除h2的第一节点，就要修改最后一个节点的next指针，以便保持循环单链表呀，这时不就是O(n)了吗？
2.在长度为n的___上,删除第一个元素,其算法的时间复杂度为O(n). A.只有表头指针的不带表头结点的循环单链表. B.只有表尾指针的不带表头结点的循环单链表. C.只有表尾指针的带表头结点的循环单链表. D.只有表头指针的不带表头结点的循环单链表. 答案选的是A.我不大理解.
解答：这个问题与前者完全相同（略）。
第三章
1.赵老师,循环队列的尾指针是指向队列中的最后一个元素的位置还是指向最后一个元素的下一个位置呢?我做题的时候发现好像两种情况都 出现过,我们考试中应该用哪种情况?
解答：尾指针应该指向最后一个元素的下一个位置！而且尾指针位置必须是空项。
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库本科考试常见题型（复习提纲）(4)在线全文阅读。
相关推荐：