试给出下列有关并查集( mfsets)的操作序列的运算结果 union (1, 2), union (3, 4), union(3, 5), union(1, 7), union(3, 6), union(8, 9),union(1, 8), union(3, 10), union(3, 11), union(3, 12). union(3, 13), union(14, 15), union (16, 0), union (14, 16), union (1, 3). union(1,14)。( union是合并运算,在以前的书中命名为 merge 要求 (1)对于unon(),以i作为j的双亲 (5分) (2)按i和j为根的树的高度实现 union(,,高度大者为高度小者的双亲 (5分) (3)按i和j为根的树的结点个数实现 union(,,结点个数大者为结点个数小者的双亲 (5分) 、设在4地(A,B,C,0D)之间架设有6座桥,如图所示: ⑥ 要求从某一地出发,经过每座桥恰巧一次,最后仍回到原地。 (1)试就以上图形说明:此问题有解的条件什么? (5分) (2)设图中的顶点数为n,试用C或 Pascal描述与求解此问题有关的数据结构并编写一 个算法,找出满足要求的一条回路。 (10分) 三、针对以下情况确定非递归的归并排序的运行时间(数据比较次数与移动次数): 1)输入的n个数据全部有序 (5分) (2)输入的n个数据全部逆向有序 (5分) (3)随机地输入n个数据 (5分) 四、简单回答有关AVL树的问题。 (1)在有N个结点的AMⅥL树中,为结点增加一个存放结点高度的数据成员,那么每一个 结点需要增加多少个字位b? (5分) (2)若每一个结点中的高度计数器有8bts,那么这样的AⅥL树可以有多少层?最少有多 少个关键码? (5分)
1 一、试给出下列有关并查集(mfsets)的操作序列的运算结果： union(1, 2), union(3, 4), union(3, 5),union(1, 7), union(3, 6), union(8, 9), union(1, 8), union(3, 10), union(3, 11), union(3, 12), union(3, 13), union(14, 15), union(16, 0), union(14, 16), union(1, 3), union(1, 14)。（union 是合并运算，在以前的书中命名为 merge） 要求 (1) 对于 union(i, j)，以 i 作为 j 的双亲； （5 分） (2) 按 i 和 j 为根的树的高度实现 union(i, j)，高度大者为高度小者的双亲； （5 分） (3) 按 i 和 j 为根的树的结点个数实现 union(i, j)，结点个数大者为结点个数小者的双亲。 （5 分） 二、设在 4 地(A, B, C, 0D)之间架设有 6 座桥，如图所示： 要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。 (1) 试就以上图形说明：此问题有解的条件什么？ （5 分） (2) 设图中的顶点数为 n，试用 C 或 Pascal 描述与求解此问题有关的数据结构并编写一 个算法，找出满足要求的一条回路。 （10 分） 三、针对以下情况确定非递归的归并排序的运行时间（数据比较次数与移动次数）： (1) 输入的 n 个数据全部有序； （5 分） (2) 输入的 n 个数据全部逆向有序； （5 分） (3) 随机地输入 n 个数据。 （5 分） 四、简单回答有关 AVL 树的问题。 (1) 在有 N 个结点的 AVL 树中，为结点增加一个存放结点高度的数据成员，那么每一个 结点需要增加多少个字位(bit)？ （5 分） (2) 若每一个结点中的高度计数器有 8bits，那么这样的 AVL 树可以有多少层？最少有多 少个关键码？ （5 分） A B C D ① ② ③ ④ ⑤ ⑥
五、设一个散列表包含 hash Size=13个表项,其下标从0到12,采用线性探查法解决冲突 请按以下要求,将下列关键码散列到表中。 101003245581263292004000 (1)散列函数采用除留余数法,用% hash size(取模运算)将各关键码映像到表中。请指 出每一个产生冲突的关键码可能产生多少次冲突。 (7分) (2)散列函数采用先将关键码各位数字折叠相加,再用% hash size将相加的结果映像到 表中的办法。请指出每一个产生冲突的关键码可能产生多少次冲突。 (8分) 六、设一棵二叉树的结点定义为 struct BinTreeNode t Elem Type data: BinTreeNode *leftChild, *right child 现采用输入广义表表示建立二叉树。具体规定如下 (1)树的根结点作为由子树构成的表的表名放在表的最前面 (2)每个结点的左子树和右子树用逗号隔开。若仅有右子树没有左子树,逗号不能省略 (3)在整个广义表表示输入的结尾加上一个特殊的符号(例如“#”)表示输入结束 例如,对于如右图所示的二叉树,其广 义表表示为AB(D,E(G,)),C(,F) 此算法的基本思路是:依次从保存广义 表的字符串ls中输入每个字符。若遇到的是 字母(假定以字母作为结点的值),则表示是 结点的值,应为它建立一个新的结点,并把 该结点作为作为左子女(当k=0)或右子女(当k=1)链接到其双亲结点上。若遇到的是左括号"( 则表明子表的开始将k置为0;若遇到的是右括号)”,则表明子表结束。若遇到的是逗号”,”, 则表示以左子女为根的子树处理完毕,应接着处理以右子女为根的子树,将k置为1。 在算法中使用了—个栈s,在进入子表之前,将根结点指针进栈,以便括号内的子女链接 之用。在子表处理结束时退栈。相关的栈操作如下 Make Empty(s) 置空栈 Push(s, p) 元素p进栈 Pop(s) 退栈 Top(s 存取栈顶元素的函数
2 五、设一个散列表包含 hashSize = 13 个表项，其下标从 0 到 12，采用线性探查法解决冲突。 请按以下要求，将下列关键码散列到表中。 10 100 32 45 58 126 3 29 200 400 0 (1) 散列函数采用除留余数法，用%hashSize（取模运算）将各关键码映像到表中。请指 出每一个产生冲突的关键码可能产生多少次冲突。 （7 分） (2) 散列函数采用先将关键码各位数字折叠相加，再用 %hashSize 将相加的结果映像到 表中的办法。请指出每一个产生冲突的关键码可能产生多少次冲突。 （8 分） 六、设一棵二叉树的结点定义为 struct BinTreeNode { ElemType data; BinTreeNode *leftChild, *rightChild; } 现采用输入广义表表示建立二叉树。具体规定如下： (1) 树的根结点作为由子树构成的表的表名放在表的最前面； (2) 每个结点的左子树和右子树用逗号隔开。若仅有右子树没有左子树，逗号不能省略。 (3) 在整个广义表表示输入的结尾加上一个特殊的符号（例如“#”）表示输入结束。 例如，对于如右图所示的二叉树，其广 义表表示为 A(B(D, E(G, ) ), C( , F) )。 此算法的基本思路是：依次从保存广义 表的字符串 ls 中输入每个字符。若遇到的是 字母 (假定以字母作为结点的值)，则表示是 结点的值，应为它建立一个新的结点，并把 该结点作为作为左子女(当 k=0)或右子女(当 k=1)链接到其双亲结点上。若遇到的是左括号”(”， 则表明子表的开始，将 k 置为 0；若遇到的是右括号”)”，则表明子表结束。若遇到的是逗号”,”， 则表示以左子女为根的子树处理完毕，应接着处理以右子女为根的子树，将 k 置为 1。 在算法中使用了一个栈 s，在进入子表之前，将根结点指针进栈，以便括号内的子女链接 之用。在子表处理结束时退栈。相关的栈操作如下： MakeEmpty(s) 置空栈 Push(s, p) 元素 p 进栈 Pop(s) 退栈 Top(s) 存取栈顶元素的函数 A B C D E F G
下面给出了建立二叉树的算法,其中有5个语句缺失。请阅读此算法并把缺失的语句补 (每空3分) void Create BinTree(BinTreeNode * bt, char ist Stack<BinTreeNode * S; Make Empty s) BT E NULLS /置空二叉树 BinTreeNode* p; int instream ins(ls); ∥/把串ls定义为输入字符串流对象is char ch; ins >>ch; /从ins顺序读入一个字符 while(ch!=`#){/逐个字符处理,直到遇到‘#′为止 switch(ch)& case'(":[① break: case ) pop(s); break; case. break default: p= new Bin TreeNode; p->leftChild NULL; p->rightchild nULL if Bt== NULL) else if (k==1) top(s)->leftchild p; else top(s)->rightchild p ⑤
3 下面给出了建立二叉树的算法，其中有 5 个语句缺失。请阅读此算法并把缺失的语句补 上。 （每空 3 分） void CreateBinTree(BinTreeNode *& BT, char ls) { Stack<BinTreeNode *> s; MakeEmpty(s) ; BT = NULL; //置空二叉树 BinTreeNode *p; int k; instream ins(ls); //把串 ls 定义为输入字符串流对象 ins char ch; ins >> ch; //从 ins 顺序读入一个字符 while (ch != ‘#’) { //逐个字符处理，直到遇到‘#’为止 switch (ch) { case ‘(’ : push(s, p); k=1; break; case ‘)’ : pop(s); break; case ‘,’ : k=2; break; default : p = new BinTreeNode; p->data = ch; p->leftChild = NULL; p->rightChild = NULL; if ( BT == NULL ) Bt = p; else if (k==1) top(s)->leftChild = p; else top(s)->rightChild = p; } ins >> ch; } } ① ② ③ ④ ⑤
七、下面是一个用C编写的快速排序算法。为了避免最坏情况,取基准记录 pivot采用从lef, nght和md=「(|et+mght)/21中取中间值,并交换到mght位置的办法。数组a存放待排 序的一组记录,数据类型为Type,left和mght是待排序子区间的最左端点和最右端点。 void quicksort(Type a[ ], int left int right)t Type temp; f left right& Type pivot= median3(a,left, right);//三者取中子程序 It i left, j= right -1; (;;){ while(i<j&& a[i< pivot)i++ while(i<j&& pivot aldj-- if (i<jt temp a[d; au]= ad: a[d= temp + else break: if ( a[j> pivot i temp=a[; a[j=a[right]: a[right]= temp; 1 quicksort(a, left, i-1) /递归排序左子区间 quicksort(a, i+l, right); /递归排序右子区间 } (1)用C或 Pascal实现三者取中子程序 median3(a,eft, right); (5分) (2)改写 quicksort算法,不用栈消去第二个递归调用 quicksort(a, i+l, right); (5分) (3)继续改写 quicksort算法,用栈消去剩下的递归调用。(5分)
4 七、下面是一个用 C 编写的快速排序算法。为了避免最坏情况，取基准记录 pivot 采用从 left, right 和 mid = ( left + right ) / 2 中取中间值，并交换到 right 位置的办法。数组 a 存放待排 序的一组记录，数据类型为 Type，left 和 right 是待排序子区间的最左端点和最右端点。 void quicksort (Type a[ ], int left, int right) { Type temp; if (left < right) { Type pivot = median3 (a, left, right); //三者取中子程序 int i = left, j = right-1; for ( ; ; ) { while (i < j && a[i] < pivot) i++; while (i < j && pivot < a[j]) j--; if (i < j) { temp = a[i]; a[j] = a[i]; a[i] = temp; i++; j--; } else break; } if ( a[i] > pivot ) { temp = a[i]; a[i] = a[right]; a[right] = temp; } quicksort (a, left, i-1); //递归排序左子区间 quicksort (a, i+1, right); //递归排序右子区间 } } (1) 用 C 或 Pascal 实现三者取中子程序 median3(a, left, right); （5 分） (2) 改写 quicksort 算法，不用栈消去第二个递归调用 quicksort (a, i+1, right); （5 分） (3) 继续改写 quicksort 算法，用栈消去剩下的递归调用。 （5 分）
、解答 (1)对于 union(j,以i作为j的双亲 (5分) ④③(⑩⑩@⑥① (2)按i和j为根的树的高度实现 union(.j,高度大者为高度小者的双亲 (5分) ③③⑨⑩@@③① (3)按i和j为根的树的结点个数实现 union(j,结点个数大者为结点个数小者的双亲 (5分) ⑦( 、解答:将下图改为无向图,城市为结点,桥为边: B ① ④ (1)此为欧拉问题。有解的充要条件是每一个结点的度为偶数。(5分) (2)数据结构采用邻接表,每个边结点有3个域,分别记录相关边号、邻接顶点号和链指针 edge AdiNo link 另外,设置一个边的访问标志数组 visited[],当 visited[]==0表示第i条边未访问过,一旦访问了
5 一、解答 (1) 对于 union(i, j)，以 i 作为 j 的双亲 （5 分） (2) 按 i 和 j 为根的树的高度实现 union(i, j)，高度大者为高度小者的双亲； （5 分） (3) 按 i 和 j 为根的树的结点个数实现 union(i, j)，结点个数大者为结点个数小者的双亲。 （5 分） 二、解答：将下图改为无向图，城市为结点，桥为边： (1) 此为欧拉问题。有解的充要条件是每一个结点的度为偶数。 （5 分） (2) 数据结构采用邻接表，每个边结点有 3 个域，分别记录相关边号、邻接顶点号和链指针。 另外，设置一个边的访问标志数组 visited[ ]，当 visited[i] == 0 表示第 i 条边未访问过，一旦访问了 1 2 7 8 9 4 5 6 10 11 12 13 3 14 15 16 0 3 15 16 0 1 2 7 8 9 4 5 6 10 11 12 13 14 4 5 6 10 11 12 13 3 1 2 7 8 9 15 16 0 14 A B C D ① ② ③ ④ ⑤ ⑥ A B C D ① ③ ② ④ ⑤ ⑥ EdgeNo AdjNo link