《2022年数据结构期中测试算法填空》由会员分享，可在线阅读，更多相关《2022年数据结构期中测试算法填空（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)
2、; / 求线性表的长度for ( i = 1; i = LB_len; 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.ele
3、m ) exit(OVERFLOW); / 存储分配失败L.length = 0; /空表长度为 0 L.listsize = LIST_INIT_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 元
4、素的位序p = L.elem; / p 的初值为第 1 元素的存储位置while ( i = L.length & L.elemi-1!=e ) +i; if (i = L.length) return i; else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 9 页 - - - - - - - - - return 0; / LocateElem_Sq此算法的时间复杂度为 : O( ListLength(L) ) 4、在线性表中指定位置前插入一个元素算法思想：1）
5、不合法：插入位置：检查i 值是否超出所允许的范围（1in+1） ，若超出，则进行 “ 超出范围 ” 错误处理；存储空间满2）将线性表的第i 个元素和它后面的所有元素均向后移动一个位置；3）将新元素写入到空出的第i 个位置上；4）使线性表的长度增1。Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在顺序线性表 L 的第 i 个元素之前插入新的元素e / i 的合法值为 1iListlength_Sq(L)+1 if(i L.length+1) return ERROR; / 插入位置不合法if(L.length = L.listsize)
6、 / 当前存储空间已满，增加分配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=i-1;j-) L.elemj+1 = L.elemj L.elemi-1 = e; /元素下标法+ length; return ok; 插
7、入算法的时间复杂度为: O( ListLength(L) ) 5、在线性表中删除第i 个元素算法思想：1）检查 i 值是否超出所允许的范围（1in） ，若超出，则进行 “ 超出范围 ” 错误处理；2）将线性表的第i 个元素后面的所有元素均向前移动一个位置；3）使线性表的长度减1。Status ListDelete_Sq( SqList &L, int i, ElemType &e ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 9 页 - - - - - - - -
8、- / 在顺序线性表 L 中删除第 i 个元素，并用 e返回其值。/ 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 );
9、/ 追加存储空间失败S.top = S.base + S.stacksize; / 修改栈顶指针S.stacksize += STACKINCREMENT; / 修改当前栈的存储空间 *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 为空，则返
10、回ERROR -S.top; e=*(S.top); / 先令 top 减 1，再将 top 所指单元值赋给ereturn OK; / Pop 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 9 页 - - - - - - - - - 9、入队在循环队列尾插入新元素算法Status EnQueue ( SqQueue &Q; QElemType e ) / 若队列满，则返回ERROR ；若队列不满，则插入元素e 为队列Q 新的队尾元素。if ( ( Q.rear + 1
11、) % 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 ；若队列不空，则删除Q 的队列头元素，用e 返回其值，并返回OK 。if ( Q.front = = Q.rear ) return ERROR
12、; / 如果循环队列空，则出错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的第 pos个字符起长度为len 的子串。/ 其中
13、 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) * sizeof(char) ex
14、it(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)
15、，若 pos=1，则查询得结果为3，若 pos=4，则得结果为 6，若 pos=6，则得查询结果为0。int Index(SString S, SString 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 In
16、dex(SString S, SString 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 15、先序遍历递归算法Status PreOrderTraverse( BiTree T, Status(*Visit)(ElemType) ) / 采用二叉链表存储结构，Visit 是对数据元素操作的应用函数，/ 先序遍历二叉树 T 的递归算
17、法，对每个数据元素调用函数Visit。/ 最简单的 Visit 函数是：/ Status PrintElement( ElemType e ) / 输出元素 e 的值/ printf( e ); / 使用时，加上格式串/ return OK; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 9 页 - - - - - - - - - / / 调用实例： PreOrderTraverse(T, PrintElement); if (T) if (Visit(T-data)
18、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是对数据元素操作的应用函数。/ 中序遍历二叉树T 的非递归算法，对每个数据元素调用函数Visit。stack S; BiTree p; InitSta
19、ck(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 / 按先序次序输入二叉树中结点的值（一个字符），/ #字符表示空
20、树，/ 构造二叉链表表示的二叉树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
21、页，共 9 页 - - - - - - - - - / CreateBiTree 18、统计出给定二叉树中结点的数目int count_n(BiTree 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
22、) num=1; else num1=count_n0(T-lchild); num2=count_n0(T-rchild); num= num1+num2; return num; 20、求二叉树的深度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)
23、if(T) if(T-data=x) return T; search(T-lchild,x); /*在左子树中查找 */ search(T-rchild,x); /*在右子树中查找 */ else return NULL; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 9 页 - - - - - - - - - 22、中序遍历二叉线索树Status InorderTraverse_Thr(BiThrTree ,status(*visit)(TElemType) /T
24、指向头结点 ,头结点的 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 data); p= p rchild; return OK; 23、构造 Huffman 树的算法实现用静态三叉链表#define M 50 #define MAX 100 typede
25、f 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; el
26、se 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 页 - - - - - - - - -
