工商自考-数据结构复习资料.doc  （行考）

C#语言中，数组的基类是Array。    栈是一种 线性结构。 在C#语言中，System.Collections命名空间中定义了队列类Queue。 链表结构中的每个节点都是由两部分组成的，即一个用来存储数据一个用来存储下一个节点         的引用。 C#语言中提供了两种类分别用来表示栈和队列，它们是Stack类和Queue类         。 StringBuilder类表达的值为可变字符序列的类似字符串的对象。 图有邻接矩阵、邻接表等存储结构。 遍历图有深度优先搜索遍历、广度优先搜索遍历等方法。 ArrayList类在.Net框架的System.Collections命名空间中 查找指定字符的方法是substring。 C#中提供了两种操作字符串的方式，分别是String和 StringBuilder类。 假设一个栈里面没有任何元素存在，我们称之为空栈。 常用的查找算法有顺序查找和折半查找。 在插入和选择排序中，若初始数据基本正序，则选用插入；若初始数据基本反序，则选用选择。 Length表示数组所有维数内元素的总数量。 Add方法用于向ArrayList中添加一个元素。 希尔排序比较适合大数据集合。 在实现插入排序过程中，一般通过二层来实现。 二叉树属于非线性结构。 栈的基础操作一般包括：判断栈是否为空、判断栈是否已满、进栈和退栈。 \n转义字符表示的是换行。 对于字典数据类型而言，它是通过键去匹配值的。 在ArrayList类中，用于返回指定数据项首次出现的索引的方法是IndexOf方法。 面向对象思想是封装、继承及多态。 时间复杂度、空间复杂度是用来描述算法性能的。 常见的图结构包括无向图和有向图。 多维数组就是多个一维数组组成的。 C#语言中字符串定义为字符的序列，它可以是字母、数字和其他符号的组合。 当栈中元素的个数n=0时，则称之为空栈。 队列结构：队列(queue)也是一种特殊的线性表，但是它允许在表的一端进行插入操作，而在表的另一端进行删除操作。一般允许删除的一端称之为队头，允许插入的一端则称之为队尾。不含任何元素的空列表则称为空队列。 归并排序算法：将数据初始序列看成是由n个长度为1的已排序子序列组成。反复将两个子序列合并成一个已排序的序列。重复直到合并成一个序列时，排序完成。 正则表达式：正则表达式中还有一个重要性的概念就是元字符，它是一种特殊的字符，用于表示重复、替换或者分组。 参数数组：同其它变量一样，数组也可以作函数的参数。数组元素只能作函数实参，且同其它变量的用法没有区别。 关键字是指数据序列（或记录）中某个数据项的值，用以标识一个数据元素（或记录）。 栈又被称为后进先出(Last In First Out)的线性表，简称LIFO线性表。 散列是一种非常有用的数据存储结构，它可以迅速的操作数据(插入、查找等)。散列采用的数据结构我们通常称之为散列表。 正则表达式：正则表达式中还有一个重要性的概念就是元字符，它是一种特殊的字符，用于表示重复、替换或者分组。 关键字：是指数据序列（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。 冒泡排序：排序算法的得名是由于数值“像气泡一样”从集合的一端浮动到另一端。假如现在要把一列数据按照从小到大的方式进行排序，那么较大的数值浮动到数列的右边，较小的数值浮动到数列的左边。这种冒泡的效果可以通过多次遍历集合，并且比较相邻元素的数值，根据数值大小进行位置交换。 栈(stack)，它是限定在表的一端进行插入、删除操作的特殊线性表，通常把栈所操作的一端称之为栈顶(top)，另一端则称之为栈底(bottom)。不含任何元素的空列表则称为空栈。 简述插入排序实现原理及执行过程? 每一数据比较都将一个待排序的数据元素，按照其关键字的大小，插入到已经排序的数据序列中，使插入后的数据序列仍然是有序的，直到全部数据序列元素插入完毕为止。 定义一个多维数组，该数组用于代表学生成绩信息，且数组中每位同学有4科成绩，定义该结构并算出每位学员的平均分数？ int [,] stuGrades = new[,]             {                {0,75,85,79,93},                {1,89,90,87,79},                {2,70,83,68,90},                {3,78,96,84,73},                {4,80,70,65,84}             };             //学生平均分             float averageGrade = 0.0f;             int last_stu = stuGrades.GetUpperBound(0);             int last_grade = stuGrades.GetUpperBound(1);             int intTotal;               for (int numRow = 0; numRow <= last_stu; numRow++)             {                 intTotal = 0;                 for (int numColumn = 0; numColumn <= last_grade; numColumn++)                 {                     intTotal += stuGrades[numRow, numColumn];                 }                 averageGrade = intTotal / last_grade;                 Console.WriteLine(string.Format("The Average Score of {0} is {1} ！",numRow,averageGrade));             } 数组结构与链表结构的区别是什么？链表结构优势有哪些？ 对于数组而言，有序数组对于查找效率好高很多。但是链表结构的执行效率更高。 简述折半查找算法的实现原理及执行流程？ 假定元素按升序排列，对于给定值k，从表的中间位置开始比较，如果k等于当前数据元素的关键字，则查找成功。若k小于当前数据元素的关键字，则在表的前半部分继续查找；反之，则在表的后半部分继续查找。依次重复进行，直至获得查找成功或不成功的结果。 定义一个字符串数组，分别通过for及foreach语句进行循环遍历输出？ string[] stuInfo = new String []{ "武大","华科","理工"}; //使用for语句循环遍历数组             for (int temp = 0; temp < stuInfo.Length; temp++)             {                 Console.WriteLine(string.Format("The Value is {0}！", stuInfo[temp]));             }             Console.WriteLine("".PadLeft(20,'='));             //使用foreach语句循环遍历数组             foreach (string strTemp in stuInfo)             {                 Console.WriteLine(string.Format("The Value of stuInfo is {0}！",strTemp));             } 简述队列的内部组成结构？ 队列同现实生活中到食堂排队买饭相仿，新来的成员总是要加入到队伍的尾部，每次离开的成员总是处于队头的。所以，与栈结构不一样，队列操作时是按照先进先出的原则进行的。因此，队列又被称为先进先出(First In First Out)的线性表，简称FIFO线性表。 选择排序：它是从数组的开始处开始，把第一个元素的值与数组中其他元素逐个进行比较，然后把最小的元素放置到第0个位置上，接着再从第1个元素开始再次进行如上操作，直到条件终止。 简答叙述散列结构实现的原理？ 散列的思想是把自身单元内的每一个键都存储到数组内，但是，由于键的数量是有可能无限多的，而数组的大小的范围是有限的，所以，散列函数会尽可能平均地分不到数组的单元内。 简述插入排序实现原理及执行过程? 每一数据比较都将一个待排序的数据元素，按照其关键字的大小，插入到已经排序的数据序列中，使插入后的数据序列仍然是有序的，直到全部数据序列元素插入完毕为止。 简述二叉树的存储结构? 二叉树的存储结构常见的有顺序存储结构和链式存储结构，二叉树的顺序存储结构适用于完全二叉树，对完全二叉树进行排序编号，将编号为i的结点存放在数组下标为i-1的位置上。 通过现实生活场景描述栈和队列结构？ 队列同现实生活中到食堂排队买饭相仿，新来的成员总是要加入到队伍的尾部，每次离开的成员总是处于队头的。所以，与栈结构不一样，队列操作时是按照先进先出的原则进行的。 论述Hashtable是如何避免冲突的？ Hashtable类用来避免冲突的方法就是桶的思想。桶其实就是具有相同散列代码对象的虚拟组合。如果两个键具有相同的散列代码，就把这两个键放在同一个桶内。否则，把每一个具有唯一散列代码的键放在其对应的桶内。 其中，用于在一个Hashtable对象内桶的数量被称之为负载系统。它是元素与桶数量之间的比率值。其初始值为1.0。 如何对基础排序算法进行时间排序比较？ 定义一个类，该类里面通过时间函数分别对基础排序算法的冒泡、排序及插入排序进行比较，比较过程中通过循环增加比较项，以此来得到比较结构。 当我们利用string类定义一个对象后，如果对它进行修改操作，在这个过程中，会产生新的字符串吗？请阐明原理？ 当我们利用string类定义一个对象后，如果对它进行修改操作，在这个过程中，会产生新的字符串，因为字符串的默认操作情况下，会通过产生新的字符串来代表操作后的字符串值。 可变字符串是如何确保在操作字符串的过程中可变的？请详细描述。 StringBuilder类表达的值为可变字符序列的类似字符串的对象。之所以说它定义的值是可变的，是因为在通过追加、移除、替换或插入字符等操作后而创建的新字符串我们可以继续对它进行修改。StringBuilder 的容量是实例在任何给定时间可存储的最大字符数，并且大于或等于实例值的字符串表示形式的长度。容量可通过 Capacity 属性来增加或减少。 编写一个IPAddress类，该类用于存储IP地址信息，其中IP地址按照降序顺序排列。 定义一个IPAddress类，类里面包含存储IP的属性和操作方法，字典类型Hahtable的每一个数据项保存一个IPAddress对象即可。 简述二叉树的概念？ 二叉树是n个结点组成的有限集合。n=0时称为空二叉树；n>0时，二叉树由一个根结点和两棵互不相交的、分别称为左子树和右子树的子二叉树构成。 什么是生成树？ 如果图T是无向图G的生成子图，且T是树，则图T称为图G的生成树。那么，图G的生成树T包含G中的所有结点和尽可能少的边。任意一个连通图都至少有一棵生成树。 什么是最小生成树？ 设G是一个连通的带权图，w(e)为边e上的权，T为G的生成树，T中各边权之和称为生成树T的权，也称为生成树的代价。权最小的生成树称为最小生成树或最小代价生成树。 什么是归并排序算法？ 将数据初始序列看成是由n个长度为1的已排序子序列组成。反复将两个子序列合并成一个已排序的序列。重复直到合并成一个序列时，排序完成。