发布于 

数据结构试题分析

作者序

  题目均来自于往年试卷，给出的代码都能够编译通过。

例题一：哈希表的使用

  题面： 假设线性表采用顺序存储结构，试实现函数int DelRepeat()，用以删除所有重复元素，并返回删除元素的个数。要求算法的时间复杂度为O(n)O(n)。线性表结构定义如下：

1
2
3
4
5
6
7
8
9
10
11
class seqList{
    private:
    int* data;//保存的元素数组
    int currentLength;//元素个数
    int noData;//数据中不存在的元素

    public:
    int DelRepeat(){
        //add your code here
    }
};

  代码实现如下，注意：测试代码未给出，请读者自行构造。

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class seqList{
    private:
    int* data;//保存的元素数组
    int currentLength;//元素个数
    int noData;//数据中不存在的元素

    public:
    seqList(int n){//构造函数
        currentLength=n;//元素个数
        data=new int[n];
        cout<<"input data:"<<endl;
        for(int i=0;i<n;++i){//获取元素值
            cin>>data[i];
        }
    }

    void display(){//展示数组元素
        cout<<"the data are:"<<endl;
        for(int i=0;i<currentLength;++i){
            cout<<data[i]<<"\t";
        }
        cout<<endl;
    }

    int delRepeat(int n){//删除重复元素
        noData=n;//标记输入数据中不存在的元素
        bool* status=new bool[currentLength];
        for(int i=0;i<currentLength;++i){//创建判断元素，为真则该位置的数字出现过
            status[i]=false;
        }
        int* hashtable=new int[2*currentLength];//创建哈希表
        for(int i=0;i<2*currentLength;++i){//哈希表初始化
            hashtable[i]=noData;
        }

        for(int i=0;i<currentLength;++i){
            int pos=data[i]%(2*currentLength);//获得哈希值

            while(hashtable[pos]!=noData&&hashtable[pos]!=data[i]) (++pos)%(2*currentLength);//定位到第一个可以插入的位置

            if(hashtable[pos]==data[i]){
                status[i]=true;//如果有该元素，标记为待删除元素
            }
            else{
                hashtable[pos]=data[i];//没有该元素，插入该元素
            }

        }//end for

        int i=0,j=0;
        int newLength=0;
        int oldLength=currentLength;
        int* tmp=new int[currentLength];//装载没被删去的元素
        for(int i=0;i<currentLength;++i){
            if(!status[i]){//如果判断数组对应位置为假，保留该数字
                tmp[j]=data[i];
                ++j;
                newLength++;
            }
        }
        delete[] data;//内存管理
        data=tmp;//数据内容更新
        delete[] hashtable;
        currentLength=newLength;//更新数组长度

        return (oldLength-currentLength);
    }
};

  总结： 对于需要反复回溯已遍历元素中某个元素出现与否的，哈希表是一个很好的解决方式，可以减少O(n)O(n)的算法复杂度。注意哈希表的重点：哈希函数和冲突解决。

例题二：二叉树

  给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。请完善下列算法，实现将上述两个二叉树合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。注意：合并后的二叉树中结点允许直接使用这两个二叉树上的结点。给出二叉树的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class binaryTree{
    private:
    struct node{//二叉树的节点类
        int value;
        node* left;
        node* right;
        node(int val){//构造函数
            value=val;
            left=NULL;
            right=NULL;
        }
    };
    node* root;//二叉树的根节点
    
    public:
    node* mergeTrees(node* t1, node* t2){//合并二树
        //add your code here
    }
};

  想法是：合并二树可以看成三个过程：合并根节点、递归调用合并左右子树。因此，合并二树的操作并不难，只需要注意递归跳出的条件：其中一棵树为空树即可。为了完成代码的检查，我们还需要复习一遍二叉树的构建和层次遍历的知识点。以下代码包含了测试代码，可以直接运行。

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<iostream>
#include<queue>
using namespace std;

class binaryTree{
    private:
    struct node{//二叉树的节点类
        int value;
        node* left;
        node* right;
        node(int val){//构造函数
            value=val;
            left=NULL;
            right=NULL;
        }
    };
    node* root;//二叉树的根节点
    
    public:
    binaryTree(){//基于层次遍历的构造函数
        int val;
        int lval;
        int rval;
        cout<<"input the root:";
        cin>>val;
        cout<<endl;
        root=new node(val);
        queue<node*> que1;
        que1.push(root);
        while(!que1.empty()){
            node* tmp=que1.front();
            que1.pop();
            cout<<"input the two children of the given node "<<tmp->value<<":";
            cin>>lval>>rval;
            cout<<endl;
            if(lval){
                tmp->left=new node(lval);
                que1.push(tmp->left);
            }
            if(rval){
                tmp->right=new node(rval);
                que1.push(tmp->right);
            }
        }
        cout<<"binarytree has been built!"<<endl;
    }

