1、绪论模拟试卷 1 及答案与解析一、单项选择题下列各题的备选答案中，只有一个是符合题意的。1 以下与数据的存储结构无关的术语是（ ）。（A）循环队列（B）链表（C）哈希表（D）栈2 以下属于逻辑结构的是（ ）。（A）顺序表（B）哈希表（C）有序表（D）单链表3 以下数据结构中，（ ）是非线性数据结构。（A）树（B）字符串（C）队列（D）栈4 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ ）。（A）数据的操作方法（B）数据元素的类型（C）数据元素之间的关系（D）数据的存取方法5 连续存储设计时，存储单元的地址（ ）。（A）一定连续（B）一定不连续（C）不一定连续（D）部分连续，部分不
2、连续6 链式存储设计时，结点内的存储单元地址（ ）。（A）一定连续（B）一定不连续（C）不一定连续（D）部分连续，部分不连续7 可以用（ ）定义一个完整的数据结构。（A）数据元素（B）数据对象（C）数据关系（D）抽象数据类型8 一个算法应该是（ ）。（A）程序（B）问题求解步骤的描述（C）要满足五个基本特性（D）A 和 C9 下面关于算法说法错误的是（ ）。（A）算法最终必须由计算机程序实现（B）为解决某问题的算法与为该问题编写的程序含义是相同的（C）算法的可行性是指指令不能有二义性（D）以上几个都是错误的10 算法的时间复杂度取决于（ ）。（A）问题的规模（B）待处理数据的初态（C）执行的次
3、数（D）A 和 B11 某算法的时间复杂度为 O(n2)，表明该算法的（ ）。（A）问题规模是 n2（B）执行时间等于 n2（C）执行时间与 n2 成正比（D）问题规模与 n2 成正比12 下面说法错误的是（ ）。(1)算法原地工作的含义是指不需要任何额外的辅助空间(2)在相同的规模 n 下，复杂度 O(n)的算法在时间上总是优于复杂度 O(2n)的算法(3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界(4)同一个算法，实现语言的级别越高，执行效率就越低（A）(1)（B） (1)，(2)（C） (1)，(4)（D）(3)13 设 n 是描述问题规模的非负整数，下面程序片段的时间复杂
4、度是（ ）。（A）0(1og 2n)（B） O(n)（C） O(nlog2n)（D）O(n 2)14 以下算法的时间复杂度为（ ）。（A）O(n)（B） O(n2)（C） O(nlog2n)（D）O(1og 2n)15 程序段，其中 n 为正整数，则最后一行的语句频度在最坏情况下是（ ）。（A）O(n)（B） O(nlogn)（C） O(n3)（D）O(n 2)16 有以下算法，其时间复杂度为（ ）。17 以下算法中加下划线语句的执行次数为（ ）。（A）n(n+1)（B） n（C） n+1（D）n 218 计算机所处理的数据一般具备某种内在联系性，这是指( )。（A）数据和数据之间存在某种关系
5、（B）元素和元素之间存在某种关系（C）元素内部具有某种结构（D）数据项和数据项之间存在某种关系19 算法的时间复杂度与( )有关。（A）问题规模（B）计算机硬件性能（C）编译程序质量（D）程序设计语言20 顺序表的长度与( ) 有关。（A）线性表中有多少个结点（B）每个结点有多少个字段（C）每个结点中各字段的类型（D）存储线性表的数组类型21 在解决计算机主机和打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写人该缓冲区，而打印机则从该缓冲区中取出数据打印。这个缓冲区应该是一个( )结构。（A）栈（B）队列 （C）数组（D）线性表22 设 n 个元素的进栈序列是 P
6、1，P2 ，Pn，出栈序列是 l，2，3，n。若Pn=1，则 Pi(1in)的值( )。（A）是 i （B）是 ni （C）是 ni+1（D）有多种可能23 如果在表示树的孩子一兄弟链表中有 6 个空的左指针域，7 个空的右指针域，5个结点左、右指针域都为空，则该树中叶子的个数( )。（A）有 7 个 （B）有 6 个（C）有 5 个 （D）不能确定24 若图的邻接矩阵中主对角线上的元素全是 0，其余元素全是 1，则可以断定该图一定( )。（A）是无向图（B）不是带权图（C）是有向图（D）是完全图25 在平衡二叉：H序树中，每个结点( )。（A）左子树结点个数和右子树结点个数相差不超过 1（B
7、）平衡因子为 O（C）左子树度数和右子树度数相差不超过 1（D）左子树深度(高度) 和右子树深度 (高度) 相差不超过 126 排序过程中，元素的移动次数与各元素原始的排列顺序无关的排序方法是( )排序。（A）简单选择（B）快速（C）堆（D）归并27 如果( ) ，则称这种排序方法是不稳定的。（A）排序前后，排序码相同的元素在线性表中的相对位置可能会被颠倒（B）排序前后，排序码相同的元素在线性表中的相对位置一定会被颠倒（C）对同一个线性表，每次排序的结果可能不相同（D）排序结果不可预测二、综合题28 试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。29 对于两
8、种不同的数据结构，逻辑结构或物理结构一定不相同吗?30 请简要列出影响一个算法（或程序）时间效率的主要因素，并指出其中与算法（或程序）本身直接有关的因素。31 若 5 个元素 A,B,C,D,E 按此先后次序进入一初始为空的堆栈，请写出在所有可能的出栈序列，第一个元素为 C、且第二个元素为 D 的出栈序列。32 有人说，采用折半查找法一定比采用顺序查找法的时间效率高，你认为如何？请说明你的理由。33 顺序队列如何解决假溢出问题。绪论模拟试卷 1 答案与解析一、单项选择题下列各题的备选答案中，只有一个是符合题意的。1 【正确答案】 D【试题解析】 存储结构有顺序存储、链式存储、索引存储和散列(H
9、ash) 存储，栈是一种抽象数据类型，可采用顺序存储或链式存储，而循环队列是首尾相连的顺序表。【知识模块】 绪论2 【正确答案】 C【试题解析】 顺序表、哈希表和单链表都是存储结构。而有序表指关键字有序的线性表，仅描述结点之间的逻辑关系，既可以链式存储也可以顺序存储。【知识模块】 绪论3 【正确答案】 A【试题解析】 树是典型的非线性数据结构，其他选项都属于线性数据结构。【知识模块】 绪论4 【正确答案】 C【试题解析】 存储数据时，不仅要存储数据元素的值，还要存储数据元素之间的关系。【知识模块】 绪论5 【正确答案】 A【试题解析】 连续存储不一定是顺序存储，也可能是静态链表，但地址的分配一
10、定是连续的。【知识模块】 绪论6 【正确答案】 A【试题解析】 链式存储设计时，各个结点的存储空间可以不连续，但是结点内的存储单元地址则必须连续。【知识模块】 绪论7 【正确答案】 D【试题解析】 抽象数据类型描述了数据的逻辑结构和抽象运算，从而构成了一个完整的数据结构定义。【知识模块】 绪论8 【正确答案】 B【试题解析】 程序不一定满足有穷性，如死循环、操作系统等，而算法必须有穷。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。【知识模块】 绪论9 【正确答案】 D【试题解析】 A，对算法没有此强制要求。B，算法不等于程序。 C，可行性的解释错误。【知识模块】 绪论10 【正确
11、答案】 D【试题解析】 算法的时间复杂度不仅取决于问题的规模，还和待处理数据的初态有关。【知识模块】 绪论11 【正确答案】 C【试题解析】 时间复杂度是问题规模 n 的函数，记为 T(n)=o(f(n)，T(n)的增长率与 f(n)的增长率相同。T(n)=O(n 2)表示 T(n)=mn2(m 为常量)，其问题规模仍为 n而不是 n2。【知识模块】 绪论12 【正确答案】 A【试题解析】 (1)算法原地工作是指算法所需辅助空间是常量。(2)时间复杂度为0(n)的算法，必然总是优于复杂度为 O(2n)的算法，文中并非指程序具体的执行时间。(3)时间复杂度总是考虑在最坏的情况下的时间复杂度，以保
12、证算法的运行时间不会比它更长。(4)对于同一个算法，实现语言的级别越高，执行效率就越低。【知识模块】 绪论13 【正确答案】 A【试题解析】 在程序中，执行频率最高的语句为“x=2*x”。设该语句共执行了 t 次，则 2t+1=n2，故 t=log2(n2)-1=log 2n-2，得 T(n)=O(log2n)。【知识模块】 绪论14 【正确答案】 D【试题解析】 基本运算是语句 i=i*2，设其执行时间为 T(n)，则有，2 T(n)n，即T(n)Iog2nO(log2n)【知识模块】 绪论15 【正确答案】 D【试题解析】 当所有相邻元素都为逆序时，则最后一行的语句每次都会执行。【知识模块
13、】 绪论16 【正确答案】 C【知识模块】 绪论17 【正确答案】 A【知识模块】 绪论18 【正确答案】 B【知识模块】 绪论19 【正确答案】 A【知识模块】 绪论20 【正确答案】 A【知识模块】 绪论21 【正确答案】 B【知识模块】 绪论22 【正确答案】 C【知识模块】 绪论23 【正确答案】 C【知识模块】 绪论24 【正确答案】 D【知识模块】 绪论25 【正确答案】 D【知识模块】 绪论26 【正确答案】 A【知识模块】 绪论27 【正确答案】 A【知识模块】 绪论二、综合题28 【正确答案】 线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为 O(
14、n)；而在链式存储方式下，插入和删除的时间复杂度都是 O(1)。【知识模块】 绪论29 【正确答案】 应该注意到，数据的运算也是数据结构的一个重要方面。对于两种不同的数据结构，它们的逻辑结构和物理结构完全有可能相同。比如二叉树和二叉排序树，二叉排序树可以采用二叉树的逻辑表示和存储方式，前者通常用来表示层次关系，而后者通常用于排序和查找。虽然它们的运算都有建立树、插入结点、删除结点和查找结点等，但是对于二叉树和二叉排序树，这些运算的定义是不同的，以查找结点为例，二叉树的时间复杂度为 O(n)，而二叉排序树的时间复杂度为O(log2n)。【知识模块】 绪论30 【正确答案】 影响一个算法（或程序）
15、时间效率的主要因素有：*算法涉的问题的规模大小；*编译程序功能的强弱以及所产生的机器代码质量的优劣；*机器执行一条指令的时间长短；*算法（或程序）中诸如循环语句的那些关键语句的执行次数。【知识模块】 绪论31 【正确答案】 CDEBA CDBAE CDBEA【知识模块】 绪论32 【正确答案】 这种说法不正确。当被查找的对象处在序列的前部，比如查找序列的第一个元素，折半查找法的时间效率比顺序查找法要低。【知识模块】 绪论33 【正确答案】 在顺序队列中，由于数组空间不够而产生的溢出叫真溢出；顺序队列因多次人队列和出队列操作后出现的有存储空间，但不能进行人队列操作的溢出称为假溢出。假溢出是由于队尾 rear 的值和队头 front 的值不能由所定义数组下界值自动转为数组上界值而产生的解决的办法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列，因此，顺序队列通常都采用顺序循环队列结构。【知识模块】 绪论
