数据结构 课后习题重点解析

1、数据结构数据结构 课后作业讲解课后作业讲解难点剖析难点剖析2013.12.30第一章 绪论 以下数据结构中，哪一个是逻辑结构（ ）？ A顺序表 B. 散列表 C. 有序表 D. 单链表答案：答案：选C解析：解析：A和D是线性表的物理存储实现方式，B也就是哈希表，也是一种物理结构。C是一种逻辑结构，它只规定了表中元素有序排列，而不关心具体的存储方式（连续或离散的）。第一章 绪论答案：答案：选D解析：解析：概念掌握。第一章 绪论 顺序存储表示中数据元素之间的逻辑关系是由（ ）表示的，链接存储表示中数据元素之间的逻辑关系是由（ ）表示的。 A. 指针 B. 逻辑顺序 C. 存储位置 D. 问题上下文

2、答案：答案：第一个选C，第二个选A解析：解析：顺序存储一般使用数组存储，而数据元素的逻辑关系是通过元素在数组中的位置表示的，也就是我们所说的下标，所以第一个空应该选C。第一章 绪论 一个数据结构在计算机中 称为存储结构。 计算机执行下面的语句时，语句s的执行次数为 。 FOR(i=l；i=i;j-) s; 表示(n+3)(n-2)/2解析：解析：外层循环的执行次数为n-2次里层循环的执行次数分别是n、n-1、n-2、4、3次，所以s的执行次数应为(3+n)*(n-2)/2。实际上是一个等差数列求和。当i=1时，里层循环为n次，当i=n-2时，里层循环为3次。第二章 线性表 顺序表是线性表的（

3、）存储表示。 A有序 B连续 C数组 D顺序存取答案：答案：选C解析：解析：顺序表是线性表的物理存储的一种实现方式，其实质就是一个数组。1. 线性表中的元素并不具备有序性，元素之间不存在有序的逻辑关系，所以A不是。2. 顺序表确实在内存中开辟了一个连续的存储空间，但是，仅仅是连续的存储空间，还不能描述线性表的逻辑特征，即： 线性表中的相邻元素具有序偶关系，3. 顺序存取是一种存储方式，而不是存储表示。第二章 线性表 带头结点的双向循环链表L为空表的条件是（ ）。 AL-lLink-rLink= NULL BL-rLink= Link CL-lLink = NULL DL=NULL答案：答案：选

4、B解析：解析：双向循环链表要是空表，那么头结点的右指针应指向自己，形成一个环路。第二章 线性表 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。 A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表答案：答案：选D解析：解析：比较每个选项的插入和删除操作的时间复杂度就可得出最节省时间的数据结构。第二章 线性表 静态链表中指针表示的是（ ）。 A内存地址 B数组下标 C下一元素地址 D左、右孩子地址答案：答案：选B解析：解析：单链表中的指针表示的是下一个元素的地址。在静态链表中，我们通过数组下标确定元素的所在位置。第二

5、章 线性表 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_和_；而又根据指针的连接方式，链表又可分成_和_。单链表多重链表动态链表静态链表第二章 线性表 下面是用c语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用L返回逆置后的链表的头指针，试在空缺处填入适当的语句。 void reverse（linklist &L）p=null； q=L；while（q！=null）(1) ; q-next=p；p=q；(2) ; (3) ; L=L-next; /暂存后继q=L; /待逆置结点L=p; /头指针仍为L第三章 栈和队列答案：答案：第一题选D，第二题选C解

6、析：解析：这两题是栈的混洗一类型的题目。进栈肯定是按照一个给定的顺序，但是通过不同时刻出栈达到混洗目的。第一题中只知道输出序列的第一个元素是i，但是后续元素的输出是不定的，所以选D。第二题中知道输出序列的第一个输出元素是n，而n是最后一个输入元素，那么这意味着，n该输出序列其实是一个逆输入序列，那么第i个元素为n-i+1。第三章 栈和队列 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 6.答案：答案：选B解析：解析：

7、根据循环队列的插入和删除函数，手动执行对应操作，观察rear和front的变化。初始状态： rear=0，front=3；删除一个元素后（即出队）： rear=0，front=4；加入一个元素后（即入队）： rear=1，front=4；加入一个元素后（即入队）： rear=2，front=4；（即为终态）第三章 栈和队列 假设以数组Am存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。 A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m答案：答案：选A解析：解析：循环队列其

8、他操作：队头、队尾指针加1，可用取模(余数)运算实现。队头指针进1: front = (front+1) %maxsize;队尾指针进1: rear = (rear+1) % maxsize;队列初始化：front = rear = 0;队空条件：front = rear;队满条件：(rear+1) % maxsize = front;第三章 栈和队列 消除递归不一定需要使用栈，此说法（ ）。 队列逻辑上是一个下端和上端既能增加又能减少的线性表。（ ）T解析：解析：尾递归算法可以通过迭代算法来消除递归。T第四、五章 字符串、数组和广义表 若串S=“software”，其子串的数目是（ ）。 A

