1.2 典型题（含历年真题）详解
一、单项选择题
1下列程常段的时间复杂度是（ ）。[2014年联考真题]
A．O（log2n）
B．O（n）
C．O（nlog2n）
D．O（n2）
【答案】C
【解析】外部循环的退出条件是k＞n，而对于k，每次循环都执行k＝k*2，所以循环次数为log2n；内部循环的退出条件是j＞n，对于j，每次循环都执行j＝j＋1，所以每次循环次数为n次。所以此程序段的时间复杂度为O（nlog2n），即选C。
2求整数n（n≥0）阶乘的算法如下，其时间复杂度是（ ）。[2012年联考真题]
A．O（log2n）
B．O（n）
C．O（nlog2n）
D．O（n2）
【答案】B
【解析】设fact（n）的运行时间函数是T（n）。
该函数中语句①的运行时间是O（1），语句②的运行时间是T（n－1）＋O（1），其中O（1）为乘法运算的时间。
因此，当n≤1时，T（n）－O（1）；当n＞1时，T（n）＝T（n－1）＋O（1）。则，T（n）＝O（1）＋T（n－1）＝2×O（1）＋T（n－2）＝（n－1）×O（1）＋T（1）＝n×O（1）＝O（n），即fact（n）的时间复杂度为O（n）。
3设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。[2011年联考真题]
A．O（log2n）
B．O（n）
C．O（nlog2n）
D．O（n2）
【答案】A
【解析】其中，以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是语句x＝2×x，设其执行时间为T（n），则有2T（n）＜n/2即T（n）＜log2（n/2）＝O（log2n）。
4以下属于逻辑结构的是（ ）。
A．顺序表
B．哈希表
C．有序表
D．单链表
【答案】C
【解析】数据结构分别为逻辑结构、存储结构（物理结构）和数据的运算。数据的逻辑结构是对数据之间关系的描述，与数据元素本身的形式、内容、相对位置、所含结点个数都无关。顺序表、哈希表、单链表都涉及到数据的存储结构，有序表是指表中数据有序，是一种逻辑结构，与存储结构无关。
5一个算法应该是（ ）。
A．程序
B．问题求解步骤的描述
C．要满足五个基本要求
D．A和C
【答案】B
【解析】程序不一定满足有穷性，如死循环，操作系统等，而算法必须有穷。算法代表了对问题求解步骤的描述，而程序是算法在计算机上的特定实现。
6下面程序段中，执行S语句的次数为（ ）。
A．n2
B．n2/2
C．n（n＋1）
D．n（n＋1）/2
【答案】D
【解析】i的变化范围是从1到n，对于每个已确定值的i，j的变化范围是从1到i，相当于求一个公差为1的等差数列1，2，…，n的前n项和，即：n（n＋1）/2。
7以下算法的时间复杂度（ ）。
A．O（n）
B．O（n2）
C．O（nlog2n）
D．O（log2n）
【答案】D
【解析】基本运算为i＝i*2，设其执行时间为T（n），则2T（n）＜＝n，即T（n）＜＝log2n＝O（log2n）。
二、综合题
1已知一个整数序列A＝（a0，a1，…，an－1），其中0≤ai＜n（0≤i≤n）,若存在ap1＝ap2＝…＝apm＝x且m＞n/2（0≤pk≤n，1≤k≤m），则称x为A的主元素。例如A＝（0，5，5，3，5，7，5，5），则称5为主元素；又如A＝（0，5，5，3，5，1，5，7）则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出－1。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C＋＋或Java语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度和空间复杂度。[2013年联考真题]
解：（1）算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。然后重新计数,确认Num是否是主元素。
算法可分为以下两步：
①选取候选的主元素
依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到c中，记录Num的出现次数为1；若遇到的下一个整数仍等于Num，则计数加1否则计数减1；当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。
②判断c中元素是否是真正的主元素，再次扫描该数组，统计c中元素出现的次数，若大于n/2，则为主元素；否则，序列中不存在主元素。
（2）算法实现如下：
（3）时间复杂度为O（n），空间复杂度为O（1）。
2阅读下面的程序，指出过程pp完成的功能及结果数据结构的名称，并估计算法的时间复杂度O（？），说明理由。设单链表长度为n。
C语言
答：（1）程序的功能是将单链表逆置；
（2）结果数据结构为存入一个带头结点、用尾指针表示的单向循环链表；
（3）算法时间复杂度为O（n）。理由：因为此程序通过递归方法达到单链表的逆置，递归深度与表的结点数相当，回退时处理插入，每层复杂度为O（1），故总的复杂度为O（n）。