数据结构习题集及实验指导

数据结构与算法学习指导与习题解析数据结构与算法学习指导与习题解析数据结构与算法学习指导与习题解析第一章绪论1．1内容介绍本章主要讲述了数据结构的基本概念、基本知识和研究方法，数据结构的发展历史，线性表的定义、存储结构、逻辑结构和线性表的顺序存储、串联存储和并联存储的各种实现方式。

1．2重点、难点重点：数组、线性表、树、二叉树、图的存储结构；线性表的应用举例；顺序表的实现。

难点：算法的时间效率，算法的空间效率；树的遍历。

1．3学习方法通过上机实验，理解相关概念及方法，使所学理论知识能够在实践中得到应用。

1．4参考书目《数据结构与算法—— C语言描述》清华大学出版社、《数据结构与算法—— C语言描述》人民邮电出版社、《（第5版）数据结构与算法》浙江大学出版社、《（第2版）数据结构与算法教程》华中科技大学出版社第二章线性表2．1内容介绍本章主要讲述线性表的定义、存储结构、逻辑结构和线性表的顺序存储、串联存储和并联存储的各种实现方式。

同时，还对线性表的特点以及在计算机中的应用进行了介绍。

1．2重点、难点重点：线性表的存储结构、顺序表的实现。

难点：顺序表的实现。

2．3学习方法通过上机实验，理解相关概念及方法，使所学理论知识能够在实践中得到应用。

2．4参考书目《数据结构与算法—— C语言描述》清华大学出版社、《数据结构与算法—— C语言描述》人民邮电出版社、《（第5版）数据结构与算法》浙江大学出版社、《（第2版）数据结构与算法教程》华中科技大学出版社第三章栈和队列3．1内容介绍本章主要讲述栈和队列的定义和应用。

同时介绍栈和队列的优化方法，为线性链表设计提供新思路。

难点：栈和队列的应用。

3．3学习方法通过上机实验，理解相关概念及方法，使所学理论知识能够在实践中得到应用。

3．4参考书目第二章线性表3．1内容介绍本章主要讲述线性表的定义、存储结构、逻辑结构和线性表的顺序存储、串联存储和并联存储的各种实现方式。

数据结构基础及深入及考试复习资料习题及实验参考答案见附录结论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->next==NULLC、head->next=headD、head!=NULL6、不带头结点的单链表head为空的判定条件是（ A ）A、head==NULLB、head->next==NULLC、head->next=headD、head!=NULL7、非空的循环单链表head的尾结点P满足（ C ）A、p->next==NULLB、p==NULLC、p->next==headD、p==head8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（B ）A、O(1)B、O(n)C、O(n2)D、O(nlog2n)9、在一个单链表中，若删除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;10、在一个单链表中，若在p所指结点之后插入s所指结点，则执行（ B ）A、s->next=p;p->next=s;B、s->next=p->next;p->next=s;C、s->next=p->next;p=s;D、p->next=s;s->next=p;11、在一个单链表中，已知q是p的前趋结点，若在q和p之间插入结点s，则执行（C ）A、s->next=p->next;p->next=s;B、p->next=s->next;s->next=p;C、q->next=s;s->next=p;D、p->next=s;s->next=q;12、在线性结构中，第一个结点没有前趋结点，其余每个结点有且只有 1 个前趋结点。

《数据结构与算法》实验指导书一、实验课程教学目的和要求《数据结构与算法》是一门实践性很强的课程，光靠读书和做习题是不能提高实践能力的。

《数据结构与算法》的实验与程序设计语言课程中的实验不同，后者更多的强调语言方面的功能实现，而前者更接近实际，需要同学们自己分析问题，设计模型和算法，再上机调试完成。

《数据结构与算法》的实验的目的主要有两个：1）深化理解书本上的理论知识，将书本的知识变“活”（为已掌握，为已活用）；2）理论和实践相结合，学会将相关的数据结构和算法应用于解决实际问题，培养数据结构的应用能力和软件工程所需要的实践能力。

《数据结构与算法》的实验类型1）验证性实验—主要是验证教材中已有的数据结构和算法。

2）设计性实验—针对具体问题，应用某一个知识点，自己设计数据结构和算法，培养对数据结构的简单运用能力。

3）综合性实验—针对具体问题，应用某几个知识点，自己设计数据结构和算法，培养对数据结构的综合运用能力。

《数据结构与算法》的实验安排《数据结构与算法》实验的一般步骤1）需求分析：要对简单的问题描述进行详细的分析，充分理解问题，明确问题要求做什么，有什么数据，边界条件……。

2）概要设计：针对问题描述中涉及到数据定义抽象数据类型，设计数据结构和算法模型。

