十二五普通高等教育国家级本科规划教材第 1 章绪论高等学校精品资源共享课程1.1 什么是数据结构？【答】：数据结构是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储于计算机中，并在这些数据上定义了一个运算集合。1.2 数据结构涉及哪几个方面？【答】：数据结构涉及三个方面的内容，即数据的逻辑结构、数据的存储结构和数据的运算集合。1.3 两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有一个运算的定义不一样，它们是否可以认作是同一个数据结构？为什么？【答】：不能，运算集合是数据结构的重要组成部分，不同的运算集合所确定的数据结构是不一样的，例如，栈与队列它们的逻辑结构与存储结构可以相同，但由于它们的运算集合不一样，所以它们是两种不同的数据结构。1.4 线性结构的特点是什么？非线性结构的特点是什么？【答】：线性结构元素之间的关系是一对一的，在线性结构中只有一个开始结点和一个终端结点，其他的每一个结点有且仅有一个前驱和一个后继结点。而非线性结构则没有这个特点，元素之间的关系可以是一对多的或多对多的。1.5 数据结构的存储方式有哪几种？【答】：数据结构的存储方式有顺序存储、链式存储、散列存储和索引存储等四种方式。1.6 算法有哪些特点？它和程序的主要区别是什么？【答】：算法具有（1）有穷性（2）确定性（3）0 个或多个输入（4）1 个或多个输出（5）可行性等特征。程序是算法的一种描述方式，通过程序可以在计算机上实现算法。1.7 抽象数据类型的是什么？它有什么特点？【答】：抽象数据类型是数据类型的进一步抽象，是大家熟知的基本数据类型的延伸和发展。抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型。抽象数据类型的设计者根据这些描述给出操作的具体实现，抽象数据类型的使用者依据这些描述使用抽象数据类型。1.8 算法的时间复杂度指的是什么？如何表示？【答】：算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个算法在不同的机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法在同一台计算机上执行的时间也不一样，另外，算法执行的时间还与输入数据的状态有关，所以对于算法的时间复杂性，采用算法执行过程中其基本操作的执行次数，称为计算量来度量。算法中基本操作的执行次数一般是与问题规模有关的，对于结点个数为 n 的数据处理问题，用T(n)表示算法基本操作的执行次数。为了评价算法的执行效率，通常采用大写 O 符号表示算法的时间复杂度，大写 O 符号给出了函数 f 的一个上限。其它义如下：3十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程定义：f (n)=O (g (n) 当且仅当存在正的常数 c 和 n0，使得对于所有的 nn0，有 f (n) c g(n)。上述定义表明，函数 f 顶多是函数 g 的 c 倍，除非 n 小于 n0。因此对于足够大的 n (如 nn0)，g 是 f 的一个上限（不考虑常数因子 c）。在为函数 f 提供一个上限函数 g 时，通常使用比较简单的函数形式。比较典型的形式是含有 n 的单个项（带一个常数系数）。表 1-1 列出了一些常用的 g 函数及其名称。对于表 1-1 中的对数函数 logn，没有给出对数基，原因是对于任何大于 1 的常数 a 和 b 都有 logan =logbn/logba,所以 logan 和 logbn 都有一个相对的乘法系数 1/logba，其中 a 是一个常量。表 1-1 常用的渐进函数1.9 算法的空间复杂度指的是什么？如何表示？【答】：算法的空间复杂度是指算法在执行过程中占用的额外的辅助空间的个数。可以将它表示为问题规模的函数，并通过大写O符号表示空间复杂度。1.10 对于下面的程序段，分析带下划线的语句的执行次数，并给出它们的时间复杂度 T(n)。（1） i+ ;（2） for(i=0;in;i+)if (aix) x=ai;（3）for(i=0;in;i+)for(j=0;jn;j+)printf(“%d”,i+j) ;（4）for (i=1;i=n-1;i+) k=i;for(j=i+1;jaj+1) k=j;t=ak; ak=ai; ai=t;（5）for(i=0;in;i+)for(j=0;jn;j+)+x;s=s+x;【答】：（1）O（1）；（2）O（n）；（3）O（n2）；（4）O（n2）；（5）O（n2）4十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程第 2 章线性表及其顺序存储2.1 选择题（1）表长为 n 的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（为（ A ）。E），删除一个元素所需移动元素的平均个数A（n1）/2En/2BnF(n+1)/2Cn+1G(n2)/2Dn1（2）设栈 S 和队列 Q 的初始状态为空，元素 e1、e2、e3、e4、e5 和 e6 依次通过栈 S，一个元素出栈后即进入队列 Q，若 6 个元素出队的序列为 e2、e4、e3、e6、e5 和 e1，则栈 S的容量至少应该为（ C ）。A6B4C3D2（3）设栈的输入序列为 1、2、3 n，若输出序列的第一个元素为 n，则第 i 个输出的元素为（ B ）。A不确定Bni+1CiDni（4）在一个长度为 n 的顺序表中删除第 i 个元素（1=i=n）时，需向前移动（ A ）个元素。AniBni+1Cni1Di（5）若长度为 n 的线性表采用顺序存储结构存储，在第 i 个位置上插入一个新元素的时间复杂度为（ A ）。AO(n)BO(1)CO(n2)DO(n3)（6）表达式 a*(b+c)d 的后缀表达式是（ B）。Aabcd*+Babc+*dCabc*+dD+*abcd（7）队列是一种特殊的线性表，其特殊性在于（ C ）。A插入和删除在表的不同位置执行 B插入和删除在表的两端位置执行C插入和删除分别在表的两端执行 D插入和删除都在表的某一端执行（8）栈是一种特殊的线性表，具有（ B ）性质。A先进先出B先进后出C后进后出D顺序进出（9）顺序循环队列中（数组的大小为 n），队头指示 front 指向队列的第 1 个元素，队尾指示 rear 指向队列最后元素的后 1 个位置，则循环队列中存放了 n 1 个元素，即循环队列满的条件为（ B）。A(rear+1)%n=front1C(rear)%n=frontB(rear+1)%n=frontDrear+1=front（10）顺序循环队列中（数组的大小为 6），队头指示 front 和队尾指示 rear 的值分别为 3和 0，当从队列中删除 1 个元素，再插入 2 个元素后，front 和 rear 的值分别为（ D ）。A5 和 1B2 和 4C1 和 5D4 和 22.2 什么是顺序表？什么是栈？什么是队列？5十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程【答】：当线性表采用顺序存储结构时，即为顺序表。栈是一种特殊的线性表，它的特殊性表现在约定了在这种线性表中数据的插入与删除操作只能在这种线性表的同一端进行（即栈顶），因此，栈具有先进后出、后进先出的特点。队列也是一种特殊的线性表，它的特殊性表现在约定了在这种线性表中数据的插入在表的一端进行，数据的删除在表的另一端进行，因此队列具有先进先出，后进后出的特点。2.3 设计一个算法，求顺序表中值为 x 的结点的个数。【答】：顺序表的存储结构定义如下（文件名 seqlist.h）：#include #define N 100typedef int 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 中，倒置的结果是使得数组 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，实现本题要求的算法程序如下：6十二五普通高等教育国家级本科规划教材void insertx(seqlist *L,datatype x)int j;if (L-lengthlength-1;while (j=0 & L-datajx) L-dataj+1=L-dataj;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