《数据结构》课程教学资源（作业习题）练习题及答案1

数据结构总复习 1.数据结构按逻辑结构可分为两大类，它们分别是线性结构一和非线性结构 (B)1. 线性结构是数据元素之间存 十算机算法必须具备铃入 B 对多关系 C)多对一关系 D) 一对一关系 (B)4. 心确定性 可移植性和可扩充性 B可行 帝定性和右 、有穷性和稳定性 D)易读性、稳定性和安全性 2向一个长度为n的向量的第i个元素(1≤i≤叶1)之前插入一个元素时，需向后移动ni+1个元素。 在n个结点的单链表中要删除已知结点P, 需找到它的前驱结点的地址 其时间复杂度为0(n)。 (D)4.线性表若采用链式存储结构时，要求内存中可用存储单元的地址 (A)必须是连续的 (B)部分地址必须是连续的 (C) 定是不连续的 (D)连续或不连续都可以 1.已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，请写出在P结点前插入S结点的 核心语句序列。 while(P->nextI=Q)P-P->next, 己知P结点，则不必“顺藤摸瓜”，直接链 接即可 P-Q ext-P.>next P->ncxt=S: -next-P->next 2.向栈中压入元素的操作是先移动栈顶指针 后存入元素 (B)2.判定一个栈ST(最多元素为m0)为空的条件是 A.ST->top 0 B.ST->top=0 C.ST->top>m0 D.ST->top=m0 A)3.判定一个队列QU(最多元素为m0)为满队列的条件是 A·Q0->rea知r-Q0->front==m0 B.QU->rear -QU->front -1==m0 >rear+ ：风满条件 的输出结果 Queue Q. Init Queue(Q). (O'h'):.EnQueue(Q.'r'). EnQueue(Q,y） DeQueue(Q.x).EnQueue(Q.x Que Printf(x) he(Q.y).printf(y).} 答：输出为“char” 素组表中的每个结点对应于稀疏矩阵的 元素值 个非零元素，它包含有三个数据项，分别表示该元素 10.求下列广义表操作的结果： (d) 2.设一棵完全二叉树具有1000个结点，则此完全三叉树有500个叶子结点，有499个度为2的结点，有1 个结点只有非空左子树，有0 个结点只有非空右子树。 答：最快方法：用叶子数=(W2=500,2=-1=499。另外，最后一结点为2i属于左叶子，右叶子是空的，所 以有1个非空左子树。完全二又树的特点决定不可能有左空右不空的情况，所以非空右子树数=， 个仪值{3， 4,5,网造的 man)树的帘仪环径长度 解：先构造 合夫曼树，得到各叶子的路径长度之后便可求出WPL=(4+5+3)×2+(1+2)×3=33 9 (60 (注：两个合并值先后不同会导致编码不同，即哈夫曼编码不唯一) 4入53 (注：合并位应排在叶子位之后) 1 2 1

1 数据结构总复习 1. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。 （ B ）1. 非线性结构是数据元素之间存在一种： A）一对多关系 B）多对多关系 C）多对一关系 D）一对一关系 （ B ）4. 计算机算法必须具备输入、输出和 等 5 个特性。 A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性 2 向一个长度为 n 的向量的第 i 个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 n-i+1 个元素。 4． 在 n 个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为 O（n）。 （ D ）4. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址: （A）必须是连续的 （B）部分地址必须是连续的 （C）一定是不连续的 （D）连续或不连续都可以 1.已知 L 是无表头结点的单链表，且 P 结点既不是首元结点，也不是尾元结点，请写出在 P 结点前插入 S 结点的 核心语句序列。 Q=P; P=L; while(P->next!=Q)P=P->next; P=Q; S->next=P->next; P->next=S; 2. 向栈中压入元素的操作是先 移动栈顶指针 ，后 存入元素 。 （ B ）2.判定一个栈 ST（最多元素为 m0）为空的条件是 Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0 Ｄ．ST->top=m0 （ A ）3.判定一个队列 QU（最多元素为 m0）为满队列的条件是 Ａ．QU->rear － QU->front = = m0 Ｂ．QU->rear － QU->front －1= = m0 Ｃ．QU->front = = QU->rear Ｄ．QU->front = = QU->rear+1 解：队满条件是元素个数为 m0。由于约定满队时队首指针与队尾指针相差 1，所以不必再减 1 了，应当选 A。当 然，更正确的答案应该取模，即：QU->front = = (QU->rear+1)% m0 4.写出下列程序段的输出结果（队列中的元素类型 QElem Type 为 char）。 void main( ){ Queue Q; Init Queue (Q); Char x=’e’; y=’c’; EnQueue (Q,’h’); EnQueue (Q,’r’); EnQueue (Q, y); DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,’a’); while(!QueueEmpty(Q)){ DeQueue (Q,y);printf(y); }; Printf(x); } 答：输出为“char”。 6. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素 的 行下标 、 列下标 和 元素值 。 10.求下列广义表操作的结果： （2） GetHead【GetTail【((a,b),(c,d))】】=== (c,d) ; （4） GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== （d） ; 2.设一棵完全二叉树具有 1000 个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为 2 的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。 答：最快方法：用叶子数＝[n/2]＝500 ，n2=n0-1=499。 另外，最后一结点为 2i 属于左叶子，右叶子是空的，所 以有 1 个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0. 4. 用 5 个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是 33 。 解：先构造哈夫曼树，得到各叶子的路径长度之后便可求出 WPL＝（4＋5＋3）×2＋（1＋2）×3=33 (15) (9) (6) （注：两个合并值先后不同会导致编码不同，即哈夫曼编码不唯一） 4 5 3 (3) （注：合并值应排在叶子值之后） 1 2 已知 P 结点，则不必“顺藤摸瓜”，直接链 接即可。 S->next=P->next; P->next=S;

(注：原题为选择题：A.32 B.33 C.34 D.15) (C)3.具 有个结点的完全二又树的深度为 7 o吧表示 logs(n) (D)「iog(+1l 大整数 (A)4.把一棵树转换为二叉树后，这棵二叉树的形态是 （A）唯一的 (B)有多种 (C)有多种，但根结点都没有左孩子 （D)有多种，但根结点都没有右孩子 3.【01年计算机研题】【严题集6.27③】给定二叉树的两种遍历序列，分别是： 前序遍历序列：D,A,C,E,B,H,F,G,I:中序遍历序列：D,C,B,E,H,A,G,1,F, 试画出二叉树B,并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。 解：方法是：由前序先确定oot,由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合 对应前序遍历序列中的元素集合，可继续确定r0的左右孩子。将他们分别作为新的r00,不断递归，则所有元 素都将股睡一确定，间题得解。 A (P604.27)把如图所示的树转化成一叉树 答：注意全部兄弟之间都要连线（包括度为2的兄弟），并注意原有连线结点一律归入左子树，新添连线结点一律 归入右子树。 A H/ 1.【严题集642③】编写递归算法，计算二叉树中叶子结点的数目。 解：思略：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。 法一：核心部分为： DLR(liuyu*root) 体中序遍历递归函数制 if(rootl=NULL -NULL)&&(root->rchild-NULL)){sum++.printf"%d\n",root->data). DLR(root->rchild);) return()

