《数据结构》试题 （C卷） 一、单选题 [在供选择的答案中选择与下列各括号中内容相匹配的答案，把其编号与其各括号的标识对应起来] （每小题3分，共24分) (1) 用单链表表示的链式队列的队头在链表的（ A ）位置。 (2) 如果只想得到1024个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ B ）方法最快。 (3) 如果待排序序列中两个数据元素具有相同的值, 在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（ C ）就是不稳定的排序方法。 (4) 线性表是具有n个（ D ）的有限序列（n ≥ 0 ）。 (5) 设无向图的顶点个数为n，则该图最多有（ E ）条边。 (6) 对某二叉树进行前序遍历的结果为ABDEFC, 中序遍历的结果为DBFEAC, 则后序周游的结果为（ F ）。 (8) 设有50行60列的二维数组A[50][60], 其元素长度为4字节, 按行优先顺序存储, 基地址为200, 则元素A[18][25]的存储地址为（ H ）。 (10) 5阶B树中, 每个结点最多有（ J ）个关键码。 【供选择的答案】 A： ① 链头 ② 链尾 ③ 链中 B： ① 起泡排序 ② 快速排序 ③ 简单选择排序 ④ 堆排序 C： ① 起泡排序 ② 归并排序 ③ 直接插入排序 ④ 简单选择排序 D： ① 表元素 ② 字符 ③ 数据元素 ④ 数据项 E： ① n-1 ② n(n-1)/2 ③ n(n+1)/2 ④ 0 F： ① DBFEAC ② DFEBCA ③ BDFECA ④ BDEFAC G： ① 3700 ② 4376 ③ 3900 ④ 4620 H： ① 2 ② 3 ③ 4 ④ 5 二、阅读理解题 [说明下列递归过程的功能] (10分) void unknown ( ListNode * f ; Type &x ) { //指针f是带表头结点的单链表的表头指针，数值x是给定值。 ListNode * temp; if ( f→link!= NULL ) { while ( f→link→data == x ) { temp = f→link; f→link = temp→link; delete temp; } unknown ( f→link, x ); } } 三、简答题 (每小题12分，共36分) 1、假定用于通信的电文仅由8个字母c1, c2, c3, c4, c5, c6, c7, c8组成, 各字母在电文中出现的频率分别为5, 25, 3, 6, 10, 11, 36, 4。试为这8个字母设计不等长Huffman编码, 并给出该电文的总码数。 2、设有序顺序表中的元素依次为017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时做性能分析用的扩充二叉搜索树（判定树），并计算搜索成功时的平均搜索长度和搜索不成功时的平均搜索长度。 3、一棵高度为h的满k叉树有如下性质: 第h层上的结点都是叶结点, 其余各层上每个结点都有k棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号, 试问: (1) 各层的结点个数是多少? （3分） (2) 编号为i的结点的父结点(若存在)的编号是多少? （3分） (3) 编号为i的结点的第m个孩子结点(若存在)的编号是多少? （3分） (4) 编号为i的结点有右兄弟的条件是什么？它的右兄弟结点的编号是多少？ （3分） 四、综合算法题 下面是对二叉树进行操作的算法, 请仔细阅读。 template <calss Type> void BinTree<Type> :: unknown ( BinTreeNode<Type> * t ) { BinTreeNode<Type> *p = t, *temp; if ( p != NULL ) { temp = p→leftChild; p→leftChild = p→rightChild; p→rightChild = temp; unknown ( p→leftChild ); unknown (p→rightChild); } } (1) 指出该算法完成了什么功能。 （5分） (2) 试写一个算法，不用栈将以上算法中的第二个递归语句消去。 （5分） (3) 试再写一个算法，用栈将以上算法中的第一个递归语句也消去。 （5分） 五、填空题 本题给出一个施加于链表的选择排序的算法。算法中用到一个临时的表头结点head，作为结果链表的表头结点，每次从first链上摘下的值最大的结点current链入head之后。算法结束前，将head删除。 template <class Type> void List<Type> :: ListSelectSort ( ) { ListNode<Type> * head = new ListNode<Type> ( ), *current, *pre, p, q; int i = 0; while (  ① ) {   p = current = first; q = NULL; while ( p != NULL ) { if ( p→data >  ② )  { pre = q; current = p; } q = p; p = p→link; } if ( current == first )  ③ ;   else pre→link = current→link; if ( !i ) last = current; i++; current→link = head→link;  ④ ;   } first = head→link; delete head; } (1) 请将缺失的语句部分补上： （8分） ( ( ( ( (2) 设待排序的记录数n = 7, 当排序前各记录关键码的初始链接顺序为40, 20, 60, 30, 70, 50, 80，试根据上述算法，画出每一趟排序时各结点指针的变化。 （7分） 试题解答 一、单选题 【解答】 A : ① B : ④ C : ④ D : ③ E : ② F : ② G : ④ H : ③ 二、阅读理解题 [说明下列递归过程的功能] 【解答】 在单链表中删除所有值为x的结点。 三、简答题 1、【解答】 已知字母集 { c1, c2, c3, c4, c5, c6, c7, c8 } 次数 { 5, 25, 3, 6, 10, 11, 36, 4 } 则Huffman编码为 c1  c2  c3  c4  c5  c6  c7  c8   0100  10  0000  0101  001  011  11  0001   电文总码数为 4 * 5 + 2 * 25 + 4 * 3 + 4 * 6 + 3 * 10 + 3 * 11 + 2 * 36 + 4 * 4 = 257 2、【解答】 描述对有序顺序表进行二分法检索的判定树为： 搜索成功时的平均搜索长度为 ASLsucc =  搜索不成功时的平均搜索长度为 ASLunsucc =  3、【解答】 (1) ki ( i = 0, 1, ……, h ) (2)  (3) ( i-1)*k + m + 1 (4) ( i-1 ) mod k ( 0 或 i时有右兄弟，右兄弟为i + 1。 四、综合算法题 【解答】 (1) 交换二叉树各结点的左、右子树的递归算法。 (2) 不用栈消去递归算法中的第二个递归语句： void BinTree<Type> :: unknown ( BinTreeNode<Type> * t ) { BinTreeNode<Type> *p = t, *temp; while ( p != NULL ) { temp = p→leftChild; p→leftChild = p→rightChild; p→rightChild = temp; unknown ( p→leftChild ); p = p→rightChild); } } (3) 使用栈消去递归算法中的两个递归语句： void BinTree<Type> :: unknown ( BinTreeNode<Type> * t ) { BinTreeNode<Type> *p = t, *temp; int finish = 0; stack<Type> S; S.makeEmpty ( ); while ( !finish ) { while ( p != NULL ) { temp = p→leftChild; p→leftChild = p→rightChild; p→rightChild = temp; S.push ( p ); p = p→leftChild; } if ( !S.Empty ( ) ) { p = S.getTop( ); S.pop( ); p = p→rightChild); } else finish = 1; } } 五、填空题 【解答】 (1) 请将缺失的语句补上 ( first != NULL ( current→data ( first = first→link ( head→link = current (2) 排序前各记录关键码的初始链接顺序为40, 20, 60, 30, 70, 50, 80，根据上述算法，每一趟排序时各结点指针的变化如下： first → 40 → 20 → 60 → 30 → 70 → 50 → 80 head ↑pre ↑current first → 40 → 20 → 60 → 30 → 70 → 50 head → 80 ↑pre ↑current first → 40 → 20 → 60 → 30 → 50 head → 70 → 80 ↑pre ↑current first → 40 → 20 → 30 → 50 head → 60 → 70 → 80 ↑pre ↑current first → 40 → 20 → 30 head → 50 → 60 → 70 → 80 ↑pre ↑current first → 20 → 30 head → 40 → 50 → 60 → 70 → 80 ↑pre ↑current first → 20 head → 30 → 40 → 50 → 60 → 70 → 80 ↑pre ↑current first head → 20 → 30 → 40 → 50 → 60 → 70 → 80 first → 20 → 30 → 40 → 50 → 60 → 70 → 80 ↑last