1.3 考研真题与典型题详解
一、选择题
1算法的计算量的大小称为计算的（ ）。[北京邮电大学2000研]
A．效率
B．复杂性
C．现实性
D．难度
【答案】B
【解析】算法复杂度通常分为时间复杂度和空间复杂度，算法的计算量的大小可以用时间复杂度衡量，即可以称为计算的复杂度。
2此程序的复杂度为（ ）。[大连理工2008研]
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
A[i][j]=i*j;
A．O（m2）
B．O（n2）
C．O（m×n）
D．O（m＋n）
【答案】C
【解析】时间复杂度是指基本操作重复执行次数的阶数T（n）＝O（f（n））。基本操作为A[i][j]＝i*j，该语句的执行次数与外层的两个循环次数相等，为m×n，因此，算法的复杂度为O（m×n）。
3计算算法的时间复杂度是属于一种（ ）。[北京理工2005研]
A．事前统计的方法
B．事前分析估算的方法
C．事后统计的方法
D．事后分析估算的方法
【答案】B
【解析】度量一个程序的执行时间通常有两种方法：
①事后统计。
②事前分析估计。
算法的时间复杂度是指算法中基本操作重复执行的次数的阶数，因此计算算法的时间复杂度属于事前分析估算的方法。
4以下属于逻辑结构的是（ ）。[西安电子2001研]
A．顺序表
B．哈希表
C．有序表
D．单链表
【答案】C
【解析】顺序表是线性表的顺序存储结构；哈希表是存储结构；单链表是线性表的链式存储结构；有序表是指已经按照某一关键字排好序的线性表，它是逻辑结构。因此，C项正确，而ABD三项都是数据元素在计算机中的存储结构，属于物理结构，而不是题目要求的逻辑结构。
5以下数据结构中，哪一个是线性结构？（ ）[北方交通大学2001研]
A．广义表
B．二叉树
C．稀疏矩阵
D．串
【答案】D
【解析】线性结构：数据元素之间存在一对一的关系，常见的线性结构有：线性表、栈、队列、双队列、数组、串。非线性结构指存在多对一或者一对多的关系，逻辑特征上表现为一个结点可能有多个前驱结点或多个后继结点，常见的非线性结构有：二维数组、多维数组、树、图、广义表等。
广义表（又称列表）是一种非线性的数据结构，是线性表的一种推广。
6下面说法错误的是（ ）。
（1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n下，复杂度O（n）的算法在时间上总是优于复杂度O（2n）的算法
（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
（4）同一个算法，实现语言的级别越高，执行效率就越低
A．（1）
B．（1），（2）
C．（1），（4）
D．（3）
【答案】C
【解析】①一个可执行程序可能涉及中间变量和数组等，需要额外的存储空间，如果这个额外空间相对于问题的规模（输入数据）来说是个常数，称之为原地工作，辅助空间为O（1）。
②对于相同的数据规模，O（n）的效率显然优于O（2n）。
③对于O（1）、O（log2n）、O（n）等，O的形式定义为：若f（n）是正数n的一个函数，则O（f（n））表示存在一个正常数M，使得当n≥n0时满足|O（f（n））|小于等于M×|f（n）|，即O（f（n））给出了函数f（n）的一个上界。
④编译链接后的最终的机器指令操作的次数越少，说明该语言在某种编译链接环境下效率越高，实际上即使同一种语言在不同的编译环境下，也有可能不同。
【注意】在对错判断题中忌“绝对化”，当出现一定，任何等表示绝对性的词语的时候需要慎重对待。
7程序段
FOR i=n-1 DOWNTO 1
DO
FOR j=l TO i
DO
IF A[j]>A[j+1]
THEN A[j]与A[j+1]对换;
其中n为正整数，则最后一行的语句频度在最坏情况下是（ ）。
A．O（n）
B．O（nlogn）
C．O（n3）
D．O（n2）
【答案】D
【解析】这个是冒泡排序，最坏的情况下需要进行1＋2＋…＋n－1次交换，即时间复杂度是O（n2）。
二、填空题
1抽象数据类型的定义仅取决于它的一组______，而与______无关，即不论其内部结构如何变化，只要它的______不变，都不影响其外部使用。[山东大学2001研]
【答案】逻辑特性；在计算机内部如何表示和实现；数学特性
2数据结构是研讨数据的______和______以及它们之间的相互关系，并对与这种结构定义相应的______，设计出相应的______。
【答案】逻辑结构；物理结构；操作（运算）；算法
3在下面的程序段中，对X的赋值语句的频度为______（表示为n的函数）。
FOR i=1 TO n
DO
FOR j=1 TO i
DO
FOR k=1 TO j
DO
x=x+delta;
【答案】1＋（1＋2）＋（1＋2＋3）＋…＋（1＋2＋…＋n）＝n（n＋1）（n＋2）/6，即O（n3）
【解析】当i＝1时，赋值语句就被执行了一次。当i＝2时，赋值语句被执行了1＋2次。当i＝3时，赋值语句被执行了1＋2＋3次。可以推出赋值语句总共被执行了1＋（1＋2）＋（1＋2＋3）＋…＋（1＋2＋…＋n）＝n（n＋1）（n＋2）/6次。
4对于给定的元素，可以构造出的逻辑结构有______，______，______，______四种。
【答案】集合；线性结构；树形结构；图状结构（网状结构）
5已知如下程序段：
FOR i=n DOWNTO 1
DO {语句1}
BEGIN
x=x+1; {语句2}
FOR j=n DOWNTO i
DO {语句3}
Y:=y+1; {语句4}
END；
语句1执行的频度为______；语句2执行的频度为______；语句3执行的频度为______；语句4执行的频度为______。
【答案】n＋1；n；n（n＋3）/2；n（n＋1）/2
【解析】语句1执行到不符合条件情况下，即从i＝n到i＝0，执行了n＋1次；当语句1不符合条件时不会执行语句2，故语句2执行了n次；语句3每次都要执行到不符合条件，故执行次数为2＋3＋4…＋（n＋1）即n（n＋3）/2；同样，当语句3不符合条件时不会执行语句4，故语句4执行了1＋2＋3…＋n次即n（n＋1）/2。
6一个算法具有5个特性：______、______、______、有零个或多个输入、有一个或多个输出。[华中理工大学2000研]
【答案】有穷性；确定性；可行性
7下面程序段中DO循环体执行次数的数量级是______。
i=1;
WHILE i<n
DO i=i+2;
【答案】n/2
8计算机执行下面的语句时，语句s的执行次数为______。[南京理工大学2000研]
for(i=1;i<n-1;i++)
for(j=n;j>=i;j--)
s;
【答案】（n＋3）（n－2）/2
【解析】当i＝1时，s被执行了n次。当i＝n－2时，s被执行了3次。所以s总共被执行了3＋4＋…＋n＝（n＋3）（n－2）/2。
三、综合题
1分析以下程序段中语句④的频度以及该程序段的时间复杂度。
for(i=0;i<n;i++) //①
{
y=y+1; //②
for(j=0;j<=2*n;j++) //③
x++; //④
}
答：语句的频度是指该语句被重复执行的次数。在本题中语句④执行的次数是内外两层循环的次数，即n（2n＋1）＝2n2＋n，因此该语句的频度是2n2＋n。
时间复杂度可以用算法中的基本操作重复执行的次数来度量，本程序段中的语句④即为基本操作，所以该算法的时间复杂度＝2n2＋n＝O（n2）。
2分析以下算法的时间复杂度。
void fun(int n)
{
int i=0;
int s=0;
while(s<n)
{
++i;
s=s+i;
}
}
答：显然n为问题规模，基本操作为语句“++i”和“s=s+i”。变量i与s都从0开始，假设循环执行m次结束，即当循环m次时，m＝n，则有s0＝0，s1＝1，s2＝1＋2＝3，s3＝1＋2＋3＝6，…，sm＝m（m＋1）/2（其中sm为执行到第m次的时候s的值），则有m（m＋1）/2＋K＝n（K为起修正作用的常数），由求根公式得
由此可知时间复杂度为
3举一个数据结构的例子，叙述其逻辑结构、存储结构、运算三个方面的内容。
答：例如有一张学生成绩表，如表1-1所示，记录了一个班的学生各门课的成绩。这个表是一个数据结构。
表1-1 学生成绩表
（1）逻辑结构
每个记录（包括学号，姓名，成绩）是指一个结点，对于整个表来说，只有一个开始结点（其前面无记录）和一个终端结点（其后面无记录），其他的结点则各有一个也只有一个前驱结点和后继结点（即它的前面和后面均有且仅只有一个记录）。
（2）存储结构
若用链式存储方式，结点的数据类型定义如下：
struct node
{
int no; //存放学号的数据域
char name[10]; //存放姓名的数据域
int score; //存放成绩的数据域
struct node* next; //指向下一个结点的指针
}
（3）数据运算
在建表之后就要对这张表中的记录进行查询、修改、删除等操作。
4以下算法的时间复杂度为多少？
void hanoi(int n,char x,char y,char z)
{
if (n==1)
printf("move %c to %c\n",x,z);
else
{
hanoi(n-1,x,z,y);
printf("move%cto%c\n",x,z);
hanoi(n-1,y,x,z);
}
}
答：设函数hanoi（n）的执行时间为T（n），则hanoi（n－1）的执行时间为T（n－1）。
有：
当n＝1时，T（1）＝1；
当n＞1时，T（n）＝2T（n－1）＋1。
所以有：
T（n）＝2T（n－1）＋1＝2（2T（n－2）＋1）＋1＝22T（n－2）＋1＋2＝22（2T（n－3）＋1）＋1＋21＝23T（n－2）＋1＋21＋22＝…＝2n－1T（1）＋1＋21＋22＋…＋2n－2＝2n－1＋2n－1－1＝2n－1＝O（2n）
5假设一个不带头结点的单链表h中所有的结点数据域都为整数，设计一个递归算法求其中的最大值。
答：设单链表h（以h为首结点指针）中最大值为f（h），根据单链表的定义，h->next也是一个单链表，则f（h->next）为以h->next为首结点指针的单链表中的最大值，如图1-7所示。
f（h）求a1…an中最大元素
图1-7 f（h）和f（h->next）的功能
得到以下递归模型：
f(h)＝h->data //若h->next＝NULL或单链表中只有一个结点
f(h)＝MAX(h->data,f(h->next)) //其他情况
其中MAX表示求两个数的最大值。对应的递归算法如下：
int f(LinkList h)
{
int m;
if(h->next==NULL)
return h->data;
else
{
m=f(h->next); //递归调用
if(m>h->data)
return m;
else
return h->data;
}
}