实用数据结构基础(第四版)课后习题

1、实用数据结构基础（第四版）课后习题一、判断题（第一章导言）数据元素是数据的最小单元。答案：错误数据结构是由逻辑结构和逻辑结构上设置的基本操作组成的整体。回答：错了答案：正确数据的逻辑结构是描述元素之间的逻辑关系，这取决于计算机。回答：错了析算法的时间答案：正确（第二章线性表）取顺序存储线性表的第ii答：正确线性链表的每一个节点都恰好包含一个指针域。答案：错误答：正确常使用。答案：错误（第三章栈）堆栈是一个线性表，用于限制堆栈的进入和退出。回答：错了c（c+）maxlentop=maxlen错误与顺序堆栈相比，链式堆栈的一个特点是堆栈通常不满。回答：正确0将十进制数转换为二进制数是堆栈的典型应用

2、之一。回答：正确（第4）队列式限制在两端进行操作的线性表。答案：正确判断序列队列为空的标准是头指针和尾指针都指向同一个节点。回答：错了在循环链列队中无溢出现像。答案：错误答：正确顺序队列和循环队列关于队满和队空的判断条件是一样的。答案：错误（第五章串）字符串是由n串的堆分配存储是一种动态存储结构。答案：正确字符串的长度是指字符串中不同字符的数量。回答：错了如贵一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。答案：错误为了提高链中的存储密度，应该增加节点的大小。回答：正确（第六章对维数组和广义表）26.N 维多维数组可以看作是由N-1 维数组元素组成的线性结构。回答：正确上三角矩阵

3、对主角线以上（不包括对主角线中的元素），均为常数c。答案：错误存储数组的三重表时，稀疏矩阵的压缩存储。回答：正确广义表ls=（a0，a1，.an-1），则an-130.广义表（a,b），a,b）的表头和表尾是相等的。答案：错误（第七章树和二叉树）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子节点。答案：正确如果有两棵以上树的林被转换为二叉树，则其根节点必须没有正确的子树。回答：错了二叉树的前序遍历中，任意一个节点均处于其子女节点的前面。答案：正确34、在中间线索线索二叉树中，如果右线索不是空的，它必须指向它的父母。回答：错了35.在哈夫曼编码中，当两个字符出现的频率相同的，其他编码也相同

4、，对于这种情况应该做特殊处理。答案：错误（第八章图）36.在无相图中，（v1,v2）与（v2,v1）是两条不同的边。答案：错误图可以没有边，但没有顶点。回答：正确若一个无向图以顶点v1以唯一确定该图。答案：错误数有关。回答：错了存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角部分就可以了。答案：正确（第九章查找）二进制搜索方法可用于提高有序序列表和有序链表的搜索速度。回答：错了在二叉排序树中，根节点的这都小于孩子节点的值。答案：错误选择一个好的哈希函数可以避免冲突。回答：错了散列存储法的基本思想是由关键字的值决定数据存储地址。答案：正确应的指针字段设置为空即可。回答：错误（

5、10）如果某种排序算法不稳定，则该排序方法就没有使用价值。答案：错误希尔排名是一个不稳定的排名。回答：正确对排序所需的时间与待排序的记录个数无关。答案：错误在任何情况下，快速排序都比其他排序方法快。回答：错了（第一章绪论）数据结果是一门计算机科学，研究非数值计。数据有逻辑结构存储结两种结构。数据逻辑结构包括线性结构、树形结构图形结构4.数据结构按逻辑结构分为两类：线性结构和非线性结构5.图形结构和树结构它们统称为非线性结构。6.在树形结构中，除了树根节点以外，其余每个节点都只1个前驱结点7.在图形结构中，每一个节点的前驱节点上数和后继节点数可以互换。8.数据的存储结构又叫做数据物理结。9.数据

6、的存储结构，包括顺序存储、链式存储和索引存储10.树结构中的元素之存在差异_uu1到_uu关系11.图形结构元素之间存在差异u多对多关系。数据结构主要研究数据的逻辑结构，存储结构算法三方面的内容。数据结构定义为RD1415.算法效率的度量可以分为事先估算事后统。16.一个算法的时间复杂度算法数据规的函数17.算法的空间复杂度是指该算法所耗费存储空，他是该算法求解问题规模n的函数。100000杂度为_o（1）_u若一个算法中的语句频度之和为t(n)=6n+3nlog2n，则算法的时间复杂度为 o(n)。20.若一个算法中的语句频度之和为t(n)=3n+nlog2n+n2，则算法的时间复杂o(n2

7、)。（第二章线性表）_uuu。顺序表中逻辑上相邻的元素在物理位置一定相邻3.顺序表相对于链表的优 点是密度和随机存取4.某线性表采用顺序存储结构，每个元素占据4个存储单元首地址为100则下标为11的(第12个元)存储地址144。当线性表中的元素总数基本稳定，插入和删除操作很少，但需要以最快的速度访现象表中的元素时，应使存储结构。顺序表中访问任意一个结点的时间复杂度均o(1)。删除序列表中要移动的第i个元素，长度为n;n-i元素8.在长度为N的序列表中，如果要在第二个元素之前插入一个元素，请将其向后移动_;N-i+1元素。线性表L=（A1，A2，an）由一个数组表示。假设删除表中任何元素的概率相

8、同，则要移动以删除元素的平均元素数_uun/2在线性表的链式存储中元素之间的逻辑关系是通指针决定的。个指向其后一个节点。线性表的元素总数不确定，且经常需要进行插入和删除操作，应采链式储结构。13.在单向链表中，需要知表头指才能遍历整个链表。要在已知节点列表中插入新节*，请在已知节点列表中查找新节址，其查找的时间复杂度o(n)。15.单向循环链表的最大优点是从任何节点开始，链表中的每个元素都可以访问。16. 删除双向链表中的已知节点*P，其复杂度为_uo（n）_uu带头节点的双循环链表l中判断只有一个元素节点的条件l-next-next=l(l-front-front=l)。_u4_1。双向链表

9、中，设pfront-rear=p-rear；p-rear-front=p-front。在如下所示的链表中，如果在指针Pa的节点，则可以使用该语句来执行此操作。（第三章）栈的特点先进后。_uuu 堆栈顶部uu。3当堆栈顶部的指针top=-1顺序栈s存储在数组s-data0.maxlen-1中，进栈操作时首先需要执行的语句有s-top=s-top+1。链堆栈LS_Uls=null已知顺序栈s在对s进行栈操作之前，首先要判栈满。若内存空间充足， 链栈可以不定义栈满运算8.同一栈的各元素类一。在包含n_o（1）_uo由于链栈的操作只在链表的头部进行，所以没有必要设头节点11.从一栈删除元素时，首先取栈

10、顶元，然后在移动栈顶指针。*Ptop_;P-next=toptop=P。若进栈的次序是a、b、cd、e执行三次出栈操作后栈顶元素b。14.四元素按、b、d顺序进s栈执行两次pop(sx)后x的值c。有一个连续的空堆栈。现有的输入序列号ABCDEpush、push、poppushpushpop对一个初始值为空栈s执行操作push(s,5)、push(s,2)、push(s,4)、push(s,x)readtop(s,x)后，x的值应2。1,2,3,4，为了获得1,3,4,2Io_uuiioo _uioo已知表达式，求它后缀表达式栈的典型应用19.a+b/c-d*e 的后缀表达式是abc/+de*