当前位置：文档之家 › 考点1：数据结构与算法

考点1：数据结构与算法

  • 格式：doc
  • 大小：202.00 KB
  • 文档页数：23

第 1 页 共 1 页 1.下列叙述中正确的是（ ）。答案：B A）所谓算法就是计算方法 B）程序可以作为算法的一种描述方法 C）算法设计只需考虑得到计算结果 D）算法设计可以忽略算法的运算时间 题目解析:算法是一组有穷指令集，是解题方案的准确而完整的描述。通俗地说，算法就是计算机解题的过程,重在解题方案的设计，并且不等于计算方法，故A和C选项不正确，程序的编制不可能优于算法的设计，但算法的描述可以用程序、伪代码、流程图来描述，故B选项正确。算法要求执行过程中所需要的基本运算次数和时间最少，即时间复杂度最低，所以C选项不正确。正确答案为B。 2.下列各序列中不是堆的是（ ）。答案：C A）(91,85,53,36,47,30,24,12) B）(91,85,53,47,36,30,24,12) C）(47,91,53,85,30,12,24,36) D）(91,85,53,47,30,12,24,36) 题目解析:堆可以看成一棵完全二叉树：任一根节点>=左右孩子（或者<=）（大的叫大根堆，小的叫小根堆。）注意一个堆中的这种性质有一致性，不能既有大于又有小于情况存在,这题可以这么做，把结点按照完全二叉树画出来就一目了然了。这个题目很明显91是最大的根，而C选项是"左根右"的排序，那么91的左边只有47，其他都在右边，而右边无法按照此顺序排列，故选C。 3.深度为5的完全二叉树的结点数不可能是（ ）。答案：A A）15 B）16 C）17 D）18 题目解析:对于满二叉树，叶子结点的数目等于2（n-1）,n为深度，这里就是2的5-1=4次方，就是16。 4.设二叉树如下：

则前序序列为（ ）。答案：A A）ABDEGCFH B）DBGEAFHC C）DGEBHFCA D）ABCDEFGH 题目解析:前序遍历首先访问根结点然后遍历左子树，最后遍历右子树；在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。故正确选项选A；B选项为中序遍历。C选项为后序遍历；D选项不正确。 第 2 页 共 2 页

5.下列叙述中正确的是（ ）。答案：A A）循环队列是顺序存储结构 B）循环队列是链式存储结构 C）循环队列是非线性结构 D）循环队列的插入运算不会发生溢出现象 题目解析:循环队列属于队列的特例和栈同属于线性结构，C选项不正确。在顺序队列中,由于数组空间不够而产生的溢出叫真溢出；顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出称为假溢出；假溢出是由于队尾rear的值和队头front的值不能由所定义数组下界值自动转为数组上界值而产生的，解决的办法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列，因此，顺序队列通常都采用顺序循环队列结构；栈的存储方式有顺序存储和链式存储，故正确选项为A；B选项不正确。循环队列虽然能解决由于假溢出，却不能解决在顺序队列中,由于数组空间不够而产生的溢出的真溢出，故选项C不正确。 6.下列叙述中正确的是（ ）。答案：D A）所有数据结构必须有根结点 B）所有数据结构必须有终端结点（即叶子结点） C）只有一个根结点，且只有一个叶子结点的数据结构一定是线性结构 D）没有根结点或没有叶子结点的数据结构一定是非线性结构 题目解析:只有一个空节点的结构也属数据结构，所以A和B选项不正确；有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件的数据结构才属于线性结构，其它的都属于非线性结构，故C选项不正确，正确选项为D。 7.下列关于算法的描述中错误的是（ ）。答案：D A）算法强调动态的执行过程，不同于静态的计算公式 B）算法必须能在有限个步骤之后终止 C）算法设计必须考虑算法的复杂度 D）算法的优劣取决于运行算法程序的环境 题目解析:算法的优劣取决自身的运行效率，时间和空间复杂度高低，并不取决于运行算法程序的环境，故D选项错误。 8.设二叉树如下：

则中序序列为（ ）。答案：B A）ABDEGCFH B）DBGEAFHC C）DGEBHFCA D）ABCDEFGH 题目解析:中序遍历（LDR）是指首先遍历左子树，然后访问根结点，最后遍历右子树；故 第 3 页 共 3 页

