数据结构习题一.ppt

第三部分 栈、队列和数组 考点三 栈的链式存储结构 栈的链式存储是栈的一种存储结构，同学们注意区分顺序栈和链栈的存储特点，并会链栈的判空、判满、出栈和入栈等基本操作。本部分命制选择题的可能性很大。 第三部分 栈、队列和数组 考点三 栈的链式存储结构 向一个栈顶指针为h的带头结点的链栈中插入指针s所指 的结点时，应执行（ ）操作。 A. h-next=s; B. s-next=h; C. s-next=h; h =s; D. s-next=h-next; h-next=s; A 因为本题的链栈带有头结点，并令h指向头结点，该头结点的下一个结点，才是栈顶。故而插入s所指向的结点，首先要把s-next=h-next，再令h-next=s即可完成插入新元素作为栈顶并调整h头结点的下一个结点为新栈顶操作。 再假设，若本题的链栈，是不带有头结点的链栈，栈顶指针仍为h，则向栈中插入指针s所指向的结点时，只需将s-next=h，再令h=s即可完成插入结点s并令h指向新的栈顶操作。 第三部分 栈、队列和数组 考点四 队列的顺序存储结构 本考点考查队列的顺序存储方式，请同学们注意队列在该结构下的判空、判满、入队列和出队列的基本操作，并能把这些基础知识用于解题。 1. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为 （ ） A. 1和5 B. 2和4 C. 4和2 D. 5和1 第三部分 栈、队列和数组 考点四 队列的顺序存储结构 B 熟悉课本中对于循环队列的定义和操作 2. 设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针。其中，front指针指向队头元素，rear指针指向队尾元素的下一个位置。则执行出队操作的语句为 （ ） A. front=(front+1)%(m+1) B. front=(front+1)%m C. rear=(rear+1)%m D. front=front+1 A 第三部分 栈、队列和数组 考点四 队列的顺序存储结构 数组为Data[0~m]，故而数组的大小为m+1，元素出队列或者入队列时应该进行mod (m+1)运算而不是mod m运算。出队列时，front=(front+1)?????? (??+1)。 3. 若顺序存储的循环队列的QueueMaxSize=n，则该队列最多可存储（ ）个元素。 A. N B. n-1 C. n+1 D. 不确定 第三部分 栈、队列和数组 考点四 队列的顺序存储结构 循环队列Q中，若不留一个位置，怎么判断Q.front=Q.rear是队空还是队满呢？显然无法区别。因为队空的时候，显然满足Q.front=Q.rear；而队满的时候，若不留下一个空位置，rear指向队尾的下一个位置，该位置刚好是front所指向的位置，也满足Q.front=Q.rear。 我们若给数组留一个空位置来区分队满和队空。那么，可用Q.front=Q.rear表示当前队列为空。当有元素需要入队时，先把元素放入rear指针值所指向的数组位置（数组下标），使得该元素成为队列的新队尾元素，接下来对rear执行Q.rear=(Q.rear+1) % ??????????????操作，指向新的队尾元素的下一个位置，(Q.rear+1)% ??????????????==??.??????????时表示队满。 B 第三部分 栈、队列和数组 考点五 队列的链式存储结构 和栈的链式存储结构一样，队列也可以用链式存储结构来存储表示，也请同学们多注意该存储结构下，队列的基本操作。 第三部分 栈、队列和数组 考点五 队列的链式存储结构 (原书第1题)用链接方式存储的队列，在进行插入运算 时 （ ） A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D. 头、尾指针可能都要修改 D 队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个