数据结构与算法——第一次大作业【考点罗列//错题修正//题解】

一、选择题

——绪论——

1.【单选题】——数据结构的研究方向

2.【单选题】 ——数据结构的研究问题

3.【单选题】——数据结构的基本术语及概念

4.【单选题】 ——数据结构与算法

5.【单选题】 ——时间复杂度计算

——顺序表与链表——

6.【单选题】——顺序表的相关知识点

7.【单选题】 ——顺序表知识点考查：长度

8.【单选题】——顺序表：插入元素算法的步骤

9.【单选题】——顺序表操作

10.【单选题】——顺序表：插入与删除算法时间复杂度：

11.【单选题】——单链表的相关知识点

12.【单选题】——单链表：插入算法

13.【单选题】 ——单链表：删除算法

14.【单选题】 ——单链表：访问元素算法

15.【单选题】——单链表：两种查找算法的时间复杂度

——栈——

16.【单选题】——栈的相关知识点

17.【单选题】 ——栈的出栈结果考查

18.【单选题】 ——栈的应用

19.【单选题】 ——应用：后缀表达式

20.【单选题】——应用：中缀表达式与后缀表达式的转换

——队列——

21.【单选题】——队列相关知识点

22.【单选题】——队列：判断为空队列的条件

23.【单选题】——队列：循环队列的相关知识点

24.【单选题】——队列：循环队列的入队情况判断

25.【单选题】——队列：两种队列入队的时间复杂度

二、填空题

——绪论——

26.【填空题】——数据结构的概念

27.【填空题】顺序存储结构的概念

28.【填空题】——算法的概念

29.【填空题】——算法效率的评估方式

30.【填空题】——函数的时间复杂度求解

——顺序表与链表——

31.【填空题】——顺序表：元素的存储位置计算

32.【填空题】——顺序表：有效插入位置的判断条件

33.【填空题】——顺序表：插入操作涉及元素的移动次数

34.【填空题】——顺序表：删除算法

35.【填空题】 ——单链表知识点：头结点

36.【填空题】——单链表指定功能的对应操作

37.【填空题】 ——单链表：查找

38.【填空题】 ——顺序表：查找指定元素算法的时间复杂度

39.【填空题】——单链表：插入算法的时间复杂度

40.【填空题】 ——单链表：删除算法的时间复杂度

——栈——

41.【填空题】 ——栈的特征

42.【填空题】 ——栈：顺序栈入栈算法

43.【填空题】 ——栈：链式栈出栈算法

44.【填空题】——应用：中缀表达式与后缀表达式的转化

45.【填空题】 ——应用：中缀表达式与后缀表达式的转化

——队列——

46.【填空题】——队列的特征

48.【填空题】 ——队列：循环队列的存储元素计算

一、选择题

——绪论——

1.【单选题】——数据结构的研究方向

数据结构主要研究数据在（ B）中的组织方式，以提高数据处理的效率。

A.计算机硬盘

B.计算机内存

C.计算机网络

D.数据库

因为计算机内存是计算机系统中用于存储数据和程序的临时存储器，对于快速访问和处理数据是非常重要的。而数据结构的设计和选择可以影响数据在内存中的存储和访问方式，从而影响数据处理的效率。

对于其他选项：

计算机硬盘（A）用于长期存储数据
计算机网络（C）用于数据传输
数据库（D）是一个用于存储和管理大量数据的软件系统

对比起B来说，数据结构与这些方面的关系相对较小。

2.【单选题】 ——数据结构的研究问题

以下哪一项不属于数据结构主要研究的问题？（D ）

A.线性表

B.树

C.图

D.数学方程式

个人理解：

这里要联系到数据结构的逻辑结构，在数据结构中，从逻辑上是可以分为两个方面的：

一个是线性结构（线性表、栈和队列、字符串、数组、广义表）

另一个是非线性结构（树结构、图结构、集合结构）

所以排除ABC选项，至于数学方程式，可能在算法的设计中会用到。

3.【单选题】——数据结构的基本术语及概念

对数据进行处理的基本单位可称为（B ）。

A.数据

B.数据元素

C.数据对象

D.数据结构

选项A:数据是所有能够被输入道计算机中，并且能够被计算机处理的符号的集合，是计算机操作对象的总称。

选项B:数据元素是数据的“基本单位”，也是元素、记录。

选项C:数据对象是性质相同的数据元素的集合，是数据的一个子集

选项D:数据结构是带“结构”的数据元素集合，描述了数据元素相互之间存在一种或多种特定关系。