9、8 B37 C36 D9第四、五章 字符串、数组和广义表 设广义表L=（a,b,c），则L的长度和深度分别为（ ）。 A. 1和1 B. 1和3 C. 1和2 D. 2和3答案：答案：选C解析：解析：n ( 0 )个表元素组成的有限序列，记作 LS = (a0, a1, a2, , an-1)LS是表名，ai是表元素，它可以是表 (称为子表)，可以是数据元素(称为原子)。n为表的长度。广义表的深度（广义表中括号的重数）设非空广义表为LS=(a1,a2,an) 其中ai(i=1,2,n)或为原子或为LS的子表。原子的深度为零，空表的深度为1，其它情况下表长为各子表深度最大值加1。第四、五章 字符

10、串、数组和广义表 实现字符串拷贝的函数 strcpy为： void strcpy(char *s , char *t) /*copy t to s*/while ( ) *s+=*t+ 或 (*s+=*t+)!=0第六章 树答案：答案：选A解析：解析：根据满二叉树的计算类比得出结果。第六章 树 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ） Am-n Bm-n-1 Cn+1 D条件不足，无法确定答案：答案：选A解析：解析：森林的对应的二叉树的根加上根的左子树就是第一棵树，那么第一棵树的结点个数即为m-n。第六章 树 某二叉树的前序

11、序列和后序序列正好相反，则该二叉树一定是（）的二叉树。 A空或只有一个结点 B任一结点无左子树 C高度等于其结点数 D任一结点无右子树答案：答案：选C解析解析：前序遍历为根左右，后序遍历为左右根，而要是两者序列逆反，那么意味着每层只有一个节点，前序遍历得到的是从根到叶子节点的顺序输出，而后序遍历得到则是从叶子节点到根的逆序输出。第六章 树 二叉树以后序遍历序列与前序遍历序列反映的同样的信息。（ ）解析：解析：反应的都是树的一种序列化信息。T第六章 树 在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是 。解析：解析：用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，

12、要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s 和t ,则结点i和j在同一层上的条件是log2s=log2t。log2s=log2t第七章 图 若一个有向图的邻接距阵中，主对角线以下的元素均为零,则该图的拓扑有序序列（ ）。 A存在 B不存在答案：答案：选A解析：解析：主对角线以下的元素均为零，说明图中不存在环，所以该图攒在拓扑有序序列。第七章 图 下列关于AOE网的叙述中，不正确的是（ ）。 A关键活动不按期完成就会影响整个工程的完成时间 B任何一个关键活动提前完成，那么整个工程将会提前完成 C所有的关键活动提前完成，那么整个工程将会提前完成 D某些关键活动提前完成，那么整个工程

13、将会提前完成答案：答案：选B解析：解析：并不是任意一个关键活动提前完成就意味着整个工程将会提前完成，比如两个事件有两个关键活动，其中一个提前完成，不能使整个工程提前完成。第七章 图 任何无向图都存在生成树。（ ） 拓扑排序算法把一个无向图中的顶点排成一个有序序列。 （ ） 在AOE图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。 （ ）FFT第九章 查找 既希望较快的查找又便于线性表动态变化的查找方法是 ( ) A顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法查找答案：答案：选C解析：解析：解题关键在于查找方法要适应线性表的动态变化，因而C是最适合的。第九章 查

14、找 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。 A. LL B. LR C. RL D. RR答案：答案：选C解析：解析：要掌握平衡二叉树各种不平衡类型的处理方法。第九章 查找 下面关于哈希(Hash，杂凑)查找的说法正确的是( ) A哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B除留余数法是所有哈希函数中最好的 C不存在特别好与坏的哈希函数，要视情况而定 D若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要 简单的将该元素删去即可答案：答案：选C解析解析：理解哈希的本质：

15、在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。哈希函数的好坏取决于数据本身。第九章 查找 散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。 A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率答案：答案：选D第九章 查找 完全二叉树肯定是平衡二叉树。（ ） Hash表的平均查找长度与处理冲突的方法无关。（ ） 在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。（ ）FFF第九章 查找 己知有序表为(12,18,24,35,47,50,62,83,90,115，134)当用二分法

16、查找90时，需_次查找成功，47时_成功，查100时，需_次才能确定不成功。 动态查找表和静态查找表的重要区别在于前者包含有_和_运算，而后者不包含这两种运算。243插入删除第十章 排序 下列排序算法中，其中（ ）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序答案：答案：选D解析：解析：什么是排序的稳定性：排序方法的稳定性: 如果在对象序列中有两 个对象ri和rj, 它们的排序码 ki = kj , 且在排序之前, 对象ri排在rj前面。如果在排序之后, 对象ri仍在对象rj的前面, 则称这个排序方法是稳定的, 否则称这个排序

17、方法是不稳定的。第十章 排序1. 排序趟数与序列的原始状态有关的排序方法是( )排序法。 A插入 B. 选择 C. 冒泡 D. 快速2. 下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( ) 排序。 A 冒泡 B. 希尔 C. 快速 D. 堆 3. 快速排序方法在（ ）情况下最不利于发挥其长处。 A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据个数为奇数 D. 要排序的数据已基本有序答案答案：1选C、D2选C3选D第十章 排序 直接插入排序用监视哨的作用是 _。 对于7个元素的集合1，2，3，4，5，6，7进行快速排序，具有最小比 较和交换次数的初始排列次序