数据结构c陈慧南ds习题课2.pptVIP

4 3 2 1 3 4 5 0 7 6 1 2 3 1 2 5 4 4 3 3 3 2 3 2 1 2 1 3 4 5 0 7 6 1 3 2 3 2 1 2 1 3 4 5 0 7 6 1 9.16 使用迪杰斯特拉算法，求以下有向图中以顶点A为源点的单源最短路径；写出二维数组d和path在执行该算法时的状态。 3 G E D B C 1 2 1 3 3 4 2 2 5 A 解： A B C D E G S d[0] d[1] d[2] d[3] d[4] d[5] path[0] path[1] path[2] path[3] path[4] path[5] A 0,-1 3,A ?,-1 4,A 5,A ?,-1 B 0,-1 3,A 4,B 4,A 4,B ?,-1 C 0,-1 3,A 4,B 4,A 4,B ?,-1 D 0,-1 3,A 4,B 4,A 4,B ?,-1 E 0,-1 3,A 4,B 4,A 4,B ?,-1 * 习题七（第137页） 7.1 7.1 7.5 建立以37，45，91，25，14，76，56，65为输入的二叉有哪些信誉好的足球投注网站树，再从该树上依次删除76，45，画出结果。 37 25 45 91 14 76 56 65 37 25 91 14 56 65 利用二叉排序树的性质。 template class T void BTreeT::IsBiTree(BTNodeT *p,int pre,bool fail) { if(p!fail) { IsBiTree(p-lc); if(prep-data) pre=p-data else fail=true; IsBiTree(p-rc); } } pre=-max; fail=false; IsBiTree(root,pre,fail); 7.6 判断二叉树是否二叉排序树。 7.7 编写一个从二叉有哪些信誉好的足球投注网站树中删除最大元素的算法，并分析算法的时间复杂度。 template class E,class K bool BSTreeE,K::Delete(Ee) { BTNodeE *p=root,*q=p; if (!p) return flse; while (p-rchild) { q=p; p=p-rchild; } if (p==root) root=root-lchild; else q-rchild=p-lchild; e=p-element; delete p; return true; } 37 25 91 14 56 65 37 25 32 14 7.8 以下列序列为输入，从空树开始构造AVL有哪些信誉好的足球投注网站树。 （1)A，Z，B，Y，C，X （2)A,V,L,T,R,E,I,S,O,K 7.9 一棵高度为h的AVL有哪些信誉好的足球投注网站树的最少结点数是多少？ 解： 或：Nh=Nh-1+Nh-2+1, N0=0, N1=1 例如:(1) 高度为8的AVL树至少有多少个结点？ 解： Nh=Nh-1+Nh-2+1, N0=0, N1=1 至少N8=N7+N6+1=(N6+N5+1)+N6+1=……=54个结点； (2) 有12个结点的AVL树最大高度？ 解： 因n5=n4+n3+1=...=12, 故最大高度5。 7.12 5阶B_树的高度为2时，树中元素个数最少为多少？ 解：5 7.13 从空树开始，以关键字序列a,g,f,b,k,d,h,m,j,e,s,i, r,x, 建立一棵4阶B_树。 7.14 从上题的B_树中删除a,e,f,h。 1 删除a 2 删除e b f d h k r m g s x i j e b f d h k r m g s x i j 3 删除f b d h f k r m g s x i j b h d k r m g s x i j 4 删除h b i d k r m g s x j 习题八（第154页） 8.3 设有散列表ht[11]，散列函数为h(key)=key % 11，采用线性探测和二次探测法处理冲突，试用关键字序列70，25，80，35，60，45，50，55分别建立散列表。 0 1 2 3 4 5 6 7 8 9 10 25 50 55 ht 70 80 35