循环队列的实现与运算

1.算法一般都可以用哪几种控制结构组合而成？答案：顺序、选择、循环。

2. 在下列选项中，哪个不是一个算法一般应该具有的基本特征？说明：算法的四个基本特征是：可行性、确定性、有穷性和拥有足够的情报。

答案：无穷性。

3. 在计算机中，算法是指什么？答案：解题方案的准确而完整的描述。

4. 算法的时间复杂度是指？答案：算法执行过程中所需要的基本运算次数。

5. 算法的空间复杂度是指？答案：执行过程中所需要的存储空间。

6. 算法分析的目的是？答案：分析算法的效率以求改进。

7. 下列叙述正确的是（C）A．算法的执行效率与数据的存储结构无关B．算法的空间复杂度是指算法程序中指令（或语句）的条数C．算法的有穷性是指算法必须能在执行有限个步骤之后终止D．算法的时间复杂度是指执行算法程序所需要的时间8. 数据结构作为计算机的一门学科，主要研究什么？答案：主要研究数据的逻辑结构、对各种数据结构进行的运算，以及数据的存储结构。

9. 数据结构中与所使用的计算机无关的是数据的（C）A．存储结构B．物理结构C．逻辑结构D．物理和存储结构10. 下列叙述中，错误的是（B）A．数据的存储结构与数据处理的效率密切相关B．数据的存储结构与数据处理的效率无关C．数据的存储结构在计算机中所占的空间不一定是连续的D．一种数据的逻辑结构可以有多种存储结构11. 数据的存储结构是指什么？答案：数据的逻辑结构在计算机中的表示。

12. 数据的逻辑结构是指？答案：反映数据元素之间逻辑关系的数据结构。

13. 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为？答案：线性结构和非线性结构。

14. 下列数据结构具有记忆功能的是（C）A．队列B．循环队列C．栈D．顺序表15. 下列数据结构中，按先进后出原则组织数据的是（B）A．线性链表B．栈C．循环链表D．顺序表16. 递归算法一般需要利用什么实现？答案：队列17. 下列关于栈的叙述中正确的是（D）A．在栈中只能插入数据B．在栈中只能删除数据C．栈是先进先出的线性表D．栈是先进后出的线性表18. 由两个栈共享一个存储空间的好处是？答案：节省存储空间，降低上溢发生的机率。

解忧书店 JieYouBookshop第二章单元测试1、(1分)以下哪种结构是逻辑结构，而与存储和运算无关：Which of the following structure is a logical structure regardless of the storage or algorithm:（There is only one correct answer）A、队列(queue)B、双链表(doubly linked list)C、数组(array)D、顺序表(Sequential list)答案： A2、(1分)计算运行下列程序段后m的值：Calculate the value of m after running the following program segmentn = 9; m = 0;for (i=1;i<=n;i++)for (j = 2*i; j<=n; j++)m=m+1;求m的值答案： 203、(1分)下列说法正确的是：Which options may be correct?（there are more than one correct answers）A、如果函数f(n)是O(g(n))，g(n)是O(h(n))，那么f(n)是O(h(n))【 if f(n) is O(g(n))，g(n) is O(h(n))，then f(n) is O(h(n))】B、如果函数f(n)是O(g(n))，g(n)是O(h(n))，那么f(n)+g(n)是O(h(n))【if f(n) is O(g(n))，g(n) is O(h(n))，so f(n)+g(n) is O(h(n))】C、如果a>b>1,logan是O(logbn)，但logbn不一定是O(logan)【if a>b>1,logan is O(logbn)，logbn may not be O(logan)】D、函数f(n)是O(g(n))，当常数a足够大时，一定有函数g(n)是O(af(n))【if f(n)是O(g(n))，When constant a is big enough ，there must be g(n) is O(af(n))】答案： A,B4、(1分)由大到小写出以下时间复杂度的序列：答案直接写标号，如：(1)(2)(3)(4)(5) （提示：系统基于字符匹配来判定答案，所以您的答案中不要出现空格）Write the following time complexity in descending sequence:Write down the answer labels such as (1)(2)(3)(4)(5). （Hint：This problem is judged by string matching, Please make sure your answer don't contain any blanks. ）RUX4%GXZNDD{IAQWTCSEEJG.png答案： (5)(1)(2)(4)(3)5、(1分)已知一个数组a的长度为n，求问下面这段代码的时间复杂度:An array of a, its length is known as n. Please answer the time complexity of the following code.（There are more than one answers.）for (i=0,length=1;i<n-1;i++){for (j = i+1;j<n && a[j-1]<=a[j];j++)if(length<j-i+1)length=j-i+1;}Screen Shot 2017-09-05 at 23.31.19.pngA、如图，A选项B、如图，B选项C、如图，C选项D、如图，D选项答案： A,B第三章单元测试1、(1分)下面关于线性表的叙述中，正确的是哪些？Which of the followings about linear list are correct?（There are more than one answers.）Select the answer that matchesA、线性表采用顺序存储，必须占用一片连续的存储单元。

