数据结构历年试题及答案汇编

1、数据结构基础历年试题汇编一、2006年上半年 在以下情形中，_(35)_适合于采用队列数据结构。(35)A监视一个火车票售票窗口等待服务的客户D描述一个组织中的管理机构C统计一个商场中的顾客数D监视进入某住宅楼的访客 元素3、1、2依次全部进入一个栈后，陆续执行出栈操作，得到的出栈序列为_(36)_。(36)A3、2、1 B3、1、2C1、2、3 D2、1、3 一棵二叉树如下图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点(根结点的下标为1，若某结点的下标为i，则其左孩子位于下标2i处、右孩子位于下标2i+1处)，则该数组的大小至少为_(37)_；若采用二叉链表存储该二叉树(各

2、 个结点包括结点的数据、左孩子指针、右孩子指针)，则该链表中空指针的数目为_(38)_。(37)A6B10C12D15(38)A6B7 C12D14 以下各图用树结构描述了7个元素之间的逻辑关系，其中_(39)_适合采用二分法查找元素。 对于二维数组a04,15，设每个元素占1个存储单元，且以行为主序存储，则元素a2,1相对于数组空间起始地址的偏移量是_(40)_。(40)A5 B10C15D25 若n表示问题的规模、O(f(n)表示算法的时间复杂度随n变化的增长趋势，则算法时间复杂度最小的是_(59)_。(59)AO(n2)BO(n)C O(log n)DO(nlog n) 二、2006年下

3、半年  在链表结构中，采用 （35） 可以用最少的空间代价和最高的时间效率实现队列结构。 （35）A.  仅设置尾指针的单向循环链表      B.  仅设置头指针的单向循环链表 C.  仅设置尾指针的双向链表          D.  仅设置头指针的双向链表   若需将一个栈 S 中的元素逆置，则以下处理方式中正确的是 （36） 。 （36）A.  将栈 S 中元素依次出栈并

4、入栈 T，然后栈 T 中元素依次出栈并进入栈 S B.  将栈 S 中元素依次出栈并入队，然后使该队列元素依次出队并进入栈 S C.  直接交换栈顶元素和栈底元素 D.  直接交换栈顶指针和栈底指针   已知 N 个数已存入数组 A1.M的前 N 个元素中（N<M），为在 Ai（1iN）之前插入一个新数，应先 （37） ，以挪出一个空闲位置插入该数。 （37）A.  从 Ai开始直到 A1，每个数向后移动一个位置 B.  从 A1开始直到 Ai，每个数向后移动一个位置 C.  从 Ai开始直到 AN，每个数向前移动一个

5、位置 D.  从 AN开始直到 Ai，每个数向后移动一个位置   若某二叉树的先序遍历序列和中序遍历序列分别为 PBECD、BEPCD，则该二叉 树的后序遍历序列为 （38） 。 （38）A. PBCDE            B. DECBP       C. EBDCP        D. EBPDC   无向图的邻接矩阵一

6、定是 （39） 。 （39）A.  对角矩阵       B.  稀疏矩阵    C.  三角矩阵    D.  对称矩阵   对具有 n 个元素的有序序列进行二分查找时， （40） 。 （40）A.  查找元素所需的比较次数与元素的位置无关 B.  查找序列中任何一个元素所需要的比较次数不超过log2(n+1) C.  元素位置越靠近序列后端，查找该元素所需的比较次数越少 D.  元素

7、位置越靠近序列前端，查找该元素所需的比较次数越少 三、2007年上半年 若将下图(a)所示的无向图改为完全图，则还需要增加 （36） 条边；下图(b)的邻接矩阵表示为 （37） （行列均以A、B、C、D、E为序）。（36）A. 1 B. 2 C. 5 D. 15 （37） 若线性表（23, 14, 45, 12, 8, 19, 7）采用散列法进行存储和查找。设散列函数为H(Key)=Key mod 7并采用线性探查法（顺序地探查可用存储单元）解决冲突，则构造的散列表为 （38） ，其中，mod表示整除取余运算。 （38） 在执行递归过程时，通常使用的数据结构是 （39） 。 （39）A. 堆栈

8、(stack) B.队列(queue) C.图 (graph) D. 树(tree) 用二分法来检索数据，最确切的说法是 （40） 。 （40）A. 仅当数据随机排列时，才能正确地检索数据 B. 仅当数据有序排列时，才能正确地检索数据 C. 仅当数据量较大时，才能有效地检索数据 D. 仅当数据量较小时，才能有效地检索数据 若原始数据序列（23,4,45,67,12,8,19,7）采用直接插入排序法（顺序地将每个元素插入到它之前的适当位置）排序，则进行完第4趟后的排序结果是 （41） 。 （41）A. 4, 8,45, 23,67,12, 19,7 B. 4,7,8,12,23, 45,67,1

9、9 C. 4,12,8,19,7,23, 45,67 D. 4,12,23,45,67,8,19,7 对下图所示的二叉树进行后序遍历（左子树、右子树、根结点）的结果是 （42） 。 （42）A. 5 2 3 4 6 1 B. 5 2 3 4 1 6 C. 2 6 4 1 3 5 D. 2 5 6 4 3 1 数组A-5.5, 0.8按列存储。若第一个元素的首地址为100，且每个元素占用4个存储单元，则元素A2,3的存储地址为 （43） 。 （43）A. 244 B. 260 C. 364 D. 300 四、2007年下半年 n个元素依次全部进入栈后，再陆续出栈并经过一个队列输出。那么， （36

10、） 。（36）A. 元素的出队次序与进栈次序相同 B. 元素的出队次序与进栈次序相反 C. 元素的进栈次序与进队次序相同 D. 元素的出栈次序与出队次序相反 若一个栈以向量V1.n存储，且空栈的栈顶指针top为n+1，则将元素x入栈的正确操作是 （37） 。（37）A. top = top+1; Vtop = x; B. Vtop = x; top = top+1; C. top = top-1; Vtop = x; D. Vtop = x; top = top-1; 广度优先遍历的含义是：从图中某个顶点v出发，在访问了v之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问

11、它们的邻接点，且“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。 （38） 是下图的广度优先遍历序列。（38）A. 1 2 6 3 4 5B. 1 2 3 4 5 6 C. 1 6 5 2 3 4 D. 1 6 4 5 2 3 对于长度为11的顺序存储的有序表，若采用折半查找（向下取整），则找到第5个元素需要与表中的 （39） 个元素进行比较操作（包括与第5个元素的比较）。（39）A. 5 B. 4C. 3 D. 2 与单向链表相比，双向链表 （40） 。（40）A. 需要较少的存储空间 B. 遍历元素需要的时间较短 C. 较易于访

12、问相邻结点 D. 较易于插入和删除元素 如果待排序序列中两个元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。 （41） 是稳定的排序方法，因为这种方法在比较相邻元素时，值相同的元素并不进行交换。（41）A. 冒泡排序 B. 希尔排序 C. 快速排序 D. 简单选择排序 对下图所示的二叉树进行中序遍历（左子树、根、右子树）的结果是 （42） 。（42）A. 2 5 3 4 6 1 B. 2 5 3 4 1 6 C. 2 6 5 4 1 3 D. 2 6 4 5 3 1 采用一维数组S存储一个n阶对称矩阵A的下三角部分（按行存放，包括主对角线），设元素Aij存放在Sk

13、 中（i、j、k均从1开始取值），且S1=A11，则k与i、j的对应关系是 （43） 。例如，元素A32存在S5中。（43）A. B. C. D. 五、2008年上半年 若二维数组 P1.5, 0.8的首地址为 base，数组元素按行存储，且每个元素占用 1个存储单元，则元素 P3, 3在该数组空间的地址为（32）。（32）A. base+13 B. base+16 C. base+18 D. base+21设初始栈为空，s 表示入栈操作，x 表示出栈操作，则（33） 是合法的操作序列。（33）A. sxxsssxxx B. xxssxxss C. sxsxssxx D. xssssxxx 满

14、二叉树的特点是每层上的结点数都达到最大值，因此对于高度为 h(h>1)的满二叉树，其结点总数为 （36） 。对非空满二叉树，由根结点开始，按照先根后子树、先左子树后右子树的次序，从 1、2、3、依次编号，则对于树中编号为 i 的非叶子结点，其右子树的编号为 （37） （高度为 3 的满二叉树如下图所示）。（36）A. 2 B. 2h-1 C. 2h 1 D. 2h-1+1（37）A. 2i B. 2i-1 C. 2i+1 D. 2i+2 在数据结构中，结点（数据元素）及结点间的相互关系组成数据的逻辑结构。按逻辑结构的不同，数据结构通常可分为（38） 两类。（38）A.线性结构和非线性结构

15、 B.紧凑结构和稀疏结构 C.动态结构和静态结构 D.内部结构和外部结构采用哈希（或散列）技术构造查找表时，需要考虑冲突（碰撞）的处理，冲突是指（39）。（39）A.关键字相同的记录被映射到不同的哈希地址 B.关键字依次被映射到编号连续的哈希地址C.关键字不同的记录被映射到同一个哈希地址D.关键字的数目超过哈希地址的数目数据结构中的树最适合用来表示（40）的情况。（40）A.数据元素有序 B.数据元素之间具有多对多关系 C.数据元素无序 D.数据元素之间具有一对多关系某循环队列的容量为M，队头指针指向队头元素，队尾指针指向队尾元素之后，如下图所示（M=8），则队列中的元素数目为（41）（MOD

16、 表示整除取余运算）。（41）A. rear front B. front rear C. (rear front + M) MOD M D. (front rear + M) MOD M二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于根结点的值；其左、右子树本身就是两棵二叉排序树。根据该定义，对一棵非空的二叉排序树进行 （42）遍历，可得到一个结点元素的递增序列。（42）A.先序（根、左、右） B.中序（左、根、右）C.后序（左、右、根） D.层序（从树根开始，按层次） 对于 n 个元素

17、的关键字序列k1,k2,kn，若将其按次序对应到一棵具有 n 个结点的完全二叉树上，使得任意结点都不大于其孩子结点(若存在孩子结点)，则称其为小顶堆。根据以上定义，（43）是小顶堆。六、2008年下半年设数组 a1.6,0.9的元素以行为主序存放，每个元素占用一个存储单元，则数组元素 a3,3的地址为 （34） 。（34）A. a+23 B. a+27 C. a+39 D. a+35若字符串 s 的长度为 n（n >1）且其中的字符互不相同，则 s 的长度为 2 的子串有（35）个。（35）A. n B. n-1 C. n-2 D. 2若线性表（24, 13, 31, 6, 15, 18

18、, 8）采用散列（Hash）法进行存储和查找，设散列函数为 H(Key)=Key mod 11，则构造散列表时发生冲突的元素为（36）。（其中的 mod表示整除取余运算）（36）A. 24 和 13 B. 6和 15 C. 6和24 D. 18 和 8线性表采用顺序存储结构，若表长为m，且在任何一个合法插入位置上进行插入操作的概率相同，则插入一个元素平均移动（37）个元素。若二叉树的先序遍历序列与中序遍历序列相同且树中结点数大于 1，则该二叉树的（38）。（38）A.只有根结点无左子树 B.只有根结点无右子树C.非叶子结点只有左子树 D.非叶子结点只有右子树由关键字序列（12，7，36，25，

19、18，2）构造一棵二叉排序树（初始为空，第一个关键字作为根结点插入，此后对于任意关键字，若小于根结点的关键字，则插入左子树中，若大于根结点的关键字，则插入右子树中，且左、右子树均为二叉排序树），该二叉排序树的高度（层数）为（39）。（39）A. 6 B. 5 C. 4 D. 3对连通图进行遍历前设置所有顶点的访问标志为 false（未被访问），遍历图后得到一个遍历序列，初始状态为空。深度优先遍历的含义是：从图中某个未被访问的顶点 v 出发开始遍历，先访问 v 并设置其访问标志为 true（已访问），同时将 v 加入遍历序列，再从 v 的未被访问的邻接顶点中选一个顶点，进行深度优先遍历；若 v

20、的所有邻接点都已访问，则回到 v 在遍历序列的直接前驱顶点，再进行深度优先遍历，直至图中所有顶点被访问过。 （40）是下图的深度优先遍历序列。（40）A. 1 2 3 4 6 5 B. 1 2 6 3 4 5 C. 1 6 2 5 4 3 D. 1 2 3 4 5 6 栈的运算特点是后进先出。元素 a、b、c、d 依次入栈，则不能得到的出栈序列是 （41）。（41）A. a b c d B. c a b d C. d c b a D. b c d a两个递增序列 A 和 B 的长度分别为 m 和 n（m<n），将二者归并为一个长度为 m+n的递增序列时，（42），归并过程中元素的比较次数

21、最少。（42）A.当 A 的最大元素大于 B 的最大元素时B.当 A 的最大元素小于 B 的最小元素时C.当 A 的最小元素大于 B 的最小元素时D.当 A 的最小元素小于 B 的最大元素时 在任意一棵非空的二叉树中，终端结点（叶子）的数目总是比具有两个孩子的非终端结点的数目（43） 。（43）A. 多 0 个 B. 多 1 个 C. 多 2 个 D. 多 3 个七、2009年上半年以下关于排序算法的叙述中，正确的是 （36）。 （36）A.冒泡排序法中，元素的交换次数与元素的比较次数一定相同 B.冒泡排序法中，元素的交换次数不少于元素的比较次数C.简单选择排序中，关键字相同的两个记录在排序前

22、后的相对位置一定不变 D.简单选择排序中，关键字相同的两个记录在排序前后的相对位置可能交换设有一个初始为空的栈，若输入序列为1、2、3、n（n>3），且输出序列的第一个元素是 n-1，则输入序列中所有元素都出栈后， （37）。 （37）A.元素 n-2 一定比 n-3 先出栈B.元素 1n-2 在输出序列中的排列是不确定的C.输出序列末尾的元素一定为 1D. 输出序列末尾的元素一定为 n某二叉树的先序遍历序列为 ABFCDE、中序遍历序列为 BFADCE，则该二叉树根的左孩子和右孩子结点分别是 （38）。（38）A. B 和 F B. F 和 B C. B 和 C D. C 和 B调用递

23、归过程或函数时，处理参数及返回地址需要用一种称为 （39） 的数据结构。（39）A.队列 B.栈 C.多维数组 D.顺序表已知对称矩阵 An*n（Ai,j=Aj,i）的主对角线元素全部为 0，若用一维数组 B 仅存储矩阵 A 的下三角区域的所有元素（不包括主对角线元素），则数组 B 的大小为 （40） 。（40）A. n(n-1) B. n2/2 C. n(n-1)/2 D. n(n+1)/2设 S 是一个长度为 5 的字符串，其中的字符各不相同，则计算 S 中互异的非平凡子串（非空且不同于 S 本身）数目的算式为（41）。（41）A. 5+4+3+2+1 B. 5+4+3+2 C. 4+3+

24、2+1 D. 4+3+2折半（二分）查找方法对查找表的要求是 （42）。（42）A.链表存储结构，元素有序排列 B.链表存储结构，元素无序排列 C.顺序存储结构，元素有序排列 D.顺序存储结构，元素无序排列若无向连通图 G 具有 n 个顶点，则以下关于图 G 的叙述中，错误的是 （43） 。A. G 的边数一定多于顶点数 B. G 的生成树中一定包含 n 个顶点C.从 G 中任意顶点出发一定能遍历图中所有顶点D. G 的邻接矩阵一定是 n 阶对称矩阵 算法是问题求解过程的精确描述，它为解决某一特定类型的问题规定了一个运算过程。以下关于算法的叙述中，错误的是（62） 。（62）A.流程图（flo

25、w chart）是算法的一种图形表示方法B.用伪代码描述的算法易于转换成程序C.用 N/S 盒图可以保证算法的良好结构（即由顺序、选择和重复结构来表示算法）D.用 E-R 图可以同时描述算法步骤和数据模型 下表列出了数字 09 的某种二进制编码值及其在某类应用中出现的概率，这种编码的平均位数大约为 （63） 。八、2009年下半年设数组a0.m,1.n的每个元素占用1个存储单元，若元素按行存储，则数组元素ai,j（0im，1jn）相对于数组空间首地址的偏移量为（32） 。（32）A. (i+1)*n+j B. i*n+j-1 C. i*m+j D. i*(m+1)+j-1 算术表达式a+b*(

26、c+d/e)可转换为后缀表达式 （35） 。 （35）A. abcde*/+ B. abcde/+*+ C. abcde*+/+ D. abcde/*+ 以下关于算法的叙述中，错误的是 （36） 。 （36）A. 对同一个算法采用不同程序语言实现，其运行时间可能不同 B. 在不同硬件平台上实现同一个算法时，其运行时间一定是相同的C. 对非法输入的处理能力越强的算法其健壮性越好 D. 算法最终必须由计算机程序实现 栈和队列都是线性的数据结构。以下关于栈和队列的叙述中，正确的是 （37） 。 （37）A. 栈适合采用数组存储，队列适合采用循环单链表存储B. 栈适合采用单链表存储，队列适合采用数组存

27、储C. 栈和队列都不允许在元素序列的中间插入和删除元素D. 若进入栈的元素序列确定，则从栈中出来的序列也同时确定 （38） 并不是算法必须具备的特性。 （38）A. 可行性 B. 可移植性 C. 确定性 D. 有穷性 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点（即叶子结点）个数是（39） 。（39）A. 不确定 B. 9 C. 11 D. 15 对具有n个元素的顺序表（采用顺序存储的线性表）进行（40） 操作，其耗时与n的大小无关。A. 在第i（1<=i<=n）个元素之后插入一个新元素 B. 删除第i（1<=i<=n）个元素 C. 对顺序表中的

28、元素进行排序 D. 访问第i（1<=i<=n）个元素的前驱和后继 以下关于图及其存储结构的叙述中，正确的是 （41） 。 A. 无向图的邻接矩阵一定是对称的 B. 有向图的邻接矩阵一定是不对称的C. 无向图采用邻接表存储更节省存储空间D. 有向图采用邻接表存储更节省存储空间 对于n个元素的关键字序列K1,K2,Kn，若有Ki<=K2i且Ki<=K2i+1（i=1,2, ,2i+1<=n），则称其为小根堆。以下关于小根堆及其元素关系的叙述中，错误的是（42） 。（42）A. 关键字序列K1,K2,Kn呈非递减排序时一定为小根堆 B.小根堆中的序列K1,K2,K4,K

29、2j（2j<=n）一定为非递减序列 C.小根堆中元素K2i与K2i+1(2i<=n,2i+1<=n)之间的大小关系不能确定 D.小根堆的最后一个元素一定是序列的最大元素若构造哈希表时不发生冲突，则给定的关键字与其哈希地址之间的对应关系是 （43）。（其中n>1且m>1）（43）A.1:1 B.1:n C.n:1 D.n:m九、2010年上半年若在单向链表上，除访问链表中所有结点外，还需在表尾频繁插入结点，那么采用（31）最节省时间。（31）A.仅设尾指针的单向链表 B.仅设头指针的单向链表C.仅设尾指针的单向循环链表 D.仅设头指针的单向循环链表表达式“a*(b

30、c)+d”的后缀式为（32）。（32）A. abcd*-+ B. ab*c-d+ C. ab-cd+* D. abc-*d+已知某二叉树的先序遍历序列是 ABDCE，中序遍历序列是 BDAEC，则该二叉树为（33）。对于二维数组 a1.6,1.8，设每个元素占 2 个存储单元，且以列为主序存储，则元素 a4,4相对于数组空间起始地址的偏移量是（34）个存储单元。（34）A. 28 B. 42 C. 48 D. 54已知某带权图 G 的邻接表如下所示，其中表结点的结构为：则图 G 是（35）。（35）A.无向图 B.完全图 C.有向图 D.强连通图已知栈 S 初始为空，对于一个符号序列a1a2a

31、3a4a5（入栈次序也是该次序），当用I表示入栈、O表示出栈，则通过栈S得到符号序列a2a4a5a3a1的操作序列为（36）。（36）A. I O I I O O I O O I B. I I O I O I O I O O C. I O O I I O I O I O D. I I O I I O I O O O队列是一种按“先进先出”原则进行插入和删除操作的数据结构。若初始队列为空，输入序列为 a b c d e，则可得到的输出序列为（37）。（37）A. abcde B.abdce C.edcba D. edabc 对于n个元素的关键字序列k1, k2,.,kn，当且仅当满足关系时称为小

32、根堆（小顶堆）。以下序列中， （38） 不是小根堆。（38）A. 12, 20, 36, 48, 25, 50, 40 B. 12, 36, 20, 48, 40, 25, 50C. 12, 20, 25, 36, 40, 48, 50 D. 12, 36, 20, 48, 25, 50, 40十、2010年下半年l 以下关于哈希表的叙述中，错误的是（36） 。（36）A.哈希表中元素的存储位置根据该元素的关键字值计算得到 B.哈希表中的元素越多，插入一个新元素发生冲突的可能性越小 C.哈希表中的元素越多，插入一个新元素发生冲突的可能性越大 D.哈希表中插入新元素发生冲突时，需要与表中某些元素进行比较l 下三角矩阵A08，08如下图所示，若将其下三角元素（即行下标不小于列下标的所有元素）按列压缩存储在数组M0m中，即A0,0存储在M0、A1,0存储在M1、A2,0存储在M2，A8,8存储在M44，则元素A5,5存储在（37） 。若将其下三角元素按列压缩存储在数组M0m中，即A0,0存储在M0、A1,0存储在M1、A1,2存储在M2，A8,8存储在M44，则元素A5,5存储在（38） 。 （37）A.M15 B.M20 C.M35 D.M39（38）A.M1