ps补充：数据项是数据不可分割的最小标识单位

4.【单选题】 ——数据结构与算法

以下关于数据结构与算法的说法中，哪一项是正确的？（B ）C

A.数据的逻辑结构与数据的存储结构一一对应。

B.抽象数据类型包括数据对象，以及数据对象上关系的集合。

C.算法执行的时间与计算机硬件有关。

D.解决同一问题的两种算法，应该优先选择时间复杂度较大的算法。

选项A：数据的逻辑结构和存储结构并不是一一对应的，同一个逻辑结构对应多种存储结构，同样的运算在不同的存储结构中实现过程是不同的。

选项B也是正确的，但是是不完全的正确：因为抽象数据类型（ADT）是由三个部分组成的，数据对象、数据对象上关系的集合以及对数据对象的基本操作的集合。

选项C：计算机硬件的性能和能力会直接影响算法的执行速度。例如，计算机的处理器速度、内存大小、存储器带宽等硬件因素都会影响算法的执行时间。较高性能的硬件可以更快地执行算法，而较低性能的硬件则可能导致算法执行变慢。

选项D：这涉及到算法的优劣，解决问题的算法当然是时间复杂度、空间复杂度都高效的情况下当然是最好的，时间复杂度大计算机处理算法的时间长，执行效率也就低了。

5.【单选题】 ——时间复杂度计算

已知算法的执行时间T(n)可表示为函数：

其中n为问题规模，则该算法的时间复杂表可表示为：（ D）。

A.O(1)

B.O(n)

C.O(n²)

D.O(n³)

——顺序表与链表——

6.【单选题】——顺序表的相关知识点

以下关于顺序表的说法中，哪一项是错误的？（A ）。C

A.顺序表只能包含一个表头元素。

B.当在顺序表中插入元素时，插入位置之后的元素需要向后移动。

C.访问顺序表尾部的元素所花的时间大于访问顺序表头部元素所花的时间。

D.顺序表的存储空间在初始化时需要设置固定大小。

选项A：线性结构的基本特点就是——有且仅有一个无前驱的表头元素，无后继的表尾元素，其余每个数据元素都有前驱后继

选项B：我们知道顺序存储结构它是指所有的数据元素依次存放在一片连续的存储空间中，既然是连续的，那么在对数据元素进行操作的时候，增加、减少数据元素个数都需要重新去调整相应的存储位置。

选项C：不一定，如果知道顺序表的长度，可以通过计算偏移量得到尾部元素的地址，访问尾部元素的时间与访问头部元素的时间相差不大。但如果没有长度信息，就需要遍历整个顺序表才能找到尾部元素，这时访问尾部元素的时间比访问头部元素的时间长。

选项D：顺序表的初始化，因为顺序表是使用连续的存储空间来存储数据元素的，这需要预先分配足够的存储空间以容纳所有的元素，以免造成存储空间不足的问题。

7.【单选题】 ——顺序表知识点考查：长度

顺序表的长度是指（C ）。

A.顺序表中一个元素占用的空间。

B.顺序表的全部存储空间。

C.顺序表中的元素个数。

D.顺序表所使用的数组的长度。

顺序表的长度是动态变化的。

随着元素的插入和删除操作，顺序表的长度会相应地增加或减少。

选项D：所用数组长度不一定等于顺序表长度

8.【单选题】——顺序表：插入元素算法的步骤

以下哪一项不属于顺序表插入元素算法的步骤？（B ）。C

A.检查顺序表是否已满。

B.检查元素的插入位置是否有效。

C.从插入位置开始一直到顺序表最后一个元素，依次逐个向后移动一个位置。

D.将新元素置于插入位置。

选项A：以防出现溢出问题

选项B：1≤pos≤length+1

选项C：在插入元素时，我们只需要将插入位置后的所有元素向后移动一位，并将新元素置于插入位置即可。没有必要逐个向后移动每一个元素，只需要一次性移动即可。

选项D：是的

【插入步骤】
1、判断所给顺序表是否已满，若满则产生上溢出错误。
2、检查插入位置是否合法，即“1≤pos≤length+1”条件是否满足。
3、将顺序表最后一个（第length个）元素到
第pos个元素之间的所有元素依次逐个向后移动一个位置，为新元素留出插入位置。
4、将新元素插入于留出的位置上。
5、顺序表长度增一。 
注意，这里的pos为逻辑位置，即从1开始计数。

