北京工业大学896历年真题算法 @StdKe整理 所有算法都是自己手写思路然后在python上模拟(暂时没C环境)再翻译成C的,难免疏漏，请不吝赐教 仅供StdKe周围学习交流，请勿传播

## 2010

  • 递归求二叉树深度
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

int GetTreeHeight(BTree T){
    int left_deep;
    int right_deep;
    if(T == NULL){
        return 0;
    }
    left_deep = GetTreeHeight(T->lchid);
    right_deep = GetTreeHeight(T->rchild);
    (left_deep>right_deep)?return left_deep+1:right_deep+1;
}
  • 荷兰旗问题
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void Holland(char list[]){
    int current = 0;
    int begin = 0;
    int end = N-1;
    while(cuuent<=end){
        if(list[current] == "red"){//红色应在前面，交换begin和current的值，begin和current向后移动
            swap(list[current],list[begin]);
            begin++;
            current++;
        }else if(list[current] == "white"){//白色，在中间，current向后移动
            current++;
        }else{//蓝色，应在最后，交换current和last，last向前移动，current向后移动
            swap(list[current],list[last]);
            last--;
            curretn++;

        }
    }
}
void swap(int a,int b){
    int c = a;
    a = b;
    b = c;
}

2011

  • 冒泡排序
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

void BubbleSort(ElemType A[],int n){
    for(i=0;i<n-1;i++){
        int flag = 0;
        for(j=n-1;j>i;j--){
            if(A[j-1].key>A[j].key){
                swap(A[j-1],A[j]);
                flag = 1;
            }
        }
        if(!flag){
            return;
        }
    }
}
  • 使用图的遍历算法判断连通图是否存在回路
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

/**
 * visited[] => 访问标记数组
 * visited[i]=1 => 当前节点已访问
 * visited[i]=0 => 当前节点正在访问
 * visited[i]=-1 => 当前节点未访问
 * */
bool exitCyclePath(Graph G,int v){
    for(i = 0;i<G.vexnum;i++){
        if(!visited[i]){ //顶点未访问
            visited[i] = 0; //准备访问
            if(DFNSCheck(G,v))
                return TRUE;
        }
    }
    return FALSE;
}

int flag = 0;
bool DFSCheck(Graph G,int v){
    if(flag){
        return TRUE;
    }
    if(visited[v]!=0){ 
        visited[v]=1;   //除正在访问的节点外，其余节点访问时访问标记都为1
    }
    for(w=FirstAdjvex(G,v);w>=0;W=NextAdjvex(G,w,v)){
        if(visited[w] == 0){
            flag = TRUE;
            break;
        }
        else{
            DFSCheck(G,w)
        }
    }
    visited[v] = 1; //当前节点访问结束
    return flag;
}

2012

  • 正负排序问题
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

void asjust(Sqlist &l){
    int front = 0;
    int last = l.size-1;
    while(front <= last){
        if(l.data[front]>0){
            swap(l.data[front],l.data[last]);
            last--;
        }else{
            front++;
        }
    }
}
void swap(int a,int b){
    //
}
  • 二叉排序树合并
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void merge(BiTree *A,BiTree *B){
    if(A=null){
        return;
    }
    BiTree *p = A;
    while(p>lchid){
        p = p->lchild;
    }
    p->lchild = B;
}

2013

  • 计数排序
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

void countSort(Sqlist A,Sqlist B){
    int i,count;
    for(i = 0;i<A.size;i++){
        count = 0;
        for(j = 0;j<A.size;j++){
            if(A.data[i]>A.data[j]){
                count++;
            }
        }
        B.data[count] = A.data[i];
    }
}
  • huffman编码长度
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

int MaxHuffmanCode(HuffmanTree HT,int n){
    int max = 0;
    for(i=1;i<=n;i++){
        int len = 0；
        int j = i;
        while(j.parent!=0){
            j = j.parent;
        }
        if(max<len){
            max = len;
        }
    }
    return max;
}

2014

  • 双向冒泡排序
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void BubbleSort(Sqlist &a){
    int n = a.size-1;
    int left = 0;
    int right = n-1;
    while(left <= right){
        for(i=left;i<right;i++){
            if(a[i]>a[a[i+1]]){
                swap(a[i],a[i+1]);
            }
        }
        right--;
        for(j=right;j>left;j--){
            if(a[j]<j[j-1]){
                swap(a[j],a[j-1]);
            }
        }
        left++;
    }
}

void swap(int a,int b){
  //
}
  • 返回兄弟节点
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include <queue>

BiTree* BrotherNode(BiTree T,Bitree*q){
    queue <CSNode> Q;
    Q.push(T);
    while(!Q.empty()){
        p = Q.pop();
        if(p->lchid==q||p->rchild==q){
            return ((p->lchild == q)?p->rchild:p->lchild);
        }
        if(p->lchild){
            Q.push(p->lchild);
        }
        if(p->rchild){
            Q.push(p->rchild);
        }
    }
    return null;
}

2015

  • 路径可达问题
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