本部分不必考虑实现的细节。

3）详细设计：设计具体的存储结构（用C++或C语言）。

此外，还要设计对象或函数间的调用关系及输入输出。

4）上机调试（运行代码，修正语法及逻辑错误）5）结果与总结《数据结构与算法》的实验要求：1）完成实验预习；2）完成并上交实验报告；3）完成电子设计文档预习/实验报告的格式要求：1）实验名称2）实验目的3）实验内容及要求4）概要设计：ADT5）详细设计：C++类或C函数6）调试分析：7）结果与总结实验一: 顺序表的操作一、实验目的：1）掌握线性表的顺序存储结构与算法实现；3）掌握顺序表的逻辑插入方法。

二、实验内容及要求：实现对有序的顺序表L进行保序插入的(C++或C)算法提示：主函数构建n个整数的顺序表L并调用输出函数；调用保序插入函数实现插入操作并调用输出函数输出。

数据结构基础及深入及考试复习资料习题及实验参考答案见附录结论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—>next==NULLC、head->next=headD、head！=NULL6、不带头结点的单链表head为空的判定条件是（ A ）A、head==NULLB、head-〉next==NULLC、head—>next=headD、head！=NULL7、非空的循环单链表head的尾结点P满足（ C ）A、p—>next==NULLB、p==NULLC、p->next==headD、p==head8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( B ）A、O（1)B、O(n）C、O(n2)D、O(nlog2n)9、在一个单链表中,若删除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;10、在一个单链表中，若在p所指结点之后插入s所指结点，则执行( B ）A、s—>next=p；p-〉next=s；B、s—〉next=p—>next;p-〉next=s;C、s->next=p—〉next;p=s;D、p->next=s；s->next=p;11、在一个单链表中,已知q是p的前趋结点，若在q和p之间插入结点s,则执行( C )A、s—>next=p-〉next;p—>next=s；B、p->next=s—>next;s—〉next=p;C、q-〉next=s;s-〉next=p;D、p-〉next=s；s-〉next=q;12、在线性结构中,第一个结点没有前趋结点，其余每个结点有且只有 1 个前趋结点。

数据结构实验指导书实验一线性表[实验目的]1．了解顺序表的结构特点及有关概念，掌握顺序表建立、插入、删除的基本操作算法。

2．了解单链表的结构特点及有关概念，掌握单链表建立、插入、删除的基本操作算法。

[实验内容]1．顺序表的实践。

1)建立4个元素的顺序表list[]={2，3，4，5}，实现顺序表建立的基本操作。

2)在list[]={2，3，4，5}的元素4和5之间插入一个元素9，实现顺序表插入的基本操作。

3)在list[]={2，3，4，9，5}中删除指定位置（i=3）上的元素9，实现顺序表的删除的基本操作。

2．单链表的实践。

1)建立一个包括头结点和3个结点的（4，2，1）的单链表，实现单链表建立的基本操作。

2)在已建好的单链表中的指定位置（x=2）插入一个结点3，实现单链表插入的基本操作。

3)在一个包括头结点和4个结点的（4，2，3，1）的单链表的指定位置删除一个结点，实现单链表删除的基本操作。

[实验要点及说明]线性表（linear list）是n（n≥0）个数据元素a1，a2，…a n组成的有限序列。

其中n 称为数据元素的个数或线性表的长度，当n=0时称为空表，n>0时称为非空表。

通常将非空的线性表记为（a1，a2，…,a n），其中的数据元素a i（1≤i≤n）是一个抽象的符号，a i是第i个数据元素,称i为数据元素a i在线性表中的位置。

其具体含义在不同情况下是不同的，即它的数据类型可以根据具体情况而定，本书中，我们将它的类型设定为elemtype，表示某一种具体的已知数据类型。

顺序表也称为线性表的顺序存储结构。

其存储方式为：在内存中用一组地址连续的存储单元依次存储线性表的数据元素，但该连续存储空间的大小要大于或等于顺序表的长度。

一般让线性表中第一个元素存放在连续存储空间第一个位置，第二个元素紧跟着第一个之后，其余依此类推。

可定义顺序表如下：#define maxnumelemtype list[maxnum];int num=-1;线性表的链式存贮结构，也称为链表。

数据结构习题集第一章绪论1.1数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的关系和运算等的学科。

1.2 算法分析的目的是分析算法的效率以求该进，算法分析的两个主要方面是空间复杂度和时间复杂度。

1.3 计算机算法指的是解决问题的有限运算序列，它必须具备输入、输出和确定性、有穷性和可行性等5个重要特性。