bool ListInsert(SqList &L, int pos, ElemType item)
{ //pos为插入的（逻辑）位置, item为待插入的数据元素
  int i;
  if (L.length == MaxSize) {                  //判表满
    cout << "顺序表满，无法插入！" << endl;
    return false; }
  if (pos < 1 || pos > L.length + 1) {        //判位置
    cout << "插入位置无效！" << endl;
    return false; }
  for (i = L.length - 1; i >= pos - 1; i--) { 
    L.data[i + 1] = L.data[i]; }  //向后移动元素
  L.data[pos - 1] = item;         //插入	
  L.length++;                     //表长增一
  return true; 
}

9.【单选题】——顺序表操作

在顺序表中进行以下哪一项操作，可体现出顺序表的优点？（ B）。

A.初始化顺序表

B.访问顺序表中的元素

C.在顺序表中插入新元素

D.在顺序表中删除已有元素

数组的特性满足顺序表的特点，因而顺序表是可以像数组那样通过给出下标（没有给出，便根据“数组名”（起始地址），通过偏移量去算出地址）从而直接访问元素，时间复杂度为O(1)，而不需要像链表那样从头开始遍历。

10.【单选题】——顺序表：插入与删除算法时间复杂度：

在顺序表中进行插入和删除操作的时间复杂度分别为（D ）。

A.O(1), O(1)

B.O(1), O(n)

C.O(n), O(1)

D.O(n), O(n)

操作 时间复杂度
初始化 O(1)
求元素个数 O(1)
判表空 O(1)
插入 O(n)
删除 O(n)
获取指定位置上的数据元素 O(1)
查找指定元素位置 O(n)
遍历 O(n)

11.【单选题】——单链表的相关知识点

以下关于单链表的说法中，哪一项是不正确的？（ D）。

A.单链表是一种递归的数据结构。

B.单链表适用于经常执行插入或删除操作的情景。

C.使用单链表时，无需设置单链表的长度。

D.在单链表中执行插入操作的时间复杂度为O(1) 。

选项A：单链表通常被认为是一种递归数据结构是因为它的定义本身是递归的。单链表由节点组成，每个节点包括一个数据域和一个指向下一个节点的指针。在单链表的定义中，每个节点的指针指向了下一个节点，这样就形成了节点之间的递归关系。
typedef int ElemType; // ElemType数据元素的数据类型
typedef struct LNode  // LNode为结点类型名
{
  ElemType data;      // data代表数据元素
  struct LNode *next; // next为指向下一结点的指针
} LinkNode;           // 单链表结点类型
选项B：这是链式存储结构的优点，较比顺序存储结构，插入和删除数据元素操作时无需移动大量的数据元素，只需要去修改指针的指向即可。

选项C：因为线性表的链式存储结构特点是——用一组任意的、可连续可不连续的存储单元去存储数据元素，无需连续的存储空间，可以动态地去分配和释放内存空间。

选项D：是O（n）

12.【单选题】——单链表：插入算法

在单链表中执行插入元素的操作。单链表结点包含数据域data和指针域next，已知指针p指向插入位置的前一结点，指针t指向待插入结点，则插入操作的正确程序实现为（ D）。

A.t->next=p; p->next=t->next;

B.p->next=t->next; t->next=p;

C.p->next=t; t->next=p->next;

D.t->next=p->next; p->next=t;

因为指针p是指向插入结点的前一个位置，在元素还未插入时，指针p的指针域还有下一个元素。因为指针t是指向待插入结点的，既是将结点插入后，在指针p的后一个位置上，所有需要先把指针p的next域存放的下一个结点的地址给指针t，然后再让指针p的next域存放结点t的位置。

13.【单选题】 ——单链表：删除算法

在单链表中执行删除元素的操作。单链表结点包含数据域data和指针域next，已知指针p指向删除位置的前一结点，指针t用于指向待删除结点，则删除操作的正确程序实现为（ C）。

A.t=p->next; p->next=t->next; delete p;

B.p->next=t->next; t=p->next; delete p;

C.t=p->next; p->next=t->next; delete t;

D.p->next=t->next; t=p->next; delete t;

看题目，指针p是指向待删除结点的前一个结点的，也就是说指针p现在指向的这个结点，下一个接结点是“待删结点”，删去这个“t”结点，得让这个“t”结点的下一个结点的地址放在“p”结点的next上，所以得先让指针t指向这个“待删结点”，而待删结点的地址就存放在p->next上，因此下一步让指针“p->next=t->next”

14.【单选题】 ——单链表：访问元素算法