2 （注：原题为选择题：Ａ．32 Ｂ．33 Ｃ．34 Ｄ．15） （ C ）3. 具有 n(n>0)个结点的完全二叉树的深度为 。 (Ａ) log2(n) (Ｂ) log2(n) (Ｃ) log2(n) +1 (Ｄ) log2(n)+1 注 1：x 表示不小于 x 的最小整数； x表示不大于 x 的最大整数，它们与[ ]含义不同！ 注 2：选（A）是错误的。例如当 n 为 2 的整数幂时就会少算一层。似乎log2(n) +1是对的？ （ A ）4．把一棵树转换为二叉树后，这棵二叉树的形态是 。 （Ａ）唯一的 （Ｂ）有多种 （Ｃ）有多种，但根结点都没有左孩子 （Ｄ）有多种，但根结点都没有右孩子 3. 〖01 年计算机研题〗【严题集 6.27③】给定二叉树的两种遍历序列，分别是： 前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F， 试画出二叉树 B，并简述由任意二叉树 B 的前序遍历序列和中序遍历序列求二叉树 B 的思想方法。 解：方法是：由前序先确定 root，由中序可确定 root 的左、右子树。然后由其左子树的元素集合和右子树的集合 对应前序遍历序列中的元素集合，可继续确定 root 的左右孩子。将他们分别作为新的 root，不断递归，则所有元 素都将被唯一确定，问题得解。 D A C F E G B H I 2. （P60 4-27）把如图所示的树转化成二叉树。 答：注意全部兄弟之间都要连线（包括度为 2 的兄弟）,并注意原有连线结点一律归入左子树，新添连线结点一律 归入右子树。 A B E C K F H D L G I M J 1.【严题集 6.42③】编写递归算法，计算二叉树中叶子结点的数目。 解：思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。 法一：核心部分为： DLR(liuyu *root) /*中序遍历 递归函数*/ {if(root!=NULL) {if((root->lchild==NULL)&&(root->rchild==NULL)){sum++; printf("%d\n",root->data);} DLR(root->lchild); DLR(root->rchild); } return(0); }

