《数据结构应用题答案.doc》由会员分享，可在线阅读，更多相关《数据结构应用题答案.doc（27页珍藏版）》请在金锄头文库上搜索。
1、数据结构应用题答案数据结构应用题答案第2章线性表1.设指针变量p指向双向链表中结点A，指针变量q指向被插入结点的后边插入结点B的操作序列（设双向链表中结点的两个指针域分别为答：操作序列以下：q-rlink=p-rlink;p-rlink=q;B，要求给出在结点Allink和rlink）。q-rlink-llink=q;q-llink=p;注意答案不独一第3章栈和行列1. 设有编号为1，2，3，4的四辆列车，次序进入一个栈式结构的车站，详细写出这四辆列车开出车站的全部可能的次序。答：合计14种，分别是：1234，1243，1324，1342，1432，2134，2143，2341，2314，24
2、31，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）能获得输出次序为1，3，5，4，2，6的序列。获得的操作以下：1入栈后即出栈，得到序列1；2，3入栈后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. 分别从行列和栈中拿出首个字符3. 比较拿出的字符，若相等，持续分别从行列和栈中取首个字符；不然跳出循环，并设置标记flag=0;4. 若行列和栈中的字符都
4、取完，则结束，设置标记flag=1;5.flag=1,表示字符以前去后和从后往前的序列完整般配，该字符串属于回文6.flag=0,表示字符以前去后和从后往前的序列不完整般配，该字符串不属于回文方法二：使用栈。将字符串的前一半入栈，再挨次出栈，与后一半进行比较，如有不等则不是回文；若挨次相等，则是回文。注意：此题要求简答算法思路，其实不要求写出详细算法。4.试写出循环行列判空和判满的条件（行列最大容量为M）。答：假定循环行列最大储存容量为M判空：Q.front=Q.rear（1）判满：（Q.rear+1）%M=Q.front（2）评分标准：给出（1）和（2）式分别得3分，其余酌情扣分。5.假定Q
5、0.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入队；状态4：front=2，rear=1；p不可以入队，因为行列已经满了。评分标准：状态1、状态4各2分，状态2、状态3各1分，状态4中状态1分，原因1分。6.若元
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,试写出借助一个栈可获得的两个输出序列和两个不可以获得的输出序列。答：借助栈结构，n个入栈元素可获得1/(n+1)(2n）！/（n!*n!）)种出栈序列。此题4个元素，可有14种出栈序列，abcd和dcba就是此中两种。但da
7、bc和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-top0=1时为栈满。9.假如输入序列为123456,试问可否经过栈结构获得以下两个序列:435612和135426；请说明为何不可以或如何才能获得。答：输入序列为123456，不可以得出435612，其原因是，输出序列最后两元素是12，前面4个元素（4356）获得后，栈中
8、元素剩12，且2在栈顶，不行能栈底元素1在栈顶元素2之前出栈。获得135426的过程以下：1入栈并出栈，获得部分输出序列1；而后2和3入栈，3出栈，部分输出序列变成：13；接着4和5入栈，5，4和2挨次出栈，部分输出序列变成13542；最后6入栈并退栈，得最后结果135426。10.假定以数组sq0.7寄存循环行列元素,变量f指向队头元素的前一地点,变量r指向队尾元素，如用A和D分别表示入队和出队操作，请给出：（ 1）队空的初始条件；（ 2）履行操作序列A3D1A5D2A1D2A4时的状态,并作必需的说明。（A3表示三次入队操作，D1表示一次出队操作）答：（1）队空的初始条件：f=r=0；（2
9、）履行操作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；履行操作D2后，f=5，r=1；履行操作A4后，按溢出办理。因为履行A3后，r=4，这时队满，若再履行A操作，则犯错。11.内存中一片连续空间（不如假定地点从1到m）供应给两个栈S1和S2使用，如何分派这部分储存空间，使得对任一个栈，仅当这部分空间全满时才发生上溢1答：S1和S2共享内存中一片连续空间（地点1到m），能够将S1和S2的栈底设在两头，两栈顶向共享空间的中心延长，仅当两栈顶指针相
10、邻（两栈顶指针值之差的绝对值等于1）时，判断为栈满，当一个栈顶指针为0，另一个栈顶指针m+1时为两栈均空。12. 设一数列的输入次序为123456，若采纳货仓结构，并以A和D分别表示入栈和出栈操作，试问经过入出栈操作的合法序列。（ 1）可否获得输出次序为325641的序列。（ 2）可否获得输出次序为154623的序列。答：（1）能获得325641。在123挨次进栈后，3和2出栈，得部分输出序列32；而后4，5入栈，5出栈，得部分出栈序列325；6入栈并出栈，得部分输出序列3256；最退后栈，直到栈空。得输出序列325641。其操作序列为AAADDAADADDD。（2）不可以获得输出次序为154
11、623的序列。部分合法操作序列为ADAAAADDAD，获得部分输出序列1546后，栈中元素为23，3在栈顶，故不行能2先出栈，得不到输出序列154623。13.设输入序列为2，3，4，5，6，利用一个栈能获得序列2，5，3，4，6吗？为何？栈能够用单链表实现吗？答：不可以获得序列253463，4，前面2，；其原因是，输出序列第三四位两元素是个元素（2，5）获得后，栈中元素剩3，4，且4在栈顶，栈底元素3不行能在栈顶元素4以前出栈。栈能够用单链表实现，这就是链栈。因为栈只在栈顶操作，所以链栈往常不设头结点。14.有5个元素，其入栈序次为：A，B，C，D，E，在各样可能的出栈序次中，以元素C，D最
12、初出栈（即C第一个且D第二个出栈）的序次有哪几个？用S表示入栈，X表示出栈，写出可能获得序次的操作序列。答：三个：CDEBA，CDBEA，CDBAECDEBA操作序列：SSSXSXSXXX；CDBEA操作序列：SSSXSXXSXX；CDBAE操作序列：SSSXSXXXSX；15. 若以1、2、3、4作为双端行列的输入序列，试分别求出以下条件的输出序列：（ 1）能由输入受限的双端行列获得，但不可以由输出受限的双端行列获得的输出序列；（ 2）能由输出受限的双端行列获得，但不可以由输入受限的双端行列获得的输出序列；（ 3）既不可以由输入受限的双端行列获得，也不可以由输出受限的双端行列获得的输出序列。
13、答：（1）4132（2）4213（3）423116. 设一个双端行列，元素进入该行列的序次为a，b，c，d。求既不可以由输入受限的双端行列获得,又不可以由输出受限的双端行列获得的输出序列。答：既不可以由输入受限的双端行列获得，也不可以由输出受限的双端行列获得的输出序列是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.用一维数组寄存的一棵完整二叉树以下表所示ABCDEFGHIJKL写出先序、中序、后序、层次遍历该二叉树时接见结点的次序。答案HIDJKEBLFGCAX23.（5分）对任何一棵二叉树T，假如其终端结点数为n0，度为2的结点数为n2，证明：n0=n2+1。X34.表达
