下载文档原格式
数据结构C语言版期末考试试题(有答案)一、选择题（每题5分，共40分）1. 下列关于数据结构的叙述中，正确的是（）A. 数据结构是研究数据元素的存储结构的学科B. 数据结构是研究数据元素之间逻辑关系的学科C. 数据结构是研究数据元素及其之间关系的学科D. 数据结构是研究数据元素的排序和查找的学科答案：C2. 在线性表中，第一个元素存储在（）A. 随机存储单元B. 数据结构的起始位置C. 数据结构的结束位置D. 数据结构的中间位置答案：B3. 下列哪种排序算法的时间复杂度是O(nlogn)（）A. 冒泡排序B. 选择排序C. 插入排序D. 快速排序答案：D4. 在下列数据结构中，哪一个不是树形结构（）A. 二叉树B. 树C. 图D. 队列答案：D5. 在下列数据结构中，哪一个不是线性结构（）A. 栈B. 队列C. 双向链表D. 图答案：D6. 在顺序表中，元素之间逻辑上的顺序关系是由（）来体现的。
A. 数据元素的物理位置B. 指针C. 引用D. 数组下标答案：A7. 在下列排序算法中，哪一个是不稳定的排序算法（）A. 冒泡排序B. 选择排序C. 插入排序D. 快速排序答案：B8. 在下列查找算法中，哪一个的平均查找长度最小（）A. 顺序查找B. 二分查找C. 二叉树查找D. 哈希查找答案：B二、填空题（每题5分，共30分）9. 一个栈的顺序存储空间为S[1..m]，栈顶指针为top，当栈为空时，top的值为______。
答案：010. 在链表中，每个节点至少包含两个域，即______和______。
答案：数据域；指针域11. 在二叉树中，度为0的节点数n0与度为2的节点数n2之间的关系为______。
答案：n0 = n2 + 112. 在顺序查找算法中，查找失败时，算法的时间复杂度为______。
答案：O(n)13. 在哈希表中，处理冲突的两种主要方法是______和______。
答案：开放地址法；链地址法三、判断题（每题5分，共20分）14. 线性表可以是空表。
数据结构c语言版耿国华课后习题答案数据结构是计算机科学中的一个重要领域，它涉及到数据的组织、管理和存储方式，以便可以高效地访问和修改数据。
C语言作为一种高级编程语言，提供了丰富的数据结构实现方法。
耿国华教授编写的《数据结构C语言版》一书，为学习者提供了深入理解和实践数据结构的机会。
以下是该书课后习题的一些参考答案。
# 第一章绪论1. 习题1：数据结构的定义是什么？- 参考答案：数据结构是计算机科学中用于组织、管理和存储数据的方式，以便可以高效地访问和修改数据。
2. 习题2：为什么需要学习数据结构？- 参考答案：学习数据结构有助于提高编程效率，优化算法性能，以及更好地解决实际问题。
# 第二章线性表1. 习题1：线性表的特点是什么？- 参考答案：线性表的特点是数据元素之间存在一对一的线性关系，可以顺序存储或链式存储。
2. 习题3：如何实现线性表的插入操作？- 参考答案：线性表的插入操作通常涉及找到插入位置，然后将新元素插入到该位置，并调整后续元素。
# 第三章栈和队列1. 习题1：栈的后进先出（LIFO）特性是什么？- 参考答案：栈的后进先出特性意味着最后插入的元素将是第一个被删除的元素。
2. 习题2：如何用C语言实现一个队列？- 参考答案：可以用数组或链表来实现队列。
队列的基本操作包括入队（enqueue）和出队（dequeue）。
# 第四章树和二叉树1. 习题1：二叉树的定义是什么？- 参考答案：二叉树是每个节点最多有两个子节点的树结构，通常分为左子节点和右子节点。
2. 习题3：二叉树的遍历方法有哪些？- 参考答案：二叉树的遍历方法包括前序遍历、中序遍历、后序遍历和层序遍历。
# 第五章图1. 习题1：图的基本概念有哪些？- 参考答案：图由顶点（节点）和边组成，可以表示对象之间的关系。
2. 习题2：图的存储方式有哪些？- 参考答案：图的存储方式主要有邻接矩阵和邻接表两种。
# 结语通过学习《数据结构C语言版》一书，读者可以掌握各种数据结构的基本概念、特性以及实现方法。
数据结构（C语言版）课后习题答案目录第1章绪论 (1)第2章线性表 (5)第3章栈和队列 (13)第4章串、数组和广义表 (26)第5章树和二叉树 (33)第6章图 (43)第7章查找 (54)第8章排序 (65)第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。
如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
在有些情况下，数据元素也称为元素、结点、记录等。
数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。
数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。
例如，学生基本信息表中的学号、姓名、性别等都是数据项。
数据对象：是性质相同的数据元素的集合，是数据的一个子集。
例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’， ‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。
逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
存储结构：数据对象在计算机中的存储表示，也称为物理结构。
抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。
具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。
2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。
![数据结构（C语言版）1800道题及答案[完整版]](https://img.taocdn.com/s1/m/9bcf54fe59f5f61fb7360b4c2e3f5727a5e9240e.png)
数据结构（C语言版）1800道题及答案[完整版]数据结构(C语言版)1800道题及答案[完整版]数据结构1800例题与答案第一章绪论一、选择题（每小题2分）1．算法的计算量的大小称为计算的（B ）。
【北京邮电大学2000 二、3 （20/8分）】A．效率 B．复杂性 C．现实性 D．难度2．算法的时间复杂度取决于（C）。
【中科院计算所 1998 二、1 （2分）】A．问题的规模 B．待处理数据的初态 C．A和B D．都不是3．计算机算法指的是（① C ），它必须具备（② B ）这三个特性。
① A．计算方法B．排序方法C．解决问题的步骤序列 D．调度方法② A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性C．确定性、有穷性、稳定性 D．易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（ B ）。
【中山大学 1998 二、1（2分）】A．程序 B．问题求解步骤的描述C．要满足五个基本特性 D．A和C.5．下面关于算法说法错误的是（ D ）【南京理工大学 2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（C ）【南京理工大学2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（ C ）两大类。
【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（D ）。
目录第1章 绪论............................................................................................................ 1 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。
............................................................................................................ 1 第2章 线性表 ........................................................................................................ 9 第3章 栈和队列 .................................................................................................... 36 第4章 串 . (65)以下是关于广义表算法涉及的描述及方法......................................................... 83 6章 树和二叉树 ..................................................................................................... 86 第7章 图 ............................................................................................................109 第9章 查找 (111)第1章 绪论1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。
数据结构试题及答案c语言版一、选择题（每题2分，共20分）1. 在C语言中，以下哪个选项是正确的链表定义？A. struct Node { int data; struct Node *next; };B. struct Node { int data; Node *next; };C. struct Node { int data; struct Node *next; } *Node;D. struct Node { int data; Node *next; };答案：A2. 下列关于栈的描述中，错误的是？A. 栈是一种后进先出（LIFO）的数据结构。
B. 栈的插入操作称为push。
C. 栈的删除操作称为pop。
D. 栈可以存储任意数量的数据。
答案：D3. 在C语言中，以下哪个关键字用于定义一个结构体？A. structB. unionC. enumD. typedef答案：A4. 下列关于队列的描述中，正确的是？A. 队列是一种先进先出（FIFO）的数据结构。
B. 队列只能从队尾进行插入操作。
C. 队列的插入操作称为pop。
D. 队列的删除操作称为push。
答案：A5. 在C语言中，以下哪个函数用于创建一个动态数组？A. mallocB. callocC. reallocD. all of the above答案：D6. 下列关于二叉树的描述中，错误的是？A. 二叉树的每个节点最多有两个子节点。
B. 二叉树的子节点被称为左子树和右子树。
C. 二叉树的遍历方式包括前序、中序、后序。
D. 二叉树的每个节点只能有一个子节点。
答案：D7. 在C语言中，以下哪个函数用于释放动态分配的内存？A. freeB. mallocC. callocD. realloc答案：A8. 下列关于图的描述中，错误的是？A. 图是由顶点和边组成的数据结构。
B. 图的边可以是有向的，也可以是无向的。
C. 图的顶点可以是孤立的，没有边与之相连。
数据结构（C语言版）（第2版）课后习题答案李冬梅2015.3目录第1章绪论 (1)第2章线性表 (5)第3章栈和队列 (14)第4章串、数组和广义表 (27)第5章树和二叉树 (34)第6章图 (44)第7章查找 (55)第8章排序 (66)第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。
如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
在有些情况下，数据元素也称为元素、结点、记录等。
数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。
数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。
例如，学生基本信息表中的学号、姓名、性别等都是数据项。
数据对象：是性质相同的数据元素的集合，是数据的一个子集。
例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。
逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
存储结构：数据对象在计算机中的存储表示，也称为物理结构。
抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。
具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。
附录习题参考答案习题1参考答案1.1.选择题(1). A. (2). A. (3). A. (4). B.,C. (5). A. (6). A. (7). C. (8). A. (9). B. (10.)A.1.2.填空题(1). 数据关系(2). 逻辑结构物理结构(3). 线性数据结构树型结构图结构(4). 顺序存储链式存储索引存储散列表（Hash）存储(5). 变量的取值范围操作的类别(6). 数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系(7). 关系网状结构树结构(8). 空间复杂度和时间复杂度(9). 空间时间(10). Ο(n)1.3 名词解释如下：数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。
数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。
数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。
数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。
数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。
数据类型：是指变量的取值范围和所能够进行的操作的总和。
算法：是对特定问题求解步骤的一种描述，是指令的有限序列。
1.4 语句的时间复杂度为：(1) Ο(n2)(2) Ο(n2)(3) Ο(n2)(4) Ο(n-1)(5) Ο(n3)1.5 参考程序：main(){int X,Y,Z；scanf(“%d, %d, %d”,&X,&Y,Z)；if (X>=Y)if(X>=Z)if (Y>=Z){ printf(“%d, %d, %d”,X,Y,Z);}else{ printf(“%d, %d, %d”,X,Z,Y);}else{ printf(“%d, %d, %d”,Z,X,Y);}elseif(Z>=X)if (Y>=Z){ printf(“%d, %d, %d”,Y,Z,X);}else{ printf(“%d, %d, %d”,Z,Y,X);}else{ printf(“%d, %d, %d”,Y,X,Z);}}1.6 参考程序：main(){int i,n;float x,a[],p;printf(“\nn=”);scanf(“%f”,&n);printf(“\nx=”);scanf(“%f”,&x);for(i=0;i<=n;i++)scanf(“%f ”,&a[i]);p=a[0];for(i=1;i<=n;i++){ p=p+a[i]*x;x=x*x;}printf(“%f”,p)’}习题2参考答案2.1选择题(1). C. (2). B. (3). B. (4). B. 5. D. 6. B. 7. B. 8. A. 9. A. 10. D.2.2.填空题(1). 有限序列(2). 顺序存储和链式存储(3). Ｏ(n) O(n)(4). n-i+1 n-i(5). 链式(6). 数据指针(7). 前驱后继(8). Ο(1) Ο(n)(9). s->next=p->next; p->next=s ;(10). s->next2.3. 解题思路：将顺序表A中的元素输入数组a，若数组a中元素个数为n,将下标为0，1,2,…,（n-1）/2的元素依次与下标为n,n-1,…, （n-1）/2的元素交换，输出数组a的元素。
一、是非题1. 数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。
.......................( T )2. 线性表的逻辑顺序与物理顺序总是一致的........( F )3. 线性表中的每个结点最多只有一个前驱和一个后继。
......( T )4. 线性的数据结构可以顺序存储，也可以链接存储。
非线性的数据结构只能链接存储。
.......................( F )5. 栈和队列逻辑上都是线性表。
..........................( T )6. 单链表从任何一个结点出发，都能访问到所有结点........( F )7. 单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。
.................................................( T )8. 在用单链表表示的链式队列中，队头在链表的链尾位置。
....( F )9. 多维数组是向量的推广。
..............................( T )10. 栈是一种先进先出的线性表。
....( F )11. 凡是递归定义的数据结构都可以用递归算法来实现它的操作。
......( T )12. 设串S的长度为n,则S的子串个数为n(n+1)/2。
...........( F )13. 一般树和二叉树的结点数目都可以为0。
................( F )14. 按中序遍历二叉树时，某结点的直接后继是它的右子树中第1个被访问的结点。
....( T )15. 后序序列和中序序列能唯一确定一棵二叉树。
....( T )16. 对于一棵具有n个结点，其高度为h的二叉树，进行任—种次序遍历的时间复杂度为O(n) .............( T )17. 网络的最小代价生成树是唯一的。
...( T )18. 图的拓扑有序序列不是唯一的。
数据结构c语言版考试题及答案一、单项选择题（每题2分，共20分）1. 在C语言中，以下哪个选项不是合法的数组声明？A. int a[10];B. int b[2][3];C. int c[];D. int d[0];答案：D2. 链表与数组相比，以下哪个特点是链表独有的？A. 随机访问B. 动态存储分配C. 连续存储D. 固定大小答案：B3. 在C语言中，以下哪个函数用于创建一个单链表节点？A. mallocB. callocC. reallocD. free答案：A4. 栈的后进先出（LIFO）特性是指？A. 最后插入的元素最先被删除B. 最先插入的元素最先被删除C. 最后插入的元素最后被删除D. 最先插入的元素最后被删除答案：A5. 在二叉树中，叶子节点是指？A. 没有子节点的节点B. 只有一个子节点的节点C. 有两个子节点的节点D. 既没有左子节点也没有右子节点的节点答案：A6. 哈希表解决冲突的常用方法不包括？A. 开放寻址法B. 链地址法C. 线性探测法D. 排序法答案：D7. 在图的遍历中，深度优先搜索（DFS）使用的是？A. 栈B. 队列C. 链表D. 数组答案：A8. 快速排序算法的时间复杂度在最好情况下是？A. O(n^2)B. O(n)C. O(nlogn)D. O(logn)答案：C9. 以下哪个不是二叉搜索树的性质？A. 左子树上所有节点的值小于根节点的值B. 右子树上所有节点的值大于根节点的值C. 左子树和右子树都是二叉搜索树D. 所有节点的值都相等答案：D10. 以下哪个算法不是排序算法？A. 冒泡排序B. 选择排序C. 插入排序D. 深度优先搜索答案：D二、填空题（每题2分，共20分）1. 在C语言中，动态分配的内存需要使用________函数来释放。
答案：free2. 一个完全二叉树的第i层（从0开始计数）最多有________个节点。
答案：2^i3. 在图的表示方法中，邻接矩阵适合表示________图，邻接表适合表示________图。
第1章 绪论1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。
解：数据是对客观事物的符号表示。
在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
数据对象是性质相同的数据元素的集合，是数据的一个子集。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
存储结构是数据结构在计算机中的表示。
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。
是对一般数据类型的扩展。
1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。
解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。
一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。
抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。
在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。
1.3 设有数据结构(D,R)，其中{}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r =试按图论中图的画法惯例画出其逻辑结构图。
解：1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。
解：ADT Complex{数据对象：D={r,i|r,i 为实数}数据关系：R={<r,i>}基本操作：InitComplex(&C,re,im) 操作结果：构造一个复数C ，其实部和虚部分别为re 和imDestroyCmoplex(&C) 操作结果：销毁复数CGet(C,k,&e)操作结果：用e 返回复数C 的第k 元的值Put(&C,k,e)操作结果：改变复数C 的第k 元的值为eIsAscending(C)操作结果：如果复数C 的两个元素按升序排列，则返回1，否则返回0IsDescending(C)操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0 Max(C,&e)操作结果：用e返回复数C的两个元素中值较大的一个Min(C,&e)操作结果：用e返回复数C的两个元素中值较小的一个}ADT ComplexADT RationalNumber{数据对象：D={s,m|s,m为自然数，且m不为0}数据关系：R={<s,m>}基本操作：InitRationalNumber(&R,s,m)操作结果：构造一个有理数R，其分子和分母分别为s和mDestroyRationalNumber(&R)操作结果：销毁有理数RGet(R,k,&e)操作结果：用e返回有理数R的第k元的值Put(&R,k,e)操作结果：改变有理数R的第k元的值为eIsAscending(R)操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0 IsDescending(R)操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0 Max(R,&e)操作结果：用e返回有理数R的两个元素中值较大的一个Min(R,&e)操作结果：用e返回有理数R的两个元素中值较小的一个}ADT RationalNumber1.5 试画出与下列程序段等价的框图。
(1) product=1; i=1;while(i<=n){product *= i;i++;}(2) i=0;do {i++;} while((i!=n) && (a[i]!=x));(3) switch {case x<y: z=y-x; break;case x=y: z=abs(x*y); break;default: z=(x-y)/abs(x)*abs(y);}1.6 在程序设计中，常用下列三种不同的出错处理方式：(1) 用exit语句终止执行并报告错误；(2) 以函数的返回值区别正确返回或错误返回；(3) 设置一个整型变量的函数参数以区别正确返回或某种错误返回。
试讨论这三种方法各自的优缺点。
解：(1)exit常用于异常错误处理，它可以强行中断程序的执行，返回操作系统。
(2)以函数的返回值判断正确与否常用于子程序的测试，便于实现程序的局部控制。
(3)用整型函数进行错误处理的优点是可以给出错误类型，便于迅速确定错误。
1.7 在程序设计中，可采用下列三种方法实现输出和输入：(1) 通过scanf和printf语句；(2) 通过函数的参数显式传递；(3) 通过全局变量隐式传递。
试讨论这三种方法的优缺点。
解：(1)用scanf和printf直接进行输入输出的好处是形象、直观，但缺点是需要对其进行格式控制，较为烦琐，如果出现错误，则会引起整个系统的崩溃。
(2)通过函数的参数传递进行输入输出，便于实现信息的隐蔽，减少出错的可能。
(3)通过全局变量的隐式传递进行输入输出最为方便，只需修改变量的值即可，但过多的全局变量使程序的维护较为困难。
1.8 设n为正整数。
试确定下列各程序段中前置以记号@的语句的频度：(1) i=1; k=0;while(i<=n-1){@ k += 10*i;i++;}(2) i=1; k=0;do {@ k += 10*i;i++;} while(i<=n-1);(3) i=1; k=0;while (i<=n-1) {i++;@ k += 10*i;}(4) k=0;for(i=1; i<=n; i++) {for(j=i; j<=n; j++)@ k++;}(5) for(i=1; i<=n; i++) {for(j=1; j<=i; j++) {for(k=1; k<=j; k++)@ x += delta;}(6) i=1; j=0;while(i+j<=n) {@ if(i>j) j++;else i++;}(7) x=n; y=0; // n 是不小于1的常数while(x>=(y+1)*(y+1)) {@ y++;}(8) x=91; y=100;while(y>0) {@ if(x>100) { x -= 10; y--; }else x++;}解：(1) n-1(2) n-1(3) n-1 (4) n+(n-1)+(n-2)+...+1=2)1(+n n (5) 1+(1+2)+(1+2+3)+...+(1+2+3+...+n)=∑=+ni i i 12)1( =∑∑∑∑====+=+=+ni n i n i n i i i i i i i 1121212121)(21)1(21 =)32)(1(121)1(41)12)(1(121++=++++n n n n n n n n (6) n (7) ⎣⎦n 向下取整(8) 11001.9 假设n 为2的乘幂，并且n>2，试求下列算法的时间复杂度及变量count 的值（以n 的函数形式表示）。
int Time(int n) {count = 0; x=2;while(x<n/2) {x *= 2; count++;} return count; }解：)(log 2n o count=2log 2-n1.11 已知有实现同一功能的两个算法，其时间复杂度分别为()n O 2和()10n O ，假设现实计算机可连续运算的时间为710秒（100多天），又每秒可执行基本操作（根据这些操作来估算算法时间复杂度）510次。
试问在此条件下，这两个算法可解问题的规模（即n 值的范围）各为多少？哪个算法更适宜？请说明理由。
解：12102=nn=40 121010=nn=16 则对于同样的循环次数n ，在这个规模下，第二种算法所花费的代价要大得多。
故在这个规模下，第一种算法更适宜。
1.12 设有以下三个函数：()10002124++=n n n f ，()3450015n n n g +=，()n n n n h log 5005.3+= 请判断以下断言正确与否：(1) f(n)是O(g(n))(2) h(n)是O(f(n))(3) g(n)是O(h(n))(4) h(n)是O(n 3.5)(5) h(n)是O(nlogn)解：(1)对 (2)错 (3)错 (4)对 (5)错1.13 试设定若干n 值，比较两函数2n 和n n 2log 50的增长趋势，并确定n 在什么范围内，函数2n 的值大于n n 2log 50的值。
解：2n 的增长趋势快。
但在n 较小的时候，n n 2log 50的值较大。
当n>438时，n n n 22log 50>1.14 判断下列各对函数()n f 和()n g ，当∞→n 时，哪个函数增长更快？(1)()()310!ln 102n n n n f ++=，()724++=n n n g (2) ()()()25!ln +=n n f ，()5.213n n g =(3)()141.2++=n n n f ，()()()n n n g +=2!ln (4) ()()()2223n n n f +=，()()52n n n g n +=解：(1)g(n)快 (2)g(n)快 (3)f(n)快 (4) f(n)快1.15 试用数学归纳法证明：(1) ()()6/12112++=∑=n n n in i ()0≥n(2) ()()1/110--=+=∑x x x n n i i()0,1≥≠n x(3) 12211-=∑=-n n i i ()1≥n (4) ()2112ni n i =-∑=()1≥n 1.16 试写一算法，自大至小依次输出顺序读入的三个整数X ，Y 和Z 的值解：int max3(int x,int y,int z){if(x>y)if(x>z) return x;else return z;elseif(y>z) return y;else return z; }1.17 已知k 阶斐波那契序列的定义为00=f ，01=f ，…，02=-k f ，11=-k f ； k n n n n f f f f ---+++=Λ21，Λ,1,+=k k n试编写求k 阶斐波那契序列的第m 项值的函数算法，k 和m 均以值调用的形式在函数参数表中出现。
