数据结构习题PPT概要.ppt

数据结构习题 回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。 设计算法判断一个算术表达式的圆括号是否正确配对。 (提示： 对表达式进行扫描，凡遇到(就进栈，遇)就退掉栈顶的(，表达式被扫描完毕，栈应为空 一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。 试为此双向栈设计初始化InitStack ( S ) 、入栈Push( S , i , x) 和出栈Pop( S , i )等算法， 其中i为0 或1， 用以表示栈号。 利用两个堆栈 S1和S2模拟一个队列，写出入队和出队的算法（可用栈的基本操作）。 已知Q是一个非空队列，S是一个空栈。 仅用队列和栈的基本操作和少量变量来编写一个算法，将队列Q中的所有元素逆置。 假设稀疏矩阵A和B均以三元组顺序表作为存储结构，试写出矩阵相加的算法，另设三元组C存放结果矩阵。 试设计一个算法，将数组A中的元素A[0]至A[n-1]循环右移k位，并要求只用一个元素大小的附加存储，元素移动或交换次数为O（n）。 若将稀疏矩阵A的非 零元素以行序列为主序的顺序存于一维数组V中，并用二维数组B表示A中的相应元素是否为零元素（以0和1分别表示零元素和非零元素），例如， 可用V=(15，22，-6，9)和 表示。 试写一算法，实现在上述表示法中实现矩阵相加的运算。并分析你的算法的时间复杂度。 谢谢！