软件设计师考试核心内容梳理及试题及答案

软件设计师考试核心内容梳理及试题及答案一、数据结构1.线性表顺序表：顺序表是用一组地址连续的存储单元依次存储线性表的数据元素。其优点是可以随机访问元素，时间复杂度为O(1)；缺点是插入和删除操作需要移动大量元素，时间复杂度为O(n)。例如，在长度为n的顺序表中第i个位置插入一个元素，需要将第i个及以后的元素依次后移一位。链表：链表是通过指针将一系列存储数据元素的结点连接起来的线性结构。分为单链表、双向链表和循环链表。单链表每个结点包含数据域和指向下一个结点的指针域；双向链表每个结点除了数据域还有指向前驱和后继的指针；循环链表的尾结点指针指向头结点。链表的插入和删除操作时间复杂度为O(1)（已知插入或删除位置的指针），但随机访问的时间复杂度为O(n)。2.栈和队列栈：栈是一种后进先出（LIFO）的线性表，只能在栈顶进行插入（入栈）和删除（出栈）操作。例如，函数调用时的栈帧管理就是利用栈的特性。表达式求值中，后缀表达式的计算也会用到栈。队列：队列是一种先进先出（FIFO）的线性表，有队头和队尾。元素从队尾入队，从队头出队。常见的应用有操作系统中的作业调度，网络中的数据包排队等。循环队列是为了克服普通队列可能出现的“假溢出”问题。3.树和二叉树树的基本概念：树是一种非线性的数据结构，由n（n≥0）个结点组成的有限集合。有根树有一个特殊的结点称为根结点，其余结点可以分为m（m≥0）个互不相交的子树。树的度是指树中结点的最大度数，结点的层次从根结点开始定义，根结点为第一层。二叉树：二叉树是每个结点最多有两个子树的树结构，分别称为左子树和右子树。满二叉树是除最后一层无任何子结点外，每一层上的所有结点都有两个子结点的二叉树；完全二叉树是除了最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。二叉树的遍历方式有前序遍历（根左右）、中序遍历（左根右）和后序遍历（左右根）。二叉排序树：又称二叉查找树，它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。4.图图的基本概念：图由顶点集V和边集E组成，记为G=(V,E)。有向图的边是有方向的，无向图的边没有方向。图的度是指与该顶点相关联的边的数目，对于有向图还有入度和出度之分。图的存储结构：主要有邻接矩阵和邻接表。邻接矩阵是用一个二维数组来表示图中顶点之间的邻接关系，对于有n个顶点的图，邻接矩阵是一个n×n的矩阵；邻接表是一种链式存储结构，对于图中的每个顶点，用一个单链表来存储与该顶点相邻接的所有顶点。图的遍历：深度优先搜索（DFS）和广度优先搜索（BFS）是图的两种基本遍历方法。深度优先搜索是沿着一条路径尽可能深地访问顶点，直到无法继续，然后回溯；广度优先搜索是逐层地访问图中的顶点，先访问距离起始顶点最近的顶点。数据结构试题及答案1.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表答案：A。顺序表可以随机访问元素，存取指定序号元素的时间复杂度为O(1)，在最后进行插入和删除操作，不需要移动大量元素，时间复杂度也为O(1)，所以顺序表最节省时间。2.设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（）。A.6B.4C.3D.2答案：C。根据出队顺序反推栈的操作过程：e1、e2入栈，e2出栈；e3、e4入栈，e4出栈，e3出栈；e5、e6入栈，e6出栈，e5出栈，e1出栈。在这个过程中，栈中最多同时存在3个元素，所以栈的容量至少为3。3.若一棵二叉树的前序遍历序列为ABDECFG，中序遍历序列为DBEACGF，则后序遍历序列为（）。A.DEBGFCAB.BDEGACFC.EDBFCGAD.DBECFGA答案：A。根据前序遍历的第一个元素是根结点，可知A是根结点。在中序遍历中，根结点将序列分为左子树和右子树，所以DBE是左子树的中序遍历序列，CFG是右子树的中序遍历序列。再根据前序遍历确定左子树和右子树的根结点，逐步构建二叉树，最后得到后序遍历序列为DEBGFCA。二、程序设计语言基础1.程序设计语言的分类机器语言：机器语言是计算机能够直接识别和执行的二进制代码，由操作码和操作数组成。它的执行效率高，但编写和维护难度大。汇编语言：汇编语言用助记符来表示机器指令，需要通过汇编程序将汇编语言程序翻译成机器语言程序。汇编语言比机器语言更易理解和编写，但仍然依赖于具体的计算机硬件。高级语言：高级语言是面向用户的程序设计语言，具有较高的抽象层次，如C、C++、Java、Python等。高级语言需要通过编译程序或解释程序将其翻译成机器语言才能执行。2.编译程序的基本原理词法分析：词法分析器按从左到右的顺序对源程序的字符流进行扫描，依据词法规则将其识别为一个个单词。例如，对于源程序“inta=10;”，词法分析器会识别出“int”、“a”、“=”、“10”、“;”等单词。语法分析：语法分析器根据语法规则分析单词序列，判断源程序的语法结构是否正确，构建语法树。例如，检查“inta=10;”是否符合C语言的语法规则。语义分析：语义分析器对语法树进行语义检查，如类型检查、变量定义检查等。例如，检查“inta=10.5;”中赋值语句的类型是否匹配。代码提供：将语义分析后的中间代码提供目标机器的机器语言代码。3.面向对象程序设计对象和类：对象是类的实例，类是具有相同属性和方法的对象的抽象描述。例如，“汽车”可以是一个类，而某一辆具体的汽车就是“汽车”类的一个对象。封装：封装是将数据和操作数据的方法绑定在一起，隐藏对象的内部实现细节，只对外提供必要的接口。例如，一个类中的私有成员变量只能通过类的公有方法来访问。继承：继承是指一个类可以继承另一个类的属性和方法，从而实现代码的复用。被继承的类称为父类或基类，继承的类称为子类或派生类。例如，“轿车”类可以继承“汽车”类的属性和方法。多态：多态是指同一个操作作用于不同的对象可以有不同的表现形式。例如，不同的“图形”类（如圆形、矩形）都有“计算面积”的方法，但实现方式不同。程序设计语言基础试题及答案1.编译程序对高级语言源程序进行编译的过程中，要不断收集、记录和使用源程序中一些相关符号的类型和特征等信息，并将其存入（）中。A.符号表B.哈希表C.动态查找表D.栈和队列答案：A。符号表用于收集、记录和使用源程序中符号的类型和特征等信息，编译程序在编译过程中会不断对符号表进行操作。2.以下关于面向对象程序设计中继承的叙述中，错误的是（）。A.继承是父类和子类之间共享数据和方法的机制B.继承定义了一种类与类之间的关系C.继承关系中的子类将拥有父类的全部属性和方法D.继承可以实现代码复用答案：C。子类可以继承父类的部分或全部属性和方法，同时可以对父类的方法进行重写或扩展，并不是拥有父类的全部属性和方法，比如父类的私有成员子类不能直接访问。3.以下关于多态的叙述中，不正确的是（）。A.多态是指同一个消息可以调用不同的方法B.多态存在的必要条件是要有继承、重写和父类引用指向子类对象C.编译时的多态通过方法重载实现D.运行时的多态通过模板实现答案：D。运行时的多态通过继承、重写和父类引用指向子类对象来实现，模板是C++中实现泛型编程的一种机制，与运行时多态无关。编译时的多态通过方法重载实现。三、操作系统1.操作系统的基本概念操作系统的功能：操作系统是管理计算机硬件与软件资源的计算机程序，具有处理机管理（进程管理）、存储器管理、设备管理、文件管理和用户接口等功能。操作系统的分类：常见的操作系统分类有批处理操作系统、分时操作系统、实时操作系统、网络操作系统和分布式操作系统等。2.进程管理进程的概念：进程是程序在操作系统中的一次执行过程，是系统进行资源分配和调度的基本单位。进程具有动态性、并发性、独立性和异步性等特征。进程的状态：进程有三种基本状态，即就绪状态、运行状态和阻塞状态。就绪状态的进程等待CPU资源，运行状态的进程正在占用CPU执行，阻塞状态的进程因等待某一事件（如I/O操作完成）而暂停执行。进程调度：进程调度的主要任务是按照一定的算法从就绪队列中选择一个进程，将CPU分配给它。常见的调度算法有先来先服务（FCFS）、短作业优先（SJF）、时间片轮转（RR）、优先级调度等。进程同步与互斥：进程同步是指多个进程在执行次序上的协调，以保证并发进程能有效共享资源和相互合作。进程互斥是指多个进程对临界资源的互斥访问，临界资源是一次仅允许一个进程使用的共享资源。信号量机制是实现进程同步与互斥的一种有效方法。3.存储器管理内存分配方式：有静态分配和动态分配。静态分配是在程序装入内存时就确定其所需的内存空间，并一次性分配；动态分配是在程序运行过程中根据需要动态地分配内存。虚拟存储技术：虚拟存储技术是将程序的一部分装入内存，其余部分放在外存，在程序执行过程中，当需要访问的信息不在内存时，由操作系统将其从外存调入内存。常见的虚拟存储管理方式有请求分页存储管理、请求分段存储管理和段页式存储管理。4.文件管理文件系统的概念：文件系统是操作系统中负责管理和存储文件信息的软件机构，它负责文件的存储、检索、共享和保护等操作。文件的物理结构：有顺序结构、链接结构和索引结构。顺序结构的文件在物理上是连续存放的；链接结构的文件通过指针将各个离散的物理块链接起来；索引结构的文件通过索引表来记录文件的物理块位置。操作系统试题及答案1.若系统中有n个进程，则就绪队列中进程的个数最多为（）。A.nB.n1C.n2D.1答案：B。系统中最多只有一个进程处于运行状态，所以就绪队列中进程的个数最多为n1。2.在虚拟分页存储管理系统中，若进程访问的页面不在主存，且主存中没有可用的空闲块时，系统正确的处理顺序为（）。A.决定淘汰页→页面调出→缺页中断→页面调入B.缺页中断→决定淘汰页→页面调出→页面调入C.缺页中断→页面调入→决定淘汰页→页面调出D.决定淘汰页→页面调入→缺页中断→页面调出答案：B。当进程访问的页面不在主存时，会产生缺页中断，然后操作系统决定淘汰哪个页面，将该页面调出主存，最后将所需页面调入主存。3.某文件系统采用多级索引结构，若磁盘块的大小为512字节，每个块号需占3字节，那么采用二级索引时的文件最大长度为（）字节。A.512×(512/3)×(512/3)B.512×512×(512/3)C.512×(512/3)D.512×(512/3)+512答案：A。一个磁盘块能存放的块号数量为512/3个。一级索引能指向的磁盘块数量为512/3个，二级索引是通过一级索引再指向磁盘块，所以二级索引时文件最大长度为512×(512/3)×(512/3)字节。四、数据库系统1.数据库系统的基本概念数据库、数据库管理系统和数据库系统：数据库是长期存储在计算机内的、有组织的、可共享的数据集合；数据库管理系统是位于用户与操作系统之间的一层数据管理软件，用于科学地组织和存储数据、高效地获取和维护数据；数据库系统是由数据库、数据库管理系统、应用程序、数据库管理员和用户等组成的计算机系统。数据模型：数据模型是对现实世界数据特征的抽象，常见的数据模型有层次模型、网状模型、关系模型和面向对象模型。关系模型是目前应用最广泛的数据模型，它用二维表来表示数据。2.关系数据库关系的基本概念：关系是一个二维表，表中的每一行称为一个元组，每一列称为一个属性。关系的键有候选键、主键和外键。候选键是能够唯一标识一个元组的属性或属性组；主键是从候选键中选定的一个；外键是一个关系中的属性或属性组，它引用另一个关系的主键。关系代数：关系代数是一种抽象的查询语言，它用对关系的运算来表达查询。关系代数的运算分为传统的集合运算（并、差、交、笛卡尔积）和专门的关系运算（选择、投影、连接、除）。SQL语言：SQL（结构化查询语言）是一种用于管理关系数据库的标准语言，包括数据定义语言（DDL）、数据操纵语言（DML）和数据控制语言（DCL）。DDL用于定义数据库对象，如创建、修改和删除表；DML用于对数据进行插入、删除和修改操作；DCL用于控制用户对数据库对象的访问权限。3.数据库设计数据库设计的步骤：数据库设计包括需求分析、概念结构设计、逻辑结构设计、物理结构设计、数据库实施和数据库运行与维护等阶段。概念结构设计通常采用ER（实体联系）模型来描述数据的概念结构；逻辑结构设计是将ER模型转换为关系模型。数据库系统试题及答案1.设关系R和S的元数分别为2和3，那么R×S（笛卡尔积）的元数为（）。A.2B.3C.5D.6答案：C。笛卡尔积的元数是参与运算的两个关系的元数之和，所以R×S的元数为2+3=5。2.若关系R(A,B,C)和S(B,C,D)，则R与S自然连接运算后的属性列数和元组数分别为（）。A.4和3B.4和6C.6和3D.6和6答案：A。自然连接是在笛卡尔积的基础上，选取公共属性值相等的元组，并去掉重复的属性列。R和S的公共属性是B和C，自然连接后的属性列为A、B、C、D，共4列。假设R有m个元组，S有n个元组，经过自然连接后元组数一般小于m×n，这里根据选项推测元组数为3。3.在数据库设计中，将ER图转换为关系模式的过程属于（）。A.需求分析阶段B.概念结构设计阶段C.逻辑结构设计阶段D.物理结构设计阶段答案：C。将ER图转换为关系模式是将概念模型转换为逻辑模型，属于逻辑结构设计阶段。五、计算机网络1.计算机网络的基本概念计算机网络的分类：按覆盖范围可分为广域网（WAN）、城域网（MAN）和局域网（LAN）；按拓扑结构可分为总线型、星型、环型、树型和网状型等。网络协议和体系结构：网络协议是为计算机网络中进行数据交换而建立的规则、标准或约定，常见的网络协议有TCP/IP协议。计算机网络的体系结构是指计算机网络层次结构模型和各层协议的集合，如OSI参考模型和TCP/IP参考模型。2.TCP/IP协议TCP/IP协议的层次结构：TCP/IP协议分为四层，分别是网络接口层、网络层、传输层和应用层。网络接口层负责将IP数据报封装成适合在物理网络上传输的帧；网络层主要负责将数据报从源主机传输到目标主机，主要协议有IP、ICMP等；传输层提供端到端的通信服务，主要协议有TCP和UDP；应用层为用户提供应用程序接口，常见的应用层协议有HTTP、FTP、SMTP等。TCP和UDP的区别：TCP是面向连接的、可靠的传输协议，它在传输数据前需要建立连接，传输过程中提供可靠的数据传输，有流量控制和拥塞控制机制；UDP是无连接的、不可靠的传输协议，它不需要建立连接，传输效率高，但不保证数据的可靠传输。3.网络安全网络安全的基本概念：网络安全是指网络系统中的硬件、软件及其数据受到保护，不受未经授权的访问、破坏、更改或泄露。网络安全的主要目标包括保密性、完整性、可用性、可控性和不可否认性。网络安全技术：常见的网络安全技术有防火墙、入侵检测系统（IDS）、加密技术和身份认证技术等。防火墙是一种网络安全设备，用于控制网络之间的访问；入侵检测系统用于检测网络中的异常活动；加密技术用于对数据进行加密，防止数据在传输过程中被窃取；身份认证技术用于验证用户的身份。计算机网络试题及答案1.在TCP/IP协议体系结构中，（）协议实现IP地址到MAC地址的转换。A.ARPB.RARPC.ICMPD.TCP答案：A。ARP（地址解析协议）用于将IP地址转换为MAC地址；RARP（反向地址解析协议）用于将MAC地址转换为IP地址；ICMP（网际控制报文协议）用于在IP主机、路由器之间传递控制消息；TCP是传输层的可靠传输协议。2.以下关于TCP和UDP的描述中，正确的是（）。A.TCP和UDP都提供面向连接的服务B.TCP和UDP都提供无连接的服务C.TCP提供面向连接的服务，UDP提供无连接的服务D.TCP提供无连接的服务，UDP提供面向连接的服务答案：C。TCP是面向连接的、可靠的传输协议，UDP是无连接的、不可靠的传输协议。3.以下不属于网络安全技术的是（）。A.防火墙B.入侵检测系统C.数据库备份D.加密技术答案：C。数据库备份是一种数据保护措施，主要是为了防止数据丢失，不属于网络安全技术。防火墙、入侵检测系统和加密技术都是常见的网络安全技术。六、软件设计与开发1.软件生命周期软件生命周期的阶段：软件生命周期包括可行性研究与计划、需求分析、设计、编码、测试、维护等阶段。可行性研究与计划阶段主要确定软件项目的可行性；需求分析阶段明确软件系统的功能和性能要求；设计阶段将需求转化为软件的体系结构和详细设计；编码阶段根据设计文档编写程序代码；测试阶段发现软件中的错误；维护阶段对软件进行修改和完善。软件开发模型：常见的软件开发模型有瀑布模型、快速原型模型、增量模型、螺旋模型和敏捷开发模型等。瀑布模型是一种线性顺序模型，各个阶段依次进行，如同瀑布流水；快速原型模型先快速构建一个可运行的软件原型，然后根据用户反馈进行修改和完善；螺旋模型将软件开发过程视为一个螺旋式的迭代过程，每一次迭代都包含制定计划、风险分析、实施工程和客户评估四个阶段。2.软件设计软件设计的原则：软件设计应遵循高内聚、低耦合的原则。内聚是指模块内部各元素之间的联系紧密程度，高内聚表示模块内部的功能联系紧密；耦合是指模块之间的相互依赖程度，低耦合表示模块之间的联系松散。软件体系结构设计：软件体系结构是指软件系统的整体结构和组织方式，常见的软件体系结构风格有分层结构、客户服务器结构、管道过滤器结构等。分层结构将软件系统分为多个层次，每层有不同的功能；客户服务器结构由客户端和服务器端组成，客户端向服务器端请求服务，服务器端提供服务。3.软件测试软件测试的方法：软件测试方法分为静态