数据结构错题典题集

时间复杂度

（1）求如下递归方程的时间复杂度

$$T(n)=\begin{cases} 1, & n=1 \\ 2T(n/2)+n, & n>1 \end{cases}$$

设$n=2^k(k\geq0)$，则根据公式可以推出：

$$T(2^k) = 2T(2^{k-1})+2^k$$

$$T(2^k) = 2^2T(2^{k-2})+2\times2^k$$

$$T(2^k) = 2^iT(2^{k-i})+i\times2^k$$

$$T(2^k) = 2^kT(2^0)+k\times2^k$$

将$2^k=n和k=log_2n$带入：

$$T(n) = 2^{log_2n} + n \times log_2n$$

所以时间复杂度为$O(nlog_2n)$

线性表

（1）对长度为n的顺序表L，编写一个时间复杂度为$O(n)$，空间复杂度为$O(1)$的算法，该算法删除线性表中所有值为x的数据元素。

用k记录顺序表中不等于x的元素个数（即需要保存的元素个数），扫描时将不等于x的元素移动到下标k的位置，并更新k值。最后修改L长度

void del_x(SeqList &L, Elemtype x){
  int k=0;
  for(int i = 0; i < L.length; i++){
    if(L.data[i] != x)
      L.data[k++] = L.data[i];
  }
  L.length = k;
}

（2）将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果结果顺序表。

bool merge(SeqList A, SeqList B, SeqList &L){
  int i = 0, j = 0, k = 0;
  while(i < A.length && j < B.length){
    if(A.data[i] <= B.data[j])
      L.data[k++] = A.data[i++];
    else
      L.data[k++] = B.data[j++];
  }
  while(i < A.length)
    L.data[k++] = A.data[i++];
  while(j < B.length)
    L.data[k++] = B.data[j++];
  L.length = k;
  return true;
}

(3)归并两个递增的链表，不额外开辟链表空间，要求结果降序,(头插法)$T(n) = O(len1 + len2)$

void merge_orderlyList(LinkList<int> &L1, LinkList<int> &L2){
  LinkList<int> p1 = L1->next, p2 = L2->next, tep;
  L1->next = nullptr;
  while(p1 && p2){
    if(p1->data < p2->data){
      tep = p1;
      p1 = p1->next;
      tep->next = L1->next;
      L1->next = tep;
    }else{
      tep = p2;
      p2 = p2->next;
      tep->next = L1->next;
      L1->next = tep;
    }
  }
  p1 = p1==nullptr?p2:p1;
  while(p1 != nullptr){
    tep = p1;
    p1 = p1->next;
    tep->next = L1->next;
    L1->next = tep;
  }
}

(4) 找到两个链表的公共节点，注意：当两个链表有公共节点时，它们从公共节点开始都是重合的,时间复杂度：$O(len1 + len2)$

LinkList<int> find_sameNode(LinkList<int> &L1, LinkList<int> &L2){
  int len1 = length(L1), len2 = length(L2);
  int dist = abs(len1 - len2);
  LinkList<int> longList, shortList;
  longList = len1<len2?L2->next:L1->next;
  shortList = len1<len2?L1->next:L2->next;
  while(dist--)
    longList = longList->next;
  while(longList != nullptr) {
    if (longList == shortList){
      return longList;
    }else{
      longList = longList->next;
      shortList = shortList->next;
    }
  }
  return nullptr;
}

(5)判断L2是否L1的连续子序列

bool subsequence(LinkList<int> &L1, LinkList<int> &L2){
  LNode<int> *pre = L1->next, *p = L1->next, *q = L2->next;
  while(p && q){
    if(p->data == q->data){
      p = p->next;
      q = q->next;
    }else{
      pre = pre->next;
      p = pre;
      q = L2->next;
    }
  }
  return q == nullptr;
}

(6)删除最小节点直至循环单链表表空，再删除头结点

void delete_minToEmpty(CLinkList<int> &L){
  CNode<int> *p, *minpre, *min, *pre;
  while(L->next != L){
    p = L->next;
    pre = L;
    min = p; minpre = pre;
    while(p != L){
      if(p->data < min->data){
        min = p;
        minpre = pre;
      }
      pre = p;
      p = p->next;
    }
    cout<<"deleted val: "<<min->data<<endl;
    minpre->next = min->next;
    free(min);
  }
  /**
     * 调用free释放掉所分配的内存后，表明该内存可以被别人使用，
     * 也就是说，其他地方调用malloc后，可以分配到该内存,
     * 并不代表free()以后指针指向null
     */
  free(L);
  L = nullptr; //一种规范
}

树

（1）三种遍历顺序的非递归实现

都是使用栈，根据遍历顺序，有不同的访问时机

/**
 * 非递归后序遍历
 * @param root
 */
void post_order(BitTree<int> root){
    cout<<endl<<"post order:"<<endl;
    TreeNode<int> *p = root, *r = nullptr;
    ListStack<TreeNode<int> *> stack;
    initListStack(stack);
    while(p || !isEmpty(stack)){
        if(p){
            Push(stack, p);
            p = p->lchild;
        }else{
            getTop(stack, p);
            if(p->rchild && p->rchild != r){
                p = p->rchild;
            }else{
                Pop(stack, p);
                visit(p);
                r = p;
                p = nullptr;
            }
        }
    }
}
/**
 * 非递归先序遍历
 * @param root
 */
void pre_order(BitTree<int> root){
    cout<<endl<<"pre order:"<<endl;
    TreeNode<int> *p = root;
    ListStack<TreeNode<int> *> stack;
    initListStack(stack);
    Push(stack, p);
    while(!isEmpty(stack)){
        Pop(stack, p);
        if(p->rchild)
            Push(stack, p->rchild);
        if(p->lchild)
            Push(stack, p->lchild);
        visit(p);
    }
}
/**
 * 非递归中序遍历
 * @param root
 */
void in_order(BitTree<int> root){
    cout<<endl<<"in order:"<<endl;
    TreeNode<int> *p = root;
    ListStack<TreeNode<int> *> stack;
    initListStack(stack);
    while(p || !isEmpty(stack)){
        if(p){
            Push(stack, p);
            p = p->lchild;
        }else{
            getTop(stack, p);
            visit(p);
            Pop(stack, p);
            p = p->rchild;
        }
    }
}

（2）给出二叉树先序序列（$pre[1-n]$）和中序序列（$in[1-n]$），构造二叉树的二叉链表。

/**
 * 给出二叉树先序序列（$pre[1-n]$）和中序序列（$in[1-n]$），构造二叉树的二叉链表。
 * @param pre 
 * @param in
 * @param pl 前序序列最左的节点
 * @param pr 前序序列最右的节点
 * @param il 中序序列最左的节点
 * @param ir 中序序列最右的节点
 * @return
 */
BitTree<int> create_by_in_pre(const int pre[], const int in[], int pl, int pr, int il, int ir){
    if(pl > pr || il > ir)return nullptr;
    auto root = (TreeNode<int> *)malloc(sizeof(TreeNode<int>));
    root->data = pre[pl];
    //注意此处应从il开始找中序的根（中序子序列中找）
    int k = il;
    for (k; in[k] != root->data; k++);
    k = k - il; // 左子树序列的长度
    root->lchild = create_by_in_pre(pre, in, pl+1, pl+k, il, il+k-1);
    root->rchild = create_by_in_pre(pre, in, pl+k+1, pr, il+k+1, ir);
    return root;
}

//测试
#include "head/c/TreeNode.h"
using namespace std;

int main() {
    int A[] = {0,1,7,4,0,9,4,8};
    int B[] = {0,4,7,0,1,4,9,8};
    BitTree<int> root = create_by_in_pre(A, B, 1, 7, 1, 7);
    print(root);
    return 0;
}
/**
TestBitTree's structure:
1
7 9
4 0 4 8
*/

（3）判断完全二叉树

/**
 * 判断是否为完全二叉树
 * @description 层序遍历，将所有节点入队(包括空节点)，如果空节点后面还有非空节点就不是完全二叉树
 * @param root
 * @return
 */
bool judgeFullBinaryTree(BitTree<int> root){
    LinkQueue<TreeNode<int> *> q{};
    TreeNode<int> *p;
    initQueue(q);
    if(!root) return true;//空树为满二叉树
    enQueue(q, root);
    while(!isEmpty(q)){
        deQueue(q, p);
        if(p){
            enQueue(q, p->lchild);
            enQueue(q, p->rchild);
        }else{
            while(!isEmpty(q)){
                deQueue(q, p);
                if(p)
                    return false;
            }
        }
    }
    return true;
}

（4）删除所有以$x$为根节点的所有子树

/**
 * 删除所有以x为根的子树,层序遍历所有可能节点
 * @param root
 * @param x
 */
void deleteTree(BitTree<int> &root){//注意删除树的方式
    if(root){
        deleteTree(root->lchild);
        deleteTree(root->rchild);
        free(root);
    }
}
void delete_by_key(BitTree<int> &root, int x) {
    LinkQueue<TreeNode<int> *> q{};
    TreeNode<int> *p;
    if (root->data == x) {
        deleteTree(root);
        return;
    }
    initQueue(q);
    enQueue(q, root);
    while(!isEmpty(q)){
        deQueue(q, p);
        if(p->lchild) {
            if (p->lchild->data == x) {
                deleteTree(p->lchild);
                p->lchild = nullptr;
            } else {
                enQueue(q, p->lchild);
            }
        }
        if(p->rchild) {
            if (p->rchild->data == x) {
                deleteTree(p->rchild);
                p->rchild = nullptr;
            } else {
                enQueue(q, p->rchild);
            }
        }
    }
}

（5）打印值为$x$的节点的所有祖先

/**
 * 找到值为x的节点的所有祖先,后序遍历遍历到x时,栈中节点都是x的祖先
 * @param root
 * @param x
 */
#define MAXSIZE 1000
void find_ancestor(BitTree<int> root, int x){
    TreeNode<int>* stack[MAXSIZE];
    int top = -1;
    TreeNode<int> *p = root, *r = nullptr;
    while(p || top != -1){
        if(p){
            stack[++top] = p;
            p = p->lchild;
        }else{
            p = stack[top];
            if(p->rchild && p->rchild != r){
                p = p->rchild;
            }else{
                p = stack[top--];
                if(p->data == x)
                    break;
                r = p;
                p = nullptr;
            }
        }
    }
    while(top != -1){
        cout<<endl<<"Ancestors: "<<stack[top--]->data<<" ";
    }
}

查找与排序

（1）排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，不可能是快速排序第二趟结果的是（D）

A : 5,2,16,12,28,60,32,72

B : 2,16,5,28,12,60,32,72

C : 2,12,16,5,28,32,72,60

D : 5,2,12,28,16,32,72,60

排序后的结果2,5,12,16,28,32,60,72

所有元素进行一遍处理：当确定一个元素的位置后，第二次应当对该元素左右子表都确定一个元素才算，遍历完。

$A$: 可见28,72是确定了位置的，当第一遍确定的是72（是边界点），第二他趟只需确定他的左子表（28）$√$

$B$：同理2,28是确定的，第一遍无论是确定2还是72都满足条件 $√$

$C$：可见2,28,32三个元素确定了最终位置，当第一遍确定的是28时，第二遍确定左右子表的2和32，满足条件 $√$

$D$：可见12,32确定了最终位置，但无论第一遍确定的是谁，第二遍都要确定左右子表的两个元素（它们不是边界点），至少应该有三个元素确定了最终位置 $×$