《数据结构》试题(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[soj60,其元素长度为4字节,按行优先顺序存储,基地址为200,则 元素A[18][25的存储地址为(H) (10)5阶B树中,每个结点最多有(J)个关键码。 【供选择的答案】 A:①链头 ②链尾 ③链中 B:①起泡排序②快速排序 ③简单选择排序④堆排序 C:①起泡排序②归并排序 ③直接插入排序④简单选择排序 D:①表元素 ②字符 ③数据元素 ④数据项 F:① DBFEAC② DFEBCA ③ BDFECA ④ BDEFAC G:①3700 ②4376 ③3900 ④4620 2 、阅读理解题[说明下列递归过程的功能](10分) void unknown( ListNode *f: Type &x)i ∥指针∫是带表头结点的单链表的表头指针,数值x是给定值。 ListNode* temp; f(f→link!=NUL){ while(f→lnk→daa==x){ temp=f→link;f→link=temp→link; delete temp; nown(f→link,x); 简答题(每小题12分,共36分) 1、假定用于通信的电文仅由8个字母cl,c2,c3,c4,cs,c6,c7,c8组成,各字母在电文中出现的频率分别为 5,25,3,6,10,11,36,4。试为这8个字母设计不等长 Huffman编码,并给出该电文的总码数
1 《数据结构》试题 （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 void Bin Tiee: unknown( BinTreeNode*t)i Bin TreeNode 'p=t,*temp f(p I=NULL)& p→ lefi child=p→ righIChild; p→ rightChild=temp; unknown(p→ lefi child); unknown(p→ rightChila) } (1)指出该算法完成了什么功能 (5分) (2)试写一个算法,不用栈将以上算法中的第二个递归语句消去 (5分) (3)试再写一个算法,用栈将以上算法中的第一个递归语句也消去 (5分) 五、填空题 本题给出一个施加于链表的选择排序的算法。算法中用到一个临时的表头结点head,作为结果链表的 表头结点,每次从frst链上摘下的值最大的结点 current链入head之后。算法结束前,将head删除 template void List: List Selectsort()& ListNode* head=new ListNode(,*current, 'pre, p, q; int i=0: while( ① p=current=first; q= NULL while(p = NULL r(p-dm>[② ipre =q: current=p; 3 q=p;p=p→limk; if( curent=first )3 else pre→link= current→link; if(! i )last=current; i++
2 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 void BinTree :: unknown ( BinTreeNode * t ) { BinTreeNode *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 void List :: ListSelectSort ( ) { ListNode * head = new ListNode ( ), *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→lik; first= head-link delete head; (1)请将缺失的语句部分补上: (8分) (2)设待排序的记录数n=7,当排序前各记录关键码的初始链接顺序为40,20,60.,30,70,50,80,试根 据上述算法,画出每一趟排序时各结点指针的变化 (7分)
3 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 次数{5,25,3,6,10,11,36,4} 则 Huffman编码为 000101 0001 36 0 c1 电文总码数为4*5+2*25+4*3+4*6+3*10+3*11+2*36+4*4=257 2、【解答】 描述对有序顺序表进行二分法检索的判定树为 154 677 553 89 搜索成功时的平均搜索长度为 ASL (1+2*2+3*4+4+7)45 14 搜索不成功时的平均搜索长度为 ASLunsucc=-(3+4*14)= 3、【解答】
4 试题解答 一、单选题 【解答】 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 = 1 14 1 2 2 3 4 4 7 45 14 ( + * + * + * ) = 搜索不成功时的平均搜索长度为 ASLunsucc= 1 15 3 4 14 59 15 ( + * ) = 3、【解答】
(1)k(i=0,1, h) k (4)(1)modk≠0或\1+k-)k时有右兄弟,右兄弟为+1。 四、综合算法题 【解答】 (1)交换二叉树各结点的左、右子树的递归算法。 (2)不用栈消去递归算法中的第二个递归语句: void BinTree: unknown( Bin TreeNode*t)i Bin TreeNode 'p=t, * temp temp=p→ lefi chil p→ rightChild=temp; unknown(p→ lefrchild); p=p→ righichile (3)使用栈消去递归算法中的两个递归语句: void Bin Tiee: unknown( BinTreeNode*t)i BinTreeNode*p=t,*temp; int finish=0; stack S;S. makeEmpty(; hile( finish)i hile(p l= Null)i tel p→ lefichild=p→ rightChild; p→ righIChild=temp; Spush(P): p=p-lefichild; if(IS Empty()i p=S getTop(; Spop(; Child) 五、填空题 【解答】 (1)请将缺失的语句补上 first I= NULL current→data
5 (1) k i ( i = 0, 1, ……, h ) (2) i k k + − 2 (3) ( i-1)*k + m + 1 (4) ( i-1 ) mod k 0 或 i + − i k k k 2 * 时有右兄弟，右兄弟为 i + 1。 四、综合算法题 【解答】 (1) 交换二叉树各结点的左、右子树的递归算法。 (2) 不用栈消去递归算法中的第二个递归语句： void BinTree :: unknown ( BinTreeNode * t ) { BinTreeNode *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 :: unknown ( BinTreeNode * t ) { BinTreeNode *p = t, *temp; int finish = 0; stack 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
frst=nrst→lik head→link= current (2)排序前各记录关键码的初始链接顺序为40,20,60,30,70,50,80,根据上述算法,每一趟排序时各 结点指针的变化如下 fist→40→20→60→30→70→50→80 head tpe↑ current frst→40→20→60→30→70→50 pre↑ current f frst→40→20→30→50 head→60→70→80 frst→40→20→30 head→50→60→70→80 tpe↑ head→40→50→60→70→80 head→30 tpe↑ first frst→20→30→40→50→60→70→80 ↑last
6 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