第二章线性表2.32 下面关于线性表的叙述中，错误的是（B）A. 线性表采用顺序存储必须占用一片连续的存储单元B. 线性表采用顺序存储便于进行插入和删除操作C. 线性表采用链式存储不必占用一片连续的存储单元D. 线性表采用链式存储便于进行插入和删除操作第三章栈与队列一、选择题3.1 栈的特点是先进后出，队列的特点是先进先出。

3.4 判定一个栈ST（最多元素MaxSize）为空的条件是ST->top==-1。

3.8 一个队列的入队序列是1，2，3，4，则出队列的输出序列是1，2，3，4。

3．16一个队列的入队序列是1，2，3，4，则队列的输出序列是1,2,3,4。

3.18 若进栈序列为 1，2，3，4，，进栈过程中可以出栈，则以下不可能的出栈序列是3，1，4，23.1 栈和队列的区别仅在于____。

3.2 通常元素进栈的操作是____。

3.3通常元素退栈的操作是____。

3.4一个栈的输入序列是12345，则栈的输出序列43512是____。

3.5一个栈的输入序列是12345，则栈的输出序列12345是____。

第四章串4.1串是一种特殊的线形表，其特殊性体现在___B_A. 可以顺序存储B. 数据元素是一个字符C. 可以链接存储D. 数据元素可以是多个字符4.2 串的两种最基本的存储方式是顺序和链式。

4.3两个串相等的充分必要条件是:长度相等且对应位置上的字符相等。

4.4 空串是____，其长度等于____.4.5 串的三种机内表示方法是________、________、和___________。

《数据结构》实验指导计算机科学与技术教研室2009年2月实验一线性表（2学时）一．目的与要求本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。

要求仔细阅读并理解下列例题，上机通过，并观察其结果，然后独立完成后面的实习题。

二．实验内容[问题描述]用链表形式存储一个字符串，插入、删除某个字符，最后按正序、逆序两种方式输出字符串。

[输入]初始字符串，插入位置，插入字符，删除字符。

[输出]已建立链表（字符串），插入字符后链表，删除字符后链表，逆转后链表。

[存储结构]采用链式存储结构[算法的基本思想]建立链表：当读入字符不是结束符时，给结点分配存储空间，写数据域，将新结点插到表尾；插入字符：根据读入的字符在链表中找插入位置，将新结点插入到该位置之前；删除字符：根据读入的删除字符在链表中找到被删结点后，将其从链表中删除；链表逆转：从链表的第一个结点开始对所有结点处理，将每个结点的前驱变为它的后继；打印链表：从链表的第一个结点开始，依次打印各个结点的数据域。

三．实验要求：在上机后写出全部源程序完毕并完成实验报告,实验报告包括：需求分析、概要设计、详细设计、调试分析、用户使用说明和测试结果。

附加题目：（从中挑选一题）1．设顺序表A中的数据元素递增有序，试写一程序，将x插入到顺序表的适当位置上，使该表仍然有序。

2．用单链表ha 存储多项式A（x ）=a0+a1x1+a2x2+…+a n x n(其中a I为非零系数)，用单链表hb 存储多项式B（x ）=b0+b1x1+b2x2+…+b m x m(其中b j为非零系数)，要求计算C（x ）= A（x ）+B（x ），结果存到单链表hc中。

试写出程序。

3．设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到m的人又出列，如此重复，直到所有的人全部出列为止。

《数据结构》课程实验指导《数据结构》实验教学大纲课程代码：0806523006 开课学期：3 开课专业：信息管理与信息系统总学时/实验学时：64/16 总学分/实验学分：3.5/0.5一、课程简介数据结构是计算机各专业的重要技术基础课。

在计算机科学中，数据结构不仅是一般程序设计的基础，而且是编译原理、操作系统、数据库系统及其它系统程序和大型应用程序开发的重要基础。

数据结构课程主要讨论各种主要数据结构的特点、计算机内的表示方法、处理数据的算法以及对算法性能的分析。

通过对本课程的系统学习使学生掌握各种数据结构的特点、存储表示、运算的原理和方法，学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储机构及其相应的操作算法，并初步掌握时间和空间分析技术。

另一方面，本课程的学习过程也是进行复杂程序设计的训练过程，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。

二、实验的地位、作用和目的数据结构是一门实践性较强的基础课程，本课程实验主要是着眼于原理和应用的结合，通过实验，一方面能使学生学会把书上学到的知识用于解决实际问题，加强培养学生如何根据计算机所处理对象的特点来组织数据存储和编写性能好的操作算法的能力，为以后相关课程的学习和大型软件的开发打下扎实的基础。

另一方面使书上的知识变活，起到深化理解和灵活掌握教学内容的目的。

