2023版数据结构考试内部题库含答案解析

数据结构考试内部题库含答案解析（全考点）1、处理冲突的方法有____。•A：线性探测法•B：除留余数法•C：链地址法•D：折叠法解析处理冲突的方法：1、开放地址法•（1）线性探测法•（2）二次探测法•（3）伪随机探测法2、链地址法答案：A，C2、下面的叙述中，不正确的是____。•A：关键活动不按期完成就会影响整个工程的完工时间•B：任何一个关键工程提前完成，将使整个工程提前完成•C：所有关键活动都提前完成，则使整个工程提前完成•D：某些关键活动若提前完成，则将使整个工程提前完成解析关键活动组成了关键路径，关键路径是图中的最长路径，关键路径长度代表整个工期的最短完成时间，关键活动延期完成，必将导致关键路径长度增加，即整个工期的最短完成时间增加，因此A正确。关键路径并不唯一，当有多条关键路径存在时，其中一条关键路径上的关键活动时间缩短，只能导致本条关键路径变成非关键路径，而无法缩短整个工期，因为其他关键路径没有变化，因此B项不正确。对于A，B两项要搞懂的是，任何一条关键路径上的关键活动变长了，都会使这条关键路径变成更长的关键路径，并且导致其他关键路径变成非关键路径（如果关键路径不唯一），因此整个工期延长。某些关键活动缩短则不一定缩短整个工期，故D也不对。答案：B，D3、10条边的简单无向图，最多有____个顶点，最少有____个顶点。•A：3•B：4•C：5•D：任意多解析完全连通图时顶点最少5个。答案：D，C4、数据结构是一门研究程序设计中数据的____以及它们之间的____和运算等的学科。•A：元素•B：计算方法•C：逻辑存储•D：映像•A：结构•B：关系•C：运算•D：算法解析数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的关系和运算等的学科。答案：A，B5、用户把观察到的且可以处理的信息根据使用要求构造成文件，这种构造方式称为文件的逻辑结构，又叫逻辑文件，逻辑文件包括________。•A：索引文件•B：顺序文件•C：流式文件•D：记录式文件解析按照文件的逻辑结构的不同，可以把文件分成流式文件和记录式文件。构成流式文件的基本单位是字符或字节，如ASCII码文件或者二进制文件；构成记录式文件的基本单位是记录，一条记录又由若干个数据项构成。这实质是从用户角度看到的文件的逻辑结构，也可以按照物理结构对文件进行分类。答案：C，D6、一维数组的逻辑结构是____，存储结构是____；对于二维或多维数组，分为按____和____两种不同的存储方式。解析逻辑结构有四种基本类型：集合结构、线性结构、树状结构和网络结构。也可以统一的分为线性结构和非线性结构，一维数组的逻辑结构是线性结构；存储结构一般有四种：顺序存储，链式存储，散列，索引，一维数组的存储结构是顺序存储；对于二维或多维数组，分为按行优先顺序和列优先顺序两种不同的存储方式。答案：线性结构；顺序结构；行优先顺序；列优先顺序7、顺序存储方法是把逻辑上____存储在物理位置上____里；链式存储方法中节点间的逻辑关系是由____的。解析顺序存储方法是把逻辑上相邻的结点存储在物理位置也相邻的存储单元中。链式存储逻辑上相邻的结点物理上不必邻接，链式存储结构是在每个结点中至少包括一个指针域，用指针来体现数据元素之间逻辑上的联系。答案：相邻的节点；相邻的存储单元；附加的指针字段表示。8、若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，需要移动表中____个数据元素。•A：n-i•B：n+i•C：n-i+1•D：n-i-1解析删除线性表的第i个数据元素，需要将线性表的第i+1个数据元素至第n个数据元素依次前移1个位置，一共需要移动n-i个数据元素。答案：A9、若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i的合法值应该是____。•A：i>0•B：in•C：1in•D：1in+1解析在线性表的第1至第n个位置插入一个数据元素显然是允许的，紧挨在线性表最后那个数据元素后面插入一个数据元素也是允许的，因此，i的合法值应该是1in+1。答案：D10、若线性表最常用的操作是存取任意指定序号的元素和最后进行插入和删除运算，则利用____存储方式最节省时间。•A：顺序表•B：双链表•C：头结点的双循环链表•D：单循环链表解析顺序表便于存取，如果要插入，删除则需要移动大量的数据，工作量大，而在末尾的插入删除就不需要；链表方便与插入、删除，而存取的话需要遍历整个链表，工作量大。答案：A1、数据对象是指____。•A：描述客观事物且由计算机处理的数值、字符等符号的总称•B：数据的基本单位•C：性质相同的数据元素的集合•D：相互之间存在一种或多种特定关系的数据元素的集合解析数据对象：是性质相同的数据元素的集合，是数据元素的子集，数据对象是一种运行时的概念，可以是外部实体（例如，专产生或使用信息的任何事物）、事物（例如，报表）、行为（例如，打电话）、事件（例如，响警报）、角色（例如，教师、学生）、单位（例如，会计科）、地点（例如，仓库）或结构（例如，文件）等。总之，可属以由一组属性来定义的实体都可以被认为是数据对象。答案：C2、假设有n个顶点e条边的有向图用邻接表表示，删除与某个顶点v相关的所有边的算法的时间复杂度为_____。•A：O(n)•B：O(e)•C：O(n+e)•D：O(n*e)解析删除与某个顶点v相关的所有边的过程：先删除下标为v的顶点表节点的单链表，出变数最多为n-1，对应时间复杂度为O(n)，再扫描所有边表的结点，删除所有的顶点V的入边，对应的时间复杂度为O(e)。故总的时间复杂为O(n+e)。选C。答案：C3、以下属于逻辑结构的是____。•A：顺序表•B：哈希表•C：有序表•D：单链表解析数据的逻辑结构是对数据元素之间的逻辑关系的描述。顺序表、哈希表和单链表属于存储结构。答案：C4、算法的时间复杂度主要用____方法来计算。•A：后期测试•B：事前估计•C：事后估计•D：统计算法中所有的程序步数解析一个算法的事件复杂度通常包括空间复杂度和时间复杂度。一般是统计算法中所有程序的执行步数来计算。答案：D5、算法的时间复杂度取决于_____。•A：问题规模•B：待处理数据的初态•C：A和B•D：与A和B无关解析问题规模是指算法复杂程度，n级别，logn平方级别。初态指的就是处理数据是否有序这种信息。时间复杂度与问题规模有关，问题规模越大，需要的时间就越长，也跟初始状态有关，初始状态越乱，需要的时间也越长。答案：C6、下面是有关抽象数据类型概念的论述，其中正确的说法是____。•A：抽象数据类型与存储结构有关•B：抽象数据类型与数据结构是同义词•C：抽象数据类型是指一个数学模型以及定义在该模型上的一组擦欧总•D：抽象数据类型是指描述客观事物且由计算机处理的数值、字符等符号的总称解析抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算，与存储结构无关；对一个抽象数据类型进行定义，须给出它的名字及各运算的运算符名，并且规定这些函数的参数性质。答案：C7、链式存储结构中，每个数据的存储结点里____指向邻接存储结点的指针，用以反映数据间的逻辑关系。•A：只能有１个•B：只能有２个•C：只能有３个•D：可以有多个解析在链式存储中，结点间的逻辑关系是由附加的指针表示。而数据的逻辑关系包括线性和非线性，线性指数据间存在一对一的关系，非线性指数据间存在一对多的关系，所以选D。答案：D8、下列排序算法中，____、____是稳定排序，____、____属于不稳定排序。•A：起泡排序•B：快速排序•C：插入排序•D：堆排序解析稳定排序就是能保证前2个相等的数在序列的前后顺序和排序后它们两个的前后顺序相同。比如，如果

=

，原来在位置前，排序后还是要在位置前。快速排序和堆排序在排序前后相同元素的位置有可能会交换，因此不是稳定排序。答案：A，C，B，D9、8个关键字的3阶B树，高度最大为____，最小为____。•A：2•B：3•C：4•D：5解析3阶B树每个节点最多有3棵子树和2个关键字。层数最高则所有节点的关键字数量最少。每个节点都是1个关键字的时候层数可以达到最多，此时为4层。层数最低则所有节点的关键字都最多。根节点最多2个关键字，叶子节点最多2个关键字，所以除了1个根节点再有3个叶子节点时层数最少