在单链表中执行访问元素的操作。单链表结点包含数据域data和指针域next，已知指针p指向当前访问的结点，则使p指向当前访问结点的下一个结点的正确程序实现为（ C）。

A.p--;

B.p++;

C.p=p->next;

D.p->next=p;

这题就无需多言了

15.【单选题】——单链表：两种查找算法的时间复杂度

在单链表中，根据位置查找元素值,以及根据元素值查找位置,两种算法的时间复杂度分别为 D

A.O(1), O(1)

B.O(1), O(n)

C.O(n), O(1)

D.O(n), O(n)

操作时间复杂度
初始化单链表 O(1)
判表空 O(1)
求单链表中当前元素的个数 O(n)
遍历单链表 O(n)
查找查找指定元素值，返回位置 O(n)
查找指定位置，返回元素值 O(n)
插入指定位置插入 O(n)
表头、表尾插入 O(1)
删除指定位置删除 O(n)
指定元素值删除 O(n)
撤销单链表 O(n)

	操作	时间复杂度
	初始化单链表	O(1)
	判表空	O(1)
	求单链表中当前元素的个数	O(n)
	遍历单链表	O(n)
查找	查找指定元素值，返回位置	O(n)
查找指定位置，返回元素值	O(n)
插入	指定位置插入	O(n)
表头、表尾插入	O(1)
删除	指定位置删除	O(n)
指定元素值删除	O(n)
	撤销单链表	O(n)

——栈——

16.【单选题】——栈的相关知识点

以下关于栈的说法，哪一项是不正确的？（D ）。

A.在栈的顶部进行插入元素的操作。

B.栈的实现可以采用顺序存储结构和链式存储结构。

C.栈的入栈和出栈算法，时间复杂度都为O(1) 。

D.自助点餐系统中的叫号功能可以使用栈来实现。

选项A：栈是限定只能在表的同一端进行插入和删除操作的线性表，允许插入和删除操作的一端称作栈顶。所以栈的顶部是可以进行元素的增删的。

选项B：是的，栈有顺序存储结构和链式存储结构

选项C：yes

选项D：这里就记住栈的特征，先进后出，所以栈肯定不能用来实现点餐系统，先排队的人应该是先拿到餐，是先进先出，应该用队列。

17.【单选题】 ——栈的出栈结果考查

在栈中执行一系列的入栈和出栈操作，如果元素的入栈顺序为1, 2, 3, 4, 5, 6，则可能的出栈顺序为（ C）。

A.4, 5, 6, 2, 3, 1

B.5, 4, 3, 6, 1, 2

C.3, 2, 1, 5, 4, 6

D.2, 1, 3, 6, 4, 5

就记住栈先进后出的特点，拿着入栈循序对着选项来看

选项A：456231，因为第一个出来的是4，所以就代表在此之前，1，2，3是放进了栈里的，所以到4的时候，放4出4，放5出5，放6出6，这里前三个都没问题。但是下一个就有问题了，因为2比3早放，3是压在2上的，3没出来2怎么出得来。

选项B：也是这样去看，第一个出5，就是1234被放去了，放5出5，这个选项到这里就没有进元素的，而是把4、3依次出了，再放6出6，接着下一个就有问题的，因为1是最先进的，所以1是被压在2下的，那么这样的话1不可能比2先出

选项C：进123，出321，然后放45，出5，出4，最后放6，出6

选项D：先进12，出2，出1，然后放3出3，接着下一个出的是6，那么就是说在出3之后，456都放进去了，6在栈顶，出，然后应该就到5，而不是4.

18.【单选题】 ——栈的应用

以下的应用问题中，哪一项与栈无关？（D ）。

A.表达式求值

B.表达式括号匹配

C.数制转换

D.班级花名册管理

ABC都是栈的应用

19.【单选题】 ——应用：后缀表达式

以下关于后缀表达式的说法，哪一项是不正确的？（ C）。

A.后缀表达式中的运算符置于该运算的操作数之后。

B.后缀表达式有利于计算机进行求值的操作。

C.后缀表达式中如有括号，则先计算括号内，再计算括号外。

D.后缀表达式可以转换为中缀表达式。

后缀表达式的特点是没有括号，也无需考虑优先级，运算符在操作数后，在式中出现的顺序恰为表达式的运算顺序，所以方便程序进行求值。

所以可以排除C了，后缀表达式没有括号。

20.【单选题】——应用：中缀表达式与后缀表达式的转换

在使用栈把中缀表达式转换为后缀表达式的过程中，栈中存放的是（ B）。

A.操作数

B.运算符

