数据结构课后答案.doc

1、第 1 章 绪论1简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生

2、基本信息表中的学号、姓名、性别等都是数据项。数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N=0，1，2，字母字符数据对象是集合 C=A， B， Z， a， b， z，学生基本信息表也可是一个数据对象。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合， “结构”就是指数据元素之间存在的关系。逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。存储结构：数据对象在计算机中的存储表示，也称为物理结构。抽象数据类型：由用户定义的，表

3、示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。2试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。答案：例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。这些学生记录在计算机中的存储

4、表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。即相同的逻辑结构，可以对应不同的存储结构。3简述逻辑结构的四种基本关系并画出它们的关系图。答案：（1）集合结构数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是否为班级成员，只需将班级看做一个集合结构。（2）线性结构数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构。（3）树结构数据元素之间存在一对多的关系。例如，在班级的管理体系中，班长管理多

5、个组长，每位组长管理多名组员，从而构成树形结构。（4）图结构或网状结构数据元素之间存在多对多的关系。例如，多位同学之间的朋友关系，任何两位同学都可以是朋友，从而构成图形结构或网状结构。其中树结构和图结构都属于非线性结构。4存储结构由哪两种基本的存储方法实现？答案：（1）顺序存储结构顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。（2）链式存储结构顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无需占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。所以链式存

6、储结构通常借助于程序设计语言的指针类型来描述。5选择题（1）在数据结构中，从逻辑上可以把数据结构分成（ ） 。A动态结构和静态结构 B紧凑结构和非紧凑结构C线性结构和非线性结构 D内部结构和外部结构答案：C（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ） 。A存储结构 B存储实现C逻辑结构 D运算实现答案：C（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ） 。A数据具有同一特点B不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C每个数据元素都一样D数据元素所包含的数据项的个数要相等答案：B（4）以下说法正确的是（ ） 。A数据元素是

7、数据的最小单位B数据项是数据的基本单位四类基本逻辑结构关系图C数据结构是带有结构的各数据项的集合D一些表面上很不相同的数据可以有相同的逻辑结构答案：D解释：数据元素是数据的基本单位，数据项是数据的最小单位，数据结构是带有结构的各数据元素的集合。（5）算法的时间复杂度取决于（ ） 。A问题的规模 B待处理数据的初态C计算机的配置 DA 和 B答案：D解释：算法的时间复杂度不仅与问题的规模有关，还与问题的其他因素有关。如某些排序的算法，其执行时间与待排序记录的初始状态有关。为此，有时会对算法有最好、最坏以及平均时间复杂度的评价。（6）以下数据结构中， （ ）是非线性数据结构A树 B字符串 C队列

