数据结构(本科)期末综合练习四(算法分析题)

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 <

2、; M; 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 <class T> void unknown ( T A , int n ) int free = 0; for ( int i = 0; i < n; i+ ) if ( Ai != 0 ) if ( i

3、 != free ) Afree = Ai; Ai = 0; free+; 算法执行的结果4.设顺序表SeqList具有下列操作： int Length( ) const;/计算表长度并返回，若表为空则返回0T Remove( );/删除当前表项并返回其值，置下一表项为当前表项T First( ); /取表中第一个表项的值并返回，并置为当前表项 T Next( );/取当前表项后继表项的值并返回， /并把此后继表项置为当前表项若顺序表中存放的数据为29,38,47,16,95,64,73,83,51,10,0,26，表的长度为12，参数值s=10, t=30，说明算法执行后顺序表的状态和长度的

4、变化。#include <iostream.h>#include “SeqList.h”template <class T> void unknown ( SeqList<T>& L, T s, T t ) if(!L.Length( ) | s>=t) cerr<<“表为空或参数值有误!”<<endl; exit(1);int i=0;T temp=L.First( ); while(i<L.Length( ) if(temp>=s && temp<=t) L.Remove( ); e

5、lse temp=L.Next( ); i+;算法执行后顺序表中的数据：算法执行后顺序表的长度：5.设字符串String具有下列操作：int Length ( ) const;/计算字符串的长度char getData ( k );/提取字符串第k个字符的值若字符串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 <=

6、Tar.Length( ) Pat.Length( ); i+ ) int j = 0; while ( j < Pat.Length( ) ) if ( Tar.getData (i+j) = Pat.getData (j) ) j+; else break; if ( j = Pat.Length( ) ) return i; return -1;算法执行的结果是： 6.阅读下列算法，并补充所缺内容。void purge_linkst( ListNode *& la ) / 从头指针为 la 的有序链表中删除所有值相同的多余元素，并释放被删结点空间ListNode *p,*q

7、;if(la=NULL) return;q=la; p = la->link;while (p) if (p && _(1)_) q=p; p = p->link; else q->link= _(2)_; delete(p); p=_(3)_; /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） /

8、Ha为指向单链表的头指针 if(Ha) unknown (Ha->link); cout<<Ha->data; 8.设单链表结点的结构为LNode=(data,link)，阅读下面的函数，指出它所实现的功能。 int AA(LNode *Ha) /Ha为指向带表头附加结点的单链表的表头指针 int n=0; LNode *p=Ha->link; while(p) n+; p=p->link; return(n); 算法功能：9.设单链表结点的结构为ListNode = (data,link)，下面程序段执行后将生成由L所指向的带头结点的单链表，给出该单链表所

9、对应的线性表。 ListNode *L = new ListNode;ListNode *p=L;for (int i = 0; i < 4; i+) p->link = new ListNode;p = p->link;p->data = i*2-1; /for p->link = NULL;10.这是一个统计单链表中结点的值等于给定值x的结点数的算法，其中有两行错误，请指出错误行的行号并改正。int count (ListNode *Ha, ElemType x) / Ha 为不带头结点的单链表的头指针int n = 0; while (Ha!= NULL)

10、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('s');while(!S.IsEmpty( ) S.Pop(y); cout<<

11、y; cout<<y<<endl; /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); cout<<y; cout<<x<

