数据结构与算法复习资料.doc

数据结构与算法课程考试复习资料一、 填空题(A卷)ArrayList类在.Net框架的 System.Collections 命名空间中。(A、B卷)C#语言中，数组的基类是 Array 。(A、B卷)C#语言中提供了两种类分别用来表示栈和队列，它们是 Stack类 和 Queue类 。 (A卷)查找指定字符的方法是 substring 。(A卷)C#中提供了两种操作字符串的方式，分别是String和 StringBuilder 类。(A卷)常用的查找算法有 顺序查找 和 折半查找 。(A卷)假设一个栈里面没有任何元素存在，我们称之为 空栈 。 (A卷)在插入和选择排序中，若初始数据基本正序，则选用 插入 ；若初始数据基本反序，则选用 选择 。 (B卷)栈是一种 线性 结构。(B卷)可变字符串默认的容量大小是 16 。(B卷)在C#语言中， System.Collections 命名空间中定义了队列类Queue。(B卷)链表结构中的每个节点都是由两部分组成的，即一个用来 存储数据 一个用来存储 下一个节点 的引用。 (B卷) StringBuilder类 表达的值为可变字符序列的类似字符串的对象。(A、B卷)负载系统指标比较重要，对应Hashtable而言，负载系数 越小 ，其性能 越好 。(A、B卷)图有 邻接矩阵 、 邻接表 等存储结构。(B卷)遍历图有 深度优先搜索遍历 、 广度优先搜索遍历 等方法。 单选题(A、B卷)下列选项中，哪个选项表示数组所有维数内元素的总数量?（ A ）A、Length B、Count C、GetLength D、Rank(A、B卷)下列哪个方法是不属于ArrayList类的？ ( D )A、Add B、Capacity C、Count D、Length(A、B卷)下列哪个方法用于向ArrayList中添加一个元素？( A ) A、Add B、Insert C、AddRange D、Item(A、B卷)下列排序方法中，哪种排序效率最高？( A )A、选择排序 B、冒泡排序 C、插入排序 D、归并排序(A、B卷)下列排序算法中，哪一种排序比较适合大数据集合？( D )A、选择排序 B、冒泡排序 C、插入排序 D、希尔排序(A、B卷)在实现插入排序过程中，一般通过( B )循环来实现？ A、一层 B、二层 C、三层 D、四层(A、B卷)下列哪个结构属于非线性结构？（ D ） A、队列 B、栈 C、数组 D、二叉树(A卷)下列哪些不属于栈的基础操作？（ D ） A、判断栈是否为空 B、判断栈是否已满 C、退栈 D、删除栈(A、B卷)下列哪个转义字符表示的是换行？（ A ） A、n B、t C、r D、hr(A、B卷)下列哪个属性表示的是字符串的长度？（ A ）A、Length B、Capatity C、Size D、Max(A、B卷)下列哪些类不能使用于字符串操作？（ D ） A、string B、stringBulider C、RegEx D、Sqlconnection(A卷)下列哪些方法不属于常用的字典类型操作方法？（ A ） A、New方法添加新数据 B、Item方法取值 C、Remove方法移除值 D、Clear方法清除值(A卷)对于字典数据类型而言，它是通过( )去匹配值的？（ A ） A、键 B、索引 C、序号 D、默认顺序(A卷)在C#底层框架中，提供了一个按照分类顺序且基于键值对的形式存储数据的数据结构( D )。 A、string B、stringBulider C、RegEx D、SortedList(A卷)散列结构不主要应用于下列哪些场景？（ B ） A、快速的插入数据 B、快速的查找数据 C、快速的删除数据 D、快速清除数据(A卷)下列哪种实例化Hashtable类是错误的？（ D ） A、Hashtable ht1 = new Hashtable(); B、Hashtable ht2 = new Hashtable(50); C、Hashtable ht3 = new Hashtable(20, 2.0f); D、Hashtable ht4 = new Hashtable(“1”,”AA”);(A卷)链表是被称为节点类的对象集合的群集。每一个链表节点通过一个引用链接到列表内的后继节点。在这些节点中需要包含哪些部分？（ C ） A、数据和索引 B、数据和超链接 C、保存数据及指向下一节点的属性 D、数据和数据变量(A卷)下列哪些是不属于链表的改进方案? （ C ） A、单向链表 B、双向链表 C、循环链表 D、递归链表 (A卷)非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足？（ D ） A、所有的结点无左孩子 B、所有的结点无右孩子 C、是任意一二叉树 D、只有一个叶子结点 (A、B卷)在ArrayList类中，用于返回指定数据项首次出现的索引的方法是？ ( B )A、Insert方法 B、IndexOf方法 C、RemoveAt方法 D、Reverse方法(B卷)下列哪些符号不能表示正则表达式数量词？( D ) A、+ B、? C、* D、&(B卷)下列排序算法中，哪一种排序比较适合大数据集合？( D ) A、选择排序 B、冒泡排序 C、插入排序 D、希尔排序 (B卷)对于集合5,3,7,4,6,8,2,1，进行第一趟排序后变成3,5,4,6,7,2,1,8,请问是通过下列哪个排序算法实现的？（ B ） A、选择排序 B、冒泡排序 C、插入排序 D、归并排序 (B卷)下列哪些类不能使用于字符串操作？（ D ） A、string B、stringBulider C、RegEx D、Sqlconnection (B卷)下面哪个选项表示的是空字符串？（ C ） A、” B、” ” C、string.Empty D、Null (B卷)下列代码向Hashtable中添加了几个值? Hashtable ht = new Hashtable(30); ht.Add(empName, angus); ht.Add(empAge,27); ht.Add(empSalary, 8000);（ B ） A、30 B、3 C、2; D、4(B卷)下列哪个特性不是属于面向对象思想?（ D ） A、封装 B、继承 C、多态 D、实例化 (B卷)利用二叉链表存储树，则根结点的右指向是?（ B ） A、指向最左节点 B、指向最右节点 C、空 D、非空(B卷)对于序列15，9，7，8，20，-1，4进行排序，进行一趟后数据的排列变为4，9，-1，8，20，7，15；则采用的是（ D ）排序。 A、选择 B、快速 C、希尔 D、冒泡 多选题(A卷)下列哪个方法是属于ArrayList类的？（ ABC ） A、Add B、Capacity C、Count D、Length(A卷)下列描述中不正确的是（ ）。 A、字符型数组中可以存放字符串 B、可以对字符型数组进行整体输入、输出 C、可以对整型数组进行整体输入、输出 D、不能在赋值语句中通过赋值运算符“=”对字符型数组进行整体赋值(A卷)下列哪个方法不是用于向ArrayList中添加一个元素的？（ CD ） A、Add B、Insert C、AddRange D、Item(A卷)下列哪些参数是用来描述算法性能的？（ AB ） A、时间复杂度 B、空间复杂度 C、程序执行次数 D、实现算法的代码量(A卷)下列哪些方法属于RegEx类？（ CD ） A、Replace B、Split C、Jion D、Open(B卷)常见的图结构包含下列哪些图？（ AB ）。 A、无向图 B、有向图 C、带权图 D、位图(B卷)在一个图中，所有顶点的度数之和等于所有边数的多少倍？（ C ）。 A、0.5 B、1 C、2 D、4(B卷)如果要快速地对序列进行稳定的排序，则不应选择下列的哪些算法？（ ACD ）。 A、快速排序 B、归并排序 C、冒泡排序 D、二分法插入排序(B卷)下列哪些是属于链表的改进方案?（ BCD ） A、单向链表 B、双向链表 C、循环链表 D、递归链表(B卷)下列哪个特性属于面向对象思想？（ ABC ） A、封装 B、继承 C、多态 D、实例化 判断题(A卷)数组是非线性结构。（ N ）(A卷)多维数组就是多个一维数组组成的。（ Y ）(A卷)在基础排序算法中，选择排序是这三种算法中效率最高的，其次便是冒泡排序和插入排序。（ Y ）(A卷)关键字是指数据序列（或记录）中某个数据项的值，用以标识一个数据元素（或记录）。（ Y ）(A、B卷)在队列结构中，向队列中插入元素的过程称为出栈。（ N ）(A、B卷)当栈中元素的个数n=0时，则称之为空栈。（ Y ）(A卷)C#语言中字符串定义为字符的序列，它可以是字母、数字和其他符号的组合。（ Y ）(A卷)在初始化 StringBuilder 的实例时没有指定容量或最大容量，则使用特定于实现的默认值。（ Y ）(A卷)在C#语言中，要使用正则表达式，必须先从底层框架中引用RegEx类。该类位于System.Text.RegularExpression命名空间。（ Y ）(A、B卷)存储在字典结构中的键值项是通过DictionaryEntry对象来进行存储的。（ Y ）(B卷)栈又被称为后进先出(Last In First Out)的线性表，简称LIFO线性表。（ Y ）(B卷)String类的Split方法用于把一个字符串分解成一个序列片段，并且把它们放入到一个Stirng类型的数组里面。（ Y ）(B卷)StringBuilder对象的MaxCapacity属性返回当前对象实例中可以允许的最大字符串数目。（ Y ） (B卷)在C#2.0以后的版本还提供了泛型的SortedList类，使用它之前需要引用System.Collections.Generic。（ Y ）(B卷)二叉树是最多只有两个子树且两个子树有左右之分的有序树。（ Y ）(B卷)邻接表由结点表和边表两部分组成。（ Y ）(B卷)Queue类的Enqueue方法用于将对象添加到Queue的结尾。（ Y ） 名称解释部分(A卷)数组结构：数组是一种数据结构，它包含若干相同类型的变量，是一组可以被索引的数据集合。(A卷)冒泡排序：排序算法的得名是由于数值“像气泡一样”从集合的一端浮动到另一端。假如现在要把一列数据按照从小到大的方式进行排序，那么较大的数值浮动到数列的右边，较小的数值浮动到数列的左边。这种冒泡的效果可以通过多次遍历集合，并且比较相邻元素的数值，根据数值大小进行位置交换。(A卷)查找关键字：是指数据序列（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。(A卷)队列结构：队列(queue)也是一种特殊的线性表，但是它允许在表的一端进行插入操作，而在表的另一端进行删除操作。一般允许删除的一端称之为队头，允许插入的一端则称之为队尾。不含任何元素的空列表则称为空队列。(B卷)正则表达式：正则表达式中还有一个重要性的概念就是元字符，它是一种特殊的字符，用于表示重复、替换或者分组。(B卷)散列结构：散列是一种非常有用的数据存储结构，它可以迅速的操作数据(插入、查找等)。散列采用的数据结构我们通常称之为散列表。(B卷)Hashtable结构：Hashtable类是Dictionary对象的一种特殊数据类型，它存储的数据项为键值对。(B卷)链表结构：链表是被称为节点类的对象集合的群集。每一个链表节点通过一个引用链接到列表内的后继节点。 问答题(A卷)简述Array类与ArrayList的区别？Array类是数组基类，ArrayList表示的一个可变数组。(A卷)定义一个字符串数组，分别通过for及foreach语句进行循环遍历输出？string stuInfo = new String 水果,蔬菜,玉米;/使用for语句循环遍历数组 for (int temp = 0; temp stuInfo.Length; temp+) Console.WriteLine(string.Format(The Value is 0！, stuInfotemp); Console.WriteLine(.PadLeft(20,=); /使用foreach语句循环遍历数组 foreach (string strTemp in stuInfo) Console.WriteLine(string.Format(The Value of stuInfo is 0！,strTemp); (A、B卷)简述插入排序实现原理及执行过程?每一数据比较都将一个待排序的数据元素，按照其关键字的大小，插入到已经排序的数据序列中，使插入后的数据序列仍然是有序的，直到全部数据序列元素插入完毕为止。(B卷)定义一个多维数组，该数组用于代表学生成绩信息，且数组中每位同学有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+) intT