8、D栈答案：A6试分析下面各程序段的时间复杂度。（1）x=90; y=100; while(y0)if(x100)x=x-10;y-;else x+;答案：O(1)解释：程序的执行次数为常数阶。（2）for (i=0; i1y=0;while(x(y+1)* (y+1)y+;答案：O( )n解释：语句 y+;的执行次数为 。n第 2 章 线性表1 选择题（1 ） 顺 序 表 中 第 一 个 元 素 的 存 储 地 址 是 100， 每 个 元 素 的 长 度 为 2， 则 第 5 个 元 素 的 地 址 是 （ ） 。A110 B108 C100 D120答案：B解释：顺序表中的数据连续存储，所

9、以第 5 个元素的地址为： 100+2*4=108。（2 ） 在 n 个结点的顺序表中，算法的时间复杂度是 O(1)的操作是（ ） 。A访问第 i 个结点（1in ）和求第 i 个结点的直接前驱（ 2in） B在第 i 个结点后插入一个新结点（1 in）C 删除第 i 个结点（1i n）D将 n 个结点从小到大排序答案：A解释：在顺序表中插入一个结点的时间复杂度都是 O(n2)，排序的时间复杂度为 O(n2)或 O(nlog2n)。顺序表是一种随机存取结构，访问第 i 个结点和求第 i 个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是 O(1)。（3 ） 向一个有 127 个元素

10、的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 的元素个数为（ ） 。A8 B63.5 C63 D7答案：B解释：平均要移动的元素个数为：n/2。（4 ）链接存储的存储结构所占存储空间（ ） 。A分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B只有一部分，存放结点值C只有一部分，存储表示结点间关系的指针D分两部分，一部分存放结点值，另一部分存放结点所占单元数答案：A（5 ）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ） 。A必须是连续的 B部分地址必须是连续的C一定是不连续的 D连续或不连续都可以答案：D（6 ）线性表在（ ）情况下适用于使用链式结构实现。

11、A需经常修改中的结点值 需不断对进行删除插入 C中含有大量的结点 中结点结构复杂答案：B解释：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。（7 ）单链表的存储密度（ ） 。A大于 1 B等于 1 C小于 1 D不能确定答案：C解释：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比，假设单链表一个结点本身所占的空间为 D，指针域所占的空间为 N，则存储密度为： D/(D+N)，一定小于1。（8 ）将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是（ ） 。An B2n-1 C2n Dn-1答案：A解释：当第一个有序表中所有的元素都小于（或

12、大于）第二个表中的元素，只需要用第二个表中的第一个元素依次与第一个表的元素比较，总计比较 n 次。（9 ）在一个长度为 n 的顺序表中，在第 i 个元素（1i n+1）之前插入一个新元素时须向后移动（ ）个元素。An-i Bn-i+1 Cn-i-1 DI答案：B(10) 线性表 L=(a1，a 2,an)，下列说法正确的是（ ） 。A每个元素都有一个直接前驱和一个直接后继B线性表中至少有一个元素C表中诸元素的排列必须是由小到大或由大到小D除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。答案：D(11) 创建一个包括 n 个结点的有序单链表的时间复杂度是（ ） 。AO

13、(1) BO(n) CO(n 2) DO(nlog 2n)答案：C解释：单链表创建的时间复杂度是 O(n)，而要建立一个有序的单链表，则每生成一个新结点时需要和已有的结点进行比较，确定合适的插入位置，所以时间复杂度是 O(n2)。(12) 以下说法错误的是（ ） 。A求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B顺序存储的线性表可以随机存取C由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活D线性表的链式存储结构优于顺序存储结构答案：D解释：链式存储结构和顺序存储结构各有优缺点，有不同的适用场合。(13) 在单链表中，要将 s 所指结点插入到 p

14、 所指结点之后，其语句应为（ ） 。As-next=p+1; p-next=s;B(*p).next=s; (*s).next=(*p).next;C s-next=p-next; p-next=s-next;Ds-next=p-next; p-next=s; 答案：D(14) 在双向链表存储结构中，删除 p 所指的结点时须修改指针（ ） 。Ap-next-prior=p-prior; p-prior-next=p-next;Bp-next=p-next-next; p-next-prior=p;C p-prior-next=p; p-prior=p-prior-prior;Dp-prior=

15、p-next-next; p-next=p-prior-prior;答案：A(15) 在双向循环链表中，在 p 指针所指的结点后插入 q 所指向的新结点，其修改指针的操作是（ ） 。Ap-next=q; q-prior=p; p-next-prior=q; q-next=q;Bp-next=q; p-next-prior=q; q-prior=p; q-next=p-next;C q-prior=p; q-next=p-next; p-next-prior=q; p-next=q;Dq-prior=p; q-next=p-next; p-next=q; p-next-prior=q;答案：C第

16、 3 章 栈和队列1选择题（1 ）若让元素 1，2 ，3，4，5 依次进栈，则出栈次序不可能出现在（ ）种情况。A5，4，3，2，1 B2，1 ，5，4 ，3 C4，3 ，1，2，5 D2，3 ，5，4，1答案：C解释：栈是后进先出的线性表，不难发现 C 选项中元素 1 比元素 2 先出栈，违背了栈的后进先出原则，所以不可能出现 C 选项所示的情况。（2 ）若已知一个栈的入栈序列是 1，2，3 ，n，其输出序列为 p1，p2 ，p3，pn，若p1=n，则 pi 为（ ） 。Ai Bn-i Cn-i+1 D不确定答案：C解释：栈是后进先出的线性表，一个栈的入栈序列是 1， 2，3，n，而输出序列

17、的第一个元素为 n，说明 1，2 ，3，n 一次性全部进栈，再进行输出，所以 p1=n，p2=n-1 ，pi=n-i+1 。（3 ）数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素个数的公式为（ ） 。Ar-f B(n+f-r)%n Cn+r-f D （n+r-f)%n答案：D解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上 MAXSIZE（本题为 n） ，然后与 MAXSIZE（本题为 n）求余，即（n+r-f)%n。（4 ）链式栈结点为：(data,link)，top