DS博客作业02--栈和队列0.PTA得分截图1.本周学习总结（0-4分）1.1 总结栈和队列内容⼀.栈栈的定义栈是⼀种只能在⼀端进⾏插⼊或删除操作的线性表，俗称：后进先出。

表中允许进⾏插⼊、删除操作的⼀端称为栈顶。

栈的进栈出栈规则：1.栈顶出栈->栈底最后出栈；2.时进时出->元素未完全进栈时，即可出栈。

栈的分类：1.顺序栈利⽤⼀组地址连续的存储单元依次存放⾃栈底到栈顶的数据元素，同时附设指针 top 指⽰栈顶元素在顺序栈中的位置，附设指针 base 指⽰栈底的位置。

同样，应该采⽤可以动态增长存储容量的结构。

如果栈已经空了，再继续出栈操作，则发⽣元素下溢，如果栈满了，再继续⼊栈操作，则发⽣元素上溢。

栈底指针 base 初始为空，说明栈不存在，栈顶指针 top 初始指向 base，则说明栈空，元素⼊栈，则 top++，元素出栈，则 top--，故，栈顶指针指⽰的位置其实是栈顶元素的下⼀位（不是栈顶元素的位置）。

2.链栈其实就是链表的特殊情形，⼀个链表，带头结点，栈顶在表头，插⼊和删除（出栈和⼊栈）都在表头进⾏，也就是头插法建表和头删除元素的算法。

显然，链栈插⼊删除的效率较⾼，且能共享存储空间。

栈的基本运算InitStack(&s)：初始化栈。

构造⼀个空栈s。

DestroyStack(&s)：销毁栈。

释放栈s占⽤的存储空间。

StackEmpty(s)：判断栈是否为空:若栈s为空，则返回真；否则返回假。

Push(&S，e)：进栈。

将元素e插⼊到栈s中作为栈顶元素。

Pop(&s，&e)：出栈。

从栈s中退出栈顶元素，并将其值赋给e。

GetTop(s，&e)：取栈顶元素。

返回当前的栈顶元素，并将其值赋给e。