C.操作数和运算符

D.括号

——队列——

21.【单选题】——队列相关知识点

以下关于队列的说法中，哪一项是正确的？（ C）。

A.队列属于一种后进先出的数据结构。

B.在队列中进行删除操作的一端称为队尾。

C.打印机的任务调度与队列相关。

D.队列的入队操作的时间复杂度为O(n) 。

选项A：栈才是。

选项B：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。在称为队尾的一端进行插入操作、在称为队头的一段进行删除操作

选项C：是的，先按打印的先打印

选项D：循序栈、链栈的出栈入栈和循环队列、链队列的出队入队操作时间复杂度都是O(1)

22.【单选题】——队列：判断为空队列的条件

已知front和rear分别为链式队列的头指针和尾指针，则队列为空的条件可表示为（C ）。

A.front==NULL

B.rear==NULL

C.front==rear

D.rear!=NULL

23.【单选题】——队列：循环队列的相关知识点

以下关于循环队列的说法中，哪一项是正确的？（C ）。D

A.在循环队列中，下标为 x 的位置，其下一个相邻位置的下标为 x+1 。

B.循环队列的存储空间可无限循环，不会存在队满的情况。

C.在循环队列中，队尾位置的下标总是大于队头位置的下标。

D.循环队列的设计充分利用了存储空间。

选项A：这样会很容易“溢出”的。应该是这样：

数组第一个单元的下标为 0
与下标1的单元相邻

(0+1)％ Max＝1

数组最后一个单元的下标为Max－1
其下一相邻的单元的下标为0

(Max-1+1)％ Max＝0

任一位置 X (0≤X≤Max-1) X的下一相邻的单元的下标为 (X+1)％Max
选项B：这是错的，当(Q.rear + 1) % MaxSize == Q.front时，就队满了，而且必须预先确定一个固定的长度，所以顺序队列有存储元素个数的限制。
选项C：不一定。
选项D：结合选项A的补充内容来理解

24.【单选题】——队列：循环队列的入队情况判断

已知循环队列所使用的数组长度为 10，front 和 rear 分别为队头和队尾位置的数组下标，则当循环队列处于以下哪一种状态时，可以将新元素入队？（A ）。B

A.front = 0, rear = 9

B.front = 8, rear = 6

C.front = 4, rear = 3

D.front = 1, rear = 0

这种题就抓着这个“(Q.rear + 1) % MaxSize == Q.front”来看，只有两者不相等的情况下，才能执行元素入队，出队的话就只需要看front和rear相不相等，相等是队空的情况，不允许执行了。

A.（9+1）%10=0

B.（6+1）%10=7

C.（3+1）%10=4

D.（0+1）%10=1

只有B是不等于front值的，所以也只有b选项才可以让元素入队。

之所以当时做错这道题，%的运算搞懵了。

25.【单选题】——队列：两种队列入队的时间复杂度

链式队列和循环队列执行入队操作的时间复杂度分别为（ A）。

A.O(1), O(1)

B.O(1), O(n)

C.O(n), O(1)

D.O(n), O(n)

循序栈、链栈的出栈入栈和循环队列、链队列的出队入队操作时间复杂度都是O(1)

二、填空题

——绪论——

26.【填空题】——数据结构的概念

相互之间存在一种或多种特定关系的数据元素的集合，称为__数据结构_。

27.【填空题】顺序存储结构的概念

逻辑上相邻的数据元素，存储在相邻的物理位置中。这样设计的存储结构称为__顺序_存储结构。

28.【填空题】——算法的概念

求解问题的一系列步骤的集合，可称为__算法_。

29.【填空题】——算法效率的评估方式

对算法的效率进行评价，主要考虑算法的__时间__效率与__空间__效率两个方面。

30.【填空题】——函数的时间复杂度求解

void func(int n) {
	while (n > 1) {
		if (n % 2 == 0)cout << n << "";
		n--;
	}
}

该算法的时间复杂度O（n/2）  O(n)

——顺序表与链表——

31.【填空题】——顺序表：元素的存储位置计算

假设顺序表的第一个元素的存储位置为 128，每个元素占用的存储空间为8，则第9个元素的存储位置为 _192__ 。

第9个元素的存储位置为 192。

计算方法：

第一个元素的存储位置为 128；
每个元素占用的存储空间为 8，因此第二个元素的存储位置为 128 + 8 = 136，第三个元素的存储位置为 136 + 8 = 144，以此类推；
因为第9个元素是从第一个元素往后数的第9个，所以第9个元素的存储位置为 128 + 8 × (9 - 1) = 192。

