2.14 已知一循环链表中数值已按递增有序排列现要插入一个新结点，并使插入一个新节点，并使插入后链表仍为有序序列 GETNODE(p) Data(p)=a
While(data(p) next(p) <--next(q)<-p return 2.18 设在长度大于1 的循环链表中，即无头结点，也无头指正，p为指向链表中每个节点的指针，试编写算法删除该节点的前趋结点。 q<-Next(p)//找到该节点的前趋结点 p<-next(q);next(q)<-next(p) RET(p) Return 2.20试用单链表表示两个多项式；A=4x12+5x8+6x3+4，B=3x12+6x7+2x4+5 (1) 设计此两个多项式的数据结构。 (2) 写出两个多项式相加的算法。 (3) 分析算法的时间、空间复杂度。 ADD-POLY(ha ,hb ) 1. p←next(ha); q←next(hb) 2. pre←ha;hc←ha //pre指向p的前趋，为c(x)头指针// 3.while (p<>nil) AND (q<>nil) do 4.case 5.EXP(p) 9.if (x<>0) then {COEF(p)←x;pre←p} 10.else {next(pre)←next(p); RET(p)} 11.p←next(pre);u←q;q←next(q);RET(u)} 12.EXP(p)>EXP(q): 13.{u←next(q);next(q)←p; next(pre)←q;pre←q;q←u} 14.end(case) 15.end(while) 16.if(q<>nil) then next(pre)←q 17.RET(hb)//释放多项式B(x)的头结点// 18.return 2.22 CQ[0:10]为一循环队列，初态 front=rear=1，画出下列操作后队的头，尾指示器状态： (1)d,e,b,g,h入队；rear=6 front=1 (2)d，e出队 rear=6 front=3 (3)I,j,k,l,m入队 rear=0 front=3 (4)b出队 rear=0 front=4 (5)n,o,p,q,r入队 rear=5 front=4 2.22 CQ[0：10]为一循环队列，初态front=rear=1，画出下列操作后队的头、尾指示器状态： (1) d,e,b,g,h入队；(2) d,e出队；(3) i,j,k,l,m,入队；(4) b出队； (5) n,o,p,q,r入队。 2.23试画出表达式A*(B-D)/C**(E*F)执行过程中NS，OS栈的变化情况。 2.24用一长度为m的数组存放一双向栈，两个栈顶分别为top1和top2,如图所示。上溢条件为top1=top2,从键盘输入一串整数，奇数入stack1，偶数如stack2，直到上溢时停止输入。试编写一算法实现此过程。 O_E(R,m,top1,top2,x) 1. top1←m;top2←1 //top1,top2置初值 2. if (top1=top2) then {‘上溢’,return} 3. while (top1<>top2) do 4. if (x mod 2=0) then {R[top2]←x;top2←top2+1} 5. else { R[top1]←x;top1←top1+1} 6.end(while) 7.retun 2.25 有一个二维数组A[1:m ;1:n],假设A[3,2]地址为1110，A[2，3]地址为1115， 若每个单元占一个空间，问A[1,4]的地址是多少 答案：1120 2.26用三元组和带行辅助向量形式表示下列的稀疏矩阵： 2.28将题图2.3的一般树化为二叉树。 答案： 2.29 设一颗完全二叉数有1000个结点，试问： (1)有多少个叶子结点 500 (2)有多少个度为2的结点 499 (3) 有多少个结点只有非空左子树 1 2.30 设一颗二叉树其中序和后序遍历为 中序：BDCEAFHG 后序：DECBHGFA 答案：ABCDEFHG 2．31.对二叉树写出如下算法： (1)复制一棵二叉树； (2)判断两棵二叉树是否相等； (3)计算二叉树的树叶； (4)计算二叉树的深度； 解： 1）//复制一棵二叉树 /*算法思想 采用递规函数来实现 （1）如果树为空，则复制一棵空树； （2）如果树不为空，则依次递规复制已知二叉树的左子树和有子树； （3）生成一个新的根结点，使复制得到的左子树和右子树的根指针分别成为这个新生成结点的左指针域和右指针域的值。 算法编写： */ BiTree *CopyTree(BiTree *T){ // if(!T) return NULL; if(T->lchild) newlchild=CopyTree(T->lchild);// else newlchild=NULL;// if(T->rchild) newrchild=CopyTree(T->rchild);// else newrchild=NULL;// newnode=GetTreeNode(T->data,newlchild,newrchild); // return newnode; }//CopyTree BiTNode *GetTreeNode(TelemType item,BiTNode *lptr,BiTNode *rptr){
计算机软件技术基础(第三版)沈被娜 课后习题答案较全
