文档介绍：数据结构与算法作业
习题 1
1. 简述下列术语:
数据数据元素数据结构存储结构数据类型抽象数据类型
,左侧是算法的执行时间,右侧是一些时间复杂度。请用连线的方式表示每个算法的时间复杂度。
(1)
(2)
(3)
(4)
(5)
(6) (a) O(1) (b) O(2n) (c) O(n) (d) O(n2) (e) O(log2n) (f) O(n3) 100n3 6n2-12n+1 1024 n+2log2n n(n+1)(n+2)/6 2n+1+100n
3. 试编写算法,求一元多项式Pn(x)=?axi
i?0ni的值Pn(x0),并确定算法中每一语句的执行次
数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法,本题输入为ai(i=0,1,…,n),x0和n,输出为Pn(x0)。
习题 2
1. 填空题:
a) 在顺序表中插入和删除一个元素,需要平均移动的元素个数与
插入或删除元素的位置有关。
b) 顺序表中逻辑上相邻的元素的物理位置紧邻。单链表中逻辑上相邻
的元素的物理位置不要求紧邻。
c) 在单链表中,除了首结点外,任一结点的存储位置由指
示。
d) 在单链表中设置头结点的作用是针。
2. 已知顺序线性表A和B中各存放一个英语单词,字母均为小写。试编写一个判定那个
单词在字典中排在前面的算法。
3. 试写一算法,实现顺序表的就地逆置,即利用原表的存储空间将线性表(a1,a2,…, an)
逆置为(an,an-1,…,a1)。
4. 已知指针ha和hb分别指向两个单链表的头结点,并且已知两个链表的长度分别为m
和n。试写一算法将这两个链表连接在一起(即令其中一个表的首元结点连在另一个表的最后一个结点之后),假设指针hc指向连接后的链表的头结点,并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。
5. 设线性表A=( a1,a2,…, am),B=( b1,b2,…, bn),试写一个按下列规则合并A、B为
线性表C的算法,即使得
C=( a1,b1,a2, b2,…, am,bm,bm+1,…, bn) 当 m≤n时;
C=( a1,b1,a2, b2,…, an,bn,an+1,…, am) 当n≤m时.
线性表A、B和C均以单链表作存储结构,且C表利用A表和B表中的结点空间构成。注意:单链表的长度值m和n均未显式存储。
注意: 2-5题完成后在上机实习时,通过程序实现检验算法的正确性(至少上机检验算法2)
习题 3
1. (b)所示铁道进行车厢调度(注意:两侧铁道均为单向行驶
道),则请问:
(1) 如果进站的车厢序列为123,则可能得到的出站车厢序列是什么?
(2) 如果进站的车厢序列为123456,则能否得到435612和135426的出站序列,并说
明为什么(即写出以‘S’表示进栈和以‘X’表示出栈的栈操作序列)。
2. 试写一个判别表达式中开、闭括号是否合法匹配的算法。
3. 按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例,()
例3-1的格式,画出下列算