还剩14页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
数据结构考试内部题库含答案解析(全考点)、下列说法中错误的是—1O・:算法具备可行性、确定性和有穷性等重要特性•A:算法的时间复杂度是指获知算法执行时间的复杂••B程度・:算法执行时间需通过依据该算法编制的程序在计算机C上运行时所消耗的时间来度量・:算法中描述的操作都是可以通过已经实现的基本运•D算执行有限次来实现的解析选项说法逻辑混乱,不明白其意思B答案B、数组的逻辑结构不同于—的逻辑结构2・:线性表•A・:栈•B・队列•C:・:树•D:线索树.•B・:栈•C・:数组•D解析、选项均涉及存储结构选项是单纯的逻辑结构A BC选项,顺序表定义了数组和长度,其中D datalength长度显然不能表示存储结构,所以顺序表的存储结length构必然通过数组体现data答案C、某顺序存储的表格中有个元素,已按关键字升490000序排列,假定对每个元素进行查找的概率是相同的,且每个元素的关键字的值皆不相同用顺序查找法杳找时,平均比较次数约为一O•A:25000•B:30000•C:45000•D:90000解析顺序查找适用于查找顺序存储或链式存储的线性表,平均比较次数是N/2O答案C,、若串其非空子串数5S=database•A:37•B:36•C:35•D:34解析长度为的子串个数分别为1,2,3,4,5,6,7,88,7,6,5,4,3,所以子串总个数2,18+7+...+1=36这类题是有规律的假设字符串长度为,则空串为n11个然后就是长度为,的子串个数分别为21,2,3,…n n,所以子串总个数为n-1,n-2,…1l+n*n+l/2,z显然这是个奇数但本题中因为长度为的字符串有重复,所以长度为的11字符串个数为题目中要求的是非空子串,所以总数为6,选34,D答案D下列排序方法中,在最坏情况下,数据的交换效率最好的
6.排序方法是一方法:插入排序••A:快速排序••B:希尔排序••C:选择排序••D解析最坏情况下,、、三种方法的时间复杂度都为A BCn2,而选择排序法又可以分为直接选择和堆排0序,若为堆排序,时间复杂度为og2r0n答案D、代码如下,其中为正整数,则最后行的语句执行在最7n坏情况下的复杂度是—Ofor i=n-1;i=l;i--for j=l;j=i;j++if A[jJA[j+1]与交换A[j]A[j+1]•A:0n•B:Onlogn3n•c0解析最坏情况下,判断语句满足,当外循环和内循环都同if时进行时,语句双重嵌套,最坏时间复杂度为for2n0答案D、若结点的存储地址与其关犍字之间存在某种映射关系,8则称这种存储结构为:顺序存储结构•A:链式存储结构•B:索引存储结构•C:散列存储结构.•D解析散列存储,又称存储,是一种力图将数据元素的存hash储位置与关键码之间建立确定对应关系的查找技术散列法存储的基本思想是由节点的关键码值决定节点的存储地址答案D、算法的时间复杂度是指—9o・:算法执行的绝对时间A・随着问题规模的增大,算法执行时间的增长趋势•B:n・:算法中执行语句的条数•C・:获得算法执行时间的复杂程度•D解析算法中基本操作重复执行的次数是问题规模的某个函数n算法的时间度量记作它表述随问题规fn,Tn=Ofno模的增大,算法执行时间的增长率和的增长率相同,n fn称作时间复杂度答案B.假设包含个非零元素的稀疏矩阵含有行列,10t Am n并采用三元组顺序表压缩存储,其快速转置算法的时间复杂度为—O•A:Om+t•B:On+t•C:Om+n•D:Om*n解析快速转置时初始化所有列的非零元素的个数统1计为统计每一列的非零元素个数接着求每On;2t;3一列第一个非零元素的首位置最后对每一个非零n;4个数转置总共时间于是,时间复杂度为t2*n+t,On+to答案数组属于线性结构选项也都属于线性结构,B A,B,C而项中树属于非线性结构D答案D数据结构在计算机内存中的表示是指
3.数据的存储结构•A::数据结构•B数据的逻辑结构•C::数据元素之间的关系.D解析存储结构是指数据结构在计算机中的表示,也称物理结构,包括数据元素的表示和关系的表示,数据的存储结构主要包括顺序存储、链式存储、索引存储和散列存储答案A在微机中,作为一个整体存储,传送和处理的数据信息单
4.位是—O・二进制位•A:・:机器字•B字节•C:英文字母•D解析在微机中,作为一个整体存储,传送和处理的数据信息单位是字节答案C下列程序段的时间复杂度为一
5.o㊀i=l;j=0;whil i+j=n{;if ijj++else i++;•C:On•D:Om/2解析每循环一次/或增,且非同时增,即增;循j11i+j1环重复执行次,所以时间复杂度为n0n答案C下列说法中,不正确的是
6.数据元素是数据的基本单位••A::数据项是数据元素中不可分割的最小可标识单位•B:数据可由若干个数据元素构成••C:数据项可由若干个数据元素构成••D解析数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行处理一个数据元素可以由若干个数据项组成数据项是数据的不可分割的最小单位数据元素也称结点、定点、元素、记录答案D、下列关于算法说法正确的是—7e:算法最终必须由计算机程序实现•A・:算法是对特定问题求解步骤的描述,是指令的有限•B序列,其中每一条指令表示一个操作・:算法的可行性是指指令不能有二义性C・以上几个都是错误的•D:解析错误程序只是实现算法的一个手段,如果不用计算机A程序还可以用其他办法实现算法错误算法是对特定B问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作确定性算法中每一条指令必须有确切的含义,无二义性,并且在任何条件下,算法只有唯一的一条执行路径,即对于相同的输入只能得出相同的输出可行性一个算法是可行的,即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现错误正确性算法应满足具体问题的需求可读C性便于阅读和交流答案D、用算法和算法构造的最小生成树,所8Prim Kruskal得到的最小生成树()・:不相同•B可能相同,可能不同.•C:・无法比较•D:解析由于无向连通图的最小生成树不一定唯一,所以用不同算法生成的最小生成树可能不同,但当无向连通图的最小生成树唯一时,不同算法生成的最小生成树必定是相同的答案C、以下叙述中,正确的是()9・只要无向连通图中没有权值相同的边,则其最小生•A:成树唯一・只要无向图中有权值相同的边,则其最小生成树一•B:定不唯一・从个顶点的连通图中选取条权值最小的边,即•C n n-1可构成最小生成树・:设连通图含有个顶点,则含有个顶点,条•D Gn nn-1边的子图一定是的生成树G解析是它本身,这时就是唯一的;选项C,选取的n-1选项若无向图本身就是一棵树,则最小生成树就B,条边可能构成回路;选项含有个顶点、条边的子D,nn-1图可能构成回路,也可能不连通答案A以下叙述中,正确的是()
10.・最短路径一定是简单路径•A:・算法不适合求有回路的带权图的最短路径•B:Dijkstra・算法不适合求任意两个顶点的最短路径•C:Dijkstra・算法求两个顶点的最短路径时,•D:Floydpath^_^pathk k解析算法适合求解有回路的带权图的最短路径,也可Dijkstra以求任意两个顶点的最短路径,不适合求带负权值的最短路径问题在用算法求两个顶点的最Floyd短路径时,当最短路径发生更改时,Path—就不是仍PQ隔子集、抽象数据类型可以用,数据关系和基本操作来定义1答案A:数据元素•A:数据对象•B原子类型•C::存储结构•D解析抽象数据类型是指一个数学模型以及定义在该模型上的一组操作它通常是指对数据的某种抽象,定义了数据的取值范围及其结构形式,以及对数据的操作的集合抽象数据类型一般可以由数据对象、数据关系及基本操作来定义故选答案B Bo、数据结构的说法中正确的是一2o・:数据结构的逻辑结构独立于其存储结构•A・数据结构的存储结构独立于该数据结构的逻辑结构•B:・:数据结构的逻辑结构唯一地决定了该数据结构的•C存储结构・:数据结构仅由其逻辑结构和存储结构决定•D解析数据结构的存储结构是和相应的数据在内存中的物理地址之间的关系有关而逻辑结构只是描述数据之间的关系(三大逻辑结构的一种)举例说明线性表(元素之间的逻辑关系是线性的)可以是顺序存储的方式,即所有元素相邻存放,在物理地址上是连续的(存储结构);而对于链式存储的线性表,他的所有元素之间不一定是线性相连的,可能是第一个结点(元素)的地址为而第0x123,二个元素又出现在物理地址上也就是说逻辑结0x100构是线性的但是存储结构不一定就是线性的答案A以下与数据的存储结构无关的术语是—
3.o。