广工计算机学院数据结构2011答案数据结构A卷.doc

9．对有序表进行折半查找时，若查找不成功时，low和high的关系为 （A）low=high (B)low=high (C)lowhigh (D)low=high 10．一个具有n个顶点的连通图的生成树，它含有图中的全部顶点，且有（ ）条边。 （A）n (B)n-1 (C)n+1 (D)2n 二、填空题（每题2分，共20分） 根据数据元素之间关系的不同特性，通常有下列四类基本的数据结构集合，线性结构，树形结构，图状结构或者网状结构＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿……..Kn}，有筛选法堆，则必须从第＿＿＿ （2）画出图G的邻接矩阵。 （3）写出G的全部拓扑有序序列。 afcbde afcdbe afcdeb afdcbe afdceb facbde facdbe facdeb fadcbe fadceb acbfde acfbde acfdbe acfdeb 2．（10分）己知一棵二叉树的中序遍历结果为BDHEAFICG，后序遍历结果为DHEBIFGCA，画出该二叉树。 3．（10分）已知一组元素的排序码为（36，25，48，12，65，20），写出用线性插入排序法每次向前面有序表插入一个元素后的排列结果 第一趟：25, 36, 48, 12, 65, 20 （2分） 第二趟：没有变化 （2分） 第三趟：12, 25, 36, 48, 65, 20 （2分） 第四趟：没有变化 （2分） 第五趟：12, 20, 25, 36, 48, 65 （2分） 4．(10分）设哈希函数为H（key） 冲突次数： 4．（10分） 0 1 2 3 4 5 6 7 8 9 10 23 47 15 48 37 29 41 73 1 2 2 四、算法设计题（共20分） 2．（10分）以顺序表为存储结构，写出折半插入排序的算法。 算法设计题 1 2. void BiInsertionSort ( SqList L ) { for ( i=2; i=L.length; ++i ) { L.r[0] = L.r[i]; // 将 L.r[i] 暂存到 L.r[0] low = 1; high = i-1; while (low=high) { m = (low+high)/2; // 折半 if (L.r[0].key L.r[m].key) high = m-1; // 插入点在低半区 else low = m+1; // 插入点在高半区 for ( j=i-1; j=high+1; --j ) L.r[j+1] = L.r[j]; // 记录后移 L.r[high+1] = L.r[0]; // 插入 } // for } // BInsertSort 每条指令1分 3．（10分）写出中序遍历求二叉树度为2的结点数目的算法。 void inorder(t,c) bitree *t;int c=0; { if(t!=NULL) { ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿ ＿＿＿＿＿＿＿＿} 2. void BiInsertionSort ( SqList L ) { for ( i=2; i=L.length; ++i ) { L.r[0] = L.r[i]; // 将 L.r[i] 暂存到 L.r[0] low = 1; high = i-1; while (low=high) { m = (low+high)/2; // 折半 if (L.r[0].key L.r[m].key) high = m-1; // 插入点在低半区 else low = m+1; // 插入点在高半区 for ( j=i-1; j=high+1; --j ) L.r[j+1] = L.r[j]; // 记录后移 L.r[high+1] = L.r[0]; // 插入 } // for } // BInsertSort 广东工业大学试卷用纸，共 6 页，第 5 页 广东工业大学考试试卷 ( A ) 课程名称: 数据结构 考试时间: 2007年6 月 21 日 (第16周 星期四 ) 题 号 一 二 三 四 五 六 七 八