二级C语言程序设计-公共基础知识-第1章数据结构与算法单选题1.下列叙述中正确的是()。A.所谓算法就是计算方法B.程序可以作为算法的一种描述方法C.算法设计只需考虑得到计算结果D.算法设计可以忽（江南博哥）略算法的运算时间 正确答案：B参考解析：A项错误，算法并不等同于计算方法，是指对解题方案的准确而完整的描述；C项错误，算法设计需要考虑可行性、确定性、有穷性与足够的情报；D项错误，算法设计有穷性要求操作步骤有限且必须在有限时间内完成，耗费太长时间得到的正确结果是没有意义的。B项正确，程序可以作为算法的一种描述方法,算法在实现时需要用具体的程序设计语言描述。答案选择B选项。单选题2.算法的有穷性是指()。A.算法程序的运行时间是有限的B.算法程序所处理的数据量是有限的C.算法程序的长度是有限的D.算法只能被有限的用户使用 正确答案：A参考解析：算法设计有穷性要求操作步骤有限且必须在有限时间内完成，耗费太长时间得到的正确结果是没有意义的。答案选择A选项。单选题4.算法的时间复杂度是指()。A.算法的执行时间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的基本运算次数 正确答案：D参考解析：算法的复杂度主要包括时间复杂度和空间复杂度。算法的时间复杂度，是指执行算法所需要的计算工作量，即基本运算次数；算法的空间复杂度，一般是指执行这个算法所需要的内存空间。答案选择D选项。单选题5.算法时间复杂度的度量方法是()。A.算法程序的长度B.执行算法所需要的基本运算次数C.执行算法所需要的所有运算次数D.执行算法所需要的时间 正确答案：B参考解析：算法的时间复杂度是指执行算法所需要的计算工作量，即算法所执行的基本运算次数来度量的。答案选择B选项。单选题6.算法的空间复杂度是指()。A.算法程序的长度B.算法程序中的指令条数C.算法程序所占的存储空间D.算法执行过程中所需要的存储空间 正确答案：D参考解析：算法的空间复杂度是指算法在执行过程中所需要的计算机存储空间。包括算法程序所占空间，输入的初始数据所占空间和执行过程中所需要的额外空间。答案选择D选项。单选题7.算法的空间复杂度是指()。A.算法在执行过程中所需要的计算机存储空间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的临时工作单元数 正确答案：A参考解析：算法的空间复杂度是指算法在执行过程中所需要的计算机存储空间。包括算法程序所占空间，输入的初始数据所占空间和执行过程中所需要的额外空间。答案选择A选项。单选题8.算法空间复杂度的度量方法是()。A.算法程序的长度B.算法所处理的数据量C.执行算法所需要的工作单元D.执行算法所需要的存储空间 正确答案：D参考解析：算法的空间复杂度是指算法在执行过程中所需要的计算机存储空间。包括算法程序所占空间，输入的初始数据所占空间和执行过程中所需要的额外空间。答案选择D选项。单选题9.下列叙述中错误的是()。A.算法的时间复杂度与算法所处理数据的存储结构有直接关系B.算法的空间复杂度与算法所处理数据的存储结构有直接关系C.算法的时间复杂度与空间复杂度有直接关系D.算法的时间复杂度与算法程序执行的具体时间是不一致的 正确答案：C参考解析：算法的时间复杂度是指执行算法所需要的计算工作量。数据的存储结构直接决定数据输入，因此会影响算法所执行的基本运算次数，A项正确；算法的空间复杂度是指执行这个算法所需要的内存空间，其中包括输入数据所占的存储空间，B项正确；算法的时间复杂度与空间复杂度没有直接关系，C项错误；算法程序执行的具体时间受到所使用的计算机、程序设计语言以及算法实现过程中的许多细节影响，而算法的时间复杂度与这些因素无关，所以算法的时间复杂度与算法程序执行的具体时间是不一致的，D项正确。答案选择C选项。单选题10.下列关于算法复杂度叙述正确的是()。A.最坏情况下的时间复杂度一定高于平均情况的时间复杂度B.时间复杂度与所用的计算工具无关C.对同一个问题，采用不同的算法，则它们的时间复杂度是相同的D.时间复杂度与采用的算法描述语言有关 正确答案：B参考解析：A项错误，最坏情况下的时间复杂度有可能与平均情况的时间复杂度相同；C项错误，对同一个问题，不同的算法时间复杂度有时可能差距很大；D项错误，算法的时间复杂度与实现算法的描述语言、运行环境无关，算法的时间复杂度是对算法执行时所花时间的度量。答案选择B选项。单选题11.下面关于算法的叙述中，正确的是()。A.算法的执行效率与数据的存储结构无关B.算法的有穷性是指算法必须能在执行有限个步骤之后终止C.算法的空间复杂度是指算法程序中指令（或语句）的条数D.算法所执行的基本运算次数与问题的规模无关 正确答案：B参考解析：A项错误，不同的数据存储结构有不同的数据读取效率，会影响到算法的执行；C项错误，算法的空间复杂度是对这个算法所需要的内存空间的量度，包括：算法程序所占的空间；输入的初始数据所占的存储空间；算法执行中所需要的额外空间；D项错误，算法所执行的基本运算次数与问题的规模有关。答案选择B选项。单选题12.下列关于算法的描述中错误的是()。A.算法强调动态的执行过程，不同于静态的计算公式B.算法必须能在有限个步骤之后终止C.算法设计必须考虑算法的复杂度D.算法的优劣取决于运行算法程序的环境 正确答案：D参考解析：算法是指对解题方案的准确而完整的描述。A项正确，算法强调实现，不同于数学上的计算方法；B项正确，算法的有穷性是指，算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成；C项正确，算法设计必须考虑执行算法所需要的资源，即时间复杂度与空间复杂度；D项错误，算法的优劣取决于算法复杂度，只有当算法被编程实现运行时才会受到运行环境影响。答案选择D选项。单选题13.线性表常采用的两种存储结构是()。A.散列方法和索引方式B.链表存储结构和数组C.顺序存储结构和链式存储结构D.线性存储结构和非线性存储结构 正确答案：C参考解析：线性表常用的存储结构为：顺序存储结构，物理上连续存储，空间位置隐含逻辑位置；链式存储结构，各元素物理存储上不连续，通过指针相连。答案选择C选项。单选题14.下列数据结构中，属于非线性结构的是()。A.双向链表B.循环链表C.二叉链表D.循环队列 正确答案：C参考解析：线性结构要满足两个条件：有且仅有一个根结点；每个结点最多有一个前驱，也最多有一个后继。线性表、栈、队列都是线性结构，循环链表和双向链表是线性表的链式存储结构，属于线性结构，只是存储结构不连续；循环队列是一个头结点和尾结点互为前驱结点和后继结点的特殊的队列，属于线性结构；二叉链表是二叉树的链式存储结构，因为二叉树有些结点有两个后继结点，不符合线性结构的定义，所以二叉链表是非线性结构。答案选择C选项。单选题15.以下数据结构中，属于非线性数据结构的是()。A.栈B.线性表C.队列D.二叉树 正确答案：D参考解析：线性结构必须满足下列两个条件：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。如果一个数据结构不是线性结构，则称之为非线性结构。二叉树中的结点后继不惟一，属于非线性结构，栈和队列都是操作受限的线性表，是线性结构。答案选择D选项。单选题16.数据结构中，与所使用的计算机无关的是数据的()。A.存储结构B.物理结构C.逻辑结构D.线性结构 正确答案：C参考解析：数据结构研究数据逻辑结构、存储结构以及数据运算，其中逻辑结构反映的是数据元素之间的逻辑关系，与使用的计算机无关。答案选择C选项。单选题17.数据结构主要研究的是数据的逻辑结构、数据的运算和()。A.数据的方法B.数据的存储结构C.数据的对象D.数据的逻辑存储 正确答案：B参考解析：数据结构是相互之间存在一种或多种特定关系的数据元素的集合，主要研究数据元素及其之间的相互关系和数据运算，包括：数据的逻辑结构；数据的存储结构；数据的运算。其中逻辑结构反映的是数据元素之间的逻辑关系，与使用的计算机无关。答案选择B选项。单选题18.下列描述中，正确的是()。A.线性链表是线性表的链式存储结构B.栈与队列是非线性结构C.双向链表是非线性结构D.只有根结点的二叉树是线性结构 正确答案：A参考解析：线性结构是指如果一个非空的数据结构满足下列两个条件：有且只有一个根结点；每个结点最多有一个前件，也最多有一个后件。B项错误，栈和队列都是操作受限的线性表；C项错误，双向链表是线性结构；D项错误，二叉树中的结点后继不唯一，属于非线性结构。答案选择A选项。单选题19.下列关于线性表的叙述中，不正确的是()。A.线性表可以是空表B.线性表是一种线性结构C.线性表的所有结点有且仅有一个前件和后件D.线性表是由n个元素组成的一个有限序列 正确答案：C参考解析：线性表是由n个元素组成的一种线性结构，当n=0时线性表为空表。C项错误，线性表中，第一个结点没有前件，最后一个结点没有后件。答案选择C选项。单选题20.以下描述中，不是线性表顺序存储结构特征的是()。A.可随机访问B.需要连续的存储空间C.不便于插入和删除D.逻辑相邻的数据物理位置上不相邻 正确答案：D参考解析：在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素称为顺序存储，其中逻辑上相邻的元素在物理位置上也相邻。顺序存储结构中可以随机访问元素，但插入和删除需要移动大量数据，耗费资源。答案选择D选项。单选题21.下列叙述中正确的是()。A.所有数据结构必须有根结点B.所有数据结构必须有终端结点（即叶子结点）C.只有一个根结点，且只有一个叶子结点的数据结构一定是线性结构D.没有根结点或没有叶子结点的数据结构一定是非线性结构 正确答案：D参考解析：D项正确，线性结构的特点是：集合中必存在“第一个元素”且惟一；集合中必存在“最后一个元素”且惟一；除最后一个元素外，其他数据元素均有惟一的“后继”；除第一个元素外，其他数据元素均有惟一的“前驱”。所以没有根结点或没有叶子结点的数据结构一定是非线性结构。AB两项错误，不是所有数据结构都必须有根结点和叶子结点；C项错误，数据结构中若有中间结点不满足只有一个前件或者后件的条件，就不是线性结构。答案选择D选项。单选题22.设数据元素的集合D=1,2,3,4,5，则满足下列关系R的数据结构中为线性结构的是()。A.R=(1,2),(3,4),(5,1),(1,2)B.R=(1,3),(4,1),(3,2),(5,4)C.R=(1,2),(2,3),(4,5),(2,3)D.R=(1,3),(2,4),(3,5),(1,2) 正确答案：B参考解析：一个非空的数据结构如果满足以下两个条件：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件，称为线性结构。不同时满足以上两个条件的数据结构就称为非线性结构。A选项，5是1的前件，1是2的前件，3是4的前件，则关系R中含有两个结构，即34和512，其中3和5均为根结点，故A项错误。B选项根结点为5，排列顺序为54132，B选项正确。C选项有两个根结点1和4，