大数据的结构习地的题目

1、第1章绪1.1有下列几种二兀组表示的数据结构,试画出它们分别对应的图形表示，(1)集合并指出它们分别属于何种结构。（1） A= （ D，R ），其中，D = a 1，a?.a 3，at ，R= 线性表(2) B= ( D，R )，其中，D = a，b，c，d，e，R= （a，b），（b，c），(c， d)，1 2(d，e)(3) C= ( D，R )，其中，D = a，b，c，d，e，f，g，R= （d，b），（d，g），（b，a），（b，c），（g，e），（e，f） K= （ D ，R ），其中，D = 1，2, 3，4，5，6，R= ， ， ， ， ， ， 树丄图1.2设n为正整数，求下列

2、各程序段中的下划线语句的执行次数。(1) i=1; k=0(2) for (in t i=1; i=n; i+)解:while(i=n-1)for (int j=1; j=n; j+)(1) n-1 cij=0;n nn:仁n3k+=10*i ;for (i nt k=1; k=n; k+)i+;cij=cij+aik*bkji =1 j mkT(3) x=0;y=0;n i jEEEn in仁送送j乏i(i+1) 一 1卄+匸1 .n( n+1)(2 n+1)+ 1 . n(n+1)for (int i=1; i=n; i+)i=t j=t ki zi2 2-2 i亠2 6 2 2for (

3、int j=1; j=i; j+)n(n +1)( n*2)for (int k=1; k=j; k+)6x=x+v;1.3指出下列个算法的功能，并求其时间复杂度。(1) int sum1(i nt n)int p=1,s=0;for (int i=1;i=n; i+) p*= i； s+=p; return s; int sum2 (int n) int s=0;for ( int i=1; i=n; i+) int p=1;for (int j=1; j=i; j+) p*=j; s+=p;解：n(1) i! , T(n)=0(n)n i!,T(n)=O(n2)iV结束return s;1

4、.4算法设计1枚是假的，伪币与真币重量略有不同。如何借用一架有3枚硬币，其中有 天平，找出伪币？以流程图表示算法。上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。1.设a, b, c为3个整数，求其中位于中间值的整数。第2章线性表1.设计算法：在顺序表中删除值为 e的兀素，删除成功，返回1; 否则，返回0。int Sqlist:DeleteElem( T e ) for (i=1; i=length; i+) /按值顺序查找* i可从0开始if (elemi-1= =e)/ 找到，进行删除操作 for ( j=i; jlength; j+)/ ai 至 an 依次前移Ele

