文档介绍：作业 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={( d i , d i+1 )| i =4,3,2,1 } (3) R={( d i , d j )| j=(5i 2 +4i+1 } 3. 为一个课题组定义一个数据结构。每组一位教师, 1~3名研究生, 1~6名本科生,关系是教师指导研究生,每名研究生指导 1~2名本科生,画出该数据结构的逻辑结构图。 : 2 100 , (3/2) n , (4/3) n, n n, n 3/2, n 2/3, n 1/2 , n!, n, log 2 n, n/log 2n, log 2 2 n, log 2 (log 2 n), nlog 2n, n log2n 作业 2 L(x 1 , x 2,…,x n)各元素按递增有序排列,用向量方式做存储结构。试编写算法,删除表中值分布在 c与 d(c<d) 之间的元素 ,将向量 L(x 1 , x 2,…,x n)倒置 ,求已知单链表的长度,并考虑表空情况 ,现要求插入一结点后,链表仍有序 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 [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 入队; ABCDEF ,经一次退压栈能否得到如下序列,若不能,则经过两次退压栈能否得到? I: CBEFDA II: AEDFBC 1. 设一个二维数组 A[1: m; 1: n],假设 A[3 , 2] 地址为 1110 , A[2 , 3]地址为 1115 ,若每个单元占一个空间,求 A[1,4] 的地址。 2. 采用三元组和带行辅助向量形式,表示下列稀疏矩阵: ????????????????????00028 00 0000091 000000 006000 0003 11 0 15 022 0015??????????????????????????????? 30 0000200 12 000000007 000004000 000000020 000000