- 1、本文档共10页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
3.1 链栈中为何不设置头结点? 3.2 循环队列的优点是什么? 如何判别它的空和满? 3.3 设长度为n的链队用单循环链表表示,若设头指针,则入队出队操作的时间为何? 若只设尾指针呢? 3.4 回文是指正读反读均相同的字符序列,如“abba”和“abdba”均是回文,但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示:将一半字符入栈) 3.5 设计算法判断一个算术表达式的圆括号是否正确配对。 (提示: 对表达式进行扫描,凡遇到(就进栈,遇)就退掉栈顶的(,表达式被扫描完毕,栈应为空。 3.6 一个双向栈S是在同一向量空间内实现的两个栈,它们的栈底分别设在向量空间的两端。 试为此双向栈设计初始化InitStack ( S ) 、入栈Push( S , i , x) 和出栈Pop( S , i )等算法, 其中i为0 或1, 用以表示栈号。 3.7 假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素站点(注意不设头指针) ,试编写相应的置空队、判队空 、入队和出队等算法。 * * 链栈中为何不设置头结点?答:链栈不需要在头部附加头结点,因为栈都是在头部进行操作的,如果加了头结点,等于要对头结点之后的结点进行操作,反而使算法更复杂,所以只要有链表的头指针就可以了。 循环队列的优点是什么? 如何判别它的空和满? 循环队列的优点是:它可以克服顺序队列的假上溢现象,能够使存储队列的向量空间得到充分的利用。判别循环队列的空或满不能以头尾指针是否相等来确定,一般是通过以下几种方法:一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间。每次入队前测试入队后头尾指针是否会重合,如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数,不仅可判别空或满,还可以得到队列中元素的个数。 设长度为n的链队用单循环链表表示,若设头指针,则入队出队操作的时间为何? 若只设尾指针呢? 答:当只设头指针时,出队的时间为1,而入队的时间需要n,因为每次入队均需从头指针开始查找,找到最后一个元素时方可进行入队操作。若只设尾指针,则出入队时间均为1。因为是循环链表,尾指针所指的下一个元素就是头指针所指元素,所以出队时不需要遍历整个队列。 回文是指正读反读均相同的字符序列,如abba和abdba均是回文,但good不是回文。试写一个算法判定给定的字符向量是否为回文。(提示:将一半字符入栈) 一个双向栈S是在同一向量空间内实现的两个栈,它们的栈底分别设在向量空间的两端。 试为此双向栈设计初始化InitStack ( S ) 、入栈Push( S , i , x) 和出栈Pop( S , i )等算法, 其中i为0 或1, 用以表示栈号。 假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素站点(注意不设头指针) ,试编写相应的置空队、判队空 、入队和出队等算法。 *
文档评论(0)