下载文档原格式
第1章绪论1.选择题（1）C （2）B （3）C （4）D （5）B2.判断题（1）√（2）Ⅹ（3）Ⅹ（4）Ⅹ（5）√3.简答题（1）根据数据元素之间的不同逻辑关系，通常将其划分为哪几类结构？【解答】常见的四种逻辑结构有：①集合结构：数据元素间的关系是“属于同一个集合”。
②线性结构：数据元素之间存在着一对一的关系。
③树型结构：数据元素之间存在着一对多的关系。
④图型结构：数据元素之间存在着多对多的关系。
（2）请描述线性结构中数据元素与数据元素之间的关系特点？【解答】线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。
在线性结构中，有且仅有一个元素被称为“第一个”，除第一个元素之外其他元素均有唯一一个“前驱”；有且仅有一个元素被称为“最后一个”，除最后一个元素之外其他元素均有唯一一个“后继”。
（3）请描述树形结构中数据元素与数据元素之间的关系特点？【解答】树形存储结构，就是数据元素与元素之间存在着一对多关系的数据结构。
在树形存储结构中，树的根节点没有前驱结点，其余的每个节点有且只有一个前驱结点，除叶子结点没有后续节点外，其他节点的后续节点可以有一个或者多个。
（4）常用的存储结构有哪几种，各自的特点是什么？【解答】常见的四种存储结构有：①顺序存储：把逻辑上相邻的元素存储在物理位置相邻的存储单元中。
顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。
②链接存储：对逻辑上相邻的元素不要求不要求物理位置相邻的存储单元，元素间的逻辑关系通过附设的指针域来表示。
③索引存储：通过建立索引表存储结点信息的方法，其中索引表一般存储结点关键字和一个地点信息，可通过该地址找到结点其它信息。
④散列存储：根据结点的关键字直接计算出该结点的存储地址的方法。
（5）简述算法和程序的区别。
【解答】一个算法若用程序设计语言来描述，则它就是一个程序。
算法的含义与程序十分相似，但又有区别。
一个程序不一定满足有穷性。
第4章串1．采用顺序结构存储串，编写一个实现串通配符匹配的算法pattern______index（），其中的通配符只有“？”，它可以和任一字符匹配成功，例如，pattern______index（″? re″，″there are″）返回的结果是2。
答：本题的基础是Brute—Force模式匹配算法，只是增加了“？”的处理功能。
对应的算法如下：2．有两个串s1和s2，设计一个算法求这样一个串，该串中的字符是s1和s2中的公共字符。
答：扫描s1，对于当前字符s1.data[i]，若在s2中，则将其加入到串s3中。
最后返回s3串。
对应的算法如下：3．设目标为t=’abcaabbabcabaacbacba’，模式p=’abcabaa’。
（1）计算模式P的nextval函数值。
（2）不写算法，只画出利用KMP算法进行模式匹配时的每一趟匹配过程。
答：（1）先计算next数组，在此基础上求nextval数组，如表4-1所示。
表4-1 计算next数组和nextval数组（2）采用KMP算法求子串位置的过程如下（开始时i=0，j=0）：第1趟匹配：此时i=4，j=4，匹配失败，而nextval[4]=0，则i=4，j=nextval[4]=0，即：第2趟匹配：此时i=6，j=2，匹配失败，而nextval[2]=0，则i=6，j=nextval[2]=0，即：第3趟匹配：此时i=6，j=0，匹配失败，而nextval[0]=-1，则i=6，j=nextval[0]=-1。
因j=-1，执行i=i+1=7，j=j+1=0，即：第4趟匹配：此时i=14，j=7，匹配成功，返回v=i-t．1ength=14-7=7。
上机实验题4实验题1编写一个程序algo4-1.cpp，实现顺序串的各种基本运算，并在此基础上设计一个程序exp4-1.cpp完成如下功能：（1）建立串s=″abcdefghefghijklmn″和串sl=″xyz″；（2）输出串s；（3）输出串s的长度；（4）在串s的第9个字符位置插入串s1而产生串s2；（5）输出串s2；（6）删除串s第2个字符开始的5个字符而产生串s2；（7）输出串s2；（8）将串s第2个字符开始的5个字符替换成串s1而产生串s2；（9）输出串s2；（10）提取串s的第2个字符开始的10个字符而产生串s3；（11）输出串s3；（12）将串s1和串s2连接起来而产生串s4；（13）输出串s4。
数据结构（第4版）习题及实验参考答案数据结构复习资料完整版（c语言版）数据结构基础及深入及考试习题及实验参考答案见附录结论1、数据的逻辑结构是指数据元素之间的逻辑关系。
即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。
它依赖于计算机。
存储结构可分为4大类：顺序、链式、索引、散列3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。
它由基本的数据类型构成，并包括一组相关的服务（或称操作）。
它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。
4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。
5、在数据结构中，从逻辑上可以把数据结构分成（C）A、动态结构和表态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构6、算法的时间复杂度取决于（A）A、问题的规模B、待处理数据的初态C、问题的规模和待处理数据的初态线性表1、线性表的存储结构包括顺序存储结构和链式存储结构两种。
2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（E），删除一个元素需要移动的元素的个数为（A）。
A、(n-1)/2B、nC、n+1D、n-1E、n/2F、(n+1)/2G、(n-2)/23、“线性表的逻辑顺序与存储顺序总是一致的。
”这个结论是（B）A、正确的B、错误的C、不一定，与具体的结构有关4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（D）A、必须是连续的B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以5、带头结点的单链表为空的判定条件是（B）A、head==NULLB、head->ne某t==NULLC、head->ne某t=headD、head!=NULL6、不带头结点的单链表head为空的判定条件是（A）A、head==NULLB、head->ne某t==NULLC、head->ne某t=headD、head!=NULL7、非空的循环单链表head的尾结点P满足（C）A、p->ne某t==NULLB、p==NULLC、p->ne某t==headD、p==head8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（B）A、O(1)B、O(n)C、O(n2)D、O(nlog2n)数据结构(第4版）习题及实验参考答案9、在一个单链表中，若删除p所指结点的后继结点，则执行（A）A、p->ne某t=p->ne某t->ne某t;B、p=p->ne某t;p->ne某t=p->ne某t->ne某t;C、p->ne某t=p->ne某t;D、p=p->ne某t->ne某t;10、在一个单链表中，若在p所指结点之后插入所指结点，则执行（B）A、->ne某t=p;p->ne某t=;B、->ne某t=p->ne某t;p->ne某t=;C、->ne某t=p->ne某t;p=;D、p->ne某t=;->ne某t=p;11、在一个单链表中，已知q是p的前趋结点，若在q和p之间插入结点，则执行（C）A、->ne某t=p->ne某t;p->ne某t=;B、p->ne某t=->ne某t;->ne某t=p;C、q->ne某t=;->ne某t=p;D、p->ne某t=;->ne某t=q;12、在线性结构中，第一个结点没有前趋结点，其余每个结点有且只有1个前趋结点。
第6章数组和广义表一、选择题1．设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。
A．13B．33C．18D．40【答案】B【解析】对于对称矩阵,a i,j=a j,i。
为了节省存储空间，为多个相同的元素只分配一个存储空间。
对于对称矩阵，元素下表之间的对应关系为：当i>=j时，k=i(i-1)/2+j -1；当i< =j 时，k=j(j-1)/2+i-1。
其中k相当于地址空间的标号，i为行号，j为列号。
因为第一个元素存储地址为1，所以最后计算的k需要加1。
所以a85的存储位置为8*（8-1）/2+5=33。
2．设有数组A[i，j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为（）。
A．BA+141B．BA+180C．BA+222D．BA+225【答案】B【解析】在计算中，可以考虑按照列存放时，A[5,8]在内存的位置，比较容易计算元素的首地址。
比如A[5，8]顺序存放时，它是第7*8+5=61个元素，由于首地址为BA，所以它的存储首地址为BA+（61-1）*3=180+BA。
3．数组通常具有的两种基本操作是（）。
A．查找和修改B．查找和索引C．索引和修改D．建立和删除【答案】A【解析】数组中的元素是顺序存放的，通过下标可以很好地查找数组元素，同时通过对应的指针可以修改数组元素的值，因此数组通常具有的两种基本操作是查找和修改。
根据数组的性质，数组通常具有的两种基本运算是排序和查找。
4．将一个A[1．.100，1．.100]的三对角矩阵，按行优先存入一维数组B[1．.298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（）。
A．198B．195C．197【答案】B【解析】将对角矩阵a[i][j]存入b[k]，三对角矩阵压缩地址计算公式如下：k=2i+j-2。
第二部分课后习题第1章绪论1．简述数据与数据元素的关系与区别。
答：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。
数据元素是数据的基本单位，是数据的个体。
数据与元素之间的关系是元素与集合之间的关系。
2．数据结构和数据类型有什么区别？答：数据结构是互相之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。
而数据类型是一个值的集合和定义在这个集合上的一组运算的总称，如C语言中的int数据类型是由-32768~32767（16位机）的整数和+、-、*、/、%等运算符组成。
3．设3个表示算法频度的函数f、g和h分别为：f（n）=100n3+n2+1000g（n）=25n3+5000n2h（n）=n1.5+5000nlog2n求它们对应的时间复杂度。
答：f（n）=100n3+n2+1000=O（n3），g（n）=25n3+5000n2=O（n3），当n→∞时，√n>log2n，所以h（n）=n1.5+5000nlog2n=O（n1.5）。
4．用C／C++语言描述下列算法，并给出算法的时间复杂度。
（1）求一个n阶方阵的所有元素之和。
（2）对于输入的任意三个整数，将它们按从小到大的顺序输出。
（3）对于输入的任意n个整数，输出其中的最大和最小元素。
答：（1）算法如下：本算法的时间复杂度为O（n2）。
（2）算法如下：本算法的时间复杂度为O（1）。
（3）算法如下：本算法的时间复杂度为O（n）。
5．设n为正整数，给出下列各种算法关于n的时间复杂度。
（1）（2）（3）答：（1）设while循环语句执行次数为T（n），则：（2）算法中的基本运算语句是if（b[k]>b[j]）k=j，其执行次数T（n）为：（3）设while循环语句执行次数为T（n），则：则6．有以下递归算法用于对数组a[i．．j]的元素进行归并排序：求mergesort（a，0，n－1）的时间复杂度。
第1章绪论知识点归纳一、数据结构概述1.数据结构的定义（1）基本概念数据是描述客观事物的数和字符的集合，是计算机能操作的对象的总称，也是计算机处理信息的某种特定的符号表示形式。
（2）相关术语① 数据元素数据元素又称元素、节点、顶点、记录等。
数据元素是数据的基本单位。
有时候，一个数据元素可以由若干个数据项组成。
② 数据项数据项又称字段或域，它是具有独立含义的最小数据单位。
③ 数据对象数据对象是性质相同的数据元素的集合，它是数据的子集。
（3）数据结构的内容① 数据元素之间的逻辑关系，即数据的逻辑结构，它是数据结构在用户面前呈现的形式。
② 数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，又称数据的物理结构。
③ 施加在数据上的操作，即数据的运算。
（4）逻辑结构数据的逻辑结构是从逻辑关系（主要是指数据元素的相邻关系）上描述数据的，它与数据的存储无关，是独立于计算机的。
因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
（5）存储结构数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示（又称映像），也就是逻辑结构在计算机中的存储方式，它是依赖于计算机语言的。
一般只在高级语言（例如C／C++语言）的层次上讨论存储结构。
数据的运算最终需在对应的存储结构上用算法实现。
总之，数据结构是一门讨论“描述现实世界实体的数学模型（通常为非数值计算）及其之上的运算在计算机中如何表示和实现”的学科。
（6）数据结构的表示对于一种数据结构，其逻辑结构总是惟一的，但它可能对应多种存储结构，并且在不同的存储结构中，同一运算的实现过程可能不同。
描述数据结构通常采用二元组表示：B=（D，R）其中，B是一种数据结构，它由数据元素的集合D和D上二元关系的集合R组成，即：D={d i | 1≤i≤n，n≥0}R={r j | 1≤j≤m，m≥0}其中d i表示集合D中的第i个数据元素（或节点），n为D中数据元素的个数，特别地，若n=0，则D 是一个空集。
Java程序设计实用教程（第4版）习题解答与实验指导叶核亚编著2013年11月目录“Java程序设计”课程教学要求 (1)第1章Java概述 (3)第2章Java语言基础 (5)第3章类的封装、继承和多态 (22)第4章接口、内部类和Java API基础 (37)第5章异常处理 (42)第6章图形用户界面 (44)第7章多线程 (49)第8章输入/输出流和文件操作 (51)“Java程序设计”课程教学要求1. 课程性质、目的和任务程序设计是高等学校计算机学科及电子信息学科各专业本科的核心专业基础课程，是培养学生软件设计能力的重要课程。
在计算机学科的本科教学中，起着非常重要的作用。
“Java程序设计”是计算机科学与技术专业本科的专业基础限选课，开设本课程的目的是：进行程序设计和面向对象方法的基础训练；使用Java编程技术，设计解决操作系统、网络通信、数据库等多种实际问题的应用程序。
本课程通过全面、系统地介绍Java语言的基础知识、运行机制、多种编程方法和技术，使学生理解和掌握面向对象的程序设计方法，理解和掌握网络程序的特点和设计方法，建立起牢固扎实的理论基础，培养综合应用程序的设计能力。
本课程的先修课程包括：C/C++程序设计I、C/C++程序设计II、数据结构、操作系统、计算机网络、数据库原理等。
2. 教学基本要求本课程的基本要求如下。
①了解Java语言特点，理解Java Application应用程序的运行原理和方法。
掌握在JDK 环境中编译和运行程序的操作，熟悉在MyEclipse集成开发环境中，编辑、编译、运行和调试程序的操作。
②掌握Java语言中语句、数组、引用类型等基本语法成分的使用方法，通过类、接口、内嵌类型、包、异常处理等机制表达和实现面向对象程序设计思想。
③掌握Java的多种实用技术，包括图形用户界面、多线程、文件操作和流、使用URL 和Socket进行网络通信等。
④熟悉Java JDBC数据库应用的设计方法。
算法与数据结构考研试题精析第4版摘要：一、算法与数据结构的重要性- 算法与数据结构在计算机科学中的地位- 考研对算法与数据结构的要求二、算法与数据结构考研试题精析第4版概述- 书籍简介- 主要内容- 适用人群三、算法与数据结构考研试题精析第4版特点- 试题收集全面- 答案解析详细- 实例丰富四、算法与数据结构考研试题精析第4版使用建议- 如何利用本书进行复习- 注意事项正文：算法与数据结构是计算机科学的基础知识，也是考研的重要内容。
在计算机科学中，算法与数据结构占据着举足轻重的地位，它们是解决各种实际问题的基础。
因此，对于想要参加计算机科学相关专业考研的学生来说，掌握算法与数据结构是必不可少的。
在这样的背景下，《算法与数据结构考研试题精析第4版》应运而生。
这本书收集了大量的考研试题，并对其进行了详细解析，旨在帮助学生更好地掌握算法与数据结构的知识。
本书的主要内容包括各种数据结构（如栈、队列、链表、树、图等）的定义、性质、操作及应用，以及各种算法（如排序、查找、动态规划、贪心算法等）的原理、步骤及应用。
书中还提供了丰富的实例，帮助读者加深理解。
本书适用于参加计算机科学相关专业考研的学生。
通过学习本书，学生可以系统地掌握算法与数据结构的知识，并在考试中取得好成绩。
本书的一个显著特点是试题收集全面。
书中收录了国家统考、985和211重点高校以及科研院所的考研试题，总数超过350套。
此外，本书的答案解析也非常详细，每个试题都提供了详细的解答过程，帮助学生理解和学习。
在使用本书进行复习时，建议学生先通过目录了解本书的主要内容，然后根据自己的需求选择相应的试题进行练习。
在练习过程中，学生应该注重理解算法的原理和数据结构的性质，并学会运用它们解决实际问题。
同时，学生还可以通过本书的实例加深对知识点的理解。
1章答案1.简述数据与数据元素的关系与区别。
解：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。
数据元素是数据的基本单位，是数据的个体。
数据与元素之间的关系是元素与集合之间的关系。
2.数据结构和数据类型有什么区别？解：数据结构是互相之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。
而数据类型是一个值的集合和定义在这个集合上的一组运算的总称，如C语言中的int数据类型是由-32768~32767（16位机）的整数和+、-、*、/、%等运算符组成。
3.设3个表示算法频度的函数f、g和h分别为：f（n）=100n3+n2+1000 g（n）=25n3+5000n2 h（n）=n1.5+5000nlog2n求它们对应的时间复杂度。
解：f（n）=100n3+n2+1000=O（n3），g（n）=25n3+5000n2=O（n3），当n→∞时，√n>log2n，所以h（n）=n1.5+5000nlog2n= O（n1.5）。
4.用C／C++语言描述下列算法，并给出算法的时间复杂度。
（1）求一个n阶方阵的所有元素之和。
（2）对于输入的任意三个整数，将它们按从小到大的顺序输出。
（3）对于输入的任意n个整数，输出其中的最大和最小元素。
解：（1）算法如下：本算法的时间复杂度为O（n2）。
（2）算法如下：本算法的时间复杂度为O（1）。
（3）算法如下：本算法的时间复杂度为O（n）。
5.设n为正整数，给出下列各种算法关于n的时间复杂度。
（1）（2）（3）解：（1）设while循环语句执行次数为T（n），则：（2）算法中的基本运算语句是if（b[k]>b[j]）k=j，其执行次数T（n）为：（3）设while循环语句执行次数为T（n），则：则6.有以下递归算法用于对数组a[i．．j]的元素进行归并排序：求mergesort（a，0，n－1）的时间复杂度。
《数据结构》课程实验指导《数据结构》实验教学大纲课程代码：0806523006 开课学期：3 开课专业：信息管理与信息系统总学时/实验学时：64/16 总学分/实验学分：3.5/0.5一、课程简介数据结构是计算机各专业的重要技术基础课。
在计算机科学中，数据结构不仅是一般程序设计的基础，而且是编译原理、操作系统、数据库系统及其它系统程序和大型应用程序开发的重要基础。
数据结构课程主要讨论各种主要数据结构的特点、计算机内的表示方法、处理数据的算法以及对算法性能的分析。
通过对本课程的系统学习使学生掌握各种数据结构的特点、存储表示、运算的原理和方法，学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储机构及其相应的操作算法，并初步掌握时间和空间分析技术。
另一方面，本课程的学习过程也是进行复杂程序设计的训练过程，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。
二、实验的地位、作用和目的数据结构是一门实践性较强的基础课程，本课程实验主要是着眼于原理和应用的结合，通过实验，一方面能使学生学会把书上学到的知识用于解决实际问题，加强培养学生如何根据计算机所处理对象的特点来组织数据存储和编写性能好的操作算法的能力，为以后相关课程的学习和大型软件的开发打下扎实的基础。
另一方面使书上的知识变活，起到深化理解和灵活掌握教学内容的目的。
三、实验方式与基本要求实验方式是上机编写完成实验项目指定功能的程序，并调试、运行，最终得出正确结果。
具体实验要求如下：1.问题分析充分地分析和理解问题本身，弄清要求，包括功能要求、性能要求、设计要求和约束，以及基本数据特性、数据间联系等等。
2.数据结构设计针对要解决的问题，考虑各种可能的数据结构，并且力求从中选出最佳方案（必须连同算法实现一起考虑），确定主要的数据结构和全程变量。
对引入的每种数据结构和全程变量要详细说明其功用、初值和操作的特点。
第9章查找一、选择题1．若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（）。
A．（n-1）／2B．n／2C．（n+1）／2D．n【答案】C【解析】最快查找一次成功，最慢查找n次成功。
平均查找次数为（1+2+3+…+n）/n，那么ASL=(n+1)/2。
2．在一个有N个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为（）。
A．O（1）B．O（N）C．O（N2）D．O（NlogN）【答案】B【解析】二分查找的时间复杂度为O(logn)。
在一个用N个元素的有序单链表中查找具有给定关键字的结点，因为查找是从头结点开始的，需要使用指针顺序往下查找，因此时间复杂度为0（N）。
3．对线性表进行折半查找时，要求线性表必须（）。
A．以顺序方式存储B．以顺序方式存储，且数据元素有序C．以链接方式存储D．以链接方式存储，且数据元素有序【答案】B【解析】二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。
因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
折半查找方法适用于对以顺序方式存储的有序表的查找，查找效率较高。
4．下列二叉排序树中查找效率最高的是（）。
A．平衡二叉树B．二叉查找树C．没有左子树的二叉排序树D．没有右子树的二叉排序树【答案】A【解析】平衡二叉树的左子树和右子树的深度之差的绝对值不超过1。
这就保证了二叉树的深度是log2n级别的。
二叉查找树或者是一颗空数；或者是具有下列性质的二叉树：①若左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若右子树不空，则右子树上所有结点的值均大于它的根结点的值；③左、右子树也分别为二叉排序树。
B、C、D 三项均不能保证左子树和右子树的深度之差的绝对值不超过1，甚至很大，因此查找效率低。
5．当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（）。
习题11.1选择题。
(1)计算机识别、存储和加工处理的对象统称为。
A．数据B.数据元素C.数据结构D.数据类型(2)数据结构通常是研究数据的及它们之间的联系。
A．存储和逻辑结构B.存储和抽象C.理想和抽象D.理想和逻辑(3)下列不是数据的逻辑结构的是。
A．散列结构 B.线性结构 C.树形结构 D.图状结构(4)数据结构被形式地定义<D,R>，其中D是的有限集，R是___的有限集。
A．算法 B.数据元素C.数据操作 D.逻辑结构(5)组成数据的基本单位是。
A．数据项 B.数据类型 C.数据元素 D.数据变量(6)设数据结构A=(D,R),其中，D={1,2,3,4},R={r},r={<1,2>,<2,3 >,<3,4>,<4,1>},则数据结构A是。
A．线性结构 B.树形结构 C.图状结构 D.集合(7)数据在计算机存储器中表示时，若物理地址与逻辑地址相同并且是连续的，则称为。
A．存储结构B.逻辑结构C．顺序存储结构D.链式存储结构(8)在数据结构的讨论中把数据结构从逻辑上分。
A．内部结构与外部结构B.静态结构与动态结构B．线性结构与非线性结构 D.紧凑结构与非紧凑结构(9)对于一个算法的评价，不包括以下方面的内容。
A.健壮性和可读性B.并行性C.正确性D.时间空间复杂度(10)算法分析的两个方面是。
A．空间复杂性和时间复杂性B.正确性和简明性C．可读性和文档性 D.数据复杂性和程序复杂性1.2填空题(1)数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。
(2)数据结构包括数据的结构和结构。
(3)数据结构从逻辑上划分为3种基本类型，即、和。
(4)数据的物理结构被分为、、和种类型。
(5)一种抽象数据结构类型包括和两个部分。
(6)数据的逻辑结构是指数据的存储结构是指(7)数据结构是指指数数据及其相互之间的当结点之间存在M对N(M:N)的联系时，称这种结构为当结点之间存在1对N(1：N)的联系时，称这种结构为(8)对算法从时间和空间两个方面进行衡量，分别称为分析。
第3章线性结构的扩展1.选择题（1）B （2）A （3）DAB （4）CCC （5）C2.判断题（1）Ⅹ（2）√（3）√（4）√（5）Ⅹ（6）Ⅹ（7）Ⅹ（8）Ⅹ（9）Ⅹ（10）Ⅹ3.简答题1．KMP算法较朴素的模式匹配算法有哪些改进?【解答】KMP算法主要优点是主串指针不回溯。
当主串很大不能一次读入内存且经常发生部分匹配时，KMP 算法的优点更为突出。
2．设字符串S=‘aabaabaabaac'，P=‘aabaac'。
（1）给出S和P的next值和nextval值；（2）若S作主串，P作模式串，试给出利用KMP算法的匹配过程。
【解答】（1）S的next与nextval值分别为012123456789和002002002009，p的next与nextval值分别为012123和002003。
（2）利用BF算法的匹配过程：利用KMP算法的匹配过程：第一趟匹配：aabaabaabaac 第一趟匹配：aabaabaabaacaabaac(i=6,j=6) aabaac(i=6,j=6)第二趟匹配：aabaabaabaac 第二趟匹配：aabaabaabaacaa(i=3,j=2) (aa)baac第三趟匹配：aabaabaabaac 第三趟匹配：aabaabaabaaca(i=3,j=1) (成功) (aa)baac第四趟匹配：aabaabaabaacaabaac(i=9,j=6)第五趟匹配：aabaabaabaacaa(i=6,j=2)第六趟匹配：aabaabaabaaca(i=6,j=1)第七趟匹配：aabaabaabaac(成功) aabaac(i=13,j=7)3．考虑对KMP算法能否再做改进。
【解答】4．说明一维数组与有序表的异同。
【解答】数组：数组是由类型名、标识符和维数组成的符合数据类型，类型名规定了存放在数组中的元素的类型，而维数则指数组中包含的元素个数。
线性表：（亦作有序表）是最基本、最简单、也是最常用的一种数据结构。
第12章文件12.1 复习笔记一、文件的基本概念1．文件概述（1）定义文件是性质相同的记录的集合。
（2）按关键字划分①单关键字文件若文件中的记录只有一个惟一标识记录的主关键字，则称之为单关键字文件；②多关键字文件若文件中的记录除了含有一个主关键字外，还含有若干个次关键字，则称之为多关键字文件。
（3）按是否定长划分①定长文件若文件中各记录含有的信息长度相同，则称这类记录为定长记录，由这种定长记录组成的文件称作定长文件；②不定长文件若文件中各记录含有的信息长度不等，则称作不定长文件。
2．文件的逻辑结构及操作（1）文件的逻辑结构文件中各记录之间存在着逻辑关系，当一个文件的各个记录按照某种次序排列起来时，各记录之间就自然地形成了一种线性关系。
在这种次序下，文件中每个记录最多只有一个直接后继记录和一个直接前驱记录，而文件的第一个记录只有直接后继没有直接前驱，文件的最后一个记录只有直接前驱而没有直接后继。
此时，文件可看成是一种线性结构。
（2）文件操作①检索文件检索就是在文件中查找满足给定条件的记录，它既可以按记录的逻辑号（即记录存入文件时的顺序编号）查找，也可以按关键字查找。
②维护文件维护主要是指对文件进行记录的插入、删除及修改等更新操作。
此外，为提高文件的效率，还要进行再组织操作、文件被破坏后的恢复操作以及文件中数据的安全保护等。
3．文件的存储结构（1）概念文件的存储结构是指文件在外存上的组织方式。
采用不同的组织方式就得到不同的存储结构。
（2）基本的组织方式①顺序组织；②索引组织；③哈希组织；④链组织。
文件组织的各种方式往往是这四种基本方式的结合。
二、顺序文件1．定义顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序跟物理顺序一致的文件。
若顺序文件中的记录按其主关键字有序，则称此顺序文件为顺序有序文件；否则称为顺序无序文件。
2．优点顺序文件的主要优点是连续存取的速度较快，即若文件中第i个记录刚被存取过，而下一个要存取的是第i+1个记录，则这种存取将会很快完成。
目录第一部分预备知识 (1)预备知识 (1)预备知识实验 (2)第二部分基础实验 (4)实验1 线性表的基本操作 (4)实验2 链表的基本操作 (9)实验3 栈的基本操作 (15)实验4 队列的基本操作 (22)实验5 数组的基本操作 (32)实验6 字符串的基本操作 (36)实验7 二叉树的基本操作 (41)实验8 树的遍历和哈夫曼树 (46)实验9 图的基本操作 (53)实验10 排序 (59)实验11 查找 (64)第三部分课程设计实验 (69)实验1 航空客运订票系统 (69)实验2 汉诺塔游戏程序 (75)实验3 全屏幕编辑程序设计 (79)实验4 旅游路线安排模拟系统 (90)实验6 最小生成树kruskal算法 (93)第一部分预备知识预备知识例1．1#include <stdio.h>int sumabc(int a, int b, int c) /* 求三个整数之和*/{ int s;a=b+c;s=a+b+c;return s;}void displayLine(void){ printf(”----------------------\n“);}void main( ){ int x,y, z ,sabc;x=y=z=8;display(); /* 画一条线*/printf(“\n sum=%d”,sumabc(x,y,z)); /* 在输出语句中直接调用函数sumabc( ) */ printf(“\n %6d%6d%6d”,x,y,z);display();/* 画一条线*/x=2; y=4; z=6;sabc =sumabc(x, y, z); /* 在赋值语句中调用函数sumabc( ) */printf(“\n “ sum=%d”, sabc);printf(“\n %6d%6d%6d”,x,y,z);display();/* 画一条线*/}例1.2int sumabc(int *a, int b, int c){int s;*a=b+c;s=*a+b+c;return s;}预备知识实验int main(){ //在main函数中调用上述声明的函数int n; //记录个数STUDENT stu[MAXSIZE;// 顺序存储结构，方法一静态一维数组。
第12章文件一、选择题1．哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（）方法是哈希文件的关键。
A．哈希函数B．除余法中的质数C．冲突处理D．哈希函数和冲突处理【答案】D【解析】哈希表是根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上。
2．下述文件中适合于磁带存储的是（）。
A．顺序文件B．索引文件C．哈希文件D．多关键字文件【答案】A【解析】磁带存储是一种顺序存储，顺序文件(sequential file)是记录按其在文件中的逻辑顺序依次进入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。
因此顺序文件适合磁带存储。
二、判断题1．倒排文件是对次关键字建立索引。
（）【答案】√【解析】倒排文件是对每一个次关键字项建立次关键字索引(称为倒排表)，将所有具有相同次关键字的记录的物理记录号都填入倒排表为此次关键字的表中。
2．倒排序文件的优点是维护简单。
（）【答案】×【解析】倒排文件的优点是检索记录较快。
特别是对某些询问，不用读取记录，就可得到解答。
3．哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。
（）【答案】×【解析】哈希文件是使用一个函数（算法）来完成一种将关键字映射到存储器地址的映射，根据用户给出的关键字，经函数计算得到目标地址，再进行目标的检索。
哈希表是根据关键码值而直接进行访问的数据结构。
4．文件系统采用索引结构是为了节省存储空间。
（）【答案】×【解析】是为了缩短查找的时间，牺牲了一部分存储空间。
5．对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。
（）【答案】×【解析】索引顺序存取方法插入操作比较麻烦，对于处理大量数据，会有大量的记录进入溢出区，而基本区中又浪费很多空间。
6．对磁带机而言，ISAM是一种方便的文件组织方法。
第10章课程设计10.4 课程设计选题课程设计的目的、要求和选题详见教材10.4节，及课程设计任务书。
10.4.1 线性表1. 多项式的表示和运算题意详见教材2.4节。
（1）使用排序单链表存储多项式10-1 ✩一元多项式相加，PolySinglyList<T>多项式排序单链表类增加以下成员方法，public权限。
//多项式相加，返回this＋list的多项式，不改变this和list，C(x)=A(x)＋B(x)。
//算法不调用深拷贝，将this（A）和list（B）中的所有结点合并（相加）到C多项式单链表PolySinglyList<T> union(PolySinglyList<T> list)10-2 ✩二元多项式相加，实现10-1题。
10-3 ✩一元多项式相乘，Polynomial多项式类增加以下成员方法。
public boolean equals(Object obj) //比较两个多项式是否相等，覆盖public Polynomial multi(Polynomial poly) //相乘，返回this*poly的多项式10-4 ✩二元多项式相乘，实现10-3题。
（2）使用排序循环双链表存储多项式10-5 ✩一元多项式相加，声明PolyDoublyList<T>多项式排序循环双链表类，继承排序循环双链表类，方法声明如下。
Polynomial多项式类使用PolyDoublyList<T>对象作为成员变量。
PolyDoublyList<T> union(PolyDoublyList<T> list) //返回相加的多项式，不调用深拷贝10-6 ✩二元多项式相加，实现10-5题。
10-7 ✩一元多项式相乘，声明PolyDoublyList<T>多项式排序循环双链表类，继承排序循环双链表类，实现二元多项式相乘运算，方法声明如下。
Polynomial多项式类使用PolyDoublyList<T>对象作为成员变量。
Polynomial multi(Polynomial poly) //返回相乘的多项式10-8 ✩二元多项式相乘，实现10-7题。
10.4.2 栈和队列及递归算法1. 计算表达式值在例4.2、例4.6计算算术表达式值的基础上，增加以下功能。
⑴检查表达式语法是否正确。
⑵使用散列映射存储运算符集合，建立从运算符到优先级的映射，快速查找指定运算符的优先级。
运算符集合包括位运算符、关系运算符、逻辑运算符、字符串连接运算符等，各运算符的优先级见附录D。
⑶整数表达式增加位运算功能。
⑷计算逻辑表达式、字符表达式、字符串表达式等，BNF定义见教材实验4-12。
⑸以浮点数作为常数，所求算术表达式值为浮点数类型。
⑹增加标识符作为变量，识别标识符，为变量赋值。
使用散列映射存储变量集合，快速查找指定变量的值。
⑺采用文件保存多行表达式字符串，读取表达式，并将结果写入文件。
10-9 ✩✩计算表达式值。
改进例4.2，同时使用运算符栈和操作数栈，省略转换成后缀表达式过程；增加运算符、浮点数等功能。
10-10 ✩✩✩计算表达式值，递归算法。
改进例4.6，增加运算符、浮点数等功能。
10-11 ✩✩✩✩✩带变量的表达式求值，使用栈，增加运算符、浮点数等功能。
10-12 ✩✩✩✩✩带变量的表达式求值，递归算法，增加运算符、浮点数等功能。
10-13 ✩✩给定一个初始序列，求解素数环问题（例4.3）的所有解，采用回溯法（10.3.4节）。
2. 走迷宫迷宫题见实验4-13，指定迷宫大小、入口及出口位置和初始状态等，求解一条或多条路径，演示走迷宫过程，显示一条或多条结果路径。
10-14 ✩✩走迷宫，使用栈。
10-15 ✩✩走迷宫，使用队列。
10-16 ✩✩走迷宫，递归算法。
10-17 ✩✩走迷宫求所有路径，采用回溯法（10.3.4节）。
10-18 ✩✩骑士游历问题（见实验题4-18）求多个解，采用回溯法（10.3.4节）。
10.4.3 矩阵和广义表1. 稀疏矩阵的压缩存储及运算以下各题实现深拷贝、矩阵相加（addAll()和union()见实验题5-3）、转置等矩阵运算。
（1）稀疏矩阵三元组行的排序单/双链表10-19 ✩设LinkedMatrix矩阵类采用行的排序单链表存储（见实验题5-4）。
10-20 ✩✩设LinkedMatrix矩阵类采用行的多项式排序单链表PolySinglyList<Triple>（见2.4节）存储。
10-21 ✩设LinkedMatrix矩阵类采用行的排序循环双链表存储。
10-22 ✩✩设LinkedMatrix矩阵类采用行的多项式排序循环双链表存储。
（2）稀疏矩阵三元组列的排序单/双链表10-23 ✩设LinkedMatrix矩阵类采用列的排序单链表存储（见实验题5-4）。
10-24 ✩✩设LinkedMatrix矩阵类采用列的多项式排序单链表PolySinglyList<Triple>（见2.4节）存储。
10-25 ✩设LinkedMatrix矩阵类采用列的排序循环双链表存储。
10-26 ✩✩设LinkedMatrix矩阵类采用列的多项式排序循环双链表存储。
（3）稀疏矩阵三元组十字链表以下各题实现深拷贝、矩阵相加（addAll()和union()见实验题5-3）、比较相等、转置等矩阵运算。
10-27 ✩✩✩设CrossLinkedMatrix矩阵类采用十字单链表存储，见图5.13。
10-28 ✩✩✩✩设CrossLinkedMatrix矩阵类采用十字双链表存储，改进图5.13，每个结点增加指向行列前驱的指针。
2. 广义表10-29 ✩✩✩声明以双链表示的广义表类GenList，实现广义表的遍历、插入、删除、查找原子、比较相等、复制等操作。
10-30 ✩✩✩以广义表双链表示实现m元多项式的相加、相乘等运算。
10.4.4 二叉树和树1. 二叉树（二叉链表存储结构）（1）二叉树的成员方法，递归算法已知BinaryTree<T>二叉树类采用二叉链表存储结构，增加以下成员方法，public权限。
10-31 ✩以先根和中根序列构造二叉树，替换其中所有与pattern匹配的子树。
成员方法声明如下：BinaryTree(T prelist[], T inlist[]) //以先根和中根序列构造二叉树void replaceAll(BinaryTree<T> pattern, BinaryTree<T> bitree) //替换所有与pattern匹配子树（深拷贝）10-32 以中根和后根序列构造二叉树，替换其中所有与pattern匹配的子树。
方法声明如下：BinaryTree(T inlist[], T postlist[]) //以中根和后根序列构造二叉树（2）二叉树的成员方法，使用栈的非递归算法10-33 ✩以先根和中根序列构造二叉树（使用栈的非递归算法），替换其中所有与pattern匹配的子树。
10-34 ✩以中根和后根序列构造二叉树（使用栈的非递归算法），替换其中所有与pattern匹配的子树。
（3）对二叉树操作的静态方法，递归算法10-35 ✩以中根和后根序列构造二叉树，求二叉树中两结点最近的共同祖先结点。
方法声明如下：T ancestor(BinaryTree<T> bitree, T x, T y) //返回x、y结点最近的共同祖先结点10-36 ✩以中根和后根序列构造二叉树，求一棵二叉树的所有直径及其路径长度。
方法声明如下：void diameterAll(BinaryTree<T> bitree) //输出二叉树的所有直径及其路径长度10-37 ✩✩以中根和后根序列构造一棵二叉树，以层次序列构造一棵完全二叉树，调用以下方法：boolean isComplete(BinaryTree<T> bitree) //判断是否为完全二叉树（4）对二叉树操作的静态方法，使用栈的非递归算法（5）表达式二叉树表达式二叉树类ExpressionBinaryTree（见例6.3）声明以下方法。
10-38 ✩✩✩ void createByPostfix(String postfix) //以后缀表达式构造表达式二叉树10-39 ✩✩✩ void inorder() //输出带括号的中缀表达式，算法必须比较运算符优先级的大小其中，使用散列映射存储运算符集合，快速查找指定运算符的优先级，Java运算符及其优先级见附录D。
（6）二叉树的其他应用10-40 ✩存储淘汰赛的比赛信息，创建表示比赛过程的满二叉树（教材图1.2），保存比赛结果。
2. 二叉树（三叉链表存储结构）（1）二叉树的成员方法，不使用栈的非递归算法10-41 ✩✩BinaryTree(T prelist[])以标明空子树的先根序列构造二叉树（不使用栈的非递归算法），替换所有与pattern匹配的子树。
10-42 ✩✩✩BinaryTree(BinaryTree<T> bitree)深拷贝，不使用栈的非递归算法。
10-43 ✩✩✩以中根和后根序列构造二叉树，printGenList()输出二叉树的广义表表示（不使用栈的非递归算法）。
（2）对二叉树操作的静态方法，不使用栈的非递归算法10-44 ✩以中根和后根序列构造二叉树，求二叉树中两结点最近的共同祖先结点。
10-45 ✩以中根和后根序列构造二叉树，求二叉树的所有直径及其路径长度（不使用栈的非递归算法）。
10-46 ✩✩✩✩BinaryTree<String> createByGenList(String genlist) //以广义表表示字符串构造二叉树（3）表达式二叉树10-47 ✩✩✩ createByPostfix(String postfix) //以后缀表达式构造表达式二叉树10-48 ✩✩✩ inorder() //输出带括号的中缀表达式，使用散列映射存储运算符集合3. 线索二叉树以下对中序线索二叉树操作的算法描述见习题解答6.3节。
10-49 ✩ ThreadNode<T> parent(ThreadNode<T> node) //返回node结点的父母结点10-50 ✩插入根，插入左/右孩子操作，方法声明如下。
void add(T x) //插入x作为根结点，原根作为x的左孩子ThreadNode<T> add(ThreadNode<T> p, T x, boolean leftChild) //插入x作为p的左/右孩子结点10-51 ✩✩删除根，删除指定结点的左孩子结点，2度结点用删除结点的左孩子顶替，方法声明如下。
