1、1数据结构（C 语言版）（第2 版）习题解析揭安全 李云清 杨庆红江西师范大学计算机信息工程学院联系方式：（习题答案仅供参考）2第1 章 绪论1.1 什么是数据结构？【答】：数据结构是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储于计算机中，并在这些数据上定义了一个运算集合。1.2 数据结构涉及哪几个方面？【答】：数据结构涉及三个方面的内容，即数据的逻辑结构、数据的存储结构和数据的运算集合。1.3 两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有一个运算的定义不一样，它们是否可以认作是同一个数据结构？为什么？【答】：不能，运算集合是数据结构的重要组成部分，不同的
2、运算集合所确定的数据结构是不一样的，例如，栈与队列它们的逻辑结构与存储结构可以相同，但由于它们的运算集合不一样，所以它们是两种不同的数据结构。1.4 线性结构的特点是什么？非线性结构的特点是什么？【答】：线性结构元素之间的关系是一对一的，在线性结构中只有一个开始结点和一个终端结点，其他的每一个结点有且仅有一个前驱和一个后继结点。而非线性结构则没有这个特点，元素之间的关系可以是一对多的或多对多的。1.5 数据结构的存储方式有哪几种？【答】：数据结构的存储方式有顺序存储、链式存储、散列存储和索引存储等四种方式。1.6 算法有哪些特点？它和程序的主要区别是什么？【答】：算法具有（1）有穷性（2）确定
3、性（3 ）0 个或多个输入（4 ）1 个或多个输出（5）可行性等特征。程序是算法的一种描述方式，通过程序可以在计算机上实现算法。1.7 抽象数据类型的是什么？它有什么特点？【答】：抽象数据类型是数据类型的进一步抽象，是大家熟知的基本数据类型的延伸和发展。抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型。抽象数据类型的设计者根据这些描述给出操作的具体实现，抽象数
4、据类型的使用者依据这些描述使用抽象数据类型。1.8 算法的时间复杂度指的是什么？如何表示？【答】：算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个算法在不同的机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法在同一台计算机上执行的时间也不一样，另外，算法执行的时间还与输入数据的状态有关，所以对于算法的时间复杂性，采用算法执行过程中其基本操作的执行次数，称为计算量来度量。算法中基本操作的执行次数一般是与问题规模有关的，对于结点个数为n 的数据处理问题，用T(n)表示算法基本操作的执行次数。为了评价算法的执行效率，通常采用大写O 符号表示算法的时间复杂度
5、，大写O 符号给出了函数 f 的一个上限。其它义如下：3定义：f (n)=O (g (n) 当且仅当存在正的常数c 和n0，使得对于所有的nn0，有f (n) c g(n)。上述定义表明，函数f 顶多是函数 g 的c 倍，除非n 小于n 0。因此对于足够大的n (如nn 0)，g 是f 的一个上限（不考虑常数因子c）。在为函数f 提供一个上限函数g 时，通常使用比较简单的函数形式。比较典型的形式是含有n 的单个项（带一个常数系数）。表1-1 列出了一些常用的g 函数及其名称。对于表1-1 中的对数函数logn ，没有给出对数基，原因是对于任何大于1 的常数a 和b 都有loga n =logb
6、n/logba,所以logan 和logbn 都有一个相对的乘法系数1/logba，其中a 是一个常量。表1-1 常用的渐进函数1.9 算法的空间复杂度指的是什么？如何表示？【答】：算法的空间复杂度是指算法在执行过程中占用的额外的辅助空间的个数。可以将它表示为问题规模的函数，并通过大写O 符号表示空间复杂度。1.10 对于下面的程序段，分析带下划线的语句的执行次数，并给出它们的时间复杂度T(n)。（1） i+;（2） for(i=0;iaj+1) k=j;t=ak; ak=ai; ai=t;（5）for(i=0;i#define N 100 /*预定义最大的数据域空间*/typedef int
7、 datatype; /*假设数据类型为整型*/typedef struct datatype dataN; /*此处假设数据元素只包含一个整型的关键字域*/int length; /*线性表长度*/ seqlist; /*预定义的顺序表类型*/算法countx（L,x）用于求顺序表L 中值为x 的结点的个数。int countx(seqlist *L,datatype x) int c=0;int i;for (i=0;ilength;i+)if (L-datai=x) c+;return c;2.4 设计一个算法，将一个顺序表倒置。即，如果顺序表各个结点值存储在一维数组a 中，倒置的结果是
8、使得数组a 中的a0等于原来的最后一个元素，a1 等于原来的倒数第2 个元素，a 的最后一个元素等于原来的第一个元素。【答】：顺序表的存储结构定义同题2.3，实现顺序表倒置的算法程序如下：void verge(seqlist *L)int t,i,j;i=0;j=L-length-1;while (idatai;L-datai+=L-dataj;L-dataj-=t;2.5 已知一个顺序表中的各结点值是从小到大有序的，设计一个算法，插入一个值为x 的结点，使顺序表中的结点仍然是从小到大有序。【答】：顺序表的定义同题2.3，实现本题要求的算法程序如下：6void insertx(seqlist
9、*L,datatype x)int j;if (L-lengthlength-1;while (j=0 j-;L-dataj+1=x;L-length+;2.6 将下列中缀表达式转换为等价的后缀表达式。(1) 5+6*7(2) (5-6)/7(3) 5-6*7*8(4) 5*7-8(5) 5*(7-6)+8/9(6) 7*(5-6*8)-9【答】：(7) 5+6*7 后缀表达式：5 6 7*+(8) (5-6)/7 后缀表达式： 5 6-7/(9) 5-6*7*8 后缀表达式：5 6 7*8*-(10) 5*7-8 后缀表达式：5 7* 8-(11) 5*(7-6)+8/9 后缀表达式：5 7
10、 6-*8 9/+(12) 7*(5-6*8)-9 后缀表达式：7 5 6 8*-*9-2.7 循环队列存储在一个数组中，数组大小为 n，队首指针和队尾指针分别为front 和rear，请写出求循环队列中当前结点个数的表达式。【答】：循环队列中当前结点个数的计算公式是：(n+rear-front)%n2.8 编号为1,2,3,4 的四列火车通过一个栈式的列车调度站，可能得到的调度结果有哪些？如果有n 列火车通过调度站，请设计一个算法，输出所有可能的调度结果。【答】：解题思路：栈具有先进后出、后进先出的特点，因此，任何一个调度结果应该是1，2，3，4全排列中的一个元素。由于进栈的顺序是由小到大的
11、，所以出栈序列应该满足以下条件：对于序列中的任何一个数其后面所有比它小的数应该是倒序的，例如4321 是一个有效的出栈序列，1423 不是一个有效的出栈结果（4 后面比它小的两个数2，3 不是倒序）。据此，本题可以通过算法产生n 个数的全排列，然后将满足出栈规则的序列输出。产生n 个数的全排列有递归与非递归两种实现算法。产生全排列的递归算法：7设R=r1,r2 ,rn是要进行排列的n 个元素，R i=R-ri。集合X 中元素的全排列记为perm(X)。(ri)perm(X) 表示在全排列perm(X)的每一个排列前加上前缀ri 得到的排列。R 的全排列可归纳定义如下：当n=1 时，perm(R
12、)=(r)，其中r 是集合R 中惟一的元素；当n1 时，perm(R) 由(r1)perm(R1),(r2)perm(R2 ),(rn)perm(Rn)构成。依此递归定义，可设计产生perm(R)的递归算法如下：递归解法：(2_8_1.c)#includeint cont=1; /*全局变量，用于记录所有可能的出栈序列个数*/void print(int str,int n);/*求整数序列str从k 到n 的全排列*/void perm(int str,int k,int n)int i,temp;if (k=n-1) print(str,n);else for (i=k;istrj) if (m=0) bm+=strj;else if (strjb0) flag=0;else b0=strj;if(flag) /*满足出栈规则则输出str中的序列*/ printf(“ %2d:“,cont+);
