西南大学《数据结构》网上作业及参考答案.docx
- 文档编号:4809429
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:20
- 大小:27.09KB
西南大学《数据结构》网上作业及参考答案.docx
《西南大学《数据结构》网上作业及参考答案.docx》由会员分享,可在线阅读,更多相关《西南大学《数据结构》网上作业及参考答案.docx(20页珍藏版)》请在冰点文库上搜索。
西南大学《数据结构》网上作业及参考答案
1:
[论述题]
1、何时选用顺序表、何时选用链表作为线性表的存储结构为宜?
2、为什么在单循环链表中设置尾指针比设置头指针更好?
3、确定下列算法中输出语句的执行次数,并给出算法的时间复杂度。
(1)voidcombi(intn)
{ intI,j,k;
for(I=1;I<=n;I++)
for(j=I+1;j<=n;j++)
for(k=j+1;k<=n;k++)
cout<
citation>
(2)voidbinary(intn)
{ while(n){
cout< n=n/2; }} 4、常用的存储表示方法有哪几种? 5.分析以下程序段的时间复杂度。 a=0;b=1;① for(i=2;i〈=n;i++)② { s=a+b;③ b=a;④ a=S;⑤ } 6.对于一个栈,给出输入项A,B,C。 如果输入项序列由A,B,C组成,试给出全部可能的输出序列 7、已知一个顺序表中的元素按元素值非递减有序排列,编写一个函数删除表中多余的值相同的元素。 参考答案: 1、答: 在实际应用中,应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构,通常有以下几方面的考虑: 1.基于空间的考虑。 当要求存储的线性表长度变化不大,易于事先确定其大小时,为了节约存储空间,宜采用顺序表;反之,当线性表长度变化大,难以估计其存储规模时,采用动态链表作为存储结构为好。 2.基于时间的考虑。 若线性表的操作主要是进行查找,很少做插入和删除操作时,采用顺序表做存储结构为宜;反之,若需要对线性表进行频繁地插入或删除等的操作时,宜采用链表做存储结构。 并且,若链表的插入和删除主要发生在表的首尾两端,则采用尾指针表示的单循环链表为宜。 2、答: 尾指针是指向终端结点的指针,用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便,设一带头结点的单循环链表,其尾指针为rear,则开始结点和终端结点的位置分别是rear->next->next和rear,查找时间都是O (1)。 若用头指针来表示该链表,则查找终端结点的时间为O(n)。 3、 (1)I取值范围从1~n,j取值范围从I+1~n,k取值范围从j+1~n,情况如下表所示: I值 j值 k值 输出语句的执行次数 1 2 3,4,…,n n-2 … … … n-1 n 1 n / / 2 3 4,5,…,n n-3 … … … n-1 n 1 n / / … … … … n-2 n-1 n 1 n / / n-1 n / / n / / / 所以,输出语句共执行次数为((n-2)+(n-3)+…+1)+((n-3)+(n-4)+…+1)+…+1 =(n-1)(n-2)/2+(n-2)(n-3)/2+…+1 =(((n-1)2+(n-2)2+(n-3)2+…+12)-((n-1)+(n-2)+(n-3)+….+1))/2 =((n-1)n(2n-1)/6-n(n-1)/2)/2 =(n(n-1)(2n-4))/12=n(n-1)(n-2)/6 (2)ceil(log2n); 4、 常用的存储表示方法有四种: 顺序存储方法: 它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现。 由此得到的存储表示称为顺序存储结构。 链接存储方法: 它不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系是由附加的指针字段表示的。 由此得到的存储表示称为链式存储结构。 索引存储方法: 除建立存储结点信息外,还建立附加的索引表来标识结点的地址。 散列存储方法: 就是根据结点的关键字直接计算出该结点的存储地址。 1: [论述题] 1、已知L1和L2分别指向两个单链表的头结点,且已知其长度分别为m和n。 试写一算法将这两个链表连接在一起,请分析你的算法的时间复杂度。 2、假设某个单向循环链表的长度大于1,且表中既无头结点也无头指针。 已知s为指向链表中某个结点指针,试编写算法在链表中删除指针s所指结点的前驱结点。 3、指出以下算法中的错误和低效之处,并把它改写为一个既正确又高效的算法。 StatusDeleteK(SqList&a,intI,intk){//本过程从顺序存储结构的线性表a中删除第I个元素起的k个元素。 if(I<1||k<0||I+k>a.length)returnERROR; else{ for(count=1;count删除一个元素 for(j=a.Length;j>=I+1;j--)a.elem[j-1]=a.elem[j]; a.length--; } rreturnOK; }//DeleteK 4、假设稀疏矩阵A采用三元组表示,编写一个函数计算其转置矩阵B,要求B也采用三元组表示 5、设二维数组A5*6的每个元素占4个字节,已知Loc(a00)=1000,A共占多少个字节? A的终端结点a45的起始地址为多少? 按行和按列优先存储时,a25的起始地址分别为多少? 6、编写下列算法(假定下面所用的串均采用顺序存储方式,参数ch、ch1和ch2均为字符型): ∙将串r中所有其值为ch1的字符换成ch2的字符。 ∙将串r中所有字符按照相反的次序仍存放在r中。 ∙从串r中删除其值等于ch的所有字符。 ∙从串r1中第index个字符起求出首次与字符r2相同的子串的起始位置。 ∙从串r中删除所有与串r3相同的子串(允许调用第(4)小题的函数和第(3)小题的删除子串的函数)。 参考答案: 1、参考答案 LinkListLink(LinkListL1,LinkListL2) { //将两个单链表连接在一起 ListNode*p,*q; p=L1; q=L2; while(p->next)p=p->next;//查找终端结点 p->next=q->next;//将L2的开始结点链接在L1之后 returnL1; } 本算法的主要操作时间花费在查找L1的终端结点上,与L2的长度无关,所以本算的法时间复杂度为: m+1=O(m) 2、参考答案 voidDelprior(Links){ p=q=s; while(p->next! =s){ q=p; p=p->next; } q->next=s; delete(p); } 3、参考答案 更正: for(j=I+k;j<=a.Length;j++)a.elem[j-k]=a.elem[j]; a.Length=a.Length? k; 1: [论述题] 1、算法的时间复杂度仅与问题的规模相关吗? 2、 下列程序段带标号语句的频度和时间复杂度。 (1)I=0; while(I =K) I++;//语句3 return(I); (2)n为不小于1的整数(设k的初值等于1) voidpp(intk) { if(k==n)//语句1 for(I=0;I语句2 printf(a[I]);//语句3 else {for(I=k-1;I语句4 a[I]=a[I]+I;//语句5 pp(k+1);//语句6 } }//pp 3、常用的存储表示方法有哪几种? 参考答案: 1、不,事实上,算法的时间复杂度不仅与问题的规模相关,还与输入实例中的元素取值等相关,但在最坏的情况下,其时间复杂度就是只与求解问题的规模相关的。 我们在讨论时间复杂度时,一般就是以最坏情况下的时间复杂度为准的。 2、 (1)这个算法完成在一维数组a[n]中查找给定值k的功能。 语句三的频度不仅与问题的规模n有关,还与输入实例中a的各元素取值以及k的取值相关,即与输入实例的初始状态复杂有关。 若a中没有与k相等的元素,则语句三的频度为n;若a中的第一个元素a[0]等于k,则语句三的频度是常数0。 在这种情况下,可用最坏情况下的时间复杂度作为时间复杂度。 在此例中即为O(n)。 这样做的原因是: 最坏情况下的时间复杂度是在任何输入实例上运行时间的上界。 有时,也可能选择将算法的平均(或期望)时间复杂度作为讨论目标。 所谓的平均时间复杂度是指所有可能的输入实例以等概率出现的情况下算法的期望运行时间与问题规模的数量级的关系。 此例中,以k出现在任何位置的概率相同,都为1/n,则语句三的执行频度为[0+1+2+…+(n-1)]/n=(n-1)/2。 它决定了此程序段的平均时间复杂度的数量级为f(n)=n,记作O(n)。 (2)在计算包含调用语句的算法的语句频度时,需考虑到调用发生时在被调用算法中各语句的执行情况。 本题所示的递归调用较之非递归调用的分析更为复杂。 由于k等于n是算法的出口条件,不妨首先分析算法pp(n)的简单情况,这时各语句的执行频度分别为: 1,n+1,n,0,0,0;而当k=n-1,n-2,…,1时,语句的执行情况和调度情况,如下表所示。 K值 不考虑调用时各语句的执行频度 调用情况 语句1 语句2 语句3 语句4 语句5 语句6 n 1 n+1 n 0 0 0 / n-1 1 0 0 3 2 1 pp(n) n-2 1 0 0 4 3 1 pp(n-1) … … … … … … … … 1 1 0 0 n+1 n 1 pp (2) 对于k=1即pp (1)而言,各语句的执行次数还须将调用pp (2)时的执行次数累计到内,pp (2)各语句的执行次数又须将调用pp(3)时执行次数累计到内,……由此可的语句频度如下: 语句1: 1+1+…+1=n 语句2: 0+0+…+0+(n+1)=n+1 语句3: 0+0+…+0+n=n 语句4: (n+1)+n+…+3=(n-1)(n+4)/2 语句5: n+(n-1)+…+2=(n-1)(n+2)/2 语句6: 1+1+….+1+0=n-1 算法的时间复杂度可以基于频度最大的语句,应为O(n2)。 4、 常用的存储表示方法有四种: 顺序存储方法: 它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现。 由此得到的存储表示称为顺序存储结构。 链接存储方法: 它不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系是由附加的指针字段表示的。 由此得到的存储表示称为链式存储结构。 索引存储方法: 除建立存储结点信息外,还建立附加的索引表来标识结点的地址。 散列存储方法: 就是根据结点的关键字直接计算出该结点的存储地址。 1: [论述题] 1、假设在二叉链表中增加两个域: 双亲域(parent)以指示其双亲结点;标志域(mark取值0..2)以区分在遍历过程中到达该结点时应继续向左或向右或访问该结点。 试以此存储结构编写不用栈进行后序遍历的递推形式的算法。 2、 设有三对角矩阵An*n,将其三条对角线上的元素逐行地存储到向量B[0…3n-3]中,使得B[k]=aij,求: (1)用I,j表示k的下标变换公式。 (2)用k表示I,j的下标变换公式。 3、 写一算法voidStrReplace(char*T,char*P,char*S),将T中首次出现的子串P替换为串S。 注意: S和P的长度不一定相等。 可以使用已有的串操作。 4、 设两个栈共享空间v[0..m-1],两栈的栈底分别设在向量的两端,且每个元素占一个分量。 试设计这两个栈的插入和删除算法。 5、若以1234作为双端队列的输入序列,试分别求出满足以下条件的输出序列: (1)能由输入受限的双端队列得到,但不能由输出受限的双端队列得到的输出序列; (2)能由输出受限的双端队列得到,但不能由输入受限的双端队列得到的输出序列; (3)既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列 6、 已知单链表L是一个递增有序表,试写一高效算法,删除表中值大于min且小于max的结点(若表中有这样的结点),同时释放被删结点的空间,这里min和max是两个给定的参数。 请分析你的算法的时间复杂度。 7、 简述以下算法的功能。 (1)voidDemo1(SeqStack*S){ intI;arr[64];n=0; while(StackEmpty(S))arr[n++]=Pop(S); for(I=0,I }//Demo1 (2)SeqStackS1,S2,tmp; DataTypex; …//假设栈tmp和S2已做过初始化 while(! StackEmpty(&S1)){ x=Pop(&S1); Push(&tmp,x); } while(! StackEmpty(&tmp)){ x=Pop(&tmp); Push(&S1,x); Push(&S2,x); (3)voidDemo2(SeqStack*S,intm){ //设DataType为int型 SeqStackT;intI; InitStack(&T); while(! StackEmpty(S)) if((I=Pop(S))! =m)Push(&T,I); while(! StackEmpty(&T)){ I=Pop(&T);Push(S,I); }} (4)voidDemo3(CirQueue*Q){ //设DataType为int型 intx;SeqStackS; InitStack(&S); while(! QueueEmpty(Q)) {x=DeQueue(Q);Push(&S,x);} while(! StackEmpty(&s)) {x=Pop(&S);EnQueue(Q,x);} }//Demo3 (5)CirQueueQ1,Q2;//设DataType为int型 intx,I,m=0; …//设Q1已有内容,Q2已初始化过 while(! QueueEmpty(&Q1)) {x=DeQueue(&Q1);EnQueue(&Q2,x);m++;} for(I=0;I {x=DeQueue(&Q2);EnQueue(&Q1,x);EnQueue(&Q2,x);} 二、填空题 1、在有n个叶子结点的哈夫曼树中,其结点总数为。 2、将下三角矩阵A「1..8,1..8」的下三角部分逐行地存储到起始地址为1000的内存单元中,已知每个元素占4个单元,则A[7,5]的地址为。 3、高度为5的三阶B-树至少有个结点。 4、具有100个结点的完全二叉树的深度为。 5、在插入和选择排序中,若初始数据基本正序,则选用_________;若初始数据基本反序,则选用_________。 参考答案: 1、voidPostOrder(Bitreeroot) { //设二叉树的结点含有四个域: //mark,parent,lchild,rchild。 p=root; while(p) swith(p->mark){ case0: p->mark=1; if(p->lchild)p->lchild; break; case1: p->mark=2; if(p->rchild)p->rchild; break; case2: p->mark=0; visit(*p); p=p->parent; break; default: ; } }//PostOrder 2、 (1)解: 要求I,j到k的下标变换公式,就是要知道在k之前已有几个非零元素,这些非零元素的个数就是k的值,一个元素所在行为I,所在列为j,则在其前面已有的非零元素个数为: (I*3-1)+j-(I+1)其中(I*3-1)是这个元素前面所有行的非零元素个数,j-(I+1)是它所在列前面的非零元素个数 化简可得: k=2i+j;//c下标是从0开始的。 (2)解: 因为K和I,j是一一对应的关系,因此这也不难算出: I=(k+1)/3//k+1表示当前元素前有几个非零元素,被3整除就得到行号 j=(k+1)%3+(k+1)/3-1//k+1除以3的余数就是表示当前行中第几个非零元素,加上前面的0元素所点列数就是当前列号 3、 voidStrReplace(char*T,char*P,char*S) { //串替换 intI,m; m=strlen(P);//取得子串长度 I=StrMatch(T,P);//取得串匹配位置 StrDelete(T,I,m);//删除匹配处子串 StrInsert(T,S,I);//将S串插入到匹配位置处 } 4、 答案: 设用变量I表示栈的编号。 类型定义: typedefstruct {ElemTypev[m];//栈空间向量 inttop[2];//栈顶指针向量 }DuStack; 栈空条件: s0栈: s->top[0]=-1 s1栈: s->top[1]=m 栈满条件: s->top[0]+1=s->top[1](此时向量空间全占满)。 (1)插入 voidpush(DuStack*s,ElemTypex,intI)//当两个栈共享空间时,再由I指定的栈中插入新元素x {if(s->top[0]+1==s->top[1]) {printf("OVERFLOW”);return;} switch(I) {case0: s->top[0]++; s->v[s->top[0]]=x; break; case1: s->top[1]--; s->v[s->top[1]]=x; break; } } (2)删除 ElemTypepop(DuStack*s,intI)//当两栈共享空间时,在由I指定的栈中删除栈顶元素,并返回该元素 {switch(I) {case0: if(s->top[0]==-1) {printf("UNDERFLOW”);return;} x=s->v[s->top[0]]; s->top[0]--; break; case1: if(s->top[1]==m) {printf("UNDERFLOW”);return;} x=s->v[s->top[1]]; s->top[1]++; break; } return(x); } 5、 答: (1)4132; (2)4213;(3)4231。 6、 要解这样的问题,我们首先想到的是拿链表中的元素一个个地与max和min比较,然后删除这个结点,其实因为已知其是有序链表,所以我们只要找到大于min的结点的直接前趋结点,再找到小于max的结点,然后一并把中间的全部摘掉就可以了。 算法如下: voidDeleteList(LinkListL,DataTypemin,DataTypemax) { ListNode*p,*q,*r; p=L->next; while(p&&p->data<=min) {//找比min大的前一个元素位置 q=p; p=p->next; } while(p&&p->data { r=p; p=p->next; free? ;//释放这个结点空间 } q->next=p;//把断点链上 } 7、 答案: (1)程序段的功能是将一栈中的元素按反序重新排列,也就是原来在栈顶的元素放到栈底,栈底的元素放到栈顶。 此栈中元素个数限制在64个以内。 (2)程序段的功能是利用tmp栈将一个非空栈的所有元素按原样复制到一个空栈当中去。 (3)程序段的功能是将一个非空栈中值等于m的元素全部删去。 (4)程序段的功能是将一个循环队列反向排列,原来的队头变成队尾,原来的队尾变成队头。 (5)这段程序的功能是将队列1的所有元素复制到队列2中去,但其执行过程是先把队列1的元素全部出队,进入队列2,然后再把队列2的元素复制到队列1中。 二、填空题 a) 2n-1 b) 1208 c) 31 d) 7 e) 插入排序选择排序 1: [论述题] 1、采用邻接表存储结构,编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。 2、 编写算法完成下列操作: 无重复地输出以孩子兄弟链表存储的树T中所有的边。 输出形式为(k1,k2)…(ki,kj)…,其中ki,kj树结点中结点的标识。 (提示: 修改二叉树遍历的递归算法,使其参数表增加参数father,指向被访问的当前结点的双亲结点。 ) 3、 一个深度为h的满k叉树有如下性质: 第h层上的结点都是叶子结点,其余各层上每个结点都有k棵非空子树。 如果按层次顺序(同层自左至右)从1开始对全部结点编号,问: (1)各层的结点数目是多少? (2)编号为I的结点的双亲结点(若存在)的编号是多少? (3)编号为I的结点的第j个孩子结点(若存在)的编号是多少? (4)编号为I的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少? 4、设哈希函数为H(K)=Kmod7,哈希表的地址空间为0,…,6,开始时哈希表为空,用线性探测法解决冲突,请画出依次插入键值23,14,9,6,30,12,18后的哈希表。 二、填空题 1、 二叉排序树上,结点的平衡因子定义为该结点_________子树的高度减去该结点_________子树的高度。 2、请列举四种处理哈希冲突的方法: 、、、 。 3、一个无向图完全图中,共有条边。 4、对如何一颗二叉树,如果其终端结点数为n0,度为2的结点数为n2,则它们之间的关系应为: 。 5、下列排序算法中,稳定的排序算法是(选择排序,堆排序,快速排序,直接插入排序) 参考答案: 1、Booleanvisited[MAX]; Booleanfindpath(ALGraphG,intk, inta,intb){ for(I=0;I visited[I]=FALSE; returnDFSsearch(G,k,a,b) } Boolean
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 西南 大学 网上 作业 参考答案