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

1、.数据结构（本科）期末综合练习四（算法分析题）1.指出算法的功能并求出其时间复杂度。int fun(int n)int i =1,s=1;while(sn)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;i+)for(j=0;jL;j+)for(k=0;kN;k+) cij+=aik

2、*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;free+; 算法执行的结果4.设顺序表SeqList具有下列操作： int Length( ) const;/计算表长度并返回，若表为空则返

3、回0T 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.h”template void unknown ( SeqList& L, T s, T t ) if(!L.Length( ) | s=t)

4、cerr“表为空或参数值有误!”endl; exit(1);int i=0;Ttemp=L.First( ); while(i=s & temp=t)L.Remove( ); else temp=L.Next( ); i+;算法执行后顺序表中的数据：算法执行后顺序表的长度：5.设字符串String具有下列操作：int Length ( ) const;/计算字符串的长度char getData ( k );/提取字符串第k个字符的值若字符串Tar的值为“ababcabcacbab”，Pat的值为“a b c a c”时，给出算法执行后函数返回的结果。*include “String.h”int

5、 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)_; /while/ purge_linkst(1) (2) (3)7.设单链表的存储结构为ListNode=(data,link)，表头指针为LH，所存线性表L=(a,b,c,d,e,f,g)，若

6、执行unknown(LH)调用下面程序，则写出执行结束后的输出结果。 void unknown（LinkNode *Ha） /Ha为指向单链表的头指针 if(Ha) unknown (Ha-link);coutdata; 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)，下面程序

7、段执行后将生成由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的结点数的算法，其中有两行错误，请指出错误行的行号并改正。int count (ListNode *Ha, ElemType x) / Ha 为不带头结点的单链表的头指针int n = 0; while (Ha!= NULL) Ha = H

8、a-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); couty; coutyendl; /main运行结果：12.写出下列程序段的输出结果:void main()queue Q;char x,y=c;Q.In

9、itQueue();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)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;re

10、turn 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) ListNode*r=p-link; p-link=q;q=p;p=r; return q; 算法功能：17.下面是判断一个带表头结点的双向循环链表L其前后结点值是否对称相等的算法, 若相等则返回1，否则返回0。请按标号补充合适的内容。 int symm

11、etry ( 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) (2) (3)18.阅读下面的算法, 写出它的功能。ListNode* unknown( ) ListNode *first, *p, *q;int x; p = first = new ListNode;cinx;while (x !=0) q =ne

12、w ListNode; q-data = x; p-rlink = q; q-llink = p; p = q; cinx;p-rlink = NULL;return first-rlink;算法功能：19.rear是指向以循环链表表示的队列的队尾指针，EnLQueue函数实现插入 x 为新的队尾元素的操作。DeLQueue函数实现删除队头元素并赋给x的操作。请按标号补充合适的内容。void EnLQueue(ListNode*& rear, ElemType x)/ rear是指向以循环链表表示的队列的队尾指针，插入 x 为新的队尾元素。ListNode*p;p = new ListNode