核心部分为： 体中序遍历递归函数 if(rootl=NULL) titrotcsleh (rochil-NUL)mm). DLRroot-rehild) return(0): 6.【严题集626@】假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为Q07,0.19,Q.02, 以方便柄造哈夫曼树。日文潮两。解：万未后天文 【1(2,3),61,7,10】,.19,21,32 (10 0入1 (40 60) 192刘 32 (28) (17)、(11) 19 9》 7/06八(5) 2、3 0. 入3 字母号对应编码出现频率 010 11110 007 1110 006 的 8 1101 010 WPL=20.19+0.32+0.21)+40.07+0.06+0.10+50.02+0.03)=144+0.92+025-2.61 （B)2.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍 A.12 1 c.2 D （B)3.有8个结点的无向图最多有条边。 4.14 B.28 C.56 D.112 （C)4有8个结点的无向速通图最少有条边。 A. B.6 D.8 C)5.有8个结点的有向完全图有条边。 A.14 B.28 C.56 D.112 （B)6.用邻接表表示图进行广度优先遗历时，通常是采用 来实现算法的， A,找 B.队列 C.树 D.图 (A)7.用邻接表表示图进行深度优先遗历时，通常是采用 _来实现算法的。 A,栈 B.队列 C,树 D.图 （D)12.已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是

3 1.【严题集 6.42③】编写递归算法，计算二叉树中叶子结点的数目。 解：思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。 法一：核心部分为： DLR(liuyu *root) /*中序遍历 递归函数*/ {if(root!=NULL) {if((root->lchild==NULL)&&(root->rchild==NULL)){sum++; printf("%d\n",root->data);} DLR(root->lchild); DLR(root->rchild); } return(0); } 6. 【严题集 6.26③】假设用于通信的电文仅由 8 个字母组成，字母在电文中出现的频率分别为 0.07，0.19，0.02， 0.06，0.32，0.03，0.21，0.10。试为这 8 个字母设计哈夫曼编码。解：方案 1；哈夫曼编码 先将概率放大 100 倍，以方便构造哈夫曼树。 w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, .19, 21, 32 （100） （40） （60） 19 21 32 （28） （17） （11） 7 10 6 （5） 2 3 WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61 （ B ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 A．1/2 B. 1 C. 2 D. 4 （ B ）3. 有 8 个结点的无向图最多有 条边。 A．14 B. 28 C. 56 D. 112 （ C ）4. 有 8 个结点的无向连通图最少有 条边。 A．5 B. 6 C. 7 D. 8 （ C ）5. 有 8 个结点的有向完全图有 条边。 A．14 B. 28 C. 56 D. 112 （ B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。 A．栈 B. 队列 C. 树 D. 图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。 A．栈 B. 队列 C. 树 D. 图 （ D ）12. 已知图的邻接表如下所示，根据算法，则从顶点 0 出发按深度优先遍历的结点序列是 0 1 0 1 0 1 19 21 32 0 1 0 1 0 1 7 10 6 0 1 2 3 字母编号 对应编码 出现频率 1 1100 0.07 2 00 0.19 3 11110 0.02 4 1110 0.06 5 10 0.32 6 11111 0.03 7 01 0.21 8 1101 0.10

