2024西藏自治区数据要领加强

1、若第 n 件物品能放入背包，则问题变为能否再从 n-1 件物品中选出若干件放入背包（这时背包可放入物品的重量变为 s-w[n]）。若第 n 件物品不能放入背包，则考虑从 n-1 件物品选若干件放入背包（这时背包可放入物品仍为 s）。若最终 s=0,则有一解；否则，若s<0 或虽然 s>0 但物品数 n<1,则无解。（1）s-w[n],n-1 //Knap(s-w[n],n-1)=true（2）s,n-1 // Knap←Knap(s,n-1)2、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。当 n=1 时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。设当 n=m-1 时结论成立，现证明当 n=m 时结论成立。设中序序列为 S1，S2，…，Sm,后序序列是 P1,P2,…，Pm。因后序序列最后一个元素Pm 是 根 ， 则 在 中 序 序 列 中 可 找 到 与 Pm 相 等 的 结 点 （ 设 二 叉 树 中 各 结 点 互 不 相同）Si(1≤i≤m)，因中序序列是由中序遍历而得，所以 Si 是根结点，S1，S2，…，Si-1是左子树的中序序列，而 Si+1,Si+2,…,Sm 是右子树的中序序列。若 i=1，则 S1 是根，这时二叉树的左子树为空，右子树的结点数是 m-1,则{S2，S3，…，Sm}和{P1，P2，…，Pm-1}可以唯一确定右子树，从而也确定了二叉树。若 i=m,则 Sm 是根，这时二叉树的右子树为空，左子树的结点数是 m-1，则{S1，S2，…，Sm-1}和{P1，P2，…，Pm-1}唯一确定左子树，从而也确定了二叉树。最后，当 1typedef char datatype;typedef struct node{ datatype data; struct node * next;} listnode;typedef listnode* linklist;/*--------------------------------------------*//* 删除单链表中重复的结点 *//*--------------------------------------------*/l...