公共基础

一、算法3、例题讲解算法的时间复杂度是指( C )A、执行算法程序所需要的时间B、算法程序的长度C、算法执行过程中所需要的基本运算次数D、算法程序中的指令条数算法的基本特征是可行性、确定性、【1】和拥有足够的情报。

【答案】:有穷性算法的空间复杂度是指( D )A) 算法程序的长度B) 算法程序中的指令条数C) 算法程序所占的存储空间D) 执行过程中所需要的存储空间在计算机中，算法是指（B）A) 加工方法B) 解题方案的准确而完整的描述C) 排序方法D) 查询方法算法分析的目的是( D )A) 找出数据结构的合理性B) 找出算法中输入和输出之间的关系C) 分析算法的易懂性和可靠性D) 分析算法的效率以求改进算法的工作量大小和实现算法所需的存储单元多少分别称为算法的【1 】。

【答案】:时间复杂度和空间复杂度一、算法算法的时间复杂度是指( C )A、执行算法程序所需要的时间B、算法程序的长度C、算法执行过程中所需要的基本运算次数D、算法程序中的指令条数算法的基本特征是可行性、确定性、【1】和拥有足够的情报。

【答案】:有穷性算法的空间复杂度是指( D )A) 算法程序的长度B) 算法程序中的指令条数C) 算法程序所占的存储空间D) 执行过程中所需要的存储空间在计算机中，算法是指（B）A) 加工方法B) 解题方案的准确而完整的描述C) 排序方法D) 查询方法算法分析的目的是( D )A) 找出数据结构的合理性B) 找出算法中输入和输出之间的关系C) 分析算法的易懂性和可靠性D) 分析算法的效率以求改进算法的工作量大小和实现算法所需的存储单元多少分别称为算法的【1 】。

【答案】:时间复杂度和空间复杂度数据结构是一门研究数据组织、存储和运算的一般方法的学科。

数据元素是数据的基本单位，即数据集合中的个体。

有时一个数据元素可由若干数据项(Data Item)组成。

数据项是数据的最小单位。

PS:数据元素是数据的基本单位，数据项是属于数据元素的！数据项是最小单位！顺序存储结构的三个弱点：1.作插入或删除操作时，需移动大量元数。

2.长度变化较大时，需按最大空间分配。

3.表的容量难以扩充。

链式存储每个节点都由两部分组成：数据域和指针域。

数据域存放元素本身的数据，指针域存放指针。

数据元素之间逻辑上的联系由指针来体现。

链接存储结构特点：1、比顺序存储结构的存储密度小(每个节点都由数据域和指针域组成)。

2、逻辑上相邻的节点物理上不必相邻。

3、插入、删除灵活(不必移动节点，只要改变节点中的指针)链表不具有的特点是（B ）A) 不必事先估计存储空间B) 可随机访问任一元素C) 插入删除不需要移动元素D) 所需空间与线性表长度成正比数据结构分为逻辑结构与存储结构，线性链表属于【1】。

【答案】存储结构 数据结构中，与所使用的计算机无关的是数据的( C )A) 存储结构B) 物理结构C) 逻辑结构D) 物理和存储结构数据的逻辑结构有线性结构和【2】两大类。

非线性结构顺序存储方法是把逻辑上相邻的结点存储在物理位置【3】的存储单元中。

【答案】相邻数据处理的最小单位是( C )A)数据B)数据元素C) 数据项D) 数据结构数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及( A )A) 数据的存储结构B) 计算方法C) 数据映象D) 逻辑存储线性表的顺序存储结构和线性表的链式存储结构分别是( B )A) 顺序存取的存储结构、顺序存取的存储结构B) 随机存取的存储结构、顺序存取的存储结构C) 随机存取的存储结构、随机存取的存储结构D) 任意存取的存储结构、任意存取的存储结构根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成( C )A) 动态结构和静态结构B) 紧凑结构和非紧凑结构C) 线性结构和非线性结构D) 内部结构和外部结构数据结构包括数据的逻辑结构、数据的【4】以及对数据的操作运算。

【答案】物理结构（或存储结构）数据的基本单位是【5】。

【答案】数据元素下列叙述中，错误的是（B ）A) 数据的存储结构与数据处理的效率密切相关B) 数据的存储结构与数据处理的效率无关C) 数据的存储结构在计算机中所占的空间不一定是连续的D) 一种数据的逻辑结构可以有多种存储结构数据的存储结构是指（B ）A）数据所占的存储空间B）数据的逻辑结构在计算机中的表示C）数据在计算机中的顺序存储方式D）存储在外存中的数据线性表的顺序存储结构及其插入与删除操作特点：1、线性表中数据元素类型一致，只有数据域，存储空间利用率高。

2、所有元素所占的存储空间是连续的。

3、各数据元素在存储空间中是按逻辑顺序依次存放的（a）做插入、删除时需移动大量元素。

（b）空间估计不明时，按最大空间分配。

插入算法删除算法顺序存储方法是把逻辑上相邻的结点存储在物理位置【1】的存储单元中。

【答案】相邻长度为n的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为【2】。

【答案】n/2线性表L=(a1,a2,a3,…ai，…an)，下列说法正确的是（D ）A) 每个元素都有一个直接前件和直接后件B) 线性表中至少要有一个元素C) 表中诸元素的排列顺序必须是由小到大或由大到小D) 除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件当线性表采用顺序存储结构实现存储时，其主要特点是【1】。

【答案】逻辑结构中相邻的结点在存储结构中仍相邻。