正确答案为B。 9.线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有（ ）。答案：B A）节省存储空间 B）插入与删除运算效率高 C）便于查找 D）排序时减少元素的比较次数 题目解析:顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大（＝1），存储空间利用率高。缺点：插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 优点：插入或删除元素时很方便效率高，使用灵活。缺点：存储密度小（<1），存储空间利用率低。故正确选项为B。 10.深度为７的完全二叉树中共有125个结点，则该完全二叉树中的叶子结点数为（ ）。答案：B A）62 B）63 C）64 D）65 题目解析: 对于满二叉树，结点的数目等于2n-1，叶子结点数目为2n-1，n为深度，这里就是2的7次方-1，就是127个结点，叶子结点是64个，然而题目中只有125个结点，说明少了两个结点，那么就少了一个叶子结点，即63个。 11.下列叙述中正确的是（ ）。答案：C A）所谓有序表是指在顺序存储空间内连续存放的元素序列 B）有序表只能顺序存储在连续的存储空间内 C）有序表可以用链接存储方式存储在不连续的存储空间内 D）任何存储方式的有序表均能采用二分法进行查找 题目解析:有序表可以用顺序存储空间内连续存放的元素序列来实现，也可以用链接存储方式存储在不连续的存储空间内，已达到逻辑上连续，存储空间上不一定连续的效果。二分法进行查找只适用于顺序存储的有序表。故选项C正确。 12.设二叉树如下：

则后序序列为（ ）。答案：C A）ABDEGCFH B）DBGEAFHC C）DGEBHFCA D）ABCDEFGH 第 4 页 共 4 页

题目解析:后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。故正确选项为C。 13.下列叙述中正确的是（ ）。答案：B A）结点中具有两个指针域的链表一定是二叉链表 B）结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构 C）二叉树只能采用链式存储结构 D）循环链表是非线性结构 题目解析:结点中尽管有两个指针域但没有分别指向两个不同的结点就不是二叉链表，故A选项不正确；二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个后继。它可采用顺序存储结构和链式存储结构，故C选项不正确；循环链表是在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点的线性结构，故D选项不正确；当结点中两个指针分别指向前驱结点和后继结点是为线性结构，当指向两个不同的前驱或后继结点时为非线性结构，故B选项正确。 14.设某二叉树中共有140个结点，其中有40个度为1的结点。则（ ）。答案：D A）该二叉树中有51个叶子结点 B）该二叉树中有50个叶子结点 C）该二叉树中有51个度为2的结点 D）不可能有这样的二叉树 题目解析:140个结点除去40个度为1的结点，说明有100个度为2的结点，而根据二叉树性质，这个数值无法得出故本题答案选D。 15.带链的栈与顺序存储的栈相比，其优点是（ ）。答案：C A）入栈与退栈操作方便 B）可以省略栈底指针 C）入栈操作时不会受栈存储空间的限制而发生溢出 D）以上都不对 题目解析:带链的栈与顺序存储的栈相比优点是不受连续存储空间大小的限制，即不需考虑栈满的问题，故C选项正确。 16.某二叉树的前序序列为ABCD，中序序列为DCBA，则后序序列为（ ）。答案：B A）BADC B）DCBA C）CDAB D）ABCD 题目解析:在二叉树前序遍历中ABCD中A是根节点，二在后序遍历中根结点位于最后，所以正确答案为B。 17.某系统结构图如下所示

该系统结构图的最大扇入数是（ ）。答案：A A）n 第 5 页 共 5 页

