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

判断题（第一章绪论）1.数据元素是数据的最小单元。答案：错误一个数据结构是由一个逻辑结构和这个逻辑结构上的基本运算集构成的整体。答案：错误数据的存储结构是数据元素之间的逻辑关系和逻辑结构在计算机存储器内的映像。答案：正确数据的逻辑结构是描述元素之间的逻辑关系，它是依赖于计算机的。答案：错误5.用语句频度来表示算法的时间复杂度的最大好处是可以独立于计算机的软硬件，分析算法的时间答案：正确（第二章线性表）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.在链串中为了提高存储密度，应该增大结点的大小。答案：正确（第六章对维数组和广义表）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为起点，进行深度优先遍历，所得的遍历序列唯一，则可以唯一确定该图。答案：错误5.顺序队列在进行入队操作时，首先要判断队列是否为满。6.顺序队列初始化后，front=rear＝-17.链队列LQ为空时，LQ-＞front-＞next=NULL8.读队首元素的操作不改变队列元素的个数。9.在一个链队列中，若队首指针为front,队尾指针为rear，则判断该队列只有一个结点的条件为front==real（front-＞next==NULL）10.设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为O(n)11.设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复杂度为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（序号为0~39）现经过一系列的入队和出队运算后，front=11，rear=19，则循环队列中还有8个元素17.设循环队列的头指针front指向队首元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，则队满标志为rear-front==MAXLEN18.从循环队列中删除一个元素时，其操作是front++19.在循环队列中，队首指针指向队首元素的前一个位置20.删除双向对列表中*p的前驱结点（存在）应执行的语句序列是xxxxxxx第五章1.由零个或多个字符组成的有限序列称为字符串。2.空格穿时有空格组成的串。3.字符串存储方式除了顺序存储，链接存储，还有堆存储。4.穿衣顺序存储非紧凑格式的缺点是密度小5.串顺序存储紧凑格式的缺点是对串的字符处理困难。6.串的链式存储结构，简称为链串。7.串链接存储的优点是插入，删除方便，缺点是存储，检索效率低。8.在c或c++语言中以字符（这个答案很奇怪）表示串值的终结9.两个串相等的充分必要条件是两个串长度相等，且对应位置的字符相同10.设S=“mymusic”则LenStr（S）=811.两个字符串分别为XXXXX12.求子串的结果是13.在串的运算中XXXXXX，返回值为July14.在串的运算中XXXXXX，返回值为-115.设有两个串P和Q，求Q在P中首次出现的位置运算称作16.在子串的定位运算中，被匹配的主串称为目标串，子串称为模式17.模式匹配成功的起始位置称为有效位移18.设XXXXX19.设Xxxx20.若n为主串长度，m为子串长度，且n＞＞m，则简单模式匹配算法最好情况下的时间复杂度为0（n*m）第六章1.多维数组的顺序存储方式有按行优先顺序存储和列优先两种。2.在n维数组中的每一个元素最多可以有n个直接前驱3.在多维数组中，数据元素的存放地址可以直接通过地址计算公式算出，所以多维数组是一种顺序存取结构4.数组元素a[0..2][0..3]的实际地址是2000，元素长度是4，则LOC[1,2]=2285.输入二维数组A[n][m]中所有元素值的时间复杂度为0（n*m）6.n阶对称矩阵，如果只存储下三角元素，只需要n*(n+1)/2个存储单元7.n阶下三角矩阵，因为对角线的上方是一个常数，需要n*(n+1)/2+1个存储单元8.非零元素的个数远小于矩阵元素总数的矩阵为稀疏矩阵9.稀疏矩阵矩阵的三元组有三列１０．稀疏矩阵中有ｎ个非零元素，则三元组有ｎ＋１１１.稀疏矩阵的三元组中的一列存储的是数组中非零元素所在的行１２．稀疏矩阵a，如图，其非零元素存于三元表中三元组415，按列优先顺序存储在三元表中的第５项１３.稀疏矩阵的压缩存储方法通常有三元组表和十字链表两种１４.任何一个非空广义表的表尾，必定是表元素１５．广义表Ｌ的表尾【１６－２０题在书上看吧】ＱＡＱ第七章1.三个节点可以组成五种不同形态的树。2.在树中，一个结点所拥有的子树数，称之为该结点的度。3.度为零的结点称之为叶结点。4.树中节点的最大层次称之为树的深度5.对于二叉树来说，第二层上至多有6.深度为h的二叉树至多有7.有20个节点的完全二叉树，编号为10的节点的父节点的编号是58.将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，其右孩子结点编号为2i+19.已知完全二叉树的第8层有8个节点，则其叶节点数是三10.采用二叉链表存储的n个节点的二叉树，共有空指针n+1个11.如图12.如图13.A.B为一棵树二叉数上的两个结点，在中序遍历时，a在b前的条件是A在B的左子树上14.设一棵二叉树节点的先序遍历序列为abcdefgh，中序遍历序列为dbeaf