线性表栈队列

1、一、选择题1. 线性表的顺序存储结构是一种 的存储结构，而链式存储结构是一种_的存储结构。A随机存取 B索引存取 C顺序存取 D散列存取2. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址_。A. 必须是连续的 B. 部分地址必须是连续的C. 一定是不连续的 D. 连续或不连续都可以3. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行_。A. s->next=p->next; p->next=s; B. p->next=s->next; s->next=p;C. q->next=s; s->nex

2、t=p; D. p->next=s; s->next=q;4. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行_。A. s->next=p; p->next=s; B. s->next=p->next; p->next=s;C. s->next=p->next; p=s; D. p->next=s; s->next=p;5. 在一个单链表中，若删除p所指结点的后续结点，则执行_。A. p->next= p->next->next； B. p= p->next; p->nex

3、t= p->next->next；C. p->next= p->next; D. p= p->next->next；6. 链表不具备的特点是 _ 。A 可随机访问任何一个元素B 插入、删除操作不需要移动元素C 无需事先估计存储空间大小D 所需存储空间与线性表长度成正比7. 一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是_ 。A 4，3，2，1 B 1，2，3，4 C 1，4，3，2 D 3，2，4，18. 栈与一般线性表区别主要在方面 。A 元素个数 B 元素类型 C 逻辑结构 D 插入、删除元素的位置9. 在一个链队中，假设F和R分别是队

4、首和队尾指针，则删除一个结点的运算是 。  A R=F->next;  B R=R->next;  C F=F->next;  D F=R->next;10.数据三种最主要的逻辑结构是线性结构和（ ）。 A. 线性表、树 B. 树形结构、图状结构 C. 线性表、图 D. 树形结构、堆二、填空题1. 数据结构的存储结构包括：顺序存储表示、链式存储表示、索引存储表示和散列存储表示等四大类。2. 在线性结构中，第一个结点没有 前驱结点，其余每个结点有1个前驱结点；最后一个结点没有后继结点，其余每个结点有1个后继结点。3. 实现字符串逆序

5、（既输入如“ABC”，输出为“CBA”）选用栈数据结构来解决较好4. 银行柜面服务遵循“先来先服务”的原则，抽号服务终端机采用队列 数据结构来模拟这种行为5. 线性表第一个元素的存储地址是100,每个元素的长度是2,则第5个元素的地址是:1086. 引起循环队列（队首位置）发生变化的操作是出队操作7. 链式队列与顺序队列相比，一个明显的优点是通常不会出现队满8. 在一个长度为n的顺序表中删除第i个元素，要移动n-i个元素。如果要在第i个元素前插入一个元素，要后移n-i+1个元素。9. 栈操作数据的原则是 后进先出 ，队列操作数据的原则是 先进先出 。10. 在栈中，可进行插入和删除操作的一端称

6、 栈顶 。11. 栈和队列都是_线性_结构；对于栈只能在_栈顶_插入和删除元素；对于队列只能在_队尾_插入元素和_队头_删除元素。12. 计算机在运行递归程序时，要用到 栈 。13. 设将整数1，2，3，4进栈，若入、出栈次序为Push, Pop,Push,Push, Pop, Pop,Push, Pop,则出栈的数字序列为1324 ；若想得到出栈序列1432则具体操作为：Push，Pop，Push，Push，Push，Pop，Pop，Pop14. 在采用少用一个存储空间的具有n个单元的循环队列中，队满时共有n-1个元素。对于下图所示的循环队列，队满的条件是front=(rear+1)%MAX

7、SIZE；队空的条件是rear=front 三、设计题 1. 已知str是一个非空字符串，编写算法通过在临时栈S和队列Q中缓存数据，判处字符串str是否为回文，算法采用文字描述。将串str分别入队Q中和入栈S中将Q的队头元素出队至变量tq中，将S的栈顶元素出栈至变量ts中若tq=ts，重复步骤；若tq!=ts，则退出循环，return 0表示str不是回文return 1表示str是回文2. 设计函数Node * Find(Node *Head, int item)，Head为带头结点单链表的头指针，在传入的链表中查找值为item的结点并返回其地址，如不存在这样的结点则返回空值NULL。 其中结点的类型声明如下：struct Node int data; Node *next; ;Node * Find(Node *Head