2022年数据结构算法设计期末复习题文 .pdf
二、算法设计1、设计一个算法，通过一趟遍历在单链表中确定值最大的结点。ElemType Max (LinkList L ) if(L-next=NULL) return NULL; pmax=L-next; / 假定第一个结点中数据具有最大值p=L-next-next; while(p != NULL )/如果下一个结点存在if(p-data pmax-data) pmax=p; p=p-next; return pmax-data; 2、设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。void inverse(LinkList &L) / 逆置带头结点的单链表L p=L-next; L-next=NULL; while ( p) q=p-next; / q 指向 *p 的后继p-next=L-next; L-next=p; / *p 插入在头结点之后p = q; 3、 设计一个算法， 删除递增有序链表中值大于mink 且小于 maxk 的所有元素 （mink 和 maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同）。void delete(LinkList &L, int mink, int maxk) p=L-next; / 首元结点while (p & p-datanext; / 查找第一个值 mink 的结点if (p) while (p & p-datanext; / 查找第一个值maxk 的结点q=pre-next; pre-next=p; / 修改指针while (q!=p) s=q-next; delete q; q=s; / 释放结点空间 /if 4、假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s 为指向链表中某个结点的指针，试编写算法在链表中删除指针s 所指结点的前驱结点。typedef struct LNode ElemType data; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - struct LNode *next; LNode, *LinkList; ElemType DeleteNode(LinkList s) /* 删除指针s所指结点的前驱结点，并返回被删结点的元素值*/ LinkList p; p=s-next; while(p-next-next!=s) p=p-next; ElemType e=p-next-data; p-next=s; return e; 5、已知长度为n 的线性表A 采用顺序存储结构，请写一时间复杂度为0(n)、空间复杂度为0(1)的算法，该算法删除线性表中所有值为item 的数据元素。void DeleteItem(SeqList *L,ElemType item) int i=0,j=L-last; while(ij) while(ielemi!=item) i+; while(ielemi=item) j-; if(ielemi=L-elemj; i+; j-; L-last=i-1; 6、写一个算法，求出循环链表结点的个数。（不包括头结点）int count(Linklist head) int n=0; ListNode.p=head-next; while(p!=head) n+;P=P-next; return n; 7、写一算法在单链表上实现线性表的ListLength(L) 运算。int ListLength ( LinkList L ) int len=0 ; ListNode *p; p=L; / 设该表有头结点while ( p-next ) p=p-next; len+; return len; 8、试写一算法计算二叉树的深度（高度）。int Height(btre bt)/ 求二叉树bt 的深度int hl,hr; if(bt=null) return(0); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - else hI=Height(bt-lch); hr=Height(bt-rch); if(hlhr) return (hl+1); else return(hr+1); 9、试写一算法统计用二叉链表表示的二叉树叶子结点总数。int leaf ( BinTreeNode * ptr ) if ( ptr = NULL ) return 0; else if ( ptr-leftChild = NULL & ptr-rightChild = NULL ) return 1; else return leaf ( ptr-leftChild ) + leaf ( ptr-rightChild ); 10、已知二叉树的定义如下：typedef struct node int data; struct node *lchild, *rchild; *bitree ；试分别写出二叉树的后根遍历和中根遍历的递归算法。后int visit (bitree T) if(T=null) return 0; visit (T-lchirld); visit (T-rchirld); printf(“ %d ” ,data); 中int visit (bitree T) if(T=null) return 0; visit (T-lchirld); printf(“ %d ” ,data);visit (T-rchirld); 11、已知二叉树的定义如下：typedef struct node int data; struct node *lchild, *rchild; *bitree ；编写二叉树先序遍历的递归算法。先int visit (bitree T) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - if(T=null) return 0; printf(“ %d ” ,data);visit (T-lchirld); visit (T-rchirld); 12、要求二叉树按二叉链表形式存储，写一个建立二叉树的算法。BiTree Creat() /建立二叉树的二叉链表形式的存储结构ElemType x;BiTree bt; scanf(“%d”,&x); /本题假定结点数据域为整型if(x=0) bt=null; else if(x0) bt=(BiNode *)malloc(sizeof(BiNode); bt-data=x; bt-lchild=creat(); bt-rchild=creat(); else error(“输入错误”); return(bt); / 结束BiTree 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -
