数据结构 (熊回香 王伟军 著) 清华大学出版社 北京交通大学出版社 部分答案 课后答案 20页

'课后答案网您最真诚的朋友www.hackshp.cn网团队竭诚为学生服务，免费提供各门课后答案，不用积分，甚至不用注册，旨在为广大学生提供自主学习的平台！课后答案网：www.hackshp.cn视频教程网：www.efanjy.comPPT课件网：www.ppthouse.com课后答案网www.hackshp.cn 习题一一、选择题1．B2．C3．B4．D5．C6．D7．A8．C二、填空题1．数据元素数据元素间关系2.数据的组织形式，即数据元素之间逻辑关系的总体3．有穷性确定性可行性4．算法的时间复杂度和空间复杂度5．集合线性结构树形结构图状结构或网状结构三、简述题khdaw.com1．解答：四种表示方法。⑴顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作（如插入、删除）效率较差。⑵链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。课后答案网⑶索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标），兼有静态和动态特性。www.hackshp.cn⑷散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。2．解答：数据类型是程序设计语言中的一个概念，它是一个值的集合和操作的集合。如C语言中的整型、实型、字符型等，如整数的取值范围与具体机器和编译系统有关，其操作有加、减、乘、除、求余等。实际上数据类型是厂家提供给用户的已实现了的数据结构。“抽象数据类型（ADT）”指一个数学模型及定义在该模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部如何表示和实现无关。无论其内部结构如何变化，只要它的数学特性不变就不影响它的外部使用。抽象数据类型和数据类型实质上是一个概念。此外，抽象数据类型的范围更广，它已不再局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类型。使用抽象数据类型定义的软件模块含定义、表示和实现三部分，封装在一起，对用户透明（提供接口），而不必了解实现细节。抽象数据类型的出现使程序设计不再是“艺术”，而是向“科学”迈进了一步。3．解答：评价好的算法有四个方面。一是算法的正确性；二是算法的易读性；三是算法的健壮性；四是算法的时空效率（运行）。khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 4．解答：逻辑结构、存储结构、操作（运算）。5．解答：通常考虑算法所需要的存储空间量和算法所需要的时间量。后者又涉及到四方面：程序运行时所需输入的数据总量，对源程序进行编译所需时间，计算机执行每条指令所需时间和程序中指令重复执行的次数。6．解答：栈和队列的逻辑结构相同，其存储表示也可相同（顺序存储和链式存储），但由于其运算集合不同而成为不同的数据结构。7．解答：khdaw.com线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为O(n)；而在链式存储方式下，插入和删除时间复杂度都是O(1)。8．解答：对算法A1和A2的时间复杂度T1和T2取对数，得nlog22和2log2n。显然，算法A2好于A1。课后答案网9．解答：⑴语句的的次数为n-2次，T(n)=O(n)。⑵语句的的次数为n-1次，T(n)=www.hackshp.cnO(n)。⑶语句的的次数为n次，T(n)=O(n)。1/21/2⑷语句的的次数为n次，T(n)=O(n)。3⑸语句的的次数为(n(n-1)(n-2))/6次，T(n)=O(n)。khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 习题六一、选择题1．C2.D3．B4．B5．D6．C7．C8．C9．C10．A二、填空题k-1k1．22-12．0(n-1)/2(n+1)/2⎣log2n⎦+1k-2k-13．2+1（第k层1个结点，总结点个数是2，编号最小的叶子在第k-1层最左边，H-1k-2k-1其双亲是2/2=2）2⎣log2i⎦+14．完全二叉树单枝树（树中任一结点（除最后一个结点是叶子外）,只有左子女或只有右子女）khdaw.com5．先序中序6．任何结点至多只有右孩子的二叉树7．二叉树8．62619．(n×(k-1)+1)/k设叶子结点个数为n0，则有分枝数n-1=(n-n0)×k，即n0=(n×(k-1)+1)/kn-110．2课后答案网n个结点且高度为n的二叉树为单支树，实际上是在高度为n的满二叉树中寻找该单支树的不同排列，即走了一条由根到达所有叶子的过程，它恰好为满二叉树的叶子数。（n个结点的满二叉树的叶子数为(n+1)/2）www.hackshp.cn11．空指针域存放该结点的前驱或后继信息12．2513．2n-114．n+115．先序遍历三、简述题1．解答：目的：树和森林采用二叉树的存储结构，可以利用二叉树的已有算法解决树和森林的有关问题；主要区别：树中结点的最大度数没有限制，而二叉树结点的最大度数为2；树的结点无左右之分，而二叉树的结点有左右之分。2．解答：线性表属于约束最强的线性结构，在非空线性表中，只有一个“第一个”元素，也只有一个“最后一个”元素；除第一个元素外，每个元素有唯一前驱；除最后一个元素外，每个元素有唯一后继。树是一种层次结构，有且只有一个根结点，除叶子结点外（叶子结点无后继），每个结点可以有多个后继（孩子），除根结点外，每个结点只有一个前驱（双亲），根结点无前驱，从这个意义上说存在一（双亲）对多（孩子）的关系。广义表中的元素既可以是原子，也可以是子表，子表可以为它表共享。从表中套表意义上说，广义表也是层次结构。从逻辑上讲，树和广义表均属非线性结构。但在以下意义上，又蜕变为线性结构。如度为1khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 的树，以及广义表中的元素都是原子时。另外，广义表从元素之间的关系可看成前驱和后继，也符合线性表，但这时元素有原子，也有子表，即元素并不属于同一数据对象。3．解答：⑴第i层结点数为di-1⑵当n=1时，该结点为根，无双亲结点；否则，双亲结点的编号为⎣(n+d−2)/d⎦。⑶当(n-1)d+i+1小于等于树的总结点个数时，编号为n的结点存在第i个孩子结点，其编号为(n-1)d+i+1。⑷当(n-1)%d≠0且n+1小于等于树的总结点个数时，编号为n的结点有右兄弟，其右兄弟的编号是n+1。分析：这个问题实际上是由完全k叉树的特点来求结点编号之间的关系，类似于完全二叉树的性质。khdaw.com⑴在深度为k的满d叉树中，第1层有1个结点，第2层有k个结点……第i层有di-1个结点。⑵设编号为n的结点是在满d叉树的第1层上从左边数第j个结点，那么ld−1j=n−课后答案网d−1这j个结点对应有⎣(j−1)/d+⎦1个双亲结点。因此，编号为n的结点的双亲结点是第l−1层的第⎣www.hackshp.cn(j−1)/d+⎦1个结点，其编号p为：l−1l−1d−1⎢j−1⎥⎢d−1j−1⎥p=+⎢⎥+1=⎢++1⎥+1d−1⎣d⎦⎣d−1d⎦ld−1⎢n+d−2⎥将j=n−代入上式，化简得：p=。⎢⎥d−1⎣d⎦⑶设编号为n的结点是在满d叉树的第1层上从左边数第j个结点，那么n就等于前l−1层的结点数目加j，即：l−1l−1dd−1n=+j或j=n−d−1d−1由于满d叉树的第1层上的第j个结点左边有j-1个结点，它们共有(j-1)d个孩子。因此第j个结点的第i个孩子是第l+1层上从左边数第(j-1)d+i个结点，其编号p为：ld−1p=+d(j−1)+id−1l−1d−1将j=n−代入上式，化简得：p=(n−)1d+i+1d−1⑷编号为n的结点不是其双亲结点的第d个孩子时，则它有右兄弟。根据⑵和⑶的结论，khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com ⎢n+d−2⎥它的父结点编号为，而它的双亲结点的第d个孩子编号为：⎢⎥⎣d⎦⎛⎢n+d−2⎥⎞⎢n+d−2⎥⎜−1⎟d+d+1=d−1⎜⎢⎥⎟⎢⎥⎝⎣d⎦⎠⎣d⎦⎢n+d−2⎥n−1⎢n+d−2⎥因此，当n≠d+1，即≠时，编号为n的结点有右兄弟，⎢⎥⎢⎥⎣d⎦d⎣d⎦也就是说当n-1不能被d整除时，它有右兄弟，其右兄弟的编号为n+1。4．解答：设树中有n个叶子结点，那么树中总结点数目N为khdaw.com0N=n+n+⋯+n（a）01m另一方面，树中除根结点外，其他各结点都有且仅有一个分支指向它，所以树中的总结点个数恰好比分支数多1。如果B是树中的总分支数，即有：N=B+1但是，除度为0的结点没有分支外，每个度为课后答案网k的结点有k个分支，所以总分支数为：B=n+2×n+⋯+m×n12m即总结点数目为：www.hackshp.cnN=n+2×n+⋯+m×n+1（b）12m由（a）和（b）两个等式有n+n+⋯+n=n+2×n+⋯+m×n+101m12m即得：mn=1×n+2×n+⋯+(i−1)×n+⋯+(m−1)×n+1=(i−1)×n+1023im∑ii=25．解答：先序序列：ABDFGHCE中序序列：BFDHGACE]后序序列：FHGDBECA层序序列：ABCDEFGH6．解答：⑴若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。⑵若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。⑶若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。⑷若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 7．解答：⑴二叉树如图7.1所示：图7.1二叉树khdaw.com⑵该二叉树的先序线索二叉树如图7.2所示：课后答案网www.hackshp.cn图7.2先序线索二叉树该二叉树的中序线索二叉树如图7.3所示：图7.3中序线索二叉树该二叉树的后序线索二叉树如图7.4所示：khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 图7.4的序线索二叉树8．解答：khdaw.com虽然哈夫曼树的带权路径长度是唯一的，但形态不唯一。本题各字母编码如下：c1:0110c2:10c3:0010c4:0111c5:000c6:010c7:11c8:00119．解答：树的先序遍历序列：ABEFCGIJKDH树的后序遍历序列：EFBIJKGCHDA转换后二叉树如图7.5所示：课后答案网www.hackshp.cn图7.5转换后的二叉树其先序遍历序列：ABEFCGIJKDH其中序遍历序列：EFBIJKGCHDA其后序遍历序列：FEKJIGHDCBA对比遍历树和其对应的二叉树的结果，可得出如下结论：⑴先序遍历树与先序遍历该树所对应的二叉树具有相同的遍历结果，即它们的先序序列是相同的；⑵后序遍历树与中序遍历与该树所对应的二叉树具有相同的遍历结果。四、算法设计题khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 说明：以下解答中有关二叉树的习题要包含头文件：BiTree.h。1．算法描述如下：BiTreeCreatTree(TElemType*nodelist,intposition){BiTreep;if(nodelist[position]==0||position>15)returnNULL;else{p=(BiTree)malloc(sizeof(BiTNode));p->data=nodelist[position];p->lchild=CreatTree(nodelist,2*position);p->rchild=CreatTree(nodelist,2*position+1);khdaw.comreturnp;}}2．可以用两种常用的方法求解这个问题。方法一设置一个初始值为0的变量leafNum进行计数，在对二叉树进行遍历过程中判断当前所访问的结点是否为叶子结点，若为叶子结点，则课后答案网leafNum加1。因此当遍历完整个二叉树后，leafNum的值即为叶子结点的数目。其算法描述如下：intleafNum=0;voidCountLeaf_1(BiTreeT)www.hackshp.cn{if(!T)return;if(!T->lchild&&!T->rchild)leafNum++;else{CountLeaf_1(T->lchild);CountLeaf_1(T->rchild);}}方法二根据二叉树的特点可知：当二叉树为空时，叶子结点总数为0；当二叉树只有一个结点时，叶子结点数为1；否则，叶子结点数等于左、右子树叶子结点数之和，因此，可定义二叉树t的叶子结点数目leaf（t）的递归计算模型为：⎧0，当t=NULL时⎪leaf(t)=⎨1，当t为叶子时⎪⎩leaf(t−>Lchild)+leaf(t−>Rchild)，否则根据这个计算模型，可以编写如下算法：intCountLeaf_2(BiTreeT){if(!T)return0;if(!T->lchild&&!T->rchild)return1;return(CountLeaf_2(T->lchild)+CountLeaf_2(T->rchild));khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com }3．解答⑴递归算法用前序遍历算法交换二叉树中的各结点的左右子树，其算法描述如下：voidSwap_1(BiTreeT){BiTreer;if(!T)return;else{r=T->lchild;T->lchild=T->rchild;T->rchild=r;khdaw.comSwap_1(T->lchild);Swap_1(T->rchild);}}此算法亦可用后序遍历的递归算法实现，但不宜用中序遍历递归算法实现，因为若用中序遍历的算法进行交换时，则只能交换根结点的左、右孩子。⑵非递归算法课后答案网voidSwap_2(BiTreeT){inttop;www.hackshp.cnBiTreetemp,stack[max];if(T){top=1;stack[top]=T;//根结点入栈do{T=stack[top];//弹出栈顶结点top--;//退栈if(T->lchild||T->rchild){temp=T->lchild;//结点的左右指针交换T->lchild=T->rchild;T->rchild=temp;}if(T->lchild){top++;//交换后的左指针入栈stack[top]=T->lchild;}if(T->rchild){khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com top++;//交换后的右指针入栈stack[top]=T->rchild;}}while(top!=0);//栈空时结束}}4．如果对二叉树的结点对照完全二叉树进行编号，即根结点编号为1，结点i的左孩子编号为2×i，右孩子编号为2×i＋1，那么对于完全二叉树，结点的编号一定是连续的，此时树中最大的结点编号一定等于树中的结点个数；而对于非完全二叉树，结点编号一定不连续，树中最大的结点编号一定大于树中的结点个数。因此，可以先对二叉树的结点按这种编号原则进行编号，求出树中结点个数和最大结点编号，然后再比较结点个数和最大编号是否相等。基于这种思想可编写如下算法：khdaw.comintNum(BiTreeT,inti,int&m){//T为子树的根，i为根结点编号,m中保存结点的最大编号,函数返回树中结点的个数if(!T)return0;if(mlchild,2*i,m)+Num(T->rchild,2*i+1,m));}课后答案网boolCheckTree_1(BiTreeT){intn,maxno=0;www.hackshp.cnn=Num(T,1,maxno);//计算结点个数，并求出最大编号maxnoif(n==maxno)returntrue;elsereturnfalse;}进一步讨论：本算法充分利用了完全二叉树结点编号连续的特点，根据这个特点，也可以编写另一种判断二叉树是否为完全二叉树的特点。基本思想是将结点按其编号存放在一个一维数组中，如果数组中的结点是连续存放的，则为完全二叉树。算法描述如下：#defineN50//定义最大结点个数boolCheckTree_2(BiTreeT){BiTreesa[N+1];inti,n;if(!T)returntrue;//空二叉树为完全二叉树for(i=1;i<=N;i++)sa[i]=NULL;//初始化数组sai=n=1;sa[1]=T;//将根结点指针存放到sa的第1个位置while(i<=n){if(!sa[i])returnfalse;//sa中结点不连续if(sa[i]->lchild)khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com {n=2*i;//对左孩子编号sa[n]=sa[i]->lchild;//将左孩子指针存放到sa的第n个位置}if(sa[i]->rchild){n=2*i+1;//对右孩子编号sa[n]=sa[i]->rchild;//将右孩子指针存放到sa的第n个位置*/}i++;}returntrue;khdaw.com}5．采用先序遍历方法查找值为x的结点所有的层次。对应的算法描述如下：voidLevel(BiTreeT,TElemTypex,inth1,int&h){//查找值为x的结点所在的层次if(!T)h1=0;else{课后答案网if(T->data==x)h=h1;Level(T->lchild,x,h1+1,h);//在左子树中查找Level(T->rchild,x,h1+1,h);www.hackshp.cn//在右子树中查找}}intNodeLevel(BiTreebt,TElemTypex){//值为x的结点所有的层次inth;Level(bt,x,1,h);return(h);}6．根据祖先结点的定义，如果结点r是p的祖先，那么p必定是在r的左子树或右子树中的结点。因此，定义函数InTree(BT,p)检查p是否为子树BT中的结点，并在这个过程中输出p的祖先。基本思想为：⑴若BT==NULL，则返回0，表明p不在子树BT中;⑵若BT==p，则返回1，表明p包含在子树BT中;⑶若InTree(BT->lchild,p)==1或者InTree(BT->rchild,p)==1，则BT为p的祖先，输出BT并返回1;⑷否则，返回0。根据这一思路，可编写如下递归算法：intInTree(BiTreeBT,BiTreep){khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com if(!BT)return0;if(BT==p)return1;if(InTree(BT->lchild,p)||InTree(BT->rchild,p)){cout<data<<"";return1;}return0;}进一步讨论：⑴在上述算法中，通过检查p是否为子树BT中的结点来输出p的所有祖先。实际上检查p是否为子树BT中结点的过程等价于二叉树的先序遍历，即首先判断根结点是否为p，若不是，再去检查p是否为BT的左子树或右子树中的结点。但本算法中，p的祖先结点的输出顺序为：p的父结点、祖父结点……最后输出根结点。khdaw.com⑵可以从另一个角度来求解这个问题。根据祖先结点的定义，如果结点r是p的祖先，那么必须满足下列条件之一：①p为r的左孩子或右孩子；②r的左孩子或右孩子为p的祖先。根据这个思路可编写递归算法如下：intAncestor(BiTreeBT,BiTreep){课后答案网if(!BT)return0;if(BT->lchild==p||BT->rchild==p||Ancestor(BT->lchild,p)||Ancestor(BT->rchild,p))www.hackshp.cn{cout<data<<"";return1;}return0;}⑶本题也可采用非递归后序遍历二叉树来实现，当后序遍历访问到p时，栈中所有结点均为p的祖先结点。7．利用后序遍历二叉树的非递归遍历算法。为了叙述方便，不妨假定p比q先进栈，当p进栈时，栈中的结点均为p的祖先，此时可用变量pos保存p在栈中的位置，然后继续进行后序遍历，直到q进栈。在这个过程中，如果pos位置上的元素需要出栈，那么将pos指向栈中前一个元素的位置，以保证pos位置上的元素一定是当前栈中距离p最近的祖先结点，那么当q进栈时，同样栈中结点均为q的祖先。因此，pos位置上的元素就是为包含p和q的最小子树的根结点。#defineMaxLen20//定义栈的最大空间，大于树的最大深度BiTreeMinTree(BiTreeBT,BiTreep,BiTreeq){BiTreestack[MaxLen+1],r;intpos=0,top=0;r=BT;khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com do{while(r){stack[++top]=r;if(r==p||r==q)if(pos==0)pos=top;//第一个结点进栈elsereturn(stack[pos]);//第二个结点进栈r=r->lchild;}while(top>0&&stack[top]->rchild==r){if(pos==top)pos--;//pos位置上的元素需要出栈r=stack[top--];//栈顶结点出栈khdaw.com}if(top>0)r=stack[top]->rchild;//开始遍历右子树}while(top>0);returnNULL;}8．可以借鉴对中序线索二叉树进行遍历的思想，即先找到中序序列的第一个结点，然课后答案网后依次找结点的后继。在二叉树的中序序列中，第一个结点为二叉树中最左边的结点，即从根结点开始，沿结点的左指针向下查找，直到左指针为空。而对于二叉树中的任何一个结点p，可分下列两种情况来找www.hackshp.cnp的后继：⑴若p的右子树不为空，则p的后继为其右子树的中序序列的第一个结点；⑵否则，沿p的双亲指针向上查找p的祖先，直到找到第一个在左子树中包含p结点的祖先，这个祖先结点则为p的后继。根据这个思想，可编写算法如下：voidInOrder(PBiTreeBT,voidVisit(TElemType)){PBiTreep,q;if(!BT)return;p=BT;while(p->lchild)//找中序序列的第一个结点p=p->lchild;while(p){Visit(p->data);//访问结点if(p->rchild)//在p的右子树中找p的后继{p=p->rchild;while(p->lchild)p=p->lchild;}else//在p的祖先中找p的后继khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com {q=p;p=q->parent;while(p&&p->lchild!=q){q=p;p=q->parent;}}}}进一步讨论：（1）在这种存储结构中，由于每个结点增加了一个指向双亲结点的指针，利用这个指针和左、右孩子指针可以找到一个结点的后继。本算法正是利用这个特点来实现中序遍历的。因此，如果在二叉树中的一种存储结构中，如果能够由一个结点找到其左、右khdaw.com孩子及双亲结点（如二叉树的顺序存储结构），那么就可以不用栈实现中序遍历。按照这个算法的思路，也可以在这种存储结构下编写不设栈进行前序和后序遍历的非递归算法。在二叉树的前序序列中，第一个结点为根结点，而一个结点p的后继可按下列方法找到：①若p的左子树不为空，则后继为其左孩子；②若p的左子树为空但右子树不为空，则后继为其右孩子；课后答案网③否则，沿p的双亲指针一直向上找到这样一个祖先f，使得f的左子树中包含p，且f的右子树不为空。则f的左孩子为p的后继。算法描述如下：www.hackshp.cnvoidPreOrder(PBiTreeBT,voidVisit(TElemType)){PBiTreep,q;if(!BT)return;p=BT;while(p){Visit(p->data);if(p->lchild)p=p->lchild;elseif(p->rchild)p=p->rchild;else{q=p;p=q->parent;while(p&&(p->lchild!=q||!p->rchild)){q=p;p=q->parent;}if(p)p=p->rchild;}khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com }}在二叉树的后序序列中，第一个结点为左边的叶子结点，即从根结点开始，若结点的左子树不空，则沿左指针向下查找，否则沿右指针向下查找，直到叶子结点。而一个结点p的后继可按下列方法找到：①若p是其双亲的右孩子或是其双亲的左孩子且其双亲没有右孩子，则其后继即为双亲结点；②若p是其双亲的左孩子且其双亲的右子树不空，则其后继为双亲右子树上按后序遍历的第一个结点；算法描述如下：voidPostOrder(PBiTreeBT,voidVisit(TElemType)){PBiTreep,q;khdaw.comif(!BT)return;p=BT;while(p->lchild||p->rchild)//找后序序列的第一个结点if(p->lchild)p=p->lchild;elseif(p->rchild)p=p->rchild;while(p){课后答案网Visit(p->data);q=p;www.hackshp.cnp=q->parent;if(p&&p->lchild==q&&p->rchild){p=p->rchild;while(p->lchild||p->rchild)if(p->lchild)p=p->lchild;elseif(p->rchild)p=p->rchild;}}}khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 习题十一、选择题1．D2．B3．A4．D5．C6．B7．A8．D二、填空题1．操作系统文件数据库2.单关键字文件多关键字文件3．顺序组织索引组织哈希组织链组织4．第i-15．索引集顺序集数据集6．随机7．提高查找速度khdaw.com8．分配和释放存储空间重组对插入的记录9．逻辑顺序和物理顺序10．主关键字三、简述题1．解答：⑴顺序结构，相应文件为顺序文件，其记录按存入文件的先后次序顺序存放。顺序文件课后答案网本质上就是顺序表。若逻辑上相邻的两个记录在存储位置上相邻，则为连续文件；若记录之间以指针相链接，则称为串联文件。顺序文件只能顺序存取，要更新某个记录，必须复制整个文件。顺序文件连续存取的速度快，主要适用于顺序存取，批量修改的情况。www.hackshp.cn⑵带索引的结构，相应文件为索引文件。索引文件包括索引表和数据表，索引表中的索引项包括数据表中数据的关键字和相应地址，索引表有序，其物理顺序体现了文件的逻辑次序，实现了文件的线性结构。索引文件只能是磁盘文件，既能顺序存取，又能隋机存取。⑶散列结构，也称计算寻址结构，相应文件称为散列（哈希）文件，其记录是根据关键字值经散列函数计算确定其地址，存取速度快，不需索引，节省存储空间。不能顺序存取，只能随机存取。其它文件均由以上文件派生而得。文件采用何种存储结构应综合考虑各种因素，如：存储介质类型、记录的类型、大小和关键字的数目以及对文件作何种操作。2．解答在主文件外，再建立索引表指示关键字及其物理记录的地址间一一对应关系。这种由索引表和主文件一起构成的文件称为索引文件。索引表依关键字有序。主文件若按关键字有序称为索引顺序文件，否则称为索引非顺序文件（通常简称索引文件）。索引顺序文件因主文件有序，一般用稀疏索引，占用空间较少。常用索引顺序文件有ISAM和VSAM。ISAM采用静态索引结构，而VSAM采用B+树的动态索引结构。索引文件既能顺序存取，也能随机存取。3．解答：ISAM是专为磁盘存取设计的文件组织方式。即使主文件关键字有序，但因磁盘是以盘组、柱面和磁道（盘面）三级地址存取的设备，因此通常对磁盘上的数据文件建立盘组、柱面和磁道（盘面）三级索引。在ISAM文件上检索记录时，先从主索引（柱面索引的索引）khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 找到相应柱面索引。再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直到查到为止；反之，若找遍该磁道而未找到所查记录，则文件中无此记录。4．解答：ISAM是一种专为磁盘存取设计的文件组织形式，采用静态索引结构，对磁盘上的数据文件建立盘组、柱面、磁道三级索引。ISAM文件中记录按关键字顺序存放，插入记录时需移动记录并将同一磁道上最后的一个记录移至溢出区，同时修改磁道索引项，删除记录只需在存储位置作标记，不需移动记录和修改指针。经过多次插入和删除记录后，文件结构变得不合理，需周期整理ISAM文件。VSAM文件采用B+树动态索引结构，文件只有控制区间和控制区域等逻辑存储单位，与外存储器中柱面、磁道等具体存储单位没有必然联系。VSAM文件结构包括索引集、顺序集和数据集三部分，记录存于数据集中，顺序集和索引集构成B+树，作为文件的索引部分可实现顺链查找和从根结点开始的随机查找。khdaw.com与ISAM文件相比，VSAM文件有如下优点：动态分配和释放存储空间，不需对文件进行重组；能保持较高的查找效率，且查找先后插入记录所需时间相同。因此，基于B+树的VSAM文件通常作为大型索引顺序文件的标准组织。5．解答：多重表文件是把索引与链接结合而形成的组织方式。记录按主关键字顺序构成一个串联课后答案网文件，建立主关键字的索引（主索引）。对每一次关键字建立次关键字索引，具有同一关键字的记录构成一个链表。主索引为非稠密索引，次索引为稠密索引，每个索引项包括次关键字，头指针和链表长度。多重表文件易于编程，也易于插入，但删除繁锁。需在各次关键字www.hackshp.cn链表中删除。倒排文件是一种多关键字的文件，主数据文件按关键字顺序构成串联文件，并建立主关键字索引。对次关键字也建立索引，该索引称为倒排表。倒排表包括两项，一项是次关键字，另一项是具有同一次关键字值的记录的物理记录号（若数据文件非串联文件，而是索引顺序文件—如ISAM，则倒排表中存放记录的主关键字而不是物理记录号）。倒排表作索引的优点是索引记录快，缺点是维护困难。在同一索引表中，不同的关键字其记录数不同，各倒排表的长度不同，同一倒排表中各项长度也不相等。6．解答：倒排表有两项，一是次关键字值，二是具有相同次关键字值的物理记录号，这些记录号有序且顺序存储，不使用多重表中的指针链接，因而节省了空间。7．解答：⑴顺序文件只能顺序查找，优点是批量检索速度快，不适于单个记录的检索。顺序文件不能象顺序表那样插入、删除和修改，因文件中的记录不能象向量空间中的元素那样“移动”，只能通过复制整个文件实现上述操作。⑵索引非顺序文件适合随机存取，不适合顺序存取，因主关键字未排序，若顺序存取会引起磁头频繁移动。索引顺序文件是最常用的文件组织，因主文件有序，既可顺序存取也可随机存取。索引非顺序文件是稠密索引，可以“预查找”，索引顺序文件是稀疏索引，不能“预查找”，但由于索引占空间较少，管理要求低，提高了索引的查找速度。⑶散列文件也称直接存取文件，根据关键字的散列函数值和处理冲突的方法，将记录散khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 列到外存上。这种文件组织只适用于像磁盘那样的直接存取设备，其优点是文件随机存放，记录不必排序，插入、删除方便，存取速度快，无需索引区，节省存储空间。缺点是散列文件不能顺序存取，且只限于简单查询。经多次插入、删除后，文件结构不合理，需重组文件，但这个工作是很费时的。8．解答：类似最优二叉树（哈夫曼树），可先合并含较少记录的文件，后合并较多记录的文件，使移动次数减少。见下面的哈夫曼树。khdaw.com图10.1哈夫曼树9．解答：多重表文件如图10.2所示：课后答案网www.hackshp.cn图10.2多重表文件及索引文件khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com 10．解答：主索引及相应的倒排索引如图10.3所示：khdaw.com课后答案网www.hackshp.cn图10.3倒排文件在图10.3中进行题中的各类搜索，其结果如下：⑴男性职工（搜索性别倒排表）：{10032,10104,10140,10176,10212}⑵月工资超过900的职工（搜索工资倒排表）：{10176,10248,10068,10140,10320}⑶月工资超过平均工资的职工（搜索工资倒排表）：月平均工资为901元，所以结果与⑵一样。⑷职业为实验员的男性职工（搜索职业和性别倒排表）：{10104，10284}∩{10032，10104，10140，10176，10212}={10104}⑸年龄超过30岁且职业为实验员或教师的女性职工（搜索性别和年龄倒排表）：{10068,10248,10284,10320}∩{10320,10068,10104,10212,10284}={10320,10068,10284}khdaw.com若侵犯了您的版权利益，敬请来信通知我们！℡www.khdaw.com'