2018年国家电网考试备考计算机之数据结构与算法

事业单位招聘网

2018年国家电网公司招聘公告预计于2017年10月末(一批)、2018年3月(二批)、2018年5月(三批)发布，届时广大考生请及时关注华图教育事业单位频道，我们会第一时间发布国家电网考试信息!更多2018年国家电网备考资料，尽在事业单位频道(http://sydw.huatu.com/)!
        计算机——数据结构与算法
        1.数据结构
        数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。记为：Data_Structure=(D,R)，其中D是数据元素的集合，R是该集合中所有元素之间的关系的有限集合。
        数据的逻辑结构：指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后件关系，而与他们在计算机中的存储位置无关。逻辑结构包括：1.集合2.线性结构3.树形结构4.图形结构
        2.数组 (Array)
        在程序设计中，为了处理方便， 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在C语言中， 数组属于构造数据类型。一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同，数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。
        数组类别：
        多维数组
        有时需要追踪记录数组中的相关信息。
        例如，为了追踪记录计算机屏幕上的每一个像素，需要引用它的 X、Y坐标。这时应该用多维数组存储值。
        可用 Visual Basic 声明多维数组。
        例如，下面的语句声明了一个过程内的 10 × 10 的二维数组。
        Static MatrixA (9,9) As Double
        可用显式下界来声明两个维数或两个维数中的任何一个：
        Static MatrixA (1 To 10,1 To 10) As Double
        可以将所有这些推广到二维以上的数组。例如：
        Dim MultiD (3,1 To 10,1 To 15)
        这个声明建立了三维数组，大小为 4 × 10 × 15。元素总数为三个维数的乘积，为 600。
        注意
        在增加数组的维数时，数组所占的存储空间会大幅度增加，所以要慎用多维数组。使用 Variant 数组时更要格外小心，因为他们需要更大的存储空间。
        用循环操作数组：
        可以用 For循环嵌套有效的处理多维数组。例如，在 MatrixA 中基于每个元素在数组中的位置为其赋值：
        Dim I As Integer,J As Integer
        Static MatrixA(1 To 10,1 To 10) As Double
        For I = 1 To 10
        For J = 1 To 10
        MatrixA (I,J) = I * 10 + J
        Next J
        Next I
        一维数组
        定义
        一维数组是最简单的数组，其逻辑结构是线性表。要使用一维数组，需经过定义、初始化和应用等过程。
        数组声明
        在数组的声明格式里，“数据类型”是声明数组元素的数据类型，可以是java语言中任意的数据类型，包括简单类型和结构类型。“数组名”是用来统一这些相同数据类型的名称，其命名规则和变量的命名规则相同。
        数组声明之后，接下来便是要分配数组所需要的内存，这时必须用运算符new，其中“个数”是告诉编译器，所声明的数组要存放多少个元素，所以new运算符是通知编译器根据括号里的个数，在内存中分配一块空间供该数组使用。利用new运算符为数组元素分配内存空间的方式称为动态分配方式。
        举例：
        int[]x; //声明名称为x的int型数组
        x=new int[10]; //x数组中包含有10个元素，并为这10个元素分配内存空间
        在声明数组时，也可以将两个语句合并成一行，格式如下：
        数据类型[]数组名= new 数据类型[个数];
        利用这种格式在声明数组的同时，也分配一块内存供数组使用。如上面的例子可以写成：
        int[]x = new int [10];
        等号左边的int[]x相当于定义了一个特殊的变量x，x的数据类型是一个对int型数组对象的引用，x就是一个数组的引用变量，其引用的数组元素个数不定。等号右边的new int[10]就是在堆内存里创建一个具有10个int型变量的数组对象。int[]x = new int [10];就是将右边的数组对象赋值给左边的数组引用变量。
       

sydwone

        
                 
        二维数组
        定义
        前面介绍的数组只有一个下标，称为一维数组， 其数组元素也称为单下标变量。在实际问题中有很多量是二维的或多维的， 因此C语言允许构造多维数组。多维数组元素有多个下标， 以标识它在数组中的位置，所以也称为多下标变量。本小节只介绍二维数组，多维数组可由二维数组类推而得到。二维数组类型说明的一般形式是：
        类型说明符数组名[常量表达式1][常量表达式2]…;
        其中常量表达式1表示第一维下标的长度，常量表达式2 表示第二维下标的长度。例如：
        int a[3][4]; 说明了一个三行四列的数组，数组名为a，其下标变量的类型为整型。该数组的下标变量共有3×4个，即：
        a[0][0],a[0][1],a[0][2],a[0][3]
        a[1][0],a[1][1],a[1][2],a[1][3]
        a[2][0],a[2][1],a[2][2],a[2][3]
        二维数组在概念上是二维的，即是说其下标在两个方向上变化， 下标变量在数组中的位置也处于一个平面之中， 而不是象一维数组只是一个向量。但是，实际的硬件存储器却是连续编址的， 也就是说存储器单元是按一维线性排列的。如何在一维存储器中存放二维数组，可有两种方式：一种是按行排列， 即放完一行之后顺次放入第二行。另一种是按列排列， 即放完一列之后再顺次放入第二列。在C语言中，二维数组是按行排列的。在如上中，按行顺次存放，先存放a[0]行，再存放a[1]行，最后存放a[2]行。每行中有四个元素也是依次存放。由于数组a说明为
        int类型，该类型占两个字节的内存空间，所以每个元素均占有两个 字节(图中每一格为一字节)。
        元素的表示方法
        二维数组的元素也称为双下标变量，其表示的形式为：数组名[下标][下标]
        其中下标应为整型常量或整型表达式。例如：a[3][4] 表示a数组三行四列的元素。
        下标变量和数组说明在形式中有些相似，但这两者具有完全不同的含义。数组说明的方括号中给出的是某一维的长度，即可取下标的最大值; 而数组元素中的下标是该元素在数组中的位置标识。前者只能是常量， 后者可以是常量，变量或表达式。
        一个学习小组有5个人，每个人有三门课的考试成绩。求全组分科的平均成绩和各科总平均成绩。
        课程 成绩姓名Math　C　DBASE
        张　80　75　92
        王　61　65　71
        李　59　63　70
        赵　85　87　90
        周　76　77　85
        可设一个二维数组a[5][3]存放五个人三门课的成绩。再设一个一维数组v[3]存放所求得各分科平均成绩，设变量l为全组各科总平均成绩。编程如下：
        void main()
        {
        int i,j,s=0,l,v[3],a[5][3];
        printf("input score\n");
        for(i=0;i
        for(j=0;j
        { scanf("%d",&a[j]);
        s=s+a[j];}
        v[i]=s/5;
        s=0;
        }
        l=(v[0]+v[1]+v[2])/3;
        printf("math:%d\nc languag:%d\ndbase:%d\n",v[0],v[1],v[2]);
        printf("total:%d\n",l);
        } for(i=0;j
        for(j=0;j
        { scanf("%d",&a[j]);
        s=s+a[j];}
        v=s/5;
        s=0;
        }
        l=(v[0]+v[1]+v[2])/3;
        程序中首先用了一个双重循环。在内循环中依次读入某一门课程的各个学生的成绩，并把这些成绩累加起来， 退出内循环后再把该累加成绩除以5送入v之中，这就是该门课程的平均成绩。外循环共循环三次，分别求出三门课各自的平均成绩并存放在v数组之中。退出外循环之后，把v[0],v[1],v[2]相加除以3即得到各科总平均成绩。最后按题意输出各个成绩。
       

sydwtwo

        
                 
        初始化
        二维数组初始化也是在类型说明时给各下标变量赋以初值。二维数组可按行分段赋值，也可按行连续赋值。例如对数组a[5][3]：
        1.按行分段赋值可写为static int a[5][3]={ {80,75,92},{61,65,71},{59,63,70},{85,87,90},{76,77,85} };
        2.按行连续赋值可写为static int a[5][3]={ 80,75,92,61,65,71,59,63,70,85,87,90,76,77,85 };
        这两种赋初值的结果是完全相同的。
        void main()
        {
        int i,j,s=0,l,v[3];
        static int a[5][3]={ {80,75,92},{61,65,71},{59,63,70},
        {85,87,90},{76,77,85} };
        for(i=0;i
        { for(j=0;j
        s=s+a[j];
        v=s/5;
        s=0;
        }
        l=(v[0]+v[1]+v[2])/3;
        printf("math:%d\nc languag:%d\ndbase:%d\n",v[0],v[1],v[2]);
        printf("total:%d\n",l);
        }
        初始化的额外说明
        对于二维数组初始化赋值还有以下说明：
        1.可以只对部分元素赋初值，未赋初值的元素自动取0值。
        例如：static int a[3][3]={,,}; 是对每一行的第一列元素赋值，未赋值的元素取0值。赋值后各元素的值为：1 0 02 0 03 0 0
        static int a [3][3]={{0,1},{0,0,2},}; 赋值后的元素值为 0 1 00 0 23 0 0
        2.如对全部元素赋初值，则第一维的长度可以不给出。
        例如：static int a[3][3]={1,2,3,4,5,6,7,8,9}; 可以写为：static int a[][3]={1,2,3,4,5,6,7,8,9};
        分解
        数组是一种构造类型的数据。二维数组可以看作是由一维数组的嵌套而构成的。设一维数组的每个元素都又是一个数组， 就组成了二维数组。当然，前提是各元素类型必须相同。
        根据这样的分析，一个二维数组也可以分解为多个一维数组。C语言允许这种分解有二维数组a[3][4]，可分解为三个一维数组，其数组名分别为a[0],a[1],a[2]。对这三个一维数组不需另作说明即可使用。这三个一维数组都有4个元素，例如：一维数组a[0]的元素为a[0][0],a[0][1],a[0][2],a[0][3]。最后必须强调的是，a[0],a[1],a[2]不能当作下标变量使用，它们是数组名，不是一个单纯的下标变量。
        字符数组
        用来存放字符量的数组称为字符数组。
        字符数组类型说明的形式与前面介绍的数值数组相同。例如：char c[10]; 由于字符型和整型通用，也可以定义为int c[10]但这时每个数组元素占2个字节的内存单元。
        字符数组也可以是二维或多维数组，例如：char c[5][10];即为二维字符数组。
        字符数组也允许在类型说明时作初始化赋值。例如：static char c[10]={`c`,` `,`p`,`r`,o`,g`,r`,`a`,`m`};赋值后各元素的值为：数组C c[0]c[1]c[2]c[3]c[4]c [5]c[6]c[7]c[8]c[9]其中c[9]未赋值，由系统自动赋予0值。
        当对全体元素赋初值时也可以省去长度说明。例如：static char c[]={`c`,` `,`p`,`r`,`o`,`g`,`r`,`a`,`m`};这时C数组的长度自动定为9。
        main()
        {
        int i,j;
        char a[][5]={{'B','A','S','I','C',},{'d','B','A','S','E'}};
        for(i=0;i
        {
        for(j=0;j
        printf("%c",a[j]);
        printf("\n");
        }
        }
        本例的二维字符数组由于在初始化时全部元素都赋以初值， 因此一维下标的长度可以不加以说明。字符串在C语言中没有专门的字符串变量， 通常用一个字符数组来存放一个字符串。在2.1.4节介绍字符串常量时，已说明字符串总是以'\0'作为串的结束符。因此当把一个字符串存入一个数组时， 也把结束符'\0'存入数组，并以此作为该字符串是否结束的标志。有了'\0'标志后，就不必再用字符数组的长度来判断字符串的长度了。
       

sydwsix

        
                 
        C语言允许用字符串的方式对数组作初始化赋值。例如：
        static char c[]={'c',' ','p','r','o','g','r','a','m'}; 可写为：
        static char c[]={"C program"}; 或去掉{}写为：
        static char c[]="C program";
        用字符串方式赋值比用字符逐个赋值要多占一个字节， 用于存放字符串结束标志'\0'。上面的数组c在内存中的实际存放情况为：C program'\0'是由C编译系统自动加上的。由于采用了'\0'标志，所以在用字符串赋初值时一般无须指定数组的长度， 而由系统自行处理。在采用字符串方式后，字符数组的输入输出将变得简单方便。除了上述用字符串赋初值的办法外，还可用scanf函数和printf函数一次性输入输出一个字符数组中的字符串， 而不必使用循环语句逐个地输入输出每个字符。
        void main()
        {
        static char c[]="BASIC\ndBASE";
        printf("%s\n",c);
        } printf("%s\n",c);
        注意在本例的printf函数中，使用的格式字符串为“%s”， 表示输出的是一个字符串。而在输出表列中给出数组名则可。不能写为：printf("%s",c[]);
        void main()
        {
        char st[15];
        printf("input string:\n");
        scanf("%s",st);
        printf("%s\n",st);
        } char st[15];
        本例中由于定义数组长度为15， 因此输入的字符串长度必须小于15，以留出一个字节用于存放字符串结束标志'\0'。应该说明的是，对一个字符数组，如果不作初始化赋值，则必须说明数组长度。还应该特别注意的是，当用scanf函数输入字符串时，字符串中不能含有空格，否则将以空格作为串的结束符。例如运行例4.8，当输入的字符串中含有空格时，运行情况为：input string:this is a book this 从输出结果可以看出空格以后的字符都未能输出。为了避免这种情况，可多设几个字符数组分段存放含空格的串。程序可改写如下：
        Lesson
        void main()
        {
        char st1[6],st2[6],st3[6],st4[6];
        printf("input string:\n");
        scanf("%s%s%s%s",st1,st2,st3,st4);
        printf("%s %s %s %s\n",st1,st2,st3,st4);
        }
        本程序分别设了四个数组， 输入的一行字符的空格分段分别装入四个数组。然后分别输出这四个数组中的字符串。在前面介绍过，scanf的各输入项必须以地址方式出现，如 &a,&b等。但在例4.8中却是以数组名方式出现的，这是为什么呢?这是由于在C语言中规定，数组名就代表了该数组的首地址。整个数组是以首地址开头的一块连续的内存单元。如有字符数组char c[10]，在内存可表示如图4.2。设数组c的首地址为2000，也就是说c[0]单元地址为2000。则数组名c就代表这个首地址。因此在c前面不能再加地址运算符&。如写作scanf("%s",&c);则是错误的。在执行函数printf("%s",c) 时，按数组名c找到首地址，然后逐个输出数组中各个字符直到遇到字符串终止标志'\0'为止。
        3.队列 (Queue)
        一种特殊的线性表，它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列是按照“先进先出”或“后进后出”的原则组织数据的。队列中没有元素时，称为空队列。
        顺序队列
        空队时指针(下标)front和rear在一起都指向队前方，当有元素进队，则rear后移;有元
        素出队，则front后移，最后，开始时分配给队的前端不再被利用。
        为了充分利用队列，顺序队列总是做成一个逻辑上的循环队列。
       

20140927xunhuan08.png

       

sydwfour

        
                 
        注意：空队时rear等于front，满队时必须空一个位置。
        顺序循环队列类模板
        templateclass Queue
        {
        int rear,front; //队尾与队头下标
        T *elements; //存放队列元素的容器
        int maxSize; //队列最多可容纳元素个数+1
        public:
        Queue(int ms=18);
        ~Queue()
        {
        delete[] elements;
        }
        bool IsEmpty() const //判队空
        {
        return front==rear;
        }
        bool IsFull() const //判队满
        {
        return (rear+1)%maxSize==front;
        }
        int Length() const //求队中元素数，注意求余算法
        {
        return (rear-front+maxSize)%maxSize;
        }
        void EnQue(const T &data); //进队
        T DeQue(); //出队
        T GetFront(); //取队头数据
        void MakeEmpty()//队置空(初始态)
        {
        front=rear=0;
        }
        };
        4.链表 (Linked List)
        是一种物理存储单元上非连续、非顺序的存储结构，它既可以表示线性结构，也可以用于表示非线性结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
        基本操作(pascal语言)
        建立
        第一行读入n，表示n个数
        第二行包括n个数
        以链表的形式存储输出这些数
       

sydwthree

        
                 
       

201409272008.png

       

201409274408.png

        在以z为头的链表中搜索第一个n，如果找到则删去，返回值为1，否则返回0
       

201409271608.png

        查找
        类似于删除，只需要找到不删即可
       

sydwsix

        
                 
        插入
        插入，在以zz为头的链表第w个的前面插入nn元素，函数返回值正常是0，如果w超过了链表的长度，函数返回链表的长度
       

20140927changdu08.png

        5.树 (Tree)
        数据结构中为了存储和查找的方便，用各种树结构来存储文件。树结构包括：二叉查找树(二叉排序树)、平衡二叉树(AVL树)、红黑树、B-树、B+树、字典树(trie树)、后缀树、广义后缀树。各种树的表示方法、特点及各自的用途如下：
        1、二叉查找树(二叉排序树)
       

tua08.png

        (图a)
        二叉查找树是一种动态查找表(图a)，具有这些性质：
        (1)若它的左子树不为空，则左子树上的所有节点的值都小于它的根节点的值;
        (2)若它的右子树不为空，则右子树上所有节点的值都大于它的根节点的值;
        (3)其他的左右子树也分别为二叉查找树;
        (4)二叉查找树是动态查找表，在查找的过程中可见添加和删除相应的元素，在这些操作中需要保持二叉查找树的以上性质。
        2、平衡二叉树(AVL树)
       

tub08.png

        (图b)
        含有相同节点的二叉查找树可以有不同的形态，而二叉查找树的平均查找长度与树的深度有关，所以需要找出一个查找平均长度最小的一棵，那就是平衡二叉树(图b)，具有以下性质：
        (1)要么是棵空树，要么其根节点左右子树的深度之差的绝对值不超过1;
        (2)其左右子树也都是平衡二叉树;
        (3)二叉树节点的平衡因子定义为该节点的左子树的深度减去右子树的深度。则平衡二叉树的所有节点的平衡因子只可能是-1,0,1。
       

sydwsix

        
                 
        3、红黑树
       

tuc08.png

        (图c)
        红黑树是一种自平衡二叉树，在平衡二叉树的基础上每个节点又增加了一个颜色的属性，节点的颜色只能是红色或黑色。具有以下性质：
        (1)根节点只能是黑色;
        (2)红黑树中所有的叶子节点后面再接上左右两个空节点，这样可以保持算法的一致性，而且所有的空节点都是黑色;
        (3)其他的节点要么是红色，要么是黑色，红色节点的父节点和左右孩子节点都是黑色，及黑红相间;
        (4)在任何一棵子树中，从根节点向下走到空节点的路径上所经过的黑节点的数目相同，从而保证了是一个平衡二叉树。
        4、B-树
       

tud08.png

        图d)
        B-树是一种平衡多路查找树，它在文件系统中很有用。一棵m阶B-树(图d为4阶B-树)，具有下列性质：
        (1)树中每个节点至多有m棵子树;
        (2)若根节点不是叶子节点，则至少有2棵子树;
       

20140927kezishu08.png

        (3)除根节点之外的所有非终端节点至少有棵子树;
        (4)每个节点中的信息结构为(A0,K1,A1,K2......Kn,An)，其中n表示关键字个数，Ki为关键字，Ai为指针;
        (5)所有的叶子节点都出现在同一层次上，且不带任何信息，也是为了保持算法的一致性。
       

sydwone

        
                 
        5、B+树
       

tue08.png

        (图e)
        B+数是B-树的一种变形，它与B-树的差别在于(图e为3阶B+树)：
        (1)有n棵子树的节点含有n个关键字;
        (2)所有的叶子节点包含了全部关键字的信息，及指向这些关键字记录的指针，且叶子节点本身按关键字大小自小到大顺序链接;
        (3)所有非终端节点可以看成是索引部分，节点中仅含有其子树(根节点)中最大(或最小)关键字，所有B+树更像一个索引顺序表;
        (4)对B+树进行查找运算，一是从最小关键字起进行顺序查找，二是从根节点开始，进行随机查找。
        6、字典树(trie树)
       

tuf08.png

        (图f)
        字典树是一种以树形结构保存大量字符串。以便于字符串的统计和查找，经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。具有以下特点(图f)：
        (1)根节点为空;
        (2)除根节点外，每个节点包含一个字符;
        (3)从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
        (4)每个字符串在建立字典树的过程中都要加上一个区分的结束符，避免某个短字符串正好是某个长字符串的前缀而淹没。
        7、后缀树
        后缀树则是一个字符串的所有后缀组成的字典树。具体内容再前几章已讲过。
        8、广义后缀树
        广义后缀树是好几个字符串的的所有后缀组成的字典树，同样每个字符串的所有后缀都具有一个相同的结束符，不同字符串的结束符不同。
        6.图 (Graph)
        图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。
        1.图的存储结构
       

sydwone

        
                 
        1.1 邻接矩阵
        图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(邻接矩阵)存储图中的边或弧的信息。
        设图G有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：
       

20140927dingyi08.png

        看一个实例，下图左就是一个无向图。
       

20140927wuxiang08.png

        从上面可以看出，无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴，右上角的元和左下角相对应的元全都是相等的。
        从这个矩阵中，很容易知道图中的信息。
        (1)要判断任意两顶点是否有边无边就很容易了;
        (2)要知道某个顶点的度，其实就是这个顶点vi在邻接矩阵中第i行或(第i列)的元素之和;
        (3)求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍，arc[j]为1就是邻接点;
        而有向图讲究入度和出度，顶点vi的入度为1，正好是第i列各数之和。顶点vi的出度为2，即第i行的各数之和。
        若图G是网图，有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：
       

20140927fanzhi08.png

        这里的wij表示(vi,vj)上的权值。无穷大表示一个计算机允许的、大于所有边上权值的值，也就是一个不可能的极限值。下面左图就是一个有向网图，右图就是它的邻接矩阵
       

20140927dingdian08.png

        。
        那么邻接矩阵是如何实现图的创建的呢?代码如下。