《数据结构第2和3章应用题答案》由会员分享，可在线阅读，更多相关《数据结构第2和3章应用题答案（3页珍藏版）》请在金锄头文库上搜索。
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， 1432， 2134， 2143
2、， 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）能得到输出顺序为1，3，5，4，2，6的序列。得到的操作如下：1入栈后即
3、出栈，得到序列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.分别从队列和栈中取出首个字符3.比较取出的字符，若相等，继续分别从队列和栈中取首个字符；否则跳出循环，并设置标志flag
4、=0;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）式分
5、别得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入队；状态4：front=2，rear=1；p不能入队，因为队列已经满了。评分标准：状态1、状态4各2分，状态2、状态3各1分，状态4
6、中状态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,试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列。答：借助栈结构，n个入栈元素可得到1/(n+1)(2n）！/（n!*n!）)种出栈序列。本题4个元素，可有14种出栈序列，abcd和dc
7、ba就是其中两种。但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-top0=1时为栈满。9.如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2和1 3 5 4 2 6；请说明为什么不能或如何才能得到。答：输入序列为123456，不能得出435612，其理由是，输出序列最后
8、两元素是12，前面4个元素（4356）得到后，栈中元素剩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）执行操作序列A3 D1 A5 D2 A1 D2 A4时的状态,并作必要的说明。（A3表示三次入队操作，D1表
9、示一次出队操作）答：（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；执行操作D2后，f=5，r=1；执行操作A4后，按溢出处理。因为执行A3后，r=4，这时队满，若再执行A操作，则出错。11.内存中一片连续空间（不妨假设地址从1到m）提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢1 答： S1和S2共享内存中一片连续空间（地址1到m），可以将S1和S
10、2的栈底设在两端，两栈顶向共享空间的中心延伸，仅当两栈顶指针相邻（两栈顶指针值之差的绝对值等于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。其操作序列为A
11、AADDAADADDD。（2）不能得到输出顺序为154623的序列。部分合法操作序列为ADAAAADDAD，得到部分输出序列1546后，栈中元素为23，3在栈顶，故不可能2先出栈，得不到输出序列154623。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个元素，其入栈次序
12、为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？用S表示入栈，X表示出栈，写出可能得到次序的操作序列。答：三个：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。求既不能由输入受限的双端队列得到,又不能由输出受限的双端队列得到的输出序列。答：既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是dbca。