12、;<endl; /main输出结果：13.指出下面算法的功能。 Stack unknown(Stack S) Stack T; int d; T.IniStack( ); /初始化栈 While(!S.IsEmpty( ) d=S.GetTop( ); S.Pop( ); T.Push(d); return T; 14.请写出下面算法的功能.void unknown(Queue &Q) Stack S; int d; S.InitStack( ); while(!Q.IsEmpty( ) Q.DeQueue(d); S.Push(d); while(!S.IsEmpty( ) S

13、.Pop(d); Q.EnQueue(d); 15.下面算法的功能为：将两个有序单链表合并成一个有序单链表并返回其表头指针。阅读下列算法, 按标号填写空缺的内容，要求统一填写在算法后面的标记处。 ListNode* Merge1(ListNode*& p1, ListNode*& p2) ListNode a; /a结点作为结果有序单链表的表头附加结点 ListNode* p=&a; p->link=NULL; while(p1!=NULL && p2!=NULL) if(p1->data<=p2->data) _(1)_; p1

14、=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)

15、ListNode *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

16、) _(2)_; else _(3)_; return 1; (1) (2) (3)18.阅读下面的算法, 写出它的功能。ListNode* unknown( ) ListNode *first, *p, *q; int x; p = first = new ListNode; cin>>x; while (x != 0) q = new ListNode; q->data = x; p->rlink = q; q->llink = p; p = q; cin>>x; p->rlink = NULL; return first->rlink

17、;算法功能：19.rear是指向以循环链表表示的队列的队尾指针，EnLQueue函数实现插入 x 为新的队尾元素的操作。DeLQueue函数实现删除队头元素并赋给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,

18、 ElemType& x) / rear是指向以循环链表表示的队列的队尾指针，若队列不空，/则删除队头元素并以 x 带回，并返回 true, 否则返回 false, x 无意义 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. 设有一个求解

19、汉诺塔（Hanoi）的递归算法如下：void HANOI ( int n, int peg1, int peg2, int peg3 ) if(n=1) cout<<peg1<<-><<peg3<<endl;else HANOI(n-1, peg1, peg3, peg2); cout<<peg1<<-><<peg3<<endl; HANOI(n-1, peg2, peg1, peg3); 当使用HANOI( 3,1,2,3)进行调用时，执行过程中else子句的cout语句得到的结果为：

20、21.针对如下算法，回答问题：(1)若整型数组A8 = 12, 24, 33, 38, 95, 83, 64, 57，n=8，则给出算法返回的结果。 (2)说明算法的功能是什么。int unknown ( int A , int n ) if ( n = 1 ) return A0; int temp = unknown ( A, n-1 ); return An-1 > temp ? An-1:temp;返回结果：算法功能：22.针对如下算法，设整数链表L中各结点的数据为12, 24, 30, 90, 84, 36，n的初值为0，则（1）给出执行unknown( L.first, n

21、)调用后的返回结果;（2）指出算法功能。在算法中getLink()函数返回结点指针域的值，getData()函数返回结点的数据域的值。float unknown ( ListNode<int> *f , int& n ) if ( f = NULL ) return 0;else n+; return unknown (f->getLink(),n) + f->getData()/n ;返回结果：算法功能：23.已知二叉树中的结点类型BinTreeNode定义为: struct BinTreeNode ElemType data; BinTreeNode *le

22、ft, *right;其中data为结点值域，left和right分别为指向左、右子女结点的指针域。下面函数的功能是返回二叉树BT中值为X的结点所在的层号，请在划有横线的地方填写合适内容。int NodeLevel(BinTreeNode * BT, ElemType X) if(BT=NULL) return 1; /空树的层号为-1 else if(BT->data=X) return 0; /根结点的层号为0 /向子树中查找X结点 else int c1=NodeLevel(BT->left,X); if(c1>=0) _(1)_; int c2=_(2)_; if _

