下载文档原格式
数据结构习题答案.doc单元练习1一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。
（√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。
（ㄨ）（3）数据元素是数据的最小单位。
（ㄨ）（4）数据的逻辑结构和数据的存储结构是相同的。
（ㄨ）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。
（√）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。
（√）（7）数据的存储结构是数据的逻辑结构的存储映像。
（√）（8）数据的物理结构是指数据在计算机内实际的存储形式。
（ㄨ）（9）数据的逻辑结构是依赖于计算机的。
（√）（10）算法是对解题方法和步骤的描述。
二．填空题（1）数据有逻辑结构和存储结构两种结构。
（2）数据逻辑结构除了集合以外，还包括：线性结构、树形结构和图形结构。
（3）数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。
（4）树形结构和图形结构合称为非线性结构。
（5）在树形结构中，除了树根结点以外，其余每个结点只有 1 个前趋结点。
（6）在图形结构中，每个结点的前趋结点数和后续结点数可以任意多个。
（7）数据的存储结构又叫物理结构。
（8）数据的存储结构形式包括：顺序存储、链式存储、索引存储和散列存储。
（9）线性结构中的元素之间存在一对一的关系。
（10）树形结构结构中的元素之间存在一对多的关系，（11）图形结构的元素之间存在多对多的关系。
（12）数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）三个方面的内容。
（13）数据结构被定义为(D，R)，其中D是数据的有限集合，R是D 上的关系的有限集合。
（14）算法是一个有穷指令的集合。
（15）算法效率的度量可以分为事先估算法和事后统计法。
（16）一个算法的时间复杂性是算法输入规模的函数。
（17）算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n的函数。
数据结构模拟考试试卷(1卷)一．判断题（下列各题，正确的请在前面的括号内打√；错误的打×）（√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。
（ㄨ）（2）线性表的链式存储结构优于顺序存储。
（√）（3）将中缀表达式转换成后缀表达式是栈的重要应用。
（×）（4）栈和队列都是顺序存储的线性结构。
（×）（5）“DT”是“DA TA”的子串。
（×）（6）在二叉树中，具有一个子女的父结点，在中序遍历的序列中，它没有后继子女结点。
（×）（7）带权图的最小生成树是唯一的。
（√）（8）散列存储法的基本思想是由关键字的值决定数据的存储地址。
（√）（9）希尔排序是不稳定的排序。
（√）（10）具有n个叶子结点的哈夫曼树共有2n-1个结点。
二．填空题1．线性结构中元素之间存在一对一关系。
2．树形结构和图形结构合称为：非线性结构。
3．顺序表中逻辑上相邻的元素在物理位置上必须相连。
4．在单链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为O (n) 。
5．同一栈的各元素的类型相同。
6．已知表达式，求它的后缀表达式是栈的典型应用之一。
7．队列在进行出队操作时，首先要判断队列是否为空。
8．设循环队列的头指针front指向队头元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，则队满标志为front==(rear+1)% MAXLEN 。
9．串的链式存储结构简称为链式串。
10．求子串函数SubStr("Today is 30 July,2005",13,4)的结果是：July 。
11．给定如下图所示的二叉树，其层次遍历序列为：ABCEFGH 。
12．将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，该结点右孩子的编号为：2*i+1 。
13．图的遍历有：深度优先搜和 _广度优先搜 __等方法。
第一章绪论一，选择题1．组成数据的基本单位是（）A．数据项B．数据类型C．数据元素D．数据变量2．数据结构是研究数据的（）以及它们之间的相互关系。
A．理想结构，物理结构B．理想结构，抽象结构C．物理结构，逻辑结构D．抽象结构，逻辑结构3．算法分析的两个主要方面是（）A．正确性和简单性B．可读性和文档性C．数据复杂性和程序复杂性D．时间复杂度和空间复杂度4．算法分析的目的是（）。
A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进D．分析算法的易懂性和文档性5. 算法的时间复杂度取决于（）A．问题的规模 B. 待处理数据的初态 C. A和B Ｄ．以上都不是6．一个算法应该是（）。
A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C.7. 下面关于算法说法错误的是（）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的8．从逻辑上可以把数据结构分为（）两大类。
A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构9．程序段 for ( i=n-1;i>=1;i--)for (j=1j<=i;j++)if( A[j]>A[j+1])A[j]与A[j+1]对换；其中 n为正整数，则最后一行的语句频度在最坏情况下是（）A．O（n）B．O(nlogn) C.．O(n3) D．O(n2)10．连续存储设计时，存储单元的地址（）。
A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续二，判断题1．数据结构的抽象操作的定义与具体实现有关。
( )2．数据结构是数据对象与对象中数据元素之间关系的集合。
3．在顺序存储结构中，有时也存储数据结构中元素之间的关系。
( )4．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用的需要建立的。
一．判断题（下列各题，正确的请在前面的括号内打√；错误的打×）第1章（√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。
（√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。
（×）（3）数据元素是数据的最小单位。
（×）（4）数据项是数据的基本单位。
（×）（5）数据的逻辑结构和数据的存储结构是相同的。
（√）（6）数据的逻辑结构是各数据元素之间的逻辑关系，是用户按使用需要而建立的。
（√）（7）数据的物理结构是指数据在计算机内实际的存储形式。
（√）（8）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。
（√）（9）数据的存储结构是数据的逻辑结构的存储映像。
（√）（10）算法是对解题方法和步骤的描述。
第2章（×）（1）链表的物理存储结构具有同链表一样的顺序。
（×）（2）链表的每个结点都恰好包含一个指针域。
（√）（3）线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。
（×）（4）链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
（×）（5）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
（√）（6）数组元素的存储位置是下标的线性函数。
（√）（7）在单链表中，元素的存储位置用指针联系，所以可以从头结点开始查找任何一个元素。
（×）（8）顺序存储线性表的插入和删除操作不需要付出很大的代价，因为平均每次移动仅一半的元素。
（×）（9）顺序存储方式的优点是存储密度大，插入、删除效率高。
（×）（10）在单链表中，要取得某个元素，只要知道该元素的指针即可，因此单链表是随机存取的存储结构。
第3章（√）（1）大多数排序算法都有比较关键字大小和改变指向记录的指针或移动记录本身两种基本操作。
数据结构复习题2020秋季第一章绪论一、选择题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. 有穷性6、算法的时间复杂度与（）有关。
A. 计算机的操作系统B. 算法本身C. 数据结构D. 所使用的计算机。
7、下面程序段的时间复杂度是（）。
i=s=0;while (s<n){i++;s+=i;}A.O(n0.5)B. O(log2n)C. O(n)D.O(1)8、下面程序段的时间复杂度是（）。
int f(unsigned int n){if (n==0||n==1) return 1;else return n*f(n-1);}A.O(1)B. O(log2n)C. O(n!)D. O(n)10、在数据结构中，从逻辑上可以把数据结构分为（）。
A.动态结构和静态结构B.紧凑结构和非紧凑结构C.内部结构和外部结构D.线性结构和非线性结构11、执行下面程序段时，执行S语句的次数为（）。
for (int i=1;i<=n;i++)for (int j=1;i<=i;j++)S;A.n2B.n2/2C.n(n+1)D.n(n+1)/212、数据的存储结构包括数据元素的表示和（）。
A. 数据元素间的关系的表示B. 数据处理的方法C. 数据元素的类型D. 相关算法13、树状结构中数据元素的位置之间存在（）的关系。
2024年国家电网招聘之电网计算机通关题库(附带答案)单选题（共45题）1、CPU在响应中断的过程中，保护现场的工作由()完成。
A.中断隐指令B.中断服务程序C.A或B之一完成D.A和B共同完成【答案】 D2、梭形细胞横纹肌肉瘤的特点是：（）A.瘤细胞形态似胚胎性肌管的形态B.瘤细胞形态似晚肌管形态C.肿瘤中央由原始间叶细胞逐渐向边缘成熟区过渡D.瘤细胞奇形怪状，多形性突出【答案】 B3、若片选地址为111时.选定某-32K×16的存储芯片工作，则该芯片在存储器中的首地址和末地址分别为()。
A.00000H，01000HB.38000H，3FFFFHC.3800H，3FFFHD.0000H，0100H【答案】 B4、数据库管理系统通常提供授权功能来控制不同用户访问数据的权限，这主要是为了实现数据库的()。
A.完整性B.一致性C.可靠性D.安全性【答案】 D5、在微型计算机中，内存储器通常采用（）。
A.光存储器B.磁表面存储器C.半导体存储器D.磁芯存储器【答案】 C6、word中编辑状态下，选择表格中的一单元格，并执行删除列的命令，则（）A.删除整个表格B.删除表格中的一列C.删除表格中的一行D.行和列均被删除【答案】 B7、用以指定待执行指令所在地址的是（）。
A.指令寄存器B.数据计数器C.程序计数器D.累加器【答案】 C8、当B属性函数依赖于A属性时，属性A与B的关系是()。
A.一对多B.多对一C.多对多D.以上都不是【答案】 D9、计算机中机械硬盘的性能指标不包括（）A.磁盘转速及容量B.盘片数及磁道数C.容量及平均寻道时间D.磁盘转速及平均寻道时间【答案】 B10、下面所列的()不属于系统总线接口的功能。
A.状态设置B.数据转换C.数据缓冲D.完成算术和逻辑运算【答案】 D11、业界通常用 4 个 V（即 Volume、Variety、Value、Velocity）来概括大数据的特征，这 4 个 V 分别是指（）。
1判断题（√）1. 数据的逻辑结构与数据元素本身的内容和形式无关。
（）2. 线性表的逻辑顺序与物理顺序总是一致的。
（）3. 若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。
（）4. 对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的。
（√）5. 最优二叉搜索树的任何子树都是最优二叉搜索树。
（√）6. 在二叉搜索树上插入新结点时，不必移动其它结点，仅需改动某个结点的指针，使它由空变为非空即可。
（√）7. 有n（n≥1）个顶点的有向强连通图最少有n条边。
（）8. 连通分量是无向图中的极小连通子图。
（）9. 二叉树中任何一个结点的度都是2。
（）10. 单链表从任何一个结点出发，都能访问到所有结点。
（）11.线性表的长度是线性表占用的存储空间的大小。
（）12.队列只能采用链式存储方式。
（√）13.用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关。
（√）14.由二叉树的先序序列和中序序列能唯一确定一棵二叉树。
（）15.图中一个顶点i的出度等于其邻接矩阵中第i列的非0元个数。
（）16. 线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。
（√）17.数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。
（√）18.线性表中的每个结点最多只有一个前驱和一个后继。
（）19.二叉排序树查找总比顺序查找速度快。
（）20.对具有n个顶点的连通图进行深度优先遍历，所得顶点序列是唯一的。
（）21.线性表中各个数据元素的类型必须是相同的。
（）22.B+树是一种特殊的二叉树。
（）23.栈可视为一种特殊的线性表。
（√）24.快速排序总是比其它排序方法快。
（）25.使用双向链表存储数据，可以提高查找（定位运算）的速度。
（）26.最小生成树是边数最少的生成树。
二、单选题1 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ b ）个元素。
2008级计算机、软件、网络专业2009—2010学年 第一学期《数据结构》期末试题(A 卷)一、 填空题(20空×1分=20分)1．（ ）是数据的最小单位，（ ）是讨论数据结构是涉及的最小数据单位。
2．在有尾指针rear 指示的循环单链表中，在表尾插入一个结点s 的操作序列是（ ）；删除开始结点的操作序列为（ ）。
3．（ ）可作为实现递归函数调用的一种数据结构。
4．栈和队列是两种特殊的线性表，栈的操作特性是（ ），队列的操作特性是（ ），栈和队列的主要区别在于（ ）。
5．数组通常只有两种运算：存取和（ ），这决定了数组通常采用（ ）结构来实现存储。
6．一棵有(0)n n >个结点的满二叉树共有（ ）个叶子结点和（ ）个非终端结点。
7．图的深度优先遍历类似于树的（ ）遍历，它所用到的数据结构是（ ）。
8．设有一个已按各元素值排好序的线性表，长度为125，用折半查找与给定值相等的元素，若查找成功，则至少需要比较（ ）次，至多需比较（ ）次。
9．对n 个待排序记录序列进行快速排序，所需要的最好时间是（ ），最坏时间是（ ）。
10．一棵5阶B_树中，除根结点外，每个结点的子树数目最少为（ ），最多为（ ）。
二、选择题(10题×2分=20分)1．下面（ ）不是算法所必须具备的特性。
A ．有穷性B ．确切性C ．高效性D ．可行性2．链表不具有的特点是（ ）。
A ．可随机访问任一元素B ．插入、删除不需要移动元素C ．不必事先估计存储空间D ．所需空间与线性表长度成正比3．使用双链表存储线性表，其优点是可以（ ）。
A ．提高检索速度B ．更方便数据的插入和删除C ．节约存储空间D ．很快回收存储空间4．一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是（ ）。
A ．54321B ．45321C ．43512D ．123455．一个队列的入队顺序是1，2，3，4，则队列的输出顺序是（ ）。
判断题，在每小题前面打对号表示正确或打叉号表示错误1. 数据的逻辑结构与数据元素本身的内容和形式无关。
对2. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。
对3. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，则对它分别进行前序遍历和按层遍历时具有相同的结果。
对4. 能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上相同。
错5. 邻接表表示只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。
错6. 在索引顺序结构上实施分块搜索，在等概率情况下，其平均搜索长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。
对7. 向一棵B树插入关键码的过程中，若最终引起树根结点的分裂，则新树比原树的高度减少1。
错8. 算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。
错9. 用字符数组存储长度为n的字符串，数组长度至少为n+1。
对10. 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
对11. 邻接矩阵适用于稀疏图的表示，邻接表适用于稠密图的表示。
错12. 对一个无向连通图进行一次深度优先搜索遍历时可以访问到图中的所有顶点。
对13. 在索引顺序结构的搜索中，对索引表只可以采取顺序搜索，不可以采用折半搜索。
错14. 图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。
对15. 线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。
对16. 在线性链表中删除结点时，只需要将被删结点释放，不需要修改任何指针。
错17. 在用单链表表示的链式队列Q中，假定队头指针为Q->front，队尾指针为Q->rear，则链队为空的条件为Q->front==Q->rear。
错18. 一棵AVL树的所有叶结点不一定在同一层次上，同样，平衡的m路搜索树的叶结点也不一定在同一层次上。
对19. 一个广义表((a),((b),c),(d))的表尾是“((b),c),(d)”。
第一章测试1【单选题】(2分)研究数据结构就是研究()。
A.数据的逻辑结构B.数据的逻辑结构、存储结构及其数据在运算上的实现C.数据的逻辑结构和存储结构D.数据的存储结构2【单选题】(2分)关于算法的说法，的是()。
A.算法的可行性是指指令不能有二义性B.其他三项都是的C.为解决某问题的算法和为该问题编写的程序含义是相同的D.算法最终必须由计算机程序实现3【单选题】(2分)数据的()包括集合、线性、树和图4种基本类型。
A.基本运算B.算法描述C.存储结构D.逻辑结构4【单选题】(2分)数据的存储结构包括顺序、链式、散列和()4种基本类型。
A.数组B.向量C.集合D.索引5【单选题】(2分)下面算法的时间复杂度为()。
for(i=0;i<m;i++)for(j=0;j<n;j++)A[i][j]=i*j;A.O(m2)B.O(m+n)C.O(m×n)D.O(n2)6【多选题】(2分)以下（）属于设计一个“好”的算法应考虑达到的目标。
A.健壮性B.效率与低存储量要求C.可读性D.正确性7【多选题】(2分)依据所有数据成员之间的逻辑关系的不同，数据结构分为（）。
A.线性结构B.物理结构C.非线性结构D.逻辑结构8【判断题】(2分)在存储数据时，不仅要考虑存储各数据元素的值，而且还要存储数据元素之间的关系。
A.对B.错9【判断题】(2分)在逻辑结构定义的操作与具体实现有关。
A.对B.错10【判断题】(2分)算法是对解题方法和步骤的描述。
A.对B.错11【判断题】(2分)算法分析的两个主要方面是时间复杂度和空间复杂度的分析。
A.错B.对第二章测试1【单选题】(2分)线性表是（）。
A.一个无限序列，可以为空。
B.一个无限序列，不能为空。
C.一个有限序列，可以为空。
D.一个有限序列，不能为空。
2【单选题】(2分)若某线性表中最常用的操作是取第i个元素和查找第i个元素的前驱，则采用（）存储方法最节省时间。
第一章数据结构概论1.1 判断下列叙述的对错。
如果正确，在题前打“√”，否则打“⨯”。
(1) 数据元素是数据的最小单位。
(2) 数据结构是数据对象与对象中数据元素之间关系的集合。
(3) 数据结构是具有结构的数据对象。
(4) 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。
(5) 算法和程序原则上没有区别，在讨论数据结构时二者是通用的。
1.2 判断下列叙述的对错。
如果正确，在题前打“√”，否则打“⨯”。
(1) 所谓数据的逻辑结构是指数据元素之间的逻辑关系。
(2) 同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等。
(3) 数据的逻辑结构与数据元素本身的内容和形式无关。
(4) 数据结构是指相互之间存在一种或多种关系的数据元素的全体。
(5) 从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。
1.3 填空题算法是一个有穷的指令集，它为解决某一特定任务规定了一个运算序列。
它应当具有输入、输出、( ① )、有穷性和可执行性等特性。
算法效率的度量分为( ② )和( ③ )。
( ② )主要通过在算法的某些部位插装时间函数来测定算法完成某一规定功能所需的时间。
而( ③)不实际运行算法，它是分析算法中语句的执行次数来度量算法的时间复杂性。
程序所需的存储空间包含两个部分( ④ )和( ⑤ )。
( ④ )空间的大小与输入输出数据的个数多少，数值大小无关；( ⑤)空间主要包括其大小与问题规模有关的成分变量所占空间，引用变量所占空间，以及递归栈所用的空间，还有在算法运行过程中动态分配和回收的空间。
1.4 设n为正整数, 分析下列各程序段中加下划线的语句的执行次数。
(1) for ( int i = 1; i <= n; i++ )for ( int j = 1; j <= n; j++ ) {c[i][j]=0.0;for ( int k = 1; k <= n; k++ )c[i][j] = c[i][j] + a[i][k] * b[k][j];}(2) x = 0; y = 0;for ( int i = 1; i <= n; i++ )for ( int j = 1; j <= i; j++ )for ( int k = 1; k <= j; k++ )x = x + y;1.5 试计算以下求和程序中所有语句的总执行次数。
1．算法分析的目的是( C )。
A.找出数据结构的合理性B.研究算法中输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2．（ B ）是具有相同特性数据元素的集合，是数据的子集。
A.数据符号B.数据对象C.数据D.数据结构3．用链表表示线性表的优点是( C )。
A.便于随机存取B.花费的存储空间比顺序表少C.便于插入与删除D.数据元素的物理顺序与逻辑顺序相同4．输入序列为（A,B,C,D）不可能的输出有（D ）。
A.(A,B,C,D)B. (D,C,B,A)C. (A,C,D,B) D . (C,A,B,D)5．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( B )。
A. front=maxSizeB. (rear+1)%maxSize=frontC. rear=maxSizeD. rear=front6．设有串t='I am a good student '，那么Substr(t,6,6)=（ D ）。
A. studentB. a good sC. goodD. a good7．设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85地址为（ B ）。
D. 408．已知广义表LS=(A,(B,C,D),E)运用head和tail函数，取出LS中原子b的运算（C ）。
A. Gethead(Gethead(LS))B. Gettail(Gethead(LS))C. Gethead(Gethead(Gettail(LS)))D. Gethead(Gettail(LS))9．若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为( A ) 。
A. CDBGFEAB. CDBFGEAC. CDBAGFED. BCDAGFE10．下列存储形式中，( C ) 不是树的存储形式。
1判断题（）1. 数据的逻辑结构与数据元素本身的内容和形式无关。
（）2. 线性表的逻辑顺序与物理顺序总是一致的。
（）3. 若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。
（）4. 对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的。
（）5. 最优二叉搜索树的任何子树都是最优二叉搜索树。
（）6. 在二叉搜索树上插入新结点时，不必移动其它结点，仅需改动某个结点的指针，使它由空变为非空即可。
（）7. 有n（n≥1）个顶点的有向强连通图最少有n条边。
（）8. 连通分量是无向图中的极小连通子图。
（）9. 二叉树中任何一个结点的度都是2。
（）10. 单链表从任何一个结点出发，都能访问到所有结点。
（）11.线性表的长度是线性表占用的存储空间的大小。
（）12.队列只能采用链式存储方式。
（）13.用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关。
（）14.由二叉树的先序序列和中序序列能唯一确定一棵二叉树。
（）15.图中一个顶点i的出度等于其邻接矩阵中第i列的非0元个数。
（）16. 线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。
（）17.数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。
（）18.线性表中的每个结点最多只有一个前驱和一个后继。
（）19.二叉排序树查找总比顺序查找速度快。
（）20.对具有n个顶点的连通图进行深度优先遍历，所得顶点序列是唯一的。
（）21.线性表中各个数据元素的类型必须是相同的。
（）22.B+树是一种特殊的二叉树。
（）23.栈可视为一种特殊的线性表。
（）24.快速排序总是比其它排序方法快。
（）25.使用双向链表存储数据，可以提高查找（定位运算）的速度。
（）26.最小生成树是边数最少的生成树。
二、单选题1 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。
客观题第一章绪论一、判断题(1）数据的逻辑结构与数据元素本身的内容和形式无关。
(2）数据元素是数据的最小单位。
(3）算法是对解题方法和步骤的描述。
(4）程序和算法原则上没有区别，在讨论数据结构时可以通用。
(5）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。
(6）数据的存储结构是数据的逻辑结构的存储映像。
二、选择题(l）数据结构通常是研究数据的（）及它们之间的相互联系。
A．存储结构和逻辑结构 B．存储和抽象 C．联系和抽象 D．联系与逻辑(2) 下列与数据元素有关的叙述中错误的是（）。
A．数据元素是有独立含义的数据最小单位 B．数据元素是描述数据的基本单位C．数据元素可以称做结点 D．数据元素可以称做记录(3）数据结构中，在逻辑上可以把数据结构分成：( ）。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构(4）数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为( ）。
A．存储结构 B．逻辑结构 C．顺序存储结构 D．链式存储结构(5）非线性结构的数据元素之间存在（）。
A．一对一关系 B．一对多关系 C．多对多关系 D. B 或 C (6）在非线性结构中，每个结点（）。
A. 无直接前驱B．只有一个直接前驱和个数不受限制的直接后继C．只有一个直接前驱和直接后继D．有个数不受限制的直接前驱和直接后继(7）除了考虑存储数据结构本身所占用的空间外，实现算法所用的辅助空间的多少称为算法的（）。
A．时间效率 B．空间效率 C．硬件效率 D．软件效率(8)以下属于顺序存储结构优点的是（）。
A．存储密度大 B．插入运算方便 C．删除运算方便D．可方便地用于各种逻辑结构的存储表示(9)数据结构研究的内容是（）。
一、判断题(每题1分,共131分)1. 线性表的逻辑顺序总是与其物理顺序一致。
（）【答案】错2. 线性表的顺序存储优于链式存储。
（）【答案】错3. 在长度为n的顺序表中，求第i个元素的直接前驱算法的时间复杂度为0（1）。
（）【答案】对4. 若一棵二叉树中的结点均无右孩子，则该二叉树的中根遍历和后根遍历序列正好相反。
（）【答案】错5. 顺序表和一维数组一样，都可以按下标随机（或直接）访问。
（）#【答案】对6. 内部排序是指排序过程在内存中进行的排序。
（）【答案】对7. 当待排序序列初始有序时，简单选择排序的时间复杂性为O(n)。
（）【答案】错8. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。
( )【答案】对9. 任何一棵二叉树的叶结点在三种遍历中的相对次序是不变的。
（）【答案】对:10. 若将一批杂乱无章的数据按堆结构组织起来,则堆中数据必然按从小到大的顺序线性排列。
( )【答案】错11. 如果采用如下方法定义一维字符数组：int maxSize = 30;char * a = new char[maxSize];则这种数组在程序执行过程中不能扩充。
（）【答案】错12. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。
（）【答案】对13. 对稀疏矩阵进行压缩存储是为了节省存储空间。
（）【答案】对14. 当向一个最小堆插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。
( )【答案】对;15. 哈希查找法中解决冲突问题的常用方法是除留余数法。
（）【答案】错16. 对具有n个结点的堆进行插入一个元素运算的时间复杂度为O(n)。
( )【答案】错17. 堆排序是一种稳定的排序算法。
( )【答案】错18. 如果有向图中各个顶点的度都大于2，则该图中必有回路。
( )【答案】错19. 在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置。
数据结构期末习题答案第⼀章绪论⼀，选择题1．组成数据的基本单位是（）A．数据项B．数据类型C．数据元素D．数据变量2．数据结构是研究数据的（）以及它们之间的相互关系。
A．理想结构，物理结构B．理想结构，抽象结构C．物理结构，逻辑结构D．抽象结构，逻辑结构3．算法分析的两个主要⽅⾯是（）A．正确性和简单性B．可读性和⽂档性C．数据复杂性和程序复杂性D．时间复杂度和空间复杂度4．算法分析的⽬的是（）。
A．找出数据结构的合理性B．研究算法中的输⼊和输出的关系C．分析算法的效率以求改进D．分析算法的易懂性和⽂档性5. 算法的时间复杂度取决于（）A．问题的规模 B. 待处理数据的初态 C. A和B Ｄ．以上都不是6．⼀个算法应该是（）。
A．程序 B．问题求解步骤的描述 C．要满⾜五个基本特性 D．A和C. 7. 下⾯关于算法说法错误的是（）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可⾏性是指指令不能有⼆义性D. 以上⼏个都是错误的8．从逻辑上可以把数据结构分为（）两⼤类。
A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、⾮线性结构 D．初等结构、构造型结构9．程序段 for ( i=n-1;i>=1;i--)for (j=1j<=i;j++)if( A[j]>A[j+1])A[j]与A[j+1]对换；其中 n为正整数，则最后⼀⾏的语句频度在最坏情况下是（）A． O（n） B． O(nlogn) C.．O(n3) D．O(n2)10．连续存储设计时，存储单元的地址（）。
A．⼀定连续 B．⼀定不连续 C．不⼀定连续 D．部分连续，部分不连续⼆，判断题1．数据结构的抽象操作的定义与具体实现有关。
( )2．数据结构是数据对象与对象中数据元素之间关系的集合。
3．在顺序存储结构中，有时也存储数据结构中元素之间的关系。
( )4．数据的逻辑结构是指各数据元素之间的逻辑关系，是⽤户按使⽤的需要建⽴的。
2023年国家电网招聘之电网计算机高分通关题型题库附解析答案单选题（共40题）1、下列关于双核技术的叙述中，正确的是（）。
A.双核就是指主板上有两个CPUB.双核是利用超线程技术实现的C.双核就是指CPU上集成两个运算核心D.主板上最大的一块芯片就是核心【答案】 C2、RAM具有的特点是()。
A.海量存储B.存储在其中的信息可以永久保存C.一旦断电，存储在其上的信息将全部消失且无法恢复D.存储在其中的数据不能改写【答案】 C3、以下（）不是队列的基本运算。
A.从队尾插入一个新元素B.从队列中删除第 i 个元素C.判断一个队列是否为空D.读取队头元素的值【答案】 B4、甲状旁腺腺瘤分泌：（）A.PTHB.降钙素C.两者均有D.两者均无【答案】 A5、SMTP协议的下层协议为____。
A.ARPB.IPC.TCPD.UDP【答案】 C6、主机与 I/O 设备传送数据时，采用（）时主机与设备是串行工作的。
A.程序查询方式B.中断方式C.DMA 方式D.通道方式【答案】 A7、以下算法中属于报文摘要算法的是（）.A.MD5B.DESC.RSAD.AES【答案】 A8、为使数字信号传输得更远，可采用的设备是（）。
A.中继器B.放大器C.网桥D.路由器【答案】 A9、WLAN（Wireless LAN）是计算机网络与无线通信技术相结合的产物。
下列哪些不属于WLAN 技术标准？( )。
A.802.11aB.802.11bC.802.11cD.802.11g【答案】 C10、对线下零售而言，做好大数据分析应用的前提是（）。
A.增加统计种类B.扩大营业面积C.增加数据来源D.开展优惠促销【答案】 C11、下列哪一条不是数据库管理系统必须提供的基本功能()。
A.数据操纵B.安全性保护和完整性控制C.数据定义D.可移植性保证【答案】 D12、网桥有两个显著的优点，其一是(4)()，其二是利用公共通信链路实现了两个远程LAN的互联。
客观题第一章绪论一、判断题(1）数据的逻辑结构与数据元素本身的内容和形式无关。
(2）数据元素是数据的最小单位。
(3）算法是对解题方法和步骤的描述。
(4）程序和算法原则上没有区别，在讨论数据结构时可以通用。
(5）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。
(6）数据的存储结构是数据的逻辑结构的存储映像。
二、选择题(l）数据结构通常是研究数据的（）及它们之间的相互联系。
A．存储结构和逻辑结构 B．存储和抽象 C．联系和抽象 D．联系与逻辑(2) 下列与数据元素有关的叙述中错误的是（）。
A．数据元素是有独立含义的数据最小单位 B．数据元素是描述数据的基本单位C．数据元素可以称做结点 D．数据元素可以称做记录(3）数据结构中，在逻辑上可以把数据结构分成：( ）。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构(4）数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为 ( ）。
A．存储结构 B．逻辑结构 C．顺序存储结构 D．链式存储结构(5）非线性结构的数据元素之间存在（）。
A．一对一关系 B．一对多关系 C．多对多关系 D. B 或 C (6）在非线性结构中，每个结点（）。
A. 无直接前驱B．只有一个直接前驱和个数不受限制的直接后继C．只有一个直接前驱和直接后继D．有个数不受限制的直接前驱和直接后继(7）除了考虑存储数据结构本身所占用的空间外，实现算法所用的辅助空间的多少称为算法的（）。
A．时间效率 B．空间效率 C．硬件效率 D．软件效率(8)以下属于顺序存储结构优点的是（）。
A．存储密度大 B．插入运算方便 C．删除运算方便D．可方便地用于各种逻辑结构的存储表示(9)数据结构研究的内容是（）。
A．数据的逻辑结构 B．数据的存储结构C．建立在相应逻辑结构和存储结构上的算法 D．包括以上三个方面(10)链式存储的存储结构所占存储空间（）。
A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点值，另一部分存放结点所占单元数(11)一个正确的算法应该具有 5 个特性，除输入、输出特性外，另外 3 个特性是（）。
A．确定性、可行性、有穷性 B．易读性、确定性、有效性C．有穷性、稳定性、确定性 D．可行性、易读性、有穷性(12)以下关于数据的逻辑结构的叙述中正确的是（）。
A．数据的逻辑结构是数据间关系的描述B．数据的逻辑结构反映了数据在计算机中的存储方式C．数据的逻辑结构分为顺序结构和链式结构D．数据的逻辑结构分为静态结构和动态结构(13)设问题的规模为 n ，分析以下程序段：k = n ; /* n > l */m = 0 ;while ( k > = ( m + l ) * ( m - l ) )m ++；以上程序段的算法时间复杂度是( )A. O( n )B. O(1)C. O(n)D. O( n2 )(14)设问题的规模为n ，分析以下程序段：a = 10 ;b = l00 ;while （b＞ 0 ){ a + + ; b ――；}以上程序段的算法时间复杂度是（）。
A.O( n )B. O(1)C. O(n)D. O( n2 )(15)设语句 s=s+i 的时间是单位时间，则语句：s=0;for (i=l;i<=n;i++)s=s+i;的时间复杂度为：( ）。
A. O(l)B. O(n)C. O(n2)D. O(n3)(16)算法分析的主要任务是（）。
A．探讨算法的正确性和可读性 B．探讨数据组织方式的合理性C．为给定问题寻找一种性能良好的解决方案 D．研究数据之间的逻辑关系(17)以下叙述中正确的是（）。
A．顺序存储方式只能用于存储线性结构B．链式存储方式只能用于存储线性结构,探讨数据组织方式的合理性,研究数据之间的逻辑关系C．顺序存储和链式存储都可以用于线性和非线性结构D．以上三种都不对(18)以下叙述中正确的是（）。
A．数据元素是数据处理的最小单位 B．数据项是数据处理的基本单位C．关键字是能够惟一标识一个数据元素的数据项 D．数据结构和数据类型的概念是等价的第二章线性表一、判断题(l）线性表的链式存储结构优于顺序存储。
(2）链表的每个结点都恰好包含一个指针域。
(3）线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。
(4）在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。
(5）在单链表中，任何两个元素的存储位置之间都有固定的联系，所以可以从头结点开始查找任何一个元素。
(6）在线性表的顺序结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。
(7）顺序存储方式的优点是存储密度大，插入、删除效率高。
(8）在单链表中，要取得某个元素，只要知道该元素的指针即可，因此单链表是随机存取的存储结构。
(9）顺序存储的线性表可以实现随机存取。
(10）线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。
二、选择题(1)线性表是（）A．一个有限序列，可以为空 B．一个有限序列，不可以为空C．一个无限序列，可以为空 D．一个无限序列，不可以为空(2) 一维数组与线性表的特征是（）。
A．前者长度固定，后者长度可变 B．两者长度均固定C．后者长度固定，前者长度可变 D．两者长度均可变(3) 用单链表方式存储的线性表，存储每个结点需要两个域，一个数据域，另一个是( ).A．当前结点所在地址域 B．指针域 C．空指针域 D．空闲域(4) 用链表表示线性表的优点是（）。
A．便于随机存取 B．便于进行插入和删除操作C．占用的存储空间较顺序表少 D．元素的物理顺序与逻辑顺序相同(5) 在具有 n 个结点的单链表中，实现___的操作，其算法的时间复杂度都是O（n）。
A．遍历链表和求链表的第 i 个结点 B．在地址为 P 的结点之后插入一个结点C．删除开始结点 D．删除地址为 P 的结点的后继结点(6)下面关于线性表的叙述中，错误的是（）。
A．线性表采用顺序存储必须占用一片连续的存储单元B．线性表采用顺序存储便于进行插入和删除操作C．线性表采用链式存储不必占用一片连续的存储单元D．线性表采用链式存储便于进行插入和删除操作(7)已知单链表的每个结点包括一个指针域next，它指向该结点的后继结点。
现要将指针 q指向的新结点插入到指针 p 指向的结点之后，下面的操作序列中正确的是（）。
A . q = p 一＞next ; p 一＞ next = q 一＞next ;B . p 一＞next = q 一＞next ; q = p 一＞next ;C . q 一＞next = p 一＞next; p 一＞next = q ;D . p 一＞next = q ; q 一＞next = p 一＞next ;(8)设 a l，a2， a3为三个结点； p , 10 , 20 代表地址，则如下的链表存储结构称为______。
A．链表 B．单链表 C．双向循环链表 D．双向链表(9)单链表的存储密度（）。
A．大于 1 B．等于1 C．小于1 D．不能确定(10)己知一个顺序存储的线性表，设每个结点需占 m 个存储单元，若第一个结点的地址al ，则第i个结点的地址为（）。
A. al+(i-1)*mB. al+i*mC. al-i*mD. al+(i+1)*m(11)在 n 个结点的顺序表中，算法的时间复杂度是 O(l）的操作是（）。
A．访问第i个结点（1 ≤ i ≤ n）和求第 i 个结点的直接前驱（2 ≤ i ≤ n)B．在第 i 个结点之后插入一个新结点（1 ≤ i ≤ n-1）C．删除第 i 个结点（ 1 ≤ i ≤ n )D．将 n 个结点从小到大排序(12)在线性表中（）只有一个直接前驱和一个直接后继。
A．首元素 B．中间元素 C．尾元素 D．所有元素(13)对具有 n 个结点的线性表进行查找运算，所需的算法时间复杂度为（）。
A. 0 ( n2 )B. 0 ( nlog2n )C. O ( log2n )D. O ( n )(14)线性表采用顺序存储的缺点是（）。
A．存储密度降低 B．只能顺序访问C．元素的逻辑顺序与物理顺序不一致 D．插入、删除操作效率低(15)以下链表结构中，从当前结点出发能够访问到任一结点的是（）。
A．单向链表和双向链表 B．双向链表和循环链表C．单向链表和循环链表 D．单向链表、双向链表和循环链表(16)线性表是具有 n 个（）的有限序列。
A．数据项 B．数据元素 C．表元素 D．字符(17)若长度为 n 的线性表采用链式存储结构，访问其第 i 个元素的算法时间复杂度为（）。
A. 0 ( l )B. 0 ( n )C. 0 ( n2 )D. 0 ( log2n )(18)指针 P 指向循环链表 L 的首元素的条件是（）。
A. P＝＝LB. L->next＝＝PC.P->next= =NULLD. P->next＝＝L(19)指针 P 所指的元素是双循环链表 L 的尾元素的条件是（）。
A. P＝＝LB. P->prior＝＝LC. P＝＝NULLD. P->next＝＝L(20)不带头结点的单链表L为空的条件是( )A. L!＝NULLB. L＝＝NULLC. L->next＝＝NULLD. L->next＝＝L(21)带头结点的单链表L为空的条件是( )A. L!＝NULLB. L＝＝NULLC. L->next＝＝NULLD. L->next＝＝L(22)两个指针 P 和 Q ，分别指向单链表的两个元素， P 所指元素是 Q 所指元素前驱的条件是（）。
A. P->next＝＝Q->nextB. P->next＝＝QC. Q->next＝＝PD. P＝＝Q(23)在长度为 n 的顺序表中，若要删除第 i (1≤i≤n ）个元素，则需要向前移动元素的次数为（）。
A. 1B. n 一 iC. n 一 i + 1D. n 一 i 一l(24)在长度为 n 的顺序表中第 i (1≤i≤n）个位置上插入一个元素时，为留出插入位置所需移动元素的次数为（）。
A. n - iB. iC. n – i + 1D. n - i - l(25)假定己建立以下动态链表结构，且指针 Pl 和 P2 已指向如图所示的结点：则以下可以将 P2 所指结点从链表中删除并释放该结点的语句组是( )A. pl -> next = p2 -> next ; free ( pl ) ;B. pl = p2 ; free ( p2 ) ;C. pl -> next = p2 -> next ；free ( p2 ) ;D. pl = p2 -> next ; free ( p2) ;(26)若已建立如图所示的单向链表：则以下不能将 s 所指的结点插入到链表尾部，构成新的单向链表的语句组是（）。
