广东工业大学考试试卷 000复习样题答案 数据结构.doc

数据结构复习样题答案一. 单项选择题（共12分）1. B 2. A 3. A 4. D 5. C 6. D 7. B 8. C二. 填空题(共12分) 9. 数据对象、数据关系、基本操作10.从表中任一结点出发均可找到表中其他结点11. 字符依次对应相同且长度相同12.3313.各结点均无左孩子14.n-115.在排序过程中需要访问外存16.散列三. 解答题（共36分）JanFebMarAprJuneMayJulyAugSepOctNovDec成功的平均查找长度42/12ESCJSBSDISKSASFGS17（5分）后序线索18.（10分）已知一个长度为12的表为（Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec）（1） 试将表中元素依次插入到一棵初始为空的二叉排序树（字符串之间按字典顺序比较大小）。画出该二叉排序树，并求出等概率情况下查找成功的平均查找长度。（2） 设哈希表长度为13，哈希函数H（k）= i/2，其中i为关键字k中第一个字母在字母表中的序号（例如A和D的序号分别为1和4），用链地址法解决冲突。请画出通过依次插入表中元素所构造的散列表，并求出在等概率情况下查找成功的平均查找长度。0123456789101112MayAugSepNovDecFebJulyMarAprOctJuneJan成功的平均查找长度18/1219.（5分）假设电文中仅由a到h共8个字母组成，字母在电文中出现的频度依次为7，19，2，6，32，3，21，10请画出由此构造的哈夫曼树（要求树中所有结点的左右孩子必须是左大右小），并写出这8个字母相应的哈夫曼编码。b1917c2d6e32f3a7h10g213833625113000000001111111字符哈夫曼码a111b010c01111d0110e00f01110g10h11020.（8分）若对序列（25，19，7，41，29，12，23，26）按升序排序，请分别给出（1） 步长为4的一趟希尔排序的结果；（2） 初始大根堆。答：（1） （12，7，25，29，19，23，26，41） （2） （41，26，23，25，29，12，7，19）524319426138127721.（8分）对于右边的带权图G，请（1） 画出G的邻接矩阵；（2） 画出G的最小生成树。答：（1） （2）5243142327四. 算法题（共30分）22（5分）函数f22定义如下，其中函数调用Insert(L, i, k)在顺序表L的第i位置插入k。 void f22(SqList &L, int i) if (i 0) f22(L, i-1);for (int k=1; knext; L-next = NULL ; while ( p ) LinkList s = p-next ;p-next = L-next; L-next = p ; p = s; 24.（5分） s是一个升序静态查找表，请简要说明函数调用f24(s, 1, s.length, k)的意义。int f24(SSTable s, int low, int high, KeyType k) if (lowhigh) return 0; int mid=(low+high)/2; if (k=s.elemmid.key) return mid; if (ks.elemmid.key) return f24(s,mid+1,high,k); else return f24(s,low,mid-1,k);答：在s中递归折半查找k。25（5分）请对以下函数填空，实现求二叉树T中各结点的子孙总数，并填入结点的DescNum域中的算法。int f25(BiTree T) if ( !T ) return -1;else T-DescNum = f25(T-lchild) + f25(T-rchild) + 2 ;return T-DescNum;26（5分）图的邻接矩阵表示和算法f26描述如下：#define MaxNum 5typedef struct char vexsMaxNum;int arcsMaxNumMaxNum; int n,e; MGraph; int f26(MGraph G, int i) int d=0;for (int j=0; jnext; while ( p ) / p 指向当前被考察的结点 q = p; while (q-next) / 考察 q 所指后继结点 if (q-next-data != p-data) q