计算机系统基础主要涵盖计算机组成原理与体系结构两个层面。计算机组成原理研究计算机硬件各部件的内部结构和工作原理包括运算器、控制器、存储器、输入设备和输出设备五大基本部件。其中运算器负责算术运算和逻辑运算控制器负责指令的取指、译码和执行存储器用于存放程序和数据。计算机体系结构则从程序员的角度研究计算机系统的属性重点关注指令集架构ISA、数据表示、寻址方式、寄存器组织等。经典的冯·诺依曼体系结构确立了存储程序的核心思想即程序和数据以同等地位存储在存储器中计算机按顺序逐条执行指令。现代计算机在此基础上发展出哈佛结构指令和数据分开存储、流水线技术、多级缓存体系等优化手段。指令流水线是提高CPU性能的关键技术通过将指令执行过程划分为取指、译码、执行、访存、写回等多个阶段使多条指令可以重叠执行。流水线冒险结构冒险、数据冒险、控制冒险是流水线设计中需要解决的核心问题常用的解决方法包括前推技术、分支预测、乱序执行等。二、数据结构与算法数据结构是计算机存储、组织数据的方式常见的数据结构包括线性结构数组、链表、栈、队列、树形结构二叉树、二叉搜索树、AVL树、红黑树、B树/B树、图结构邻接矩阵、邻接表以及散列表等。算法是解决问题的步骤描述评价算法优劣的核心指标是时间复杂度和空间复杂度。常见的时间复杂度从低到高依次为O(1) O(log n) O(n) O(n log n) O(n²) O(2ⁿ)。经典算法策略包括分治法将问题分解为若干子问题递归求解后合并结果如归并排序、快速排序。动态规划将问题分解为重叠子问题通过状态转移方程自底向上求解如背包问题、最长公共子序列。贪心算法每一步选择当前最优解如Dijkstra最短路径算法、Huffman编码。回溯法通过深度优先搜索遍历解空间树在搜索过程中剪枝如八皇后问题、图的着色问题。三、操作系统操作系统是管理计算机硬件与软件资源的系统软件主要功能包括进程管理、内存管理、文件管理和设备管理。进程管理涉及进程的创建、调度、同步和通信。进程有三种基本状态就绪、运行、阻塞。进程调度算法包括先来先服务FCFS、短作业优先SJF、时间片轮转RR、多级反馈队列等。进程同步问题中经典的生产者-消费者问题和哲学家就餐问题需要通过信号量机制解决。死锁产生的四个必要条件是互斥、占有并等待、不可剥夺、循环等待预防死锁可通过破坏其中一个条件实现。内存管理采用分页、分段、段页式等存储管理方式。虚拟内存技术通过请求分页和页面置换算法OPT、FIFO、LRU、Clock实现逻辑地址到物理地址的映射提高了内存利用率。四、数据库系统数据库系统由数据库、数据库管理系统DBMS、应用系统和数据库管理员组成。数据模型包括层次模型、网状模型和关系模型其中关系模型是目前最常用的模型。关系数据库的基本概念包括关系表、元组行、属性列、主键、外键等。关系代数运算包括选择、投影、连接、除、并、交、差等。数据库设计的步骤包括需求分析、概念结构设计E-R图、逻辑结构设计关系模式转换、物理结构设计。E-R图中的实体用矩形表示属性用椭圆表示联系用菱形表示联系类型包括一对一1:1、一对多1:N、多对多M:N。SQL语言分为数据定义语言DDLCREATE、ALTER、DROP、数据操纵语言DMLINSERT、UPDATE、DELETE、数据查询语言DQLSELECT和数据控制语言DCLGRANT、REVOKE。事务是数据库操作的逻辑单位具有ACID四大特性原子性Atomicity、一致性Consistency、隔离性Isolation、持久性Durability。并发控制主要通过锁机制共享锁、排他锁和两段锁协议实现可能产生的问题包括丢失修改、不可重复读、读脏数据等。五、计算机网络计算机网络按照覆盖范围可分为局域网LAN、城域网MAN和广域网WAN。OSI参考模型分为七层物理层、数据链路层、网络层、传输层、会话层、表示层、应用层。TCP/IP模型则分为四层网络接口层、网际层、传输层、应用层。物理层负责比特流的传输涉及传输介质、编码方式等。数据链路层负责帧的传输提供差错控制和流量控制CSMA/CD是以太网采用的介质访问控制协议。网络层负责路由选择和分组转发IP协议是核心协议IPv4地址分为A、B、C、D、E五类子网掩码用于划分子网。常见路由协议包括RIP基于距离向量和OSPF基于链路状态。传输层提供端到端的通信TCP是面向连接的可靠传输协议通过三次握手建立连接、四次挥手释放连接采用滑动窗口机制实现流量控制UDP是无连接的不可靠传输协议适用于实时性要求高的应用。应用层协议包括HTTP、FTP、SMTP、DNS等。六、软件工程软件工程是应用工程化的方法开发和维护软件的学科。软件生命周期包括可行性研究、需求分析、概要设计、详细设计、编码、测试、运行维护等阶段。需求分析的目标是明确系统必须做什么常用方法包括结构化分析SA和面向对象分析OOA。结构化分析的核心工具是数据流图DFD和数据字典DD。DFD由数据流、加工处理、数据存储、外部实体四个基本元素组成采用自顶向下、逐层分解的方法绘制。软件测试分为单元测试、集成测试、确认测试和系统测试。白盒测试基于程序内部逻辑设计测试用例常用方法包括语句覆盖、判定覆盖、条件覆盖、路径覆盖等黑盒测试基于功能需求设计测试用例常用方法包括等价类划分、边界值分析、错误推测法、因果图法等。软件维护分为改正性维护、适应性维护、完善性维护和预防性维护其中完善性维护所占比例最大。七、面向对象技术与UML面向对象OO技术以对象为核心具有封装、继承、多态三大基本特征。封装将数据和操作数据的方法绑定在一起隐藏内部实现细节继承允许子类复用父类的属性和方法多态使同一操作作用于不同对象时产生不同的行为。UML统一建模语言是面向对象系统的可视化建模语言包含多种图形用例图描述系统功能与参与者之间的关系包括参与者、用例、关联、包含、扩展、泛化等关系。类图描述系统的静态结构包括类名、属性、方法以及类之间的关联、聚合、组合、依赖、泛化继承、实现等关系。序列图时序图描述对象之间的动态交互按时间顺序展示消息传递过程。状态图描述对象在其生命周期中的状态变化。活动图描述业务流程或算法的工作流程。八、信息安全信息安全的基本属性包括机密性、完整性、可用性、可控性和不可否认性。常见的安全威胁包括窃听、篡改、伪装、重放、拒绝服务攻击等。加密技术分为对称加密DES、AES和非对称加密RSA、ECC。对称加密加解密使用同一密钥速度快但密钥分发困难非对称加密使用公钥和私钥配对解决了密钥分发问题但速度较慢。实际应用中常将两者结合如SSL/TLS协议。数字签名利用非对称加密技术实现身份认证和不可否认性发送方用私钥签名接收方用公钥验证。数字证书由认证中心CA签发用于绑定公钥和持有者身份。防火墙是网络安全的屏障分为包过滤防火墙、应用级网关和状态检测防火墙。入侵检测系统IDS用于监测网络或系统中的异常行为。九、标准化与知识产权信息技术标准是规范信息技术产品、系统和服务的技术规范。我国标准分为国家标准GB、行业标准、地方标准和企业标准。国际标准主要包括ISO国际标准化组织、IEC国际电工委员会、ITU国际电信联盟制定的标准。软件著作权保护软件的源代码和目标代码保护期为作者终生及其死亡后50年。专利权保护发明创造发明专利保护期为20年实用新型和外观设计专利保护期为10年。商标权保护商业标识注册有效期为10年可续展。十、计算机专业英语计算机专业英语是阅读技术文档、国际标准和前沿论文的基础。常见术语包括algorithm算法、compiler编译器、database数据库、encryption加密、interface接口、protocol协议、thread线程、virtual memory虚拟内存等。十一、应用技术当前主流应用技术包括云计算、大数据、人工智能、物联网、区块链等。云计算提供IaaS、PaaS、SaaS三种服务模式大数据技术涉及Hadoop、Spark等分布式计算框架人工智能涵盖机器学习、深度学习、自然语言处理等领域物联网通过RFID、传感器等技术实现物物相连区块链是一种去中心化的分布式账本技术。十二、数据流图DFD设计与分析数据流图是结构化分析的核心工具用于描述系统的数据流动和处理过程。DFD包含四种基本符号外部实体External Entity系统之外的数据源或数据终点用矩形表示。加工Process对数据进行变换或处理的单元用圆角矩形或圆形表示。数据流Data Flow数据的流动方向用带箭头的线段表示。数据存储Data Store数据的静态存储用双横线或开口矩形表示。DFD设计遵循自顶向下、逐层分解的原则。顶层DFD将整个系统视为一个加工展示系统与外部实体的交互0层DFD将系统分解为若干主要加工下层DFD对上层加工进一步细化。DFD设计需注意父图与子图的平衡输入输出数据流一致、加工的命名规范动词宾语、避免黑洞只有输入无输出和奇迹只有输出无输入等错误。十三、数据库设计数据库设计是构建高效、可靠数据库系统的关键过程主要包括以下步骤1. 需求分析收集和分析用户对数据的需求形成数据字典和需求说明书。2. 概念结构设计使用E-R图描述实体、属性和联系。设计原则包括真实性、简洁性、易理解性。局部E-R图设计完成后需进行视图集成消除冲突属性冲突、命名冲突、结构冲突形成全局E-R图。3. 逻辑结构设计将E-R图转换为关系模式。转换规则为每个实体转换为一个关系模式每个多对多联系转换为一个独立的关系模式一对多联系可与任一实体合并一对一联系可与任意实体合并。然后进行规范化处理消除数据冗余和操作异常。范式包括第一范式1NF属性不可再分、第二范式2NF消除非主属性对码的部分依赖、第三范式3NF消除非主属性对码的传递依赖、BCNF消除主属性对码的部分和传递依赖。4. 物理结构设计确定存储结构、存取方法、索引策略等。5. SQL实现使用SQL语言创建表、视图、索引编写查询语句。例如CREATETABLEStudent(SnoCHAR(10)PRIMARYKEY,SnameVARCHAR(20)NOTNULL,SageINT,SdeptVARCHAR(20));SELECTSname,SageFROMStudentWHERESdeptCSANDSage20ORDERBYSageDESC;十四、UML建模用例图描述系统功能。例如图书馆管理系统中参与者读者的用例包括查询图书“借阅图书”“归还图书”参与者管理员的用例包括添加图书“删除图书”“管理读者”。类图描述系统静态结构。例如------------------ ------------------ | Reader | | Book | ------------------ ------------------ | - readerId: int | | - isbn: String | | - name: String | | - title: String | | - phone: String | | - author: String | ------------------ | - available: bool| | borrow() | ------------------ | returnBook() | | checkStatus() | ------------------ ------------------ | | | ------------------ ------| BorrowRecord | ------------------ | - recordId: int | | - borrowDate | | - returnDate | ------------------ | createRecord() | | updateRecord() | ------------------序列图描述对象间交互。以借阅图书为例读者对象向系统界面发送借阅请求界面调用控制器的borrowBook方法控制器查询Book对象检查可借状态创建BorrowRecord对象记录借阅信息最后返回结果给读者。十五、C语言算法实现以下分别用C语言实现分治、动态规划和回溯三种经典算法策略1. 分治法——归并排序#includestdio.h#includestdlib.h// 合并两个有序子数组voidmerge(intarr[],intleft,intmid,intright){intn1mid-left1;intn2right-mid;int*L(int*)malloc(n1*sizeof(int));int*R(int*)malloc(n2*sizeof(int));for(inti0;in1;i)L[i]arr[lefti];for(intj0;jn2;j)R[j]arr[mid1j];inti0,j0,kleft;while(in1jn2){if(L[i]R[j])arr[k]L[i];elsearr[k]R[j];}while(in1)arr[k]L[i];while(jn2)arr[k]R[j];free(L);free(R);}voidmergeSort(intarr[],intleft,intright){if(leftright){intmidleft(right-left)/2;mergeSort(arr,left,mid);// 分解左半部分mergeSort(arr,mid1,right);// 分解右半部分merge(arr,left,mid,right);// 合并}}2. 动态规划——0/1背包问题#includestdio.hintmax(inta,intb){returnab?a:b;}intknapsack(intW,intwt[],intval[],intn){intdp[n1][W1];for(inti0;in;i){for(intw0;wW;w){if(i0||w0)dp[i][w]0;elseif(wt[i-1]w)dp[i][w]max(val[i-1]dp[i-1][w-wt[i-1]],dp[i-1][w]);elsedp[i][w]dp[i-1][w];}}returndp[n][W];}3. 回溯法——八皇后问题#includestdio.h#includestdbool.h#defineN8intboard[N][N];intsolutionCount0;boolisSafe(introw,intcol){// 检查当前列上方for(inti0;irow;i)if(board[i][col])returnfalse;// 检查左上对角线for(intirow,jcol;i0j0;i--,j--)if(board[i][j])returnfalse;// 检查右上对角线for(intirow,jcol;i0jN;i--,j)if(board[i][j])returnfalse;returntrue;}voidsolveNQueens(introw){if(rowN){solutionCount;return;}for(intcol0;colN;col){if(isSafe(row,col)){board[row][col]1;// 放置皇后solveNQueens(row1);// 递归下一行board[row][col]0;// 回溯}}}十六、选答题Java面向对象程序设计Java是纯粹的面向对象语言以下展示面向对象语法与设计模式的应用1. 封装、继承与多态// 抽象基类abstractclassShape{protectedStringcolor;publicShape(Stringcolor){this.colorcolor;}publicabstractdoublearea();publicvoiddisplay(){System.out.println(Color: color, Area: area());}}// 子类继承classCircleextendsShape{privatedoubleradius;publicCircle(Stringcolor,doubleradius){super(color);this.radiusradius;}Overridepublicdoublearea(){returnMath.PI*radius*radius;}}classRectangleextendsShape{privatedoublewidth,height;publicRectangle(Stringcolor,doublewidth,doubleheight){super(color);this.widthwidth;this.heightheight;}Overridepublicdoublearea(){returnwidth*height;}}// 多态演示publicclassPolymorphismDemo{publicstaticvoidmain(String[]args){Shape[]shapes{newCircle(Red,5),newRectangle(Blue,4,6)};for(Shapes:shapes){s.display();// 运行时多态}}}2. 设计模式——单例模式与工厂模式// 单例模式饿汉式classDatabaseConnection{privatestaticfinalDatabaseConnectioninstancenewDatabaseConnection();privateDatabaseConnection(){}publicstaticDatabaseConnectiongetInstance(){returninstance;}publicvoidconnect(){System.out.println(Database connected.);}}// 工厂模式interfaceAnimal{voidspeak();}classDogimplementsAnimal{publicvoidspeak(){System.out.println(Woof!);}}classCatimplementsAnimal{publicvoidspeak(){System.out.println(Meow!);}}classAnimalFactory{publicstaticAnimalcreateAnimal(Stringtype){if(dog.equalsIgnoreCase(type))returnnewDog();if(cat.equalsIgnoreCase(type))returnnewCat();thrownewIllegalArgumentException(Unknown animal type);}} 指令流水线是提高CPU性能的关键技术，通过将指令执行过程划分为取指、译码、执行、访存、写回等多个阶段
计算机系统基础主要涵盖计算机组成原理与体系结构两个层面。计算机组成原理研究计算机硬件各部件的内部结构和工作原理包括运算器、控制器、存储器、输入设备和输出设备五大基本部件。其中运算器负责算术运算和逻辑运算控制器负责指令的取指、译码和执行存储器用于存放程序和数据。计算机体系结构则从程序员的角度研究计算机系统的属性重点关注指令集架构ISA、数据表示、寻址方式、寄存器组织等。经典的冯·诺依曼体系结构确立了存储程序的核心思想即程序和数据以同等地位存储在存储器中计算机按顺序逐条执行指令。现代计算机在此基础上发展出哈佛结构指令和数据分开存储、流水线技术、多级缓存体系等优化手段。指令流水线是提高CPU性能的关键技术通过将指令执行过程划分为取指、译码、执行、访存、写回等多个阶段使多条指令可以重叠执行。流水线冒险结构冒险、数据冒险、控制冒险是流水线设计中需要解决的核心问题常用的解决方法包括前推技术、分支预测、乱序执行等。二、数据结构与算法数据结构是计算机存储、组织数据的方式常见的数据结构包括线性结构数组、链表、栈、队列、树形结构二叉树、二叉搜索树、AVL树、红黑树、B树/B树、图结构邻接矩阵、邻接表以及散列表等。算法是解决问题的步骤描述评价算法优劣的核心指标是时间复杂度和空间复杂度。常见的时间复杂度从低到高依次为O(1) O(log n) O(n) O(n log n) O(n²) O(2ⁿ)。经典算法策略包括分治法将问题分解为若干子问题递归求解后合并结果如归并排序、快速排序。动态规划将问题分解为重叠子问题通过状态转移方程自底向上求解如背包问题、最长公共子序列。贪心算法每一步选择当前最优解如Dijkstra最短路径算法、Huffman编码。回溯法通过深度优先搜索遍历解空间树在搜索过程中剪枝如八皇后问题、图的着色问题。三、操作系统操作系统是管理计算机硬件与软件资源的系统软件主要功能包括进程管理、内存管理、文件管理和设备管理。进程管理涉及进程的创建、调度、同步和通信。进程有三种基本状态就绪、运行、阻塞。进程调度算法包括先来先服务FCFS、短作业优先SJF、时间片轮转RR、多级反馈队列等。进程同步问题中经典的生产者-消费者问题和哲学家就餐问题需要通过信号量机制解决。死锁产生的四个必要条件是互斥、占有并等待、不可剥夺、循环等待预防死锁可通过破坏其中一个条件实现。内存管理采用分页、分段、段页式等存储管理方式。虚拟内存技术通过请求分页和页面置换算法OPT、FIFO、LRU、Clock实现逻辑地址到物理地址的映射提高了内存利用率。四、数据库系统数据库系统由数据库、数据库管理系统DBMS、应用系统和数据库管理员组成。数据模型包括层次模型、网状模型和关系模型其中关系模型是目前最常用的模型。关系数据库的基本概念包括关系表、元组行、属性列、主键、外键等。关系代数运算包括选择、投影、连接、除、并、交、差等。数据库设计的步骤包括需求分析、概念结构设计E-R图、逻辑结构设计关系模式转换、物理结构设计。E-R图中的实体用矩形表示属性用椭圆表示联系用菱形表示联系类型包括一对一1:1、一对多1:N、多对多M:N。SQL语言分为数据定义语言DDLCREATE、ALTER、DROP、数据操纵语言DMLINSERT、UPDATE、DELETE、数据查询语言DQLSELECT和数据控制语言DCLGRANT、REVOKE。事务是数据库操作的逻辑单位具有ACID四大特性原子性Atomicity、一致性Consistency、隔离性Isolation、持久性Durability。并发控制主要通过锁机制共享锁、排他锁和两段锁协议实现可能产生的问题包括丢失修改、不可重复读、读脏数据等。五、计算机网络计算机网络按照覆盖范围可分为局域网LAN、城域网MAN和广域网WAN。OSI参考模型分为七层物理层、数据链路层、网络层、传输层、会话层、表示层、应用层。TCP/IP模型则分为四层网络接口层、网际层、传输层、应用层。物理层负责比特流的传输涉及传输介质、编码方式等。数据链路层负责帧的传输提供差错控制和流量控制CSMA/CD是以太网采用的介质访问控制协议。网络层负责路由选择和分组转发IP协议是核心协议IPv4地址分为A、B、C、D、E五类子网掩码用于划分子网。常见路由协议包括RIP基于距离向量和OSPF基于链路状态。传输层提供端到端的通信TCP是面向连接的可靠传输协议通过三次握手建立连接、四次挥手释放连接采用滑动窗口机制实现流量控制UDP是无连接的不可靠传输协议适用于实时性要求高的应用。应用层协议包括HTTP、FTP、SMTP、DNS等。六、软件工程软件工程是应用工程化的方法开发和维护软件的学科。软件生命周期包括可行性研究、需求分析、概要设计、详细设计、编码、测试、运行维护等阶段。需求分析的目标是明确系统必须做什么常用方法包括结构化分析SA和面向对象分析OOA。结构化分析的核心工具是数据流图DFD和数据字典DD。DFD由数据流、加工处理、数据存储、外部实体四个基本元素组成采用自顶向下、逐层分解的方法绘制。软件测试分为单元测试、集成测试、确认测试和系统测试。白盒测试基于程序内部逻辑设计测试用例常用方法包括语句覆盖、判定覆盖、条件覆盖、路径覆盖等黑盒测试基于功能需求设计测试用例常用方法包括等价类划分、边界值分析、错误推测法、因果图法等。软件维护分为改正性维护、适应性维护、完善性维护和预防性维护其中完善性维护所占比例最大。七、面向对象技术与UML面向对象OO技术以对象为核心具有封装、继承、多态三大基本特征。封装将数据和操作数据的方法绑定在一起隐藏内部实现细节继承允许子类复用父类的属性和方法多态使同一操作作用于不同对象时产生不同的行为。UML统一建模语言是面向对象系统的可视化建模语言包含多种图形用例图描述系统功能与参与者之间的关系包括参与者、用例、关联、包含、扩展、泛化等关系。类图描述系统的静态结构包括类名、属性、方法以及类之间的关联、聚合、组合、依赖、泛化继承、实现等关系。序列图时序图描述对象之间的动态交互按时间顺序展示消息传递过程。状态图描述对象在其生命周期中的状态变化。活动图描述业务流程或算法的工作流程。八、信息安全信息安全的基本属性包括机密性、完整性、可用性、可控性和不可否认性。常见的安全威胁包括窃听、篡改、伪装、重放、拒绝服务攻击等。加密技术分为对称加密DES、AES和非对称加密RSA、ECC。对称加密加解密使用同一密钥速度快但密钥分发困难非对称加密使用公钥和私钥配对解决了密钥分发问题但速度较慢。实际应用中常将两者结合如SSL/TLS协议。数字签名利用非对称加密技术实现身份认证和不可否认性发送方用私钥签名接收方用公钥验证。数字证书由认证中心CA签发用于绑定公钥和持有者身份。防火墙是网络安全的屏障分为包过滤防火墙、应用级网关和状态检测防火墙。入侵检测系统IDS用于监测网络或系统中的异常行为。九、标准化与知识产权信息技术标准是规范信息技术产品、系统和服务的技术规范。我国标准分为国家标准GB、行业标准、地方标准和企业标准。国际标准主要包括ISO国际标准化组织、IEC国际电工委员会、ITU国际电信联盟制定的标准。软件著作权保护软件的源代码和目标代码保护期为作者终生及其死亡后50年。专利权保护发明创造发明专利保护期为20年实用新型和外观设计专利保护期为10年。商标权保护商业标识注册有效期为10年可续展。十、计算机专业英语计算机专业英语是阅读技术文档、国际标准和前沿论文的基础。常见术语包括algorithm算法、compiler编译器、database数据库、encryption加密、interface接口、protocol协议、thread线程、virtual memory虚拟内存等。十一、应用技术当前主流应用技术包括云计算、大数据、人工智能、物联网、区块链等。云计算提供IaaS、PaaS、SaaS三种服务模式大数据技术涉及Hadoop、Spark等分布式计算框架人工智能涵盖机器学习、深度学习、自然语言处理等领域物联网通过RFID、传感器等技术实现物物相连区块链是一种去中心化的分布式账本技术。十二、数据流图DFD设计与分析数据流图是结构化分析的核心工具用于描述系统的数据流动和处理过程。DFD包含四种基本符号外部实体External Entity系统之外的数据源或数据终点用矩形表示。加工Process对数据进行变换或处理的单元用圆角矩形或圆形表示。数据流Data Flow数据的流动方向用带箭头的线段表示。数据存储Data Store数据的静态存储用双横线或开口矩形表示。DFD设计遵循自顶向下、逐层分解的原则。顶层DFD将整个系统视为一个加工展示系统与外部实体的交互0层DFD将系统分解为若干主要加工下层DFD对上层加工进一步细化。DFD设计需注意父图与子图的平衡输入输出数据流一致、加工的命名规范动词宾语、避免黑洞只有输入无输出和奇迹只有输出无输入等错误。十三、数据库设计数据库设计是构建高效、可靠数据库系统的关键过程主要包括以下步骤1. 需求分析收集和分析用户对数据的需求形成数据字典和需求说明书。2. 概念结构设计使用E-R图描述实体、属性和联系。设计原则包括真实性、简洁性、易理解性。局部E-R图设计完成后需进行视图集成消除冲突属性冲突、命名冲突、结构冲突形成全局E-R图。3. 逻辑结构设计将E-R图转换为关系模式。转换规则为每个实体转换为一个关系模式每个多对多联系转换为一个独立的关系模式一对多联系可与任一实体合并一对一联系可与任意实体合并。然后进行规范化处理消除数据冗余和操作异常。范式包括第一范式1NF属性不可再分、第二范式2NF消除非主属性对码的部分依赖、第三范式3NF消除非主属性对码的传递依赖、BCNF消除主属性对码的部分和传递依赖。4. 物理结构设计确定存储结构、存取方法、索引策略等。5. SQL实现使用SQL语言创建表、视图、索引编写查询语句。例如CREATETABLEStudent(SnoCHAR(10)PRIMARYKEY,SnameVARCHAR(20)NOTNULL,SageINT,SdeptVARCHAR(20));SELECTSname,SageFROMStudentWHERESdeptCSANDSage20ORDERBYSageDESC;十四、UML建模用例图描述系统功能。例如图书馆管理系统中参与者读者的用例包括查询图书“借阅图书”“归还图书”参与者管理员的用例包括添加图书“删除图书”“管理读者”。类图描述系统静态结构。例如------------------ ------------------ | Reader | | Book | ------------------ ------------------ | - readerId: int | | - isbn: String | | - name: String | | - title: String | | - phone: String | | - author: String | ------------------ | - available: bool| | borrow() | ------------------ | returnBook() | | checkStatus() | ------------------ ------------------ | | | ------------------ ------| BorrowRecord | ------------------ | - recordId: int | | - borrowDate | | - returnDate | ------------------ | createRecord() | | updateRecord() | ------------------序列图描述对象间交互。以借阅图书为例读者对象向系统界面发送借阅请求界面调用控制器的borrowBook方法控制器查询Book对象检查可借状态创建BorrowRecord对象记录借阅信息最后返回结果给读者。十五、C语言算法实现以下分别用C语言实现分治、动态规划和回溯三种经典算法策略1. 分治法——归并排序#includestdio.h#includestdlib.h// 合并两个有序子数组voidmerge(intarr[],intleft,intmid,intright){intn1mid-left1;intn2right-mid;int*L(int*)malloc(n1*sizeof(int));int*R(int*)malloc(n2*sizeof(int));for(inti0;in1;i)L[i]arr[lefti];for(intj0;jn2;j)R[j]arr[mid1j];inti0,j0,kleft;while(in1jn2){if(L[i]R[j])arr[k]L[i];elsearr[k]R[j];}while(in1)arr[k]L[i];while(jn2)arr[k]R[j];free(L);free(R);}voidmergeSort(intarr[],intleft,intright){if(leftright){intmidleft(right-left)/2;mergeSort(arr,left,mid);// 分解左半部分mergeSort(arr,mid1,right);// 分解右半部分merge(arr,left,mid,right);// 合并}}2. 动态规划——0/1背包问题#includestdio.hintmax(inta,intb){returnab?a:b;}intknapsack(intW,intwt[],intval[],intn){intdp[n1][W1];for(inti0;in;i){for(intw0;wW;w){if(i0||w0)dp[i][w]0;elseif(wt[i-1]w)dp[i][w]max(val[i-1]dp[i-1][w-wt[i-1]],dp[i-1][w]);elsedp[i][w]dp[i-1][w];}}returndp[n][W];}3. 回溯法——八皇后问题#includestdio.h#includestdbool.h#defineN8intboard[N][N];intsolutionCount0;boolisSafe(introw,intcol){// 检查当前列上方for(inti0;irow;i)if(board[i][col])returnfalse;// 检查左上对角线for(intirow,jcol;i0j0;i--,j--)if(board[i][j])returnfalse;// 检查右上对角线for(intirow,jcol;i0jN;i--,j)if(board[i][j])returnfalse;returntrue;}voidsolveNQueens(introw){if(rowN){solutionCount;return;}for(intcol0;colN;col){if(isSafe(row,col)){board[row][col]1;// 放置皇后solveNQueens(row1);// 递归下一行board[row][col]0;// 回溯}}}十六、选答题Java面向对象程序设计Java是纯粹的面向对象语言以下展示面向对象语法与设计模式的应用1. 封装、继承与多态// 抽象基类abstractclassShape{protectedStringcolor;publicShape(Stringcolor){this.colorcolor;}publicabstractdoublearea();publicvoiddisplay(){System.out.println(Color: color, Area: area());}}// 子类继承classCircleextendsShape{privatedoubleradius;publicCircle(Stringcolor,doubleradius){super(color);this.radiusradius;}Overridepublicdoublearea(){returnMath.PI*radius*radius;}}classRectangleextendsShape{privatedoublewidth,height;publicRectangle(Stringcolor,doublewidth,doubleheight){super(color);this.widthwidth;this.heightheight;}Overridepublicdoublearea(){returnwidth*height;}}// 多态演示publicclassPolymorphismDemo{publicstaticvoidmain(String[]args){Shape[]shapes{newCircle(Red,5),newRectangle(Blue,4,6)};for(Shapes:shapes){s.display();// 运行时多态}}}2. 设计模式——单例模式与工厂模式// 单例模式饿汉式classDatabaseConnection{privatestaticfinalDatabaseConnectioninstancenewDatabaseConnection();privateDatabaseConnection(){}publicstaticDatabaseConnectiongetInstance(){returninstance;}publicvoidconnect(){System.out.println(Database connected.);}}// 工厂模式interfaceAnimal{voidspeak();}classDogimplementsAnimal{publicvoidspeak(){System.out.println(Woof!);}}classCatimplementsAnimal{publicvoidspeak(){System.out.println(Meow!);}}classAnimalFactory{publicstaticAnimalcreateAnimal(Stringtype){if(dog.equalsIgnoreCase(type))returnnewDog();if(cat.equalsIgnoreCase(type))returnnewCat();thrownewIllegalArgumentException(Unknown animal type);}}