int flag = 0;
int w = 0;
int PathFind(MGraph &G){
    int count = 0;
    for(i=0;i<G.vexnum;i++){
        for(j=0;j<G.vexnum;j++){
            if(DfsFindPath(G,i,j)){
                    flag = 0; //每次执行完如果返回存在目标节点后flag初始化
                    count++;
            }
        }
    }
    return count;
}
int DfsFindPath(Graph G,int i,int j){
    if(flag){
        return flag;//如果在后续递归中找到了目标节点，直接返回
    }
    for(w = FirstAdjvex(G,i);w>=0;w=NextAdjvex(G,i,w)){
        if(w==j){
            flag = 1;   //找到目标节点
            return flag;
        }else if(!visited[w]){
            DfsFindPath(G,w,j);
        }
    }
    return flag; //for循环结束flag仍未执行说明节点不符合条件，return flag === return 0
}
  • 排序链表
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

void CreateLinkList(int A[],int n,LinkList &L){
    LinkList *q;
    LinkList *p = L;
    for(int i=0;i<n;i++)
        while(p->next!=NULL && p->next->data < A[i]){
            p = p->next;
        }//退出while说明找到了p->next->data > A[i] || p->next =null,此时在表尾插入
        q = p->next;
        s = (LinkList*)malloc(sizeof(LinkList)); 
        //插入
        s->data = A[i];
        s->next = q;
        p->next = s;
        p = L;//重置p
    }
}

2016

  • 图非递归遍历
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include <stack>
void UnrecDFSTraverse(MGraph G,int v){
    stack<int> s;
    int i;
    int n = G.n;
    for(i=0;i<n;i++){
        vistited[i] = 0;
    }
    s.push(v);
    while(!s.empty()){
        p = s.pop()
        visited();
        for(w=FirstAdjVex(G,p);w>=0;w=NextAdjVex(G,p,w)){
            if(!vistied[p]){
                s.push(p)
            }
        }
    }
}
  • 求树叶节点
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

\#include <queue>

int OutPutLeaves(CSTree T){
    if(T == NULL){
        return 0;
    }
    int count = 0;
    CSNode *p;
    queue <CSNode> q;
    q.push(T);
    while(!q.empty()){
        p = q.pop();
        if(p->firstnode == NULL){
            count++;
        }else{
            q.push(p->firstnode);
        }
        if(p->nextsilbing){
            q.push(p->nextsilbing);
        }
    }
    return count;
}

2017

  • 判断AVL树
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

int TreeDepth(BiTNode *T){
    if(T == NULL){
        return 0;
    }
    int left_depth = TreeDepth(T->lchid);
    int right_depth = TreeDepth(T->rchild);
    return (left_depth>right_depth?(left_depth+1):(right_depth+1));
}

bool isBalanced(BiTNode *T,int &h){
    if(T == NULL){
        return TRUE;
    }
    int left_depth = TreeDepth(T->lchid);
    int right_depth = TreeDepth(T->rchild);

    bool balance_flag_left = isBalanced(T->lchild,left_depth);
    bool balance_flag_right = isBalanced(T->right,right_depth);

    if(balance_flag_left && lablace_flag_right){
        int drect = right_depth - left_depth;
        if(abs(drect)<2){
            return TURE;
        }else{
            return FALSE;
        }
    }
}
  • 背包问题
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <stack>
int<stack> s;
int i;
void KNAP(int T,int w[],int n){
    int current -= w[1];
    int i = 1;
    s.push(w[0]);
    while(!s.empty() && i<n ){
        if(current - w[i] > 0){
            s.push(w[i]);
            current -= w[i];
            i++;
        }else if(current - w[i] == 0){
            s.push(w[i]);
            //符合条件 打印出栈
            printf("有这种方案：/n");
            while(!s.empty()){
                i = s.pop();
                print("%d/n",i);
                return;
            }
            else if (current - w[i] < 0){
                t = s.pop();
                current -= current+t
            }
        }
    }//while结束没有return表示没有这种方案
    print("未找到解决方案");
    return;
}

2018

  • 后序遍历树
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

void ForestPostOrderK(CSTree T, int k){
    if(T == NULL || k > n || k < 1){
        return;
    }
    CSTree p = T;
    int i;
    for(i=1;i<n;i++){
        p = p.nextsilbing;
    }//找到第k颗树
    PostOrder(p);   //后序访问
}
void PostOrder(CSTree T){   //树的后序 == 二叉树的中序
    if(T != null){
        PostOrder(T.firstchild);
        printf("%d",T.data);
        PostOrder(T.nextsilbing);
    }
}
  • k步内可到达
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

void Disgraph(MGraph G,int v ,int k){
    for(int i =0;i <G.vexnum;i++){
        vistted[i] = 0;
    }
    int tag[MAX] = {0};
    DFS(G,v,0,k,tag);
}

void DFS(MGraph G,int v int j,int k, int tag[]){
    if(j>0 && j <= k && tag[v] == 0){
        printf("%d",v);
        tag[v] = 1;
        vistted[v] = 1;
    }
    for(int w = FirstAdjVex(G,v);w>=0;w = NextAdjVex(G,w,v)){
        if(!vistted[w]){
            DFS(G,w,j+1,k,tag);    
        }
        vistted[v] = 0;
    }
}

2018-11-03 18:25 powered by Std::ke