1/116十万种考研考证电子书、题库视频学习平台圣才电子书第二部分课后习题第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）。
2/116十万种考研考证电子书、题库视频学习平台圣才电子书4．用C／C++语言描述下列算法，并给出算法的时间复杂度。（1）求一个n阶方阵的所有元素之和。（2）对于输入的任意三个整数，将它们按从小到大的顺序输出。（3）对于输入的任意n个整数，输出其中的最大和最小元素。答：（1）算法如下：本算法的时间复杂度为O（n2）。（2）算法如下：本算法的时间复杂度为O（1）。（3）算法如下：
3/116十万种考研考证电子书、题库视频学习平台圣才电子书本算法的时间复杂度为O（n）。5．设n为正整数，给出下列各种算法关于n的时间复杂度。（1）（2）（3）
4/116十万种考研考证电子书、题库视频学习平台圣才电子书答：（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）的时间复杂度。其中，merge（a，i，j，m）用于两个有序子序列a[i．．m]和a[m+l．．j]的合并，是一个非递归函数，它的时间复杂度为O（合并的元素个数）。答：设mergesort（a，0，n-1）的执行次数为T（n），分析得到以下递归关系：O（n）为merge（）所需的时间，设为cn（c为常量）。因此：
数据结构典型例题解析
第2章 线 性 表
典型例题解析
一、选择题
1．线性表是具有n个（n≥0） 的有限序列。
A．表元素 B．字符 C．数据元素 D．数据项
【分析】线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列,通常记为（a1,a2，…，an），其中n为表长，n=0时称为空表.
【答案】C
2．顺序存储结构的优点是 .
A．存储密度大 B．插入运算方便
C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示
【分析】顺序存储结构是采用一组地址连续的存储单元来依次存放数据元素，数据元素的逻辑顺序和物理次序一致。因此,其存储密度大。
【答案】A
3．带头结点的单链表head为空的判断条件是 .
A．head==NULL B．head—〉next==NULL
C．head->next==head D．head!=NULL
【分析】链表为空时，头结点的指针域为空。
【答案】B
4．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用 存储方式最节省运算时间。
A．单链表 B．仅有头指针的单循环链表
C．双链表 D．仅有尾指针的单循环链表
【分析】根据题意要求，该线性表的存储应能够很方便地找到线性表的第一个元素和最后一个元素，A和B都能很方便地通过头指针找到线性表的第一个元素，却要经过所有元素才能找到最后一个元素；选项C双链表若存为双向循环链表，则能很方便地找到线性表的第一个元素和最后一个元素，但存储效率要低些，插入和删除操作也略微复杂；选项D可通过尾指针直接找到线性表的最后一个元素，通过线性表的最后一个元素的循环指针就能很方便地找到第一个元素。
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]的元素进行归并排序：
数据结构第二章线性表1答案
第二部分线性表
一、选择题
1．关于顺序存储的叙述中,哪一条是不正确的( B )
A.存储密度大
B.逻辑上相邻的结点物理上不必邻接
C.可以通过计算直接确定第i个结点的位置
D.插入、删除操作不方便
2．长度为n的单链表连接在长度为m的单链表后的算法的时间复杂度为( C )
A O(n)
B O(1)
C O(m)
D O(m+n)
3．在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是：( A )
A 访问第i个结点（1<=i<=n）和求第i个结点的直接前趋（2<=i<=n）
B 在第i个结点（1<=i<=n）后插入一个新结点
C 删除第i个结点（1<=i<=n）
D 将n个结点从小到大排序
4．一个向量第一个元素的存储地址是100 ，每个元素的长度为2 ，则第5 个元素的地址是：( B )
（A ）110 （ B ）108 （C ）100 （D ）120
5．已知一个顺序存储的线性表，设每个结点需要占m个存储单元，若第一个结点的地址为da，则第i个结点的地址为：( A )
A）da+(i-1)*m B) da+i*m C) da-i*m D) da+(i+1)*m
6．在具有n个结点的单链表中，实现（A ）的操作，其算法的时间复杂度为O(n)。 A）遍历链表和求链表的第i个结点B）在地址为p的结点之后插入一个结点
C）删除开始结点D）删除地址为p的结点的后继结点
7．链表是一种采用（B ）存储结构存储的线性表。
（A ）顺序（B ）链式（ C ）星式（D ）网状
8．线性表若采用链式存储结构时，要求内存中可用存储单元的地址：（D ）（A ）必须是连续的（ B ）部分地址必须是连续的
（C ）一定是不连续的（ D ）连续或不连续都可以
9．线性表Ｌ在（B ）情况下适用于使用链式结构实现。
（Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入
（Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂
