25-26-1-数据结构-期中(软件工程)

填空

  1. for(i=0;i<n;i++){for(j=i;j<n;j++){......}}的时间复杂度 【暂无答案】
  2. 在长度为 n 的线性表的开头插入和删除元素,分别需要移动多少元素 【暂无答案】
  3. 栈的进出操作在 【暂无答案】 进行,队列的插入操作在 【暂无答案】 进行
  4. 给定一个字符串,根据substring()写出其子串 【暂无答案】
  5. 二叉树中 n0n_0 和 n2n_2 的关系 【暂无答案】

简答

1.

简述一个关于栈的函数的作用

2.

简述一个关于链表的函数的作用

3.

补全一段关于双向链表的代码并简述其作用

4.

  1. 已知一个二叉树的后序 abcdefg,中序 acbgedf,是否有且仅有 1 个这样的树?若有,将其画出
  2. 已知中序和后序的遍历结果,能否唯一地确定一个树?并证明

代码

1.

  1. 定义一个不带头结点的单链表,并将头指针初始化为空
  2. 使用尾插法,向空链表中插入六个元素
  3. 删除第一个结点
  4. 从头逐个删除链表中的结点

2.

使用固定长度数组实现字符串的连接

3.

计算二叉树中度为 2 的结点个数