搜索
第一章数据结构与算法考点1：算法（概念、特征、组成、方法、算法的复杂度）1、算法的概念(1)概念：是指解题方案的准确而完整的描述。【考题1】在计算机中，算法是指()A查询方法B加工方法C对解题方案的准确而完整的描述D排序方法【答案】：C【考题2】问题处理方案的正确而完整的描述称为。【答案】：算法2、算法的特征(1)算法的特征具有4种：可行性、确定性、有穷性、拥有足够的情报。①可行性：在算法的执行过程中，每一个步骤都要可行，可通。经过执行能够得到一个结果。②确定性：算法中的每一个步骤都要有确切的含义，不能有二义性，对于相同的输入必须能得出相同的执行结果。③有穷性：一个算法包含的操作步骤是有限的。也就是说，在执行若干个操作步骤之后算法结束，而且每一个步骤都要在合理的时间内完成。④拥有足够的情报：即拥有足够的输入数据。通过大量的给算法输入数据来验证算法输出的结果是否有误。【考题1】下列选项中不属于算法特征的是()A无穷性B确定性C可行性D拥有足够的情报【答案】：A【考题2】对于一个算法，它必须要在有限步骤合理时间内完成，这属于算法的()A可行性B确定性C有穷性D拥有足够的情报【答案】：C【考题3】在算法中，算法的特征具有可行性、确定性、、拥有足够的情报。【答案】：有穷性3、算法的组成(1)算法的组成有两种：对数据对象的运算和操作、算法的控制结构。(2)算法的控制结构有3种：顺序结构、选择结构、循环结构。4、算法的方法(1)在算法中，对问题描述的方法有6种：列举法、归纳法、递推、递归、减半递推技术、回溯法。5、算法的复杂度(1)算法的复杂度是对算法中的各种方法进行衡量的标准。(2)算法的复杂度有两种：算法的时间复杂度和算法的空间复杂度。①算法的时间复杂度：是指执行算法所需要的（计算工作量）基本运算次数。②算法的空间复杂度：是指执行算法所需要的内存空间。【知道】算法时间复杂度的好与坏不会影响空间复杂度的好与坏。【考题1】算法的时间复杂度是指()A执行算法程序所需要的时间B算法程序的长度C算法执行过程中所需要的基本运算次数D算法程序中的指令条数【答案】：C【考题2】算法的空间复杂度是指()A算法程序的长度B算法程序中的指令条数C算法程序所占的存储空间D算法执行过程中所需要的存储空间【答案】：D【考题3】下列叙述中正确的是()A一个算法的空间复杂度大，则其时间复杂度也必定大B一个算法的空间复杂度大，则其时间复杂度必定小C一个算法的时间复杂度大，则其空间可复杂度必定小D上述三种说法都不对【答案】：D【解析】：算法时间复杂度的好与坏不会影响空间复杂度的好与坏。考点2：数据结构（逻辑结构、存储结构、线性表、栈、队列、树和二叉树、查找和排序）1、数据结构(1)数据结构主要研究和讨论三个方面的内容：逻辑结构、存储结构、运算。【考题1】数据结构包括数据的和数据的存储结构。【答案】：逻辑结构2、逻辑结构(1)满足逻辑结构的的条件：①表示数据元素的信息；②表示各数据元素之间的前后件关系。(2)逻辑结构的分类：线性结构、非线性结构。①线性结构：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。在本书中，线性结构主要讲到的有：线性表、栈、队列。②非线性结构：不满足线性结构条件的就属于非线性结构。在本书中，非线性结构主要讲到的有：树、二叉树。【考题1】数据结构中，与所使用的计算机无关的是数据的()A存储结构B物理结构C逻辑结构D物理和存储结构【答案】：C【解析】：逻辑结构讨论的是现实世界中数据与数据之间的关系；存储结构也叫物理结构，指的是逻辑结构在计算机存储空间的存放形式。所以存储结构和计算机有关。A、B和D都不选。【考题2】以下数据结构中不属于线性结构的是()A队列B线性表C二叉树D栈【答案】：C【考题3】数据的逻辑结构有线性结构和两大类。【答案】：非线性结构3、存储结构(1)概念：数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)(2)数据的逻辑结构在计算机存储空间中的存储形式通常有两种：顺序存储结构、链式存储结构。①顺序存储结构：数据在存储空间中必须连续，且元素之间一定要有前后件的关系。②链式存储结构：数据在存储空间中不一定连续，且各元素的存储顺序是任意的。(3)两种存储结构的优缺点：①顺序存储结构：优点是查找方便。缺点是插入、删除不方便。②链式存储结构：优点是插入、删除方便。缺点是查找不方便。【考题1】数据的存储结构是指()A存储在外存中的数据B数据所占的存储空间C数据在计算机中的顺序存储D数据的逻辑结构在计算机中的表示【答案】：D【考题2】下列叙述正确的是()A一个逻辑数据结构只能有一种存储结构B数据的逻辑结构属于线性结构，存储结构属于非线性结构C一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率【答案】：D【解析】：一个逻辑数据结构可以有多种存储结构，例如顺序存储结构和链式存储结构。所以A答案不正确；数据的逻辑结构分为两类：线性结构和非线性结构。存储结构的存储形式可以有多种，例如顺序存储结构和链式存储结构。逻辑结构和存储结构都是我们数据结构的讨论内容。所以B答案不正确；只有D答案正确，因为一个逻辑数据结构可以有多种存储结构，例如顺序存储结构和链式存储结构，且各种存储结构影响数据处理的效率。【考题3】下列叙述中正确的是()A算法的效率只与问题的规模有关，而与数据的存储结构无关B算法的时间复杂度是指执行算法所需要的计算工作量C数据的逻辑结构与存储结构是一一对应的D算法的时间复杂度与空间复杂度一定相关【答案】：B【解析】：算法的执行效率与数据的存储结构密切相关。所以A不正确；B是正确的；数据的逻辑结构与存储结构中的顺序存储结构是一一对应的（一致的），而与链式存储结构就不一定一一对应了。所以C不正确；算法时间复杂度的好与坏不会影响空间复杂度的好与坏，所以不相关，故D不正确。【考题4】下列叙述中正确的是()A程序执行的效率与数据的存储结构密切相关B程序执行的效率只取决于程序的控制结构C程序执行的效率只取决于所处理的数据量D以上三种说法都不对【答案】：A4、线性表(1)线性表往计算机中进行存放，不仅可以采用顺序存储结构存放，还可以采用链式存储结构存放。①顺序表：即线性表采用顺序存储结构存放。②线性链表：即线性表采用链式存储结构存放。(2)顺序表和线性链表的特点：①顺序表：随机（访问）存取、查找方便，插入删除不方便、事先估计存储空间。②线性链表：顺序（访问）存取、插入删除方便，查找不方便、不必事先估计存储空间。【考题1】在下面关于线性表的叙述中，选出正确的一项()A线性表的每一个元素都有一个直接前驱和直接后继B线性表中至少要有一个元素C线性表中的元素必须按递增或递减的顺序排列D除第一个元素和最后一个元素外，每个元素都有一个直接前驱和直接后继【答案】：D【解析】：A答案不正确，因为除第一个元素和最后一个元素外，每个元素都有一个直接前驱和直接后继；B答案不正确，线性表中也可以没有元素，此时为空表；C答案不正确，线性表中元素的排列顺序没有要求；D答案正确。【考题2】下列对线性链表描述正确的是()A存储空间不一定连续，且各元素的存储顺序是任意的B存储空间不一定连续，且前件元素一定存储在后件元素的前面C存储空间必须连续，且前件元素一定存储在后件元素的前面D存储空间必须连续，且各元素的存储顺序是任意的【答案】：A【解析】：线性表采用顺序存储结构存储时，数据在计算机存储空间中必须连续，且元素之间一定要有前后件的关系；线性表采用链式存储结构存储时，数据在计算机存储空间中不一定连续，且各元素的存储顺序是任意的。【考题3】下列对线性表叙述中，正确的一项是()A采用链式存储的线性表，必须占用一片连续的存储单元B采用顺序存储的线性表，便于进行插入和删除操作C采用链式存储的线性表，不必占用一片连续的存储单元D链式和顺序存储的线性表，都便于进行插入和删除操作【答案】：C【解析】：线性表采用顺序存储结构存储时，数据在计算机存储空间中必须连续，且元素之间一定要有前后件的关系；线性表采用链式存储结构存储时，数据在计算机存储空间中不一定连续，且各元素的存储顺序是任意的。顺序表便于查找，线性链表便于插入和删除操作。【考题4】线性表的顺序存储结构和线性表的链式存储结构分别是()A顺序存取的存储结构、顺序存取的存储结构B随机存取的存储结构、顺序存取的存储结构C随机存取的存储结构、随机存取的存储结构D任意存取的存储结构、任意存取的存储结构【答案】：B【解析】：顺序表的特点是随机（访问）存取；线性链表的特点是顺序（访问）存取。【考题5】链表不具有的特点是()A不必事先估计存储空间B可随机访问任一元素C插入删除不需要移动元素D所需空间与线性表长度成正比【答案】：B【解析】：线性链表具有的特点：顺序（访问）存取、插入删除方便，查找不方便、不必事先估计存储空间。A、C、D都属于，其D也要知道，线性表多长，在内存空间中也就多长。故B不正确。【考题6】数据结构分为逻辑结构与存储结构，线性链表属于。【答案】：存储结构【解析】：线性链表是线性表在计算机的存储空间中的链式存储结构。所以在计算机的存储空间中，因此属于存储结构。5、栈(1)栈是一种特殊的线性表，其特殊性是插入与删除运算都只在线性表的一端进行。即栈的一个考点是：入栈和退栈都是在一端（栈顶）进行的。(2)栈在计算机中进行存储时通常采用的存储方式有：顺序存储结构、链式存储结构。(3)栈的原则是：先进后出、后进先出。【考题1】下列关于栈的描述正确的是()A在栈中只能插入元素而不能删除元素B在栈中只能删除元素而不能插入元素C栈是特殊的线性表，只能在一端插入或删除元素D栈是特殊的线性表，只能在一端插入元素，而不能在一端删除元素【答案】：C【解析】：栈的入栈运算和退栈运算都是在一端进行的，即栈顶。【考题2】下列关于栈的描述中错误的是()A栈是先进后出的线性表B栈只能顺序存储C栈具有记忆作用D对栈的插入与删除操作中，不需要改变栈底指针【答案】：B【解析】：栈通常采用的存储方式有：顺序存储结构、链式存储结构。所以B不正确；关于C答案同学们也要知道，栈具有记忆作用。6、队列(1)队列是一个允许在一端进行插入、而在另一端进行删除的线性表。即队列的一个考点是：队列的入队运算是在队尾进行、退队运算是在队头进行的。(2)队列在计算机中进行存储时通常采用的存储方式有：顺序存储结构、链式存储结构。(3)队列的原则是：先进先出、后进后出。(4)循环队列是队列在计算机存储空间中采用顺序存储结构进行存储的一种形式。【考题1】下列关于队列的叙述中正确的是()A在队列中只能插入元素B在队列中只能删除数C队列是先进先出的线性表D队列是先进后出的线性表【答案】：C【解析】：队列是一个先进先出的特殊线性表，其特殊性在于队列的插入是从队尾进行的，删除是从队头进行的。【考题2】一个队列的入队序列是1，2，3，4，则队列的输出序列是()A4，3，2，1B1，2，3，4C1，4，3，2D3，2，4，1【答案】：B【考题3】栈和队列的共同点是()A都是先进后出B都是先进先出C只允许在端点处插入和删除元素D没有共同点【答案】：C【解析】：栈和队列的共同点都是在端点处进行运算的。栈的插入与删除运算都只在线性表的一端进行；队列是一个允许在一端进行插入、而在另一端进行删除的特殊线性表。而与前面所讲的线性表不同，它可以在任意位置进行插入、删除运算。【考题4】线性表在计算机中的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的存储结构。【答案】：顺序【考题5】设某循环队列的容量为50，头指针front=5(指向队头元素的前一位置)，尾指针rear=29(指向对尾元素)，则该循环队列中共有个元素。【答案】：24【解析】：队头指针中不存放元素，从6号空间到29号空间中，总共有24个元素。7、树和二叉树(1)树是一种简单的非线性结构。在树中，所有数据元