12☐3口 0 2 县 0 □3 02 （A)13.已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是 32□ 1 2 01 0 3 0/ 201 （A)14.深度优先遍历类似于二叉树的 A.先序遮历 B.中序遍历 C后序遍历D.层次遮历 （D)15.广度优先遍历类似于二叉树的 A.先序遍历 B中序遍历 C后序遍历D.层次遍历 二、填空题（每空1分，共20分) 2.有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点1的出度· 3.如果个顶点的图是一个环，则它有棵生成树。 (以任意一顶点为起点，得到-1条边) 三、简答题（每题6分，共24分） 1.【严愿集7.1①】已知如图所示的有向图，请给出该图的 13 每个顶点的入√出度； (2)邻接矩阵： 项点■23456 (3)邻接表： 人度 出度 （4)逆邻接表。 答案： 7.1(1) (2)邻接矩阵 顶点123456 0000007 入度321122 100100 010001 出度022313 001011 100000 山10010 (3)邻接表 (4)逆邻接表 A 6 间囚

4 （ A ）13. 已知图的邻接表如下所示，根据算法，则从顶点 0 出发按广度优先遍历的结点序列是 （ A ）14. 深度优先遍历类似于二叉树的 A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 （ D ）15. 广度优先遍历类似于二叉树的 A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 二、填空题（每空 1 分，共 20 分） 2. 有向图 G 用邻接表矩阵存储，其第 i 行的所有元素之和等于顶点 i 的 出度 。 3. 如果 n 个顶点的图是一个环，则它有 n 棵生成树。 （以任意一顶点为起点，得到 n-1 条边） 三、简答题（每题 6 分，共 24 分） 1. 【严题集 7.1①】已知如图所示的有向图，请给出该图的: （1） 每个顶点的入/出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表。 答案： A．0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3 A．0 3 2 1 B. 0 1 2 3 C. 0 1 3 2 D. 0 3 1 2 顶点 1 2 3 4 5 6 入度 出度

度优先生成树。 1 23 5678910 深度优先生成树 广度优先生成树 10 0 ⊙ ⊙ 1 ⊙ 。 81 0010 9000 001 ⊙ 101000 0 10000 ⊙ 一、填空题（每空1分，共10分） （A）2.【计研题2001】折半查找有序表(4,6,10,12,20,30,50,70,8器，100).若查找表中元素58， 比较大小，查找结果是失败。 A.20,70,30,50 B.30,88,70 50 C.20,50 D.30,88,50 4.【计研愿1999】设哈希(Hash)表的地址范围为0~17，哈希函数为：H(K)=KMOD16。 K为关键字，用线性探测法再散列法处理冲突，输入关赞字序列： 10,24,32,17,31,30,46,47,40,63,49) 行比较 若查找 (4)假定每个关键字的春找率相等，求查找成功时的平均查找长度 解：(1)画表如下： 01234567891011121314151617 32176349 24401030314647 (2)查找63，首先要与H(63)=63%16=15号单元内容比较，即63vs31,no: 然后顺移，与46,47,32,17,63相比，一共比较了6次1 产0先要与600%16=2号单元内容比。但因为12号单元为空位当有空标记.所以应当只 (4)对干里色数据元素，各出技1次：共6次 对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次， “47”需要3次， 所以ASL=1/11(6+2+3×3)=17111=1.5454545454≈1.55 四、分析题（每小题6分，共24分） 2.【全国专升本考题】在一棵空的二叉查找树中依次插入关键字序列为12,7,17,11,16,2,13,9,21,4， 请画出所得到的二叉查找树。 答： 2、 21 62n 5

