发布时间 : 星期二 文章实用数据结构基础(第四版)课后习题更新完毕开始阅读c6a7062802d8ce2f0066f5335a8102d276a26109
址，其查找的时间复杂度为__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-1__。
第四章 队列 第四章填空
1.在队列中存取数据应遵循的原则是先进先出。 2.在队列中允许插入的一段称之为队尾。 3.在队列中允许删除的一端，称之为对头。
4.队列在进行出队操作时，首先要判断队列是否为空。
5.顺序队列在进行入队操作时，首先要判断队列是否为满。 6.顺序队列初始化后，front=rear＝-1
7.链队列LQ为空时，LQ-＞front-＞next=NULL 8.读队首元素的操作不改变队列元素的个数。
9.在一个链队列中，若队首指针为front,队尾指针为rear，则判断该队列只有一个结点的条件为front==real（front-＞next==NULL）
10.设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为O(n) 11.设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复杂度为O(n) 12.队列Q，经过InitQueue(Q)XXXXXX 运算后的值是0
13.队列Q，经过InitQueue(Q)XXXXXX 运算后，x的值是a
14.解决顺序队列“假溢出”的方法是采用循环队
15.循环队列q的对手指针为Q.front，队尾指针为Q.rear，则队空的条件为Q.rear==Q.front 16.设循环队列的容量为40（序号为0~39）现经过一系列的入队和出队运算后，front=11，rear=19，则循环队列中还有8个元素
17.设循环队列的头指针front指向队首元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，则队满标志为rear-front==MAXLEN 18.从循环队列中删除一个元素时，其操作是front++ 19.在循环队列中，队首指针指向队首元素的前一个位置
20.删除双向对列表中*p的前驱结点（存在）应执行的语句序列是xxxxxxx
第五章
1.由零个或多个字符组成的有限序列称为字符串。 2.空格穿时有空格组成的串。
3.字符串存储方式除了顺序存储，链接存储，还有堆存储。 4.穿衣顺序存储非紧凑格式的缺点是密度小
5.串顺序存储紧凑格式的缺点是对串的字符处理困难。 6.串的链式存储结构，简称为链串。
7.串链接存储的优点是插入，删除方便，缺点是存储，检索效率低。 8.在c或c++语言中以字符（这个答案很奇怪）表示串值的终结
9.两个串相等的充分必要条件是两个串长度相等，且对应位置的字符相同 10.设S=“my music”则LenStr（S）=8 11.两个字符串分别为XXXXX 12.求子串的结果是
13.在串的运算中XXXXXX，返回值为July 14.在串的运算中XXXXXX，返回值为-1
15.设有两个串P和Q，求Q在P中首次出现的位置运算称作
16.在子串的定位运算中，被匹配的主串称为目标串，子串称为模式 17.模式匹配成功的起始位置称为有效位移 18.设XXXXX 19.设Xxxx
20.若n为主串长度，m为子串长度，且n＞＞m，则简单模式匹配算法最好情况下的时间复
杂度为0（n*m）
第六章
1.多维数组的顺序存储方式有按行优先顺序存储和列优先两种。 2.在n维数组中的每一个元素最多可以有n个直接前驱
3.在多维数组中，数据元素的存放地址可以直接通过地址计算公式算出，所以多维数组是一种顺序存取结构
4.数组元素a[0..2][0..3]的实际地址是2000，元素长度是4，则LOC[1,2]=228 5.输入二维数组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的节点的父节点的编号是5
8.将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，其右孩子结点编号为2i+1 9.已知完全二叉树的第8层有8个节点，则其叶节点数是三 10.采用二叉链表存储的n个节点的二叉树，共有空指针n+1个 11.如图 12.如图
13.A.B为一棵树二叉数上的两个结点，在中序遍历时，a在b前的条件是A在B的左子树上 14.设一棵二叉树节点的先序遍历序列为abcdefgh，中序遍历序列为dbeafchg，则二叉树中叶结点是EFH
15.某二叉树的中序遍历序列为debac，后序遍历序列为dbcad，则前序遍历序列为DABEC 16.前序为ABC，且后续为CBA的二叉树共有1种
17.由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树
18.由树转换成二叉树时，其根结点无右子树 19.哈夫曼树是带权路径长度的最短二叉树。 20.具有n个节点的哈夫曼树共有2n-1个结点。