23、(3)_; /若树中不存在X结点则返回-1 else return -1; (1)(2)(3)24.已知二叉树中的结点类型BinTreeNode定义为:struct BinTreeNode ElemType data; BinTreeNode *left, *right;其中data为结点值域，left和right分别为指向左、右子女结点的指针域。下面函数的功能是：从二叉树BT中查找值为X的结点，返回指向其父结点的指针。若该结点不存在或为树根结点则返回空。算法中参数PT的初值为NULL。请在划有横线的地方填写合适内容。BinTreeNode* ParentPtr(BinTreeNode* BT

24、, 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.已知二叉树中的结点类型BinTreeNode定义为:struct BinTreeNode ElemType data; BinTreeNode *left, *right;其中data为结点值域，left和right分别为指向左、

25、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数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=BTreeSwopX(BT->right); return pt;算法功能：26. 已知二叉树中的结点类型STreeNode定义为:struct STreeNo

26、de datatype data; STreeNode *lchild, *rchild, *parent;其中data为结点值域，lchild和rchild分别为指向左、右子女结点的指针域，parent为指向父亲结点的指针域。根据下面函数的定义指出函数的功能。算法中参数ST指向一棵二叉树，X保存一个结点的值。STreeNode* PN(STreeNode* ST, datatype& X) if(ST=NULL) return NULL; else StreeNode* mt; if(ST->data=X) return ST->parent; else if(mt=PN

27、(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指向一棵二叉树。 void BTC(BinTreeNode* BT) if(BT!=NULL) if( BT->

28、;left!=NULL && BT->right!=NULL) if(BT->left->data>BT->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为结点

29、值域，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

30、->left, x, k); 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=NUL

31、L) _(1)_; else if( BT->data=x) _(2)_; else BinTreeNode* t; if(t=BTF(BT->left, x) _(3)_; _(4)_; else return NULL; (1)(2)(3)(4)30.已知二叉树中的结点类型BinTreeNode定义为: struct BinTreeNode char data; BinTreeNode *left, *right;其中data为结点值域，left和right分别为指向左、右子女结点的指针域。假定一棵二叉树采用链接存储，它的广义表表示为r(b(,d(f,g),t(e)，rt,bt

32、,dt和et指针变量分别保存指向r,b,d和e结点的指针值，则：执行BTM(rt)调用后，得到的函数值为_(1)_;执行BTM(bt)调用后，得到的函数值为_(2)_;执行BTM(dt)调用后，得到的函数值为_(3)_;执行BTM(et)调用后，得到的函数值为_(4)_;char BTM(BinTreeNode* BT) static char max=0; if(BT!=NULL) char k1,k2; k1=BTM(BT->left); k2=BTM(BT->right); if(k1>max) max=k1; else if(k2>max) max=k2; el

33、se if(BT->data>max) max=BT->data; return max;(1)t /2分(2)g /2分(3)g /2分(4)e /2分31.已知二叉树中的结点类型BinTreeNode定义为: struct BinTreeNode ElemType data;BinTreeNode *left, *right;其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树。void preserve(BinTreeNode* BT, ElemType a, int n) stat

34、ic int i=0; if(BT!=NULL) preserve(BT->left, a, n); ai+=BT->data; preserve(BT->right, a, n); 算法功能：32.在a10数组中的数据16,42,35,73,54,38,80为一个最小堆，n为整型变量，其值为7，则执行IH(a,n,25)调用下面算法后数组a中的数据变为_。void IH(int HBT, int& n, int item) HBTn=item; n+; int x=item; int i=n-1; while(i!=0) int j=(i-1)/2; if(x>

35、;=HBTj) break; HBTi=HBTj; i=j; HBTi=x;33.在a10数组中数据16,35,42,73,54,58,80为一个最小堆，n为整型变量，其值为7，则执行DH(a,n)调用下面算法后数组a中的数据变为_。int DH(int HBT, int& n) if(n=0) cerr<<"null!"<<endl; exit(1); int temp=HBT0; n-; int x=HBTn; int i=0; int j=2*i+1; while(j<=n-1) if(j<n-1 && HB

36、Tj>HBTj+1) j+; if(x<=HBTj) break; HBTi=HBTj; i=j; j=2*i+1; HBTi=x; return temp;34.已知二叉搜索树中的结点类型BinTreeNode定义为:struct BinTreeNode ElemType data; BinTreeNode *left, *right;其中data为结点值域，left和right分别为指向左、右子女结点的指针域。指针参数BST指向一棵二叉搜索树。试根据下面的函数定义指出此算法的功能。 ElemType FM(BinTreeNode* BST) if(BST=NULL) cerr&

37、lt;<"此树为空"<<endl; exit(1); BinTreeNode* t=BST; while(t->right!=NULL) t=t->right; return t->data; 算法功能：35.假定p1和p2是两个有序单链表的表头指针，用来表示两个集合，单链表中的结点包括值域data和指向后继结点的指针域link，试指出下面算法的功能。ListNode* BU(ListNode* p1, ListNode* p2)ListNode* p3=new ListNode, *p=p3;While(p1!=NULL &&a

38、mp; p2!=NULL) ListNode* newptr=new ListNode; if(p1->data<p2->data) newptr->data=p1->data; p1=p1->link; else if(p1->data>p2->data) newptr->data=p2->data; p2=p2->link;else newptr->data=p1->data; p1=p1->link; p2=p2->link;p3->link=newptr;p3=newptr;if(p2

39、!=NULL) p1=p2;while(p1!=NULL) p3=p3->link=new ListNode; p3->data=p1->data; p1=p1->link; p3->link=NULL; p3=p->link; delete p;return p3;算法功能：36.假定p1和p2是两个单链表的表头指针，用来表示两个集合，单链表中的结点包括值域data和指向后继结点的指针域link，试根据下面算法指出算法功能。int SS(ListNode* p1, ListNode* p2) while(p2!=NULL) ListNode* r=p1;

40、While(r!=NULL) if(p2->data=r->data) break; r=r->link; if(r=NULL) return 0; p2=p2->link; return 1;37.假定HL为保存一个集合的有序单链表的表头指针，item为一个新元素，HL单链表中的结点包括值域data和指向后继结点的指针域link，试根据下面算法指出算法功能。void IS(ListNode*& HL, const ElemType& item) ListNode* newptr=new ListNode; newptr->data=item; i

41、f(HL=NULL | item<HL->data) newptr->link=HL; HL=newptr; return; ListNode *cp, *ap; ap=HL; cp=HL->link; while(cp!=NULL) if(item<cp->data) break; ap=cp; cp=cp->link; newptr->link=cp; ap->link=newptr;算法功能：38.已知二叉搜索树中的结点类型BinTreeNode定义为: struct BinTreeNode ElemType data; BinTre

42、eNode *left, *right;其中data为结点值域，left和right分别为指向左、右子女结点的指针域。参数t指向一棵二叉搜索树，该树的广义表表示为: 25(10(5,16(12),40(32(,38)。按照下面算法，则： 执行LN(pt,40)调用后返回的值为_(1)_。 执行LN(pt,38)调用后返回的值为_(2)_。 执行LN(pt,5)调用后返回的值为_(3)_。 int LN(BinTreeNode* t, ElemType X)if(t=NULL) return 0; else if(t->data=X) return 1;else if(t->data

43、>X) return 1+LN(t->left,X);elsereturn 1+LN(t->right,X);(1) (2) (3)39.已知二叉树中的结点类型BinTreeNode定义为:struct BinTreeNode ElemType data; BinTreeNode *left, *right;其中data为结点值域，left和right分别为指向左、右子女结点的指针域。参数bt指向一棵二叉树，引用参数x一开始具有的值小于树中所有结点的值。试根据下面的函数定义指出此算法的功能。 int JB(BinTreeNode* bt, ElemType& x) i

44、f(bt=NULL) return 1; else if(JB(bt->left,x)=0) return 0; if(bt->data<x) return 0; x=bt->data; if(JB(bt->right,x)=0) return 0; else return 1; 算法功能：40. 已知一个有向图的顶点集V和边集G分别为：V=0,1,2,3,4;E=<0,1>,<0,2>,<0,3>,<1,3>,<1,4>,<2,3>,<2,4>,<3,0>,<4

45、,3>若它采用邻接矩阵存储，对应Graph类型的对象为a，则：(1)使用a.count_D(3)调用下面算法后的返回值是多少？(2)该算法的功能是什么？(3)给出该算法的时间复杂度。 Template<class Type> int Graph<Type>:count_D(int i) int d=0;for (int j=0; j<CurrentNode; j+) / CurrentNode为图中的顶点数if (Edgeij!=0) d+;if (Edgeji!=0 ) d+;return(d);答（1）（2）（3）41. 假定一个有向图采用邻接矩阵存储,

46、 请指出下面算法的功能。 template<class Type> void Graph<Type>:unknown(int i) int d,j; d = 0; for (j=0; j<CurrentNodes; j+) /CurrentNodes为图中的顶点数 if(Edgeij) d+; Edgeij=0; if(Edgeji) d+; Edgeji=0; CurrentEdges -= d; / CurrentEdges为图中的边数算法功能：42.已知图的邻接表中边结点类型Edge的结构为(dest, cost, link)，在表头向量中指向顶点单链表的表头指针为adj，下面算法是在用邻接表表示的图中计算所有顶点的出度，并保存在数组Degree中。请按标号填补合适内容。template<class Type> void Graph<Type>:FindDegree(int Degree) int i; Edge *p=NULL; for(i=0; i<NumVertices; i+) Degreei =_(1)_; /NumVertices为顶点数for(i=0; i<NumVertices; i+) for (p = NodeTablei.adj; p!=NULL; _(2)_