数据结构习题集第二版.doc

C语言描述 数据结构习题分析 付 永 华 信息技术教研室 数据结构习题分析 前 言 这本数据结构习题集是数据结构习题分析的第二版，保留了数据结构习题分析的基本题目，其修改的侧重点是增加了题目（尤其是算法）的分析，使得使用者在作题目尤其是自学的时候，能够更快更好得了解和掌握。这本数据结构习题集的内容是按照严蔚敏老师编著的教科书数据结构(C语言版)的内容和课程教学要求组织的各章均由基本内容、学习要点、基础知识题（填空、判断、选择、综合、算法）三部分组成。 基本内容 列举了该章的内容提要，提醒读者把握该章主要内容；学习要点 指出了该章的教学重点和难点，以供读者在组织教学或自学时选择习题作参考，而且部分题目是学习要点的发挥，可以引导学生进一步了解数据结构的特点。数据结构的基础知识练习题 大致可分为填空、判断、选择、综合、算法五类。主要供读者进行复习自测之用，目的是帮助读者深化理解教科书的内容，澄清基本概念、理解和掌握数据结构中分析问题的基本方法和算法要点，为完成算法设计题做准备。其实，算法设计是数据结构这门课的重点，虽然，我们因为学时的原因，对设计算法的题目练习的比较少，但是，我们必须知道，算法设计实际是数据结构的精华和核心部分，我们所学的基本知识主要是为算法的设计服务的。在这本习题集里，编者根据每一章节的特点，结合实际应用，给出了部分算法实现的题目，这也是数据结构考研题目的特点。 在习题集中，各章的题量根据教学内容的多少和重要程度而定，为了便于理解和掌握，编者按教科书的每一小节做的安排选择；为了表明题目的难易程度，也便于学生对题目可以根据自己的需要自由的取舍，编者在每个题的题号之后注了一个难度系数，难度级别从A至D逐渐加深。同时每一个题目都有答案，部分难度较大的题目还给除了求解答案的方法和过程，便于理解数据结构题目的解答的思路。在习题集的最后，编者还附了一套考研的真题，从里面可以看出来，数据结构的题目考研的题目并不难，有比较多的基础题，主要是考试的面比较宽，这就需要我们对数据结构的基本知识点掌握的比较扎实，才能在考试的时候举一反三。比如说有一道题目是这样的：在一个图的邻接表中，边结点的个数为7，要求判断这个图示有向图还是无向图，根据无向图和有向图邻接表存储的特点，我们知道肯定是有向图。除了掌握知识点之外，还需要我们多做题目，对题型比较熟练，这样才能比较迅速的得到答案，不至于浪费时间。比如说 给出一棵二叉树的先序遍历序列和中序遍历序列，要求写出它的后序遍历，我们都知道应该采用我们总结的根结点和左右子树位置法求解，用根结点法区判断结果的正确性，但是因为平时训练的比较少，像这类本应该迅速得到答案的题目还需要一定的时间去考虑，这样必然会浪费时间的。因为编者本身知识有限，因此错误之处在所难免，请同学们在使用时指出，随时欢迎同学们提出宝贵意见和建议。fuyonghua_12 信息技术教研室 2006/8/101第一章 绪 论 第一章 绪 论 一、基本内容 1、数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义； 2、抽象数据类型的定义、表示和实现方法；描述算法的类C语言；算法设计的基本要求以及从时间和空间角度分析算法的方法。二、学习要点 1、熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。 2、了解抽象数据类型的定义、表示和实现方法。 3、熟悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式以及错误处理方式。 4、理解算法五个要素的确切含义：有穷性(能执行结束)；确定性(对于相同的输入执行相同的路径);有输入;有输出;可行性(用以描述算法的操作都是足够基本的)。5、掌握计算语句频度和估算算法时间复杂度的方法。三、基础知识 3 . 1 数据结构1、数据是指能被计算机识别、存储和加工的信息的载体。2、数据元素是数据的最小的基本单位，有时候一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小数据表示单位。3、数据结构是相互之间存在一种或者多种特定关系的数据元素的集合，这些结构不是孤立存在的，而是有着某种联系，这种关系称为结构。根据数据元素之间关系的不同，可以分为下列四类基本结构：集合：结构中数据元素同属于一个集合。线性结构：结构中数据元素存在一对一的关系。树形结构：结构中数据元素存在一对多的关系。图形结构：结构中数据元素存在多对多的关系。数据结构包括三方面的内容：逻辑结构、存储结构（物理结构）和数据运算或操作。4、逻辑结构是对数据结构之间关系的描述，所以有时候就把数据的逻辑结构简称为数据结构。它被形式的定义为（D，R），其中D是数据元素的的有限集合，R是D上的关系。5、数据在计算机内的表示成为数据的物理结构（或者存储结构）。6、在数据的物理结构中，结点有四种存储方式：1） 顺序存储方式是把逻辑上相邻的结点存储在物理上相邻的存储单元里，结2数据结构习题分析点之间的关系由存储单元的邻接关系来体现。其优点是占用最少的存储空间;其缺点是由于只能使用相邻的的一整块儿存储单元，因此可能产生较多的碎片。 2）链式存储方式是把逻辑上相邻的结点存储在物理上任意的存储单元里，结点之间的关系由存储单元的指针来体现。结点所占的存储单元分为两部分，一本分用来存放本身的信息，即为数据项;另一部分用来存放该结点的后继结点的存储单元的地址，即指针信息。优点是不会出现碎片，缺点每一个结点所占的存储空间变大（多了指针域）。而且不能一步查找数据元素。3）索引式存储方式是用结点的索引号来确定结点的存储地址，优点是检索速度快。缺点是增加了附加的索引表，会占用较多的存储空间;而且在增加和删除数据是由于用较多的索引表而花费太多的时间。4）散列式存储方式是根据结点的值确定它们的存储位置，其优点是检索、增加、删除结点的速度都很快;其缺点是采用不好的散列函数会出现结点冲突，为了解决冲突需要增加时间和空间的开销。7、在循环队列、链表、哈希表、和栈中，与数据存储无关的哈希表。8、数据结构的分类 数组、顺序表 线性结构 栈和队列、串 逻辑结构 非线性结构 广义表、树和二叉树 图、文件 数据结构 顺序存储结构 存储结构 链式存储结构索引式存储结构 散列式存储结构 9、在算法设计过程中，常用下面三种不同的出错处理方式：1） 用exit 语句终止执行并报告错误。2） 以函数的返回值区别正确返回或错误返回。3） 设置一个整型变量的函数参数以区别正确返回和错误返回。 3 .2 2 算法和算法分析1、算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一种指令表示一个或者多个操作。2、算法有五个重要的特性：1） 有穷性：能执行结束，而且在有限的时间之内执行结束。（有的材料认为有穷行不考虑实际的执行时间，在这里我们按照课本叙述）2） 确定性：对于相同的输入执行相同的路径，没有二义性。3） 输入：一个算法有零个或者多个输入。4） 输出：一个算法有一个或者多个输出。35） 可行性：用以描述算法的操作都是足够基本的已经实现的。第一章 绪 论3、算法评级标准：正确性、可读性、健壮性、效率与低存储率。4、算法分析主要有两个方面：算法的时间复杂度和空间复杂度。5、语句的频度指的是语句在算法中被执行的次数，有确定的值。算法中所有的语句的频度之和记作T（n），当问题的规模n趋向于无穷大时，T（n）的数量级称为渐进时间复杂度，简称为时间复杂度，记作T（n）=O（f（n）。6、时间复杂度和问题的规模n有关，在一般情况下，我们考虑在最坏情况下的实际复杂度，以保证算法的运行时间不会比它的时间复杂度更长。四、练习题 4 . 1 填 空 题1、数据逻辑结构包括集合、线性结构、 、 四种类型，其中后两种结构又称为 。答案： 树形结构、图形结构、非线性结构2、在线性结构中， 结点没有前驱结点，其余结点有且只有一个前驱结点; 结点没有后继结点，其余每一个结点有且只有一个后继。答案： 第一个、最后一个3、在树形结构中， 没有前驱结点;其余每一个结点有且只有 前驱; 没有后继结点，其余的结点的后继结点可以是任意多个。 答案： 根结点、叶子结点4、下面程序的时间复杂度是多少 。 for （ i = 0 ;i n ; i + + ） for （ j = 0 ;j m ; j + + ） A i j = 0 ; 答案： O（ m * n ） 5、下面程序的时间复杂度是多少 。 i = s = 0 ; while （ s n ） i + + ; s + = i ; 答案： O（ ） 6、下面程序的时间复杂度是多少 。 i = 1; while （ i = n ） i = i * 3 ; 答案： O（ log 3 n ）7、如果n是偶数，下面的程序的时间复杂度是多少 。m值是多少？4 数据结构习题分析m = 0 ; for （ i = 1 ;i = n ; i + + ） for （ j = 2 * i ;j = n ; j + +） m = m +1 ; 答案： O（ n 2 ） n 2 / 48、分析下面语句中循环语句执行的次数 int j = 0 ，s = 0 ， n = 100 ; do j = j + + ; s = s +10 * j ; while （ j n & s n ）; 答案： 4次 (是先循环,后判断)9、分析下面语句中循环语句执行的次数。 for （int I=1，I=n ,I+） for （int j=1，j=I ,j+） s;答案： n(n+1)/2 10、分析下面语句中循环语句执行的次数。 for （int I=1，I=I ,j- -） s;答案： (n+3)(n-2)/2 11、下面两个算法违反了算法的那些特性？（1）void exam1（） n = 2 ; while （n%2 = = 0）n = n +2 ; printf（ “ % d n ”, n）; （2）void exam2（） y = 0 ; x = 5 / y ;printf（ “ % d, % d n ”, x ,y）; 答案： （1）是一个死循环，违反了算法的有穷性。 （2）包含了除零错误，违反了可行性。4 . 2 判 断 题 1、 顺序存储方式只能用来存储线性结构 X 2、 顺序存储方式的优点是存储密度大，且插入、删除、运算效率高。X 3、 散列存储方式的基本思想是有关键字的的值决定数据的存储地址。5第一章 绪 论4、 散列表的结点只包含数据本身的信息，不包含任何指针。 X 5、 栈和队列的存储方式既可以是顺序方式，也可以是链式方式。 6、 算法的时间复杂度只取决于问题的规模，与待处理的数据的无关。7、 算法最终必须要由计算机来实现。 X8、 为解决某问题的算法与为该问题编写的程序的含义是一样的。 9、 原地工作的意义就是不需要任何额外的辅助空间 X10、在相同的规模下，时间复杂度为O(n)的算法在时间上总是优于时间复杂度为 O(2n)的算法. 11、所谓的时间复杂度就是在最坏的情况下，估计一个算法执行时间的上界。12、同一个算法，实现算法的语言越高，执行效率越低。 13、公式或者图形不能用来描述算法。 X 14、数据结构为算法提供了工具，而算法则是运用了这些工具来实施解决问题的最优方案。 15、算法独立于具体的程序设计语言和具体的计算机。 16、算法的设计取决了选定的逻辑结构，算法的实现依赖于采用的存储结构。4 . 3 选 择 题1、下面函数中，渐进时间最小的是什么？ ( A ) A T1（n）=n log 2 n +1000 log 2 n B T2（n）=n log 2 3 1000 log 2 n C T3（n）=n 2 1000 log 2 n D T4（n）=2n log 2 n 1000 log 2 n2、每一种数据结构都具有三个基本运算：插入、删除和求长度。 ( B ) A 正确 B 不正确3、计算机算法指的是什么？ ( C ) A 计算方法 B 排序方法 C 解决问题的有限运算序列 D 调度方法4、线性结构的顺序存储是一种 的结构。 ( A ) A 随机存储 B 顺序存储 C 索引存储 D 散列存储5、算法分析的目的是 。 ( A ) A 分析算法的效率以求改进 B 研究算法中的输出和输入的关系 C 找出数据结构的合理性 D 分析算法的易懂性和文档性 4 . 4 综 合 题1、有下列二元组表示的数据结构，划出他们的逻辑图。 图 1_1A = （ K ，R ） K = （ a ，b ，c ，d ，e ，f ，g ，h ）R = r r = , 6 数据结构习题分析2、有下列二元组表示的数据结构，划出他们的逻辑图。A = （ K ，R ） K = （ 1 ，2 ，3 ，4 ，5 ，6 ） 图1_2 R = r r = （1 ,2）,（2 ,3）,（2 ,4）,（3 ,4）,（3 ,5）,（3 ,6）,（4 ,5）,（4 ,6） 3、有下列二元组表示的数据结构，划出他们的逻辑图。 图1_3 A = （ K ，R ） K = （ 48 ，25 ，64 ，57 ，82 ，36 ，75）R = r 1 ，r2 R1 = , R2 = , 图1_348253664578275dbgacehf 图1_1124356图1_24 . 5 算法设计题 1、求两个n阶矩阵的乘法 C = A B，求其算法并分析该算法的时间复杂度 define MAX 100void maxtrixmult （ int n ，float a MAX MAX ，b MAX MAX ，float c MAX MAX ） int i ，j ，k ;float x ;for （ i = 1;i = n ;i + + ） for （ j = 1;j = n ;j + + ） x = 0 ; for （k = 1 ;k= n ;k + +） x + = a i k * b k j ; c i j = x ; 答案： 语句的频度为 n + 1 n（n+1） n 2 n 2（n+1） n 3 n 2 所以时间复杂度为 + =2 n 3 + 3n 2 +2n +1 =O（n 3）2、 编写一个算法求一元多项式之和 P n（x）= a i x i 的值 P n（x 0） 7 算法如下：第一章 绪 论void polyvalue() float ad ; float *p=a ; printf(Input number of terms:) ； scanf(%d,&n) ； printf(Input the %d coefficients from a0 to a%d:n,n,n); for(i=0;i=n;i+) scanf(%f,p+); printf(Input value of x:); scanf(%f,&x); p=a;xp=1;sum=0; /xp用于存放x的i次方 for(i=0;inext)是结点*p的后继等)，链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求。3、熟练掌握线性表在顺序存储结构上实现基本操作：查找、插入和删除的算法。4、熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构。了解静态链表，能够加深对链表本质的理解。5、能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。三、基础知识 1、线性表是具有n个数据元素的有限序列。2、线性表中的元素的个数n定义为线性表的长度。n = 0时为空表。3、线性表中常表示为（a1 ，a2 ，ai ， an），其中a1称为起始结点，an称为终端结点，i 称为元素ai 的位置或者序号，成为位序。ai 称为ai+1的直接前驱， ai+1 称为ai的直接后继。4、线性结构中的每一个结点表示一个数据元素，在不同的实际问题中，结点的数据元素可以不同，但是通常要求同一个线性表中的所有结点代表的数据元素具有相同的属性。5、线性表的顺序存储结构通过元素的相对存储地址来表示元素之间的关系。顺序存储结构具有三个弱点：其一，在做插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间；其三，表的容量难以扩充。优点是可以随机存取数据,空间利用率高。 6、顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。7、在数组中，顺序表的表长为sq . length，但是最后一个结点应该为sq . date sq . length - 19第二章 线性表8、如果一个线性表的每一个元素占用L个存储单元，用LOC（ai）表示第i个元素的存储起始位置，则LOC（ai+1）=LOC（ai）+L LOC（ai）=LOC（a1）+（i-1）*L。LOC（a1）通常称为线性表的起始位置或者基地址。9、在一个长度为n的顺序存储的线性表中插入或者删除一个元素的时间复杂度为O（n）。10、线性表的最常用的操作是存取第i 个元素及其前驱的值或者插入和删除，如果采用顺序存储节省时间。11、线性表的链接存储结构是一种顺序存取的存储结构。在单链表中，不能从当前结点出发访问到任一结点。欲删除某一指定结点时，必须找到该结点的前驱结点。12、在单链表中设置头结点的作用是便于结点的插入和删除运算。13、在单链表、静态链表、线性链表和顺序存储结构中，不需要分配较大空间和删除不需要移动元素的线性表，应该采取单链表存储结构。 14、非空的循环单链表sq的最后一个结点(由p所指向)满足p-next= =sq 15、非空的循环单链表sq的尾结点(只设尾结点，由p所指向)满足条件sq-next=p; 16、在单链表中，删除*p结点的后继结点的语句是p-next=p-next-next; 17、在一个长度为n(n1)的单链表上，设有头和尾两个指针，在以下操作中，删除单链表中的第一个元素；删除单链表中最后一个元素； 在单链表第一个元素前插入一个新元素；在单链表最后一个元素后插入一个新元素。执行，操作与链表的长度无关。 18、在双链表中，能够从当前结点出发访问到任意结点。如果某链表中的最常用的操作是在最后结点之后插入结点,则采用带头结点的循环双链表存储方式最节省时间。 19、带头结点的循环双链表sq为空的条件是sq-prior = = sq或者sq-next = = sq。四、练习题 4 . 1填 空 题 1、在顺序表中插入或删除一个元素，需要平均移动 元素，具体移动的元素个数与 有关。 答案： n/ 2 或 n - 1 / 2 表长和该元素在表中的位置有关。 2、在单链表中，除了首元结点外，任一结点的存储位置由 指示。 答案： 其直接前驱结点的链域的值3、在单链表中设置头结点的作用是 。10 数据结构习题分析答案： 插入和删除首元素时不必作特殊的处理 4、已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 a在P结点后【前】插入S结点的语句序列是 。 b在表首插入S结点的语句序列是 。 答案： a： Q= P； P = L； while (P-next != Q) P = P-next； S-next = P-next； P-next = S； b： S-next = L； L = S； 5、已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元 结点，试从下列提供的答案中选择合适的语句序列。 a删除P结点的语句序列是 。 b删除尾元结点的语句序列是 。 答案： a： Q = P ； P = L ； while ( P-next!Q ) P = P-next； P-next P-next -next； free（Q）b： while ( P-next-next! = NULL ) P = P-next；Q = P-next；P-next =P-next -next；free（Q）6、可以用 表示树形结构。 答案： 双链表4 . 2 判 断 题4 . 31、若以线性表表示集合并且进行集合的各种运算，最好先对线性表进行排序2、将两个各具有n个结点的有序表合成一个有序表,最少的比较次数为n次 。3、在表长为n的线性表的inselem（L，i，x）插入元素操作中，i的取值范围是 1=inext=NULL。 6、对于一个具有n个结点的单链表,在已知的指针所指结点后面插入一个新的结点的时间复杂度为O(n)，在已知的值为X的结点后面插入一个新的结点的时间复杂度为O(1)。 X7、给定一个具有n个元素的单链表，建立一个有序单链表的时间复杂度为O(n2) 选 择 题1、在一个单链表中，如果删除p所指结点的后续结点，则执行？ （ A ） A p-next=p-next-next; B p=p-next ;p-next=p-next-next; C p-next=p-next; D p=p-next-next;2、在循环双链表的p所指的结点之后插入s所指的结点的操作是？ （ D ）11 第二章 线性表A p-right=s；s-left=p; p-right-left=s; s-right=p-right; B p-right=s；p-right-left=s; s-left=p; s-right=p-right; C s-left=p; s-right=p-right; p-right=s； p-right-left=s; D s-left=p; s-right=p-right; p-right-left=s; p-right=s； 3、带头结点的单链表head为空的判定条件是什么？ （ B ） A head = = NULL B head-next = = NULL C head-next = = head D head != NULL4、非空的循环单链表的head的尾结点（由p所指）满足 （ C ） A p-next = = NULL B p = = NULLC p-next = = head D p = = head5、在一个链队中，假设f和r分别为队首和队尾的指针，则删除一个结点的运算为 （ C ） A r = f - next B r = r - nextC f = f - next D f = r - next6、在一个栈顶指针为HS的链栈中插入一个s所指的结点运算为？ （ C ） A HS- next = s B s - next = HS-next; HS- next = sC s - next = HS; HS=s; D s - next = HS; HS - next =