工学
填空题用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（）和（）。
题目
相似问题和答案
第1题：
第2题：
此题为判断题(对，错)。
第3题：
● 若对一个链表最常用的操作是在末尾插入结点和删除尾结点，则采用仅设尾指针的单向循环链表（不含头结点）时， （65） 。
（65）
A. 插入和删除操作的时间复杂度都为O(1)
B. 插入和删除操作的时间复杂度都为O(n)
C. 插入操作的时间复杂度为O(1)，删除操作的时间复杂度为O(n)
D. 插入操作的时间复杂度为O(n)，删除操作的时间复杂度为O(1)
第4题：
对于长度为m(m>1)的指定序列，通过初始为空的一个栈、一个队列后，错误的叙述是( )。
A．若入栈和入队的序列相同，则出栈序列和m队序列可能相同
B．若入栈和入队的序列相同，则出栈序列和出队序列可以互为逆序
C．入队序列与出队序列关系为1：1，而入栈序列与出栈序列关系是1：n(n≥1)
D．入栈序列与出栈序列关系为1：1，而入队序列与出队序列关系是1：n(n≥1)
解析：栈和队列都是在一个特定范围的存储单元中存储的数据，这些数据都可以重新被取出使用。不同的是栈是“先进先出”，而队列是先进后m。
第5题：
对于长度为m(m>1)的指定序列，通过初始为空的一个栈、一个队列后，错误的叙述是()
A.若入栈和入队的序列相同，则出栈序列和出队序列可能相同
B.若入栈和入队的序列相同，则出栈序列和出队序列可以互为逆序
C.入队序列与出队序列关系为1:1，而入栈序列和出栈序列关系是1：n(n>=1)
D.入栈序列和出栈序列关系为1:1，而入队序列与出队序列关系是1：n(n>=1)
第6题：
第7题：
●设长度为n的链队列用单循环链表表示，若只设头指针，则入队、出队操作的时间是 (41) ，若只设尾指针呢，需要的时间为 (42) 。
(41) A．O(n2,O (1)
B．O(n),O (1)
C．O(n2-1),O(n)
D．O(n-1),O(n-1)
(42) A．O (1) ，O (1)
B．O(n),O (1)
C．O(n2),O (1)
D．O(n),O(n)
【解析】只设头指针时，入队操作的时间为O(n)，出队操作的时间为O(1)；
只设尾指针时，入队操作的时间为O(1)，出队操作的时间也为O(1)。
第8题：
第9题：
设循环队列Q的定义中有rear和len两个域变量，其中rear表示队尾元素的指针，len表示队列的长度，如下图所示(队列长度为3，队头元素为e)。设队列的存储空间容量为M，则队头元素的指针为(57)。
A．(Q．rear+Q．len-1)
B．(Q．rear+Q．1en-1+M)％M
C．(Q．rear-Q．1en+1)
D．(Q．rear-Q．1en+1+M)％M
解析：按照正常线性存储的队列，队头元素的指针为(Q．rear-Q．len+1)，而在循环队列里面，Q．rear-Q．1en+1可能会由于循环存储而变为负值，所以需要处理为(Q．rear-Q．1en+1+M)％M。
第10题：
下面关于栈和队列的叙述，错误的是( )。
A．栈和队列都是操作受限的线性表
B．队列采用单循环链表存储时，只需设置队尾指针就可使入队和出队操作的时间复杂度都为O(1)
C．若队列的数据规模n可以确定，则采用顺序存储结构比链式存储结构效率更高
D．利用两个栈可以模拟一个队列的操作，反之亦可
解析：栈和队列都是操作受限的线性表：栈仅在表尾插入和删除元素，队列仅在表头删除元素、在表尾插人元素。入队时初始队列为空，出队后队列变为空要进行特殊处理。入队操作和出队操作均与队列长度无关，因此其时间复杂度都为O(1)。队列是先入先出的线性表，栈是后进先出的线性表。一个线性序列经过队列结构后只能得到与原序列相同的元素序列，而经过一个栈结构后则可以得到多种元素序列。用两个栈可以模拟一个队列的人队和出队操作。