B）1 C）2 D）3 题目解析:系统结构图中的最大扇入数为系统图中进入某一节点的最大节点数，本系统图中功能n.1节点输出节点为功能1到功能n,所以系统结构图的最大扇入数为n,故正确选项为A。 18.下列关于算法复杂度叙述正确的是（ ）。答案：B A）最坏情况下的时间复杂度一定高于平均情况的时间复杂度 B）时间复杂度与所用的计算工具无关 C）对同一个问题，采用不同的算法，则它们的时间复杂度是相同的 D）时间复杂度与采用的算法描述语言有关 题目解析:准确把握算法复杂度的概念。 19.设有栈S和队列Q，初始状态均为空。首先依次将A,B,C,D,E,F入栈，然后从栈中退出三个元素依次入队，再将X,Y,Z入栈后，将栈中所有元素退出并依次入队，最后将队列中所有元素退出，则退队元素的顺序为（ ）。答案：B A）DEFXYZABC B）FEDZYXCBA C）FEDXYZCBA D）DEFZYXABC 题目解析:栈是一种特殊的线性表栈中的数据时按照先进后出或者是后进先出的规则进行的，队列是同栈不太相同的线性结构，进出顺序为先进先出的规则，根据题意要求本题正确答案为B选项。 20.下列叙述中正确的是（ ）。答案：D A）有两个指针域的链表称为二叉链表 B）循环链表是循环队列的链式存储结构 C）带链的栈有栈顶指针和栈底指针，因此又称为双重链表 D）结点中具有多个指针域的链表称为多重链表 题目解析:结点中尽管有两个指针域但没有分别指向两个不同的结点就不是二叉链表，故A选项不正确；循环链表是在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点的线性结构，故B选项不正确；当结点中两个指针分别指向前驱结点和后继结点是为线性结构，当指向两个不同的前驱或后继结点时为非线性结构，故B选项正确。双重链表的结点有两个指针，一个指向前驱，一个指向后继，从一个结点既可以向前也可以向后才是双重链表，故C选项不正确。D选项正确。 21.某二叉树共有845个结点，其中叶子结点有45个，则度为1的结点数为（ ）。答案：C A）400 B）754 C）756 D）不确定 题目解析:二叉树中，度为0的结点（即叶子节点）比度为2的结点多1个，而度为0、1、2的结点相加等于总结点数845，所以度为1的结点数为845-45-（45-1）=756。 22.深度为7的二叉树共有127个结点，则下列说法中错误的是（ ）。答案：A A）该二叉树有一个度为1的结点 B）该二叉树是满二叉树

合集下载

算法与数据结构期中复习

算法与数据结构期中复习