顺序栈的功能操作代码实现1.图像表⽰2.结构体定义typedef struct{ ElemType data[MaxSize]；int top； //栈顶指针} Stack；typedef Stack *SqStack;3.基本运算<1>初始化栈initStack(&s)void InitStack(SqStack &s){ s=new Stack;s->top=-1;}<2>销毁栈ClearStack(&s)void DestroyStack(SqStack &s){ delete s;}<3>判断栈是否为空StackEmpty(s) bool StackEmpty(SqStack s){ return(s->top==-1);}<4>进栈Push(&s,e)bool Push(SqStack &s,ElemType e){ if (s->top==MaxSize-1)return false;s->top++; //栈顶指针增1s->data[s->top]=e;return true;}<5>出栈Pop(&s,&e)bool Pop(SqStack &s,ElemType &e){if (s->top==-1) //栈为空的情况，栈下溢出 return false;e=s->data[s->top];//取栈顶指针元素s->top--; //栈顶指针减1return true;}<6>取栈顶元素GetTop(s)bool GetTop(SqStack *s,ElemType &e) { if (s->top==-1) //栈为空的情况return false;e=s->data[s->top];return true;}4.顺序栈的四要素栈空条件：top=-1栈满条件：top=MaxSize-1进栈e操作：top++; st->data[top]=e 退栈操作：e=st->data[top]; top--;链栈的功能操作代码实现1.图像表⽰2.结构体定义typedef int ElemType;typedef struct linknode{ ElemType data; //数据域struct linknode *next; //指针域} LiNode,*LiStack3.基本运算<1>初始化栈initStack(&s)void InitStack(LiStack &s){ s=new LiNode;s->next=NULL;}<2>销毁栈ClearStack(&s)void DestroyStack(LiStack &s){　LiStack p;while (s!=NULL){ p=s;s=s->next;free(p);}}<3>判断栈是否为空StackEmpty(s)bool StackEmpty(LiStack s){return(s->next==NULL);}<4>进栈Push(&s,e)void Push(LiStack &s,ElemType e){ LiStack p;p=new LiNode;p->data=e; //新建元素e对应的节点*pp->next=s->next; //插⼊*p节点作为开始节点s->next=p;}<5>出栈Pop(&s,&e)bool Pop(LiStack &s,ElemType &e){ LiStack p;if (s->next==NULL) //栈空的情况return false;p=s->next; //p指向开始节点e=p->data;s->next=p->next; //删除*p节点free(p); //释放*p节点return true;}<6>取栈顶元素GetTop(s,e)bool GetTop(LiStack s,ElemType &e){ if (s->next==NULL) //栈空的情况return false;e=s->next->data;return true;}4.链栈的四要素栈空条件：s->next=NULL栈满条件：不考虑进栈e操作：结点插⼊到头结点后，链表头插法退栈操作：取出头结点之后结点的元素并删除之对于栈的C++模板类：stack#include<stack>1.stack<int> s:初始化栈，参数表⽰元素类型2.s.push(t):⼊栈元素t3.s.top()：返回栈顶元素4.s.pop()：出栈操作只是删除栈顶元素，并不返回该元素。

实现循环队列的入队出队等基本操作循环队列是一种特殊的队列数据结构，通过循环利用数组空间来实现入队和出队操作。

它的特点是队头和队尾可以在数组上循环移动，从而充分利用数组空间，提高队列的效率。

下面将详细介绍循环队列的实现。

1.定义循环队列的数据结构循环队列的数据结构由以下几个成员组成：-一个固定大小的数组，用于存储队列元素。

- 一个队头指针front，指向队列的第一个元素。

- 一个队尾指针rear，指向队列的最后一个元素的下一个位置。

2.初始化循环队列首先，我们需要在内存中分配一个固定大小的数组，并初始化队头和队尾指针为0。

```pythondef __init__(self, k: int):self.queue = [0] * kself.front = self.rear = 0```3.入队操作入队操作会在队尾插入一个新元素，并将队尾指针后移一位。

如果队列已满，则入队操作会失败。

```pythondef enqueue(self, value: int) -> bool:if self.isFull(:return Falseself.queue[self.rear] = valueself.rear = (self.rear + 1) % len(self.queue)return True```4.出队操作出队操作会删除队头元素，并将队头指针后移一位。

如果队列为空，则出队操作会失败。

```pythondef dequeue(self) -> bool:if self.isEmpty(:return Falseself.front = (self.front + 1) % len(self.queue)return True```5.判空操作判空操作会检查队头和队尾指针是否相等，如果相等则说明队列为空。

```pythondef isEmpty(self) -> bool:return self.front == self.rear```6.判满操作判满操作会检查队尾指针的下一位是否等于队头指针，如果相等则说明队列已满。

循环队列实现杨辉三⾓形的打印知识温习循环队列：即将顺序队列的数组看成是⼀个环状的空间，规定最后⼀个单元的后继为第⼀个单元。

运⽤循环队列可以有效的解决链队列的“假溢出”现象。

假溢出其实是指在链队列中，当rear==MAXSIZE时就认为队满。

然⽽由于元素的出队，使得数组前⾯出现⼀些空单元，⽽元素⼜只能在队尾⼊队，如果此时已经到数组的尾部，就认为队列已满，但其实还存在上述那些空单元未使⽤，队列并未真正满。

这种现象即为“假溢出”现象。

真正的队满条件应该是rear-front==MAXSIZE。

在循环队列中，我们通过数学中的求模运算来改变头指针和尾指针的位置。

进队操作时，队尾指针的变化是：rear=（rear+1）mod MAXSIZE；⽽出队操作时，队头指针的变化是：front=（front+1）mod MAXSIE。

杨辉三⾓形11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 1从上图中可以看出，杨辉三⾓形的特点：每⾏的第⼀个元素和最后⼀个元素都为1，其他位置上的元素总是等于上⼀⾏与之相邻的两个元素之和。

故第i⾏的元素要由第i-1⾏的元素来⽣成。

可以利⽤循环队列实现杨辉三⾓形的打印过程：在循环队列中依次存放第i-1⾏上的元素，然后逐个出队并打印，同时⽣成第i⾏元素并⼊队。

下⾯⽤第6⾏元素⽣成第7⾏元素为例⼦来说明打印过程：①第7⾏的第⼀个元素1⼊队。

element[Q->rear] = 1;Q->rear = (Q->rear + 1)% MAXSIZE;②循环做以下操作，⽣成第7⾏的中间5个元素并⼊队。

element[Q->rear] = element[Q->front] + element[(Q->front+1)%MAXSIZE];Q->rear = (Q->rear + 1)%MAXSIZE;Q->front = (Q->front + 1)%MAXSIZE;③第6⾏的最后⼀个元素1⼊队。

实验二栈与队列操作实验题目实验二栈与队列操作实验目的：(1)理解栈与队列的结构特征和运算特征，以便在实际问题背景下灵活运用。

(2)了解复杂问题的递归算法设计。

本次实验中，下列实验项目选做一。

1、顺序栈的基本操作[问题描述]设计算法，实现顺序栈的各种基本操作[基本要求]（1）初始化栈s。

（2）从键盘输入10个字符以$结束，建立顺序栈。

（3）从键盘输入1个元素，执行入栈操作。

（4）将栈顶元素出栈。

（5）判断栈是否为空。

（6）输出从栈顶到栈底元素。

要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。

2、链栈的基本操作[问题描述]设计算法，实现链栈的各种基本操作[基本要求]（1）初始化栈s。

（2）从键盘输入10个字符以$结束，建立带头结点的链栈。

（3）从键盘输入1个元素，执行入栈操作。

（4）完成出栈操作。

（5）判断栈是否为空。

（6）输出从栈顶到栈底元素。

（7）输出链栈的长度。

要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。

3、循环队列的基本操作[问题描述]设计算法，实现循环顺序队列的建立、入队、出队等操作。

[基本要求]（1）从键盘输入10个字符以$结束，建立循环队列，并显示结果。

（2）从键盘输入1个元素，执行入队操作，并显示结果。

（3）将队头元素出队，并显示结果。

（4）要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。

4、只用尾指针表示的循环链表队列的综合操作[问题描述]假设以带头结点的的循环链表表示队列，并且只设一个指针指向队尾元素的结点（注意不设头指针），试编写队列初始化、入队、出队函数。

[基本要求及提示]（1）首先定义链表结点类型。

（2）编写带头结点的循环链表的初始化函数，只用尾指针表示。

（3）编写入队函数、出队函数。

（4）在主函数中编写菜单（1.初始化；2.入队；3.出队；4.退出），调用上述功能函数。