5、mj-1 = elemj;length - - ;/ 表长减一return 1 ;删除成功，返回1return 0 ;/未找到，删除不成功，返回02.分析顺序表中兀素疋位算法int SqList:Locate ( T e )的时间复杂度。解：设表长为n,等概率下，每个兀素被定位的概率为：p-1/n疋位成功第i个兀素，需比较i次、二 1 .1.1 n(n + 1) n + 1f (n) _迟_ 迟 i -im nn i二n223对于有头结点的单链表，分别写出定位成功时，实现下列定位 语句序列。(1)定位到第i个结点ai ；p=head; j=0;while ( p & jn ext; j+;定位

6、到第i个结点的前驱a-1 ；p=head; j=0;while ( p & j next; j+;(3)定位到尾结点；p=head;while ( p -next )p=p-n ext;(4)定位到尾结点的前驱。p=head;while ( p-n ext- next )p=p-n ext;4描述一下二个概念的区别：头指针，头结点，首兀结点。并给头指针：是一个指针变量，里面存储的是链表中首结点的地址，并以此来标识一个链表。予图示。头结点：附加在第一个兀素结点之前的一个结点，头指针指向头结点。首兀结点：指链表中的第一个兀素结点。头指针头结点首(元)结点尾(元)结点aia少丨Tn a5.对于无头结

7、点单链表，给出删除第i个结点的算法描述。template T LinkList:Delete(int i)template T LinkList:Delete(int i) /在单链表上删除第i个数据元素if ( head=NULL) throw 表空！”;/ 空表，不能删 else if ( i=1) /删除第1个兀素p=Head; x=p-data;/保存被删兀素值Head= p-n ext ;delete p ;else /兀素疋位到第 ai-1p=Head; j=1 ; /疋位查找起始位置while p- next & jn ext; j+ ; if ( !p- next | ji-1

8、 ); /定位失败throw删除位置不合理；else /定位成功，进行结点删除q=p-n ext;x=pdata;p-n ext=q-n ext; delete q;retrun x; /返回被删除兀素值/#6.用教材定义的顺序表的基本操作实现下列操作： template int DeleteElem(SqList L, T e)#include SqList.h “ template int DeleteElem(SqList L, T e) /i = L.LocateElem(e) ; / 按值杳找if (!i)/未找到return 0;else/找到delete (i) ; /删除被找到

9、的元素 7.已知L是有表头结点的单链表，且P结点既不是首兀结点，也不是尾结点，试写出实现下列功能的语句序列。(1) 在P结点后插入S结点；(2) 在P结点前插入S结点；(3) 在表首插入S结点；(4) 在表尾插入S结点.【解】(1) s-next=p-next; p-next=s; q=L;while( q-n ext!=p)q=q-n ext;s-next=p 或 q-next ;q _n ext=s;(3) s-n ext=L-n ext; L-n ext=s; q=L;while( q-n ext!=NULL)q=q-n ext;s-n ext= q-n ext ; q-n ext=s;

10、上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。编程实现：删除单链表中值为e的兀素。第3章栈与队列1.铁路进行列车调度时，常把站台设计 成栈式结构的站台，如右图所示。试问： 若进站的六辆列车顺序如上所述,那么是否能够得到325641和154623的出站序 列，如果不能，说明为什么不能；如果能, 说明如何得到（即写出”进栈”或”出栈”的 序列）。2.简述以下算法的功能(栈的兀素类型为int )。 status algo_1( SqStack S ) int i, n, A 255;n=0;while (!S.StackEmpty() ) n+; An= S.Pop();for

11、 ( i=1; i= n ; i+) S.Push(Ai);(2) status algo_2(SqStack S, int e) SqStack T;int d;while (!S.tackEmpty()d = S. Pop();if (d!=e ) T.Push(d);while (!T.StackEmpty()d=T .P op();T.Push(d);解：(1)借助一个数组，将栈中的兀素逆置。(2)借助栈T,将栈S中所有值为e的数据元素删除之。3.编写一个算法，将一个非负的十进制整数 N转换为B进制数， 并输出转换后的结果。 当N=248D，B分别为8和16时，转换后 的结果为多少？#

12、include stack.h”int NumTrans( int N, int B)/十进制整数 N转换为B进制数stack S; / 建立一个栈while( N!=0) / N 非零i=N%B ; /从低到高，依次求得各位N=N/B;S.push(i); / 各位入栈 while ( !S.StackEmpty() / 栈不空 i= S.pop();If (i9) i= 10-i;cout S.pop(); /依次出栈，得到从咼到低的输出结果/#4借且栈，设计算法：假设一个算术表达式中包含“(、” “括号，对一个合法的数学表达式来说，括号“(和 “)应是相互匹配的。若匹配，返回1 ;否则，

13、返回0。解：以字符串存储表达式，也可以边输入边判断。顺序扫描表达式，左括号，入栈；右括号，如果此时栈空，表示多右括号，不匹 配；如果栈不空，出栈一个左括号。扫描结束，如果栈空，表示括号匹配；否则，括 号不匹配，多左括号。int blank_match(char *exp)用字符串存表达式SqStack s;/ 创建一个栈char *p=exp; 工作指针p指向表达式首 while ( *p!= = ) /不是表达式结束符switch(p) case (:左括号，入栈s.push(ch); break;case )/右括号if (s.StackEmpty() return 0;/ 栈空，不匹配，

14、多右括号else s.Pop(); break; / 左括号出栈/switchp+; /取表达式下一个字符 / whileif (!s.StackEmpty() / 表达式结束，栈不空return 0 ; /不匹配，多左括号 elsereturn 1 ; / 匹配 /#5.简述栈和队列的逻辑特点，各举一个应用实例。6.与出卜列中缀表达式的后缀表达式。(1) A-B+C-D+(1)-A+B-C+D(2) AB+D*EFAD*+/+C+(2)(A+B)*D+E/(F+A*D)+C(3) AB&EF ! | A&B|!(EF)7计算后缀表达式：4 5 * 3 2 + -的值。解:158将下列递推过程

15、改写为递归过程。解:void recurisi on (i nt j)void recurs ion( int n ) if (j1)int i=n; cour1) recurisi on (j-1);cout x;cin x;if (x=0) sum=0;while (x) else S.push(x);test(sum); sum+=x; cin x; coutsum;sum=0;coutsum;while ( x=S.pop() ) sum+=x; coutsum; II10.简述以下算法的功能（栈和队列的兀素类型均为int ）。解：禾U用栈，将队列中的兀素逆置void algo (Qu

16、eue &Q)Stack S; / 创建一个栈int d;while (!Q.QueueEmpty()d=DeQueue(Q); S. Push(d); while (!S.StackEmpty()d=S.Pop();Q.E nQueue(d);12.假设以数组sem存放循环队列的兀素，冋时设变量rear和front分别作为队首、队尾指针，且队首指针指向队首前一个位置， 队尾指针指向队尾兀素处，初始时，rear=fornt=-1。与出这样设计的循环队列入队、出队的算法。解：米用教材队空与队满判别方法。为了区分队空与队满条件，牺牲一个兀素空间。 即：rear=front, 为队空；rear=(f

17、ront+1)%m，为队满。template void EnQueue( T Se, T e, int m ) / 入队if ( rear+1)%m =fornt ) / 队满，不能插入throw队满，不能插入！”else rear = (rear+1) % m ; /队尾指针后移serear=e; / 兀素入队return ;/#template T DnQueue( T Se, int m ) / 出队if ( rear= =fornt )/队空，不能出队！throw队空，不能出队！”else front = (fron t+1)%m ; II指针后移，指向队首兀素 e =sefront;

18、 II取队首兀素return e ;/#上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。1借助栈，实现单链表上的逆置运算。1试问执行以下函数会产生怎样的输出结果？void dem on strate()StrAssig n( s, THIS IS A BOOK);StrRep ( s, StrSub(s, 3, 7), ESE ARE);StrAssig n( t, StrCo neat ( s, S);StrAssig n(u, XYXYXYXYXYXY);StrAssig n(v, StrSub ( u, 6, 3 );StrAssig n(w, W);eout “ t

19、=” tendl;eout “v= ” v;eout “ u= ” StrRep(u, v, w); / dem on strate解: t= THESE ARE BOOKS v= YXYw= XWXWXW2.设字符串 S= aabaabaabaae ， P= aabaae1）给出S和P的next值和nextval值；2）若S作主串，P作模式串，试给出 KMP算法的匹配过程。1) S 的 next 与 nextval 值分别为 012123456789 和 002002002009， p 的 next 与 nextval 值分别为 012123 和 0020032) 利用KMP算法的匹配过程：

20、第一趟匹配：aabaabaabaaeaabaae(i=6,j=6)第二趟匹配： aabaabaabaae(aa)baae第三趟匹配：aabaabaabaae( 成功)(aa)baae3.算法设计 串结构定义如下：struet SStri ngchar *data;/ 串首址int len;/ 串长int StrSize ;/存放数组的最大长度.；(1)编写一个函数，计算一个子串在一个字符串中出现的次数， 如果不出现，则为 0。int str_co un t (SStri ng S, SStri ng T )解：int str_cou nt (SStri ng S, SStri ng T) in

21、t i, j,k, coun t=0;for ( i=0; S.datai; i+)for ( j=i, k=0; (S.dataj=T.datak; j+,k+) if ( k= =T.le n-1)count + +;retur n count; 编写算法，从串s中删除所有和串t相同的子串。解：int SubString_Delete(SString &s, SString t )从串s中删除所有与t相同的子串，并返回删除次数for ( n=0, i=0; i=s.le n-t.le n; i+ )for ( j=0; j t.len)/找到了与t匹配的子串for ( k = i; kse

22、n-t.le n; k+ )sk=sk+t.len; / 左移删除s.len-=t.le n ;n+; II被删除次数增1/for return n;/Delete_SubStri ng(2)编写一个函数，求串s和串t的一个最长公共子串。void maxcomstr( SStri ng *s, SStri ng *t)解：void maxcomstr( SString *s, SString *t) in t i ndex=0,le n1=0, i,j,k,le n2;i=0;/作为扫描s的指针while ( i s.len) j = 0;/作为扫描t的指针while ( j len1) /

23、将较大长度者给 index 和 lenlin dex=i;len 1=le n2;j + = len2; /ifelse j+;/whilecout最长公共子串：for ( i=0; ile n1; i+;)cout8+7=45003 一个稀疏矩阵如图所示-030000020500(1) 给出二元组存储示意图；A =000000(2) 给出带行指针向量的链式存储示意图；9 0 0 0 0 4翅(3) 十字链表存储示意图。M dataijeA01234013112*013A135112*235 A309A351309b-451 AM.mu M.nu (1) M.tU465(2)A. cheadA. rheadA1A.mu 4 IA.nu 6o I 1 I 31 A1 1 21 1 35A.tu 5AA