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

1、1、 判断题（第一章 绪论）1.数据元素是数据的最小单元。 答案：错误2. 一个数据结构是由一个逻辑结构和这个逻辑结构上的基本运算集构成的整体。答案：错误3. 数据的存储结构是数据元素之间的逻辑关系和逻辑结构在计算机存储器内的映像。答案：正确4. 数据的逻辑结构是描述元素之间的逻辑关系，它是依赖于计算机的。答案：错误5.用语句频度来表示算法的时间复杂度的最大好处是可以独立于计算机的软硬件，分析算 法的时间答案：正确（第二章 线性表）6.取顺序存储线性表的第 i 个元素的时间同 i 的大小有关。答案：错误7.线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。答案：正确8.线性链表

2、的每一个节点都恰好包含一个指针域。答案：错误9.顺序存储方式的优点的存储密度大，插入和删除效率不如练市存储方式好。答案：正确10.插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。答案：错误（第三章 栈）11.栈是一种对进栈和出栈作了限制的线性表。答案：错误12.在 C（或 C+）语言中设顺序栈的长度为 MAXLEN，则 top=MAXLEN 表示栈满。答案：错误13.链栈与顺序栈相比，其特点之一是通常不会出现满栈的情况。答案：正确14.空栈就是所有元素都为 0 上的栈。答案：错误15.将十进制数转换为二进制数是栈的典型应用之一。答案：正确（第四章 队列）16.队列

3、式限制在两端进行操作的线性表。答案：正确17.判断顺序队列为空的标准是头指针和尾指针都指向同一结点。答案：错误18.在循环链列队中无溢出现像。答案：错误19.在循环队列中，若尾指针 rear 大于头指针 front，则元素个数为 rear-front。答案：正确20.顺序队列和循环队列关于队满和队空的判断条件是一样的。答案：错误（第五章 串）21.串是 n 个字母的有限序列。答案：错误22.串的堆分配存储是一种动态存储结构。答案：正确23.串的长度是指串中不同字符的个数。答案：错误24.如贵一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。答案：错误25.在链串中为了提高存储密度，

4、应该增大结点的大小。答案：正确（第六章 对维数组和广义表）26. n 维的多维数组可以视为 n-1 维数组元素组成的线性结构。答案：正确27.上三角矩阵对主角线以上（不包括对主角线中的元素） ，均为常数 C。答案：错误28.数组的三元组表存储时对稀疏矩阵的压缩存储。答案：正确29.广义表 Ls=（a0，a1 ，.an-1） ，则 an-1 是其表尾。答案：错误30.广义表（a,b） ，a,b）的表头和表尾是相等的。答案：错误（第七章 树和二叉树）31.在完全二叉树中，若一个结点没有左孩子，则它必然是叶子节点。答案：正确32.含多于两棵树的森林转换到二叉树，其根节点一定无右子树。答案：错误33.

5、二叉树的前序遍历中，任意一个节点均处于其子女节点的前面。答案：正确34.在中序线索二叉树中，右线索若不为空，则一定指向其双亲。答案：错误35.在哈夫曼编码中，当两个字符出现的频率相同的，其他编码也相同，对于这种情况应该做特殊处理。答案：错误（第八章 图）36.在无相图中， （v1,v2）与（ v2,v1）是两条不同的边。答案：错误37.图可以没有边，但不能没有顶点。答案：正确38.若一个无向图以顶点 v1 为起点，进行深度优先遍历，所得的遍历序列唯一，则可以唯一确定该图。答案：错误39.用邻接矩阵法存储一个图时，所占用的存储空间大小与图中的顶点个数无关，而只与图的边数有关。答案：错误40.存储

6、无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）部分就可以了。答案：正确（第九章 查找）41.在有序的顺序表和有序的链表上，均可以采用二分查找法来提高查找速度。答案：错误42.在二叉排序树中，根节点的这都小于孩子节点的值。答案：错误43.选择好的哈希函数就可以避免冲突的发生。答案：错误44.散列存储法的基本思想是由关键字的值决定数据存储地址。答案：正确45.在二叉排序树上删除一个节点时，不必移动其他节点，只要将该节点的父节点的相应指针域置空即可。答案：错误（第十章 排序）46.如果某种排序算法不稳定，则该排序方法就没有使用价值。答案：错误47.希尔排序是不稳定的排序。答案：正

7、确48.对排序所需的时间与待排序的记录个数无关。答案：错误49.快速排序在任何情况下都比其他排序方法速度快。答案：错误50.采用归并排序可以实现外排序。答案：错误二、填空题（第一章 绪论）1. 数据结果是一门研究非数值计算的程序设计问题中计算机的_ 数据元素_，以及它们之间关系和运算的学科。2. 数据有逻辑结构和 _存储结构 _两种结构。3. 数据逻辑结构除了集合以外的还包括线性结构，树形结构和_图形结构_。4. 数据结构按逻辑结构可分为两大类，分别是线性结构和_非线性结构_。5. 图形结构和_树形结构_合称为非线性结构。6. 在树形结构中，除了树根节点以外，其余每个节点都只有_1_ 个前驱结