    binaryTree(node* r){//给定根节点的构造函数
        root=r;
    }

    void display(){//层次遍历
        queue<node> que1;
        que1.push(*root);
        while(!que1.empty()){
            node tmp=que1.front();
            que1.pop();
            cout<<tmp.value<<" ";
            if(tmp.left){
                que1.push(*(tmp.left));
            }
            if(tmp.right){
                que1.push(*(tmp.right));
            }
        }
        cout<<"display completed!"<<endl;
    }

    node* findRoot(){//返回二叉树根节点的位置
        return root;
    }

    node* mergeTrees(node* t1, node* t2){//合并二树
        if(!t1) return t2;//递归跳出条件，即其中一棵树是空树
        if(!t2) return t1;

        node* t3=new node(t1->value+t2->value);
        t3->left=mergeTrees(t1->left,t2->left);//假定该函数能够完成合并二树的操作，只需要对左右子树递归调用
        t3->right=mergeTrees(t1->right,t2->right);

        return t3;

    }
};

int main(){
    binaryTree tree1;
    tree1.display();
    binaryTree tree2;
    tree2.display();//构建两棵树并展示之
    binaryTree tree3(tree1.mergeTrees(tree1.findRoot(),tree2.findRoot()));//合并子树
    tree3.display();

    return 0;
}

例题三：拓扑排序

  题面： 学生需要修读完所有的课程才能毕业，这些课程之间有先导关系（比如要修读数据结构，必须先修读程序设计思想方法）。假设任意一门课程可以在任何一个学期给满足条件的学生选修，且学生每个学期可以选修的课程数不限。先给出一些课程与课程之间的关系，求能够修完所有课程的最少学期数。

  输入格式： 第1行：n m //正整数n ，代表课程的数量。非负整数m代表要给出几个先导关系。第2行到第1+m行: a b //每行两个整数：代表要选修编号为a的课程，必须先修读编号为b的课程。

  输出格式： 一个整数，即修完所有课程的最少学期数。

  思路： 本题可以参考拓扑排序的方式，即：选取入度为零的点，将其移除，然后更新有向图；再移除入度为零的点，如此循环。实现的代码如下，主函数也已经给出，且能够编译通过。

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<iostream>
#include<queue>
using namespace std;

class adjListGraph{
    private:
    struct edgeNode{
        int end;
        edgeNode* next;
        edgeNode(int e,edgeNode* n=NULL){
            end=e;
            next=n;
        }
    };

    struct verNode{
        int ver;
        edgeNode* head;

        verNode(int val=0){
            ver=val;
            head=NULL;
        }
    };

    verNode* verList;
    int Vers;
    int* inDegree;//入度统计数组

    public:
    adjListGraph(int vSize){//构造函数
        Vers=vSize;
        verList=new verNode[Vers+1];
        inDegree=new int[Vers+1];
        for(int i=1;i<=Vers;++i){
            verList[i].ver=i;
            inDegree[i]=0;
        }
    }

    void insert(int end,int in){
        verList[in].head=new edgeNode(end,verList[in].head);
        inDegree[end]++;//入度增加
    }

    int topSort(){
        int counter=0;
        int remain=Vers;//剩余未被删除的元素个数，用于判断循环结束
        int current;//当前将要出队的元素
        queue<verNode> que1;
        
        while(remain!=0){
            for(int i=1;i<=Vers;++i){
                if(inDegree[i]==0){
                    que1.push(verList[i]);//入度为零的点入队
                }
            }//end for
            while(!que1.empty()){
                current=que1.front().ver;
                que1.pop();
                edgeNode*p=verList[current].head;
                while(p){
                    inDegree[p->end]--;//该出队元素所指向的元素入度自减
                    p=p->next;
                }
                remain--;
                inDegree[current]=-1;//已修完的课在下一次循环不需要被读取
            }
            counter++;//完成后计数器增加
        }

        return counter;
    }
};

int main(){
    int n,m;//课程数量、先导关系
    cin>>n>>m;
    adjListGraph graph(n);
    for(int i=1;i<=m;++i){
        int a,b;
        cin>>a>>b;
        graph.insert(a,b);
    }

    cout<<graph.topSort()<<endl;

    return 0;
}

  上述程序中指定队列的原因是，为了区分出每一学期修了多少门课。每一个学期进行一次统一的入队操作，而后出队直至队空为止。

许可协议

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。

分享文章
快来参与讨论吧