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

WORD格式WORD格式.分享精品精品.资料一、判断题（第一章 绪论）答案：错误答案：错误答案：正确答案：错误法的时间答案：正确（第二章 线性表）取顺序存储线性表的第i个元素的时间同i答案：错误答案：正确答案：错误答案：正确插入和删除操作是数据结构中最基本的两种操作答案：错误（第三章 栈）答案：错误在C（或C++）语言中设顺序栈的长为 MAXLEN，则top=MAXLEN表示栈满答案：错误答案：正确空栈就是所有元素为 0上的栈答案：错误答案：正确（第四章 队）答案：正确答案：错误答案：错误在循环队中，尾指针 rear大于头指针front，则元素个数为rear-front答案：正确答案：错误（第五章 ）是 n个字母的有限序答案：错误答案：正确答案：错误答案：错误答案：正确（第章 对维数组和广义表）n维的多维数组可以视为n-1维数组元素组成的线性结构。答案：正确上三角矩阵对主角线以上（包括对主角线中的元素），均为常数答案：错误答案：正确广义表Ls（a，a， an-，则an-1是其表尾。答案：错误广义表a,a,）答案：错误（第七章 树和二叉树）答案：正确答案：错误答案：正确答案：错误做特殊处。答案：错误（第八章 图）v1,v）与v2,v）答案：错误答案：正确一个无向图以顶点 v1为起点进深优先遍历， 所得的遍历序唯一， 则可以唯确定该图。答案：错误的边数有关。答案：错误存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）可以。答案：正确（第九章 查找）答案：错误答案：错误答案：错误答案：正确针域置空即可。答案：错误（第十章 排序）答案：错误答案：正确答案：错误答案：错误答案：错误二、填空题（第一章 绪论）数据结果是一门研究非数值计算的程序设计问题中计算机数据元以及它们间关系和运算的学科。数据有逻辑结构和 存储结两种结构。数据逻辑结构除集合以外的还包括线性结构，树形结构和 图形结。数据结构按逻辑结构可分为两大类，分别是线性结构非线性结。图形结构树形结合称为非线性结构。在树形结构中，除树根节点以外，其余每个节点只有

1 个前驱结点。在图形结构中，每一个节点的前驱节点上数和后继节点数可互。数据的存储结构，又叫做数据物结构 。数据的存储结构形式，包括顺序存储，链式存储引存储和 散存储 。树形结构中的元素之间存1对的关系。图形结构的元素之间存多对的关系。数据结构主要研究数据的逻辑结构，存储结构算法 三方面的内容。数据结构被定义(D,R),D是数据的有限集合是D上逻辑关的有限集合算法是对特定问解决步的描述。算法效的可以分为事先估算和

