数据结构等级考试(例题分析和习题)详解.doc

数据结构与算法 例题分析 一、选择题 1．数据的__________包括集合、线性结构、树型结构和图状结构四种基本类型。 A)算法描述 B)基本运算 C)逻辑结构 D)存储结构 [答案]C [分析]数据结构是数据元素之间逻辑关系的整体。根据数据元素之间关系的不同特性，数据的逻辑结构通常包括集合、线性结构、树型结构和图状结构四种基本类型。 2．___________中任何两个结点之间都没有逻辑关系。 A)集合 B)图状结构 C)树型结构 D)线性结构 [答案]A [分析]树型结构具有分支、层次特性，其形态有点像自然界中的树。集合中任何两个结点之间都没有逻辑关系，组织形式松散。图状结构最复杂，其中的各个结点按逻辑关系互相关联，任何两个结点都可以邻接。线性结构中结点按逻辑关系依次排列形成一条“链”。 3．数据的存储结构包括顺序、___________、索引和散列四种基本类型。 A)向量 B)数组 C)集合 D)链接 [答案]D [分析]数据的计算机内部表示称为数据的存储结构。通常，存储结点之间有四种关联方式，称为四种基本存储方式，即：顺序存储、链式存储、索引存储和散列存储。 4．计算机算法指的是__________。 A)计算方法 B)调度方法 C)排序方法 D)解决某一问题的有限运算序列 [答案]D [分析]算法的定义是算法规定了求解给定类型问题所需的所有“处理方法与步骤”及其执行顺序，使得给定类型的任何问题能在有限时间内被求解，所以本题应选D。 5．下面____________的时间复杂性最好，即执行时间最短。 A)O(n) B)O(nlog2n) C)O(log2n) D)O(n3) [答案]C [分析]算法的时间复杂性的数量级采用大O表示，通常有常量级、对数级、线性与对数乘积级、平方级、立方级、指数级等级别，对应量级表示依次为O(1)，O(log2n)，O(n)，O(nlog2n)，O(n2)，O(n3)，O(2n)。当n较大时，量级越靠前的算法，其运行时间越短，或者说该算法效率越高。所以，上述四个选项中应选C。 6．把算法的工作量大小和实现算法所需的存储单元多少分别称为算法的____(1)_____和____(2)____。 (1) A)可实现性 B)时间复杂度 C)困难度 D)计算有效性 (2) A)可行性 B)高效性 C)可实现性 D)空间复杂度 [答案](1)B (2)D [分析]算法的复杂性是指对一个在有限步骤内终止算法和所需存储空间大小的估计。算法的计算量是算法的时间复杂性，算法所需存储空间大小是算法的空间复杂性。 7．在一个长度为n的顺序表中，向第i个元素(1≤i≤n+1)位置插入一个新元素时，需要从后向前依次后移_________个元素。 A) n-i B) i C) n-i-1 D) n-i+l [答案]D [分析]线性表的插入运算是指在表的第i (1≤i≤n+1)个位置上，插入一个新结点x，使长度为n的线性表变成长度为n+l的线性表。用顺序表作为线性表的存储结构时，插入算法的基本步骤是：①将结点ai, …，an各后移一位以便腾出第i个位置；②将x置入该空位；③表长加1。根据步骤①可知需移动元素个数是从i到n个，即n-i+1个。 8．从一个长度为n的顺序表中，删除第i个元素(1≤i≤n)时，需要从前向后依次向前移动_____个元素。 A) i B) n-i C) n-i-1 D) n-i+l [答案]B [分析]线性表的删除运算是指将表的第i (1≤i≤n)个结点删去，使长度为n的线性表变成长度为n-1的线性表。若i=n，则只要简单地删除终端结点，无需移动结点：若1≤i≤n-1，则必须将表中位置i+l，i+2，…，n上的结点依次前移到位置i，i+l，…，n-1上，以填补删除操作造成的空缺。所以，当1≤i≤n - 1时，需要向前移动的元素个数是从i+l到n个，即n-i个。当i=n时，移动元素个数为n-i。 9．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的，插入一个元素时平均移动表中的_______个元素。 A) n/2 B) (n-1)／2 C) (n+1)／2 D) n [答案]A [分