吉大数据结构12002.docVIP

吉林大学2002 1、[20分] 设N1，N2，……，Nk是一个整数序列，若满足条件 N1≤N2≤……≤Nk-1，1≤k 则称上述序列为准递增有序。这时若把Nk插入到N1，N2，……，Nk-1中，使得插入后所得的序列N1′， N2′，……，NK′仍然保持递增性，则我们称这种插入为保序插入。试写出一个函数（或过程）insert，使得它只要给出一个准递增序列和其长度，则将对其进行保序插入，并返回保序插入后的新序列。在写程序时，要求把insert写成递归的形式。 2、[20分] 假设有整数序列N1，N2，……，Nn，则我们称其中的子序列Ni，Ni+1，……，Nj为上述序列的递增子序列，如果有Nk≤Nk+1，其中i≤kj。试写一个函数MaxLeng，使得它对任给的整数序列，返回一个整数，它表示给定序列的最长递增子序列的长度。例如，假设有（7，2，3，4，2，2，5）则其最长递增子序列的长度是3。在函数MaxLeng中，要求序列中的每个元素不能被扫描一次以上。 3、[20分] 假设用链表表示集合。例如集合{1，3，4}可表示为下列链表： Q 要求写一个函数SetAdd，它有两个参数P和Q，它们分别指向两个链表（表示集合，每个没有相同元素），执行函数调用SetAdd（P，Q）后将返回链表R。R是表示P集合加Q集合所得集合的链表（集合加即集合并）。例如，再有P链表为： P 则执行SetAdd（P，Q），结果应返回下面链表： R 4、[20分] 假设用链表表示八进制数，如八进制数536被表示为下面链表： Q 要求写一个函数Add，它有两个参数P和Q ，分别指向表示八进制数的链表。执行函数调用Add（P，Q）后，将返回表示P八进制数加Q八进制数所得数的链表R。例如，假设再有P链表： P 则执行Add（P，Q），结果应返回下面链表： R 5、假设有某种语言的函数定义 function f（x：real；y：real）:real begin L：S1； S2； x←x+1.5； y←y+x； if y≤100 then goto L return（sin（y）） end 其中表示赋值操作，S1和S2表示语句，其中没对x和y的赋值，也不含goto语句。要求把函数f的定义改写成递归函数的形式。函数f有两个实型形参，计算结果是返回一个实数，即返回sin（y）的值。 1 3 4 3 5 1 4 3 1 5 6 3 5 3 4 2 7 0 0 0 1 1