《离散数学课件总复习之习题讲解.ppt》由会员分享，可在线阅读，更多相关《离散数学课件总复习之习题讲解.ppt（45页珍藏版）》请在三一办公上搜索。
1、数据结构重点题型与课后题讲解,2012年秋季,各内容重点题型讲解作业中易错题讲解课后练习讲解,各内容重点题型讲解,P86 2.22,设在一个带附加头结点的单链表中所有元素结点的数据值按递增顺序排列，试编写一个函数，删除表中所有大于min，小于max的元素（若存在）。,温习：,（1）带附加结点的单链表的结构,（2）单链表的删除,q=p-link;p-link=q-link;delete q;,参考解析：,templatevoid rangeDelete(List,P133 3.22,假设以数组Qm存放循环队列中的元素，同时以rear和length分别指示循环队列中的队尾位置和队列中所含元素的个数
2、。试给出该循环队列的对空条件和队满条件，并写出相应的插入（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；,参考解
3、析：,#include#include“Queue.h”template class SeqQueue:public Queue/循环队列的类定义 protected:int rear,length;/队尾指针与队列长度 T*elements;/队列存放数组 int maxSize;/队列最大容量public:SeqQueue(int size=100);/构造函数 SeqQueue()delete elements;/析构函数 bool EnQueue(T x);/新元素进队列 bool DeQueue(T,template SeqQueue:SeqQueue(int size):rear(
4、0),length(0),maxSize(size)/构造函数：建立一个最大具有maxSize个元素的空队列 elements=new Tsize;assert(elements!=NULL);template bool SeqQueue:EnQueue(T x)/若队列不满,则将x插入到该队列队尾,否则返回false if(IsFull()=true)return false;/判队列是否已满，满则返回false elementsrear=x;/先存入 rear=(rear+1)%maxSize;/尾指针加一 length+;/队列长度加1 return true;template bool
5、 SeqQueue:DeQueue(T,P185 4.13,所谓回文，是指从前向后顺读和从后向前倒读都一样的不含空白字符的串。例如did，madamimadam，pop即是回文。试编写一个算法，以判断一个串是否是回文。,解法一（基于字符串的顺序存储）算法思想：从数组两头向中间并进，检查对应字符是否相等，直到中间会合。,#include Astring.hbool palindrome(AString,解法二（基于字符串的单链表存储结构）算法思想：利用栈。先把字符串所有元素进栈，再逐个退栈与从头遍历链表同时进行，都相等说明是回文。,#include LinkedStack.hbool palin
6、drome(AString,P248 5.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,P248 5.20,假定用于通信的电文仅由8个字母c1,c2,c3,c4,c5,c6,c7,c8组成，各字母在电文中出现的频率分别为5,25,3,6,10,11,36,4。试为这8个
7、字母设计不等长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
8、,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,电文总码数：45 225 43 46 310 311 236 4
9、4257,P295 6.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）mod m（i=1,2,.k（km
10、-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=12 H1(23)=23%13=10 H1(45)=45%13=6 H1(57)=57%13=5 H1(20)=20%13=7 H1(03)=3%13=3 H1(78
11、)=78%13=0 H1(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=2 H1(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
12、-1（k）+RH(key)）%13，RH(key)=(7*key)%10+1 由散列函数H(key)=key%13可得:H1(12)=12%13=12 H1(23)=23%13=10 H1(45)=45%13=6 H1(57)=57%13=5 H1(20)=20%13=7 H1(03)=3%13=3 H1(78)=78%13=0 H1(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=2 H1(36)=36%13=10（发生冲突）RH(36)=(736)%10
13、+1=3 H2(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,P302 8.10,对于如下图所示的有向图，试写出：（1）从顶点出发进行深度优先搜索所得到的深度优先生成树（DFS树）；（2）从顶点出发进行广度优先搜索所得到的广度优先生成树。,温习：,深度优先搜索：不断探查和回溯广度优先搜索：逐层遍历,4,2,3,1,5,参考
14、解析：,4,2,3,1,5,4,2,3,1,5,4,2,3,1,5,深度优先搜索,广度优先搜索,P317 8.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
15、,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,P343 7.15,将关键码DEC,FEB,NOV,OCT,JUL,SEP,AUG,APR,MAR,MAY,JUN,JAN依次插入一棵初始为空的AVL树中，画出每插入一个关键码后的AVL树，并标明平衡旋转的类型。,温习：,（1）AVL树 如果T是一棵非空的二叉搜索树，TL和TR分别是其左子树和右子树，那么当T满足以下条件时，T是
16、一棵AVL树：1）TL和TR 是AVL树；2）|hR-hL|1，hL和hR分别是左子树和右子树的高度，即平衡因子只能取0,1和-1。二叉搜索树：1）每个结点都有一个作为搜索依据的关键码(key)，所有结点的关键码互不相同，都是唯一的；2）左子树（如果非空）上所有结点的关键码都小于根结点的关键码。3）右子树（如果非空）上所有结点的关键码都大于根结点的关键码。,（2）平衡化旋转 从插入位置沿通向根的路径回溯，检查各节点的平衡因子，从发生不平衡的节点起，沿刚才回溯的路径取直接下两层的节点，做平衡化旋转。,A,RR,C,LL,A,B,B,A,B,C,C,B,A,A,C,LR,RL,NOV,DEC,DE
17、C,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,P440 9.2,设待排序的排序码序列为12,2,16,30,28,10,16*，20,6,18，试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次排序码比较。（1）直接插入排序（2）希尔排序（增量为5,2,1）（3）起泡排序（4）快速排
18、序（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,
19、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+基础问题P38 1.10（3）P39 1.12（1）/栈的利用P132 3.16（2）/矩阵的压缩存储P183 4.4,P132 3.16（2）,已知Ackerman函数定义如下：n+1 当m=0时akm(m,n)=akm(m-1,1)当m0，n=0时 akm(m-1,akm(
20、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,int Ackerman(int m,int n)int i,j,k,top=-1;int Sm10,Sn10;Sm+top=m;Sntop=n;/Sm和Sn是栈，top
21、是栈顶指针 while(1)i=Smtop;j=Sntop;top-;/出栈 if(i=0)/m=0情形，结果为n+1 k=j+1;if(top!=-1)Sntop=k;else return k;else if(j=0)/m0，n=0情形 Sm+top=i-1;Sntop=1;else Sm+top=i-1;Smtop=i;Sntop=j-1;,P183 4.4,设有三对角矩阵Ann，将其三条对角线上的元素逐行存储到数组B0：3n-3中，使得Bk=aij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i,j的下标变换公式。,解析：,若0in-1,则：k=(3i-1)+(j-i+1)=
22、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）。A p-llink-rlink=p-rlink;p-rlink-llink=p-llink;B p-llink=p-llink-llink;p-llink-rlink=p;C
23、 p-rlink-llink=p;p-rlink=p-rlink-rlinkD p-rlink=p-llink-llink;p-llink=p-rlink-rlink;,3、用I表示入栈操作，O表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的I和O操作串为（C）。AIIOOIIOO BIOIOIIOO CIOIIOIOO DIOIIOOIO4、数组A0.5,0.6的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A5，5的地址是（A）。A 1175 B 1180 C1205 D1210,5、已知一棵完全二叉树中共有768结点，则该树中共有
24、_384_ 个叶子结点。,完全二叉树中度为1的节点数只有两种可能：要么为0个（奇数个结点），要么为1个（偶数个结点）。n0=n2+1,6、已知某二叉树的中序遍历序列是dgbaechf，后序遍历序列是gdbehfca，则其前序遍历序列是（A）。Aabdgcefh Bagdbecfh Cabdgechf D adbgcefh,6、有数据53，30，37，12，45，24，96，从空二叉树开始逐个插入数据来形成二叉搜索树，若希望高度最小，则应选择下面哪个序列输入 B。A、45，24，53，12，37，96，30 B、37，24，12，30，53，45，96 C、12，24，30，37，45，53，9
25、6 D、30，24，12，37，45，96，53,7、已知一长度为12的表（Jan，Feb，Mar，Apr，May，June，July，Aug，Sept，Oct，Nov，Dec）。（1）依次取表中各元素构造一棵二叉搜索树（按照在英文字典中的先后顺序比较元素值的大小）；并求其在等概率情况下搜索成功时的平均搜索长度。（2）若对表中元素进行排序构成有序表，求在等概率情况下对此有序表进行折半搜索成功的平均搜索长度。（3）按表中元素顺序构造一棵AVL树，并求其在等概率情况下搜索成功的平均搜索长度。,二叉搜索树,解答：42/12,Jan,Feb,July,Nov,Sept,Mar,June,May,Oct,Apr,Aug,Dec,折半搜索,解答：37/12,Mar,Jan,Apr,July,Nov,Oct,June,May,Sept,Aug,Feb,Dec,AVL树,解答：38/12,8、在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为 D。Ae B2e Cn2-e Dn2-2e,预祝全体同学考试成功！,