13、;p-data = x; _(1)_;rear-link = p; rear = p; bool DeLQueue(ListNode*& rear, 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-lin

14、k;_(2)_;delete p; _(3)_;(1) (2) (3) 20. 设有一个求解汉诺塔（Hanoi）的递归算法如下：voidHANOI ( int n, int peg1, int peg2, int peg3 ) if(n=1) coutpeg1peg3endl;else HANOI(n-1, peg1, peg3, peg2); coutpeg1peg3temp An-1:temp;返回结果：算法功能：22.针对如下算法，设整数链表L中各结点的数据为12, 24, 30, 90, 84, 36，n的初值为0，则（1）给出执行unknown( L.first, n )调用后的返回

15、结果;（2）指出算法功能。在算法中getLink()函数返回结点指针域的值，getData()函数返回结点的数据域的值。floatunknown ( ListNode *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 *left, *right;其中data为结点值域，left和right分别

16、为指向左、右子女结点的指针域。下面函数的功能是返回二叉树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 _(3)_; /若树中不存在X结点则返回-1 else return -1; (1)(2)(3)

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

18、urn 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分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树。BinTreeNode* BTre

19、eSwopX(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 STreeNode datatype data; STreeNode *lchild, *rchild, *parent;其中data为结点值域，lchild和rchild分别为指

20、向左、右子女结点的指针域，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(ST-lchild,X) return mt; else if(mt=PN(ST-rchild,X) return mt; return NULL; 算法功能：27.已知二叉树中的结点类型

21、BinTreeNode定义为: struct BinTreeNode ElemType data;BinTreeNode *left, *right;其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树。 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=

22、t;BTC(BT-left);BTC(BT-right);算法功能：28.已知二叉树中的结点类型BinTreeNode定义为: struct BinTreeNode char data; BinTreeNode *left, *right;其中data为结点值域，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)调用后，

23、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); BTC1( BT-right, x, k); (1)(2)(3)(4)29.已知二叉树中的结点类型BinTreeNode定义为: struct BinTreeNode ElemType data; BinTreeNode *left, *right;其中data为结点值域，left和right分别为指向左、右子女结点的指针域。下

24、面函数的功能是从二叉树BT中查找值为X的结点，若查找成功则返回结点地址，否则返回空。请在划有横线的地方填写合适内容。BinTreeNode* BTF(BinTreeNode* BT, ElemType x) if(BT=NULL) _(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; BinTr

25、eeNode *left, *right;其中data为结点值域，left和right分别为指向左、右子女结点的指针域。假定一棵二叉树采用链接存储，它的广义表表示为r(b(,d(f,g),t(e)，rt,bt,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) ch

26、ar k1,k2; k1=BTM(BT-left); k2=BTM(BT-right); if(k1max) max=k1; else if(k2max) max=k2; else if(BT-datamax) 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分别为指向左、右子女结点的指针域。根据下面函数的定义指出

27、函数的功能。算法中参数BT指向一棵二叉树。void preserve(BinTreeNode* BT, ElemType a, int n) static 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+;

28、int x=item; int i=n-1; while(i!=0) int j=(i-1)/2; if(x=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) cerrnull!endl;exit(1);int temp=HBT0;n-;int x=HBTn; int i=0; int j=2*i+1; while(j=n-1) if(jHBTj+1)

29、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此树为空right!=NULL) t=

30、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 & p2!=NULL) ListNode* newptr=new ListNode;if(p1-datadata) newptr-data=p1-data; p1=p1-link; else if(p1-datap2-d

31、ata) 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!=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和指向后继结

32、点的指针域link，试根据下面算法指出算法功能。int SS(ListNode* p1, ListNode* p2) while(p2!=NULL) ListNode* r=p1; 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 Ele

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

34、lemType data; BinTreeNode *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, ElemTypeX)if(t=NULL) return 0; else if(t-data=X) return 1;else i

35、f(t-dataX) 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) if(bt=NUL

36、L) return 1; else if(JB(bt-left,x)=0) return 0;if(bt-datadata; if(JB(bt-right,x)=0) return 0; else return 1; 算法功能：40. 已知一个有向图的顶点集V和边集G分别为：V=0,1,2,3,4;E=,;若它采用邻接矩阵存储，对应Graph类型的对象为a，则：(1)使用a.count_D(3)调用下面算法后的返回值是多少.(2)该算法的功能是什么.(3)给出该算法的时间复杂度。Template int Graph:count_D(int i) int d=0;for (int j=0; jC

37、urrentNode; j+) / CurrentNode为图中的顶点数if (Edgeij!=0) d+;if (Edgeji!=0 ) d+;return(d);答（1）（2）（3）41. 假定一个有向图采用邻接矩阵存储, 请指出下面算法的功能。 template void Graph:unknown(int i)int d,j;d = 0;for (j=0; jCurrentNodes; j+) /CurrentNodes为图中的顶点数 if(Edgeij) d+; Edgeij=0;if(Edgeji) d+; Edgeji=0;CurrentEdges -= d; / Current

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

39、j; p!=NULL; _(2)_)_(3)_;答(1)(2)(3)43.已知图的邻接表中边结点类型Edge的结构为(dest, cost, link)，在表头向量中指向顶点单链表的表头指针为adj，下面算法是在用邻接表表示的图中计算顶点i的入度并返回。请按标号填补合适内容。 Template intGraph:FindDegree(int i);int deg=0,j;for(j=0; jdest=i) _(2)_; break; else p=_(3)_; return deg; 答(1)(2)(3)44.已知图的邻接表中边结点类型Edge的结构为(dest, cost, link)，在表

40、头向量中指向顶点单链表的表头指针为adj，下面算法是在用邻接表表示的有向图中删除所有以i为弧头（即终点）的有向边。请按标号填补合适内容。templatevoid Graph:DeletEdge(int i) int de=0,j;Edge *p, *q;if(i=NumVertices)cout错误输入endl; exit(1); /NumVertices为顶点数 for(j=0;jdest=i) _(1)_; else q=p;_(2)_;if(p!=NULL) if(q=NULL) NodeTablej.adj=p-link; else _(3)_;delete p;de+;NumEdge

41、s=NumEdges-de;答(1)(2)(3) 45. 下面是进行快速排序的一次划分的算法，请按标号填补合适的内容。void Exchange(int s, int i, int j) int temp =si; si=sj; _(1)_;int Partition(int seq, int low, int high) int pivotpos=low, pivot=seqlow, i; for(i=low+1; i=high; i+)if(_(2)_)pivotpos+;if(pivotpos!=i) Exchange(seq, pivotpos, i);_(3)_;return pivotpos;答(1) (