顺序存储结构的线性表——习题.ppt

第二章顺序存储结构的线性表 习题课 选择题 1 一个顺序表的首元存储地址是100 每个元素的长度为2 则第5个元素的地址是 A110B108C112D1202 一个栈的入栈序列为a b c d e 则栈的不可能的输出序列是 AedcbaBdecbaCdceabDabcde 3 若已知一个栈的入栈序列是1 2 n 其输出序列为p1 p2 p3 pn 若p1 n 则pi AiBn iCn i 1D不能确定4 一个队列的入队序列为1 2 3 4 则其输出序列可能是 A4 3 2 1B1 2 3 4C1 4 2 3D3 2 4 15 判定一个容量为m的队列为空的条件是 Arear front mBfront rear mCrear front 1 mDfront rear 1 mErear frontFrear front 1 6 栈和队列的共同点是 A 都是先进后出B 都是先进先出C 只允许在端点处插入和删除元素D 没有共同点 填空题 1 向量 栈和队列都是 结构 可以在向量的 位置插入和删除元素 对于栈只能在 插入和删除元素 对于队列只能在 插入元素和 删除元素 2 向一个长度为n的向量的第i 0 i n 2 个元素之前插入一个元素时 需向后移动 个元素 3 向一个长度为n的向量中删除第i 0 i n 2 个元素时 需向前移动 个元素 4 一个栈的输入序列是12345 如果栈的输出序列43512是 5 一个栈的输入序列是12345 如果栈的输出序列12345是 算法编写题 1 已知一个顺序表按元素值的升序排列 编写一个算法 插入一个元素后保持该顺序表是有序的 PROCEDUREInsert ETa intn intx If x a n a n 1 x Else inti 1 while x a i doi i 1 forj ntoidoa j 1 a j a i x n n 1 END 第二题 试写出在顺序存储结构下逆转线性表的算法 要求使用最少的附加空间 PROCEDUREnizhuan ETa intn Fork 1ton 2do t a k a k a n k 1 a n k 1 t END 第三题 有两个顺序表A和B 分别有m个和n个元素 其元素均以从小到大的升序排列 编写一个算法将它们合并成一个顺序表C 要求C的元素也是以从小到大的升序排列 比如A 3 5 8 11 B 2 6 8 9 11 15 20 则C 2 3 5 6 8 8 9 11 11 15 20 PROCEDUREhebing a b m n ETa ETb intm intni 1 j 1 k 1 While i mandj n doIf a i b j c k a i i i 1 k k 1 Else c k b j j j 1 k k 1 If j n fort i 1 tomdo c k a t k k 1 If i m fort j 1 tondo c k b t k k 1 第四题 设有n个人围成一圈 每个人的编号依次为1 2 3 n 现从编号为k的人开始报数 数到m的人便出列 接着从出列的下一个人开始重新报数 数到m的人又出列 以此类推 直到所有的人都出列为止 请写出算法求出n个人的出列顺序 分析 设以自然数1 2 3 n为元素构成一个循环队列 并用一个数组a存放该队列中每个元素的直接后继 其中a i 表示i的后继 显然该数组初始化时应该这样 a i i 1 i 1 2 n 1a n 1 设x为当前所求的出列者 序号 它的前驱为t 则有a t x 而且x的后继为a x 则当前的队列为 t x a x 当x出列后 队列变为 t a x 显然 此时t的后继已变为a x 由此可见 当x出列时 只需作以下两个操作 1 将所求到的x存入另一个数组b 2 a x 赋值给a t 即a t a x 接下来的问题是如何确定每次出列者 设s首先指向每次第一个报数者 t指向s时 s便指向它的后继 t再指向s时 s又指向它的后继 如此循环m次后 t便是当前出列者x s便是下次开始报数