三、实验方式与基本要求实验方式是上机编写完成实验项目指定功能的程序，并调试、运行，最终得出正确结果。

具体实验要求如下：1.问题分析充分地分析和理解问题本身，弄清要求，包括功能要求、性能要求、设计要求和约束，以及基本数据特性、数据间联系等等。

2.数据结构设计针对要解决的问题，考虑各种可能的数据结构，并且力求从中选出最佳方案（必须连同算法实现一起考虑），确定主要的数据结构和全程变量。

对引入的每种数据结构和全程变量要详细说明其功用、初值和操作的特点。

【关键字】实验数据结构课程实验指导书数据结构课程组编西南交通大学电气工程学院一、实验教学的目的与基本要求实验目的：用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下了厚实的知识基础，同时也提供了必要的技能训练。

因此，数据结构课程在计算机应用中具有举足轻重的作用。

通过实验实践内容的训练，突出学生程序思维训练和动手上机调试程序的能力, 使学生掌握数据结构的基本原理和编程方法，提高学生组织数据及编写程序的能力。

实验要求：1、实验前要预习：实验前必须认真预习相关的知识，做好充分准备。

2、学生进入实验室，要保持室内整洁和安静。

按照指定的内容进行实验。

3、学生在实验前做好预习，写好算法；实验完毕由教师验收合格后方可离开，并写好实验报告。

4、报告内容包括实验目的、实验内容、程序清单和实验结果等。

要求书写文字整齐简洁。

5、实验过程中要注意人身和设备安全，遇到事故或出现异常现象，应立即切断电源，保持现场并报告指导教师处理。

二、实验报告要求、实验考核方式、内容及成绩评定标准实验报告要求内容清晰完整，写出实验结果。

实验考核方式依据实验报告完成情况和实验上机情况综合考核。

根据实验报告和实验课出席情况给出实验成绩,满分10分。

三、实验教材及参考书《数据结构》严蔚敏清华大学出版社 2005实验一熟悉开发环境和抽象数据类型一．实验目的1．熟悉VC软件开发环境。

2．熟悉抽象数据类型的定义与应用。

二．实验内容1.在VC下编写程序，实现求出从键盘输入的两个数的最大值。

例如，从键盘输入a=4,b=5。

得出结果c = 52.在VC下编写程序，实现求出两个复数的和。

定义复数的数据类型，复数由实部和虚部构成。

复数的和是两个复数的实部和虚部分别求和得出。

其中的两个复数分别从键盘输入，例如，输入3, 4表示复数Z1：3+4i; 输入1, 2表示复数Z2：1+2i。

数据结构实验指导书目录实验说明 (3)实验要求 (4)实验1 线性表的顺序存储结构的实现及其应用 (5)实验2 线性表的链式存储结构的实现及其应用 (10)实验3 栈和队列的存储结构的实现 (17)实验4 树和二叉树的存储结构的实现 (26)实验5 图的存储结构的实现 (34)实验6 图的简单应用 (39)实验7 查找算法的实现 (44)实验8 排序算法的实现 (47)上机实验报告（仅供参考） (52)实验说明A．每班学习委员或班长至少在上机实验前一周到软件学院教务室（创新大楼西楼4楼教务室）购买上机实验报告B．上机实验报告封面上要写完整：班级、姓名、指导老师姓名，学期、报告日期等。

C．其它1)本学期上机实验一共16学时，大家需要完成8个实验。

2)上机前写好预习报告（即上机报告中调试分析之前的内容），准备好程序和测试数据。

3)报告要简洁明了，一个实验报告只有3页，书写时字体大小不要太大，以免写不下。

4)请按照指定时间完成上机报告，上机报告于课程结束后上交存档，缺交上机报告达三分之一者取消考试资格。

5)请大家认真完成上机任务及上机报告，严禁抄袭。

有任何问题可以及时跟任课教师联系！6)希望在愉快的环境中完成本学期的学习，请大家积极配合！谢谢！实验要求一、实验步骤⒈问题分析充分地分析和理解问题本身，弄清要求做什么，包括功能要求、性能要求、设计要求和约束以及基本数据特性，数据元素之间的关系等。

⒉数据结构设计针对要求解决的问题，考虑各种可能的数据结构，并且力求从中找出最佳方案(必须连同算法一起考虑)，确定主要的数据结构（可以采用抽象数据类型描述）及全局变量。

对引入的每种数据结构和全局变量要详细说明其功能、初值和操作特点。

⒊算法设计算法设计分概要设计和详细设计。

概要设计着重解决程序的模块设计问题，这包括考虑如何把被开发的问题程序自顶向下分解成若干顺序模块，并决定模块的接口，即模块间的相互关系以及模块之间的信息交换问题。