32.【填空题】——顺序表：有效插入位置的判断条件

已知顺序表的存储空间为MaxSize，顺序表的长度为Length，在顺序表中进行插入操作的位置为Pos，则有效的插入位置可表示为__1≤Pos≤Length+1__

 if (pos < 1 || pos > L.length + 1) {        //判位置
    cout << "插入位置无效！" << endl;
    return false; }

33.【填空题】——顺序表：插入操作涉及元素的移动次数

已知顺序表的长度为n，插入操作的位置为i（从1开始计算），则插入操作需要移动的元素个数为 _n-i+1__。

【n-i（从插入位置）+1(的后一个元素)】开始移动

34.【填空题】——顺序表：删除算法

以下是顺序表的删除操作的算法实现，程序划线处应填入的语句是：_i-1__

这里post是指删除元素的逻辑位置

用item去返回被删除的元素

所以item这里应该让逻辑指定位置-1，才是被删元素在表中的存储下标

接着一个for循环，开始删除元素，删除元素那肯定就是要把删除元素的后面元素往上提拔一下，所以i=pos，后一个元素提到前一个元素上，表长减一

35.【填空题】 ——单链表知识点：头结点

为方便单链表的相关操作，在单链表的第一个元素结点前增设一个不使用数据域的结点，这个增设的结点可称为__头_结点。

36.【填空题】——单链表指定功能的对应操作

当使用C++实现单链表的相关算法时，如需要分配结点的空间可执行__new_操作，如需要回收结点的空间可执行 delete 操作。

37.【填空题】 ——单链表：查找

在单链表的第 6 个元素之前插入新元素，需要首先找到第 __5_ 个元素的位置。

因为第六个元素的地址存放在第五个元素的next域上，找到第五个元素的位置，把第五个元素的next域值给新元素的next域值，再更新第五个元素的next域值为新元素的地址，这样就完成了插入元素操作

38.【填空题】 ——顺序表：查找指定元素算法的时间复杂度

在顺序表中，查找指定元素在顺序表中的位置，该算法的时间复杂度为__O(n)_。

39.【填空题】——单链表：插入算法的时间复杂度

在单链表的头部插入新元素，算法的时间复杂度是_O(1)__ 。

单、双链表的插入操作，若给定前驱节点，则时间复杂度均为O (1)。否则只能按序或按值查找前驱节点，时间复杂度为O (n)。

至于查找，二者的时间复杂度均为O (n)。

40.【填空题】 ——单链表：删除算法的时间复杂度

在单链表中删除元素的算法，时间复杂度为_O(n)__ 。

——栈——

41.【填空题】 ——栈的特征

在使用栈的过程中，最后入栈的元素必须最先__出栈_。

42.【填空题】 ——栈：顺序栈入栈算法

以下是顺序栈入栈算法的程序实现，程序划线处应填入的语句是：_S.top__

栈：栈顶入栈出栈操作

43.【填空题】 ——栈：链式栈出栈算法

以下是链式栈出栈算法的程序实现，程序划线处应填入的语句是：__S_

44.【填空题】——应用：中缀表达式与后缀表达式的转化

已知中缀表达式为a*(b+c)–d ，则相应的后缀表达式为 __abc+*d-_ 。

45.【填空题】 ——应用：中缀表达式与后缀表达式的转化

已知中缀表达式为a*b/(c–d)*(e+f) ，则相应的后缀表达式为abcd-/*ef+* 。ab*cd-/ef+*

——队列——

46.【填空题】——队列的特征

队列是限定在表的一端进行插入，另一端进行__删除_的线性表。

48.【填空题】 ——队列：循环队列的存储元素计算

已知循环队列的存储空间最大长度为100，则该循环队列最多可以存储 __99_ 个队列的元素。

为了解决“队满”“队空”的问题，常用的解决方法是少用一个存储单元

队空 front==rear
队满 (rear + 1) % MaxSize == front
队列长度 (rear–front+MaxSize) % MaxSize

50.【填空题】——队列：循环队列出队算法的时间复杂度

循环队列出队算法的时间复杂度为 _O(1)__ 。

操作	时间复杂度
初始化	O(1)
求元素个数	O(1)
判表空	O(1)
插入	O(n)
删除	O(n)
获取指定位置上的数据元素	O(1)
查找指定元素位置	O(n)
遍历	O(n)

队空	front==rear
队满	(rear + 1) % MaxSize == front
队列长度	(rear–front+MaxSize) % MaxSize