数据结构作业.doc
文本预览下载声明
注意：作业，大家一定要独立完成！！！
第1章作业
P.8
1.8 设n为正整数.试确定下列各程序段中前置以记号@的语句的频度:
(1) i=1;k=0; (2) i=1;k=0;
While(i=n-1){ do{
@ k+=10*i; @ k+=10*i;
i++; i++;
} } While(i=n-1);
(3) i=1;k=0; (4) k=0;
While(i=n-1){ for( i=1;i=n;i++){
i++; for(j=i;j=n;j++)
@ k+=10*i; @ k++;
} }
(5) for( i=1;i=n;i++){ (6) i=1;j=0;
for(j=1;j=i;j++){ While(i+j=n){
for(k=1;k=j;k++) @ if(ij) j++;
@ x+=delta; else i++;
} }
(7) x=n;y=0; //n是不小于1的常数 (8)x=91;y=100;
While(x=(y+1)*(y+1)){ while(y0){
@y++; @ if(x100){x-=10;y--}
} else x++;
}
第2章作业
顺序表部分作业
2.11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
2.21 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1,a2,…,an)逆置为(an,an-1,…,a1)。
链表部分作业
2.14试写一算法在带头结点的单链表结构上实现线性表操作LENGTH(L)
2.19 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间（注意：mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。
第3章作业
p.24
3.15 假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈。它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化inistack（tws）、入栈push（tws,i,x）和出栈pop（tws,i）的算法，其中i为0或1，用以分别指示设在数组两端的两个栈。
3.28 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。
第4章作业
p.28
4.8 已知主串s=’ADBADABBAABADABBADADA’
模式串pat=’ADABBADADA’
写出模式串的nextval函数值，并由此画出KMP算法匹配的全过程。
第6章作业
6.5 已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，…… nk个度为k的结点，问该树中有多少个叶子结点？
6.7 一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各为多少？
6.15 请对下图所
显示全部