(全)2024版数据结构考试内部题库含答案解析.docx

《(全)2024版数据结构考试内部题库含答案解析.docx》由会员分享，可在线阅读，更多相关《(全)2024版数据结构考试内部题库含答案解析.docx（14页珍藏版）》请在优知文库上搜索。

1、数据结构考试内部题库含答案解析（全考点）1、下列说法中错误的是一。 A:算法具备可行性、确定性和有穷性等重要特性B：算法的时间复杂度是指获知算法执行时间的复杂程度 C:算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量 D:算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的解析B选项说法逻辑混乱，不明白其意思。答案：B2、数组的逻辑结构不同于的逻辑结构。 A:线性表.B:栈 C:队列 D:树解析数组属于线性结构，A,B,C选项也都属于线性结构，而D项中树属于非线性结构。答案：D3、数据结构在计算机内存中的表示是指o A:数据的存储结构.B:数据结构 C:数据

2、的逻辑结构.D:数据元素之间的关系解析存储结构是指数据结构在计算机中的表示，也称物理结构，包括数据元素的表示和关系的表示，数据的存储结构主要包括：顺序存储、链式存储、索引存储和散列存储。答案：A4、在微机中，作为一个整体存储，传送和处理的数据信息单位是O A:二进制位 B:机器字 C:字节 D:英文字母解析在微机中，作为一个整体存储，传送和处理的数据信息单位是字节。答案：C5、下列程序段的时间复杂度为一oi=l;j=O;while(i+jj)j+；elsei+;.B: C:0(n) D:0(m2)解析每循环一次，i或j增I,且非同时增1,即i+j增1；循环重复执行11次，所以时间复杂度为0(n

3、)。答案：C6、下列说法中，不正确的是o A:数据元素是数据的基本单位 B:数据项是数据元素中不可分割的最小可标识单位.C:数据可由若干个数据元素构成 D:数据项可由若干个数据元素构成解析数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行处理。一个数据元素可以由若干个数据项组成。数据项是数据的不可分割的最小单位。数据元素也称结点、定点、元素、记录。答案：D7.下列关于算法说法正确的是。A:算法最终必须由计算机程序实现 B:算法是对特定问题求解步骤的描述，是指令的有限序列，其中每一条指令表示一个操作 C:算法的可行性是指指令不能有二义性 D:以上几个都是错误的解析A错误：程序只是实现算

4、法的一个手段，如果不用计算机程序还可以用其他办法实现算法。B错误：算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。确定性：算法中每一条指令必须有确切的含义，无二义性，并且在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。可行性：一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。C错误。正确性：算法应满足具体问题的需求。可读性：便于阅读和交流。答案：D8、用Prim算法和Kruskal算法构造图的最小生成树，所得到的最小生成树（） B:不相同 C:可能相同，可能不同 D:无法比较解析由于无向连

5、通图的最小生成树不一定唯一，所以用不同算法生成的最小生成树可能不同，但当无向连通图的最小生成树唯一时，不同算法生成的最小生成树必定是相同的。答案：C9、以下叙述中，正确的是（）。A:只要无向连通图中没有权值相同的边，则其最小生成树唯一B:只要无向图中有权值相同的边，则其最小生成树一定不唯一 C从n个顶点的连通图中选取n-1条权值最小的边,即可构成最小生成树 D:设连通图G含有n个顶点，则含有11个顶点,n-1条边的子图一定是G的生成树解析选项B,若无向图本身就是一棵树，则最小生成树就是它本身，这时就是唯一的；选项C,选取的Fl-I条边可能构成回路；选项D,含有n个顶点、n-l条边的子图可能构成

6、回路，也可能不连通。答案：A10.以下叙述中，正确的是（）。 A:最短路径一定是简单路径 .B:Dijkstra算法不适合求有回路的带权图的最短路径.C:Dijkstra算法不适合求任意两个顶点的最短路径 D:Floyd算法求两个顶点的最短路径时,pathk-一日Pathk解析Dijkstra算法适合求解有回路的带权图的最短路径,也可以求任意两个顶点的最短路径，不适合求带负权值的最短路径问题。在用FlOyd算法求两个顶点的最短路径时，当最短路径发生更改时，Pathk_1就不是PQ历%子集。答案：A1、抽象数据类型可以用_、数据关系和基本操作来定义。 A:数据元素.B:数据对象 C:原子类型.D

7、:存储结构解析抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。它通常是指对数据的某种抽象，定义了数据的取值范围及其结构形式，以及对数据的操作的集合。抽象数据类型一般可以由数据对象、数据关系及基本操作来定义。故选Bo答案：B2、数据结构的说法中正确的是。 A:数据结构的逻辑结构独立于其存储结构 B:数据结构的存储结构独立于该数据结构的逻辑结构 C:数据结构的逻辑结构唯一地决定了该数据结构的存储结构 D:数据结构仅由其逻辑结构和存储结构决定解析数据结构的存储结构是和相应的数据在内存中的物理地址之间的关系有关。而逻辑结构只是描述数据之间的关系（三大逻辑结构的一种）。举例说明：线性表（元素之

8、间的逻辑关系是线性的）可以是顺序存储的方式，即所有元素相邻存放，在物理地址上是连续的（存储结构）；而对于链式存储的线性表，他的所有元素之间不一定是线性相连的，可能是第一个结点（元素）的地址为0x123,而第二个元素又出现在物理地址0x1000也就是说逻辑结构是线性的但是存储结构不一定就是线性的。答案：A3、以下与数据的存储结构无关的术语是oA:循环队列 B:线索树 C:栈 D:数组解析A、B选项均涉及存储结构。C选项是单纯的逻辑结构。D选项，顺序表定义了data数组和length长度，其中length长度显然不能表示存储结构，所以顺序表的存储结构必然通过data数组体现。答案：C4、某顺序存储

9、的表格中有90000个元素，已按关键字升序排列，假定对每个元素进行直找的概率是相同的，且每个元素的关键字的值皆不相同。用顺序查找法查找时，平均比较次数约为一O A:25000.B:30000C:45000.D:90000解析顺序查找适用于查找顺序存储或链式存储的线性表，平均比较次数是N2o答案：C5、若串S=database，其空子串数目为一o.A:37.B:36.C:35.D:34解析长度为1,2,3,4,5,6,7,8的子串个数分别为：8,7,6,5,4,3,2,1。所以子串总个数：87+.+l=36o这类题是有规律的：假设字符串长度为n,则(1)空串为1个(2)然后就是长度为1,2,3,

10、，n的子串个数分别为：n,(n-l),(n-2)，1所以子串总个数为：l+n*(n+l)2,显然这是个奇数。但本题中因为长度为1的字符串有重复，所以长度为1的字符串个数为6,题目中要求的是非空子串，所以总数为34,选D。答案：D6、下列排序方法中，在最坏情况下，数据的交换效率最好的排序方法是_方法。 A:插入排序 B:快速排序 C:希尔排序 D:选择排序解析最坏情况下，A、B、C三种方法的时间复杂度都为n20(),而选择排序法又可以分为直接选择和堆排序，若为堆排序，时间复杂度为0(ng21答案：D7、代码如下，其中n为正整数，则最后行的语句执行在最坏情况下的复杂度是Ofor(i=n-1;i=l

11、;i-)for(j=l;jAj+1)Aj与Aj+1交换 A:0(n) B:O(nlog()n3 C:0()解析最坏情况下，if判断语句满足，当外循环和内循环都同时进行时，for语句双重嵌套，最坏时间复杂度为答案：D8、若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为一O A:存储结构 B：链式存储结构.C:索引存储结构-D:散列存储结构解析散列存储，又称hash存储，是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。散列法存储的基本思想是：由节点的关键码值决定节点的存储地址。答案：D9、算法的时间复杂度是指o A:算法执行的绝对时间 B：随着问题规模n的增

12、大，算法执行时间的增长趋势 C:算法中执行语句的条数 D:获得算法执行时间的复杂程度解析算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记作T(n)=O(f(n)o它表述随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作时间复杂度。答案：B10、假设包含t个非零元素的稀疏矩阵A含有m行n歹U,并采用三元组顺序表压缩存储，其快速转置算法的时间复杂度为O.A:O(m+t) B:O(n+t) C:0(m+n) D:0(m*n)解析快速转置时：1)初始化所有列的非零元素的个数统计为O(Fi);2)统计每一列的非零元素个数(t);3)接着求每一列第一个非零元素的首位置(n);4)最后对每一个非零个数转置仕)。总共时间：2*(nt),于是，时间复杂度为：O(n+t)0答案：B