典型例题详解.doc

第一章 概述 一、单项选择题 1．（ B ）不是算法的基本特征。 A．可行性 B．长度有限 C．在规定的时间内完成 D．确定性 2．下列关于算法的说法，正确的是（ C ）。 A．算法是最终必须由计算机程序实现 B．算法的可行性是指指令不能有二义性 C．为解决某问题的算法与为该问题编写的程序含义是相同的 D．程序一定是算法 3．下列说法中错误的是（ A ）。 A．空间效率为O（1）的算法不需要任何额外的辅助空间 B．在相同的规模n下，时间复杂度为O（n）的算法在时间上总是优于时间复杂度为O（）的算法 C．所谓时间复杂度是指在最坏情况下，估算算法执行时间的一个上界 D．同一个算法，实现语言的级别越高，执行的效率不一定越低 4．以下关于数据的存储结构的叙述中，正确的有（ D ）。 A．顺序存储方式只能用于存储线性结构 B．顺序存储方式的优点是存储密度大，且插入、删除运算效率高 C．链表的每个结点中都恰好包含一个指针 D．散列法存储的基本思想是由关键字的值决定数据的存储地址 E．散列表的结点只包含数据元素自身的信息，不包含任何指针 5．某算法仅含程序段1和程序段2，程序段1的执行次数，程序段2的执行次数为，则该算法的时间复杂度为（ C ）。 A． B． C． D． 6．以下说法正确的是（ A ）。 A．数据结构的逻辑结构独立于其存储结构 B．数据结构的存储结构独立于该数据结构的逻辑结构 C．数据结构的逻辑结构唯一地决定了该数据结构的存储结构 D．数据结构仅由其逻辑结构和存储结构决定 7．以下说法正确的是（ B ）。 A．数据元素是具有独立意义的最小标识单位 B．原子类型的值不可再分解 C．原子类型的值由若干个数据项值组成 D．结构类型的值不可以再分解 8．设有如下遗产继承规则：丈夫和妻子可以互相继承遗产，子女可以继承父亲和母亲的遗产，子女间不能相互继承，则表示该遗产继承关系最合适的数据结构应该是（ B ）。 A．树 B．图 C．线性表 D．集合 二、判断题 1．数据元素是数据的最小单位。（ F ） 2．数据的逻辑结构是指各数据元素之间的逻辑关系，与物理结构无关。（ T ） 3．算法的时间效率和空间效率往往相互冲突，有时很难两全其美。（ T ） 4．运算的定义依赖于逻辑结构，运算的实现也依赖于逻辑结构而与存储结构无关。（ F ） 5．数据结构是指相互之间存在一种或多种关系的数据元素的全体。（ F ） 6．从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。（ T ） 7．算法和程序都应具有下面一些特征：有输入、有输出、确定性、有穷性、有效性。（ F ） 三、填空题 1．数据的逻辑结构被分为集合、线性结构、树形结构和图形结构四种。 数据的存储结构包括顺序存储结构、链式存储结构、索引存储结构散列（或哈希）存储结构四种。 2．在图状结构中，每个结点的前驱结点和后继结点数可以_____________。 3．时间和空间复杂度在最好和最坏情况下分别是O（1）和O（n!）。 4．一种抽象数据类型包括数据抽象和数据封装两部分。 5．当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的_时间复杂度_。 第二章 线性表 一、选择题 1．线性表中在链式存储中各结点之间的地址（ D ）。 A．必须连续 B．部分地址必须连续 C．不能连续 D．连续与否无所谓 2．将两个各有n个元素的有序线性表归并成一个有序线性表，最少的比较次数是（ A ）。 A．n B．2n-1 C．2n D．n-1 3．线性表中正确的说法是（ D ）。 A．每个元素都有一个直接前驱和一个直接后继 B．线性表至少要求一个元素 C．表中的元素必须按由小到大或由大到小排序 D．除了第一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和直接后继 4．以下说法错误的是（ D ）。 A．求表长、定位这两种运算在采用顺序存储结构时，实现的效率不比采用链式存储结构时实现的效率低 B．顺序存储的线性表可以随机存取 C．由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活 D．线性表的链式存储结构优于顺序存储结构 5．在n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是（ B ）。 A．O(1) B．O(n) C． D． 6．（ A ）是顺序存储结构的优点。 A．存储密度大