8、点。7. 在图形结构中，每一个节点的前驱节点上数和后继节点数可以_互换_。8. 数据的存储结构，又叫做数据的_物理结构_ 。9. 数据的存储结构形式，包括顺序存储，链式存储索引存储和_散列存储_。10. 树形结构中的元素之间存在_1 对多_的关系。11. 图形结构的元素之间存在_多对多_ 的关系。12. 数据结构主要研究数据的逻辑结构，存储结构和_算法_三方面的内容。13. 数据结构被定义为(D,R),D 是数据的有限集合，R 是 D 上的_ 逻辑关系_的有限集合14. 算法是对特定问题_解决步骤 _的描述。15. 算法效率的度量可以分为事先估算和_事后统计_ 。16. 一个算法的时间复杂度是

9、算法_数据规模_ 的函数。17. 算法的空间复杂度是指该算法所耗费的_存储空间_，他是该算法求解问题规模 n 的函数。18. 若一个算法中，还有 10 万条基本语句，但有问题的规模无关，则该算法的时间复杂度为_O(1)_。19. 若一个算法中的语句频度之和为 T(n)=6n+3nlog2n，则算法的时间复杂度为_O(n)_。20. 若一个算法中的语句频度之和为 T(n)=3n+nlog2n+n2，则算法的时间复杂度为_O(n2)_。（第二章 线性表）1.在线性表中，数据的长度定义为_表长_。2.顺序表中逻辑上相邻的元素在物理位置上_一定_相邻。3.顺序表相对于链表的优点是_密度大_和随机存取。

10、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)用数组表示假定删除表中任意元素的概率相同，则删除一个元素平均需要移动元素

11、的个数是_n/2_。10.在线性表的链式存储中元素之间的逻辑关系是通过_指针_ 决定的。11.在双向链表中每个节点都有两个指针域他们一个指向其_前驱_ 结点，另一个指向其后继结点。12.线性表的元素总数不确定，且经常需要进行插入和删除操作，应采用_链式_ 存储结构。13.在单向链表中，需要知道_表头指针_才能遍历整个链表。14.在单向链表中，要在已知的节点*p 之前插入一个新节点，需找到 *p 的直接前驱结点的地址，其查找的时间复杂度为_O(n)_。15.单向循环链表的最大优点是_从任意节点出发_可以访问到链表中每一个元素。16.在双向链表中要删除已知节点*p ，其实间复杂度为_O(n)_。1

12、7.带头节点的双循环链表 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. 在栈结构中，允许插入，删

13、除的一端称为_栈顶_ 。3. 在顺序栈中，在栈顶指针 top=-1 时表示_栈为空_。4.顺序栈 s 存储在数组 s-data0.maxlen-1中，进栈操作时首先需要执行的语句有： s-top=_s-top+1_。5.链栈 LS 为空的条件是_LS=NULL_。6.已知顺序栈 s 在对 s 进行栈操作之前，首先要判断_栈满否 _。7.若内存空间充足，_链_栈可以不定义栈满运算。8.同一栈的各元素类型_一致_。9.在有 n 个元素的链栈中，进栈操作的时间复杂度为_O(1)_。10.由于链栈的操作只在链表的头部进行，所以没有必要设置_头_ 节点。11.从一个栈删除元素时，首先取出_栈顶元素_，然

14、后在移动栈顶指针。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)、r

15、eadTop(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-1_。第四章 队列第四章填空1.在队列中存取数据应遵循的原则是先进先出。2.在队列中允许插入的一段称之为队尾。3.在队列

16、中允许删除的一端，称之为对头。4.队列在进行出队操作时，首先要判断队列是否为空。5.顺序队列在进行入队操作时，首先要判断队列是否为满。6.顺序队列初始化后，front=rear-17.链队列 LQ 为空时， LQ-front-next=NULL8.读队首元素的操作不改变队列元素的个数。9.在一个链队列中，若队首指针为 front,队尾指针为 rear，则判断该队列只有一个结点的条件为 front=real（front-next=NULL）10.设长度为 n 的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为O(n)11.设长度为 n 的链队列用单循环链表表示，若只设尾指针，则出队

17、操作的时间复杂度为O(n)12.队列 Q，经过 InitQueue(Q)XXXXXX运算后的值是 013.队列 Q，经过 InitQueue(Q)XXXXXX运算后，x 的值是 a14.解决顺序队列“假溢出”的方法是采用循环队15.循环队列 q 的对手指针为 Q.front，队尾指针为 Q.rear，则队空的条件为 Q.rear=Q.front16.设循环队列的容量为 40（序号为 039）现经过一系列的入队和出队运算后，front=11，rear=19，则循环队列中还有 8 个元素17.设循环队列的头指针 front 指向队首元素，尾指针 rear 指向队尾元素后的一个空闲元素，队列的最大空

18、间为 MAXLEN，则队满标志为 rear-front=MAXLEN18.从循环队列中删除一个元素时，其操作是 front+19.在循环队列中，队首指针指向队首元素的前一个位置20.删除双向对列表中*p 的前驱结点（存在）应执行的语句序列是 xxxxxxx第五章1.由零个或多个字符组成的有限序列称为字符串。2.空格穿时有空格组成的串。3.字符串存储方式除了顺序存储，链接存储，还有堆存储。4.穿衣顺序存储非紧凑格式的缺点是密度小5.串顺序存储紧凑格式的缺点是对串的字符处理困难。6.串的链式存储结构，简称为链串。7.串链接存储的优点是插入，删除方便，缺点是存储，检索效率低。8.在 c 或 c+语言中以字符（这个答案很奇怪）表示串值的终结9.两个串相等的充分必要条件是两个串长度相等，且对应位置的字符相同10.设 S=“my music”则 LenStr（S ）=8