答：如果i<j，则对于pi<pj情况，说明pi在pj入 栈前先出栈。而对于pi>pj的情况，则说明 要将pj压到pi之上，也就是在pj出栈之后pi才 能出栈。这就说明，对于i<j<k，不可能出 现pj<pk<pi的输出序列。
• 试证明:同一棵二叉树的所有叶子结点，在 先序序列、中序序列以及后序序列中都按 相同的相对位置出现（即先后顺序相同）， 例如先序abc,后序bca 中序bac。
试推导求解 n 阶hanoi塔问题至少要执行的移动操作 move 次数。
答：钢设针HXn移为到n个钢盘针子Z，的可Ha借n助oi塔钢的针移Y)动次数。(假定n个盘子从 则移到HZn，=2再H将n-1那+1n-/1/先个将移n到-1Z个盘子从X移到Y，第n个盘子 =2（2Hn-2+1）+1 =22 Hn-2+2+1 =22（2Hn-3+1）+2+1 =23 Hn-3+22+2+1 ·
请在下列算法的横线上填入适当的语句。
typedef struct node {int data; struct node *next; }linknode,*link;
bool inclusion(link ha,link hb) /*以ha和hb为头指针的带头节点单链表分别表示递增有序表A和B，本算法判别表A是否包
赋值语句A[i]执行了一次；最坏情况出现在二进制数各位均为1（最高位为零，因题目 假设无溢出），这时判断n次，循环体执行了n-1次，时间复杂度是O(n)， 平均情况：应该考虑从最低位其连续1的个数。
***0->2(n-1) 循环体判断条件执行1次 **01 -> 2(n-2)循环体判断条件执行2次 **011->2(n-3)循环体判断条件执行3次 **01..1(i个1)- 2(n-i-1)循环体判断条件执行i次 1..1(n个1)->1循环体判断条件执行n次 平均情况时间复杂度为0(n)
全国计算机等级考试《二级c语言程序设计》专用教材考纲分析考点精讲真题演练强化习题

全国计算机等级考试《二级c语言程序设计》专用教材考纲分析考点精讲真题演练强化习题

全国计算机等级考试《二级C＋＋语言程序设计》专用教材【考纲分析＋考点精讲＋真题演练＋强化习题】最新资料，WORD格式，可编辑修改！目录第一部分公共基础知识........................................................第1章数据结构与算法....................................................考纲分析..............................................................考点精讲..............................................................1.1 算法.......................................................1.2 数据结构的基本概念...........................................1.3 线性表及其顺序存储结构.......................................1.4 栈和队列.....................................................1.5 线性链表.....................................................1.6 树与二叉树...................................................1.7 查找技术.....................................................1.8 排序技术.....................................................强化习题..............................................................第2章程序设计基础......................................................考纲分析..............................................................考点精讲..............................................................2.1 程序设计方法与风格...........................................2.2 结构化程序设计...............................................2.3 面向对象的程序设计...........................................强化习题..............................................................第3章软件工程基础......................................................考纲分析..............................................................考点精讲..............................................................3.1 软件工程基本概念.............................................3.2 结构化分析方法...............................................3.3 结构化设计方法...............................................3.4 软件测试.....................................................3.5 程序的调试...................................................强化习题..............................................................第4章数据库设计基础....................................................考纲分析..............................................................考点精讲..............................................................4.1 数据库系统的基本概念.........................................4.2 数据模型.....................................................4.3 关系代数.....................................................4.4 数据库设计与管理.............................................强化习题.............................................................. 第二部分C++语言程序设计.....................................................第1章C++语言概述.......................................................考纲分析..............................................................考点精讲..............................................................1.1 C++语言的发展................................................1.2 C++语言的特点................................................1.3 面向对象程序设计.............................................1.4 C++语言的基本符号............................................1.5 C++语言的词汇................................................1.6 C++程序的基本框架............................................1.7 C++程序的开发过程............................................强化习题..............................................................第2章数据类型、运算符和表达式..........................................考纲分析..............................................................考点精讲..............................................................2.1 C++语言的数据类型............................................2.2 常量.......................................................2.3 变量.......................................................2.4 运算符和表达式...............................................强化习题..............................................................第3章基本控制结构......................................................考纲分析..............................................................考点精讲..............................................................3.1 C++语句......................................................3.2 顺序结构.....................................................3.3 选择结构.....................................................3.4 循环结构.....................................................3.5 跳转语句.....................................................强化习题..............................................................第4章数组、指针与引用..................................................考纲分析..............................................................考点精讲..............................................................4.1 数组.......................................................4.2 指针.......................................................4.3 引用.......................................................4.4 动态存储分配.................................................强化习题.............................................................. 第5章函数............................................................考纲分析..............................................................考点精讲..............................................................5.1 函数定义.....................................................5.2 函数调用.....................................................5.3 函数原型.....................................................5.4 函数返回类型.................................................5.5 函数参数.....................................................5.6 函数重载.....................................................5.7 内联函数.....................................................5.8 递归函数.....................................................5.9 变量的生存周期...............................................强化习题.............................................................. 第6章类和对象..........................................................考纲分析..............................................................考点精讲..............................................................6.1 类的定义.....................................................6.2 对象的定义...................................................6.3 构造函数和析构函数...........................................6.4 自由存储对象.................................................6.5 this指针.....................................................6.6 静态成员.....................................................6.7 常成员.......................................................6.8 友元.......................................................6.9 对象数组.....................................................6.10 成员对象....................................................强化习题.............................................................. 第7章继承和派生........................................................考纲分析..............................................................考点精讲..............................................................7.1 继承与派生...................................................7.2 派生类对基类成员的访问.......................................7.3 派生类的构造函数和析构函数...................................7.4 多继承与虚基类...............................................7.5 子类型关系...................................................7.6 虚函数与多态性...............................................强化习题.............................................................. 第8章运算符重载........................................................考纲分析..............................................................考点精讲..............................................................8.1 运算符函数与运算符重载.......................................8.2 典型运算符的重载.............................................8.3 运算符重载应注意的几个问题...................................强化习题.............................................................. 第9章模板............................................................考纲分析..............................................................考点精讲..............................................................9.1 函数模板.....................................................9.2 类模板.......................................................强化习题.............................................................. 第10章C++流............................................................考纲分析..............................................................考点精讲..............................................................10.1 C++流的概念.................................................10.2 输入输出的格式控制..........................................10.3 文件流......................................................强化习题..............................................................第一部分公共基础知识第1章数据结构与算法考纲分析1．算法的基本概念，算法复杂度的概念和意义（时间复杂度与空间复杂度）。

罗文劼《数据结构与算法》第4版-第1章 绪论

罗文劼《数据结构与算法》第4版-第1章 绪论


第1章 数据结构与算法
⒈教学内容：
(1)数据结构的概念 (2)抽象数据类型 (3)算法和算法分析 (4)递归
⒉ 教学目的：
(1)领会数据、数据元素和数据项的概念及其相互间关系 (2)清楚数据结构的逻辑结构、存储结构的联系与区别 (3)理解抽象数据类型的概念 (4)掌握进行简单算法分析的方法 (5)理解递归的特点，会分析什么样的问题适合用递归解决；领会递归调 用的执行过程； 了解递归的优缺点
下图为表示上述四类基本结构的示意图。
（a）集合结构
（b）线性结构
（c）树结构
（d）图结构 四类基本结构的示意图
1.2.2 抽象数据类型
1、数据类型
数据类型是一个值的集合和定义在这个值集上的一 组操作的总称。
2、抽象数据类型
抽象数据类型（Abstruct Data Type，简称ADT） 是指一个数学模型以及定义在该模型上的一组操作。
1.3 算法
1.3.1 算法及其特性
算法（Algorithm）是对特定问题求解步骤的一种描述， 是指令的有限序列。其中每一条指令表示一个或多个操作。
算法特性： ⑴ 有穷性。 ⑵ 确定性。 ⑶ 可行性。 ⑷ 输入。 ⑸ 输出。
算法要求： ⑴正确。 ⑵可读。 ⑶健壮。 ⑷高效。
2022年2月21日
1.3.2 算法描述
将一个算法转换成程序并在计算机上执行时，其运行所需 要的时间取决于下列因素：
⑴ 硬件的速度。 ⑵ 书写程序的语言。 ⑶ 编译程序所生成目标代码的质量。 ⑷ 问题的规模。
本课程的任务：
在基础方面，要求学生掌握常用数据结构的 基本概念及其不同的实现方法；在技能方面，通过 系统学习能够在不同存储结构上实现不同的运算， 并对算法设计的方式和技巧有所体会。
数据结构与算法试题库(附答案)

数据结构与算法试题库(附答案)

数据结构与算法试题库（附答案）一、单选题（共86题，每题1分，共86分）1.对于任意一棵高度为 5 且有 10 个结点的二叉树，若采用顺序存储结构保存，每个结点占 1 个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元的数量至少是：A、31B、10C、16D、15正确答案：A2.数组 A[0..6, 0..5] 的每个元素占 5 个字节，将其按列优先次序存储在起始地址为 1000 的内存单元中，则元素 A[5, 5] 的地址是( )。

A、1175B、1180C、1200D、1205正确答案：C3.一个有N个顶点的强连通图至少有多少条边？A、NB、N+1C、N(N−1)D、N−1正确答案：A4.用二分查找从100个有序整数中查找某数，最坏情况下需要比较的次数是：A、10B、7C、50D、99正确答案：B5.已知一个长度为16的顺序表L，其元素按关键字有序排列。

若采用二分查找法查找一个L中不存在的元素，则关键字的比较次数最多是：A、4B、7C、6D、5正确答案：D6.对空栈 S 进行 Push 和 Pop 操作，入栈序列为 a, b, c, d, e，经过 Push, Push, Pop, Push, Pop, Push, Push, Pop 操作后，得到的出栈序列是：A、b, c, eB、b, c, aC、b, a, cD、b, a, e正确答案：A7.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用哪种存储方式最节省时间？A、双链表B、单循环链表C、顺序表D、带头结点的双循环链表正确答案：C8.下列各种数据结构中属于线性结构的有()A、树B、图C、队列D、集合正确答案：C9.如果AVL树的深度为6（空树的深度定义为−1），则此树最少有多少个结点？A、12B、20C、33D、64正确答案：C10.对N个记录进行快速排序，在最坏的情况下，其时间复杂度是：A、O(N2)B、O(N)C、O(N2logN)D、O(NlogN)正确答案：A11.稀疏矩阵采用三元组存储的时候，一般需要一个行逻辑链接的顺序表，用以指出每一行的第一个非零元素在三元组中的位置。