线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D ）A) 必须是连续的B) 部分地址必须是连续的C) 一定是不连续的D) 连续不连续都可以下列叙述中，错误的是（B ）A) 数据的存储结构与数据处理的效率密切相关B) 数据的存储结构与数据处理的效率无关C) 数据的存储结构在计算机中所占的空间不一定是连续的D) 一种数据的逻辑结构可以有多种存储结构删除算法Array 顺序存储方法是把逻辑上相邻的结点存储在物理位置【1】的存储单元中。

【答案】相邻长度为n的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为【2】。

【答案】n/2线性表L=(a1,a2,a3,…ai，…an)，下列说法正确的是（D ）A) 每个元素都有一个直接前件和直接后件B) 线性表中至少要有一个元素C) 表中诸元素的排列顺序必须是由小到大或由大到小D) 除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件栈和队列的共同特点是（C ）A)都是先进先出B) 都是先进后出C) 只允许在端点处插入和删除元素D) 没有共同点如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是（B ）A) e3,e1,e4,e2 B) e2,e4,e3,e1C) e3,e4,e1,e2 D) 任意顺序一些重要的程序语言(如C语言和Pascal语言) 允许过程的递归调用。

而实现递归调用中的存储分配通常用（ A ）A) 栈B) 堆C) 数组D) 链表栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是（B ）A) ABCED B) DCBEAC) DBCEA D) CDABE栈通常采用的两种存储结构是（A ）A) 线性存储结构和链表存储结构B) 散列方式和索引方式C) 链表存储结构和数组D) 线性存储结构和非线性存储结构栈和队列通常采用的存储结构是【1】。

【答案】链式存储和顺序存储下列数据结构中，按先进后出原则组织数据的是（B ）A) 线性链表B) 栈C) 循环链表D) 顺序表当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。

这种情况称为【2】。

答案：上溢由两个栈共享一个存储空间的好处是（B ）A) 减少存取时间，降低下溢发生的机率B) 节省存储空间，降低上溢发生的机率C) 减少存取时间，降低上溢发生的机率D) 节省存储空间，降低下溢发生的机率下列关于栈的叙述中正确的是（D ）Ａ)在栈中只能插入数据B）在栈中只能删除数据C）栈是先进先出的线性表D）栈是后进先出的线性表 下列关于队列的叙述中正确的是（C ）Ａ）在队列中只能插入数据B）在队列中只能删除数据C）队列是先进先出的线性表D）队列是后进先出的线性表二叉树的性质第三层上(i=3)，有23-1=4个节点。

第四层上(i=4)，有24-1=8个节点此树的深度h=4，共有24-1=15个节点、设一棵完全二叉树共有700个结点，则在该二叉树中有350 个叶子结点。

2、在深度为5的满二叉树中，叶子结点的个数为（ C ）A) 32 B) 31 C) 16 D) 151、设一棵二叉树的中序遍历结果为DBEAFC,前序遍历结果为ABDECF，则后序遍历结果为：DEBFCA2、已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为（B ）A) GEDHFBCA B) DGEBHFCAC) ABCDEFGH D) ACBFEDHG具有3个结点的二叉树有（D ）A) 2种形态B) 4种形态C) 7种形态D) 5种形态设有下列二叉树：对此二叉树前序遍历的结果为（B ）A) ZBTTCPXA B) ATBZXCTP C) ZBTACTXP D) ATBZXCPT结构化程序设计的3种结构是（ D ）A) 顺序结构、选择结构、转移结构B) 分支结构、等价结构、循环结构C) 多分支结构、赋值结构、等价结构D) 顺序结构、选择结构、循环结构在设计程序时，应采纳的原则之一是（D ）A) 不限制goto语句的使用B) 减少或取消注解行C) 程序越短越好D) 程序结构应有助于读者理解程序设计语言的基本成分是数据成分、运算成分、控制成分和（D ）A) 对象成分B) 变量成分C) 语句成分D) 传输成分结构化程序设计主要强调的是（D ）A) 程序的规模B) 程序的效率C) 程序设计语言的先进性D) 程序易读性以下不属于对象的基本特点的是（A ）A) 分类性B) 多态性C) 继承性D) 封装性对建立良好的程序设计风格，下面描述正确的是（A ）A) 程序应简单、清晰、可读性好B) 符号名的命名只要符合语法C) 充分考虑程序的执行效率D) 程序的注释可有可无在结构化程序设计思想提出之前，在程序设计中曾强调程序的效率，现在，与程序的效率相比，人们更重视程序的（C）A) 安全性B) 一致性C) 可理解性D) 合理性下列叙述中，不属于结构化程序设计方法的主要原则的是（B）A) 自顶向下B) 由底向上C) 模块化D) 限制使用goto语句对象实现了数据和操作的结合，是指对数据和数据的操作进行（C ）A) 结合B) 隐藏C) 封装D) 抽象在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送（D ）A）调用语句B）命令C）口令D）消息信息屏蔽的概念与下述哪一种概念直接相关（B ）A）软件结构定义B）模块独立性C）模块类型划分D）模块偶合度下列对对象概念描述错误的是（A ）A）任何对象都必须有继承性B）对象是属性和方法的封装体C）对象间的通讯靠消息传递D）操作是对象的动态属性面向对象的设计方法与传统的面向过程的方法有本质的不同,它的基本原理是（C ）A) 模拟现实世界中不同事物之间的联系B) 强调模拟现实世界中的算法而不强调概念C) 使用现实世界的概念抽象地思考问题从而自然地解决问题D) 鼓励开发者在软件开发的绝大部分中都用实际领域的概念去思考在面向对象的程序设计中，类描述的是具有相似性质的一组【1】。