数据结构和算法作业.pptx

文档介绍：作业 1
计算下列各片断程序中@语句的执行次数及其大O形式:
(1) for i=1 to n
for j=1 to i
for k=1 to j
@ x=x+1
end
end
end
(2) for i=1 to n
j=1
for k=j+1 to n
***@x=x+1
end
end
(3) i=1;
while (i<100)
@ x=x+1
i=i+1
end
(4) i=1
while (i<=n)
@ x=x+1
i=2*i
end
(5) x=91 ; y=100 ;
while (y>0) {
@ if (x>100) {x - = 10 ; y--}
else x++ ;
}
2. 设数据元素的集合为D={d1, d2, d3, d4, d5},试指出下列关系R所对应的数据结构B=(D,R)中哪些是线性结构,哪些是非线性结构。
(1) R={(d1,d2), (d2,d4),(d4,d2),(d2,d5),(d4,d1)}
(2) R={(di, di+1)|i=4,3,2,1}
(3) R={(di, dj)|j=(5i2+4i+1}
3. 为一个课题组定义一个数据结构。每组一位教师,1~3名研究生,1~6名本科生,关系是教师指导研究生,每名研究生指导1~2名本科生,画出该数据结构的逻辑结构图。
:
2100, (3/2)n, (4/3)n, nn, n3/2, n2/3, n1/2, n!, n, log2n, n/log2n, log22n, log2(log2n), nlog2n, nlog2n
作业 2
已知线性表L(x1, x2,…,xn)各元素按递增有序排列,用向量方式做存储结构。试编写算法,删除表中值分布在c与d(c<d)之间的元素
编写一算法,将向量L(x1, x2,…,xn)倒置
试编写算法,求已知单链表的长度,并考虑表空情况
已知一循环链表中各数值已按递增有序排列,现要求插入一结点后,链表仍有序
缩写单链表倒置算法
在双向链表的值为a、b的两个结点之间插入值为x的结点
7. 简述以下算法的功能:
Sample(head) //head是无表头结点的单链表
{
if(head && next(head)){
q<-head; head<-next(head); p<-head;
while(next(p)) p<-next(p);
next(p)<-q; next(q)<-nil;
}
return;
}
作业 3
Q[0:10]为循环队列,初态front=rear=1,画出下列操作后,队的头、尾指示器状态:
d,e,b,g,h入队;
d, e出队;
i,j,k,l,m入队;
b出队;
n,o,p,q,r入队
2. 试画出表达式:A*(B-C)+D**(E/F)执行过程中NS,OS栈的变化情况,并给出相应的后缀表达式结果
3. 设置一个单元,作为队满或队空的标志,写出循环队列插入和删除的算法d,e,b,g,h入队;
,经一次退压栈能否得到如下序列,若不能,则经过两次退压栈能否得到?
I: CBEFDA II: AEDFBC
1. 设一个二维数组A[1:m; 1:n],假设A[3,2]地址为1110,A[2,3]地址为1115,若每个单元占一个空间,求A[1,4]的地址。
2. 采用三元组和带行辅助向量形式,表示下列稀疏矩阵:
作业 4