数据结构应用题答案VIP专享

精品文档---下载后可任意编辑第 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， 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 入栈后即出栈，得到序列 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’则不是回文。假设一字符序列已存入计算机，请用堆栈推断其是否为回文，简述算法。答：方法一：使用数据结构:循环队列和顺序栈。算法思路为：3.比较取出的字符，若相等，继续分别从队列和栈中取首个字符；否则跳出循环，并设置标志 flag=0;都取完，则结束，设置标志 flag=1;5.flag=1,表示字符从前往后和从后往前的序列完全匹配，该字符串属于回文6.flag=0,表示字符从前往后和从后往前的序列不完全匹配，该字符串不属于回文方法二：使用栈。将字符串的前一半入栈，再依次出栈，与后一半进行比较，若有不等则不是回文；若依次相等，则是回文。注意：本题要求简答算法思路，并不要求写出具体算法。4.试写出循环队列判空和判满的条件（队列最大容量为 M）...