1.什么是算法？

算法是计算机科学中的基本概念，是对特定问题的求解步骤

2.什么是算法的复杂度？

分为时间复杂度和空间复杂度，前者一般是指程序运行从开始到结束所需的时间，后者一般是指对应的程序从运行开始到结束所需的储存空间

3.数据结构中的逻辑结果可分为哪几种？

  • 线性结构
  • 树形结构
  • 图结构
  • 集合结构

4.线性表的顺序存储、链式存储在以下五个方面有何差异？

  1. 存储空间分配方式：
    • 顺序存储结构是讲逻辑上的相关的数据元素依次存储在地址连续的存储空间中；
    • 链式存储结构中，数据元素的存储位置并不能体现它们之间的逻辑关系。
  2. 存储密度：
    • 顺序存储密度大（=1），存储空间利用率高
    • 链式存储密度小（<1），存储空间利用率低
  3. 根据位置访问元素的时间复杂度：
    • 顺序存储O(1)
    • 链式存储O(n)
  4. 插入、删除操作的时间复杂度：
    • 顺序存储O(n)
    • 链式存储O(1)
  5. 适用情形：
    • 顺序存储适宜于做查找这样的静态操作
    • 链式存储适宜做插入、删除这样的动态操作

5.线性表的特点有哪些？

  • 存在唯一的一个被称作“第一个”的数据元素，表头元素；
  • 存在唯一的一个被称作“最后一个”的数据元素。表尾元素；
  • 除第一个之外，结构中的每个数据元素均只有一个前驱；
  • 除最后一个外，结构中的每个数据元素均只有一个后继。

6.在长度为n的顺序表中的第i个位置处插入一个元素，需要移动多少个元素？

n-i+1

7.理解算法：线性表La和Lb，将两个表合并成一个新的线性表并存于La中。

练习：已知La、Lb和以下函数（可直接使用）

int Length(LinkList list){}   //获取list链表的长度
int getLocByValue(LinkList list,int x) {}  //查元素x在 链表list中的位置，如果不存在返回0
int getNodeByLoc(LinkList list,int i) {}  //查链表list 中 i位置的元素

请完成connect方法，补全将两个表合并成一个新的线性表 存于La中的代码：

LinkList connect(LinkList La,LinkList Lb){
    LinkList Lc;
    Init(Lc, Length(La)+Length(Lb));
    for(int i=0;i<=Length(La)-1;i++){
        Insert(Lc,i,getNodeByLoc(La,i));
    }
    for(int i=0;i<=Length(Lb)-1;i++){
        value = getNodeByL(Lb,i);
        if(value = 0){break;}
        for(int j=0;j<=Length(Lc)-1;i++){
            if(value < getNodeByL(Lc,j)){
                Insert(Lc,i,value);
                break;
            }
        }
    }
    return Lc;
}

8.带头结点的单链表和不带头结点的单链表为空的条件分别是？带头结点的循环单链表为空的条件是？

  • 带头结点：head->next==NULL
  • 不带头结点：head == NULL
  • 带头结点的循环单链表：head->next==head

9.在单链表中插入结点的算法中，指针如何修改

  1. 将需要插入节点的next指针指向后一个节点
  2. 将前面的节点的next指针指向需要插入的节点

10.理解单链表中插入新结点的算法

已知方法 getElem(List list, int i)可获取链表list上位置i处的结点。请写出 创建新结点S，并将结点插入到 位置i之前的代码：

// i之前即为i-1
Node S;
Node bNode = getElem(list, i-1);
S.next = bNode;
Node fNode = getElem(list, i-2);
fNode.next = S;

11.理解双向链表中插入新结点的算法

  1. 将S的prev指向a结点
  2. 将S的next指向b结点
  3. 将a的next指向S结点
  4. 将b的prev指向S结点

已知方法getElem(List list, int i)可获取链表list上位置i处的结点。请写出矿建新节点S，并将结点插入到位置I之前的代码。

Node S;
Node b = getElem(list, i);
Node a = getElem(list, i-1);
S.prev = a;
S.next = b;
a.next = S;
b.prev = S;

12.理解栈和队列的操作特点：

先进后出，先进先出；已经进栈顺序，求可能的出栈顺序。

链栈相对于顺序栈的优点是什么？

  • 使用链式栈的优点在于它能够克服用数组实现的顺序栈空间利用率不高的特点
  • 使用链栈通常不会出现栈满的情况，因为链栈是动态申请内存的

练习：一个栈的入栈顺序为ABCDE, 则出栈顺序不可能是：

A.EDCBA B.DECBA C.DCEAB D.ABCDE

答：C

13.理解算法：顺序栈的进栈操作

先要判断栈S是否为满，若不满再将记录栈顶的下标变量top加1，再将进栈元素放进栈顶位置上

14.循环单链表的特点是什么？

链表中最后一个结点的指针域不再是结束标志，而是指向整个链表的第一个结点，从而使链表形成一个环。和单链表相同，循环单链表也有带头结点和不带头结点两种。带头结点的循环单链表实现插入和删除操作较为方便，且更加适用。

15.循环队列中进行插入和删除操作后，其头尾指针如何变化？

  • 插入：头指针front不变，尾指针rear = (rear + 1)%len(list)
  • 删除： 头指针front = (front + 1)%len(list)

根据循环队列的容量及头尾指针，求循环队列中元素的个数。

(length + rear - front) % length

16.用哪种数据结构来实现括号匹配的算法？

使用栈结构

假设表达式中包含三种括号：圆括号、方括号和花括号，它们可互相嵌套，编写一个检查表达式中括号是否配对的函数。

  • 依次读取字符串
  • 若读取的是左括号，入栈
  • 若读取的是右括号，且与栈顶的左括号匹配，则左括号出栈，否则不合法
  • 若读取结束后，栈内依然有任何元素存在，则不合法
  • 若读取结束后，栈内无元素存在，则括号匹配合法