1、数据结构本科期末综合练习四算法分析题数据结构（本科）期末综合练习四（算法分析题）1.指出算法的功能并求出其时间复杂度。int fun ( int n ) int i = 1, s = 1; while ( s n ) s += +i;return i;功能为：时间复杂度为：2.指出算法的功能并求出其时间复杂度。void matrimult ( int aMN, int bNL, int cML ) /M、N、L均为全局整型常量 int i, j, k; for ( i = 0; i M; i+ ) for ( j = 0; j L; j+ ) cij = 0; for ( i = 0; i M
2、; i+ ) for ( j = 0; j L; j+ ) for ( k = 0; k N; k+ ) cij += aik * bkj;功能为：时间复杂性为：3.针对如下算法，回答问题：若数组An = 12, 24, 0, 38, 0, 0, 0, 0, 29, 0, 45, 0, n = 12，给出算法执行后数组An的状态。template void unknown ( T A , int n ) int free = 0; for ( int i = 0; i n; i+ ) if ( Ai != 0 ) if ( i != free ) Afree = Ai; Ai = 0; fre
3、e+; 算法执行的结果4.设顺序表SeqList具有下列操作： int Length( ) const;/计算表长度并返回，若表为空则返回0 T Remove( ); /删除当前表项并返回其值，置下一表项为当前表项 T First( ); /取表中第一个表项的值并返回，并置为当前表项 T Next( ); /取当前表项后继表项的值并返回， /并把此后继表项置为当前表项若顺序表中存放的数据为29,38,47,16,95,64,73,83,51,10,0,26，表的长度为12，参数值s=10, t=30，说明算法执行后顺序表的状态和长度的变化。 #include #include “SeqList
4、.h” template void unknown ( SeqList& L, T s, T t ) if(!L.Length( ) | s=t) cerr“表为空或参数值有误!”endl; exit(1); int i=0; T temp=L.First( ); while(i=s & temp=t) L.Remove( ); else temp=L.Next( ); i+; 算法执行后顺序表中的数据：算法执行后顺序表的长度：5.设字符串String具有下列操作：int Length ( ) const; /计算字符串的长度char getData ( k ); /提取字符串第k个字符的值若
5、字符串Tar的值为“a b a b c a b c a c b a b”，Pat的值为“a b c a c”时，给出算法执行后函数返回的结果。#include “String.h”int unknown ( String& Tar, String& Pat ) const for ( int i = 0; i = Tar.Length( ) Pat.Length( ); i+ ) int j = 0; while ( j link;while (p) if (p & _(1)_) q=p; p = p-link; else q-link= _(2)_; delete(p); p=_(3)_;
6、/while/ purge_linkst(1) (2) (3)7.设单链表的存储结构为ListNode=(data,link)，表头指针为LH，所存线性表L=(a,b,c,d,e,f,g)，若执行unknown(LH)调用下面程序，则写出执行结束后的输出结果。 void unknown（LinkNode *Ha） /Ha为指向单链表的头指针 if(Ha) unknown (Ha-link); coutdata; 8.设单链表结点的结构为LNode=(data,link)，阅读下面的函数，指出它所实现的功能。 int AA(LNode *Ha) /Ha为指向带表头附加结点的单链表的表头指针 in
7、t n=0; LNode *p=Ha-link; while(p) n+; p=p-link; return(n); 算法功能：9.设单链表结点的结构为ListNode = (data,link)，下面程序段执行后将生成由L所指向的带头结点的单链表，给出该单链表所对应的线性表。 ListNode *L = new ListNode;ListNode *p=L;for (int i = 0; i link = new ListNode;p = p-link;p-data = i*2-1; /for p-link = NULL;10.这是一个统计单链表中结点的值等于给定值x的结点数的算法，其中有两
8、行错误，请指出错误行的行号并改正。int count (ListNode *Ha, ElemType x) / Ha 为不带头结点的单链表的头指针int n = 0; while (Ha!= NULL) Ha = Ha-link; if (Ha-data = x) n+; /whilereturn n; /count错误语句号: 修改如下: 11.写出下列程序段的输出结果:void main()stack S;char x,y;S.InitStack( );x=c;y=k;S.Push(x); S.Push(a); S.Push(y);S.Pop(S,x); S.Push(t); S.Push
9、(s);while(!S.IsEmpty( ) S.Pop(y); couty; coutyendl; /main运行结果：12.写出下列程序段的输出结果:void main()queue Q;char x, y=c;Q.InitQueue( );Q.EnQueue(h); Q.EnQueue(r); Q.EnQueue(y);Q.DeQueue(x); Q.EnQueue(x); Q.DeQueue(x);Q.EnQueue(a);while(Q.IsEmpty( ) Q.DeQueue(y); couty; coutxlink=NULL; while(p1!=NULL & p2!=NULL
10、) if(p1-datadata) _(1)_; p1=p1-link; else p-link=p2; p2=p2-link; _(2)_; if(p1!=NULL) p-link=p1; else _(3)_; p1=p2=NULL; return a.link; (1) (2) (3) 16.阅读下列算法，写出算法功能。 LinkNode* BB(LinkNode *first) if(first=NULL | first-link=NULL) return first; LinkNode *q=first,*p=q-link; q-link=NULL; while(p!=NULL) L
11、istNode *r=p-link; p-link=q; q=p; p=r; return q; 算法功能：17.下面是判断一个带表头结点的双向循环链表L其前后结点值是否对称相等的算法, 若相等则返回1，否则返回0。请按标号补充合适的内容。 int symmetry ( DoublelList* DL ) DoublelNode * p = DL-rLink, *q = DL-lLink; while (p != q) if ( p-data = q-data ) p = p-rLink; _(1)_; if(p-lLink=q) _(2)_; else _(3)_; return 1; (1
12、) (2) (3)18.阅读下面的算法, 写出它的功能。ListNode* unknown( ) ListNode *first, *p, *q; int x; p = first = new ListNode; cinx; while (x != 0) q = new ListNode; q-data = x; p-rlink = q; q-llink = p; p = q; cinx; p-rlink = NULL; return first-rlink;算法功能：19.rear是指向以循环链表表示的队列的队尾指针，EnLQueue函数实现插入 x 为新的队尾元素的操作。DeLQueue函
13、数实现删除队头元素并赋给x的操作。请按标号补充合适的内容。void EnLQueue(ListNode*& rear, ElemType x)/ rear是指向以循环链表表示的队列的队尾指针，插入 x 为新的队尾元素。 ListNode *p; p = new ListNode; p-data = x; _(1)_; rear-link = p; rear = p; bool DeLQueue(ListNode*& rear, ElemType& x) / rear是指向以循环链表表示的队列的队尾指针，若队列不空，/则删除队头元素并以 x 带回，并返回 true, 否则返回 false, x
14、无意义 if(rear=NULL) return false;if ( rear-link = rear ) x=rear-data; delete rear; rear=NULL; return true; ListNode *p=rear-link; rear-link=p-link; _(2)_; delete p; _(3)_;(1) (2) (3) 20. 设有一个求解汉诺塔（Hanoi）的递归算法如下：void HANOI ( int n, int peg1, int peg2, int peg3 ) if(n=1) coutpeg1peg3endl;else HANOI(n-1,
15、 peg1, peg3, peg2); coutpeg1peg3 temp ? An-1:temp;返回结果：算法功能：22.针对如下算法，设整数链表L中各结点的数据为12, 24, 30, 90, 84, 36，n的初值为0，则（1）给出执行unknown( L.first, n )调用后的返回结果;（2）指出算法功能。在算法中getLink()函数返回结点指针域的值，getData()函数返回结点的数据域的值。float unknown ( ListNode *f , int& n ) if ( f = NULL ) return 0; else n+; return unknown (f
16、-getLink(),n) + f-getData()/n ;返回结果：算法功能：23.已知二叉树中的结点类型BinTreeNode定义为: struct BinTreeNode ElemType data; BinTreeNode *left, *right;其中data为结点值域，left和right分别为指向左、右子女结点的指针域。下面函数的功能是返回二叉树BT中值为X的结点所在的层号，请在划有横线的地方填写合适内容。int NodeLevel(BinTreeNode * BT, ElemType X) if(BT=NULL) return 1; /空树的层号为-1 else if(BT
17、-data=X) return 0; /根结点的层号为0 /向子树中查找X结点 else int c1=NodeLevel(BT-left,X); if(c1=0) _(1)_; int c2=_(2)_; if _(3)_; /若树中不存在X结点则返回-1 else return -1; (1)(2)(3)24.已知二叉树中的结点类型BinTreeNode定义为:struct BinTreeNode ElemType data; BinTreeNode *left, *right;其中data为结点值域，left和right分别为指向左、右子女结点的指针域。下面函数的功能是：从二叉树BT中查
18、找值为X的结点，返回指向其父结点的指针。若该结点不存在或为树根结点则返回空。算法中参数PT的初值为NULL。请在划有横线的地方填写合适内容。BinTreeNode* ParentPtr(BinTreeNode* BT, BinTreeNode* PT, ElemType& X) if(BT=NULL) return NULL; else if(BT-data=X) return PT; else if(PT=ParentPtr(BT-left,BT,X) _(1)_; if _(2)_ return PT; else _(3)_; (1)(2)(3)25.已知二叉树中的结点类型BinTreeN
19、ode定义为:struct BinTreeNode ElemType data; BinTreeNode *left, *right;其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树。 BinTreeNode* BTreeSwopX(BinTreeNode* BT) if(BT=NULL) return NULL; else BinTreeNode* pt=new BinTreeNode; pt-data=BT-data; pt-right=BTreeSwopX(BT-left); pt-left=BT
20、reeSwopX(BT-right); return pt; 算法功能：26. 已知二叉树中的结点类型STreeNode定义为:struct STreeNode datatype data; STreeNode *lchild, *rchild, *parent;其中data为结点值域，lchild和rchild分别为指向左、右子女结点的指针域，parent为指向父亲结点的指针域。根据下面函数的定义指出函数的功能。算法中参数ST指向一棵二叉树，X保存一个结点的值。STreeNode* PN(STreeNode* ST, datatype& X) if(ST=NULL) return NULL;
21、 else StreeNode* mt; if(ST-data=X) return ST-parent; else if(mt=PN(ST-lchild,X) return mt; else if(mt=PN(ST-rchild,X) return mt; return NULL; 算法功能：27.已知二叉树中的结点类型BinTreeNode定义为: struct BinTreeNode ElemType data; BinTreeNode *left, *right;其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT
22、指向一棵二叉树。 void BTC(BinTreeNode* BT) if(BT!=NULL) if( BT-left!=NULL & BT-right!=NULL) if(BT-left-dataBT-right-data) BinTreeNode* t=BT-left; BT-left=BT-right; BT-right=t; BTC(BT-left); BTC(BT-right); 算法功能：28.已知二叉树中的结点类型BinTreeNode定义为: struct BinTreeNode char data; BinTreeNode *left, *right;其中data为结点值域，
23、left和right分别为指向左、右子女结点的指针域。假定指针bt指向一棵二叉树，该二叉树的广义表表示为a(b(a,d(f),c(e(,a(k),b)，每次调用时整数变量C的值均为0，若：执行BTC1(bt,a,C)调用后，C的值为_(1)_;执行BTC1(bt,b,C)调用后，C的值为_(2)_;执行BTC1(bt,c,C)调用后，C的值为_(3)_;执行BTC1(bt,g,C)调用后，C的值为_(4)_;void BTC1(BinTreeNode* BT, char x, int& k) if(BT!=NULL) if( BT-data=x) k+; BTC1( BT-left, x, k
24、); BTC1( BT-right, x, k); (1)(2)(3)(4)29.已知二叉树中的结点类型BinTreeNode定义为: struct BinTreeNode ElemType data; BinTreeNode *left, *right;其中data为结点值域，left和right分别为指向左、右子女结点的指针域。下面函数的功能是从二叉树BT中查找值为X的结点，若查找成功则返回结点地址，否则返回空。请在划有横线的地方填写合适内容。BinTreeNode* BTF(BinTreeNode* BT, ElemType x) if(BT=NULL) _(1)_; else if( BT-data=x) _(2)_; else BinTreeNode* t; if(t=B