18、 指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到 x 中,则应执行操作（ ） 。Ax=top-data;top=top-link； Btop=top-link;x=top-link； Cx=top;top=top-link； Dx=top-link；答案：A解释：x=top-data 将结点的值保存到 x 中，top=top-link 栈顶指针指向栈顶下一结点，即摘除栈顶结点。（5 ） 设有一个递归算法如下int fact(int n) /n 大于等于 0if(n=0) return 1;else return n*fact(n-1); 则计算 fact(n)需要调用该函数的次数为（ ）

19、。 A n+1 B n-1 C n D n+2答案：A解释：特殊值法。设 n=0，易知仅调用一次 fact(n)函数，故选 A。（6 ）栈在 （ ）中有所应用。A递归调用 B函数调用 C表达式求值 D前三个选项都有答案：D解释：递归调用、函数调用、表达式求值均用到了栈的后进先出性质。（7 ）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ） 。A队列 B栈 C 线性表 D有序表答案：A解释：解决缓冲区问题应利用一种先进先出的线性表，而队列正是一种先进先出的线性表。（8 ）设栈

20、 S 和队列 Q 的初始状态为空，元素 e1、e2 、e3、e4、e5 和 e6 依次进入栈 S，一个元素出栈后即进入 Q，若 6 个元素出队的序列是 e2、e4、e3 、e6 、e5 和 e1，则栈 S 的容量至少应该是（ ） 。A2 B3 C4 D 6答案：B解释：元素出队的序列是 e2、e4 、e3、e6、e5 和 e1，可知元素入队的序列是e2、e4、e3 、e6、e5 和 e1，即元素出栈的序列也是 e2、 e4、e3、e6、e5 和 e1，而元素e1、e2、e3 、e4、e5 和 e6 依次进入栈，易知栈 S 中最多同时存在 3 个元素，故栈 S 的容量至少为 3。（9 ）若一个栈

21、以向量 V1.n存储，初始栈顶指针 top 设为 n+1，则元素 x 进栈的正确操作是( )。Atop+; Vtop=x; BVtop=x; top+;Ctop-; Vtop=x; DVtop=x; top-;答案：C解释：初始栈顶指针 top 为 n+1，说明元素从数组向量的高端地址进栈，又因为元素存储在向量空间 V1.n中，所以进栈时 top 指针先下移变为 n，之后将元素 x 存储在 Vn。（10 ）设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。A线性表的顺序存储结构 B队列 C. 线性表的链式存储结构 D. 栈答案：D解释：利用栈的后进先出原则。（11 ）用

22、链接方式存储的队列，在进行删除运算时（ ） 。A. 仅修改头指针 B. 仅修改尾指针C. 头、尾指针都要修改 D. 头、尾指针可能都要修改答案：D解释：一般情况下只修改头指针，但是，当删除的是队列中最后一个元素时，队尾指针也丢失了，因此需对队尾指针重新赋值。（12 ）循环队列存储在数组 A0.m中，则入队时的操作为（ ） 。A. rear=rear+1 B. rear=(rear+1)%(m-1)C. rear=(rear+1)%m D. rear=(rear+1)%(m+1) 答案：D解释：数组 A0.m中共含有 m+1 个元素，故在求模运算时应除以 m+1。（13 ）最大容量为 n 的循环

