下载文档原格式
数据结构与算法-模拟试题3一、单项选择题（每个题只有一个答案是正确的，请将正确的答案填写到括号内。
本题共15个小题，每小题3分，共45分）1. 下面的说法正确的是（）。
A.数据结构可以分成逻辑结构和线性结构B.数据的逻辑结构是指数据及其逻辑结构在计算机中的表示C.从逻辑结构角度数据结构可以分为集合、线性结构、树结构和图结构四类D.数据的存储结构是从具体问题抽象出来的数学模型2. 线性表采用链式存储时，存储空间（）。
A．必须是不连续的B．连续与否均可C．必须是连续的D．和头结点的存储地址相连续3.顺序循环队列容量为20，队头表示第一个元素的位置，队尾表示最后一个元素的下一个位置，当队头为12，队尾为5的时候，队列中共有（）个元素。
A.15B.14C.12D.134. 设计一个判别表达式中括号是否配对的算法，采用（）数据结构最佳。
A. 顺序表B. 链表C. 队列D. 栈5. 下列有关串的操作中，（）不是串的常用操作。
A.连接（concat）B.求子串（substring）C.插入（insert）D.求长度(length)6. 广义表GL=(a, (a))的表头是（）。
A. aB. (a)C. ()D. ((a))7.二叉树高度为k，第1层到第k-1层每层都是满的，第k层结点数不满，但该层结点从左到右满放，则该二叉树为（）。
A. 斜树B. 有序树C. 满二叉树D. 完全二叉树8.将一棵树转换为二叉树后，该转换后的二叉树的特点是（）。
A. 没有右子树B. 没有左子树C. 左右子树都有D. 每层上只有一个结点9. 关于有向图的的说法错误的是（）。
A. 有向图中顶点v的入度(indegree)是以顶点v为终点（弧头）的弧的数目B. 有向图中顶点v的出度(outdegree)是以顶点v为始点（弧尾）的弧的数目C. 有向图中各顶点的入度之和等于各顶点的出度之和D. 有向图中各顶点入度之和等于弧数e的2倍10. 在无向图的邻接表存储结构中插入一个顶点和一条边，不需要进行的操作是（）。
国家二级C语言（数据结构与算法）机试模拟试卷1(题后含答案及解析)题型有：1. 选择题选择题1．算法具有五个特性，以下选项中不属于算法特性的是A．有穷性B．简洁性C．可行性D．确定性正确答案：B解析：算法的五个特性分别是：有穷性、可行性、确定性、输入和输出。
知识模块：数据结构与算法2．算法的有穷性是指A．算法程序的运行时间是有限的B．算法程序所处理的数据量是有限的C．算法程序的长度是有限的D．算法只能被有限的用户使用正确答案：A解析：算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。
知识模块：数据结构与算法3．算法的时间复杂度是指A．算法的执行时间B．算法所处理的数据最C．算法程序中的语句或指令条数D．算法在执行过程中所需要的基本运算次数正确答案：D解析：算法的时间复杂度，是指执行算法所需要的计算工作量。
算法的工作量可以用算法在执行过程中所需基本运算的执行次数来度量。
知识模块：数据结构与算法4．对存储器按字节进行编址，若某存储器芯片共有10根地址线，则该仔储器芯片的存储容量为A．1kbB．2kbC．4kbD．8kb正确答案：A解析：10根地址线，每根地址线有0和1两种情况，地址范围就是2的10次方=1024=1K。
知识模块：数据结构与算法5．磁盘处于写保护状态时其中的数据A．不能读出，不能删改B．可以读出，不能删改C．不能读出，可以删改D．可以读出，可以删改正确答案：B解析：磁盘处于写保护状态时其中的数据可以读出来，但是不能修改和删除。
知识模块：数据结构与算法6．在Windows环境下，单击当前窗口中的按钮“”，其功能是A．讲当前应用程序转为后台运行B．退Windows后再关机C．终止当前应用程序的运行D．退出Windows后重新启动计算机正确答案：C解析：在Windows中，单击窗口中的按钮“”表示关闭当前运行的程序。
知识模块：数据结构与算法7．下列描述中正确的是A．数据的逻辑结构与存储结构必定是一一对应的B．由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构C．程序设计语言中的数据一般是顺序存储结构，因此，利用数组只能处理线性结构D．以上三种说法都不对正确答案：D解析：数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。
数据结构c语言版试题大全(含答案)数据结构C语言版试题大全（含答案）第一章：基本概念与算法设计1.1 数据结构的定义与特点数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，它包括了数据的存储、组织和管理方式。
数据结构的特点包括以下几个方面：- 数据元素之间存在某种关系，构成逻辑结构- 对数据元素的操作对应于对其逻辑结构的操作- 数据结构有存储结构，包括顺序存储结构和链式存储结构- 算法是对数据结构的操作步骤的描述和实现1.2 算法的基本概念算法是解决特定问题或完成特定任务的一系列操作步骤。
算法的基本概念包括以下几个方面：- 有穷性：算法必须能在有限步骤内完成- 确定性：算法的每一步骤必须有确定的含义和结果- 可行性：算法的每一步骤必须可行，能够通过执行有限次数实现- 输入：算法接受的输入数据是原始问题的实例- 输出：算法产生的输出数据与输入有明确的关系1.3 算法的描述方法算法可以用自然语言、伪代码或流程图来描述。
常用的伪代码描述方法包括结构化语言和算法描述语言，结构化语言包括顺序结构、分支结构和循环结构。
第二章：线性结构2.1 线性表的定义与基本操作线性表是n个数据元素的有限序列，其中相邻元素之间存在唯一的前驱和后继关系。
线性表的基本操作包括插入、删除、查找和修改等。
2.2 数组与广义表数组是指具有相同数据类型的一组数据元素的集合，可以通过下标访问元素。
广义表是线性表的推广，其中元素可以是基本数据类型或另一个广义表。
第三章：树与二叉树3.1 树的定义与基本术语树是n（n≥0）个结点的一个有限集合，其中满足以下条件：- 有且仅有一个特定的称为根的结点- 其余结点可分为m（m≥0）个互不相交的有限集合，每个集合本身又是一棵树3.2 二叉树的定义与性质二叉树是指每个结点最多有两个子结点的树结构。
二叉树的性质包括以下几个方面：- 深度为k的二叉树最多有2^k-1个结点- 一棵二叉树的第i层最多有2^(i-1)个结点- 在二叉树的第i层上至多有2^(n-i+1)-1个结点（n为树的深度）第四章：图4.1 图的基本概念与术语图是由顶点的有穷非空集合和边的有穷集合组成的。
国家二级C语言（数据结构与运算）机试模拟试卷1(题后含答案及解析)题型有：1. 选择题选择题1．对长度为n的线性表排序，在最坏情况下，比较次数不是n(n-1)/2的排序方法是A．快速排序B．冒泡排序C．直接插入排序D．堆排序正确答案：D解析：各种排序方法中最坏情况下需要比较的次数分别为：冒泡排序n(n-1)/2、快速排序n(n-1)/2、简单插入排序n(n-1)/2、希尔排序O(n1.5)、简单选择排序n(n-1)/2、堆排序O(nlog2n)。
知识模块：数据结构与运算2．下列关于栈的叙述正确的是A．栈按“先进先出”组织数据B．栈按“先进后出”组织数据C．只能在栈底插入数据D．不能删除数据正确答案：B解析：栈是限定在一端进行插入和删除的线性表，允许进行插入和删除元素的一端称为栈顶，另一端称为栈底。
栈是按照“先进后出”的原则组织数据的。
知识模块：数据结构与运算3．某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是A．10B．8C．6D．4正确答案：C解析：根据二叉树的性质，在任意二叉树中，度为0的结点总是比度为2的结点多一个。
知识模块：数据结构与运算4．下列叙述中正确的是A．算法复杂度是指算法控制结构的复杂程度B．算法复杂度是指设计算法的难度C．算法的时间复杂度是指设计算法的工作量D．算法的复杂度包括时间复杂度与空间复杂度正确答案：D解析：算法复杂度，即算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。
一个算法的评价主要从时间复杂度和空间复杂度来考虑。
算法的时间复杂度是指执行算法所需要的计算工作量。
空间复杂度是指算法在计算机内执行时所需存储空间的度量。
知识模块：数据结构与运算5．下列叙述中正确的是A．循环队列有队头和队尾两个指针，因此，循环队列是非线性结构B．在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况C．在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况D．循环队列中元素的个数是由队头指针和队尾指针共同决定正确答案：D解析：循环队列中元素的个数是由队头指针和队尾指针共同决定的，元素的动态变化也是通过队头指针和队尾指针来反映的。
国家二级C语言（数据结构与算法）机试模拟试卷2(题后含答案及解析)题型有：1. 选择题选择题1．算法中，对需要执行的每一步操作，必须给出清楚、严格的规定。
这属于算法的A．正当性B．可行性C．确定性D．有穷性正确答案：C解析：本题考查算法的基本特征。
算法的可行性表示算法中执行的任何步骤都是可以被分解为基本的可执行的操作步：确定性是指算法的每一步骤必须有确切的含义；有穷性是指算法必须能在执行有限个步骤之后终止。
知识模块：数据结构与算法2．下列叙述中正确的是A．算法就是程序B．设计算法时只需要考虑数据结构的设计C．设计算法时只需要考虑结果的可靠性D．以上三种说法都不对正确答案：D解析：所谓算法是指解题方案的准确而完整的描述。
是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。
算法不等于程序，也不等于计算方法。
设计算法时不仅要考虑对数据对象的运算和操作，还要考虑算法的控制结构。
知识模块：数据结构与算法3．下列叙述中正确的是A．算法的效率只与问题的规模有关，而与数据的存储结构无关B．算法的时间复杂度是指执行算法所需要的计算工作量C．数据的逻辑结构与存储结构是一一对应的D．算法的时间复杂度与空间复杂度一定相关正确答案：B解析：算法的时间复杂度是指执行算法所需要的计算工作量。
算法的工作量用算法所执行的基本运算的次数来度量，而算法所执行的基本运算次数是问题规模的函数；算法的空间复杂度一般是指执行这个算法所需要的内存空间。
算法的时间复杂度与空间复杂度并不相关。
数据的逻辑结构就是数据元素之间的逻辑关系，它是从逻辑上描述数据元素之间的关系，是独立于计算机的；数据的存储结构是研究数据元素和数据元素之问的关系如何在计算机中表示，它们并非一一对应。
算法的执行效率不仅与问题的规模有关，还与数据的存储结构有关。
知识模块：数据结构与算法4．在DOS环境F，代表键盘和显示器的设备文件名为A．PRNB．CONC．NULD．LPT正确答案：B解析：本题考查DOS下面的虚拟设备文件，选项A)的PRN表示打印机，选项B)中的CON表示键盘或屏幕，选项C）的NUL表示虚拟空设备，选项D)的LPT表示并口。
《数据结构与算法——C语言版（容易）》试卷得分一、单选题（每题2分，共计40分）1．设循环队列中数组的下标范围是01，其头尾指针分别为f和r，则其元素的个数为（）。
（）A、B、1C、()1D、()2．若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，则从顶点1开始对该图进行广度优先搜索，得到的顶点序列可能为（）。
（）A、1,2,3,4,5B、1,2,4,3,5C、1,2,4,5,3D、1,4,2,5,33．带头结点的单链表为空的判定条件是（）。
（）A、B、C、4．散列函数有一个共同特性，即函数值应当以（）取其值域的每个值。
（）A、最大概率B、最小概率C、平均概率D、同等概率5．对于顺序表，以下说法错误的是（）。
（）A、顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C、顺序表的特点是：逻辑结构中相邻的结点在存储结构中仍相邻D、顺序表的特点是：逻辑上相邻的元素，存储在物理位置也相邻的单元中6．以下错误的是（）。
（）A、对循环链表来说，从表中任一结点出发，都能通过前后操作扫描整个循环链表B、对单链表来说，只有从头结点开始才能扫描表中全部结点C、双链表的特点：是找结点的前驱和后继都很容易D、对双链表来说，结点*p的存储位置既存放在其前驱结点的后继指针域中，也存放在它的后继结点的前驱指针域中。
7．图的深度优先或广度优先遍历的空间复杂性均为（）。
（访问标志位数组空间）（）A、O(n)B、O(e)C、O()D、O()8．若对n阶对称矩阵A以行序优先存储将其下三角的元素（包括主对角线上所以元素）依次存放于一维总分题号一二三四五题分得分数组B[1..(n(1))/2]中，则在B中确定（i<j）的位置k的关系为（）。
数据结构与算法模拟测试题数据结构与算法是计算机科学中非常重要的基础知识，它们对于编写高效、可靠的程序起着至关重要的作用。
以下是一组数据结构与算法的模拟测试题，希望能帮助您巩固和检验对这部分知识的掌握程度。
一、选择题（每题 5 分，共 30 分）1、在一个具有 n 个元素的有序单链表中插入一个新元素，平均需要移动的元素个数为（）A nB n/2C （n ＋ 1)／2D log₂n2、设栈的初始状态为空，元素 1、2、3、4、5 依次入栈，出栈序列不可能是（）A 5 4 3 2 1B 2 1 5 4 3C 2 1 3 4 5D 1 2 5 4 33、对于一个具有 n 个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小为（）A nB n²C n(n 1)／2D n(n ＋ 1)／24、以下排序算法中，在最坏情况下时间复杂度不是O(n²)的是（）A 冒泡排序B 选择排序C 插入排序D 快速排序5、已知一棵二叉树的先序遍历序列为 ABCDEFG，中序遍历序列为 CBDAEGF，则其后序遍历序列为（）A CDBAFGEB CDBGFEAC CDBAGFED CDGBFEA6、以下数据结构中，不属于线性结构的是（）A 队列B 栈C 二叉树D 线性表二、填空题（每题 5 分，共 30 分）1、设一棵完全二叉树共有 700 个结点，则在该二叉树中有______个叶子结点。
2、对于顺序存储的线性表，访问第 i 个元素的时间复杂度为______。
3、在一个长度为 n 的顺序表中删除第 i 个元素（1≤i≤n），需要向前移动______个元素。
4、若对序列(49, 38, 65, 97, 76, 13, 27)进行冒泡排序，在第一趟排序过程中，需要进行相邻元素比较的次数为______。
5、具有 10 个顶点的无向完全图，其边的数量为______。
6、已知一个图的邻接表如下所示，从顶点 1 出发进行深度优先遍历的序列为______。
完美WORD格式编辑《数据结构与算法》模拟题一、填空题：（共15分）（每空一分）1.按照排序时，存放数据的设备，排序可分为<1> 内部排序和<2> 外部排序。
2.图的常用的两种存储结构是<3> 邻接矩阵存储和<4>邻接表面存储。
3.数据结构中的三种基本的结构形式是<5> x线性结构和<6> 树形结构、<7> 图形结构。
4.一个高度为6的二元树，最多有<8> 63 个结点。
5.线性查找的时间复杂度为：<9> ，折半查找的时间复杂度为：<10> 、堆分类的时间复杂度为：<11> 。
6.在采用散列法进行查找时，为了减少冲突的机会，散列函数必须具有较好的随机性，在我们介绍的几种散列函数构造法中，随机性最好的是<12>随机数法、最简单的构造方法是<13> 除留余数法。
7.线性表的三种存储结构是：数组、<14> 链表、<15>静态链表。
二、回答下列问题：（共30分）1.现有如右图的树，回答如下问题：A）根结点有：6B）叶结点有：5C）具有作大度的结点：9和10D）结点☐的祖先是：0和2E）结点☐的后代是：102.栈存放在数组A[m]中，栈底位置是m-1。
试问：A）栈空的条件是什么？B）栈满的条件是什么？3.数据结构和抽象数据型的区别与联系：4.已知一株非空二元树，其先根与中根遍历的结果为：先根：ABCDEFGHI中跟：CBEDAGFHI将此二元树构造出来。
5.分析下列程序的运行时间：A)void mystery(int n){int i, j, k;for(i=1; i<n; i++)for(j=i+1; j<=n; j++)for(k=1; k<=j; k++){some statement requiring O(1) time;}}B）void podd(int n){int I, j, x, y;for(I=1; I<=n; I++)if( odd(I ) ){for(j=I; j<=n; j++)x=x+1;for(j=1; j<=I; j++)y=y+1;}}6.已知数学表达式是(3+b)sin(x+5)—a/x2，求该表达式的波兰表示法的前缀和后缀表示（要求给出过程）。
【精编】数据结构与算法分析-C++版答案数据结构与算法是计算机科学的核心内容之一，它为解决实际问题提供了有效的方法和技巧。
C++是一种常用的编程语言，具有强大的功能和灵活性，因此在数据结构和算法的学习与实践中被广泛应用。
1. 什么是数据结构？数据结构是组织和存储数据的方式，它涉及到数据的逻辑关系和物理存储方式。
常见的数据结构有数组、链表、栈、队列、树、图等。
2. 什么是算法？算法是解决问题的方法和步骤的描述，它是一个有限的指令集合。
算法包括输入、输出和执行步骤，可以用来解决各种问题。
3. 什么是时间复杂度和空间复杂度？时间复杂度是衡量算法执行时间的度量，表示算法的运行时间与输入规模之间的关系。
空间复杂度是衡量算法所需存储空间的度量，表示算法的存储空间与输入规模之间的关系。
4. 数组和链表的区别是什么？数组是一种连续存储的数据结构，可以通过下标访问元素，但插入和删除元素时需要移动其他元素。
链表是一种非连续存储的数据结构，每个节点包含数据和指向下一个节点的指针，插入和删除元素时只需要修改指针。
5. 栈和队列的区别是什么？栈是一种后进先出（LIFO）的数据结构，只能在栈顶插入和删除元素。
队列是一种先进先出（FIFO）的数据结构，只能在队尾插入元素，在队头删除元素。
6. 二叉树和二叉搜索树的区别是什么？二叉树是一种每个节点最多有两个子节点的树结构。
二叉搜索树是一种二叉树，其中左子树的值小于根节点的值，右子树的值大于根节点的值。
7. 图的遍历算法有哪些？图的遍历算法包括深度优先搜索（DFS）和广度优先搜索（BFS）。
DFS以深度为优先级，沿着图的某一分支尽可能深地搜索，直到无法继续为止。
BFS以广度为优先级，按照距离从近到远的顺序搜索。
8. 动态规划和贪心算法的区别是什么？动态规划和贪心算法都是求解最优化问题的方法。
动态规划通过将问题划分为子问题，并保存已解决子问题的解来求解整个问题。
贪心算法则根据每个子问题的局部最优解，选择当前最优解，而不考虑整体最优解。
数据结构C语言模拟试题及答案没印不思，故有惑；不求，故无得；不问，故不知。
数据结构C语言模拟试题及答案数据结构与算法》复习题一、选择题1．在数据结构中从逻辑上可以把数据结构分为 CA．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构2．数据结构在计算机内存中的表示是指 AA．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系3．在数据结构中与所使用的计算机无关的是数据的 A 结构A．逻辑B．存储C．逻辑和存储D．物理4．在存储数据时通常不仅要存储各数据元素的值而且还要存储 CA．数据的处理方法B．数据元素的类型C．数据元素之间的关系D．数据的存储方法5．在决定选取何种存储结构时一般不考虑 AA．各结点的值如何B．结点个数的多少C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便6．以下说法正确的是 DA．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是 C算法分析的两个主要方面是 A（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性C．可读性和文档性 D．数据复杂性和程序复杂性8．下面程序段的时间复杂度是O（n2）s ＝0；for（ I ＝0； i＜n； i＋＋）for（j＝0；j＜n；j＋＋）s ＋＝B[i][j]；sum ＝ s ；9．下面程序段的时间复杂度是O（n*m）for（ i ＝0； i＜n； i＋＋）for（j＝0；j＜m；j＋＋）A[i][j] ＝ 0；10．下面程序段的时间复杂度是O（log3n）i ＝ 0；while（i＜＝n）i ＝ i * 3；11．在以下的叙述中正确的是 BA．线性表的顺序存储结构优于链表存储结构B．二维数组是其数据元素为线性表的线性表C．栈的操作方式是先进先出D．队列的操作方式是先进后出12．通常要求同一逻辑结构中的所有数据元素具有相同的特性这意味着 BA．数据元素具有同一特点B．不仅数据元素所包含的数据项的个数要相同而且对应的数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等13．链表不具备的特点是 AA．可随机访问任一结点B．插入删除不需要移动元素C．不必事先估计存储空间D．所需空间与其长度成正比14．不带头结点的单链表head为空的判定条件是 Anext ＝＝NULLC．head－＞next ＝＝head D head！＝NULL15．带头结点的单链表head为空的判定条件是 Bnext ＝＝NULLC．head－＞next ＝＝head D head！＝NULL16．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点则采用D 存储方式最节省运算时间A．单链表 B．给出表头指针的单循环链表C．双链表D．带头结点的双循环链表17．需要分配较大空间插入和删除不需要移动元素的线性表其存储结构是 BA．单链表 B．静态链表C．线性链表 D．顺序存储结构18．非空的循环单链表head的尾结点（由p所指向）满足 CA．p－＞next ＝＝ NULL B．p ＝＝ NULLC．p－＞next ＝＝head D．p ＝＝ head19．在循环双链表的p所指的结点之前插入s所指结点的操作是DA．p－＞prior－＞priorB．p－＞prior－＞priorC．s－＞prior－＞next ＝ sD．s－＞prior－＞prior ＝ s20．如果最常用的操作是取第i个结点及其前驱则采用 D 存储方式最节省时间A．单链表 B．双链表C．单循环链表D．顺序表21．在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 BA．O（1） B．O（n）C．O（n2）D．O（nlog2n）22．在一个长度为n（n＞1）的单链表上设有头和尾两个指针执行 B 操作与链表的长度有关A．删除单链表中的第一个元素B．删除单链表中的最后一个元素C．在单链表第一个元素前插入一个新元素D．在单链表最后一个元素后插入一个新元素23．与单链表相比双链表的优点之一是 DA．插入、删除操作更简单B．可以进行随机访问C．可以省略表头指针或表尾指针D．顺序访问相邻结点更灵活24．如果对线性表的操作只有两种即删除第一个元素在最后一个元素的后面插入新元素则最好使用 BA．只有表头指针没有表尾指针的循环单链表B．只有表尾指针没有表头指针的循环单链表C．非循环双链表D．循环双链表25．在长度为n的顺序表的第i个位置上插入一个元素（1≤ i ≤n＋1）元素的移动次数为： AA．n - i ＋ 1 B．n - i C．i D．i - 126．对于只在表的首、尾两端进行插入操作的线性表宜采用的存储结构为 CA．顺序表 B．用头指针表示的循环单链表C．用尾指针表示的循环单链表 D．单链表27．下述哪一条是顺序存储结构的优点? CA插入运算方便 B可方便地用于各种逻辑结构的存储表示C存储密度大 D删除运算方便28．下面关于线性表的叙述中错误的是哪一个? BA线性表采用顺序存储必须占用一片连续的存储单元B线性表采用顺序存储便于进行插入和删除操作C线性表采用链式存储不必占用一片连续的存储单元D线性表采用链式存储便于进行插入和删除操作29．线性表是具有n个 B 的有限序列A．字符B．数据元素 C．数据项D．表元素30．在n个结点的线性表的数组实现中算法的时间复杂度是O（1）的操作是 AA．访问第i（1＜＝i＜＝n）个结点和求第i个结点的直接前驱（1＜i＜＝n）B．在第i（1＜＝i＜＝n）个结点后插入一个新结点C．删除第i（1＜＝i＜＝n）个结点D．以上都不对31．若长度为n的线性表采用顺序存储结构在其第i个位置插入一个新元素的算法的时间复杂度为CA．O（0） B．O（1）C．O（n）D．O（n2）32．对于顺序存储的线性表访问结点和增加、删除结点的时间复杂度为 CA．O（n） O（n） B．O（n） O（1）C．O（1） O （n）D．O（1） O（1）33．线性表（a1a2...an）以链式方式存储访问第i位置元素的时间复杂度为 CA．O（0） B．O（1）C．O（n）D．O（n2）34．单链表中增加一个头结点的目的是为了 CA．使单链表至少有一个结点B．标识表结点中首结点的位置C．方面运算的实现 D．说明单链表是线性表的链式存储35．在单链表指针为p的结点之后插入指针为s的结点正确的操作是 BA．p－＞next＝p－＞next＝p－＞next＝s；C．p－＞next＝s－＞next＝s－＞next；p－＞next＝s36．线性表的顺序存储结构是一种 AA．随机存取的存储结构B．顺序存取的存储结构C．索引存取的存储结构D．Hash存取的存储结构37．栈的特点是 B队列的特点是 AA．先进先出 B．先进后出38．栈和队列的共同点是 CA．都是先进后出 B．都是先进先出C．只允许在端点处插入和删除元素 D．没有共同点39．一个栈的进栈序列是abcde则栈的不可能的输出序列是 CA．edcba B．decba C．dceab D．abcde40．设有一个栈元素依次进栈的顺序为A、B、C、D、E下列 C 是不可能的出栈序列A．ABCDE B．BCDEA C．EABCD D．EDCBA41．以下 B 不是队列的基本运算?A．从队尾插入一个新元素B．从队列中删除第i个元素C．判断一个队列是否为空D．读取队头元素的值42．若已知一个栈的进栈序列是123n其输出序列为p1p2p3...pn若p1＝n则pi为 CA．i B．n－i C．n－i＋1 D．不确定43．判定一个顺序栈st（最多元素为MaxSize）为空的条件是 BA．st－＞top ！top ＝＝－1C．st－＞top ！top ＝＝MaxSize44．判定一个顺序栈st（最多元素为MaxSize）为满的条件是 DA．st－＞top ！top ＝＝－1C．st－＞top ！top ＝＝MaxSize45．一个队列的入队序列是1234则队列的输出序列是 BA．4321 B．1234C．1432 D．324146．判定一个循环队列qu（最多元素为MaxSize）为空的条件是CA．qu－＞rear - qu－＞rear - qu－＞front －1＝＝MaxSizeC．qu－＞front －147．在循环队列中若front与rear 分别表示对头元素和队尾元素的位置则判断循环队列空的条件是 CA．front＝＝rear＋1 B．rear＝＝front＋1 C．front ＝＝rear D．front＝＝048．向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时应执行 D 操作A．h－＞next＝h ；C．s－＞next＝h－＞next＝s ；49．输入序列为ABC可以变为CBA时经过的栈操作为 BA．pushpoppushpoppushpop B．pushpushpushpoppoppopC．pushpushpoppoppushpop D．pushpoppushpushpoppop50．若栈采用顺序存储方式存储现两栈共享空间V[1 m]top[1]、top[2]分别代表第1和第2个栈的栈顶栈1的底在V[1]栈2的底在V[m]则栈满的条件是 BA．|top[2]－top[1]|＝0 B． top[1]＋1＝top[2] C．top[1]＋top[2]＝m D．top[1]＝top[2]51．设计一个判别表达式中左、右括号是否配对出现的算法采用 D 数据结构最佳A．线性表的顺序存储结构 B．队列 C．线性表的链式存储结构D．栈52．允许对队列进行的操作有 DA．对队列中的元素排序B．取出最近进队的元素C．在队头元素之前插入元素D．删除队头元素53．对于循环队列 DA．无法判断队列是否为空 B．无法判断队列是否为满C．队列不可能满 D．以上说法都不对54．若用一个大小为6的数值来实现循环队列且当前rear和front的值分别为0和3当从队列中删除一个元素再加入两个元素后rear和front的值分别为 BA．1和5 B．2和4 C．4和2 D．5和155．队列的"先进先出"特性是指 DA．最早插入队列中的元素总是最后被删除B．当同时进行插入、删除操作时总是插入操作优先C．每当有删除操作时总是要先做一次插入操作D．每次从队列中删除的总是最早插入的元素56．和顺序栈相比链栈有一个比较明显的优势是 AA．通常不会出现栈满的情况 B．通常不会出现栈空的情况 C．插入操作更容易实现 D．删除操作更容易实现57．用不带头结点的单链表存储队列其头指针指向队头结点尾指针指向队尾结点则在进行出队操作时 CA．仅修改队头指针B．仅修改队尾指针C．队头、队尾指针都可能要修改D．队头、队尾指针都要修改58．若串S＝'software'其子串的数目是 BA．8 B．37 C．36 D．959．串的长度是指 BA．串中所含不同字母的个数 B．串中所含字符的个数C．串中所含不同字符的个数 D．串中所含非空格字符的个数60．串是一种特殊的线性表其特殊性体现在 BA．可以顺序存储B．数据元素是一个字符C．可以链式存储D．数据元素可以是多个字符61．设有两个串p和q求q在p中首次出现的位置的运算称为 BA．连接 B．模式匹配 C．求子串D．求串长62．数组A中每个元素的长度为3个字节行下标i从1到8列下标j从1到10从首地址SA开始连续存放的存储器内该数组按行存放元素A[8][5]的起始地址为 CA．SA＋141 B． SA＋144 C．SA＋222 D．SA＋22563．数组A中每个元素的长度为3个字节行下标i从1到8列下标j从1到10从首地址SA开始连续存放的存储器内该数组按行存放元素A[5][8]的起始地址为 CA．SA＋141 B． SA＋180 C．SA＋222 D．SA＋22564．若声明一个浮点数数组如下： froat average[]＝new float[30]；假设该数组的内存起始位置为200average[15]的内存地址是 CA．214 B．215 C．260 D．25665．设二维数组A[1... m1... n]按行存储在数组B中则二维数组元素A[ij]在一维数组B中的下标为 AA．n*（i－1）＋j B． n*（i－1）＋j－1 C．i*（j－1）D．j*m＋i－166．有一个100×90的稀疏矩阵非0元素有10设每个整型数占2个字节则用三元组表示该矩阵时所需的字节数是 BA．20 B． 66 C．18 000 D．3367．数组A[0 (4)－1 ... －35 ...7]中含有的元素个数是 AA．55 B． 45 C．36 D．1668．对矩阵进行压缩存储是为了 DA．方便运算B．方便存储C．提高运算速度 D．减少存储空间69．设有一个10阶的对称矩阵A采用压缩存储方式以行序为主存储a11为第一个元素其存储地址为1每个元素占1个地址空间则a85的地址为 BA．13 B． 33 C．18 D．4070．稀疏矩阵一般的压缩存储方式有两种即 CA．二维数组和三维数组 B．三元组和散列C．三元组和十字链表 D．散列和十字链表71．树最适合用来表示 CA．有序数据元素B．无序数据元素C．元素之间具有分支层次关系的数据D．元素之间无联系的数据72．深度为5的二叉树至多有 C 个结点A．16 B． 32 C．31 C． 1073．对一个满二叉树m个叶子n个结点深度为h则 DA．n ＝ h＋m B h＋m ＝ 2n C m ＝ h－1 D n ＝2h－174．任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序 AA．不发生改变 B．发生改变C．不能确定D．以上都不对75．在线索化树中每个结点必须设置一个标志来说明它的左、右链指向的是树结构信息还是线索化信息若0标识树结构信息1标识线索对应叶结点的左右链域应标识为__ D __A．00 B．01 C．10D．1176．在下述论述中正确的是 D①只有一个结点的二叉树的度为0；②二叉树的度为2；③二叉树的左右子树可任意交换；④深度为K的顺序二叉树的结点个数小于或等于深度相同的满二叉树A．①②③B．②③④ C．②④ D．①④77．设森林F对应的二叉树为B它有m个结点B的根为pp的右子树的结点个数为n森林F中第一棵树的结点的个数是 AA．m－n B．m－n－1 C．n＋1 D．不能确定78．若一棵二叉树具有10个度为2的结点5个度为1的结点则度为0的结点的个数是 BA．9 B．11 C．15 D．不能确定79．具有10个叶子结点的二叉树中有 B 个度为2的结点A．8 B．9 C．10 D．1180．在一个无向图中所有顶点的度数之和等于所有边数的 C 倍A．1/2 B 1 C 2 D 481．在一个有向图中所有顶点的入度之和等于所有顶点的出度之和的 B 倍A．1/2 B 1 C 2 D 482．某二叉树结点的中序序列为ABCDEFG后序序列为BDCAFGE则其左子树中结点数目为： CA．3 B．2 C．4D．583．已知一算术表达式的中缀形式为A＋B *C-D/E后缀形式为ABC *＋DE/-其前缀形式为 DA．-A＋B*C/DE B．-A＋B*CD/E C -＋*ABC/DE D．-＋A*BC/DE84．已知一个图如图所示若从顶点a出发按深度搜索法进行遍历则可能得到的一种顶点序列为____D___；按广度搜索法进行遍历则可能得到的一种顶点序列为___A___；①A．abecdf B．acfebdC．aebcfdD．aedfcb②A．a bcedf B．a bcefdC．aebcfdD．acfdeb85．采用邻接表存储的图的深度优先遍历算法类似于二叉树的___A____A．先序遍历 B．中序遍历 C．后序遍历 D．按层遍历86．采用邻接表存储的图的广度优先遍历算法类似于二叉树的___D____A．先序遍历 B．中序遍历 C．后序遍历 D．按层遍历87．具有n 个结点的连通图至少有 A 条边A．n－1 B． n C． n（n－1）/2 D． 2n88．广义表（（a）a）的表头是 C表尾是 CA．a B （） C （a） D （（a））89．广义表（（a））的表头是 C表尾是 BA．a B （） C （a） D （（a））90．顺序查找法适合于存储结构为 B 的线性表A 散列存储B 顺序存储或链式存储C 压缩存储D 索引存储91．对线性表进行折半查找时要求线性表必须 BA 以顺序方式存储B 以顺序方式存储且结点按关键字有序排列C 以链式方式存储D 以链式方式存储且结点按关键字有序排列92．采用折半查找法查找长度为n的线性表时每个元素的平均查找长度为 DA O（n2）B O（nlog2n）C O（n）D O（log2n）93．有一个有序表为{139123241456275778295100}当折半查找值为82的结点时C 次比较后查找成功A．11 B 5 C 4 D 894．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值这种说法 BA 正确B 错误95．下面关于B树和B＋树的叙述中不正确的结论是 AA B树和B＋树都能有效的支持顺序查找B B树和B ＋树都能有效的支持随机查找C B树和B＋树都是平衡的多叉树D B树和B ＋树都可用于文件索引结构96．以下说法错误的是 BA．散列法存储的思想是由关键字值决定数据的存储地址B．散列表的结点中只包含数据元素自身的信息不包含指针C．负载因子是散列表的一个重要参数它反映了散列表的饱满程度D．散列表的查找效率主要取决于散列表构造时选取的散列函数和处理冲突的方法97．查找效率最高的二叉排序树是 CA．所有结点的左子树都为空的二叉排序树B．所有结点的右子树都为空的二叉排序树C．平衡二叉树D．没有左子树的二叉排序树98．排序方法中从未排序序列中依次取出元素与已排序序列中的元素进行比较将其放入已排序序列的正确位置上的方法称为 CA．希尔排序 B冒泡排序 C插入排序 D选择排序99．在所有的排序方法中关键字比较的次数与记录的初始排列次序无关的是 DA．希尔排序B．冒泡排序 C．直接插入排序D．直接选择排序100．堆是一种有用的数据结构下列关键码序列 D 是一个堆A．943153231672 B．9453311623C．165323943172 D．163123945372101．堆排序是一种 B 排序A．插入B．选择C．交换D．归并102． D 在链表中进行操作比在顺序表中进行操作效率高A．顺序查找B．折半查找C．分块查找D．插入103．直接选择排序的时间复杂度为 D（n 为元素个数）A．O（n） B．O（log2n） C．O（nlog2n）D． O （n2）二、填空题1．数据逻辑结构包括线性结构、树形结构和图状结构三种类型树形结构和图状结构合称非线性结构2．数据的逻辑结构分为集合、线性结构、树形结构和图状结构4种3．在线性结构中第一个结点没有前驱结点其余每个结点有且只有 1 个前驱结点；最后一个结点没有后续结点其余每个结点有且只有 1 个后续结点4．线性结构中元素之间存在一对一关系树形结构中元素之间存在一对多关系图形结构中元素之间存在多对多关系5．在树形结构中树根结点没有前驱结点其余每个结点有且只有 1 个前驱结点；叶子结点没有后续结点其余每个结点的后续结点可以任意多个6．数据结构的基本存储方法是顺序、链式、索引和散列存储7．衡量一个算法的优劣主要考虑正确性、可读性、健壮性和时间复杂度与空间复杂度8．评估一个算法的优劣通常从时间复杂度和空间复杂度两个方面考察9．算法的5个重要特性是有穷性、确定性、可行性、输入和输出10．在一个长度为n的顺序表中删除第i个元素时需向前移动 n－i－1 个元素11．在单链表中要删除某一指定的结点必须找到该结点的前驱结点12．在双链表中每个结点有两个指针域一个指向前驱结点另一个指向后继结点13．在顺序表中插入或删除一个数据元素需要平均移动 n 个数据元素移动数据元素的个数与位置有关14．当线性表的元素总数基本稳定且很少进行插入和删除操作但要求以最快的速度存取线性表的元素是应采用顺序存储结构15．根据线性表的链式存储结构中每一个结点包含的指针个数将线性链表分成单链表和双链表16．顺序存储结构是通过下标表示元素之间的关系的；链式存储结构是通过指针表示元素之间的关系的17．带头结点的循环链表L中只有一个元素结点的条件是L －＞next－＞next＝L18．栈是限定仅在表尾进行插入或删除操作的线性表其运算遵循后进先出的原则19．空串是零个字符的串其长度等于零空白串是由一个或多个空格字符组成的串其长度等于其包含的空格个数20．组成串的数据元素只能是单个字符21．一个字符串中任意个连续字符构成的部分称为该串的子串22．子串 "str" 在主串 "datastructure" 中的位置是 523．二维数组M的每个元素是6个字符组成的串行下标i的范围从0到8列下标j的范围从1到10则存放M至少需要 540个字节；M的第8列和第5行共占108个字节24．稀疏矩阵一般的压缩存储方法有两种即三元组表和十字链表25．广义表（（a）（（b）c）（（（d））））的长度是 3深度是 426．在一棵二叉树中度为零的结点的个数为n0度为2 的结点的个数为n2则有n0＝n2＋127．在有n个结点的二叉链表中空链域的个数为__n＋1__28．一棵有n个叶子结点的哈夫曼树共有__2n－1_个结点29．深度为5的二叉树至多有31 个结点30．若某二叉树有20个叶子结点有30个结点仅有一个孩子则该二叉树的总结点个数为 6931．某二叉树的前序遍历序列是abdgcefh中序序列是dgbaechf其后序序列为gdbehfca32．线索二叉树的左线索指向其遍历序列中的前驱右线索指向其遍历序列中的后继33．在各种查找方法中平均查找长度与结点个数n无关的查找方法是散列查找法34．在分块索引查找方法中首先查找索引表然后查找相应的块表35．一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列构造树的过程即为对无序序列进行排序的过程36．具有10个顶点的无向图边的总数最多为__45__37．已知图G的邻接表如图所示其从顶点v1出发的深度优先搜索序列为_v1v2v3v6v5v4_其从顶点v1出发的广度优先搜索序列为_v1v2v5v4v3v6__38．索引是为了加快检索速度而引进的一种数据结构一个索引隶属于某个数据记录集它由若干索引项组成索引项的结构为关键字和关键字对应记录的地址39．Prim 算法生成一个最小生成树每一步选择都要满足边的总数不超过n－1当前选择的边的权值是候选边中最小的选中的边加入树中不产生回路三项原则40．在一棵m阶B树中除根结点外每个结点最多有 m 棵子树最少有 m/2 棵子树1．数据逻辑结构包括__线性结构______ 、___树形结构_____ 和___图状结构_____ 三种类型树形结构和图状结构合称 ___非线性结构_____2．在线性结构中第一个结点___无_____前驱结点其余每个结点有且只有_____1___个前驱结点；最后一个结点____无____ 后续结点其余每个结点有且只有___1_____个后续结点4．线性结构中元素之间存在 ___一个对一个的_____ 关系树形结构中元素之间存在___一个对多个的_____ 关系图形结构中元素之间存在___多个对多个的_____关系5．在树形结构中树根结点没有___前驱_____ 结点其余每个结点有且只有____1____个前驱结点；叶子结点没有___后续_____ 结点其余每个结点的后续结点可以___任意多个_____6．数据结构的基本存储方法是 __顺序______ 、_____链式___ 、 __索引______ 和___散列_____存储7．衡量一个算法的优劣主要考虑__正确性______、___可读性_____、___健壮性_____和 ___时间复杂度_____与 __空间复杂度______8．算法的5个重要特性是___有穷性_____ 、__确定性______ 、__可行性______ 、_输入和输出_______10．在一个长度为n的顺序表中删除第i个元素时需向前移动 ____n-i-1____ 个元素11．在单链表中要删除某一指定的结点必须找到该结点的____前驱____结点12．在双链表中每个结点有两个指针域一个指向__直接后续______结点另一个指向___直接前驱结点_____13．在顺序表中插入或删除一个数据元素需要平均移动____n____个数据元素移动数据元素的个数与 ___位置_____有关14．当线性表的元素总数基本稳定且很少进行插入和删除操作但要求以最快的速度存取线性表的元素是应采用____顺序表____ 存储结构15．根据线性表的链式存储结构中每一个结点包含的指针个数将线性链表分成___单链表_____ 和 ___双向链表_____16．顺序存储结构是通过___下标_____ 表示元素之间的关系的；链式存储结构是通过____指针____表示元素之间的关系的17．带头结点的循环链表L中只有一个元素结点的条件是____L->next->next=L____18．__栈______是限定仅在表尾进行插入或删除操作的线性表其运算遵循__后进先出______的原则三、判断题1．在决定选取何种存储结构时一般不考虑各结点的值如何（√）2．抽象数据类型（ADT）包括定义和实现两方面其中定义是独立于实现的定义仅给出一个ADT的逻辑特性不必考虑如何在计算机中实现（√ ）3．抽象数据类型与计算机内部表示和实现无关（√）4．顺序存储方式插入和删除时效率太低因此它不如链式存储方式好（×）5．线性表采用链式存储结构时结点和结点内部的存储空间可以是不连续的（× ）6．对任何数据结构链式存储结构一定优于顺序存储结构（×）7．顺序存储方式只能用于存储线性结构（×）8．集合与线性表的区别在于是否按关键字排序（×）9．线性表中每个元素都有一个直接前驱和一个直接后继（×）10．线性表就是顺序存储的表（×）11．取线性表的第i个元素的时间同i的大小有关（×）12．循环链表不是线性表（×）13．链表是采用链式存储结构的线性表进行插入、删除操作时在链表中比在顺序表中效率高（√）14．双向链表可随机访问任一结点（×）15．在单链表中给定任一结点的地址p则可用下述语句将新结点s插入结点p的后面：p－＞next；（× ）16．队列是一种插入和删除操作分别在表的两端进行的线性表是一种先进后出的结构（×）17．串是一种特殊的线性表其特殊性体现在可以顺序存储（× ）18．长度为1的串等价于一个字符型常量（×）19．空串和空白串是相同的（×）20．数组元素的下标值越大存取时间越长（× ）21．用邻接矩阵法存储一个图时在不考虑压缩存储的情况下所占用的存储空间大小只与图中结点个数有关而与图的边数无关（√ ）22．一个广义表的表头总是一个广义表（×）23．一个广义表的表尾总是一个广义表（√ ）24．广义表（（（ a ）b）c ）的表头是（（ a ）b）表尾是（ c ）（√ ）25．二叉树的后序遍历序列中任意一个结点均处在其孩子结点的后面（√ ）26．度为2的有序树是二叉树（× ）27．二叉树的前序遍历序列中任意一个结点均处在其孩子结点的前面。
国家二级C语言机试（数据结构与算法）模拟试卷2(题后含答案及解析)题型有：1. 选择题选择题1．对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为（）。
A．9B．10C．45D．90正确答案：C解析：在最坏情况下，冒泡排序的时间复杂度为n(n-1)/2，为45，答案选C。
知识模块：数据结构与算法2．下列叙述中正确的是（）。
A．算法的效率只与问题的规模有关，而与数据的存储结构无关B．算法的时间复杂度是指执行算法所需要的计算工作量C．数据的逻辑结构与存储结构是一一对应的D．算法的时间复杂度与空间复杂度一定相关正确答案：B解析：算法的时间复杂度是指执行算法所需要的计算工作量，与数据的存储结构有关，与算法的空间复杂度没有关系。
数据的逻辑结构与存储位置无关，即与存储结构无关，所以选择B。
知识模块：数据结构与算法3．下列叙述中正确的是（）。
A．线性表链式存储结构的存储空间一般要少于顺序存储结构B．线性表链式存储结构与顺序存储结构的存储空间都是连续的C．线性表链式存储结构的存储空间可以是连续的，也可以是不连续的D．以上说法都不对正确答案：C解析：在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的，所以选择C。
知识模块：数据结构与算法4．某二叉树共有12个结点，其中叶子结点只有1个。
则该二叉树的深度为（根结点在第1层）（）。
A．3B．6C．8D．12正确答案：D解析：根据二叉树的性质，叶子结点比度为2的结点个数多一个，叶子结点只有1个，那么度为2的结点为0个，可以得出共有11个度为1的结点，那么该二叉树每一层上只能有一个结点，共12层，即深度为12。
知识模块：数据结构与算法5．对长度为n的线性表作快速排序，在最坏情况下，比较次数为（）。
A．nB．n-1C．n(n-1)D．n(n-1)/2正确答案：D解析：在最坏情况下，快速排序需要比较n(n-1)/2次。
国家二级C语言（数据结构与算法）机试模拟试卷3(题后含答案及解析)题型有：1. 选择题选择题1．下关于算法的叙述错误的是A．算法可以用伪代码、流程图等多种形式来描述B．朋流程图描述的算法可以用任何一种计算机高级语言编写程序代码C．一个正确的算法必须有输入D．一个正确的算法必须有输出正确答案：C解析：本题考查算法的基本概念。
选项C)错误，算法不一定需要输入，但是一定有输出。
知识模块：数据结构与算法2．算法的空间复杂度是指A．算法在执行过程中所需要的计算机存储空间B．算法所处理的数据量C．算法程序中的语句或指令条数D．算法在执行过程中所需要的临时工作单元数正确答案：A解析：算法的空间复杂度是指执行这个算法所需要的内存空间。
这个内存空间包括算法程序所占的空间。
输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。
知识模块：数据结构与算法3．下列叙述中正确的是A．一个算法的空间复杂度大，则其时间复杂度也必定大B．一个算法的空间复杂度大，则其时间复杂度必定小C．一个算法的时间复杂度大，则其空间复杂度必定小D．算法的时间复杂度与空间复杂度没有直接关系正确答案：D解析：算法的复杂度主要包括时间复杂度和空间复杂度。
算法的时间复杂度是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f(n)，其中n是问题的规模；算法的空间复杂度，一般是指执行这个算法所需要的内存空间。
一个算法所占用的存储空间包括算法程序所占用的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。
根据各自的定义可知，算法的时间复杂度与空间复杂度并不相关。
知识模块：数据结构与算法4．计算机网络的主要特点是A．运算速度快B．运算精度高C．资源共享D．人机交换正确答案：C解析：计算机网络主要特点是资源共享。
知识模块：数据结构与算法5．在Windows菜单中，暗淡的命令名项目表示该命令A．暂时不能用B．正在执行C．包含下一层菜单D．包含对话框正确答案：A解析：在Windows菜单中．暗淡的命令名项目表示该命令在当前状态下不可用，或是已被禁用。
国家二级C语言（数据结构与运算）机试模拟试卷3(题后含答案及解析)题型有：1. 选择题选择题1．下列排序方法中，最坏情况下时间复杂度最小的是A．冒泡排序B．快速排序C．堆排序D．直接插入排序正确答案：C解析：根据上表可知选项C正确。
知识模块：数据结构与运算2．为了对有序表进行对分查找，则要求有序表A．只能顺序存储B．只能链式存储C．可以顺序存储也可以链式存储D．任何存储方式正确答案：A解析：有序表的对分查找条件是有序表为顺序存储。
顺序查找：①如果线性表为无序表（即表中元素的排序是无序的），则无论是顺序存储结构还是链式存储结构，都只能用顺序查找；②即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。
分块查找（又称索引顺序查找）：分块有序表结构分为两部分，①线性表本身采用顺序存储结构；②在建立一个索引表，在索引表中，对线性表的每个子表建立一个索引结点，每个结点包括两个域：一是数据域，用于存放对应子表中的最大元素值；二是指针域，用于指示对应子表的第一个元素在整个线性表中的序号。
显然索引表关于数据域是有序的。
知识模块：数据结构与运算3．设某二叉树的后序序列为CBA，中序序列为ABC，则该二叉树的前序序列为A．BCAB．CBAC．ABCD．CAB正确答案：C解析：二叉树的前序遍历顺序为首先访问根结点，再依次访问左结点和右结点。
中序遍历的顺序为首先访问左结点，然后依次访问根结点和右结点。
后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。
根据后序可以很快确定根结点，然后可以查看根在中序中位置，将中序分为左右两部分，左边和右边两颗树，在按照上述方式递推出确定左子树的根和右子树。
本题根据后序，可以确定A为根结点；根据B在中序中的位置，可以确定A没有左子树，BC为A的右子树，C为B的右子树。
本题的具体二叉树如下：因此，这棵二叉树的前序是ABC，选项C正确。
知识模块：数据结构与运算4．下列叙述中正确的是A．存储空间不连续的所有链表一定是非线性结构B．结点中有多个指针域的所有链表一定是非线性结构C．能顺序存储的数据结构一定是线性结构D．带链的栈与队列是线性结构正确答案：D解析：计算机中数据按照其数据逻辑结构，可以分为线性结构和非线性结构。
数据结构模拟卷3一、单项选择题，在每小题的四个备选答案中，选出一个正确的答案，并将其代码填入答题纸上对应题号后的括号内。
不准不填，否则无分。
（共15 小题，每小题2分，共30 分）1、线性表是具有n个C的有限序列。
A、表元素B、字符C、数据元素D、信息项2、若长度为n的线性表采用顺序存储结存，在其第i个位置插入一个新元素的算法时复杂度为C。
(1≤i≤n+1)A、O(0)B、O(1)C、O(n)D、O(n*n)3、设单链表中结点的结构为（data，Link）。
已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插人结点*s，则应执行下列哪一个操作B。
A、s->link=p->link; p->link=s;B、q->link=s; s->link=p;C、p->link=s->link; s->link=p;D、p->link=s; s->link=q;4、设单链表中结点的结构为（data，Link）。
已知指针p所指结点不是尾结点的，若在*p之后插入结点*s，则应执行下列哪一个操作 B ？A、s->link=p; p->link=s;B、s->link=p->link; p->link=s;C、s->link=p->link; p=s;D、p->link=s; s->link=p;5、将一个递归算法改为对应的非递归算法时，通常需要使用A。
A、栈B、队列C、循环队列D、优先队列6、当利用大小为n 的数组顺序存储一个队列时，该队列的最大长度为C。
A、n-2B、n-1C、nD、n+17、广义表A(a),则表尾为C。
A、aB、(( ) )C、空表D、（a）8、对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点为n2,则AA、 n0=n2+1B、 n2=n0+1C、n0=2n2+1D、 n2=2n0+19、栈的插入和删除操作在A进行。
《数据结构》模拟卷一、单项选择题1．数据结构是（D）。
A．一种数据类型B．数据的存储结构C．一组性质相同的数据元素的集合D．相互之间存在一种或多种特定关系的数据元素的集合2．算法分析的目的是（B）。
A．辨别数据结构的合理性B．评价算法的效率C．研究算法中输入与输出的关系D．鉴别算法的可读性3．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（D）。
A．插入B．删除C．排序D．定位4．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（B）。
A．3，2，6，1，4，5 B．3，4，2，1，6，5C．1，2，5，3，4，6 D．5，6，4，2，3，15．设串sl=″Data Structures with Java″,s2=″it″，则子串定位函数index(s1,s2)的值为（C）。
A．15 B．16C．17D．186．二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（A）。
A．1207B．1209C．1211 D．12137．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（A）。
A．队列B．栈C．线性表D．有序表8．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（B）。
A．不一定相同B．都相同C．都不相同D．互为逆序9．若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（C）。
A．层次遍历算法B．前序遍历算法C．中序遍历算法D．后序遍历算法10．若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（A）。
A．图中每个顶点的入度B．图中每个顶点的出度C．图中弧的条数D．图中连通分量的数目11．图的邻接矩阵表示法适用于表示（B）。
A．无向图B．有向图C．稠密图D．稀疏图12．在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为（D）。
假设二叉树中每个结点所含数据元素均为单字母，以二叉链表为存储结构，试编写算法按如下图所示的树状显示二叉树。
从上图来看，二叉树的第一层显示在第一列，第二层显示在第二列，第三层显示在第三列；每行显示一个结点，从上至下是先显示右子树，再显示根，最后最左子树，也就是以先遍历右子树，最后遍历左子树的中序遍历次序显示各结点。
具体算法实现如下：// 文件路径名:exam1\alg.htemplate <class ElemType>void DisplayHelp(BinTreeNode<ElemType> *r, int level)// 操作结果：按树状形式显示以r为根的二叉树，level为层次数，可设根结点的层次数为1{if(r != NULL){ // 空树不显式，只显式非空树DisplayHelp<ElemType>(r->rightChild, level + 1); // 显示右子树cout << endl; // 显示新行for(int i = 0; i < level - 1; i++)cout << " "; // 确保在第level列显示结点cout << r->data; // 显示结点DisplayHelp<ElemType>(r->leftChild, level + 1); // 显示左子树}}template <class ElemType>void Display(const BinaryTree<ElemType> &bt)// 操作结果：树状形式显示二叉树{DisplayHelp<ElemType>(bt.GetRoot(), 1); // 树状显示以bt.GetRoot()为根的二叉树cout << endl; // 换行}以二叉链表作存储结构，试编写计算二叉树中叶子结点数目的递归算法。
本题只要在遍历二叉树的过程序中对叶子结点进行记数即可。
具体算法实现如下：// 文件路径名:exam2\alg.htemplate <class ElemType>long LeafCountHelp(BinTreeNode<ElemType> *r)// 操作结果：按树状形式显示二叉树，level为层次数，可设根结点的层次数为1{if (r == NULL){ // 空二叉树return 0; // 空树返回0}else if (r->leftChild == NULL && r->rightChild == NULL){ // 只有一个结点的树return 1; // 只有一个结点的树返回1}else{ // 其他情况, 叶子结点数为左右子树的叶子结点数之和return LeafCountHelp(r->leftChild) + LeafCountHelp(r->rightChild);}}template <class ElemType>long LeafCount(const BinaryTree<ElemType> &bt)// 操作结果：计算二叉树中叶子结点数目{return LeafCountHelp(bt.GetRoot()); // 调用辅助函数实现计算二叉树中叶子结点数目}编写一个算法求二叉树的深度。
若二叉树为空，深度为0；若二叉树不空，则二叉树的深度为左右子树深度的最大值加1。
本题最简单算法是递归算法。
具体算法实现如下：template <class ElemType>int DepthHelp(BinTreeNode<ElemType> *r)// 操作结果：求二叉树的深度{if (r == NULL){ // 空二叉树return 0; // 空二叉树的深度为0}else{ // 非空二叉树int lDepth = DepthHelp(r->leftChild); // 左子树的深度int rDepth = DepthHelp(r->rightChild); // 右子树的深度return ((lDepth > rDepth) ? lDepth : rDepth) + 1; // 返回左右子树的深度最大值加1}}template <class ElemType>int Depth(BinaryTree<ElemType> &bt)// 操作结果：求二叉树的深度{return DepthHelp(bt.GetRoot()); // 调用辅助函数求二叉树的深度}试写一递归算法，从大到小输出二叉排序树中所有的关键字值小于key的元素值。
可按先遍历右子树，遍历根结点，再遍历左子树进行中序遍历，这样可实现由大到小遍历一棵二叉排序树。
具体算法实现如下：// 文件路径名:exam4\alg.htemplate <class ElemType, class KeyType>void InOrderHelp(BinTreeNode<ElemType> *r, const KeyType &key)// 操作结果: 从大到小输出以r为根的二叉排序树中所有的关键字值小于key的元素值{if (r != NULL){ // 非空二叉排序树InOrderHelp(r->rightChild, key); // 遍历右子树if(r->data < key) cout << r->data << " "; // 输出根结点InOrderHelp(r->leftChild, key); // 遍历左子树}}template <class ElemType, class KeyType>void InOrder(const BinarySortTree<ElemType, KeyType> &t, const KeyType &key) // 操作结果: 从大到小输出二叉排序树中所有的关键字值不小于key 的元素值 { InOrderHelp(t.GetRoot(), key); // 调用辅助函数实现从大到小输出二叉排序树中所有的关键字值不小于key 的元素值 }编写复制一棵二叉树的非递归算法。
可采用层次遍历的方式进行复制，将已复制的结点进入一个队列中即可。
具体算法实现如下：// 文件路径名:exam5\alg.h template <class ElemType>void CopyBitree(BinaryTree<ElemType> *fromBtPtr, BinaryTree<ElemType> *&toBtPtr) // 操作结果: 复制二叉树fromBt 到toBt 的非递归算法 { if (toBtPtr != NULL) delete toBtPtr; // 释放toBtPtr if (fromBtPtr == NULL || fromBtPtr->Empty()) { // 空二叉树 toBtPtr = NULL; // 空二叉树 } else { // 非空二叉树 LinkQueue<BinTreeNode<ElemType> *> fromQ, toQ; // 队列 BinTreeNode<ElemType> *fromPtr, *toPtr, *fromRoot, *toRoot; fromRoot = fromBtPtr->GetRoot(); // 取出fromBtPtr 的根 toRoot = new BinTreeNode<ElemType>(fromRoot->data); // 复制根结点 fromQ.InQueue(fromRoot); // 入队 toQ.InQueue(toRoot); // 入队 while (!fromQ.Empty()) // fromQ 非空 { fromQ.OutQueue(fromPtr); // 出队 toQ.OutQueue(toPtr); // 出队 if (fromPtr->leftChild != NU LL) // 左子树非空 // 复制fromPtr 左孩子 { toPtr->leftChild = new BinTreeNode<ElemType>(fromPtr->leftChild->data); fromQ.InQueue(fromPtr->leftChild); toQ.InQueue(toPtr->leftChild); // 入队 } if (fromPtr->rightChild != NULL) // 右子树非空 // 复制fromPtr 右孩子 { toPtr->rightChild = new BinTreeNode<ElemType>(fromPtr->rightChild->data); fromQ.InQueue(fromPtr->rightChild); toQ.InQueue(toPtr->rightChild); // 入队 } } toBtPtr = new BinaryTree<ElemType>(toRoot); // 生成toBtPtr } }已知广义表L=(((b,c),d),((a),((b,c),d)),())，试画出它的存储结构。
0120121∧d 011b1∧c 2012011∧a 2∧012011b1∧c 1∧d 2∧0∧1已知两个带头结点的单链表A和B分别表示两个集合，元素值递增有序，设计算法求出A，B的交集C，并同样以递增的形式存储。
解答：由于单链表A和B是递增有序的，可设置两个整型变量分别表示两个单链表的当前元素的位置，依次取出A 与B的元素进行比较，当A的数据元素小于B的值时，将指向A的当前位置都后移；当A的数据元素大于B的值时，将指向B的当前位置都后移，否则将A（或B）的当前元素复制到C中，并同时将A与B的当前位置后移。
具体算法如下：用单链表la表示集合la，用单链表lb表示集合lb，用单链表lc表示集合lc，具体算法如下：// 文件路径名:exam6\alg.htemplate <class ElemType>void Interaction(const LinkList<ElemType> &la, const LinkList<ElemType> &lb,LinkList<ElemType> &lc)// 初始条件: la和lb中数据元素递增有序// 操作结果: lc返回la与lb表示的集合的交集，并使lc中数据元素仍递增有序{ElemType aItem, bItem; // la和lb中当前数据元素int aLength = la.Length(), bLength = lb.Length(); // la和lb的长度int aPosition = 1, bPosition = 1; // la和lb的当前元素序号lc.Clear(); // 清空lcwhile (aPosition <= aLength && bPosition <= bLength ){ // 取出la和lb中数据元素进行归并la.GetElem(aPosition, aItem); // 取出la中数据元素lb.GetElem(bPosition, bItem); // 取出lb中数据元素if (aItem < bItem){ // aItem插入到lcaPosition++; // 指向la下一数据元素}else if (aItem > bItem){ // lb后移bPosition++; // 指向lb下一数据元素}else{ // aItem == bItem，la和lb同时后移lc.Insert(lc.Length() + 1, aItem); // 插入aItem到lcaPosition++; // 指向la下一数据元素bPosition++; // 指向lb下一数据元素}}}试用递归法编写输出从n个数中挑选 k个进行排列所得序列的算法。
