数据结构与算法（严蔚敏）.ppt

第2章 线性表 2.1.2 线性表的逻辑结构 2.1.3 线性表的抽象数据类型定义 2.5 一元多项式的表示和相加 1 一元多项式的表示 一元多项式 p(x)=p0+p1x+p2x2+ … +pnxn ，由n+1个系数唯一确定。则在计算机中可用线性表(p0 ，p1 ，p2 ，… ，pn )表示。既然是线性表，就可以用顺序表和链表来实现。两种不同实现方式的元素类型定义如下： 习 题 二 1 简述下列术语：线性表，顺序表，链表。 2 何时选用顺序表，何时选用链表作为线性表的存储结构合适?各自的主要优缺点是什么? 3 在顺序表中插入和删除一个结点平均需要移动多少个结点?具体的移动次数取决于哪两个因素? 4 链表所表示的元素是否有序?如有序，则有序性体现于何处?链表所表示的元素是否一定要在物理上是相邻的?有序表的有序性又如何理解? 5 设顺序表L是递增有序表，试写一算法，将x插入到L中并使L仍是递增有序表。 6 写一求单链表的结点数目ListLength(L)的算法。 7 写一算法将单链表中值重复的结点删除，使所得的结果链表中所有结点的值均不相同。 8 写一算法从一给定的向量A删除值在x到y(x≤y)之间的所有元素(注意：x和y是给定的参数，可以和表中的元素相同，也可以不同)。 9 设A和B是两个按元素值递增有序的单链表，写一算法将A和B归并为按按元素值递减有序的单链表C，试分析算法的时间复杂度。 第3章 栈和队列 习 题 三 1 设有一个栈，元素进栈的次序为a, b, c。问经过栈操作后可以得到哪些输出序列？ 2 循环队列的优点是什么?如何判断它的空和满? 3 设有一个静态顺序队列，向量大小为MAX，判断队列为空的条件是什么？队列满的条件是什么？ 4 设有一个静态循环队列，向量大小为MAX，判断队列为空的条件是什么？队列满的条件是什么？ 5 利用栈的基本操作，写一个返回栈S中结点个数的算法int StackSize(SeqStack S) ，并说明S为何不作为指针参数的算法? 6 一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。试为此双向栈设计初始化InitStack(S) ，入栈Push(S,i,x)，出栈Pop(S,i,x)算法，其中i为0或1 ，用以表示栈号。 7 设Q[0,6]是一个静态顺序队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入对，请指出其元素，并说明理由。 a, b, c, d入队 a, b, c出队 i , j , k , l , m入队 d, i出队 n, o, p, q, r入队 8 假设Q[0,5]是一个循环队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入对，请指出其元素，并说明理由。 d, e, b, g, h入队 d, e出队 i , j , k , l , m入队 b出队 n, o, p, q, r入队 第4章 串 习 题 四 ⑴ 解释下列每对术语的区别：空串和空白串；主串和子串；目标串和模式串。 ⑵ 若x和y是两个采用顺序结构存储的串，写一算法比较这两个字符串是否相等。 ⑶ 写一算法void StrRelace(char *T, char *P, char *S)，将T中第一次出现的与P相等的子串替换为S，串S和P的长度不一定相等，并分析时间复杂度。 第5章 数组和广义表 数组是一种人们非常熟悉的数据结构，几乎所有的程序设计语言都支持这种数据结构或将这种数据结构设定为语言的固有类型。数组这种数据结构可以看成是线性表的推广。 科学计算中涉及到大量的矩阵问题，在程序设计语言中一般都采用数组来存储，被描述成一个二维数组。但当矩阵规模很大且具有特殊结构(对角矩阵、三角矩阵、对称矩阵、稀疏矩阵等)，为减少程序的时间和空间需求，采用自定义的描述方式。 广义表是另一种推广形式的线性表，是一种灵活的数据结构，在许多方面有广泛的应用。 习 题 五 ⑴ 什么是广义表？请简述广义表与线性表的区别？ ⑵ 一个广义表是(a, (a, b), d, e, (a, (i, j), k)) ，请画出该广义表的链式存储结构。 ⑶ 设有二维数组a[6][8]，每个元素占相邻的4个字节，存储器按字节编址，已知a的起始地址是1000，试计算： ① 数组a的最后一个元素a[5][7]起始地址； ② 按行序优先时，元素a[4][6]起始地址； ③ 按行序优先时，元素a[4][6]起始地址。 ⑷ 设A和B是稀疏矩阵，都以三元组作为存储结构，请写出矩阵相加的算法，其结果存放