1、数据结构应用题答案第 2章 线性表1.设指针变量 p指向双向链表中结点 A，指针变量 q指向被插入结点 B，要求给出在结点 A的后面插入结点 B的操作序列（设双向链表中结点的两个指针域分别为 llink和 rlink） 。答：操作序列如下：q-rlink = p-rlink ; p-rlink = q ;q-rlink-llink = q ; q-llink = p ;注意答案不唯一 第 3章 栈和队列1.设有编号为 1，2，3，4 的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。答：共计 14种，分别是：1234， 1243， 1324， 1342， 14
2、32， 2134， 2143， 2341， 2314， 2431， 3214， 3241， 3421， 43212.如果输入序列为 1，2，3，4，5，6，试问能否通过栈结构得到以下两个序列：4，3，5，6，1，2 和 1，3，5，4，2，6；请说明为什么不能或如何才能得到。答：（1）不能得到 4，3，5，6，1，2 ；因为 1，2，3，4 入栈后；4，3 出栈；得到序列4，3；栈中还有 1，2；5 入栈后即出栈，得到序列 4，3，5；6 入栈后即出栈，得到序列4，3，5，6；此时，栈中还有 1，2；必须 2 先出栈，然后 1 再出栈，1 不可能在 2 之前出栈。故而得不到该序列。（2）能得到
3、输出顺序为 1，3，5，4，2，6 的序列。得到的操作如下：1 入栈后即出栈，得到序列 1；2，3 入栈后 3即出栈，得到序列 1，3；4，5 入栈后，5 出栈，4 出栈，得到序列 1，3，5，4；2 出栈，得到序列 1，3，5，4，2；6 入栈后即出栈，得到序列1，3，5，4，2，6。3.假设正读和反读都相同的字符序列为“回文” ，例如， abba和abcba是回文，abcde 和ababab则不是回文。假设一字符序列已存入计算机，请用堆栈判断其是否为回文，简述算法。答：方法一：使用数据结构:循环队列和顺序栈。算法思路为：1.将字符串按照用户输入的顺序分别入栈和队列2.分别从队列和栈中取出首
4、个字符3.比较取出的字符，若相等，继续分别从队列和栈中取首个字符；否则跳出循环，并设置标志 flag=0;4.若队列和栈中的字符都取完，则结束，设置标志 flag=1;5.flag=1,表示字符从前往后和从后往前的序列完全匹配，该字符串属于回文6.flag=0,表示字符从前往后和从后往前的序列不完全匹配，该字符串不属于回文方法二：使用栈。将字符串的前一半入栈，再依次出栈，与后一半进行比较，若有不等则不是回文；若依次相等，则是回文。注意：本题要求简答算法思路，并不要求写出具体算法。4.试写出循环队列判空和判满的条件（队列最大容量为 M） 。答：假设循环队列最大存储容量为 M 判空：Q.front
5、=Q.rear （1）判满：（Q.rear+1）%M=Q.front （2）评分标准：给出（1）和（2）式分别得 3分，其他酌情扣分。5.假设 Q0.10是一个循环队列，初始状态为 front=rear=0，画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。d,e,b,g,h入队；d,e 出队；i,j,k,l,m 入队；n,o,p 入队答：（图自己根据解答画出）d,e,b,g,h 入队；状态 1：front=0，rear=5；d,e出队；状态 2：front=2，rear=5；i,j,k,l,m入队；状态 3：front=2，rear=10；n,o,p入队；
6、状态 4：front=2，rear=1；p 不能入队，因为队列已经满了。评分标准：状态 1、状态 4各 2分，状态 2、状态 3各 1分，状态 4中状态 1分，理由 1分。6.若元素的进栈序列为：A、 B、C、D、E，运用栈操作，能否得到出栈序列B、C、A、E 、D 和 D、B、A、C 、E？为什么？答：能得到出栈序列 B、C、A 、E、D，不能得到出栈序列 D、B、A、C、E。其理由为：若出栈序列以 D 开头，说明在 D 之前的入栈元素是 A、B 和 C，三个元素中 C 是栈顶元素，B 和 A 不可能早于 C 出栈，故不可能得到 D、B、A、C、E 出栈序列。7.设输入序列为 a,b,c,d
7、,试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列。答：借助栈结构，n 个入栈元素可得到 1/(n+1)(2n）！/（n!*n! ）)种出栈序列。本题 4 个元素，可有 14 种出栈序列，abcd 和 dcba 就是其中两种。但 dabc 和 adbc 是不可能得到的两种。8.将两个栈存入数组 V1.m应如何安排最好？这时栈空、栈满的条件是什么？答：设栈 S1和栈 S2共享向量 V1.m，初始时，栈 S1的栈顶指针 top0=0，栈 S2的栈顶指针 top1=m+1，当 top0=0为左栈空，top1=m+1 为右栈空；当 top0=0并且top1=m+1时为全栈空。当 top1-
8、top0=1时为栈满。9.如果输入序列为 1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2和 1 3 5 4 2 6；请说明为什么不能或如何才能得到。答：输入序列为 123456，不能得出 435612，其理由是，输出序列最后两元素是 12，前面4个元素（4356）得到后，栈中元素剩 12，且 2在栈顶，不可能栈底元素 1在栈顶元素 2之前出栈。得到 135426的过程如下：1 入栈并出栈，得到部分输出序列 1；然后 2和 3入栈，3出栈，部分输出序列变为：13；接着 4和 5入栈，5，4 和 2依次出栈，部分输出序列变为13542；最后 6入栈并退栈，得最终
9、结果 135426。10.假设以数组 sq0.7存放循环队列元素,变量 f指向队头元素的前一位置,变量 r指向队尾元素，如用 A和 D分别表示入队和出队操作，请给出：（1）队空的初始条件；（2）执行操作序列 A3 D1 A5 D2 A1 D2 A4时的状态,并作必要的说明。 （A3 表示三次入队操作，D1 表示一次出队操作）答：（1）队空的初始条件：f=r=0；（2）执行操作 A3后，f=0，r=3；/A3 表示三次入队操作执行操作 D1后，f=1，r=3；/D1 表示一次出队操作执行操作 A5后，f=1，r=0；执行操作 D2后，f=3，r=0；执行操作 A1后，f=3，r=1；执行操作 D
10、2后，f=5，r=1；执行操作 A4后，按溢出处理。因为执行 A3后，r=4，这时队满，若再执行 A操作，则出错。11.内存中一片连续空间（不妨假设地址从 1到 m）提供给两个栈 S1和 S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢 1 答： S1和 S2共享内存中一片连续空间（地址 1到 m） ，可以将 S1和 S2的栈底设在两端，两栈顶向共享空间的中心延伸，仅当两栈顶指针相邻（两栈顶指针值之差的绝对值等于1）时，判断为栈满，当一个栈顶指针为 0，另一个栈顶指针 m+1时为两栈均空。12.设一数列的输入顺序为 123456，若采用堆栈结构，并以 A和 D分
11、别表示入栈和出栈操作，试问通过入出栈操作的合法序列。（1）能否得到输出顺序为 325641的序列。（2）能否得到输出顺序为 154623的序列。答：（1）能得到 325641。在 123依次进栈后，3 和 2出栈，得部分输出序列 32；然后4，5 入栈，5 出栈，得部分出栈序列 325；6 入栈并出栈，得部分输出序列 3256；最后退栈，直到栈空。得输出序列 325641。其操作序列为 AAADDAADADDD。（2）不能得到输出顺序为 154623的序列。部分合法操作序列为 ADAAAADDAD，得到部分输出序列 1546后，栈中元素为 23，3 在栈顶，故不可能 2先出栈，得不到输出序列1
12、54623。13.设输入序列为 2，3，4，5，6，利用一个栈能得到序列 2，5，3，4，6 吗？为什么？栈可以用单链表实现吗？ 答：不能得到序列 2，5，3，4，6；其理由是，输出序列第三四位两元素是 3，4，前面 2个元素（2，5）得到后，栈中元素剩 3，4，且 4在栈顶，栈底元素 3不可能在栈顶元素 4之前出栈。栈可以用单链表实现，这就是链栈。由于栈只在栈顶操作，所以链栈通常不设头结点。14.有 5个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素 C，D最先出栈（即 C第一个且 D第二个出栈）的次序有哪几个？用 S表示入栈，X 表示出栈，写出可能得到次序的操作序列
13、。答：三个：CDEBA，CDBEA，CDBAECDEBA操作序列：SSSXSXSXXX；CDBEA 操作序列：SSSXSXXSXX；CDBAE 操作序列：SSSXSXXXSX；15.若以 1、2、3、4 作为双端队列的输入序列，试分别求出以下条件的输出序列：（1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列；（2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；（3）既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。答：（1）4132 （2）4213 （3）423116.设一个双端队列，元素进入该队列的次序为 a，b，c，d
14、。求既不能由输入受限的双端队列得到,又不能由输出受限的双端队列得到的输出序列。答：既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是dbca。第 6章 树和二叉树1.（8 分）已知一棵树的边的集合表示为：(L,N),(G,K),(G,L),(G,M),(B,E),(B,F),(D,G),(D,H),(D,I),(D,J),(A,B),(A,C),(A,D)画出这棵树，并回答下列问题：(1)树根是哪个结点？哪些是叶子结点？哪些是非终端结点？(2)树的度是多少？各个结点的度是多少？(3)树的深度是多少？各个结点的层数是多少？以结点为根的子树的深度是多少？X72.用一维数组存
15、放的一棵完全二叉树如下表所示A B C D E F G H I J K L写出先序、中序、后序、层次遍历该二叉树时访问结点的顺序。答案 HIDJKEBLFGCAX23.（5 分）对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2的结点数为 n2，证明：n0=n2+1。X34.叙述并证明二叉树的性质 3。 X35.（8 分）已知一棵二叉树如下，（1）请分别写出按前序、中序、后序和层次遍历时得到的结点序列。（2）如果此二叉树由森林转换得到，请画出原森林中的各棵树。X1X56.（8 分）画出由下列序列得到的二叉树以及由此二叉树转化的森林：先序：EBADCFHGIKJ；中序：ABCDEFGHIJ
16、K。X87.有二叉树中序序列为：ABCEFGHD，后序序列为：ABFHGEDC，请画出此二叉树，并写出二叉树的先序遍历序列和层次遍历序列。答案根据后序序列知根结点为 C，因此左子树：中序序列为 AB 后序序列为 AB 右子树：中序序列为 EFGHD ，后序序列为：FHGED 依次推得该二叉树结构如下图所示先序遍历序列：CBADEGFH层次遍历序列：CBDAEGFHX58.（8 分）二叉树 T的前序遍历序列和中次遍历序列分别是 ABCDEFG和 CBEDAFG，试画出该二叉树，并写出二叉树的后序遍历序列和层次遍历序列。X99.（6 分）二叉树的先序序列为 EBADCFHGIKJ；二叉树的中序序列
17、为 ABCDEFGHIJK，请画出该二叉树，并写出二叉树的后序遍历序列和层次遍历序列。X1010.（8 分）设一棵二叉树的先序、中序遍历序列分别为先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C请画出该二叉树，并将这棵二叉树转换成对应的树（或森林） 。X411.（8 分）设一棵二叉树的前序序列为 ABDGECFH，中序序列为：DGBEAFHC 。试画出该二叉树。并写出后序和层次遍历序列。12.（6 分）设给定一个权值集合 W=(3，5，7，9，11) ，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度 WPL。X613.（8 分）
18、假设字符 a,b,c,d,e,f,g,h的使用频度分别是0.15,0.19,0.07,0.08,0.04,0.23，0.13，0.11 画出哈夫曼树并写出 a,b,c,d,e,f,g,h的Huffman（哈夫曼）编码。X514.（8 分）假设字符 a,b,c,d,e,f的使用频度分 0.07,0.09,0.12,0.22,0.23,0.27，写出 a,b,c,d,e,f的 Huffman（哈夫曼）编码。X715.（8 分）假设字符 a,b,c,d,e,f的使用频度分别是0.07,0.10,0.12,0.16,0.25,0.30，构造哈夫曼树并写出 a,b,c,d,e,f的哈夫曼编码。16.（6
19、 分）试分别画出具有三个结点的树和三个结点的二叉树的不同形态。X617.请画出下图所示的树所对应的二叉树。答案：18.（6 分）请画出与下列二叉树对应的森林。X10X819.已知一棵树边的集合为, , ,，请回答下列问题：x10（1）哪个是根结点？（2）X8 哪些是叶子结点？X10 哪些是分支结点？X8（3）哪个是结点 G的双亲结点？（4）哪些是结点 G的祖先？X8（5）哪些是结点 G的孩子？X8（6）哪些是结点 E的子孙？X8（7）哪些是结点 E的兄弟？哪些是结点 F的兄弟？（8）结点 B和 N的层次号分别是多少？（9）树的深度是多少？（10）以结点 C为根的子树的深度是多少？答案（1）A；
20、 （2）D, M, N, F, J, K, L； (3) C； (4) A, C； (5) J,K；(6) I, M, N； (7) E 的兄弟是 D，F 的兄弟是 G和 H；（8）2, 5； (9) 5； (10) 3。X920.假设在树中，结点 x是结点 y的双亲时，用（x，y）来表示树边。已知一棵树边的集合为：（i，m） ， （i，n） ， （e，i） ， （b，e） ， （b，d） ， （a，b） ， （g，j） ， （g，k） ， （c，g） ，（c，f） ， （h，l） ， （c，h） ， （a，c）。用树形表示法画出此树，并回答下列问题：（1）哪个是根结点：（2）哪些是叶结点？（
21、3）哪个是 g的双亲？（4）哪些是 g的祖先？（5）哪些是 g的孩子？（6）哪些是 e的子孙？（7）哪些是 e的兄弟？哪些是 f的兄弟？（8）结点 b和 n的层次各是多少？（9）树的深度是多少？（10）以结点 c为根的子树的深度是多少？（11）树的度数是多少？答案：（1）根结点：a （2）叶结点：m、n、d、l、h、j、k （3）g 的双亲：c（4）g 的祖先：a、c （5）g 的孩子：j、k （6）e 的子孙：i、m、n（7）e 的兄弟：d （8）b 的层次：2 （9）树的深度：5 f 的兄弟：g、hn 的层次；5（10）以结点 c为根的子树的深度：3 （11）树的度数：321.已知一棵树边
22、的结点为（I,M） ，(I，N),(E，I),(B，E)，(B，D),(C，B),(G，L)，(G，K)，(A，G)，(A，F),(H，J)，(A，H)，(C，A)，试画出这棵树，并回答下列问题：(1)哪个是根结点？(2)哪些是叶子结点？(3)树的深度是多少？答案如下图所示。 （图不对，缺结点 H的孩子结点 J， ）根结点 C，叶子结点 F、K、L、J、D、M、N，深度 5 五、应用题（每小题 6分，共 48分）3.答：快速排序的思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。评分标准：
23、只要基本思想对就可得分。3、 （8 分）二叉树为：AEGDCFB后序遍历序列：CEDBGFA，层次遍历序列：ABFCDGE评分标准：得出二叉树得 4分，给出后序和层次遍历序列得 4分，步骤不全酌情给分。4、 （8 分）哈夫曼树：c de hb fag哈夫曼编码：a：011 b：10 c：00000 d：0010e：0001 f：11 g：001 h：0101 评分标准：得出哈夫曼树给 4分，给出哈夫曼编码给 4分，步骤不全酌情给分。5、 （10 分）（1）邻接表存储结构ABCDEF1 3 0 21 3 4 0 2 4 5 1 33 （2）深度优先遍历序列：BADCEF广度优先遍历序列：BACE
24、DF评分标准：画出邻接表存储结构得 5分，求出深度优先和广度优先遍历序列得 5分，其他情况全酌情给分。6、 （8 分）二叉判定树6 0 1 0 03 27 23 81 24 55 2 0 9 0平均查找长度：ASL=（1+2*2+4*3+3*4）/10=2.9 评分标准：得出二叉判定树给 6分，求出平均查找长度给 2分，步骤不全酌情给分。2、 （6 分）快速排序的思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。评分标准：只要基本思想对就可得分。3、 （8 分）二叉树为：AEGDCFB后序
25、遍历序列：CEDBGFA，层次遍历序列：ABFCDGE评分标准：得出二叉树得 4分，给出后序和层次遍历序列得 4分，步骤不全酌情给分。4、 （8 分）哈夫曼树：c de hb fag哈夫曼编码：a：011 b：10 c：00000 d：0010e：0001 f：11 g：001 h：0101 评分标准：得出哈夫曼树给 4分，给出哈夫曼编码给 4分，步骤不全酌情给分。5、 （10 分）（1）邻接表存储结构ABCDEF1 3 0 21 3 4 0 2 4 5 1 33 （2）深度优先遍历序列：BADCEF广度优先遍历序列：BACEDF评分标准：画出邻接表存储结构得 5分，求出深度优先和广度优先遍历
26、序列得 5分，其他情况全酌情给分。6、 （8 分）二叉判定树6 0 1 0 03 27 23 81 24 55 2 0 9 0平均查找长度：ASL=（1+2*2+4*3+3*4）/10=2.9 评分标准：得出二叉判定树给 6分，求出平均查找长度给 2分，步骤不全酌情给分。四、算法题（22 分）1、 （6 分）评分标准：每写错一种形态扣 1分。2、 （8 分）（1）前序：ABDGCEFH 中序：DGBAECHF 后序：GDBEHFCA 层次：ABCDEFGH（2）二叉树所对应的森林：ABD GCEFH评分标准：第一小题每个 1分，第二小题三棵树 4分，每错一个扣 1分。3、 （8 分）二叉排序树
27、的构造过程如下：4 63 98 84 54 68 84 54 68 84 64 67 05 81 0 14 53 98 84 67 05 83 94 5 8 84 67 03 94 5 8 84 65 87 03 41 01 0 16 64 53 98 84 67 01 06 61 0 15 84 53 98 84 67 01 0 11 0 5 84 53 98 8评分标准：没有过程或过程不全酌情减分4、 （8 分）15624391562431 091562431 091 11562431 091 151562431 091 156评分标准：结果正确得 5分，步骤不全酌情扣分。5、 （10 分）
