数据结构课后习题答案
第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 while(y>0) for(j=0;j {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和2log n。显然，当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%。 第2章线性表 一、基础知识题 2.1 试述头指针、头结点、元素结点、首元结点的区别，说明头指针和头结点的作 【解答】指向链表第一个结点（或为头结点或为首元结点）的指针称为头指针。“头指针”具有标识一个链表的作用，所以经常用头指针代表链表的名字，如链表L既是指链表的名字是L，也是指链表的第一个结点的地址存储在指针变量L中，头指针为“NULL”则表示指针变量L没指向任何链表。 有时，我们在整个线性链表的第一个元素结点之前加入一个结点，称为头结点，它的数据域可以不存储任何信息（当然，作为“副产品”，头结点的数据域也可能做监视哨或存放线性表的长度等附加信息），指针域中存放的是第一个数据结点的地址，空表时为空。“头结点”的加入，使插入和删除等操作方便、统一。 元素结点即是数据结点，至少包括元素自身信息和其后继元素的地址两个域。 首元结点是指链表中第一个数据元素的结点；为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点。 2.2分析顺序存储结构和链式存储结构的优缺点，说明何时应该利用何种结构。 【解答】①从空间上来看，当线性表的长度变化较大，难以估计其规模时，选用动态的链表作为存储结构比较合适。由于链表除了需要设置数据域外，还要额外设置指针域，因此当线性表长度变化不大，易于事先确定规模时，为了节约存储空间，宜采用顺序存储结构。 ②从时间上看，顺序表具有按元素序号随机访问的特点，在顺序表中按序号访问数据元素的时间复杂度为O(1)；而链表中按序号访问的时间复杂度为O(n)。所以如果经常按序号访问数据元素，使用顺序表优于链表。 在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此n较大时顺序表的插入和删除效率低。在链表中作插入、删除，虽然也要找插入位