[工学]09上半年软件设计师辅导-数据结构与算法.ppt

全国计算机技术与软件专业技术资格（水平）考试软件设计师级辅导教程 数据结构与算法设计部分 主讲：崔婀娜 辽宁省软考备考站专家组 数据结构基础知识 数据结构的定义： 数据结构是指数据元素及元素间的相互关系构造的集合。一个数据结构B可以用一个二元组表示为B = (A,R) S=（D，R）是用二元组表示的数据结构，试选择下面两种数据结构S1和S2分别对应的图形表示是（1）和（2） ，并且指出它们分别属于（3）和（4）类型的结构。 S1={D，R}，D={1，2，3，4，5}，R={ }； S2={D，R}，D={1，2，3，4，5}，R={（1，2），（1，3），（2，4），（2，5）}； 试题举例 数据结构主要研究数据的（35） 。 供选答案： A 逻辑结构 B 存储结构 C 逻辑结构和存储结构 D 逻辑结构和存储结构及其运算 数据结构基础知识 数据结构的分类： 数据结构按照逻辑关系不同分为线性结构和非线性结构，其中非线性结构又可分为树型结构和图状结构。 线性结构 线性结构是研究数据元素之间一对一的数据关系； 常用的线性结构包括：线性表、栈、队列、串、数组、广义表（考纲没要求）。 ? 线性结构的特点：P334页 ①存在唯一一个称作是“第一个”元素； ②存在唯一一个称作是“最后一个”元素； ③除第一个元素外，集合中的每个元素均只有 一个直接前驱； ④除最后一个元素外，集合中的每个元素均只有 一个直接后继； ?? 线性表 定义：是一种最简单、最常用的数据结构，简单说是由n个数据元素组成的有限序列。 ( n≥0 ) L = (a1a2～an) 线性表的存储结构： ① 顺序存储：用一组地址连续单元依次存放线性表中逻辑位置相邻的元素。(随机存取) ②?链式存储：用一组任意的存取单元依次存放线性表中的元素及元素的关系。（不可以随机存取） 包含的几种链表结构：单向链表、双向链表、循环链表 试题举例 线性表具有两种存储方式，即顺序方式和链式方式。现有一个具有五个元素的线性表L={23，17，47，05，31}，若它以链式方式存储在下列100～119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成。 100 102 104 106 108 110 112 114 116 118 05 U 17 X 23 V 31 Y 47 Z 其中指针X，Y，Z的值分别为（1） 、 （2） 、 （3） 。 （1）～（3）： A．100 B．104 C．108 D．112 E．116 F．118 G．0 H．102 I．106 J．110 试题举例 链表不具备的特点是________ A.可随机访问任何一个元素 B.插入、删除不需要移动元素 C.无需事件估计存储空间大小 D.所需空间与线性表长度呈正比 线性表的基本运算 ①在顺序存储结构上的插入、删除。 ②在链式存储结构上的运算（算法设计重点） a.单链表的插入、删除、查找。 b.双向链表的插入、删除。 ?? 试题举例 某线性表最常用的运算是插入和删除，插入运算是指在表尾插入一个新元素，删除运算是指删除表头第一个元素，那么采用 （1） 存储方式最节省运算时间。 供选答案： A 仅有尾指针的单向循环链表 B 仅有头指针的单向循环链表 C 仅有尾指针的单向链表 D 仅有尾指针的双向链表 ?? 栈 栈的定义 ：是一种特殊的线性表，它只允许在一端进行插入和删除，所以栈也称操作受限的线性表。通常把可以运算的一端称为栈顶，用top表示，而另一端称为栈底,用bottom表示。 栈的运算特点：先出后出(FILO) 栈的存储结构： ①顺序栈 ②链栈 栈的基本运算 ①初始化栈：InitStack(S) ②判栈空：Empty(S) ③入栈：Push(S,X) ④出栈：Pop(S) ⑤读栈顶元素：Top(S) ?? 试题举例 PUSH 和POP命令常用于（36）操作。 供选答案： A 队列 B 数组 C 栈 D 记录 栈的应用 表达式求值、括号匹配、将递归过程转变为非递归过程及利用栈的结构进行数制转换等等。 试题举例 设有三个元素依次进入一个栈中，则可能得到 （1） 种出栈序列，不能得到的出栈序列是