5 3. 【严题集 7.5②】已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点 1 出发进行遍历所得的深 度优先生成树和广度优先生成树。 一、填空题（每空 1 分，共 10 分） （ A ）2．【计研题 2001】折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素 58， 则它将依次与表中 比较大小，查找结果是失败。 A．20，70，30，50 B．30，88，70，50 C．20，50 D．30，88，50 4. 【计研题 1999】设哈希（Hash）表的地址范围为 0～17，哈希函数为：H（K）＝K MOD 16。 K 为关键字，用线性探测法再散列法处理冲突，输入关键字序列： （10，24，32，17，31，30，46，47，40，63，49） 造出 Hash 表，试回答下列问题： （1） 画出哈希表的示意图； （2） 若查找关键字 63，需要依次与哪些关键字进行比较？ （3） 若查找关键字 60，需要依次与哪些关键字比较？ （4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 解： （1）画表如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 32 17 63 49 24 40 10 30 31 46 47 （2） 查找 63,首先要与 H(63)=63%16=15 号单元内容比较，即 63 vs 31 ,no; 然后顺移，与 46,47,32,17,63 相比，一共比较了 6 次！ （3）查找 60,首先要与 H(60)=60%16=12 号单元内容比较，但因为 12 号单元为空（应当有空标记），所以应当只 比较这一次即可。 （4） 对于黑色数据元素，各比较 1 次；共 6 次； 对红色元素则各不相同，要统计移位的位数。“63”需要 6 次，“49”需要 3 次，“40”需要 2 次，“46”需要 3 次， “47”需要 3 次， 所以 ASL=1/11（6＋2＋3×3）＝17/11=1.5454545454≈1.55 四、分析题（每小题 6 分，共 24 分） 2. 【全国专升本考题】在一棵空的二叉查找树中依次插入关键字序列为 12，7，17，11，16，2，13，9，21，4， 请画出所得到的二叉查找树。 答： 12 7 17 2 11 16 21

49 13 验算方法：用中序遍历应得到排序结果：2,4,7,9,11,12,13,16,17,21 4.选取散列函数H(key)=(3*ky)%1山，用线性探测法处理冲突，对下列关健码序列构造一个散列地址空间 为0~10，表长为11的散列表，22,41,53,08,46,30,01,31,66. 解：由题意知，m=11(刚好为素数) 地址位 接指计一 则(22*3)%11-6 2.6 13031以11=8 101*31以11-0.3 (31*3)%11=8.5 (66*3)%11=9.0 10 [2266418305346131☐ 45 910 34,7 、填空题（每空1分，共24分） 1,大多数排序算法都有两个基本的操作：比较（两个关健字的大小）和移动（记录或政变指向记录的推 卧)。 2.在对一组记录(54,38,96,23,15.72. 5,83)进行直接插入排序时，当把第7个记录60插入到有 洋表胡技插受位童多青比较次同可的定为 5.对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是0（山·若对其进行快速排序，在最 环的情况下所需要的时间是O)。 7 H.C.O.P.A.M.S.R.D.F.X.Y 初始步长为4的希尔(She)排序一精的结果是PACS.O.D,FX,RH,MY: 二路归并排序一趙扫描的结果是HOCY,A卫山SD,REX； 快速排序 一趙扫描的结果是 EH.C.D.P.A.M.Q.R.S,Y,X 推排序初始建堆的结果是AD.CR,F Q.M.S.Y,P山X。 快速排序 和归并排 ,其次选取快速排庄方法，最后选取归并排庄方法； 若只从平均情况下最快考，则应选取快速排 方移 若只从最坏情况下最快并且要节省内存考忠，则应选取堆排庄方法。 二、单项选择题（每小题1分，共18分） （C)8.若一组记录的排序码为（4679,56384084)，则利用快速排序的方法，以第一个记录为基准得到 的一次划分结果为 6

