离散数学课件总复习之习题讲解

数据结构重点题型与课后题讲解,2012年秋季,各内容重点题型讲解作业中易错题讲解课后练习讲解,各内容重点题型讲解,P862.22,设在一个带附加头结点的单链表中所有元素结点的数据值按递增顺序排列，试编写一个函数，删除表中所有大于min，小于max的元素（若存在）。,温习：,（1）带附加结点的单链表的结构,（2）单链表的删除,q=p-link;p-link=q-link;deleteq;,参考解析：,templatevoidrangeDelete(List,P1333.22,假设以数组Qm存放循环队列中的元素，同时以rear和length分别指示循环队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的对空条件和队满条件，并写出相应的插入（EnQueue）和删除（DlQueue）元素的操作。,温习：,（1）循环队列结构,0,1,2,3,4,5,6,7,front,A,B,C,rear,（3）循环队列插入,（4）循环队列删除,存入存放循环队列元素的数组elementsrear=x;尾指针加一rear=(rear+1)%maxSize;,取队头元素x=elementsfront;队头指针加一front=(front+1)%maxSize;,（2）循环队列对空条件与队满条件,队空条件：front=rear;队满条件：(rear+1)%maxSize=front；,参考解析：,#include#include“Queue.h”templateclassSeqQueue:publicQueue/循环队列的类定义protected:intrear,length;/队尾指针与队列长度T*elements;/队列存放数组intmaxSize;/队列最大容量public:SeqQueue(intsize=100);/构造函数SeqQueue()deleteelements;/析构函数boolEnQueue(Tx);/新元素进队列boolDeQueue(T,templateSeqQueue:SeqQueue(intsize):rear(0),length(0),maxSize(size)/构造函数：建立一个最大具有maxSize个元素的空队列elements=newTsize;assert(elements!=NULL);templateboolSeqQueue:EnQueue(Tx)/若队列不满,则将x插入到该队列队尾,否则返回falseif(IsFull()=true)returnfalse;/判队列是否已满，满则返回falseelementsrear=x;/先存入rear=(rear+1)%maxSize;/尾指针加一length+;/队列长度加1returntrue;templateboolSeqQueue:DeQueue(T,P1854.13,所谓回文，是指从前向后顺读和从后向前倒读都一样的不含空白字符的串。例如did，madamimadam，pop即是回文。试编写一个算法，以判断一个串是否是回文。,解法一（基于字符串的顺序存储）算法思想：从数组两头向中间并进，检查对应字符是否相等，直到中间会合。,#includeAstring.hboolpalindrome(AString,解法二（基于字符串的单链表存储结构）算法思想：利用栈。先把字符串所有元素进栈，再逐个退栈与从头遍历链表同时进行，都相等说明是回文。,#includeLinkedStack.hboolpalindrome(AString,P2485.18,已知一棵二叉树的前序遍历的结果是ABECDFGHIJ，中序遍历的结果是EBCDAFHIGJ，试画出这颗二叉树。,温习：,前序遍历：根左右中序遍历：左根右后序遍历：左右根,前序,参考解析：,C,B,E,A,D,F,G,H,I,J,中序,D,B,C,E,A,F,H,I,G,J,D,B,C,E,F,H,I,G,J,D,C,H,I,G,J,H,I,e,E,G,D,H,J,I,P2485.20,假定用于通信的电文仅由8个字母c1,c2,c3,c4,c5,c6,c7,c8组成，各字母在电文中出现的频率分别为5,25,3,6,10,11,36,4。试为这8个字母设计不等长Huffman编码，并给出该电文的总码数。,温习：,Huffman树：WPL最小的二叉树，也是权值大的外结点离根结点最近的扩充二叉树。,参考解析：,思路：每个结点看做一棵树，找权值最小的两棵树合为一棵树。,6,25,3,5,10,11,36,4,c1,c2,c3,c4,c5,c6,c7,c8,6,25,3,5,10,11,36,4,c1,c2,c3,c4,c5,c6,c7,c8,7,6,25,3,5,10,11,36,4,c1,c2,c3,c4,c5,c6,c7,c8,7,11,6,25,3,5,10,11,36,4,c1,c2,c3,c4,c5,c6,c7,c8,7,11,17,6,25,3,5,10,11,36,4,c1,c2,c3,c4,c5,c6,c7,c8,7,11,17,22,6,25,3,5,10,11,36,4,c1,c2,c3,c4,c5,c6,c7,c8,7,11,17,22,39,6,25,3,5,10,11,36,4,c1,c2,c3,c4,c5,c6,c7,c8,7,11,17,22,39,61,6,25,3,5,10,11,36,4,c1,c2,c3,c4,c5,c6,c7,c8,7,11,17,22,39,61,100,0,0,0,0,0,0,0,1,1,1,1,1,1,1,电文总码数：45225434631031123644257,P2956.9,设散列表为HT13，散列函数H(key)=key%13，用闭散列法解决冲突，对下列关键码序列12,23,45,57,20,03,78,31,15,36造表。（1）采用线性探查法寻找下一个空位，画出相应的散列表，并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。（2）采用双散列法寻找下一个空位，再散列函数RH(key)=(7*key)%10+1，寻找下一个空位的公式为Hi（Hi-1RH(key)）%13，H1=H(key)。画出相应的散列表，并计算等概率下搜索成功的平均搜索长度。,温习：,Hi（k）=（H0（k）+di）modm（i=1,2,.k（km-1）,其中，每次再探测时的地址增量di可以有不同的取值：（1）di=1，2，3，.；线性探测法（2）di=12，-12，22，-22.；二次探测法（3）di=伪随机序列；伪随机再散列如：双散列法Hi（H0ReHash(key)）%m,参考解析：,（1）线性探查法（设H1=H（key）若发生冲突，则调用Hi（k）=（H1（k）+di）%13（di=1,2,）由散列函数H(key)=key%13可得:H1(12)=12%13=12H1(23)=23%13=10H1(45)=45%13=6H1(57)=57%13=5H1(20)=20%13=7H1(03)=3%13=3H1(78)=78%13=0H1(31)=31%13=5（发生冲突）H2(31)=（5+1）%13=6（发生冲突）H3(31)=（6+1）%13=7（发生冲突）H4(31)=（7+1）%13=8（成功）H1(15)=15%13=2H1(36)=36%13=10（发生冲突）H2(36)=（10+1）%13=11（成功）,1,2,3,5,6,7,9,10,11,23,57,ASL成功=（1+1+1+1+1+1+1+4+1+2）/10=14/10ASL不成功=（2+1+3+2+1+5+4+3+2+1+5+4+3）/13=36/13,（2）双散列法（设H1=H（key）若发生冲突，则调用Hi（k）=（Hi-1（k）+RH(key)）%13，RH(key)=(7*key)%10+1由散列函数H(key)=key%13可得:H1(12)=12%13=12H1(23)=23%13=10H1(45)=45%13=6H1(57)=57%13=5H1(20)=20%13=7H1(03)=3%13=3H1(78)=78%13=0H1(31)=31%13=5（发生冲突）RH(31)=(731)%10+1=8H2(31)=（5+8）%13=0（发生冲突）H3(31)=（0+8）%13=8（成功）H1(15)=15%13=2H1(36)=36%13=10（发生冲突）RH(36)=(736)%10+1=3H2(36)=（10+3）%13=0（发生冲突）H3(36)=（0+3）%13=3（发生冲突）H4(36)=（3+3）%13=6（发生冲突）H4(36)=（6+3）%13=9（成功）,1,2,3,5,6,7,9,10,11,23,57,ASL成功=（1+1+1+1+1+1+1+3+1+5）/10=16/10,31,15,36,P3028.10,对于如下图所示的有向图，试写出：（1）从顶点出发进行深度优先搜索所得到的深度优先生成树（DFS树）；（2）从顶点出发进行广度优先搜索所得到的广度优先生成树。,温习：,深度优先搜索：不断探查和回溯广度优先搜索：逐层遍历,4,2,3,1,5,参考解析：,4,2,3,1,5,4,2,3,1,5,4,2,3,1,5,深度优先搜索,广度优先搜索,P3178.24,以下图为例，按Dijkstra算法计算得到的从顶点A到其他各个顶点的最短路径和最短路径长度。,温习：,Dijkstra算法是最短路径算法之一。具体做法：用一个集合S存放已经求得最短路径的终点。初始状态时，集合S只有一个源点v0，以后每次求得一条最短路径，就将其终点vk加入集合S，且可证明：下一条最短路径必然是从v0出发，中间只经过S中的顶点便可到达的那些顶点vx(vxV-S)的路径中的一条，直至全部顶点都加入到集合S中。,D,B,C,A,E,2,18,5,5,2,2,10,D,B,C,A,E,2,18,5,5,2,2,10,参考解析：,D,B,C,A,E,2,18,5,5,2,2,10,D,B,C,A,E,2,18,5,5,2,2,10,D,B,C,A,E,2,18,5,5,2,2,10,D,B,C,A,E,2,18,5,5,2,2,10,P3437.15,将关键码DEC,FEB,NOV,OCT,JUL,SEP,AUG,APR,MAR,MAY,JUN,JAN依次插入一棵初始为空的AVL树中，画出每插入一个关键码后的AVL树，并标明平衡旋转的类型。,温习：,（1）AVL树如果T是一棵非空的二叉搜索树，TL和TR分别是其左子树和右子树，那么当T满足以下条件时，T是一棵AVL树：1）TL和TR是AVL树；2）|hR-hL|1，hL和hR分别是左子树和右子树的高度，即平衡因子只能取0,1和-1。二叉搜索树：1）每个结点都有一个作为搜索依据的关键码(key)，所有结点的关键码互不相同，都是唯一的；2）左子树（如果非空）上所有结点的关键码都小于根结点的关键码。3）右子树（如果非空）上所有结点的关键码都大于根结点的关键码。,（2）平衡化旋转从插入位置沿通向根的路径回溯，检查各节点的平衡因子，从发生不平衡的节点起，沿刚才回溯的路径取直接下两层的节点，做平衡化旋转。,A,RR,C,LL,C,A,B,B,A,B,C,C,B,A,A,C,LR,RL,NOV,DEC,DEC,FEB,DEC,FEB,+2,FEB,NOV,DEC,FEB,NOV,DEC,OCT,RR,FEB,NOV,DEC,OCT,JUL,FEB,NOV,DEC,OCT,JUL,SEP,+2,NOV,OCT,FEB,SEP,JUL,DEC,RR,参考解析：,FEB,JUL,AUG,JUN,DEC,APR,NOV,OCT,MAY,SEP,MAR,JAN,P4409.2,设待排序的排序码序列为12,2,16,30,28,10,16*，20,6,18，试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次排序码比较。（1）直接插入排序（2）希尔排序（增量为5,2,1）（3）起泡排序（4）快速排序（5）简单选择排序（6）锦标赛排序（7）堆排序（8）二路归并排序（9）基数排序,温习：,排序：插入排序：直接插入排序、折半插入排序、希尔排序交换排序：起泡排序、快速排序选择排序：直接选择排序、堆排序归并排序,参考解析（以希尔排序为例）：,30,2,16,12,28,10,16*,20,6,18,d=5,12,10,2,16*,16,20,30,6,28,18,6,2,16,10,18,12,16*,20,30,28,结果,排序码比较次数：1+1+1+1+1=5,6,2,16,10,18,12,16*,20,30,28,d=2,16,10,18,16*,30,6,2,12,20,28,6,2,16,10,16*,12,18,20,30,28,结果,排序码比较次数：（1+1+2+1）+（1+1+1+1）=9,6,2,16,10,16*,12,18,20,30,28,d=1,16,6,10,2,16*,12,18,20,28,30,结果,排序码比较次数：1+1+3+1+3+1+1+1+2=14,易错题讲解,/C+基础问题P381.10（3）P391.12（1）/栈的利用P1323.16（2）/矩阵的压缩存储P1834.4,P1323.16（2）,已知Ackerman函数定义如下：n+1当m=0时akm(m,n)=akm(m-1,1)当m0，n=0时akm(m-1,akm(m,n-1)当m0，n0时（2）利用栈，写出它的非递归求解算法。,解析（以m=2,n=1为例分析）：,akm(2,1)=akm(1,akm(2,0),akm(2,0)=akm(1,1),akm(1,1)=akm(0,akm(1,0),akm(1,0)=akm(0,1),akm(0,1)=2,2,2,=3,3,3,akm(1,3)=akm(0,akm(1,2),akm(1,2)=akm(0,akm(1,1),3,=4,4,=5,intAckerman(intm,intn)inti,j,k,top=-1;intSm10,Sn10;Sm+top=m;Sntop=n;/Sm和Sn是栈，top是栈顶指针while(1)i=Smtop;j=Sntop;top-;/出栈if(i=0)/m=0情形，结果为n+1k=j+1;if(top!=-1)Sntop=k;elsereturnk;elseif(j=0)/m0，n=0情形Sm+top=i-1;Sntop=1;elseSm+top=i-1;Smtop=i;Sntop=j-1;,P1834.4,设有三对角矩阵Ann，将其三条对角线上的元素逐行存储到数组B0：3n-3中，使得Bk=aij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i,j的下标变换公式。,解析：,若0in-1,则：k=(3i-1)+(j-i+1)=2i+ji=（k+1）/3取下整，j=k-2i,若1in,则：k=(3(i-1)-1)+(j-i+1)=2i+j-3i=（k+1）/3取下整+1，j=k-2i+3,课后练习讲解,1、已知有序表为（12，18，24，35，47，50，62，83，90，115，134）,当用折半搜索90时，需进行2次搜索可确定搜索成功；搜索40时需进行_4次搜索才能确定不成功。2、在双向链表存储结构中，删除p所指的结点时须修改指针（A）。Ap-llink-rlink=p-rlink;p-rlink-llink=p-llink;Bp-llink=p-llink-llink;p-llink-rlink=p;Cp-rlink-llink=p;p-rlink=p-rlink-rlinkDp-rlink=p-llink-llink;p-llink=p-rlink-rlink;,3、用I表示入栈操作，O表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的I和O操作串为（C）。AIIOOIIOOBIOIOIIOOCIOIIOIOODIOIIOOIO4、数组A0.5,0.6的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A5，5的地址是（A）。A1175B1180C1205D1210,5、已知一棵完全二叉树中共有768结