精华内容
参与话题
问答
  • 2020考研计算机(408)考试大纲

    万次阅读 多人点赞 2019-11-03 17:08:42
    2020考研计算机(408)考试大纲 ...


    I 考试性质

    计算机学科专业基础综合考试是为高等院校和科研院所招收计算机科学与技术学科的硕士研究生而设置的具有选拔性质的联考科目,其目的是科学、公平、有效地测试考生掌握计算机科学与技术学科大学本科阶段专业知识、基本理论、基本方法的水平和分析问题、解决问题的能力,评价的标准是高等院校计算机科学与技术学科优秀本科毕业生所能达到的及格或及格以上水平,以利于各高等院校和科研院所择优选拔,确保硕士研究生的招生质量。


    II 考查目标

    计算机学科专业基础综合考试涵盖数据结构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的基本概念、基本原理和基本方法,能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。


    III 考试形式和试卷结构

    一、试卷满分及考试时间

    本试卷满分为150分,考试时间为180分钟。


    二、答题方式

    答题方式为闭卷、笔试。


    三、试卷内容结构

    数据结构 45

    计算机组成原理 45

    操作系统 35

    计算机网络 25


    四、试卷题型结构

    单项选择题 80 (40小题,每小题2)

    综合应用题 70


    IV 考查内容

    数据结构

    【考查目标】

    1.掌握数据结构的基本概念、基本原理和基本方法。

    2.掌握数据的逻辑结构、存储结构及基本操作的实现,能够对算法进行基本的时间复杂度与空间复杂度的分析。

    3.能够运用数据结构基本原理和方法进行问题的分析与求解,具备采用CC++语言设计与实现算法的能力。


    一、线性表

    ()线性表的定义和基本操作

    ()线性表的实现

    1.顺序存储

    2.链式存储

    3.线性表的应用


    二、栈、队列和数组

    ()栈和队列的基本概念

    ()栈和队列的顺序存储结构

    ()栈和队列的链式存储结构

    ()栈和队列的应用

    ()特殊矩阵的压缩存储


    三、树与二叉树

    ()树的基本概念

    ()二叉树

    1.二叉树的定义及其主要特征

    2.二叉树的顺序存储结构和链式存储结构

    3.二叉树的遍历

    4.线索二叉树的基本概念和构造

    ()树、森林

    1.树的存储结构

    2.森林与二叉树的转换

    3.树和森林的遍历

    ()树与二叉树的应用

    1.二叉排序树

    2.平衡二叉树

    3.哈夫曼(Huffman)树和哈夫曼编码


    四、图

    ()图的基本概念

    ()图的存储及基本操作

    1.邻接矩阵法

    2.邻接表法

    3.邻接多重表、十字链表

    ()图的遍历

    1.深度优先搜索

    2.广度优先搜索

    ()图的基本应用

    1.最小(代价)生成树

    2.最短路径

    3.拓扑排序

    4.关键路径


    五、查找

    ()查找的基本概念

    ()顺序查找法

    ()分块查找法

    ()折半查找法

    ()B树及其基本操作、B+树的基本概念

    ()散列(Hash)

    ()字符串模式匹配

    ()查找算法的分析及应用


    六、排序

    ()排序的基本概念

    ()插入排序

    1.直接插入排序

    2.折半插入排序

    ()气泡排序(bubble sort)

    ()简单选择排序

    ()希尔排序(shell sort)

    ()快速排序

    ()堆排序

    ()二路归并排序(merge sort)

    ()基数排序

    ()外部排序

    (十一)各种内部排序算法的比较

    (十二)排序算法的应用


    计算机组成原理

    【考查目标】

    1.理解单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式,具有完整的计算机系统的整机概念。

    2.理解计算机系统层次化结构概念,熟悉硬件与软件之间的界面,掌握指令集体系结构的基本知识和基本实现方法。

    3.能够综合运用计算机组成的基本原理和基本方法,对有关计算机硬件系统中的理论和实际问题进行计算、分析,对一些基本部件进行简单设计;并能对高级程序设计语言(C语言)中的相关问题进行分析。


    一、计算机系统概述

    ()计算机发展历程

    ()计算机系统层次结构

    1.计算机系统的基本组成

    2.计算机硬件的基本组成

    3.计算机软件和硬件的关系

    4.计算机的工作过程

    ()计算机性能指标

    吞吐量、响应时间;CPU时钟周期、主频、CPICPU执行时间;MIPSMFLOPS GFLOPSTFLOPSPFLOPS


    二、数据的表示和运算

    ()数制与编码

    1.进位计数制及其相互转换

    2.真值和机器数

    3.BCD

    4.字符与字符串

    5.校验码

    ()定点数的表示和运算

    1.定点数的表示

    无符号数的表示;有符号整数的表示。

    2.定点数的运算

    定点数的位移运算;原码定点数的加减运算;补码定点数的加/减运算;定点数的乘/除运算;溢出概念和判别方法。

    ()浮点数的表示和运算

    1.浮点数的表示

    IEEE 754标准

    2.浮点数的加/减运算

    ()算术逻辑单元ALU

    1.串行加法器和并行加法器

    2.算术逻辑单元ALU的功能和结构


    三、存储器层次结构

    ()存储器的分类

    ()存储器的层次化结构

    ()半导体随机存取存储器

    1.SRAM存储器

    2.DRAM存储器

    3.只读存储器

    4.Flash存储器

    ()主存储器与CPU的连接

    ()双口RAM和多模块存储器

    ()高速缓冲存储器(Cache)

    1.Cache的基本工作原理

    2.Cache和主存之间的映射方式

    3.Cache中主存块的替换算法

    4.Cache写策略

    ()虚拟存储器

    1.虚拟存储器的基本概念

    2.页式虚拟存储器

    3.段式虚拟存储器

    4.段页式虚拟存储器

    5.TLB(快表)


    四、指令系统


    ()指令格式

    1.指令的基本格式

    2.定长操作码指令格式

    3.扩展操作码指令格式

    ()指令的寻址方式

    1.有效地址的概念

    2.数据寻址和指令寻址

    3.常见寻址方式

    ()CISCRISC的基本概念


    五、中央处理器(CPU)

    ()CPU的功能和基本结构

    ()指令执行过程

    ()数据通路的功能和基本结构

    ()控制器的功能和工作原理

    1、硬布线控制器

    2、微程序控制器

    微程序、微指令和微命令;微指令的编码方式;微地址的形式方式。

    ()指令流水线

    1、指令流水线的基本概念

    2、指令流水线的基本实现

    3、超标量和动态流水线的基本概念


    六、总线

    ()总线概述

    1、总线的基本概念

    2、总线的分类

    3、总线的组成及性能指标

    ()总线仲裁

    1、集中仲裁方式

    2、分布仲裁方式

    ()总线操作和定时

    1、同步定时方式

    2、异步定时方式

    ()总线标准


    七、输入输出(I/O)系统


    ()I/O系统基本概念

    ()外部设备

    1、输入设备:键盘、鼠标

    2、输出设备:显示器、打印机

    3、外存储器:硬盘存储器、磁盘阵列、光盘存储器

    ()I/O接口(I/O控制器)

    1I/O接口的功能和基本结构

    2I/O端口及其编址

    ()I/O方式

    1、程序查询方式

    2、程序中断方式

    中断的基本概念;中断响应过程;中断处理过程;多重中断和中断屏蔽的概念。

    3DMA方式

    DMA控制器的组成,DMA传送过程。


    操作系统

    【考查目标】

    1.掌握操作系统的基本概念、基本原理和基本功能,理解操作系统的整体运行过程。

    2.掌握操作系统进程、内存、文件和I/O管理的策略、算法、机制以及相互关系。

    3.能够运用所学的操作系统原理、方法与技术分析问题和解决问题,并能利用C语言描述相关算法。

    一、操作系统概述

    ()操作系统的概念、特征、功能和提供的服务

    ()操作系统的发展与分类

    ()操作系统的运行环境

    1.内核态与用户态

    2.中断、异常

    3.系统调用

    ()操作系统体系结构


    二、进程管理

    ()进程与线程

    1.进程概念

    2.进程的状态与转换

    3.进程控制

    4.进程组织

    5.进程通信

    共享存储系统;消息传递系统;管道通信。

    6.线程概念与多线程模型

    ()处理机调度

    1.调度的基本概念

    2.调度时机、切换与过程

    3.调度的基本准则

    4.调度方式

    5.典型调度算法

    先来先服务调度算法;短作业(短进程、短线程)优先调度算法;时间片轮转调度算法;优先级调度算法;高响应比优先调度算法;多级反馈队列调度算法。

    ()同步与互斥

    1.进程同步的基本概念

    2.实现临界区互斥的基本方法

    软件实现方法;硬件实现方法。

    3.信号量

    4.管程

    5.经典同步问题

    生产者-消费者问题;读者-写者问题;哲学家进餐问题。

    ()死锁

    1.死锁的概念

    2.死锁处理策略

    3.死锁预防

    4.死锁避免

    系统安全状态,银行家算法。

    5.死锁检测和解除


    三、内存管理

    ()内存管理基础

    1.内存管理概念

    程序装入与链接;逻辑地址与物理地址空间;内存保护。

    2.交换与覆盖

    3.连续分配管理方式

    4.非连续分配管理方式

    分页管理方式;分段管理方式;段页式管理方式。

    ()虚拟内存管理

    1.虚拟内存基本概念

    2.请求分页管理方式

    3.页面置换算法

    最佳置换算法(OPT);先进先出置换算法(FIFO);最近最少使用置换算法(LRU);时钟置换算法(CLOCK)

    4.页面分配策略

    5.工作集

    6.抖动


    四、文件管理

    ()文件系统基础

    1.文件概念

    2.文件的逻辑结构

    顺序文件;索引文件;索引顺序文件。

    3.目录结构

    文件控制块和索引节点;单级目录结构和两级目录结构;树形目录结构;图形目录结构。

    4.文件共享

    5.文件保护

    访问类型;访问控制。

    ()文件系统实现

    1.文件系统层次结构

    2.目录实现

    3.文件实现

    ()磁盘组织与管理

    1.磁盘的结构

    2.磁盘调度算法

    3.磁盘的管理

    五、输入输出(I/O)管理

    ()I/O管理概述

    1.I/O控制方式

    2. I/O软件层次结构

    ()I/O核心子系统

    1.I/O调度概念

    2.高速缓存与缓冲区

    3.设备分配与回收

    4.假脱机技术(SPOOLing)


    计算机网络

    【考查目标】

    1.掌握计算机网络的基本概念、基本原理和基本方法。

    2.掌握计算机网络的体系结构和典型网络协议,了解典型网络设备的组成和特点,理解典型网络设备的工作原理。

    3.能够运用计算机网络的基本概念、基本原理和基本方法进行网络系统的分析、设计和应用。


    一、计算机网络体系结构

    ()计算机网络概述

    1.计算机网络的概念、组成与功能

    2.计算机网络的分类

    3.计算机网络的标准化工作及相关组织

    ()计算机网络体系结构与参考模型

    1.计算机网络分层结构

    2.计算机网络协议、接口、服务等概念

    3.ISO/OSI参考模型和TCP/IP模型


    二、物理层

    ()通信基础

    1.信道、信号、宽带、码元、波特、速率、信源与信宿等基本概念

    2.奈奎斯特定理与香农定理

    3.编码与调制

    4.电路交换、报文交换与分组交换

    5.数据报与虚电路

    ()传输介质

    1.双绞线、同轴电缆、光纤与无线传输介质

    2.物理层接口的特性

    ()物理层设备

    1.中继器

    2.集线器


    三、数据链路层

    ()数据链路层的功能

    ()组帧

    ()差错控制

    1.检错编码

    2.纠错编码

    ()流量控制与可靠传输机制

    1.流量控制、可靠传输与滑轮窗口机制

    2.停止-等待协议

    3.后退N帧协议(GBN)

    4.选择重传协议(SR)

    ()介质访问控制

    1.信道划分

    频分多路复用、时分多路复用、波分多路复用、码分多路复用的概念和基本原理。

    2.随即访问

    ALOHA协议;CSMA协议;CSMA/CD协议;CSMA/CA协议。

    3.轮询访问

    令牌传递协议

    ()局域网

    1.局域网的基本概念与体系结构

    2.以太网与IEEE 802.3

    3.IEEE 802.11

    4.令牌环网的基本原理

    ()广域网

    1.广域网的基本概念

    2.PPP协议

    3.HDLC协议

    ()数据链路层设备

    1.网桥的概念和基本原理

    2.局域网交换机及其工作原理。


    四、网络层

    ()网络层的功能

    1.异构网络互联

    2.路由与转发

    3.拥塞控制

    ()路由算法

    1.静态路由与动态路由

    2.距离-向量路由算法

    3.链路状态路由算法

    4.层次路由

    ()IPv4

    1.IPv4分组

    2.IPv4地址与NAT

    3.子网划分与子网掩码、CIDR

    4.ARP协议、DHCP协议与ICMP协议

    ()IPv6

    1.IPv6的主要特点

    2.IPv6地址

    ()路由协议

    1.自治系统

    2.域内路由与域间路由

    3.RIP路由协议

    4.OSPF路由协议

    5.BGP路由协议

    ()IP组播

    1.组播的概念

    2.IP组播地址

    ()移动IP

    1.移动IP的概念

    2.移动IP的通信过程

    ()网络层设备

    1.路由器的组成和功能

    2.路由表与路由转发


    五、传输层

    ()传输层提供的服务

    1.传输层的功能

    2.传输层寻址与端口

    3.无连接服务与面向连接服务

    ()UDP协议

    1.UDP数据报

    2.UDP校验

    ()TCP协议

    1.TCP

    2.TCP连接管理

    3.TCP可靠传输

    4.TCP流量控制与拥塞控制


    六、应用层

    ()网络应用模型

    1.客户/服务器模型

    2.P2P模型

    ()DNS系统

    1.层次域名空间

    2.域名服务器

    3.域名解析过程

    ()FTP

    1.FTP协议的工作原理

    2.控制连接与数据连接

    ()电子邮件

    1.电子邮件系统的组成结构

    2.电子邮件格式与MIME

    3.SMTP协议与POP3协议

    ()WWW

    1.WWW的概念与组成结构

    2.HTTP协议



    展开全文
  • 计算机408考研专题(建议收藏)

    千次阅读 2020-08-01 15:45:33
    一、笔试部分 1. 数学 ① 高数 ② 线性代数 ③ 概率论与数理统计 数学会在后期更新。。。。 2.英语 英语,这个我办不了。 3.政治 萧阿姨万岁 4.专业课 ① 数据结构 ② 计算机组成原理 ...一般OJ类型的算法和数据结

    一、笔试部分

    1. 数学

    ① 高数
    ② 线性代数
    ③ 概率论与数理统计

    数学会在后期更新。。。。

    2.英语

    英语,这个我办不了。

    3.政治

    萧阿姨万岁

    4.专业课

    ① 数据结构
    ② 计算机组成原理
    ③ 计算机网络
    ④ 操作系统

    二、 面试部分

    1.数据库

    2. 设计模式

    3. 算法设计分析

    4.软件工程

    5. Java、Python、C++等相关语言

    6.时下研究方向的热点问题

    7.英语素养(英语问答,英文介绍什么的)

    8.唠嗑(拉家常,展现个人涵养的机会)

    三、可能面临的机试

    一般OJ类型的算法和数据结构题目,可以参考ACM(入门难度),PAT。






    2020年8月21发布,本次首先给出框架,稍后会对内容进行填充。希望大家多多给出意见,然后收藏,点赞。👍

    展开全文
  • 408考研整理资料

    2019-04-10 10:57:25
    本人考研上岸985,自己整理了一些计算机408的资料,里面还有包括高数,英语的一些资料。需要的积分不是很多,希望下载看看~
  • 2018考研计算机408经验详谈

    万次阅读 多人点赞 2018-03-22 20:46:07
    考研408经验详谈 备考时间:2017.03.10 基础情况:数据结构,计组,操作系统,网络水过。。。基础约为零。。。 实考成绩:133 前言:408备考最讲求“反复多次与全面”,这句话在王道单科书-《操作系统复习指导...

    2018浙大计算机考研经验总述

    2018考研数学经验详谈

    考研408经验详谈

    备考时间:2017.03.10

    基础情况:数据结构,计组,操作系统,网络水过。。。基础约为零。。。

    实考成绩:133

     

    前言:408备考最讲求“反复多次与全面”,这句话在王道单科书-《操作系统复习指导》中出现了三次,可见这句话对于复习408而言是十分重要的,我也在复习过程中对这句话十分有感触,量变总会产生质变。408考试的难度在于出题面十分广泛,题型千变万化,唯有把基础打扎实才能以不变应万变。本人复习为了求稳大概过了有5-6+轮,考试成绩也略高于估分。选择题应该是错2-3个,大题错10分左右。(18考试难度略低于前几年,题型均为常规题。19年考试也许会变难一些,所以不管题目难易,把目标都定在130+,并且要脚踏实地的复习)

     

    辅导书:

    数据结构:严蔚敏教材(一遍),王道(3遍),天勤(1遍),1800题(不是很推荐,可以买来刷一下选择题)

    计算机组成原理:教材(一遍),计算机软硬件接口(一遍),王道(3遍),天勤(1遍)

    操作系统:教材(粗略看过1遍,导致操作系统学的最差。。),王道(3遍),天勤(1遍)

    网络:谢希仁教材(太厚,没有看。。),王道(3遍),天勤(1遍)

    真题、模拟题:王道真题、王道8套模拟题、天勤8套模拟题。

    (注:以上的遍数都是完整的次数,部分重点章节可能次数++)

     

    视频课:(1.5倍速)

    数据结构:姥姥的DS课,强推

    计组:哈工大刘宏伟(第一轮打基础听着看的。。并没有记住多少)

    操作系统:mooc上一位南大教授的课(第一轮听过一遍,10月份又听过一遍)

    网络:前期网络没有听课,后期复习的比较充分后,听过哈工大一位老师的网课来强化(10月份)

     

    具体时间规划:(仅供参考)

    第一轮:3.10-6.30 (每天3小时左右)

    第一轮还在打基础阶段,很多知识都是第一次认真学,进度特别慢,复习(预习)特别痛苦,尤其是计组、操作系统王道上选择题错哭。。。(错误率50%+?)这对于跨考生第一次学是十分正常的现象,所以不用担心,第一轮学习对计算机学科大体框架有个印象,后期二三轮复习就会加快很多,做题错误率也会大量减少。大概时间分配数据结构、计组各一个月左右,操作系统、网络各二十天左右。

    第二轮:7.1-8.31(每天4小时+)

    七月初考试周再加上暑假期间回家呆了一周基本上暑假两个月的时间真正复习的时间大概一个半月。在这一个半月期间,为了加深记忆,根据王道天勤的知识点做了一份详细的笔记,基本上提取了王道和天勤上更加精华的知识点。这轮复习主要是做笔记和完成王道习题,经过一轮复习和做笔记的强化,做题错误率明显下降。

     

    第三轮:9.1-10.20

    经过第一轮预习的懵懂再加上第二轮复习的强化,此时对计算机的理解会达到一个比较深刻的阶段,但由于408的知识点广而全面,所以很多知识点会有所遗忘。9月份把天勤上的选择题刷过一遍,也把历年真题打印了下来,除了16,17的真题都做了第一遍,由于基本上所有真题都在王道出现过,所以09-15年真题基本上都有130+。16、17准备后边留着模拟一下。做完真题又跑去做天勤模拟题,天勤的模拟题选择题质量还可以,每套卷子错5-10个选择题的样子,大题的话风格和408真题有所不同,可以用来查漏补缺。王道的模拟题比较简单,选择题可以控制在5个以内。做完这些模拟题也到了10月中旬报志愿的阶段,这时候模拟了一下16和17的真题,由于自己计组浮点数的运算学的还行,前期基础复习的还比较扎实,选择题做了8个,大题错10分左右,模拟分大概125左右。16的卷子由于做王道时候做过部分题目,大概也能得倒120+的分数。经过三轮复习基本上会对408的知识提升到一个比较高的境界,也基本上可以达到应试的状态了。

    第四轮及以上:10.21-考试

    后期的复习会加快很多,这两个月基本上都在保持做题感觉,查漏补缺,加深记忆的阶段。为了加深理解,看过计算机组成与设计(软硬件接口)、现代操作系统。个别知识点比如操作系统的文件系统、内核态用户态很难理解的知识点针对性的听一些慕课上的视频。基本上所有知识点都达到一个很熟练的状态。这段时间自己之前所做的笔记也看过三四遍,王道、天勤、真题、模拟题又刷了一遍,直到考试。到应试时基本上王道上的知识点都能达到一个比较熟练的状况。。考前10天特意针对笔记中的重点、难点,还有王道天勤中的易错点,以填空的形式给自己出了一些题目,多复印了两份,感觉这个效果非常棒,那些易错的,经常错的在这个时刻也可以熟练掌握。

     

    总结:

    408复习的要点还是反复多次与全面,只有经历过不断量变才能达到质的飞跃。也不能一味追求次数而忽略了质量,特别是在复习过程中要注重思考,比如学习计组,学到后期就要对计算机的构造,形成一个三维的形态,寻找各大硬件之间的联系与区别;计算机网络构建网络的五层模型,熟练掌握各层的功能,协议等等。不是死记硬背,而是真正把书本上的知识学到自己的脑海中,这样即使出的题目再为灵活也能从容应对。

    本人基本上0基础跨考,所以费了很大的功夫去准备专业课的考试。据我所知,初试410+大多都是非科班学生,所以觉得自身实力菜的童鞋更要努力准备,赶上科班甚至超过科班的学生。对于科班的童鞋更加不能掉以轻心,不能因为是科班而放松警惕,同样也需要更加认真的准备来守住自己的那边天空!

    以下是部分笔记内容:

    以下是最后10天总结的重点、难点、易错知识点:

     

    by Phoenix

    2018浙大计算机考研经验总述

    2018考研数学经验详谈

     

     

     

     

     

    展开全文
  • 数据结构一、绪论1.1 数据结构的目的1.2 基本概念1.2.1、 数据1.2.2、数据元素、数据项1.2.3、数据对象、数据结构1.2.4、数据类型、抽象数据类型(ADT)1.3 三要素1.3.1、逻辑结构——数据元素之间的`逻辑关系`。...

    本文中使用图片,来对微信公众号【研者荣耀】中相关课程的学习

    若发布的内容有什么错误,欢迎留言探讨。

    一、绪论

    1.1 数据结构的目的

    1、如何用程序代码把现实世界的问题信息化

    如:金钱信息化(支付宝、微信)、排队信息化(微信小程序排号等待提示),聊天软件(QQ、微信等)、点餐(美团外卖、饿了么)

    2、如何用计算机高效地处理这些信息从而创造价值
    如:金钱信息化(使用float进行存储)、排队(使用数组或者数据结构中的队列)

    1.2 基本概念

    1.2.1、数据

    数据是信息的载体,是描述客观事物属性的数、字符及所有能输入到计算机并被计算机程序识别和处理的符号的集合。

    数据是计算机程序加工的原料

    1.2.2、数据元素、数据项

    数据元素是数据的基本单位,通常作为一个整体进行考虑和处理。

    一个数据元素可由若干数据项组成,数据项是构成数据元素不可分割的最小单位

    例如:在吃饭时使用基础的排队取号系统时,他将会存储每一波客户的相关信息(如下)。

       客户: 
    			取号码
    			取号时间
    			客户人数
    

    此时,这个客户的总体信息便是数据元素,而相应取号码、取号时间、客户人数则是数据元素中的三个数据项

    1.2.3、数据对象、数据结构

    结构:各个元素之间的关系

    数据结构:相互之间存在一种或者多种特定关系的数据元素的集合。

    数据对象:具有相同性质的数据元素的集合,是数据的一个子集。

    举例:依旧是上面排队吃饭的例子

    在某个门店排队的客户信息之间,存在一个取号先后和用餐先后的顺序(如下),那么便可以使用数据结构来对这一列有关系的数据进行存储。
    在这里插入图片描述
    同样的对于,其他门店也存在一样的排队信息,这时这两个数据之间具有相同的性质(号码先后等),我们就可以把他们看成是一个相同的数据对象

    1.2.4、数据类型、抽象数据类型(ADT)

    数据类型:一个值的集合和定义在此集合上的一组操作的总称。

    1)原子类型:其值不可再分的数据类型
    如:int、bool类型
    2)结构类型:其值可以分解为若干成分(分量)的数据类型。
    如:struct

    抽象数据类型(ADT):抽象数据组织及与之相关的操作。通常不考虑存储结构。

    1.3 三要素

    讨论一种数据结构时,需要关注的三个方面

    1.3.1、逻辑结构——数据元素之间的逻辑关系

    集合:各个元素同属于一个集合,数据间没有其他关系

    线性结构:数据元素之间是一对一的关系。
    特点:除了第一个元素,所有元的都有唯一的前驱;除了最后一个元素,所有的元素都有唯一的后继。
    在这里插入图片描述

    树形结构:数据元素中存在一对多的关系(类似思维导图)
    在这里插入图片描述

    图状结构(网状结构):数据元素之间存在多对多的关系
    在这里插入图片描述

    1.3.2、物理结构(存储结构)——如何用计算机表示数据元素的逻辑关系

    下列举例图逻辑结构,如下:
    在这里插入图片描述

    顺序存储:把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现。
    在这里插入图片描述

    链式存储:逻辑上相邻的元素在物理位置上可以不相邻,借助元素存储地址的指针来表示元素之间的逻辑关系。
    在这里插入图片描述

    索引存储:在存储元素信息的同时,还建立附加的索引表。索引表中的每项称为索引项,索引项的一般形式是(关键字,地址)。

    在这里插入图片描述

    散列存储:根据元素的关键字直接解算出该元素的存储地址,又称“哈希(hash)存储”(详细看第六章)。

    后三种统称为非顺序存储

    【注】:
    1、若采用顺序存储,各个数据元素在物理上必须连续的,若采用非顺序存储,啧各个数据元素在物理上可以离散的
    2、数据的存储结构会影响存储空间分配的方便程度(增删数据)。
    3、数据的存储结构会影响数据运算的速度(查找、修改数据)。

    1.3.3、数据的运算

    1、施加在数据上的运算包括运算的定义实现

    2、运算的定义是针对逻辑结构的,用于指出运算的功能

    3、运算的实现是针对存储结构的,用于指出运算的具体操作步骤

    1.4 算法

    在这里插入图片描述
    算法:
    如何处理数据结构中的信息,并用以解决实际问题。

    1.4.1 五个特性

    1、有穷性:一个算法必须在有穷步之后结束,且每一步都可在有穷时间内完成。
    [注] 程序可以是无穷的(一直在运行),但是算法必须是有穷的(在一定步骤内解决某个问题)。

    2、确定性:算法中每条指令必须有确切的含义,对于相同的输入只能得到相同的输出

    3、可行性:算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。

    4、输入:一个算法有零个或多个输入,这些输入取自于某个特定对象的集合。

    5、输出:一个算法有一个或多个输出,这些输出与输入存在某些特定的关系。

    1.4.2 “好”算法的特点

    1、正确性。算法能够正确地解决问题。

    2、可读性:算法应具有良好的可读性,以帮助人们理解。

    3、健壮性:输入非法数据时,算法能适当地做出反应或进行处理,而不会产生莫名其妙的输出结果。

    4、高效率与低存储量需求

    1.5 时间复杂度(计算技巧、必考)

    时间复杂度事前预估算法时间开销T(n)问题规模n的关系。

    时间复杂度的计算,一般是考察主函数中的while和for循环以及递归函数中的时间开销与问题规模n之间的关系。
    例如:

    for(int i =1; i <=s;i++){
    	i *= 2;
    }
    

    对于上面的这个例子我们可以看到,i在每一次的循环中他都会变成原来的2倍,也就是说最后要出现的结果过是:

    S<=i=2x,x为计算的次数

    相应的计算次数已转换就变成了x=log2S,S就是我们问题的规模将它替换成n,便可以得到时间复杂度T=O(log2n)。

    使用O(n)进行表示:

    1、一个算法的时间复杂度,可以只考虑时间复杂度公式中阶数最高的部分。

    如:T(n)=3n+3,则T(n)=O(n);
    T(n)=n2+3n,则T(n)=O(n2)

    常见阶数比较如下:
    在这里插入图片描述
    计算复杂度时的加法与乘法:

    在这里插入图片描述

    2、对于代码的时间复杂度判断:
    1)顺序执行的代码只会影响常数项,可以忽略。
    2)只需要挑选循环中的一个基本操作来分析他执行次数与n的关系即可。
    3)如果有多层嵌套循环,只需关注深层循环循环了几次。

    3、评价时间复杂度时一般考虑最坏时间复杂度平均时间复杂度

    1.6 空间复杂度

    空间复杂度:用于衡量空间开销与问题规模n之间的关系。

    程序运行时的内存需求= 程序代码+数据

    在这里插入图片描述
    如上图所示代码,无论n怎么变化,内存中的数据的大小都不会变化,因此该程序的空间复杂度S(n)=O(1)。

    算法原地工作=算法的空间复杂度为函数。

    在这里插入图片描述
    如该算法,在n发生改变时,内存中的数据所用空间也将随之变大,根据算法推断,其变化与n成正比,因此该程序空间复杂度S(n)=O(n)。

    1、与时间复杂度一样,空间复杂度只需考虑最大阶数。

    2、计算空间复杂度时只需考虑与问题规模n相关的内存空间开销,一般为变量对内存的申请。

    3、函数递归调用时也会带来内存的开销,递归时会同时开始对内存中申请多个变量,因此会影响空间复杂度。(如下图)
    加粗样式
    当n等于5时,就调用了5次函数,申请了5个内存。

    具体递归时的空间复杂度,根据算法具体情况进行计算。

    小结

    在探讨一种数据结构时:
    1)定义逻辑结构(数据元素之间的关系)
    2)定义数据的预算(针对现实需求,应该对这种逻辑结构进行什么样的运算)
    3)确定某种存储结构,实现数据结构,并实现一些对数据结构的基本运算。
    着重点:
    时间复杂度,算法的五个特性、逻辑结构,数据元素与数据项的关系。

    后篇跳转

    考研408复习笔记(二)—— 数据结构(二)

    展开全文
  • 前几天,考研大纲公布了!公布的不仅仅是政治/数学/英语等公共课大纲,还包括计算机统考的408大纲。与408大纲一起公布的,还有2019年计算机统考408的真题。小编尽可能快的获取到了真题...
  • 2009—2018年计算机考研408真题及答案高清无水印版,欢迎下载使用,可直接打印,禁止用于盈利用途。
  • 2020计算机考研408教材,全是最新版本。计算机操作系统-汤子瀛,计算机组成原理-唐朔飞,数据结构-C-严蔚敏,计算机网络-谢希仁,数据库系统概论-第5版_完整版(王珊,萨师煊) PDF电子书下载 带书签目录m
  • 计算机考研 408真题, 包含2017年之前的一些计算机真题及其答案
  • 2019年计算机考研408历年真题2009-2019下载免费下载

    万次阅读 多人点赞 2018-10-03 15:34:53
    链接:https://pan.baidu.com/s/1CWsXVt-r82IJFd-M6dUTMg 提取码:e566
  • 计算机408历年真题,2009-2019年历年真题,祝大家考研顺利,下载不了可在CSDN上联系博主~
  • 2017年计算机统考408考研真题与答案解析
  • 2020王道408 考研指导PDF,祝各位考研金榜题名!
  • 2021计算机408考研大纲 可作为复习参考
  • 2019年计算机408考研书籍

    千次阅读 2018-06-06 09:00:56
    2019年计算机408考研书籍资料收集于网络,如有侵权,请联系我百度云试看地址:链接:https://pan.baidu.com/s/1j4ozYtlf3lOG2JH8sa9lHA 密码:1da9
  • 2017年计算机统考408考研真题(含答案)2017年计算机统考408考研真题(含答案)2017年计算机统考408考研真题(含答案)
  • 2020 408考研大纲-计算机学科专业基础综合考试大纲,计算机学科专业基础综合考试大纲
  • 408计算机考研必做 2019年天勤数结高分笔记pdf 高清版
  • 408考研知识总结分析

    2020-08-01 15:10:31
    MY FIRST CSDN 第一次写文章,现在正在考研,以后会把每天学到的知识分享到这里,许愿考研成功,啊,我太难了
  • 新年已经过了几天了,现在20考研的同学们也已经开始准备复习了吧,下面启航君给大家分享一位考清华的计算机的学长的初试复试经验,希望能给大家一些帮助。 @烟雨任平生 自己考研之前也和大家一样在知乎、王道等各大...
  • 2020版的,自己实拍影印版的,看着还凑合,大小也控制的还好,没有水印什么乱七八糟的,希望大家都能考上。
  • 2020年计算机考研王道指导书籍:数据结构,计算机组成原理,操作系统,计算机网络 。 四本,无水印,pdf格式。
  • 前言 初试+复试 初试: 英语 数学 政治 专业课 初试总结 ...我是个很懒的人,不怎么喜欢写博客,所以我简单的胡说八道几句吧,写的不好,拍我我可能也看不到,右上角的×看到了么,对,就是那个,点一下。...
  • 2019-408考研之组成原理笔记——第一章

    千次阅读 多人点赞 2018-08-03 10:59:08
    计算机组成原理——笔记(基于王道资料+自己理解) 计算机系统概述 计算机发展历程 1计算机硬件与软件发展: 硬件:四代计算机:电子管-&gt;晶体管-&gt;中小规模集成电路-&...(摩尔定律-18月数量与...
  • 图片来源于王道,大致能看清楚 图片
  • 2021考研——复习规划(408篇)

    千次阅读 多人点赞 2020-04-29 20:09:21
    计算机考研408是全国统考的科目,统考科目包括四门计算机专业课:数据结构、计算机组成原理、操作系统和计算机网络,这四门课程合在一起称为计算机科学专业基础综合,共150分。四门专业课在试卷中所占的分数分别为:...
  • 2016年408考研真题43题

    2019-10-20 19:12:15
    #include<stdio.h> int setPartition(int a[],int n){ int pviot,low=0,low0=0,high=n-1,high0=n-1,flag=1,k=n/2,i; int s1=0,s2=0; while(flag){ pviot=a[low]; while(low<...
  • 408考研详解

    2018-11-16 16:09:53
    2018年考研真题,2018年考研答案解析 计算机学科专业基础综合试题
  • 2018年教育部考研大纲 数据结构+计算机组成+计算机网络+操作系统
  • 2020计算机考研408教材

    2019-03-01 21:53:26
    资源包含计算机考研408统考所有书籍:数据结构-严蔚敏/操作系统-汤子瀛/计算机组成原理-唐朔飞/计算机网络-谢希仁,均为最新版本

空空如也

1 2 3 4 5 ... 20
收藏数 66,376
精华内容 26,550
关键字:

408考研