23、队列，队尾指针是 rear，队头是 front，则队空的条件是（ ） 。A. (rear+1)%n=front B. rear=front Crear+1=front D. (rear-l)%n=front答案：B解释：最大容量为 n 的循环队列，队满条件是(rear+1)%n=front，队空条件是 rear=front。（14 ）栈和队列的共同点是（ ） 。A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点答案：C解释：栈只允许在栈顶处进行插入和删除元素，队列只允许在队尾插入元素和在队头删除元素。（15 ）一个递归算法必须包括（ ） 。A. 递归部

24、分 B. 终止条件和递归部分C. 迭代部分 D. 终止条件和迭代部分答案：B第 4 章 串、数组和广义表1 选择题（1 ）串是一种特殊的线性表，其特殊性体现在（ ） 。A可以顺序存储 B数据元素是一个字符 C可以链式存储 D数据元素可以是多个字符若 答案：B（2 ）串下面关于串的的叙述中， （ ）是不正确的？ A串是字符的有限序列 B空串是由空格构成的串C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储答案：B解释：空格常常是串的字符集合中的一个元素，有一个或多个空格组成的串成为空格串，零个字符的串成为空串，其长度为零。 （3 ）串“ababaaababaa”的 next

25、 数组为（ ） 。A012345678999 B012121111212 C011234223456 D0123012322345答案：C（4 ）串“ababaabab ”的 nextval 为（ ） 。A010104101 B010102101 C010100011 D010101011 答案：A（5 ）串的长度是指（ ） 。A串中所含不同字母的个数 B串中所含字符的个数C串中所含不同字符的个数 D串中所含非空格字符的个数答案：B解释：串中字符的数目称为串的长度。（6 ）假设以行序为主序存储二维数组 A=array1.100,1.100，设每个数据元素占 2 个存储单元，基地址为 10，则

26、LOC5,5=（ ） 。A808 B818 C1010 D1020答案：B解释：以行序为主，则 LOC5,5=（5-1）*100+（5-1）*2+10=818。（7 ）设有数组 Ai,j，数组的每个元素长度为 3 字节，i 的值为 1 到 8，j 的值为 1 到 10，数组从内存首地址 BA 开始顺序存放，当用以列为主存放时，元素 A5,8的存储首地址为（ ） 。ABA+141 BBA+180 CBA+222 DBA+225答案：B解释：以列序为主，则 LOC5,8=（8-1）*8+ （5-1）*3+BA=BA+180。（8 ）设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储

