2022年2022年计算机公共基础知识 2.pdf
《2022年2022年计算机公共基础知识 2.pdf》由会员分享,可在线阅读,更多相关《2022年2022年计算机公共基础知识 2.pdf(5页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第一章:数据结构和算法1、算法:(1)算法的复杂度包括时间复杂度 和空间复杂度 。(2)时间复杂度用算法的基本运算次数 来度量(3)空间复杂度指执行这个算法所需要的内存空间。习题 : (1) 算法的时间复杂度是指(D) A)算法的执行时间 B)算法所处理的数据量C)算法程序中的语句或指令条数D)算法在执行过程中所需要的基本运算次数(2) 算法的空间复杂度是指(A) 。A. 算法在执行过程中所需要的计算机存储空间 B.算法所处理的数据量C.算法程序中的语句或指令条数 D.算法在执行过程中所需要的临时工作单元数2、数据结构线性结构:只有一个根节点、最多一个前件,最多一个后件 (1) 下列数据结构中
2、,属于非线性结构的是( C) 。A.循环队列 B. 带链队列C.二叉树 D. 带链栈3、线性表4、栈和队列栈限定在一端进行插入和删除的线性表。特点是先进后出或后进先出。习题:(1)下列关于栈叙述正确的是(A)A)栈顶元素最先能被删除B)栈顶元素最后才能被删除C)栈底元素永远不能被删除D)以上三种说法都不对(2.) 下列数据结构中,能够按照 ” 先进后出 ” 原则存取数据的是() 。A. 循环队列B.栈C.队列 D.二叉树(3)一个栈的初始状态为空。首先将元素5,4,3,2,1依次入栈,然后退栈一次,再将元素A,B,C,D 依次入栈,之后将所有元素全部退栈,则所有元素退栈(包括中间退栈的元素)
3、的顺序为 (1DCBA2345) 队列是允许在一端进行插入而在另一端进行删除的线性表。特点是先进先出或后进后出。(1) 一个队列的初始状态为空。现将元素A,B,C,D,E,F,5,4,3,2,1依次入队, 然后再依次退队,则元素退队的顺序为 (ABCDEF54321) (2) 下列对队列的叙述正确的是。A)队列属于非线性表B)队列按先进后出的原则组织数据C)队列在队尾删除数据D)队列按先进先出原则组织数据队列的顺序存储结构一般是循环队列的形式(1)线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表,循环队列是队列的(顺序 )存储结构循环队列中元素个数计算公式。尾指针 头
4、指针时尾指针 -头指针例如:容量为15 的循环队列中,头指针为6,尾指针为9,循环队列中共有()个元素。答:9-6=3 尾指针 头指针时尾指针 -头指针 +容量. 例如:容量为15 的循环队列中,头指针为6,尾指针为3,循环队列中共有()个元素。答:3-6+15=12 (1)设某循环队列的容量为50,头指针为 5,尾指针为 29,则该循环队列中共有(24)个元素。(2) 设某循环队列的容量为50,如果头指针front=45(指向队头元素的前一位置) ,尾指针rear=10( 指向队尾元素 ) ,则该循环队列中共有(15)个元素。栈中元素个数的计算。栈顶-栈底 +1 例如:已知栈顶指针为8,栈底
5、指针为1,栈中共有8 个元素。(1)假设用一个长度为50 的数组(数组元素的下标从0 到 49 )作为栈的存储空间,栈底指针bottom 指向栈底元素,栈顶指针top 指向栈顶元素,如果bottom=49 ,top=30 (数组下标),则栈中具有(20)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 5 页 - - - - - - - - - 个元素。5、链表6、树与二叉树性质 1:第 k 层上最多2k-1个结点。性质 3:度为 0 的节点(叶子结点)总是比度为2 的节点
6、多一个。(1)深度为 5 的满二叉树有(16)个叶子结点。25-1=16 (2)在深度为7 的满二叉树中,度为2 的结点个数为(63) 个。 27-1=64 64-1=63 (3)某二叉树由5 个度为 2 的结点以及3 个度为 1 的结点,则该二叉树中共有(14 )个结点。n=n0+n1+n2 n2=5 n1=3 n0=n2+1=6 n=6+5+3=14 ( 4)一棵二叉树有10 个度为 1 的结点, 7 个度为 2 的结点,则该二义树共有(25) 个结点。n=n0+n1+n2 n2=7 n1=10 n0=n2+1=8 n=8+10+7=14 二叉树的遍历。前序(根左右)中序(左根右)后序(左
7、右根)遍历方法注意上课笔记。7、查找二分法查找只适用于顺序存储的有序表。最坏情况下二分查找只需要比较Log2n 次,顺序查找比较n 次(1)有序线性表能进行二分查找的前提是该线性表必须是【1】 存储的。(2)在长度为 n的有序线性表中进行二分查找,最坏情况下需要比较的次数是( C) A )O(n) B)O(n2) C)O(log2n) D)O(nlog2n) 8、排序1、冒泡排序法、简单插入排序法、简单选择排序法德比较次数为n(n-1)/2 。2、希尔排序的比较次数为n1.5 3、堆排序的比较次数为nLog2n (1)下列排序方法中,最坏情况下比较次数最少的是( D ) 。 A )冒泡排序 B
8、 )简单选择排序 C )直接插入排序 D )堆排序(2)冒泡排序在最坏情况下的比较次数是A)2/)1( nnB)nn2logC)2/)1(nnD)2/n第二章一、程序设计方法与风格。1、程序设计方法经过了结构化程序设计和面向对象的程序设计阶段。2、程序设计风格:清晰第一,效率第二3、符号名的命名要具有实际含义,注释分为序言性注释和功能性注释。二、结构化程序设计1、原则:自顶向下、逐步求精、模块化、限制使用goto 语句。2、三种基本结构:顺序结构、选择结构(分支结构)、重复结构(循环结构)三、面向对象的程序设计1、面向对象方法已经成为主流的软件开发方法。优点: (1)与人类习惯的思维方法一致(
9、2)稳定性好( 3)可重用性好(4)易于开发大型软件产品(5)可维护性好2、基本概念:对象:表示客观世界中的任何实体。对象的基本特点:标示唯一性、分类性、多态性、封装性、模块独立性好。类:具有共同属性,共同方法的对象的集合。实例:指一个具体的对象。消息:一个实例与另一个实例之间传递的信息。继承:能够直接获得已有的性质和特征,而不必重复定义它们。多态:同样的消息被不同的对象接受时可导致完全不同的行动。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 5 页 - - - - -
10、 - - - - 第三章一、软件工程的基本概念:1、软件包括 程序、数据和文档组成。2、软件分为 应用软件、系统软件、支持软件(工具软件)3、软件危机是 成本、质量、生产率的问题。4、软件工程三要素:方法、工具和过程。5、软件工程过程是把输入转化为输出的一组彼此相关的资源和活动。6、软件工程过程包括软件规格说明、软件开发、软件确认、软件演进。7、软件生命周期分为软件定义、软件开发、软件运行和维护三个大的阶段。软件定义分为:可行性研究和计划制定、需求分析。软件开发分为:概要设计、详细设计、实现、测试软件运行和维护分为:使用、维护、退役8、软件工程内容包括软件开发技术和软件工程管理。9、软件工程的
11、原则:抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性、可验证性。10、软件开发环境是全面支持软件开发全过程的软件工具集合。二、结构化分析方法:1、需求分析阶段的工作:需求获取、需求分析、编写需求规格说明书、需求评审。2、面向数据流的分析方法(SA) 、面向数据结构的Jackson方法 (JSD) 面向数据结构的结构化数据系统开发方法(DSSD) 面向对象的分析方法(OOA) 3、数据流图( DFD ) :椭圆代表加工(转换)、箭头代表数据流、双横线代表存储文件、矩形代表源、潭P67 面的图形。4、数据字典是结构化分析方法的核心。三、结构化设计方法:1、软件设计是把软件需求转换为软件表示
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年2022年计算机公共基础知识 2022 计算机 公共 基础知识
限制150内