2022年数据结构习题整理 .pdf

第 1 章 绪1.1 有下列几种二元组表示的数据结构，试画出它们分别对应的图形表示，并指出它们分别属于何种结构。(1) A= ( D ，R )，其中， D = a1，a2，a 3，a4 ， R= (2) B= ( D ，R )，其中， D = a ，b，c，d，e， R= (a ，b)，(b，c)，(c，d)，(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) (4) K= ( D，R ) ，其中， D = 1，2，3，4，5，6 ， R= ， ， (1) 集合(2) 线性表abcde(3) 树fgabcde(4) 图1453621.2 设 n 为正整数，求下列各程序段中的下划线语句的执行次数。(1) i=1; k=0 while(i=n-1) k+=10*i ; i+; (2) for (int i=1; i=n; i+) for (int j=1; j=n; j+) cij=0; for (int k=1; k=n; k+) cij=cij+aik*bkj 解：(1) n-1 (2) ninjnkn11131(3) x=0; y=0; for (int i=1; i=n; i+) for (int j=1; j=i; j+) for (int k=1; k=j; k+) x=x+y; (3) 62)1)(nn(n21)(216) 12)(1(2121212) 1(1112111111nnnnniiiijnininiijjkniijni名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 21 页 - - - - - - - - - 1.3 指出下列个算法的功能，并求其时间复杂度。(1) int sum1(int n) int p=1,s=0; for (int i=1;i=n; i+) p*= i; s+=p; return s; (2) 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; return s; 解：(1) n1ii!, T(n)=O(n) (2) n1ii!, T(n)=O(n2) 1.4 算法设计有 3 枚硬币，其中有1 枚是假的，伪币与真币重量略有不同。如何借用一架天平，找出伪币？以流程图表示算法。上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。1. 设 a, b, c 为 3 个整数，求其中位于中间值的整数。开始A=B ？A=C ？A是伪币C是伪币B是伪币结束是是否否名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 21 页 - - - - - - - - - 第 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 依次前移Elemj-1 = elemj; length - - ; / 表长减一return 1 ; /删除成功，返回1 return 0 ; / 未找到，删除不成功，返回0 2. 分析顺序表中元素定位算法int SqList:Locate ( T e ) 的时间复杂度。解：设表长为n，等概率下，每个元素被定位的概率为：p=1/n 定位成功第i 个元素，需比较i 次212)1(111)(11nnnnininnfnini3.对于有头结点的单链表，分别写出定位成功时，实现下列定位语句序列。(1) 定位到第i 个结点 ai；p=head; j=0; while ( p & jnext; j+; (2) 定位到第i 个结点的前驱ai-1；p=head; j=0; while ( p & jnext; j+; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 21 页 - - - - - - - - - (3) 定位到尾结点；p=head; while ( p -next ) p=p-next; (4) 定位到尾结点的前驱。p=head; while ( p-next-next ) p=p-next; 4.描述一下三个概念的区别：头指针，头结点，首元结点。并给予图示。头指针：是一个指针变量，里面存储的是链表中首结点的地址，并以此来标识一个链表。头结点：附加在第一个元素结点之前的一个结点，头指针指向头结点。首元结点：指链表中的第一个元素结点。头结点. aa1a2n 首 ( 元 )结点尾 ( 元 )结点头指针名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 21 页 - - - - - - - - - 5. 对于无头结点单链表，给出删除第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-next ; delete p ; else / 元素定位到第ai-1p=Head; j=1 ; / 定位查找起始位置while p-next & jnext; j+ ; if ( !p-next | ji-1 ); / 定位失败throw “ 删除位置不合理” ; else / 定位成功，进行结点删除q=p-next; x=pdata; p-next=q-next; 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) ; / 按值查找名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 21 页 - - - - - - - - - if (!i) / 未找到return 0; else / 找到delete (i) ; / 删除被找到的元素 7. 已知 L 是有表头结点的单链表，且P 结点既不是首元结点，也不是尾结点，试写出实现下列功能的语句序列。(1) 在 P 结点后插入S 结点；(2) 在 P 结点前插入S 结点；(3) 在表首插入S结点；(4) 在表尾插入S结点 . 【解】(1) s-next=p-next; p-next=s; (2) q=L; while( q-next!=p) q=q-next; s-next=p 或 q-next ; q -next=s; (3) s-next=L-next; L-next=s; (3) q=L; while( q-next!=NULL) q=q-next; s-next= q-next ; q-next=s; 上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。编程实现：删除单链表中值为e的元素。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 21 页 - - - - - - - - - 第 3 章 栈与队列1. 铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。试问：若进站的六辆列车顺序如上所述, 那么是否能够得到325641 和 154623 的出站序列 , 如果不能 , 说明为什么不能; 如果能 , 说明如何得到(即写出 进栈 或出栈 的序列 )。解： 325641 可以154623 不可以。123456名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 21 页 - - - - - - - - - 2. 简述以下算法的功能（栈的元素类型为 int ）。(1) status algo_1( SqStack S ) int i, n, A 255; n=0; while (!S.StackEmpty() ) n+; An= S.Pop(); for ( 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.Pop(); T.Push(d); 解： (1) 借助一个数组，将栈中的元素逆置。(2) 借助栈 T，将栈 S中所有值为e 的数据元素删除之。3.编写一个算法，将一个非负的十进制整数N 转换为 B 进制数，并输出转换后的结果。当 N=248D ，B 分别为 8 和 16 时，转换后的结果为多少？#include “ stack.h”int NumTrans( int N, int B) / 十进制整数N 转换为 B 进制数stack S; / 建立一个栈while( N!=0) / N非零i=N%B ; / 从低到高，依次求得各位名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 21 页 - - - - - - - - - N=N/B; S.push(i); / 各位入栈while ( !S.StackEmpty() / 栈不空 i= S.pop(); If (i9) i= A +10-i; cout S.pop(); / 依次出栈，得到从高到低的输出结果 /# 4 借且栈，设计算法：假设一个算术表达式中包含“ ( ”、“) ”括号，对一个合法的数学表达式来说，括号“( ”和“) ”应是相互匹配的。若匹配，返回1；否则，返回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; / 栈空，不匹配，多右括号else s.Pop(); break; / 左括号出栈/switch p+; / 取表达式下一个字符 / while if (!s.StackEmpty() / 表达式结束，栈不空名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 21 页 - - - - - - - - - return 0 ; /不匹配，多左括号else return 1 ; / 匹配 /# 5. 简述栈和队列的逻辑特点，各举一个应用实例。6. 写出下列中缀表达式的后缀表达式。(1)-A+B-C+D (2)(A+B)*D+E/(F+A*D)+C (3) A&B|!(EF) (1) A-B+C-D+ (2) AB+D*EFAD*+/+C+ (3) AB&EF ! | 7.计算后缀表达式：4 5 * 3 2 + - 的值。解： 15 8.将下列递推过程改写为递归过程。void recursion( int n ) int i=n; while( i1) cout1) courx; if (x=0) sum=0; else test(sum); sum+=x; coutx; while (x) S.push(x); cinx; sum=0; coutsum; while ( x=S.pop() ) sum+=x; coutsum; / 10. 设计求一元多项式pn(x)= p0 + p1x + p2x2 +,+pnxn 递归算法。解： Pn(x) = (.( (anx + an-1) x+ an-2) x+. ) x+ a ) x+a0 / 递归定义An+1 =an , an-1 , an-2 ,.，a0 / 系数矩阵float f ( float x, float A, int n ) if ( n=0) p =A0 ; else p= f ( x , A, n-1)*x + An; return p; /# 11. 简述以下算法的功能（栈和队列的元素类型均为 int）。解：利用栈，将队列中的元素逆置名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 21 页 - - - - - - - - - void algo (Queue &Q) Stack S; /创建一个栈int d; while (!Q.QueueEmpty() d=DeQueue(Q); S.Push(d); while (!S.StackEmpty() d=S.Pop();Q.EnQueue(d); 12. 假设以数组sem存放循环队列的元素，同时设变量rear 和front 分别作为队首、 队尾指针， 且队首指针指向队首前一个位置，队尾指针指向队尾元素处，初始时，rear=fornt=-1 。写出这样设计的循环队列入队、出队的算法。解：采用教材队空与队满判别方法。为了区分队空与队满条件，牺牲一个元素空间。即： rear=front ， 为队空； rear=(front+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 “ 队空，不能出队!”名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 21 页 - - - - - - - - - else front = (front+1)%m ; / 指针后移，指向队首元素e =sefront; / 取队首元素return e ; /# 13. 设有一个双端队列，元素进入该队列的顺序是1,2，3,4。试分别求出满足下列条件的输出序列。(1) 能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列；(2) 能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；(3) 既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得至的输出序列。解：允许在一端进行插入和删除，但在另一端只允许插入的双端队列叫做输出受限的双端队列， 允许在一端进行插入和删除，但在另一端只允许删除的双端队叫做输入受限的双端队列。(1) 输出受限双端队列能得到的输出序列有：4 1 3 2 4 2 3 1 (2) 输入受限双端队列不能得到输出序列有：4 2 1 3 4 2 3 1 (3) 输入受限和输出受限的双端队列不得到的输出序列有：4 2 1 3 上机练习题要求：给出问题分析、 算法描述、 源程序及运行截图，在线提交。1.借助栈，实现单链表上的逆置运算。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 21 页 - - - - - - - - - 第 4 章 串1. 试问执行以下函数会产生怎样的输出结果? void demonstrate( ) StrAssign( s, THIS IS A BOOK); StrRep ( s, StrSub(s, 3, 7), ESE ARE); StrAssign( t, StrConcat ( s, S ) ) ; StrAssign(u, XYXYXYXYXYXY ); StrAssign(v, StrSub ( u, 6, 3 ) ); StrAssign(w, W); cout“t=” tendl; cout“v=” v; cout“u=” StrRep(u, v, w); / demonstrate 解： t= THESE ARE BOOKS v= YXY w= XWXWXW 2. 设字符串S=aabaabaabaac ，P=aabaac 1）给出 S和 P的 next 值和 nextval值；2）若 S作主串， P作模式串，试给出KMP算法的匹配过程。1）S的 next 与 nextval值分别为 012123456789 和 002002002009，p 的 next 与 nextval值分别为 012123 和 002003 2）利用 KMP算法的匹配过程：第一趟匹配： aabaabaabaac aabaac(i=6,j=6) 第二趟匹配： aabaabaabaac (aa)baac 第三趟匹配： aabaabaabaac (成功 ) (aa)baac 3. 算法设计串结构定义如下：struct SString 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 21 页 - - - - - - - - - char *data；/ 串首址int len; / 串长int StrSize ； / 存放数组的最大长度. ; (1) 编写一个函数，计算一个子串在一个字符串中出现的次数，如果不出现，则为0。int str_count (SString S, SString T ) 解： int str_count (SString S, SString T) int i, j,k, count=0; for ( i=0; S.datai; i+) for ( j=i, k=0; (S.dataj=T.datak; j+,k+) if ( k= =T.len-1) count + +; return count; (2) 编写算法，从串s中删除所有和串t 相同的子串。解：int SubString_Delete(SString &s, SString t ) /从串 s 中删除所有与t 相同的子串 ,并返回删除次数 for ( n=0, i=0; i=s.len-t.len; i+ ) for ( j=0; j t.len) / 找到了与t 匹配的子串 for ( k = i; ks.len-t.len; k+ ) sk=sk+t.len; / 左移删除名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 21 页 - - - - - - - - - s.len-=t.len ; n+; / 被删除次数增1 /for return n; /Delete_SubString(2) 编写一个函数，求串s 和串 t 的一个最长公共子串。void maxcomstr( SString *s, SString *t) 解： void maxcomstr( SString *s, SString *t) int index=0,len1=0, i,j,k,len2; i=0; / 作为扫描 s 的指针while ( i s.len) j = 0; / 作为扫描 t 的指针while ( j len1) / 将较大长度者给index 和 len1 index=i; len1=len2; j + = len2; /if else j+; /while cout” 最长公共子串：”for ( i=0; ilen1; i+; ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 21 页 - - - - - - - - - couts.dataindex+1; / # 1. 已知下列字符串a = THIS, f = A SAMPLE, c = GOOD, d =NE, b = , s = StrConcat(a,StrConcat(StrSub(f,2,7),StrConcat(b, StrSub (a,3,2), t = StrRep(f, StrSub (f,3,6),c), u = StrConcat(StrSub(c,3,1),d), g = IS, v = StrConcat(s,StrConcat(b,StrConcat(t,StrConcat(b,u), 试问 : s, t, v, StrLength(s), StrIndex(v,g), StrIndex(u,g) 各是什么 ? 已知： s=(XYZ)+* ，t=(X+Z)*Y 。试利用下列运算，将s 转化为 t。联接： StrConcat ( &S,T ) 求子串： (char *) StrSub( S, i, len ) 置换： StrRep ( &S, T, R ) 上机练习题要求：给出问题分析、 算法描述、 源程序及运行截图，在线提交。串结构定义如下：struct SString char *data；/ 串首址int len; / 串长int StrSize； / 存放数组的最大长度. ; 求：串 S 所含不同字符的总数和每种字符的个数，不区分英文字名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 21 页 - - - - - - - - - 母的大小写。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 21 页 - - - - - - - - - 第 5 章 数组与压缩矩阵1. 假设有二维数组A6 8，每个元素用相邻的6 个字节存储，存储器按字节编址。已知A 的起始存储位置(基地址 )为 1000，计算：(1) 数组A 的体积（即存储量）; (2) 数组A 的最后一个元素a57的第一个字节的地址; (3) 按行存储时，元素a14的第一个字节的地址; (4) 按列存储时，元素a47的第一个字节的地址。解： (1）686 = 288Byte (2）1000+288-6=1282 ；(3）1000+(18+4)6=1072 (4）1000+(76+4)6=1276 2. 假设按低下标优先存储整数数组A9 3 5 8时，第一个元素的字节地址是 100，每个整数占四个字节。问下列元素的存储地址是什么？(1) a0000(2) a8247解： (1) 100 (2) 100+8358+2 5 8+4 8+7=4500 3一个稀疏矩阵如图所示(1) 给出三元组存储示意图；(2) 给出带行指针向量的链式存储示意图；(3) 十字链表存储示意图。(1) 110ei153903531213jM.data M.mu4M.nu6M.tu501234(2) (3) 013309112135A.rheadA.mu 4A.nu 6A.tu 5A.chead351013112235309451A 030000020500000000900001A = 4 6名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 21 页 - - - - - - - - - 4. 算法设计：一个按行优先存储的n*n 矩阵，就地转置。解： void trans ( ElemType A, int n) int i, j; ElemType tmp; for ( i = 0; in;i+) for ( j=0;j x ) j - - ; else i + +; out” i=” i ” ,j=” jendl; /# 上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。选用数组作为数据结构，编程求解Josephus问题。手工推演下列测试用例，并检查程序的正确性。人数 n 开始报数的人s 密码 m 9 1 5 9 1 0 殷习P30 2-2 n=,s=1,m=5 时，出局顺序为： 5,1，7,4，3,6，9, 2，8 m=0， 报错， m=0 是无效参数；m=10，时间代价最大名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 21 页 - - - - - - - - - 9 1 10 出局顺序为： 1,3,6,2,9,5,7,4,8 源程序Void Josephus(in A, int n,s,m) int i, j, k, tmp; if (m=0) cerr” m=0 是无效的参数！” endl; return; for(i=0;i=1;k-) / 逐个出局，执行n-1 次；if (i=k) i=0; / 第 n 个人，下标为0 i = (i+m-1)%k; / 寻找出局位置if ( i ! = k-1 ) / 把出局者移到最后tmp=Ai; / 保留出局序号for ( j = i; j k-1; j+ ) Aj =Aj+1 ; / 第 i 至第 k 个元素依次前移Ak-1=tmp; / 出局者移至k-1 处 for(k=0;kn/2;k+) /全部逆置，得到出局序列。Ak=An-k-1; An-k-1=tmp; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 21 页 - - - - - - - - -