2022年数据结构期中测试算法填空 .pdf

《2022年数据结构期中测试算法填空 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构期中测试算法填空 .pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1、两个集合 A 和 B 的并集，集合 A、B 分别用线性表 LA、LB 表示。要求：AAB。注：并集，属于 A 或者属于 B)思路：1从线性表 LB 中依次取得每个数据元素;GetElem(LB,i)e2依值在线性表 LA 中进行查访;LocateElem(LA,e,equal()3.若不存在，则插入之。ListInsert(LA,n+1,e)void union(List&LA,List LB)/将所有在线性表Lb 中但不在 La 中的数据元素插入到La 中LA_len=ListLength(LA);LB_len=ListLength(LB);/求线性表的长度for(i=1;i=LB_le

2、n;i+)GetElem(LB,i,e);/取 Lb 中第 i 个数据元素赋给 e if(!LocateElem(LA,e,equal()ListInsert(LA,+LA_len,e);/La 中不存在和e 相同的数据元素，则插入之 /union 2、线性表的初始化Status InitList_Sq(SqList&L)、/构造一个空的线性表L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);/存储分配失败L.length=0;/空表长度为 0 L.listsize=LIST_I

3、NIT_SIZE;/初始存储容量return OK;/InitList_Sq 3、从线性表中查找具有给定值的第一个元素：int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)/在顺序线性表 L 中查找第 1 个值与 e满足 compare()的/元素的位序。若找到，则返回其在L 中的位序，否则返回0。i=1;/i 的初值为第 1 元素的位序p=L.elem;/p 的初值为第 1 元素的存储位置while(i=L.length&L.elemi-1!=e)+i;if(i=L.length)return i;

4、else 名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 9 页 -return 0;/LocateElem_Sq此算法的时间复杂度为:O(ListLength(L)4、在线性表中指定位置前插入一个元素算法思想：1）不合法：插入位置：检查i 值是否超出所允许的范围（1in+1），若超出，则进行“超出范围”错误处理；存储空间满2）将线性表的第i 个元素和它后面的所有元素均向后移动一个位置；3）将新元素写入到空出的第i 个位置上；4）使线性表的长度增1。Status ListInsert_Sq(SqList&L,int i,ElemType e)/在顺序线性表 L 的第 i 个元素之

5、前插入新的元素e/i 的合法值为 1iListlength_Sq(L)+1 if(i L.length+1)return ERROR;/插入位置不合法if(L.length=L.listsize)/当前存储空间已满，增加分配newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);/存储分配失败L.elem=newbase;/新基址L.listsize+=LISTINCREMENT;/增加存储容量 for(int j=L.length-1;j=

6、i-1;j-)L.elemj+1=L.elemj L.elemi-1=e;/元素下标法+length;return ok;插入算法的时间复杂度为:O(ListLength(L)5、在线性表中删除第i 个元素算法思想：1）检查 i 值是否超出所允许的范围（1in），若超出，则进行“超出范围”错误处理；2）将线性表的第i 个元素后面的所有元素均向前移动一个位置；3）使线性表的长度减1。Status ListDelete_Sq(SqList&L,int i,ElemType&e)名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 9 页 -/在顺序线性表 L 中删除第 i 个元素，并用 e

7、返回其值。/i 的合法值为 1iListLength_Sq(L)if(i L.length)return ERROR;/删除位置不合法e=L.elemi-1;for(int j=i-1;j S.stacksize)/如果栈满，则追加存储空间S.base=(SElemType*)realloc(S.base,(S.stacksixe+STACKINCREMENT*sizeof(SElemType);if(!S.base)exit(OVERFLOW);/追加存储空间失败S.top=S.base+S.stacksize;/修改栈顶指针S.stacksize+=STACKINCREMENT;/修改当前

8、栈的存储空间*S.top=e;+S.top;/先将 e 送入栈顶，然后将栈顶指针加1 return OK;/Push 8、顺序栈出栈算法Status Pop(SqStack&S,SElemType&e)/如果栈 S 空，返回 ERROR；如果栈 S 不空，删除S 栈顶元素，用e返回其值，并返回OK。if(S.top=S.base)return ERROR;/如果栈S 为空，则返回ERROR-S.top;e=*(S.top);/先令 top 减 1，再将 top 所指单元值赋给ereturn OK;/Pop 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 9 页 -9、入队在循环队

9、列尾插入新元素算法Status EnQueue(SqQueue&Q;QElemType e)/若队列满，则返回ERROR；若队列不满，则插入元素e 为队列Q 新的队尾元素。if(Q.rear+1)%MAXQSIZE=Q.front)return ERROR/如果循环队列满，则出错Q.base Q.rear =e;/将 e 插入到循环队列尾Q.rear=(Q.rear+1)%MAXQSIZE;/修改队尾指针return OK;/EnQueue 10、出队在循环队列头删除元素算法Status DeQueue(SqQueue&Q,QElemType&e)/若队列空，则返回ERROR；若队列不空，则删

10、除Q 的队列头元素，用e 返回其值，并返回OK。if(Q.front=Q.rear)return ERROR;/如果循环队列空，则出错e=Q.base Q.front;/将循环队列头的元素取出Q.front=(Q.front+1)%MAXQSIZE;/修改队头指针return OK;/DeQueue 11、求子串 SubString(&Sub,S,pos,len)SubString(Sub,“commander”,4,3)得到的结果是：Sub=man。算法实现Status SubString(SString&Sub,SString S,int pos,int len)/用 Sub 返回串 S的

11、第 pos个字符起长度为len 的子串。/其中 1pos StrLength(S)且 0len StrLength(S)-pos+1 if(posS0|lenS0-pos+1)return ERROR;Sub1 len=Spos pos+len-1；Sub0=len；return OK;/SubString12、串连接Status Concat(Hstring&T,HStringS1,HstringS2)/用 T 返回由 S1和 S2联接而成的新串if(T.ch)free(T.ch);/释放旧空间if(!(T.ch=(char*)malloc(S1.length+S2.length)*size

12、of(char)exit(Overflow);T.ch0 S1.length-1=S1.ch0S1.length-1;T.length=S1.length+S2.length;T.chS1.length T.length-1=S2.ch0S2.length-1;return OK;/Concat 13、模式匹配名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 9 页 -例：Index(This is a pen,is,pos)，若 pos=1，则查询得结果为3，若 pos=4，则得结果为 6，若 pos=6，则得查询结果为0。int Index(SString S,SString

13、T,int pos)/返回子串 T 在主串 S中第 pos个字符之后的位置。若不存在，则函数值为0。其中，T 非空，1pos StrLength(S)。i=pos;j=1;while(i=S0&j T0)return i-T0;else return 0;/Index 14、KMP（克努特-莫里斯-普拉特）算法思想：每当一趟匹配过程中出现字符比较不等时，不需i 指针（主串）回溯。int Index(SString S,SString T,int pos)/返回子串 T 在主串 S中第 pos个字符之后的位置。若不存在，则函数值为0。其中，T 非空，1pos StrLength(S)。i=pos

14、;j=1;while(i=S0&j T0)return i-T0;else return 0;/Index 15、先序遍历递归算法Status PreOrderTraverse(BiTree T,Status(*Visit)(ElemType)/采用二叉链表存储结构，Visit 是对数据元素操作的应用函数，/先序遍历二叉树 T 的递归算法，对每个数据元素调用函数Visit。/最简单的 Visit 函数是：/Status PrintElement(ElemType e)/输出元素 e 的值/printf(e);/使用时，加上格式串/return OK;名师资料总结-精品资料欢迎下载-名师精心整理

15、-第 5 页，共 9 页 -/调用实例：PreOrderTraverse(T,PrintElement);if(T)if(Visit(T-data)if(PreOrderTraverse(T-lchild,Visit)if(PreOrderTraverse(T-rchild,Visit)return OK;return ERROR;else return OK;/PreOrderTraverse 16、中序遍历非递归算法Status InOrderTraverse(BiTree T,Status(*Visit)(ElemType)/采用二叉链表存储结构，Visit是对数据元素操作的应用函数。/

16、中序遍历二叉树T 的非递归算法，对每个数据元素调用函数Visit。stack S;BiTree p;InitStack(S);p=T;while(p|!StackEmpty(S)if(p)/非空指针进栈，继续左进Push(S,p);p=p-lchild;else/上层指针退栈，访问其所指结点，再向右进Pop(S,p);if(!Visit(p-data)return ERROR;p=p-rchild;/end while return OK;/InOrderTraverse 17、按先序遍历序列建立二叉树的二叉链表BiTree CreateBiTree(BiTree&T)/算法 6.4/按先序次

17、序输入二叉树中结点的值（一个字符），/#字符表示空树，/构造二叉链表表示的二叉树T。char ch;scanf(%c,&ch);if(ch=#)T=NULL;else if(!(T=(BiTNode*)malloc(sizeof(BiTNode)return ERROR;T-data=ch;/生成根结点CreateBiTree(T-lchild);/构造左子树CreateBiTree(T-rchild);/构造右子树 return T;名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 9 页 -/CreateBiTree 18、统计出给定二叉树中结点的数目int count_n(B

18、iTree T)if(T=NULL)num=0;else num1=count_n(T-lchild);num2=count_n(T-rchild);num=num1+num2+1;return num;19、统计出给定二叉树中叶子结点的数目int count_n0(BiTree T)int num,num1,num2;if(T=NULL)num=0;else if(T-lchild=NULL&T-rchild=NULL)num=1;else num1=count_n0(T-lchild);num2=count_n0(T-rchild);num=num1+num2;return num;20、

19、求二叉树的深度int tree_depth(BiTree T)int lh,rh,h;if(T=NULL)h=0;else lh=tree_depth(T-lchild);rh=tree_depth(T-rchild);if(lh=rh)h=lh+1;else h=rh+1;return h;21、结点 x 的查找Bitree search(BiTree T,ElemType x)if(T)if(T-data=x)return T;search(T-lchild,x);/*在左子树中查找*/search(T-rchild,x);/*在右子树中查找*/else return NULL;名师资料总

20、结-精品资料欢迎下载-名师精心整理-第 7 页，共 9 页 -22、中序遍历二叉线索树Status InorderTraverse_Thr(BiThrTree,status(*visit)(TElemType)/T 指向头结点,头结点的 lchild 左链指向根结点，中序遍历二叉线索树的非递归算法,对每个数据元素调用函数Visit P=T lchild;while(p!=T)while(p LTag=Link)p=p lchild;if(!visit(p data)return error;while(p RTag=Thread&p rchild!=T)p=p rchild;Visit(p d

21、ata);p=p rchild;return OK;23、构造 Huffman 树的算法实现用静态三叉链表#define M 50#define MAX 100 typedef struct int data;int pa,lc,rc;HuffmanTree;void huffman(HuffmanTree t,int n,int w)int i,j,k,x1,x2,m1,m2;for(i=1;i(2*n);i+)ti.pa=ti.lc=ti.rc=0;if(i=n)ti.data=wi;else ti.data=0;for(i=1;in;i+)m1=m2=MAX;x1=x2=0;for(j=1;j(n+i);j+)if(tj.datam1)&(tj.pa=0)m2=m1;x2=x1;m1=tj.data;x1=j;else if(tj.datam2)&(tj.pa=0)m2=tj.data;x2=j;名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 9 页 -k=n+i;tx1.pa=tx2.pa=k;tk.data=m1+m2;tk.lc=x1;tk.rc=x2;名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 9 页 -