数据结构例题剖析.docx
- 文档编号:14826183
- 上传时间:2023-06-27
- 格式:DOCX
- 页数:18
- 大小:183.07KB
数据结构例题剖析.docx
《数据结构例题剖析.docx》由会员分享,可在线阅读,更多相关《数据结构例题剖析.docx(18页珍藏版)》请在冰点文库上搜索。
数据结构例题剖析
当j=4时,找到的关键字应是5
为数组长度
∥在后半部分继续进行划分
∥在前半部分继续进行划分
!
!
对给定关键字序号j(1 (要求 用最少的时间和最少的空间) 例如: 给定无序关键字{7,5,1,6,2,8,9,3},intpartition(RecTypeA[],int1,intn){ inti=1,j=n;x=A[i].key; i=1;while(i while(i while(i }returni; } voidFind_j(RecTypeA[],intn,intj)n { i=partition(A,1,n); while(i! =j) if(i } 因装填因子为0.7,有7个元素,故哈希表长m=7/0.7=10构造的哈希表如下: 散列地址0123456789 关键字71481130189 比较次数1211133 答: ASL成功=1/7*(1*4+2*1+3*2)=12/7,失败=1/7*(3+2+1+2+1+5+4)=18/7 设图的顶点只是编号1――n,边的信息是有(用1表示)或无(用0表示),这时可用邻接矩阵表示图的存储结构。 请编写算法建立无向图的邻接矩阵的存储结构voidcreatgraph(intM[][],intn,inte)//设有n个顶点e条边 { inti,j; for(i=1;i<=n;i++) for(j=1;j<=n;j++) M[i][j]=0; for(i=1;i<=e;i++) {cin>>i>>j; M[i][j]=1;M[j][i]=1; 在根指针t所指二叉排序树中递归查找某关键字等于k的数据元素 BSTreeSearchBST1(BSTreet,keyTypek) {if(! t||k==t->key)return(t);elseif(k } 写出快速排序中一趟划分的算法。 intpartition(intR[],ints,intt)//s和t是数组的低下标和高下标 { inti=s,j=t,x=R[i].key; while(i { while(i j--; R[i]=R[j]; while(i i++;R[j]=R[i]; } r[i]=x; returni; } 要求完全利用循环队列中的元素空间,设置一个标志域tag,并以tag的值是0或1来区分尾指针和头指针相同时的队列状态是“空”还是“不空”请编写与此结构相对应的出队算法。 相关类型定义如下: voidQueueOut(CycQueuecq); { if(cq.tag==0)cout<<"队列为空\n"; else { cq.front=(cq.front+1)%m; if(cq.front==cq.rear) cq.tag=0;//空队列 } } ! ! 设n是非负整数,下面程序片段的时间复杂度是(O(log2n))x=2;while(x 已知二叉树的二叉链表存储表示如下,试编写求二叉树深度的算法 intHeight(BiTreebt) { inthl,hr; if(bt==null)return(0);else 以二叉链表作为存储结构,试编写求二叉树中叶子数的算法。 intLeafCount(BiTreeT) { if(! T)return0;//空树没有叶子 else if(! T->lchild&&! T->rchild)return1;//叶子结点elsereturnLeafCount(T->lchild)+LeafCount(T->rchild); } 设有顺序放置的n个桶,每个桶中装有一粒砾石,每粒砾石的颜色是红、白、蓝之一。 要求重新安排,使得红色砾石在前,白色砾石居中,蓝色砾石居后。 对每粒砾石的颜色只能察看一次,且只允许交换操作来调整砾石的位置。 顺序结构线性表A与B的结点关键字为整数。 A与B的元素按非递减有序,线性表空间足够大。 试给出一种高效算法,将B中元素合到A中,使新的A的元素仍保持非递减有序。 高效指最大限度的避免移动元素。 template voidUnion(arrList intm=A.curLen; intn=B.curLen;//m,n分别为线性表A和B的长度。 intk=m+n-1;//k为结果线性表的工作指针(下标) inti=m-1; intj=n-1;//i,j分别为线性表A和B的工作指针(下标)while(i>=0&&j>=0) { if(A.aList[i]>=B.aList[j]) A.aList[k--]=A.aList[i--]; else A.aList[k--]=B.aList[j--]; } while(j>=0) A.aList[k--]=B.aList[j--]; A.curLen=m+n; } 已知长度为n的线性表A采用顺序存储结构,请写一时间复杂度为0(n)、空间复杂度为0 (1)的算法,该算法删除线性表中所有值为item的数据元素。 voidarrList : DelAll(Titem) {inti=0,j=curLen-1;//设置数组低、高端指针(下标)while(i<=j) {while(i<=j&&aList[i]! =item)i++; while(i<=j&&aList[j]==item)j--; if(i } curLen=i; } PS: 若题目要求元素间相对顺序不变,可用如下语句段: voidarrList : DelAll(Titem) { i=0;j=0; while(j { if(aList[j]==item)j++; elseA[i++]=A[j++]; } }//最后线性表中的元素个数是i。 将非递减有序的单链表la和lb合并成新的非递减有序单链表lc,并要求利用原表空间 lnkList { Link lc=la;//lc利用la空间,将lb合并进来 pa=(la->head)->next;(la->head)->next=NULL; pb=(lb->head)->next;(lb->head)->next=NULL; pc=lc->head; while(pa&&pb)//la和lb均非空 中元素插入lc 中元素插入lc { if(pa->data<=pb->data)//la {pc->next=pa;pc=pa;pa=pa->next;} else//lb {pc->next=pb;pc=pb;pb=pb->next;} } if(pa) {pc->next=pa;//若pa未到尾,将pc指向pawhile(pa->next) pa=pa->next; lc->tail=pa;//修改尾指针 } elseif(pb) {pc->next=pb;//若pb未到尾,将pc指向pbwhile(pb->next) pb=pb->next; lc->tail=pb;//修改尾指针 } deletelb; return(lc); }假设一个单循环链表,其结点含有三个域pre、data、next。 其中data为数据域;pre为指针域,它的值为空指针(null);next为指针域,它指向后继结点。 请设计算法,将此表改成双向循环链表。 voidSToDouble(LinkedListla) {while(la->next->pre==null) {la->next->pre=la;la=la->next; 请编写算法将单链表L1拆成二个链表,其中以L1为头的链表保持原来向后的链接,另一个链表的表头为L2,其链接方向与L1相反,L1包含原链表的奇数序号的结点,L2包含原链表的偶数序号的结点。 Link {inti=0; Link p=L1->next;tail=L1; while(p) {i++; if(i%2) {tail->next=p;tail=p;p=p->next;}else {s=p->next;p->next=L2->next;//s储存p的下一个结点L2->next=p;p=s;//采用头插法逆置偶数序号的结点} }tail->next=NULL;∥置L1表尾 } 已知p是指向单向循环链表最后一个结点的指针,试编写只包含一个循环的算法,将线性表(a1,,⋯,an)改造为(a1,⋯,an-1,an,an-1,⋯,a1)Link {q=p->next;//q指向a1结点,工作指针t=newLink t->data=q->data;t->next=p->next;r=t;//r记住a1结点的指针p->next=t;q=q->next; while(q! =p) {t=newLink } p=r;returnp; } 设ha和hb分别是两个带头结点的非递减有序单链表的头指针,将这两个有序 链表合并成一个非递增有序的单链表。 要求使用原链表空间,表中无重复数据。 Link {pa=ha->next;pb=hb->next; ha->next=null;//ha作结果链表的头指针,先将结果链表初始化为空while(pa&&pb) {while(pa->next&&pa->data==pa->next->data) {u=pa->next;pa->next=u->next;deleteu;} while(pb->next&&pb->data==pb->next->data) {u=pb->next;pb->next=u->next;deleteu;}if(pa->data {r=pa->next;//将pa的后继结点暂存于r pa->next=ha->next;ha->next=pa;pa=r;// } if(pa)pb=pa; while(pb) {while(pb->next&&pb->data==pb->next->data) {u=pb->next;pb->next=u->next;deleteu;}r=pb->next;pb->next=ha->next;ha->next=pb;pb=r; }//将尚未到尾的表逆置到结果表中,注意也要删除重复元素returnha; } 以二叉链表作为存储结构,设计算法交换二叉树中所有结点的左、右子树 voidchange(BiTreeT) {if(T! =NULL) {change(T->lchild); change(T->rchild); t=T->lchild; T->lchild=T->rchild; T->rchild=t; } }以二叉链表作为存储结构,设计算法拷贝二叉树。 BiTreecopy(BiTreeT) {BiTreeT1; if(T==null)T1=null; else {T1=(BiTree)malloc(sizeof(BiNode));//申请结点 T1->data=T->data; T1->lchild=copy(T->lchild); T1->rchild=copy(T->rchild); } returnT1; ! ! 单链表的逆置 template : invert() {//逆置单链表 Link tail=p;while(p! =NULL){r=p->next; head->next=NULL;//保留第一个元素的指针后,将头结点的指针域置空 //将原链表的元素按头插法插入 //暂存p的后继 p->next=head->next;//逆置(头插法插入) head->next=p; p=r; //头结点的指针域指向新插入的结点 //恢复待处理结点 ! ! 已知一个带有表头结点的单链表,结点结构为(data,link),假设该链表只给出了头指针list。 在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数),若查找成功,算法输出该结点的data域的值,并返回1;否则,只返回0,intSearchInvK(constintk) {//在单链表la上查找倒数第k个结点p=list->link;//p指向当前待处理元素q=list;//若成功,q指向倒数第k个元素 i=1; while(p&&i if(p==null){cout<<“不存在\n”;return0;} while(p){q=q->link;p=p->link;}cout<<“倒数第k个元素的data域: ”< }//SearchInvK ! ! 已知递增有序的带头结点的单链表表示一类集合,设计算法以判断集合A是否是B的子集。 若A是B的子集,返回TRUE否,则返回FALSE。 BOOLjudge(node*A,node*B) { P=A->next;Q=B->next;num=0; while((P! =NULL)&&(Q! =NULL)) switch { caseP->data P=P->next;num=num+1;break;caseP->data>Q->data: Q=Q->next;break; caseP->data==Q->data: P=P->next;Q=Q->next;break; } while(P! =NULL){num=num+1;P=P->next;} judge=num==0; if(num! =0) cout<<”NumberofelementsthatisinAbutnotinB=”< } ! ! 假设用变量rear和length分别指示循环队列中队尾元素的位置和队列中元素的个数。 请按下面给出的循环队列的定义,写出相应出队(QueueOut)算法。 #defineMAXSIZE100∥队列可能达到的最大长度 typedefstruct{ElemTypedata[MAXSIZE]; intrear,length; }CyQueue; ! ! ! 设将n(n>1)个整数存放到一维数组R中。 试设计一个在时间和空间两方面都尽可能高效的算法,将R中保存的序列循环左移P(0 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或JAVA语言描述算法,关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。 (1)算法设计思想: 按照下标0到p-1、p到n-1、0到n-1的顺序,将这三段分别逆置,最后的结果即为所求。 (2)voidleftshift(intR[],intp,intn) { elemtypet;//t和数组R中的元素具有相同类型 for(i=0;i {t=R[i];R[i]=R[p-1-i];R[p-1-i]=t;} For(i=p;i<(n+p)/2;i++)//逆置p..n-1段 {t=R[i];R[i]=R[n-1-i+p];R[n-1-i+p]=t;} for(i=0;i {t=R[i];R[i]=R[n-1-i];R[n-1-i]=t;} } (3)算法执行了两趟逆置,时间复杂度为O(n);用了一个辅助变量空间,空间复杂度为O (1)。 讨论: 若采用直接左移p位,空间复杂度仍为O (1),但时间复杂度为O(np)。 ! ! ! 在一个设la是带头结点的双向链表的指针,其结点中除有prior,data和next外,还有一访问频度域freq,其值在链表初始使用时为0。 当在链表中进行ListLocate(la,x)运算时,若查找失败,则在表尾插入值为x的结点;若查找成功,值为x的结点的freq值增1,并要求链表按freq域值非增(递减)的顺序排列,且最近访问的结点排在频度相同的结点的后面,使频繁访问的结点总是靠近表头。 试编写符合上述要求的ListLocate(la,x)运算的算法,返回找到结点的指针。 Dlink {Dlink =x){q=p;p=p->next;}if(! p){printf(“不存在所查结点,现插入之\n”); s=newLink; s->data=x;s->freq=0;∥插入值为x的结点 s->next=p;s->prior=q; q->next=s;p=s;∥返回p结点; } else{p->freq++;∥令元素值为x的结点的freq域加1p->next->prior=p->prior;p->prior->next=p->next;∥将p结点摘下 q=p->prior;∥以下查找p结点的插入位置while(q! =L&&q->freq p->next=q->next;q->next->prior=p;∥将p结点插入q的后面p->prior=q;q->next=p; } return(p);}∥算法结束 ! ! ! L1与L2分别为两单链表头结点地址指针,且两表中数据结点的数据域均为一个字母。 设计把L1中与L2中数据相同的连续结点顺序完全倒置的算法。 Link*PatternInvert(Link*L1,Link*L2) {p=L1;∥p是每趟匹配时L1中的起始结点前驱的指针 q=L1->next;∥q是L1中的工作指针 s=L2->next;∥s是L2中的工作指针。 while(q&&s) if(q->data==s->data){q=q->next;s=s->next;}∥对应字母相等指针 后移 else{p=p->next;q=p->next;s=L2->next;} //失配时L1起始结点后移,L2从首结点开始。 if(s==null) ∥匹配成功,这时p为L1中与L2中首字母结点相同数据域结点的前驱,q为L1中与L2最后一个结点相同数据域结点的后继。 {r=p->next;∥r为L1的工作指针,初始指向匹配的首字母结点 ∥将p与q结点的链接∥逐结点倒置。 ∥暂存r的后继。 ∥将r所指结点倒置。 ∥恢复r为当前结点 } } elsecout<<“L2并未在L1中出现”< }∥算法结束 ! ! ! 数组A[1..n]中有n个数据,试建立一个带有头结点的循环链表,头指针为h,要求链中数据从小到大排列,重复的数据在链中只保存一个。 Link {Link h->next=h;//形成空循环链表for(i=0;i //查找A[i]的插入位置//重复数据不再输入 ∥将结点s链入p之前 {pre=h;p=h->next;while(p! =h&&p->datanext;}if(p==h||p->data! =A[i]) {s=newLink
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 例题 剖析