实用数据结构基础（第四版）课后习题.doc

实用数据构造根底〔第四版〕课后习题 - 教育文库 一、判断题 〔第一章 绪论〕 1.数据元素是数据的最小单元 答案：错误 2. 一个数据构造是由一个逻辑构造和这个逻辑构造上的根本运算集构成的整体 答案：错误 3. 数据的存储构造是数据元素之间的逻辑关系和逻辑构造在计算机存储器内的映像 答案：正确 4. 数据的逻辑构造是描绘元素之间的逻辑关系，它是依赖于计算机的 答案：错误 5.用语句频度来表示算法的时间复杂度的最大好处是可以独立于计算机的软硬件，分析^p 算 法的时间 答案：正确 〔第二章 线性表〕 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.串的长度是指串中不同字符的个数 答案：错误 24.如贵一个串中所有的字母均在另一个串中出现，那么说明前者是后者的子串 答案：错误 25.在链串中为了进步存储密度，应该增大结点的大小。

答案：正确 〔第六章 对维数组和广义表〕 26. n维的多维数组可以视为n-1维数组元素组成的线性构造 答案：正确 27.上三角矩阵对主角线以上〔不包括对主角线中的元素〕，均为常数C 答案：错误 28.数组的三元组表存储时对稀疏矩阵的压缩存储 答案：正确 29.广义表Ls=〔a0，a1，......an-1〕，那么an-1是其表尾 答案：错误 30.广义表〔〔a,b〕，a,b〕的表头和表尾是相等的 答案：错误 〔第七章 树和二叉树〕 31.在完全二叉树中，假设一个结点没有左孩子，那么它必然是叶子节点 答案：正确 32.含多于两棵树的森林转换到二叉树，其根节点一定无右子树 答案：错误 33.二叉树的前序遍历中，任意一个节点均处于其子女节点的前面 答案：正确 34.在中序线索二叉树中，右线索假设不为空，那么一定指向其双亲 答案：错误 35.在哈夫曼编码中，当两个字符出现的频率一样的，其他编码也一样，对于这种情况应该做特殊处理 答案：错误 〔第八章 图〕 36.在无相图中，〔v1,v2〕与〔v2,v1〕是两条不同的边 答案：错误 37.图可以没有边，但不能没有顶点。

答案：正确 38.假设一个无向图以顶点v1为起点，进展深度优先遍历，所得的遍历序列唯一，那么可以唯一确定该图 答案：错误 39.用邻接矩阵法存储一个图时，所占用的存储空间大小与图中的顶点个数无关，而只与图的边数有关 答案：错误 40.存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角〔或下三角〕局部就可以了 答案：正确 〔第九章 查找〕 41.在有序的顺序表和有序的链表上，均可以采用二分查找法来进步查找速度 答案：错误 42.在二叉排序树中，根节点的这都小于孩子节点的值 答案：错误 43.选择好的哈希函数就可以防止冲突的发生 答案：错误 44.散列存储法的根本思想是由关键字的值决定数据存储地址 答案：正确 45.在二叉排序树上删除一个节点时，不必挪动其他节点，只要将该节点的父节点的相应指针域置空即可 答案：错误 〔第十章 排序〕 46.假如某种排序算法不稳定，那么该排序方法就没有使用价值 答案：错误 47.希尔排序是不稳定的排序 答案：正确 48.对排序所需的时间与待排序的记录个数无关 答案：错误 49.快速排序在任何情况下都比其他排序方法速度快。

答案：错误 50.采用归并排序可以实现外排序 答案：错误 二、填空题 〔第一章 绪论〕 1. 数据结果是一门研究非数值计算的程序设计问题中计算机的___数据元素___，以及它们之间关系和运算的学科 2. 数据有逻辑构造和 __存储构造__两种构造 3. 数据逻辑构造除了集合以外的还包括线性构造，树形构造和__图形构造__ 4. 数据构造按逻辑构造可分为两大类，分别是线性构造和__非线性构造__ 5. 图形构造和__树形构造__合称为非线性构造 6. 在树形构造中，除了树根节点以外，其余每个节点都只有__1__个前驱结点 7. 在图形构造中，每一个节点的前驱节点上数和后继节点数可以__互换__ 8. 数据的存储构造，又叫做数据的__物理构造__ 9. 数据的存储构造形式，包括顺序存储，链式存储索引存储和__散列存储__ 10. 树形构造中的元素之间存在__1对多__的关系 11. 图形构造的元素之间存在__多对多__的关系 12. 数据构造主要研究数据的逻辑构造，存储构造和__算法__三方面的内容 13. 数据构造被定义为(D,R),D是数据的有限集合，R是D上的__逻辑关系__的有限集合 14. 算法是对特定问题__解决步骤__的描绘。

