数据结构第1章概论

《数据结构第1章概论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构DataStructure计算机科学与技术系主讲教师：路游2学时数：64（44讲课+20上机）学分：4教材：《数据结构（C语言版）》严蔚敏吴伟民编著清华大学出版社参考书：《数据结构题集(C语言版)》严蔚敏、吴伟民著《数据结构课程设计》苏仕华等编著机械工业出版社《数据结构题集(C语言篇)——习题与解析（修订版）》李春葆编著清华大学出版社上机：第5-14周，星期一，1-2节，3教-404内容安排章内容学时章内容学时1绪论27图62线性表68动态存储管理略3栈和队列69查找64串410内部排序45数组和广义表411外部排序略6树和二叉树612文件略4第1章序

2、论1.1计算机基本概念（复习）1.2数据结构基本概念1.3抽象数据类型概念1.4算法效率的度量作业51.1计算机基本概念(复习）计算机系统＝硬件系统＋软件系统Q1硬件系统由哪几部分组成？Q2微型计算机与其他计算机的区别？Q3内存与外存的不同之处是？Q4计算机内常用到哪些数制？Q5计算机主要技术指标有哪些?硬件概念复习软件概念复习Q1软件系统包含哪些软件？Q2什么是系统软件和应用软件？Q3机器语言、汇编语言、高级语言的区别？6Q1：计算机硬件系统由哪几部分组成？答：计算机硬件系统由部分组成：也可浓缩为3部分：存储器CPUI/O接口及设备人脑：感受→判断→计算→记

3、忆→反应电脑：输入→控制→运算→存储→输出控制器输入运算器存储器输出主机57Q2：微型计算机与一般意义上的计算机有什么区别？其本质特征是答：运算器和控制器集成在一块IC芯片上这种CPU简称MPU8Q3：内存与外存是一回事吗？能被CPU直接控制（BUS直连）的存储器称为内存通过I/O接口才能被CPU控制的存储器称为外存答：不是一回事。它们的区别是：I/O接口输入运算器内存储器控制器输出BUS外存储器CPU9Q4：计算机内常用到哪些数制？A.（11011001）BB.（75）DC.（37）OD.（2A）H答案：C2进制(B)8进制(O)10进制(D)16进制(H)

4、例3：下列四种不同进制的无符号数中，最小的数是∶例2：下列数据中，有可能是八进制数的是∶A.238B.764C.396D.789例1：10(B)＝D10(O)＝D10(H)＝D281610Q5：计算机主要技术指标有哪些？——CPU一次能处理的二进制位数，它与数据总线的根数有关，如8位机，16位机、32位机等等——运算器做一次“加”动作的最小可靠时间，如奔4机器主频2.8G（Hz）——CPU每秒能执行加法指令的次数（MIPS）——bit，Byte，KB，MB，GB，TB练：微机中1K字节表示的二进制位数是：1B=8bit1KB=210B1MB=210KB1GB=

5、210MBA.1000B.8×1000C.1024D.8×1024答案：D字长主频运算速度主存容量11Q1：软件系统包含哪些软件？裸机系统软件操作系统支援软件应用软件答：包含系统软件和应用软件两大类12Q2：什么是系统软件？什么是应用软件？答：系统软件——管理计算机系统各部分，使之高效工作，同时为上层提供服务。应用软件——处于系统软件的上层，帮助计算机用户完成特定领域的工作。系统软件中最重要的是操作系统（OperatingSystem），它是一个大型的、优秀的程序，管理着计算机的全部软、硬件资源，并提供人机交互的界面。13Q3：机器语言、汇编语言、高级语言的区

6、别？——用二进制代码直接表示的语言，是计算机唯一能识别、执行的语言——符号化了的机器语言（即用助记符来写程序，靠汇编程序翻译成机器码才能执行）——接近自然英语和数学公式的语言（要通过编译或解释程序翻译成机器码）答：低级语言面向机器，执行速度快，效率高；高级语言面向问题，易理解，易移植。机器语言汇编语言高级语言141.2数据结构基本概念Q1什么是数据结构？Q2学习数据结构有什么用？Q3数据结构涵盖的主要内容？讨论：15Q1：什么是数据结构？16“学生”表格17“课程”表格18选课单包含如下信息学号课程编号成绩时间学生选课系统中实体构成的网状关系学生(学号,姓名,

7、性别,籍贯)课程(课程号,课程名,性别,籍贯)选课(学号,课程号,成绩)19UNIX文件系统的系统结构图/(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp20术语：数据、数据元素和数据项（见教材P4定义）：数据(data)——所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息）。数据元素(dataelement)——是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。数据项(Dataitem)——构成数据元素的项目。是具有独立含义的最小标

8、识单位（又称字段、域、属性等）。三者之