下载文档原格式
最新版《数据结构》各章习题及答案第一章绪论一、选择题1.组成数据的基本单位是（）（A）数据项（B）数据类型（C）数据元素（D）数据变量2.数据结构是研究数据的（）以及它们之间的相互关系。
（A）理想结构，物理结构（B）理想结构，抽象结构（C）物理结构，逻辑结构（D）抽象结构，逻辑结构3.在数据结构中，从逻辑上可以把数据结构分成（）（A）动态结构和静态结构（B）紧凑结构和非紧凑结构（C）线性结构和非线性结构（D）内部结构和外部结构4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。
① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像② （A）结构（B）关系（C）运算（D）算法5.算法分析的目的是（）。
（A）找出数据结构的合理性（B）研究算法中的输入和输出的关系（C）分析算法的效率以求改进（D）分析算法的易懂性和文档性6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5 个特性。
① （A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法② （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性（C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性二、判断题1.数据的机内表示称为数据的存储结构。
（）2.算法就是程序。
（）3.数据元素是数据的最小单位。
（）4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。
（）5.算法的时间复杂度取决于问题的规模和待处理数据的初态。
（）三、填空题1.数据逻辑结构包括________、________、_________ 和__________ 四种类型,其中树形结构和图形结构合称为_____ 。
2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______ 个前驱结点；最后一个结点______后续结点,其余每个结点有且只有 _______ 个后续结点。
3.在树形结构中,树根结点没有_______ 结点,其余每个结点有且只有_______个前驱结点；叶子结点没有 ________ 结点,其余每个结点的后续结点可以_________。
数据结构作业题及答案第一章绪论1、简述下列概念：数据、数据元素、数据结构、逻辑结构、存储结构、线性结构、非线性结构。
数据：指能够被计算机识别、存储和加工处理的信息载体。
数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。
数据元素有时可以由若干数据项组成。
数据结构：指的是数据之间的相互关系，即数据的组织形式。
一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。
逻辑结构：指各数据元素之间的逻辑关系。
存储结构：就是数据的逻辑结构用计算机语言的实现。
线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。
线性表就是一个典型的线性结构。
非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。
2、常用的存储表示方法有哪几种?顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。
由此得到的存储表示称为顺序存储结构。
链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。
由此得到的存储表示称为链式存储结构。
索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。
散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。
3、求解下列算法的时间复杂度(1)i=1;k=0 while(i<n){k=k+10*i;i++;}T(n)=n-1∴T(n)=O(n)这个函数是按线性阶递增的(2)i=0;k=0;do{k=k+10*i;i++;} while(i<n);T(n)=n∴T(n)=O(n)这也是线性阶递增的(3)i=1;j=0;while(i+j<=n) {if(i<j)j++; else i++;}T(n)=n/2∴T(n)=O(n)虽然时间函数是n/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.数据元素是数据的最小单元。
答案：错误2.一个数据结构是由一个逻辑结构和这个逻辑结构上的基本运算集构成的整体。
答案：错误3.数据的存储结构是数据元素之间的逻辑关系和逻辑结构在计算机存储器内的映像。
答案：正确4.数据的逻辑结构是描述元素之间的逻辑关系，它是依赖于计算机的。
答案：错误5.用语句频度来表示算法的时间复杂度的最大好处是可以独立于计算机的软硬件，分析算法的时间答案：正确（第二章线性表）6.取顺序存储线性表的第i个元素的时间同i的大小有关。
答案：错误7.线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。
答案：正确8.线性链表的每一个节点都恰好包含一个指针域。
答案：错误9.顺序存储方式的优点的存储密度大，插入和删除效率不如练市存储方式好。
答案：正确10.插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。
答案：错误（第三章栈）11.栈是一种对进栈和出栈作了限制的线性表。
答案：错误12.在C（或C++）语言中设顺序栈的长度为MAXLEN，则top=MAXLEN表示栈满。
答案：错误13.链栈与顺序栈相比，其特点之一是通常不会出现满栈的情况。
答案：正确14.空栈就是所有元素都为0上的栈。
答案：错误15.将十进制数转换为二进制数是栈的典型应用之一。
答案：正确（第四章队列）16.队列式限制在两端进行操作的线性表。
答案：正确17.判断顺序队列为空的标准是头指针和尾指针都指向同一结点。
答案：错误18.在循环链列队中无溢出现像。
答案：错误19.在循环队列中，若尾指针rear大于头指针front，则元素个数为rear-front。
答案：正确20.顺序队列和循环队列关于队满和队空的判断条件是一样的。
答案：错误（第五章串）21.串是n个字母的有限序列。
答案：错误22.串的堆分配存储是一种动态存储结构。
答案：正确23.串的长度是指串中不同字符的个数。
第一章绪论一、选择题1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。
1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像2 A.结构 B.关系 C.运算 D.算法2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。
1 A.算法 B.数据元素 C.数据操作 D.逻辑结构2 A.操作 B.映像 C.存储 D.关系3.在数据结构中，从逻辑上可以把数据结构分成。
A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。
A.随机存取 B.顺序存取 C.索引存取 D.散列存取5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。
1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系C.可读性和文档性D.数据复杂性和程序复杂性k6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。
1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。
A.正确 B.不正确8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。
A.必须连续的B.部分地址必须连续的C.一定是不续的D连续不连续都可以9.以下的叙述中，正确的是。
A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。
数据结构试题第一章绪论一、选择题：1、在数据结构中，从逻辑上可以把数据结构分成（）。
A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构2、算法分析的两个主要方面是（）。
A、空间复杂性和时间复杂性B、正确性和简明性C、可读性和文档性D、数据复杂性和程序复杂性3、以下与数据的存储结构无关的术语是（）。
A、循环队列B、链表C、哈希表D、栈4、以下数据结构中，哪一个是线性结构（）。
A．广义表B、二叉树C、稀疏矩阵D、串5、在下面的程序段中，对x的赋值语句的频度为（）。
FOR i:=1TO n DOFOR j:=1TO n DOx:=x+1;n)A、O(2n)B、O(n)C、O(n2)D、O(log26、以下哪个数据结构不是多型数据类型（）。
A、栈B、广义表C、有向图D、字符串7、以下数据结构中，（）是非线性数据结构。
A、树B、字符串C、队D、栈8、以下属于逻辑结构的是（）。
A、顺序表 B.哈希表C、有序表D、单链表9、下列程序段的时间复杂度为（）。
s=0；for(i=1；i<n；i++)for(j=1；j<n；j++)s+=ij；A、O(1)B、O(n)C、O(2n)D、O(n2)10、数据结构是（）。
A、一种数据类型B、相互之间存在一种或多种特定关系的数据元素的集合C、一组性质相同的数据元素的集合D、数据的存储结构11、算法分析的目的是（）。
A、辨别数据结构的合理性B、评价算法的效率C、研究算法中输入与输出的关系D、鉴别算法的可读性12、下面程序段的时间复杂度为（）。
for(int i=0;i<m;i++)for(int j=0;j<n;j++)a[i][j]=ij;A、O(m2)B、O(n2)C、O(mn)D、O(m+n)13、执行下面程序段时，执行S语句的次数为（）。
for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)S;A、n2B、n2/2C、n(n+1)D、n(n+1)/214、算法的可读性是指（）。
数据结构知识整理（部分）第一章：绪论1．数据：数据是外部信息的载体，他能够被计算机识别、存储和加工处理，是计算机程序加工的原料；2．数据元素：数据元素是数据的基本单位，在计算机中通常被作为一个整体进行考虑和处理；3．一个数据元素可由若干个数据项组成。
数据项是不可分割的、含有独立意义的最小数据单位，数据项有时也称为字段或域；4．数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。
在任何问题中，数据元素之间都不是孤立的，而是存在着一定的关系，这种关系称为结构；5．4种基本数据结构：集合：只有“同属一个集合”的关系；线性结构：存在着一对一的关系；树形结构：存在着一对多的关系；图状结构：存在着多对多的关系；6．数据结构包括数据的逻辑结构和物理结构。
逻辑结构：从具体问题抽象出来的数学模型，与数据在计算机中的具体储存没有关系。
从逻辑上可以把数据结构分为线性结构和非线性结构，其中集合、树、图形结构属于非线性结构；7．数据的物理结构又叫存储结构，是数据在计算机中的表示和存储，包括数据元素的表示和存储以及数据元素之间关系的表示和存储，存储结构必须依赖于计算机。
数据元素之间的关系在计算机中的表示有两种:顺序映像和非顺序映像。
分别对应两和数据的存储结构：顺序存储结构和链式存储结构；顺序存储结构是指把逻辑上相邻的数据元素存储在物理位置相邻的存储单元中；链式存储结构不要求必须相邻。
链式存储结构中的数据元素叫做结点，在结点中附近设地址域来存储与该结点相邻的结点的地址来实现结点之间逻辑关系；8．在软件设计中，抽象数据类型通常包括定义、表示和实现三部分9．算法：是指在有限的时间范围之内为解决某一问题而采取的方法和步骤的准确完整的描述，他是一个有穷的规则序列，这些规则决定了解决某一特定问题的一系列运算；10算法的特征：有穷性，确定性，可行性，输入，输出；算法+数据结构=程序；11．评价一个算法的主要标准：正确性，可读性，健壮性，运行时间，占用空间；健壮性要求算法要全面细致的考虑所有可能出现的边界情况和异常情况；实际上，算法的时间效率和空间效率经常是一对矛盾，相互抵触，我们要根据实际问题进行处理，有时要牺牲空间换取时间，有时要牺牲时间换取空间。
数据结构（ C语言版）（第 2版）课后习题答案李冬梅2015.3目录第 1 章绪论 (1)第 2 章线性表 (5)第 3 章栈和队列 (13)第 4 章串、数组和广义表 (26)第 5 章树和二叉树 (33)第 6 章图 (43)第 7 章查找 (54)第 8 章排序 (65)第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。
如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
在有些情况下，数据元素也称为元素、结点、记录等。
数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。
数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。
例如，学生基本信息表中的学号、姓名、性别等都是数据项。
数据对象：是性质相同的数据元素的集合，是数据的一个子集。
例如：整数数据对象是集合N={0 ，± 1，± 2，, } ，字母字符数据对象是集合C={‘A’，‘B’， , ，‘Z’，‘ a’，‘ b’， , ，‘z ’} ，学生基本信息表也可是一个数据对象。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。
逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
存储结构：数据对象在计算机中的存储表示，也称为物理结构。
抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。
具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。
