数据结构作业.doc

注意:作业,大家一定要独立完成!!! 第1 章作业 设n 为正整数. 试确定下列各程序段中前置以记号@ 的语句的频度: (1) i=1;k=0; (2) i=1;k=0; W hile(i<=n-1){ do{ @ k+=10*i; @ k+=10*i; i++; i++; }}W hile(i<=n-1); (3) i=1;k=0; (4) k=0; W hile(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++){ W hile(i+j<=n){ for(k=1;k<=j;k++) @ if(i>j) j++; @ x+=delta; else i++; }} (7) x=n;y=0; //n 是不小于 1 的常数(8)x=91;y=100; W hile(x>=(y+1)*(y+1)){ while(y>0){ ***@y++; @ if(x>100){x-=10;y--} } else x++; } 第2 章作业顺序表部分作业 设顺序表 va 中的数据元素递增有序。试写一算法,将 x 插入到顺序表的适当位置上,以保持该表的有序性。 试写一算法, 实现顺序表的就地逆置, 即利用原表的存储空间将线性表(a 1 ,a 2,…,a n) 逆置为(a n ,a n-1,…,a 1)。链表部分作业 试写一算法在带头结点的单链表结构上实现线性表操作 LENGTH(L) 已知线性表中的元素以值递增有序排列, 并以单链表作存储结构。试写一高效的算法,删除表中所有值大于 mink 且小于 maxk 的元素( 若表中存在这样的元素), 同时释放被删结点空间( 注意: min k 和 maxk 是给定的两个参变量,它们的值可以和表中的元素相同,也可以不同)。第3 章作业 假设以顺序存储结构实现一个双向栈,即在一维数组的存储空间中存在着两个栈。它们的栈底分别设在数组的两个端点。试编写实现这个双向栈 tws 的三个操作: 初始化 inistack ( tws ) 、入栈 push ( tws,i,x )和出栈 pop ( tws,i )的算法,其中 i为0或1 ,用以分别指示设在数组两端的两个栈。 假设以带头结点的循环链表表示队列, 并且只设一个指针指向队尾元素结点( 注意不设头指针) ,试编写相应的队列初始化、入队列和出队列的算法。第4 章作业 已知主串 s=’ ADBADABBAABADABBADADA ’模式串 pat= ’ ADABBADADA ’写出模式串的 nextval 函数值, 并由此画出 KMP 算法匹配的全过程。第6 章作业 已知一棵度为 k的树中有 n 1个度为 1的结点,n 2个度为 2的结点,…… n k 个度为 k的结点,问该树中有多少个叶子结点? 一棵含有 n个结点的 k叉树,可能达到的最大深度和最小深度各为多少? 请对下图所示二叉树进行后序线索化,为每个空指针建立相应的前驱或后继线索。 AB CEDG FH