27、， a11 为第一元素，其存储地址为 1，每个元素占一个地址空间，则 a85 的地址为（ ） 。A13 B32 C33 D40答案：C（9 ）若对 n 阶对称矩阵 A 以行序为主序方式将其下三角形的元素(包括主对角线上所有元素) 依次存放于一维数组 B1.(n(n+1)/2中，则在 B 中确定 aij（ij ）的位置 k 的关系为（ ） 。Ai*(i-1)/2+j Bj*(j-1)/2+i Ci*(i+1)/2+j Dj*(j+1)/2+i答案：B（10 ）二维数组 A 的每个元素是由 10 个字符组成的串，其行下标 i=0,1,8,列下标j=1,2,10。若 A 按行先存储，元素 A8,5的

28、起始地址与当 A 按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。AA8,5 BA3,10 C. A5,8 DA0,9答案：B解释：设数组从内存首地址 M 开始顺序存放，若数组按行先存储，元素 A8,5的起始地址为：M+（8-0）*10+（5-1）*1=M+84；若数组按列先存储，易计算出元素 A3,10的起始地址为：M+（10-1）*9+（3-0）*1=M+84。故选 B。（11 ）设二维数组 A1. m，1. n（即 m 行 n 列）按行存储在数组 B1. m*n中，则二维数组元素Ai,j在一维数组 B 中的下标为（ ） 。A(i-1)*n+j B(i-1)*n+j-1 Ci

29、*(j-1) Dj*m+i-1答案：A解释：特殊值法。取 i=j=1，易知 A1,1的的下标为 1，四个选项中仅有 A 选项能确定的值为 1，故选 A。（12 ）数组 A0.4,-1.-3,5.7中含有元素的个数（ ） 。A55 B45 C36 D16答案：B解释：共有 5*3*3=45 个元素。（13 ）广义表 A=(a,b,(c,d),(e,(f,g)，则 Head(Tail(Head(Tail(Tail(A)的值为（ ） 。A(g) B(d) Cc Dd答案：D解释：Tail(A)=(b,(c,d),(e,(f,g)；Tail(Tail(A)=( (c,d),(e,(f,g)； Head

30、(Tail(Tail(A)= (c,d)；Tail(Head(Tail(Tail(A)=(d)；Head(Tail(Head(Tail(Tail(A)=d 。（14 ）广义表 (a,b,c,d)的表头是（ ） ，表尾是（ ） 。Aa B( ) C(a,b,c,d) D(b,c,d)答案：C、B解释：表头为非空广义表的第一个元素，可以是一个单原子，也可以是一个子表，(a,b,c,d)的表头为一个子表(a,b,c,d) ；表尾为除去表头之外，由其余元素构成的表，表为一定是个广义表，(a,b,c,d)的表尾为空表( )。（15 ）设广义表 L=(a,b,c)，则 L 的长度和深度分别为（ ） 。A1

31、 和 1 B1 和 3 C1 和 2 D2 和 3 答案：C解释：广义表的深度是指广义表中展开后所含括号的层数，广义表的长度是指广义表中所含元素的个数。根据定义易知 L 的长度为 1，深度为 2。2应用题 （1 ）已知模式串 t=abcaabbabcab写出用 KMP 法求得的每个字符对应的 next 和 nextval 函数值。答案：模式串 t 的 next 和 nextval 值如下：j 1 2 3 4 5 6 7 8 9 10 11 12 t 串 a b c a a b b a b c a bnextj 0 1 1 1 2 2 3 1 2 3 4 5nextvalj 0 1 1 0 2

32、1 3 0 1 1 0 5（2 ） 设目标为 t=“abcaabbabcabaacbacba”,模式为 p=“abcabaa” 计算模式 p 的 naxtval 函数值； 不写出算法,只画出利用 KMP 算法进行模式匹配时每一趟的匹配过程。答案： p 的 nextval 函数值为 0110132。 （p 的 next 函数值为 0111232） 。 利用 KMP(改进的 nextval)算法，每趟匹配过程如下：第一趟匹配： abcaabbabcabaacbacbaabcab(i=5,j=5)第二趟匹配： abcaabbabcabaacbacbaabc(i=7,j=3)第三趟匹配： abcaab

33、babcabaacbacbaa(i=7,j=1)第四趟匹配： abcaabbabcabaac bacba(成功) abcabaa(i=15,j=8)（3 ）数组 A 中，每个元素 Ai,j的长度均为 32 个二进位 ,行下标从-1 到 9，列下标从 1 到 11，从首地址 S 开始连续存放主存储器中，主存储器字长为 16 位。求： 存放该数组所需多少单元？ 存放数组第 4 列所有元素至少需多少单元？ 数组按行存放时，元素 A7,4的起始地址是多少？ 数组按列存放时，元素 A4,7的起始地址是多少？答案：每个元素 32 个二进制位，主存字长 16 位，故每个元素占 2 个字长，行下标可平移至 1 到 11。（1）242 （2）22 （3）s+182 （4）s+142(4)请将香蕉 banana 用工具 H( )Head( )，T( )Tail( )从 L 中取出。L=(apple,(orange,(strawberry,(banana),peach),pear)答案：H（H（T（H（T（H（T（L） ） ） ） ） ） ）第 5 章 树和二叉树1 选 择 题（ 1） 把 一 棵 树 转 换 为 二 叉 树 后 ， 这 棵 二 叉 树 的 形 态 是 （ ） 。 A唯 一 的 有 多 种C有多种，但根结点都没有左孩子 有多种，但根结点都没有右孩子