图+查找+排序解答题,程序题.doc

1.画出该图的邻接矩阵和邻接表。根据邻接表从A开始求DFS和BFS序列。（12分） 【答案】 101000 100001 010010 000101 001010 A B C D E F DFS序列:ABDEFC BFS序列:ABCDFE 2. 已知序列{70，73，69，23，93，18,11，68}请给出直接插入排序作升序排序每一趟的结果和快速排序作升序排序时一趟的结果。（10分） 【答案】 70，73，69，23，93，18,11，68 [70，73]，69，23，93，18,11，68 [70，69，73]， 23，93，18,11，68 [23,70，69，73]， 93，18,11，68 [23,70，69，73， 93]，18,11，68 [18,23,70，69，73， 93]， 11，68 [11，18,23,70，69，73， 93]， 68 [11，18,23,68,70，69，73， 93] 快速排序:[68,11,69,23,18] ,70,[93,73] 3.设有一组关键字关键码集为 {47，7，29，11，16，92，22，8，3}，哈希表表长为11， Hash(key)=key mod 11，用线性探测法处理冲突，构造哈希表，并求它成功查找的ASL。（8分） 【答案】 0 1 2 3 4 5 6 7 8 9 10 11 22 47 92 16 3 7 29 8 ASL=5/3 4.定义有序表抽象数据类型，并据此类型设计折半查找算法。 typedef struct { int key; float info; }JD; int binsrch(JD r[],int n,int k) { int low,high,mid,found; low=1; high=n; found=0; while((low=high)(found==0)) { mid=(low+high)/2; if(kr[mid].key) low=mid+1; else if(k==r[mid].key) found=1; else high=mid-1; } if(found==1) return(mid); else return(0); } 5. 用prim算法求下图的最小生成树，写出最小生成树的生成过程。（5分） 6.设关键字的输入序列为{4，5，7，2，1，3，6} (1)（8分）从空树开始构造平衡二叉树，画出每加入一个新结点时二叉树的形态，若发生不平衡，指明需做的平衡旋转类型及平衡旋转的结果。 (2)（4分）上面的数据作为待排序的数据，写出用快速排序进行一趟划分后的数据序列 答案（1） (2)一趟划分后的数据序列 3 1 2 4 7 5 6 7.画出无向图G的邻接表存储结构，根据邻接表存储结构写出深度优先和广度优先遍历序列。（7分） 【答案】 BFS遍历序列v1 v2 v3 v4 v5 v6 v7 v8(或1 2 3 4 5 6 7 8) 8.请在标号处填写合适的语句。完成下列程序。(每空1分，共5分) int Binary_Search(S_TBL tbl，KEY kx) { /* 在表tbl中查找关键码为kx的数据元素，若找到返回该元素在表中的位置，否则，返回0 */ int mid，flag=0； low=1；high=length； while( ⑴ !flag ) { /* 非空，进行比较测试 */ mid= ⑵ ； if(kxtbl.elem[mid].key) ⑶ ； else if(kxtbl.elem[mid].key) ⑷ ； else { flag= ⑸ ；break；} } return flag; } 答案: (2) (low+high)/2 (3) high=mid-1 (4) low=mid+1 (5) 1 9.下面是一个采用直接选择排序方法进行升序排序的函数，请在标号处填写合适的语句。(每空1分，共5分) 程序： Void seletesort(int A[n],int n) { int i,j,t,min