2022

• 第一题：A  print是格式化输出，c++的输出方式，且c语言就可以使用，不涉及面向对象

• 面向对象语言才能进行的操作：定义类或结构体，对象调用成员函数，构造派生类

• 面向对象特性：1.封装 2.继承 3.多态 4.消息机制 5.类型转换 6.模板

• 第四题：C  

• 数组和链表都能做排序。比如冒泡排序，里面只有交换相邻元素的操作，这一操作在数组和链表中都可以做；

• 链表和数组能存储的信息取决于其长度，哪个更长哪个能存储更多信息；

• 一旦申请数组，数组的长度固定，而链表可以申请和释放结点，大小可以动态调整

• 第六题： B  前缀表达式

• 中缀表达式转化为前缀表达式的例子:

  a+b ---> +ab

  a+(b-c) ---> +a-bc

  a+(b-c)*d ---> +a*-bcd

  a+1+3 ---> ++a13

• 步骤：

  1.加括号

  2.按优先级从低到高依次去括号，并将运算符移到该括号前面

• 举个栗子：

  1+(2+3)*4-5

  ((1+((2+3)*4))-5)

  -(1+((2+3)*4))5

  -+1((2+3)*4)5

  -+1*(2+3)45

  -+1*+2345

• 后缀表达式同理

  1+(2+3)*4-5

  ((1+((2+3)*4))-5)

  (1+((2+3)*4))5-

  1((2+3)*4)+5-

  1(2+3)4*+5-

  123+4*+5-

• 第八题：C 

• 左孩子下标为偶数，右孩子下标为奇数

• 左孩子下标为2i，右孩子为2i+1

• 第九题   A 

• 有向连通图，n个顶点至少存在n条边，所以有n个非零元素

• 第十题  D

• 图的深度优先遍历算法常使用的数据结构为栈

• 栈的访问原则为后进先出，队列的访问原则是先进先出

•  队列常常被用于广度优先搜索算法

• 栈与队列本质上都是功能受限的线性表，本质是相同的。用栈实现队列，虽然平时不会这样做，这样做也没什么意义，但还是可以实现的

• 第十二题  B 

• 稳定：冒泡、插入、归并、基数、折半插入

• 不稳定：选择、快速、希尔、堆排

•  第十四题  A

• abcab的不相同子串有：
  长为1的子串：a,b,c
  长为2的子串：ab,bc,ca
  长为3的子串：abc,bca,cab
  长为4的子串：abca,bcab
  长为5的子串：abcab
  共有12个

• 第十五题  B 

• 递归是通过调用自身来求解问题的编程技术

• 编译是将用某种高级语言转换为机器代码的编程技术

• 面向对象编程（或者说“类”）是面向对象和数据而不是功能和逻辑的编程语言模型