《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 页 - - - - - - - - -