数据结构与算法习题答案.doc

数据结构与算法习题答案习题一P18二 单项选择题1-6 DCCCD D三 填空题1. 元素，元素，系统 2. 集合，线性，树，图 3. 顺序，链4. 完整，一个事实 5. 指针， 6. 算法，数据结构7. 可行性，确定性，有穷性，有输入，有输出四 问答题1. 设计数据的物理结构时，重点解决的问题是什么？答：设计数据的物理结构时，重点解决的问题有两个：一个是有效存储问题，既要考虑有利于程序的处理，又要考虑存储空间的有效利用；另一个问题是逻辑结构的问题，既要考虑数据的有效存储，又要考虑物理结构和逻辑结构之间能否相互无误的转换。2. 顺序存储结构和链存储结构对存储空间的各有什么要求？答：顺序存储结构要求有足够的连续的存储空间；而链存储结构的存储空间可以是离散的不连续的存储空间。4. 算法与程序最显著的区别是什么？答：算法与程序最显著的区别是：第一，算法必须是有穷的，而程序不一定是有穷的；第二，程序是可以直接在计算机上执行的，而算法必须采用程序设计语言转换为程序才能在计算机上执行。习题二P55二 单项选择题1-8 CCBDC CBC三 填空题1. 3510 2. 上溢 3. 元素，系统4. 通过P指向已引用的结点，引用结点P的数据域，引用结点P的指针域 5. 数据项的组合顺序，第一个数据项 6. 排序对象，排序标准，排序方向，排序操作，排序结果7. 结点交换8. 大于 9. 头，尾四 问答题4. 为什么在删除单链表的第i个结点时，却要查找到第i-1个结点？答：因为单链表是通过指针进行连接的。当要删除第i个结点时，必须将第i-1个结点和第i+1个结点连接起来，也就是使第i-1个结点的指针指向第i+1个结点，因此必须查找第i-1个结点，从而得到其指针。6. 在查找表的端点设置“哨兵”结点为什么能提高查找算法的时间效率？答：因为哨兵结点具有监视查找终止的作用，增加哨兵结点后可以一边查找一边移动，不会造成结点丢失。8. 排序关键字和查找关键字有什么关系吗？答：排序关键字和查找关键字都是关键字，都可以由一个或者多个数据项组成。但是排序关键字中，数据项的排序顺序会影响排列结构；而查找关键字中数据项的排序顺序对查找结果没有任何影响。五 算法设计题5. 设有非空带头结点的单链表L，结点数据域为整数key、指针域为next, 结点顺序是关于关键字key有序。试设计一个顺序查找算法，根据给定值k在L中查找与k等值的结点并输出结点数据。用非形式语言写出算法描述，并编写C程序。答：算法描述：算法LES设有单链表L,结点关键字域为整型key,指针为next,且L关于关键字key有序，p为指针变量，给定值为k。算法查找给定值k标识的结点数据。LES1.初始化p=next(L)；LES2.结束？若p=NULL，则转LES4继续；LES3.比较若 key(p)k,pnext(p),转LES2继续；LES4. 输出data(p)，算法终止。C语言程序：int LES(LINKLIST *L, int key) LINKLIST *p; P=L-next;while(p!=NULL&p-data!=key)p=p-next;return data(p);习题三P85二 单项选择题1-5 CBACB 6-10 BABBA 11-14 BABB三 填空题1. 后进先出 2. 删除 3. 删除，同一端4. NULL，下溢出 5. 312，123 1326.front=mod(rear+1,m), rear=front 7. top+1四 问答题2. 在3.1.4节的第一个应用实例中，若车厢按1、2、3、4的次序进入调度岔道，能编组为按4、3、1、2的次序开出吗？如果不能请说明理由。还有哪些开出次序也是不能的？答：如果按1、2、3、4的次序进入调度岔道，不能编组为按4、3、1、2的次序开出，因为车厢编组调度的过程跟出入栈类似，必须按照后进先出的次序重新编组。不可能的开出次序还有1423，2413，3124，3142，3412，4132，4123，4213，4231。3. 对顺序栈结构，“栈底”一定要设置在数组的低下标端吗？答：顺序栈结构的“栈底”也可以设置在数组的高下标端。因为数组是顺序存储结构，顺序栈也是顺序存储结构。当栈底设置在数组的高下标端时，当有元素入栈时栈顶指针递减，当有元素出栈时栈顶指针递增。五 算法设计题2. 设有两个顺序栈A、B，最大程度分别为m,n,且mn。已知该两栈在运行过程中现行长度之和不超过m。问如何设计这两个栈空间最省？写出两个栈的压入和弹出操作的算法描述和C语言程序。答：因为两栈在运行过程中现行长度之和不超过其中一个栈的长度m，因此当两栈共用一个长度为m的一维数组存储时，空间最省。算法描述：顺序栈A、B共用一个一维数组spacem进行存储，栈A的栈底为space0，栈B的栈底为spacem-1，栈A的栈指针为topA，栈B的栈指针为topB。x为字符型变量。对栈A的压入和弹出操作算法PUSSTACKA：把x压入栈SA。PUSSTACKA1：栈上溢？ 若topA+topB=m, output(“overflow”)，算法终止。PUSSTACKA2：插入x 若topA+, SAtopA=x，算法终止。C语言程序：SEQSTACK PUSSTACKA(SEQSTACK SA, SEQSTACK SB, char x)if(SB.topB-SA.topA= 1)printf(“overflow!”);elseSA.topA+;SA.dataSA.topA=x;return SA;算法POPSTACKA：删除栈SA的栈顶结点。POPSTACKA1：栈下溢？ 若topA=0, output(“empty”)，算法终止。POPSTACKA2：删除栈顶 若topA-,算法终止。C语言程序：SEQSTACK POPSTACKA(SEQSTACK SA)if(SA.topA= 0)printf(“empty!”);elseSA.topA-;return SA;对栈B的压入和弹出操作算法PUSSTACKB：把x压入栈SB。PUSSTACKB1：栈上溢？ 若topA+topB=m, output(“overflow”)，算法终止。PUSSTACKB2：插入x 若topB-, SBtopB=x，算法终止。C语言程序：SEQSTACK PUSSTACKB(SEQSTACK SA, SEQSTACK SB, char x)if(SB.topB-SA.topA= 1)printf(“overflow!”);elseSB.topB-;SB.dataSB.topB=x;return SB;算法POPSTACKB：删除栈SB的栈顶结点。POPSTACKB1：栈下溢？ 若topB=m-1, output(“empty”)，算法终止。POPSTACKB2：删除栈顶 若topB+,算法终止。C语言程序：SEQSTACK POPSTACKB(SEQSTACK SB)if(SA.topB= m-1)printf(“empty!”);elseSB.topB+;return SB;习题四P107二 单项选择题1-6 CBACB B三 填空题1. 1 2. 0，空格字符的个数 3. data structure.4. ASCII 5. 堆串，空间6. 动态7. 存储位置 8. 2146 9. 上三角，下三角，对角线，对称，稀疏四 问答题3. 设有一个二维数组A5，10(c语言表示)。若=1088, =1132. 试求=？ 答：1）每个数组元素占用的存储空间为： (-) / 11 = (1132-1088)/11= 4 2） =+12*4=1132+48=1180 或者=+23*4=1088+92=1180 五 算法设计题3. 设有一个nn阶上三角形矩阵，存储为一维数组。试设计出该矩阵元素的地址计算公式。答：矩阵元素表示为Aij，因为是上上三角形矩阵，即 当ij 时Aij=0；当i=j时，Aij0。设矩阵的首地址为A0，每个元素占用b个存储单元，则 = A0 + k + j - ib其中k = n + (n-1) + (n-2) + + (n- (i-1) = i* (2n-i+1)/2习题五P139二 单项选择题1-4 CDDC三 填空题1. 层次性 分支性 2. 先根遍历，后根遍历，层次遍历 3. 68，16，524. 4 5. 整，指针五 思考题3. 设二叉树的中根遍历序序列是CDBAFEHG，先根遍历序列是ABCDEFGH。试画出该二叉树。 ABECFGDH答： 后根遍历序列为DCBFHGEA六 算法设计题3. 编写一个后根遍历二叉树的算法和C语言程序。算法描述：算法（LDRT）:已知二叉树BT存储为二叉链表。设指针变量tp,栈BS为顺序存储结构，top为栈顶指针，初值为0. LDRT1.初始化top=0,tp=BT LDRT2.tp为空若tp=NULL,则转DLRT4继续LDRT3.压栈-左行BS=PUSSTACK(BS,tp),tp=llinktp,则转LDRT2继续LDRT4.弹栈若top=0,则算法结束；否则tp=GETSTACK(BS),BS=POPSTACK(BS) LDRT5.访问-右行output(datatp) ,tp=rlinktp,转LDRT2继续。C语言程序栈结构的定义tpyedef struct BTNODE *pointer100; int top;PSTACK;遍历二叉树的C语言程序void LDRTRAVEL(BTNODE *BT)BTNODE *tp=BT; /p表示当前结点， PSTACK BS; /栈BS用来存储结点int tagMAX;BS=INISTACK();dowhile(tp != NULL)/先处理结点的左孩子结点，把所有左孩子依次入栈 BS=PUSSTACK(BS,tp);tagtop = 0;p = p-lchild; if(top 0) /所有左孩子处理完毕后 if(!tagtop) /如果当前结点的右孩子还没被访问tp = GETSTACK(BS);/输出栈顶结点 ，但不退栈 ，因为要先输出其孩子结点 tp = tp-rchild; /处理其右孩子结点 tagtop = 1; /栈中top结点的右孩子被访问过了，下次轮到它退栈时可直接输出else /如果该结点的左右孩子都被访问过了 BS=POPSTACK(BS);printf(%d, tp-data); /栈顶元素出栈，输出该结点，此时结点p指向NULL while(tp != NULL)|(top 0);习题六P155二 单项选择题1-8 BBCBD ADC习题七P183二 单项选择题1-5 CBACD三 填空题1. 1,0 2. G的极大强联通子图 3. n(n-1)4. Kruskal 5. 递增，相等 6. G中是否有环 7. n (n-1)/2四 问答题2. 无向图采用邻接矩阵表示，如何判断图中有多少边、任意一个顶点的