15. 算法效率的度量可以分为事先估算和__事后统计__ 16. 一个算法的时间复杂度是算法__数据规模__的函数 17. 算法的空间复杂度是指该算法所消耗的__存储空间__，他是该算法求解问题规模n的函数 18. 假设一个算法中，还有10万条根本语句，但有问题的规模无关，那么该算法的时间复杂度为__O(1)__ 19. 假设一个算法中的语句频度之和为T(n)=6n+3nlog2n，那么算法的时间复杂度为__O(n)__ 20. 假设一个算法中的语句频度之和为T(n)=3n+nlog2n+n2，那么算法的时间复杂度为__O(n2)__ 〔第二章 线性表〕 1.性表中，数据的长度定义为__表长__ 2.顺序表中逻辑上相邻的元素在物理位置上__一定__相邻 3.顺序表相对于链表的优点是__密度大__和随机存取 4.某线性表采用顺序存储构造，每个元素占据4个存储单元，首地址为100那么下标为11的(第12个元素)存储地址为__144__ 5.当线性表中的元素总数根本稳定，且很少进展插入和删除操作，但要求以最快的速度存取现象表中的元素时，应采用__顺序__存储构造 6.顺序表中访问任意一个结点的时间复杂度均为__O(1)__。

7.在一个长度为n的顺序表中删除第i个元素要挪动__n-i__个元素 8.在一个长度为n的顺序表中，假如要在第二个元素前插入一个元素要后移__n-i+1__个元素 9.线性表L=(a1,a2,......,an)用数组表示假定删除表中任意元素的概率一样，那么删除一个元素平均需要挪动元素的个数是__n/2__ 10.性表的链式存储中元素之间的逻辑关系是通过__指针__决定的 11.在双向链表中每个节点都有两个指针域他们一个指向其__前驱__结点，另一个指向其后继结点 12.线性表的元素总数不确定，且经常需要进展插入和删除操作，应采用__链式__存储构造 13.在单向链表中，需要知道__表头指针__才能遍历整个链表 14.在单向链表中，要在的节点*p之前插入一个新节点，需找到*p的直接前驱结点的地址，其查找的时间复杂度为__O(n)__ 15.单向循环链表的最大优点是__从任意节点出发__可以访问到链表中每一个元素 16.在双向链表中要删除节点*p，其实间复杂度为__O(n)__ 17.带头节点的双循环链表L中判断只有一个元素节点的条件是__L->next->next==L(L->front->front==L)__。

18.对于双向链表，在两个节点之间插入一个新节点需要修改的指针共__4__个 19.双向链表中，设p是指向其中待删除的节点，那么需要执行的操作命令序列为：p->front->rear=p->rear；__p->rear->front=p->front__ 20.在如下所示的链表中，假设在指针p所在的结点之后插入数据与值为a和b的两个节点,那么可用语句__S->next->next=p->next__来实现该操作 〔第三章 栈〕 1. 栈的特点是__先进后出__ 2. 在栈构造中，允许插入，删除的一端称为__栈顶__ 3. 在顺序栈中，在栈顶指针top=-1时表示__栈为空__ 4.顺序栈s存储在数组s->data[0..maxlen-1]中，进栈操作时首先需要执行的语句有： s->top=__s->top+1__ 5.链栈LS为空的条件是__LS==NULL__ 6.顺序栈s在对s进展栈操作之前，首先要判断__栈满否__ 7.假设内存空间充足，__链__栈可以不定义栈满运算 8.同一栈的各元素类型__一致__ 9.在有n个元素的链栈中，进栈操作的时间复杂度为__O(1)__。

10.由于链栈的操作只在链表的头部进展，所以没有必要设置__头__节点 11.从一个栈删除元素时，首先取出__栈顶元素__，然后在挪动栈顶指针 12.像一个栈顶指针为top的链栈插入一个新的节点*p时，应执行__p->next=top__和top=p的操作 13.假设进栈的次序是A、B、C、D、E执行三次出栈操作后栈顶元素为__B__ 14.四个元素按A、B、C、D顺序进s栈执行两次pop(S、X)后X的值是__C__ 15.设有一个顺序空栈，现有输入序列号ABCDE，经过push、push、pop、push、pop、push、push、pop操作之后输出序列式是__BCE__ 16.对一个初始值为空栈s执行操作push(s,5)、push(s,2)、push(s,4)、push(s,x)、readTop(s,x)后，x的值应是__2__ 17.设I表示入栈操作，O表示出栈操作，假设元素入栈顺序为1,2,3,4为了得到1,3,4,2出栈顺序，那么相应的I和O的操作串为__IOIIOIOO__ 18.表达式，求它后缀表达式是__栈__的典型应用 19.A+B/C-D*E的后缀表达式是__ABC/+DE*-__。

20.一个栈的进栈序列是1,2,3,4,，......，n，其输出序列是p1，p2，p3，......，pn假设p1=n，那么pi的值是__n+i-。