第1章 绪论
一、基础知识题
1.1 简述下列概念
数据，数据元素，数据类型，数据结构，逻辑结构，存储结构，算法。 【解答】数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。
数据元素是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。
数据类型是对数据的取值范围、数据元素之间的结构以及允许施加操作的一种总体描述。每一种计算机程序设计语言都定义有自己的数据类型。
“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作（运算）。而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。
数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则依赖于存储结构。
数据结构在计算机中的表示称为物理结构，又称存储结构。是逻辑结构在存储器中的映像，包括数据元素的表示和关系的表示。逻辑结构与计算机无关。
算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。一个算法应该具有下列特性：有穷性、确定性、可行性、输入和输出。
1.2 数据的逻辑结构分哪几种，为什么说逻辑结构是数据组织的主要方面？ 【解答】数据的逻辑结构分为线性结构和非线性结构。（也可以分为集合、线性结构、树形结构和图形即网状结构）。
逻辑结构是数据组织的某种“本质性”的东西： （1）逻辑结构与数据元素本身的形式、内容无关。 （2）逻辑结构与数据元素的相对位置无关。 （3）逻辑结构与所含数据元素的个数无关。
1.3 试举一个数据结构的例子，叙述其逻辑结构、存储结构、运算三方面的内容。
【解答】学生成绩表，逻辑结构是线性结构，可以顺序存储（也可以链式存储），运算可以有插入、删除、查询，等等。
1.4 简述算法的五个特性，对算法设计的要求。
【解答】算法的五个特性是：有穷性、确定性、可行性、零至多个输入和一至多个输出。
对算法设计的要求：正确性，易读性，健壮性，和高的时空间效率（运算速
度快，存储空间小）。
1.5 设n是正整数，求下列程序段中带@记号的语句的执行次数。
(1)i=1;k=0; (2) i=1;j=0;
while(i {k=k+50*i; i++; @ {if(i>j)j++; @ } else i++; } @ (3)x=y=0; (4)x=91;y=100; for(i=0;i {x++; @ {x=x-10; y--; @ for(k=0;k y++; @ else x++; @ } 【解答】(1)n-1 (2)i= ?n/2? ，j=?n/2? (3)n+1, n(n+1), n2,(n+1)n2, n3 (4)100, 1000 1.6 有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为Tl=O(2n)，A2的时间复杂度为T2=O(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。 【解答】对算法A1和A2的时间复杂度T1和T2取对数，得nlog2和2logn。显然，当n<4时，算法A1好于A2；当n=4时，两个算法时间复杂度相同；当n>4时，算法A2好于A1。 1.7 选择题：算法分析的目的是（ ） A、找出数据结构的合理性 B、研究算法中的输入和输出的关系 C、分析算法的效率以求改进 D、分析算法的易懂性和文档特点 【解答】C 二、算法设计题 1.8 已知输入x，y，z三个不相等的整数，设计一个“高效”算法，使得这三个数按从小到大输出。“高效”的含义是用最少的元素比较次数、元素移动次数和输出次数。 【算法1.8】 void Best() {//按序输出三个整数的优化算法 int a,b,c,t; scanf(“%d%d%d”,&a,&b,&c); if(a>b) {t=a; a=b; b=t:} //a和b已正序 if(b>c) {t=c; c=b; //c已到位 if(a>t) {b=a; a=t;} //a和b已正序 else b=t; } printf(“%d,%d,%d\\n”,a,b,c); //最佳2次比较，无移动；最差3次比较，7个赋值 } 1.9 在数组A[n]中查找值为k的元素，若找到则输出其位置i(1≤i≤n)，否则输出0作为标志。设计算法求解此问题，并分析在最坏情况下的时间复杂度。 【题目分析】从后向前查找，若找到与k值相同的元素则返回其位置，否则返回0。 【算法1.9】 int Search(ElemType A[n+1], ElemType k) {i=n; while(i>=1)&&(A[i]!=k)) i--; if(i>=1) return i; else return 0; } 当查找不成功时，总的比较次数为n+1次，所以最坏情况下时间复杂度为O(n)。 在学过第 9 章 “查找”后，可优化以上算法:设“监视哨”。算法如下： int Search(ElemType A[n+1], ElemType k) {i=n; A[0]=k; while(A[i]!=k) i--; return i; } 研究表明，当n>=1000时，算法效率提高50%。