6 地址 值 链接指针 0 22 1 1 66 2 41 3 3 08 4,7 4 30 5 53 6 46 7 01 8 31 9 10 4 9 13 验算方法： 用中序遍历应得到排序结果： 2,4,7,9,11,12,13,16,17，21 4. 选取散列函数 H（key）=（3*key）%11，用线性探测法处理冲突，对下列关键码序列构造一个散列地址空间 为 0～10，表长为 11 的散列表，{22，41，53，08，46，30，01，31，66}。 解：由题意知，m=11(刚好为素数) 则(22*3)%11=6.0 (41*3)%11=11.2 (53*3)%11=14.5 (08*3)%11=2.2 (46*3)%11=12.6 (30*3)%11=8.2 (01*3)%11=0.3 (31*3)%11=8.5 (66*3)%11=9.0 22 66 41 8 30 53 46 1 31 0 1 2 3 4 5 6 7 8 9 10 1 3 4，7 一、填空题（每空 1 分，共 24 分） 1. 大多数排序算法都有两个基本的操作： 比较（两个关键字的大小） 和 移动（记录或改变指向记录的指 针） 。 2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第 7 个记录 60 插入到有 序表时，为寻找插入位置至少需比较 3 次。(可约定为，从后向前比较) 5. 对于 n 个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是 O(n2 ) 。若对其进行快速排序，在最 坏的情况下所需要的时间是 O(n2 ) 。 7 8.设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则： 冒泡排序一趟扫描的结果是 H, C, Q, P, A, M, S, R, D, F, X ,Y ； 初始步长为 4 的希尔（shell）排序一趟的结果是 P, A, C, S, Q, D, F, X , R, H,M, Y ； 二路归并排序一趟扫描的结果是 H, Q, C, Y，A, P, M, S, D, R, F, X ； 快速排序一趟扫描的结果是 F, H, C, D, P, A, M, Q, R, S, Y，X ； 堆排序初始建堆的结果是 A, D, C, R, F, Q, M, S, Y，P, H, X 。 9. 在堆排序、快速排序和归并排序中， 若只从存储空间考虑，则应首先选取 堆排序 方法，其次选取 快速排序 方法，最后选取 归并排序 方法； 若只从排序结果的稳定性考虑，则应 选取归并排序方法； 若只从平均情况下最快考虑，则应选取快速排序方法； 若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。 二、单项选择题（每小题 1 分，共 18 分） （ C ）8．若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得到 的一次划分结果为

A.38,40,46,56,79,84 B.40,38,46,79,56,84 C.40,38,46,56,79,84 D.40,38,46,84,56,79 （D)12.下列关键字序列中，是堆。 A.16,72,31,23,94,53B.94,23,31,72,16,53 C.16,53,23,94,31,72 D.16,23,53,31,94,72 (C)17.下述几种排序方法中，要求内存最大的是 A.插入排序 B.快速排序 C.归并排序 D.选择排序 三、简答题（每小题4分，共36分） 3.用某种排序方法对线性表（25,84,21,47,15,27,68,35,20)进行排序时，元素序列的变化情况如下： 25,84,21,47,15,27,68,35,20+20,15,21,25,47,27,68,35,84+15,20,21,25,35,27,47,68,84+ 15,20,21,25,27,35,47,68,84,问采用的是什么排序方法？ 答：用的是快速排序方法。注意每一趙要振荡完全部元素才算一个中间结果。 7

7 Ａ. 38, 40, 46, 56, 79, 84 Ｂ. 40,38, 46 , 79, 56, 84 Ｃ. 40, 38，46, 56, 79, 84 Ｄ. 40, 38,46, 84, 56, 79 （ D ）12．下列关键字序列中， 是堆。 Ａ. 16,72,31,23,94,53 Ｂ. 94,23, 31, 72, 16, 53 Ｃ. 16, 53, 23,94,31, 72 Ｄ. 16, 23, 53,31, 94, 72 （ C ）17． 下述几种排序方法中，要求内存最大的是 Ａ. 插入排序 Ｂ.快速排序 Ｃ. 归并排序 Ｄ. 选择排序 三、简答题（每小题 4 分，共 36 分） 3. 用某种排序方法对线性表（25, 84，21,47,15,27,68,35,20）进行排序时，元素序列的变化情况如下： 25, 84，21,47,15,27,68,35,20 → 20, 15, 21, 25，47, 27,68,35, 84 → 15, 20, 21, 25，35, 27, 47, 68, 84→ 15, 20, 21, 25，27, 35, 47, 68, 84， 问采用的是什么排序方法？ 答：用的是快速排序方法。注意每一趟要振荡完全部元素才算一个中间结果