线性结构部分习题

数据结构线性结构部分习题

数据结构与算法 For 软件学院10级本科生 2011-2012秋

线性结构 习题

数据结构线性结构部分习题

本节重点 复习要点 单项选择题 综合应用题

2/32

数据结构线性结构部分习题

线性表-复习要点(1) 1.线性表的概念– 线性表的定义和特点 – 线性表的基本操作

2.线性表的存储表示– 顺序表的定义及基本运算的实现 – 单链表的定义及基本运算的实现

3.线性表的特殊链接表示– 循环链表的特殊遍历方式 – 双向链表的方向性3/32

数据结构线性结构部分习题

线性表-复习要点(2) 4.线性表的应用(1)– 在一维数组上的算法，如原地逆置、非零元 素压缩、成块元素移动等。 – 在一维数组上的递归算法，如求和平均值等。 – 在顺序表上的查找、插入、删除、合并、求 交等算法及性能分析。– 在单链表上的迭代求解算法及性能，包括统 计链表结点个数、在链表中寻找与给定值 x 匹配的结点、在链表中寻找第i个结点、链表 逆转等。4/32

数据结构线性结构部分习题

线性表-复习要点(3) 4.线性表的应用(2)– 带表头结点的单链表上的迭代算法，包括统计链表 结点个数、在链表中寻找与给定值x匹配的结点、在 链表中寻找第i个结点、两个有序链表的合并等。 – 单链表的递归算法，包括统计链表结点个数、在链 表中寻找与给定值 x匹配的结点、在链表中寻找第 i 个结点、求链表各结点值的和、平均值等。 – 循环链表的迭代算法、双向链表的迭代算法。

5.多项式的建立，两个多项式的相加，两个多 项式的相乘算法5/32

数据结构线性结构部分习题

单项选择题

6/32

数据结构线性结构部分习题

单项选择题

7/32

数据结构线性结构部分习题

单项选择题

8/32

数据结构线性结构部分习题

单项选择题

9/32

数据结构线性结构部分习题

单项选择题

10/32

数据结构线性结构部分习题

单项选择题例 11 若在长度为 n 的顺序表的表尾插入一个新元素的渐 进时间复杂度是( )。 A.O(n) B.O(1) C.O(n2) D.O(log2n)

【解答】B。在有n个元素的顺序表的表尾插入一个 新元素，可直接在表的第n+1个位置插入，渐进时间 复杂度为O(1)。

11/32

数据结构线性结构部分习题

综合应用题

此题还有其他做法

12/32

数据结构线性结构部分习题

复习要点(1) 1.栈的定义及特点 – 栈的定义、栈顶与栈底概念 – 栈的基本运算，包括进栈、出栈、判空栈、置空栈等 2.栈的存储表示 – 顺序栈的实现及基本操作 – 链式栈的实现及基本操作 3.队列的定义及特点 – 队列的定义、先进先出特点 – 队列的基本运算，包括进队、出队、判队空、置空队

13/32

数据结构线性结构部分习题

复习要点(2) 4.队列的存储表示 – 队列的顺序存储及基本操作 – 队列的链式存储及基本操作 5.栈的应用– 栈在递归过程中作为工作栈的使用，栈在表达式计 算中从中缀表示转后缀表示，栈在括号配对中的应 用，栈在数制转换中的应用

– 双栈共用一个数组的进栈、退栈、置空栈算法及栈 满、栈空条件，使用两个

栈模拟一个队列时的进队 列和出队列算法。14/32

数据结构线性结构部分习题

复习要点(3) 6.队列的应用 – 队列在分层处理中的使用，包括二叉树、树、图等 层次遍历过程中的使用– 队列在对数据循环处理过程中的使用，例如约瑟夫 问题、归并排序 – 队列在调度算法中的使用

15/32

数据结构线性结构部分习题

单项选择题 例1 为解决计算机主机与打印机之间速度不匹配的问 题，通常设置一个打印数据缓冲区。主机将要打印输 出的数据依次写入缓冲区，而打印机则依次从该缓冲 区中取出数据，该缓冲区的逻辑结构应该是( )。 A、栈 B、队列 C、树 D、图【解答】 B。通常用于输入输出的缓冲区都是采用先入先出的队 列。

16/32