数据结构与算法Python版MOOC笔记及练习【三】

• • 一、什么是线性结构
  • • 线性结构特点
  • 二、为什么要使用括号
  • 三、进制之间的转换
  • 四、前中后缀之间对比及使用
  • 五、课程练习(自己写的共14.00/19.00分，之后再填坑系列)

线性结构是一种有序数据项的集合，其中每个数据项都有唯一的前驱和后继（除了第一个没有前驱，最后一个没有后继）
新的数据项加入到数据集中，只会加入到原有某个数据项之前或之后，具有这种性质的数据集，就称为线性结构。

1、线性结构总有两端，不同线性结构的关键区别在于数据项增减的方式。

2、距离栈底越近的数据项留在栈中的时间就越长，而最新加入栈的数据项会被最先移除，这种次序通常称为“后进先出”。

括号用来指定表达式项的计算优先级，每对开闭括号都要正确的嵌套，对括号是否正确匹配的识别是很多语言编译器的基础算法。HTML/XML文档也有类似于括号的开闭标记，这种层次结构化文档的校验、操作也可以通过栈来实现。

1、二进制是计算机原理中最基本的概念，作为组成计算机最基本部件的逻辑门电路，其输入和输出均仅为两种状态：0和1。
2、十进制是人类传统文化种最基本的数值概念，0~9十个数字字符。
3、没有进制之间的转换，人们和计算机的额交互会相当的困难。


十进制转换为二进制的算法，很容易可以扩展到转换任意N进制

在前缀和后缀表达式中，操作符的次序完全决定了运算的次序，不再有混淆。因此在很多情况下，表达式的计算机表示都避免用复杂的中缀表达式。

(A+(B*C))显示表达了计算次序，每一对括号都包含了一组完整的操作符和操作数。

1单选(2分)‎假设你执行了下列的栈操作：​

‎s = Stack()
s.push(1)
s.push(3)
s.push(5)
s.pop()
s.push(7)

现在栈内还有哪些元素？
A.1, 5, 7
B.3, 5, 7
C.1, 3, 7
D.1, 3, 5

2单选(2分)‏将以下中缀表达式：‏( 5 - 3 ) * ( 2 + 4 )‏转换为后缀表达式，结果为？‍

A.5 3 2 * - 4 +
B.5 3 - 2 4 + *
C.5 3 2 * 4 + -
D.5 3 2 4 + * -

3单选(2分)‌给定后缀表达式

‌3 6 + 5 2 - /

‌求值结果为？
A.3
B.6
C.10
D.4

4单选(2分)‍使用括号匹配算法判断以下表达式：‍([()[]{]}<>)结果是否匹配？匹配过程中栈内元素最多有多少个？

A.是，3
B.是，4
C.否，3
D.否，4

5单选(2分)​判断以下函数的功能

​def func(str1):
    s = Stack()
    for char in str1:
        s.push(char)
    str2 = ''
    while not s.isEmpty():
        str2 += s.pop()
    return str2

A.判断给定字符串长度
B.将给定的字符串反转输出
C.包含错误，无法运行
D.将给定字符串复制并输出

6多选(3分)以下哪些关于栈的说法是正确的？
A.括号匹配算法需要栈结构的参与
B.在Python中栈结构可以由list来实现
C.栈的特性是先进先出(FIFO)
D.栈的特性是后进先出(LIFO)

7多选(3分)​以下未完成的函数可实现不同的功能

​def func(lst1):
    s1, s2 = Stack(), Stack()
    for item in lst1:
        s1.push(item)
    lst2 = []
    while not s1.isEmpty():
        ### 在此进行代码填空 ###
    return lst2

# 测试
print(func([1, 3, 5, 7, 9]))

在下列选项中，填空内容与分别对列表[1, 3, 5, 7, 9]调用结果相对应的选项有？

A.lst2.append(s1.pop()) [9, 7, 5, 3, 1]
B.lst2.append(s1.pop()) [1, 3, 5, 7, 9]
C.lst2.append(s1.peek()) [9, 9, 9, 9, 9]
D.lst2.append(s1.peek()) 死循环，无法运行

8多选(3分)‍以下哪些算法适合用栈来实现？

A.1到N的累计求和算法
B.实现UNDO和REDO功能的算法
C.HTML标签匹配算法
D.求列表平均数的算法