Chap1-4(习题课1)(DYS).ppt

习题课一 线性结构 第一章绪论 数据结构 逻辑结构存储结构 集合线性树形图形 顺序链式 抽象数据类型 DSP 数据对象数据关系基本操作 算法分析 时间复杂度空间复杂度 习题课一 线性结构 数据结构 抽象数据结构存储结构 线性结构非线性结构 表栈队串树图 顺序链式 算法 合适的数据结构合适的算法 习题课一 线性结构 第二章线性表 顺序表示和实现 存储表示操作 插入 删除 合并等 链式表示和实现 单链表循环链表双向链表 存储表示操作 存储表示操作 存储表示操作 习题课一 线性结构 第三章栈和队列 栈 顺序表示应用 行编辑 表达式求值 队列 循环队列顺序队列链队列 存储表示操作 存储表示操作 存储表示操作 习题课一 线性结构 第四章串 串的表示和操作 定长顺序块链堆 存储表示操作 存储表示操作 存储表示操作 存储结构 一 比较题 1 描述以下概念的区别 头指针 头结点 首结点 2 数据 数据元素和数据对象 3 数据结构与数据对象之间的区别和联系 4 数据的逻辑结构和物理结构的关系 5 数据类型和抽象数据类型 6 顺序表和线性链表 单链表 7 单链表 循环链表 双向链表 双向循环链表 习题课一 线性结构 8 栈 队列与线性表 9 栈和队列 10 限制存取点的表 双端队列 双栈 超队列 超栈 11 串和线性表 12 串的块链存储和链表 习题课一 线性结构 二 填空 1 顺序表中逻辑上相邻的元素物理位置相邻 单链表中逻辑上相邻的元素物理位置相邻 2 单链表中引入头结点的作用 3 已知p为单链表中的非首尾结点 在p结点后插入s结点的语句为 4 当对一个线性表经常进行的是存取操作 而很少进行插入和删除操作时 则采用存储结构为宜 相反 当对一个线性表经常进行的是插入和删除操作 则采用存储结构为宜 习题课一 线性结构 5 当向一个长度为n的顺序表中第i个元素之前插入一个新元素时 需要向后移动元素 6 栈和队列是两种特殊的线性表 栈的特点是 队列的特点是 对于栈 只能在插入和删除元素 对于队列 只能在插入元素和在删除元素 7 在一个单链表中删除p结点的下一个结点时 应执行的操作 8 在一个具有n个单元的顺序栈中 假定以地址高端 下标为n 作为栈底 以top作为栈顶指针 则从栈中弹出一个元素时 top的变化为 习题课一 线性结构 9 在一个链队列中 假设front和rear分别为队首指针和队尾指针 则进行插入s结点的操作时应执行 而删除一个结点的操作应执行 11 在具有n个单元的顺序存储的循环队列中 假设front和rear分别为队首指针和队尾指针 则判断队空的条件是 判断队满的条件是 12 假设有以下串 S1 IcomefromShenzhen S2 Shanghai 则完成下列运算的结果分别是 Substring Sub S1 13 7 Replace S1 Shenzhen S2 习题课一 线性结构 三 判断 1 数据元素是数据的最小单位 2 数据结构是带有结构的数据元素的集合 3 数据结构 数据元素 数据项在计算机中的映象 或表示 分别称为存储结构 结点 数据域 4 线性表的顺序存储结构优于链式存储结构 5 数据的存储结构是数据的逻辑结构在计算机中存储器里的实现 6 栈和队列是两种操作受限的线性表 习题课一 线性结构 三 判断 7 循环队列中无上溢现象 8 在线性表的顺序存储中 元素之间的逻辑关系是通过指针决定的 9 在线性结构中 每个结点有且仅有一个前驱结点和一个后继结点 10 串是一种其数据元数固定为字符的线性表 习题课一 线性结构 四 程序填空 例1 如下所示的程序是在按升序排列的单链表 不带有表头结点 中进行插入操作 在插入之后 单链表中的元素仍保持由小到大按升序排列 习题课一 线性结构 includestructnodetype intdata structnodetype link node structnodetype head q insert intx structnodetype p last next p structnodetype malloc sizeof node if p printf outofmemory n return p data x 习题课一 线性结构 if head a 单链表 首结点 不存在 return if b 插入到第一个结点 p link head head p return last head next last link while next 插入到尾结点 习题课一 线性结构 a Ap head p link NULL Bhead p p link NULL Chead p Dp head b Ahead NULLBhead link NULLChead datadataDhead data p data c Alast next next next link Bnext last last last link Cnext next link last next Dnext last link last last link d Alast pBnext pClast link pDnext link p 习题课一 线性结构 习题课一 线性结构 答案 a B b D c A d C 引发出对线性表的操作 单链表 升序 降序排列 时的插入 删除操作顺序表 升序 降序排列 时的插入 删除操作循环链表 升序 降序排列 时的插入 删除操作双向 循环 链表 升序 降序排列 时的插入 删除操作两个链表的合并操作 上机实习一 线性结构 例2 设有两个栈s1和s2 都采用顺序存储结构 并且享用一个存储区V 为尽量利用空间 减少溢出的可能 现采用栈顶相对 迎面增长的方式存储 如图所示 程序中的push 是入栈 pop 是出栈 top 是取栈顶元素 习题课一 线性结构 include defineM10intV M inttop1 top2 inti j x 习题课一 线性结构 push inti intx if A printf overflow return if i 1 top1 v top1 x elseif i 2 B intpop inti inty if i 1 if top1 M printf underflow else D return y 习题课一 线性结构 inttop inti inty if i 1 if E y v top1 return y elseprintf nodata elseif i 2 if top2 M y v top2 return y elseprintf nodata 习题课一 线性结构 答案 A top1 top2 1B top2 V top2 x C y V top1 top1 D y V top2 top2 E top1 0 习题课一 线性结构 引发 队列和栈 1 两个相向栈的入栈 出栈 2 两个背向栈的入栈 出栈 3 链栈的入栈 出栈 4 队列的入队 出队 5 其他受限制的表的插入 删除操作 上机实习二 线性结构 例3 本程序是用堆栈来模拟行编辑器的工作 它将键入的字符都送入堆栈暂存 当收到 1 回车 Enter 时 便把堆栈内的字符 包括 回车 再加上 换行 作为一条语句送入文件之中 2 如键入的是 则把堆栈内的语句全部删除 3 如键入的是 则删除最近键入的一个字符 4 如键入的是 则关闭文件 退出行编辑器 终止程序的运行 习题课一 线性结构 include defineM80inti a M voidpop if i 0 A voidclean B 习题课一 线性结构 voidpush charch FILE fp intj a i ch i if ch r a i n for C putc a j fp i 0 main FILE fp charch fp fopen file txt w printf Pleaseinputsentences n i 0 ch while D ch getch