事后统。一个算法的时间复杂是算法 数据规的函数。算法的空间复杂是指该算法所耗费的 存储空他是该算法求解问题规模n的数。一个算法中，还有 10万条基本语，但有问题的规模无关，则该算法的时间复为 O(1) 。一个算法中的语频之和为 T(n)=6n+3nlog2n，则算法的时间复杂为 O(n) 。一个算法中的语 频 之和为T(n)=3n+nlog2n+n2，则算法的时间复杂 为 O(n^2) 。（第二章 线性表）在线性表中，数据的长定义为 表。顺序表中逻辑上相邻的元素在物位置上 一相邻。顺序表相对于链表的优点密大 和随机存取。某线性表采用顺序存储结构4100则下标为1112个元存储地址144 。当线性表中的元素总数基本稳定且很少进插入和删除操作， 但要求以最快的速存现象表中的元素时，应采顺存储结构。顺序表中访问任意一个结点的时间复杂均为 O(1) 。在一个长为 n的顺序表中删除第i个元素要移n-i 个元素。在一个长为 n的顺序表中，如果要在第二个元素前插入一个元素要后n-i+1 个素。线性表L=(a1,a2,......,an)用数组表示假定删除表中任意元素的概相同， 则删除一元素平均需要移动元素的个数n/2 。在线性表的链式存储中元素之间的逻辑关系是通指决定的。在双向链表中每个节点有两个指针域他们一个指向其 前驱 结点，另一个指向其继结点。线性表的元素总数确定，且经常需要进插入和删除操作，应采链存储结构。在单向链表中，需要知表头指才能遍历整个链表。在单向链表中要在已知的节*p之前插入一个新节点需找*p的直接前驱结点的址，其查找的时间复杂为 O(n) 。单向循环链表的最大优点从任意节点出可以访问到链表中每一个元素。在双向链表中要删除已知节*p，其实间复杂为 O(n) 。带头节点的双循环链表 L 中判断只有一个元素节点的条件是 L->next->next==L(L->front->front==L) 。对于双向链表，在两个节点之间插入一个新节点需要修改的指针4 个。双向链表中，设 p是指向其中待删除的节点，则需要执的操作命序为：p->front->rear=p->rear； p->rear->front=p->front 。在如下所示的链表中，在指针 p所在的结点之后插入数据与值为a和b的两个节则可用语 S->next->next=p->next 来实现该操作。（第三章 栈）栈的特点先进后。在栈结构中，允许插入，删除的一端称栈。在顺序栈中，在栈顶指针top=-1时表栈为。顺序栈s存储在数组s->data[0..maxlen-1]中，进栈操作时首先需要执的语有s->top= s->top+1 。链栈LS为空的条件LS==NULL 。已知顺序栈s在对s进栈操作之前，首先要判断 栈满。内存空间充足， 栈可以定义栈满运算。同一栈的各元素类一致 。在有n个元素的链栈中，进栈操作的时间复杂为 O(1) 。由于链栈的操作只在链表的头部进，所以没有必要设置 头 节点。从一个栈删除元素时，首先取栈顶元，然后在移动栈顶指针。像一个栈顶指针为top的链栈插入一个新的节*p时应执 p->next=top 和top=p的操作。进栈的次序是 A、、C、、E执三次出栈操作后栈顶元素为 B 。四个元素按A、、D顺序进s栈执两次 pop(S、X)后X的值C 。设有一个顺序空栈现有输入序号 经过pushpushpoppushpoppushpushpop操作之后输出序式是 BCE 。对一个初始值为空栈 s执操作 push(s,5)、push(s,2)、push(s,4)、push(s,x)readTop(s,x)后，x的值应2 。设I表示入栈操作表示出栈操作，元素入栈顺序为 1,2,3,4为得到 1,3,4,2栈顺序，则相应的I和O的操作为 IOIIOIOO 。已知表达式，求它后缀表达式栈 的典型应用。A+B/C-D*E的后缀表达式ABC/+DE*- 。20已知一个栈的进栈序是 1,2,3,4，.....，，其输出序是 ppp3， ，pn。 p1=n，则pi的值n+i-1 。第四章 第四章填在队中存取数据应遵循的原则是先进先出。在队中允许插入的一段称之为队尾。在队中允许删除的一端，称之为对头。队在进出队操作时，首先要判断队是否为空。顺序队在进入队操作时，首先要判断队是否为满6.顺序队初始化后， front=rear＝-17.链队 8.读队首元素的操作改变队元素的个数。在一个链队中，队首指针为 front,队尾指针为rear，则判断该队只有一个结点条件为front==real（front-＞next==NULL）设长为 n的链队用单循环链表表示，只设头指针，则入队操作的时间复杂为 O(n)设长为 n的链队用单循环链表表示，只设尾指针，则出队操作的时间复杂为 O(n)队 Q，经过InitQueue(Q)XXXXXX运算后的值是0队 Q，经过InitQueue(Q)XXXXXX运算后，x的值是a解决顺序队“假溢出的方法是采用循环队循环队 q 的对手指针为 Q.front，队尾指针为 Q.rear，则队空的条件Q.rear==Q.front设循环队的容为 40（序号为0~39）现经过一系的入队和出队运算后， rear=19，则循环队中还有 8个元素设循环队的头指针 front指向队首元素尾指针rear指向队尾元素后的一个空闲元素队的最大空间为 MAXLEN，则队满标志为rear-front==MAXLEN从循环队中删除一个元素时，其操作是 front++在循环队中，队首指针指向队首元素的前一个位置删除双向对表中 *p的前驱结点（存在）应执的语序是 xxxxxxx第五章由个或多个字符组成的有限序称为字符。空格穿时有空格组成的。字符存储方式除顺序存储，链接存储，还有堆存储。穿衣顺序存储非紧凑格式的缺点是密小顺序存储紧凑格式的缺点是对的字符处困难。的链式存储结构，简称为链。链接存储的优点是插入，删除方，缺点是存储，检效低。cc++语言中以字符（这个答案很奇怪）表示值的终结两个相等的充分必要条件是两个长相等，且对应位置的字符相10设S=mymusi则 LenStS=8两个字符分别为 XXXXX求子的结果是在的运算中 XXXXXX，返回值为July在的运算中 XXXXXX，返回值-1设有两个 P和Q，求Q在P中首次出现的位置运算称作在子的定位运算中，被匹配的主称为目标，子称为模式模式匹配成功的起始位置称为有效位移设XXXXX设Xxxx20.n为主长，m为子长，且n＞＞m，则简单模式匹配算法最好情况下的时间复杂为0（n*m）第章多维数组的顺序存储方式有按优先顺序存储和优先两种。n维数组中的每一个元素最多可以有n个直接前驱种顺序存取结构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+18.非元素的个数远小于矩阵元素总数的矩阵为稀疏矩阵9.稀疏矩阵矩阵的三元组有三１０．稀疏矩阵中有ｎ个非元素，则三元组有ｎ＋１１１.稀疏矩阵的三元组中的一存储的是数组中非元素所在的１２．稀疏矩阵a，如图，其非元素存于三元表中三元组415，按优先顺序存储在三元表中的第５项稀疏矩阵的压缩存储方法通常有三元组表和十字链表两１４.任何一个非空广义表的表尾，必定是表元素１５．广义表Ｌ 的表尾【１６－２０题在书上看吧】 ＱＡＱ第七章三个节点可以组成五种同形态的树。在树中，一个结点所拥有的子树数，称之为该结点的。为的结点称之为叶结点。树中节点的最大层次称之为树的深对于二叉树来说，第二层上至多有深为 h的二叉树至多有20个节点的完全二叉树，编号为10