今日热门!数据结构试题有哪些?数据结构试题及评分解析
1.设A=(a1,a2,…,an),B=(b1,b2,…,bm)是两个递增有序的线性表(其中n、m均大于1),且所有数据元素均不相同。假设A、B均采用带头节点的单链表存放,设计一个尽可能高效的算法判断B是否为A的一个子序列,并分析你设计的算法的时间复杂度和空间复杂度。(15分) 1.(15分)解:采用二路归并思路,用p、q分别扫描有序单链表A、B,先找到第一个两者值相等的节点,然后在两者值相等时同步后移,如果B扫描完毕返回1,否则返回0。对应的算法如下:
(资料图片)
int SubSeq(LinkList *A,LinkList *B){LinkList *p=A->next,*q=B->next;while (p!=NULL && q!=NULL)//找两个单链表中第一个值相同的节点{if (p->datadata)p=p->next;else if (p->data>q->data)q=q->next;elsebreak;}while (p!=NULL && q!=NULL && p->data==q->data){//当两者值相等时同步后移p=p->next;q=q->next;}if (q==NULL)//当B中节点比较完毕返回1return 1;else//否则返回0return 0;}
本算法的时间复杂度为O(m+n),空间复杂度为O(1)。其中m、n分别为A、B单链表的长度。
2.假设二叉树b采用二叉链存储结构存储,试设计一个算法,输出该二叉树中从根节点出发的第一条最长的路径长度,并输出此路径上各节点的值。并分析你设计的算法的时间复杂度和空间复杂度。(15分) 3.2.(15分)解:由于二叉树中最长路径一定是从根节点到某个叶子节点的路径,可以求出所有叶子节点到根节点的逆路径,通过比较长度得出最长路径,可以采用多种解法。算法中用形参maxpath[]数组存放最长路径,maxpathlen存放最长路径长度。 解法1:对应的算法如下:
void MaxPath(BTNode *b,ElemType maxpath[],int &maxpathlen){//maxpathlen的初值为0struct snode{BTNode *node;//存放当前节点指针int parent;//存放双亲节点在队列中的位置} Qu[MaxSize];//定义非循环队列ElemType path[MaxSize];//存放一条路径int pathlen;//存放一条路径长度int front,rear,p,i;//定义队头和队尾指针front=rear=-1;//置队列为空队列rear++;Qu[rear].node=b;//根节点指针进进队Qu[rear].parent=-1;//根节点没有双亲节点while (frontfront++;b=Qu[front].node;//队头出队列if (b->lchild==NULL && b->rchild==NULL)//*b为叶子节点{p=front;pathlen=0;while (Qu[p].parent!=-1){path[pathlen]=Qu[p].node->data;pathlen++;p=Qu[p].parent;}path[pathlen]=Qu[p].node->data;pathlen++;if (pathlen>maxpathlen)//通过比较求最长路径{for (i=0;ilchild!=NULL)//左孩子节点进队{rear++;Qu[rear].node=b->lchild;Qu[rear].parent=front;}if (b->rchild!=NULL)//右孩子节点进队{rear++;Qu[rear].node=b->rchild;Qu[rear].parent=front;}}}
本算法的时间复杂度为O(n),空间复杂度为O(n)。
假设一个无向图是非连通的,采用邻接表作为存储结构,试设计一个算法,输出图中各连通分量的节点序列。(10分)(10分)解:采用深度优先搜索遍历非连通图,并输出各连通分量节点序列的算法如下: int visited[MAXV]={0}; DFSGraph(AGraph *G) { int i,j=1; //用j记录连通分量的序号 for (i=0;in;i++) if (visited[i]==0) { printf(“第%d个连通分量节点序列:”,j++); DFS(G,i); //调用前面的深度优先遍历算法 } } 采用广度优先搜索遍历非连通图,并输出各连通分量节点序列的算法如下: int visited[MAXV]={0}; BFSGraph(AGraph *G) { int i,j=1; //用j记录连通分量的序号 for (i=0;in;i++) if (visited[i]==0) { printf(“第%d个连通分量节点序列:”,j++); BFS(G,i); //调用前面的广度优先遍历算法 } }题3 1.设A和B是两个结点个数分别为m和n的单链表(带头结点),其中元素递增有序。设计一个尽可能高效的算法求A和B的交集,要求不破坏A、B的结点,将交集存放在单链表C中。给出你所设计的算法的时间复杂度和空间复杂度。
设A和B是两个结点个数分别为m和n的单链表(带头结点),其中元素递增有序。设计一个尽可能高效的算法求A和B的交集,要求不破坏A、B的结点,将交集存放在单链表C中。给出你所设计的算法的时间复杂度和空间复杂度。 解:算法如下:void insertion(LinkList *A,LinkList *B,LinkList *&C){LinkList *p=A->next,*q=B->next,*s,*t;C=(LinkList *)malloc(sizeof(LinkList));t=C;while (p!=NULL && q!=NULL){if (p->data==q->data){s=(LinkList *)malloc(sizeof(LinkList));s->data=p->data;t->next=s;t=s;p=p->next;q=q->next;}else if (p->datadata)p=p->next;elseq=q->next;}t->next=NULL;}
算法的时间复杂度为O(m+n),空间复杂度为O(MIN(m,n))。 【评分说明】算法为8分,算法的时间复杂度和空间复杂度各占1分。
假设二叉树b采用二叉链存储结构,设计一个算法void findparent(BTNode *b,ElemType x,BTNode *&p)求指定值为x的结点(假设这样的结点是唯一的)的双亲结点地址p,提示,根结点的双亲为NULL,若在b中未找到值为x的结点,p亦为NULL。假设二叉树b采用二叉链存储结构,设计一个算法void findparent(BTNode *b,ElemType x,BTNode *&p)求指定值为x的结点的双亲结点p,提示,根结点的双亲为NULL,若未找到这样的结点,p亦为NULL。 解:算法如下:void findparent(BTNode *b,ElemType x,BTNode *&p){if (b!=NULL){if (b->data==x) p=NULL;else if (b->lchild!=NULL && b->lchild->data==x)p=b;else if (b->rchild!=NULL && b->rchild->data==x)p=b;else{findparent(b->lchild,x,p);if (p==NULL)findparent(b->rchild,x,p);}}else p=NULL;}
【评分说明】本题有多种解法,相应给分。
题4 1.用单链表来存储集合,并假设这样的单链表中的节点递增有序,设计一个尽可能高效的算法求两个集合A和B的并集C。设A、B中分别有m和n个元素,分析你设计的算法的时间和空间复杂度。(15分)
解:由于单链表是递增有序的,可以采用归并算法提高求并集的效率,结果并集C采用尾插法建表。对应算法如下:void Unionset(LinkList *A,LinkList *B,LinkList *&C){LinkList *pa=A->next,*pb=B->next,*s,*r;C=(LinkList *)malloc(sizeof(LinkList));//建立C的头节点r=C;//r始终指向单链表C的尾节点while (pa!=NULL && pb!=NULL){if (pa->datadata)//仅复制*pa节点{s=(LinkList *)malloc(sizeof(LinkList));s->data=pa->data;r->next=s; r=s;pa=pa->next;}else if (pa->data>pb->data)//仅复制*pb节点{s=(LinkList *)malloc(sizeof(LinkList));s->data=pb->data;r->next=s; r=s;pb=pb->next;}else{s=(LinkList *)malloc(sizeof(LinkList));s->data=pa->data;r->next=s; r=s;pa=pa->next;pb=pb->next;}}while (pa!=NULL)//复制A单链表的余下节点{s=(LinkList *)malloc(sizeof(LinkList));s->data=pa->data;r->next=s; r=s;pa=pa->next;}while (pb!=NULL)//复制B单链表的余下节点{s=(LinkList *)malloc(sizeof(LinkList));s->data=pb->data;r->next=s; r=s;pb=pb->next;}r->next=NULL;}
本算法的时间复杂度为O(m+n),空间复杂度为O(m+n),其中m、n分别为A、B单链表中的节点个数。 评分:算法占11分,时间和空间复杂度各占2分。
2.假设二叉树采用二叉链存储结构进行存储,假设每个节点值为单个字符且所有节点值不同,设计一个算法,输出二叉树b中第k的所有节点值,并分析你所设计算法的时间复杂度。(15分) 2. 解:采用先序序列,对应的算法如下:
void Dispk(BTNode *b,int k){Dispk1(b,k,1);}void Dispk1(BTNode *b,int k,int h){if (b!=NULL){if (h==k) printf(“%c “,b->data);Dispk1(b->lchild,k,h+1);Dispk1(b->rchild,k,h+1);}}
评分:采用先序、中序、后序和层次遍历均可,算法占13分,时间复杂度占2分。
说明:以上两题求算法的时间和空间复杂度只需给出结果,不必给出详细步骤。
图的邻接表是一种图的链式存储结构,请给出邻接表的完整类型定义。采用你所设计的邻接表作为存储结构,设计一个算法,求出无向图G的连通分量个数。(10分)3. 解:邻接表的类型定义如下:typedef char ElemType;typedef int InfoType;typedef struct ANode//边的节点结构类型{int adjvex;//该边的终点位置struct ANode *nextarc;//指向下一条边的指针InfoType info;//该边的相关信息,对于带权图可存放权值} ArcNode;typedef struct Vnode//邻接表头节点的类型{ElemType data;//顶点信息ArcNode *firstarc;//指向第一条边} VNode;typedef VNode AdjList[MAXV];//AdjList是邻接表类型typedef struct{AdjList adjlist;//邻接表int n,e;//分别为图中顶点数和边数} AGraph;//声明图的邻接表类型采用遍历方式求无向图G中连通分量个数。基于深度优先遍历的算法如下:int visited[MAXV]={0};int Getnum(AGraph *G)//求图G的连通分量{int i,n=0,visited[MAXVEX];for (i=0;in;i++)if (visited[i]==0){DFS(G,i);//对图G从顶点i开始进行深度优先遍历n++;//调用DFS的次数即为连通分量数}return n;}基于广度优先遍历的算法如下:int visited[MAXV]={0};int Getnum1(AGraph *G)//求图G的连通分量{int i,n=0,visited[MAXVEX];for (i=0;in;i++)if (visited[i]==0){BFS(G,i);//对图G从顶点i开始进行广度优先遍历n++;//调用BFS的次数即为连通分量数}return n;}
评分:邻接表的类型定义占5分,求无向图G的连通分量个数的算法占5分。
第五套题
(10分)某带头结点的非空单链表L中所有元素为整数,结点类型定义如下:typedef struct node{int data;struct node *next;} LinkNode;
设计一个尽可能高效的算法,将所有小于零的结点移到所有大于等于零的结点的前面。
(10分)答案:void Move(LinkNode *&L){LinkNode *p=L->next,*pre=L; while (p!=NULL && p->data<0)//跳过小于0的结点 {pre=p;p=pre->next; }while (p!=NULL){if (p->data<0)//若*p结点值小于0{pre->next=p->next;//从链表中删除*p结点p->next=L->next;//将*p结点插入到头结点之后L->next=p;p=pre->next;//p指向*pre之后结点,pre不变}else//若*p结点值不小于0{pre=p;//pre、p同步后移一个结点p=p->next;}}}
(15分)假设二叉树中有n个结点,每个结点值为单个字符,而且所有结点值均不相同,采用二叉链存储结构存储,其结点类型定义如下: typedef struct node{char data; struct node *lchild,*rchild;} BTNode;
请完成以下任务: (1)设计一个算法,在二叉树b中查找x结点(指结点值为x的结点),若找到该结点,返回其地址,否则返回NULL。给出你设计的算法的时间复杂度。(8分) (2)设计一个算法,利用(1)小题设计的算法输出二叉树b中x结点的所有子孙结点值。(7分) 2. (15分)答案: (1)(7分)
BTNode *Findx(BTNode *b,char x)//在二叉树b中查找x结点{BTNode *p;if (b==NULL) return NULL;else{if (b->data==x)return b;p=Findx(b->lchild,x);if (p!=NULL)return p;return Findx(b->rchild,x);}}
算法的时间复杂度为O(n)(1分)。 (2)(7分)
void Sons(BTNode *b,char x)//输出x结点的子孙,初始时b指向x结点{if (b!=NULL){if (b->data!=x)printf("%c ",b->data);Sons(b->lchild,x);Sons(b->rchild,x);}}void OutSons(BTNode *b,char x)//输出二叉树b中x结点的所有子孙结点值{BNode *p= Findx(b,x);if (p!=NULL)Sons(p,x);}
题6
1.设计一个算法delminnode(LinkList *&L),在带头结点的单链表L中删除所有结点值最小的结点(可能有多个结点值最小的结点)。
解:用p从头至尾扫描单链表,pre指向p结点的前驱,用minp保存值最小的结点指针,minpre指向minp结点的前驱。一面扫描,一面比较,将最小值的结点放到*minp中。算法如下:void delminnode(LinkList *&L){LinkList *pre=L,*p=pre->next,*minp=p,*minpre=pre;ElemType mindata=p->data;while (p!=NULL && p->datamindata=p->data;p=p->next;}p=pre->next;while (p!=NULL){if (p->data==mindata){pre->next=p->next;free(p);}pre=pre->next;p=pre->next;}}
评分标准:根据算法的正确性评分,不考虑算法的时间复杂度。
2.假设二叉树采用二叉链存储结构存储,设计一个算法copy(BTNode *b,BTNode *&t),由二叉树b复制成另一棵二叉树t。 2.解:递归算法如下:
void copy(BTNode *b,BTNode *&t){BTNode *l,*r;if (b==NULL) t=NULL;else{t=(BTNode *)malloc(sizeof(BTNode));copy(b->lchild,l);copy(b->rchild,r);t->lchild=l;t->rchild=r;}}
评分标准:根据算法的正确性评分,不考虑算法的时间复杂度。
假设一个无向图是非连通的,采用邻接表作为存储结构,试设计一个算法,输出图中各连通分量的节点序列。解:采用深度优先搜索遍历非连通图,并输出各连通分量节点序列的算法如下:DFSGraph(AGraph *G){int i,j=1;//用j记录连通分量的序号for (i=0;in;i++)if (visited[i]==0){printf("第%d个连通分量节点序列:",j++);DFS(G,i);//调用深度优先遍历算法}}
题9
(15分)有两个递增有序表,所有元素为整数,均采用带头结点的单链表存储,结点类型定义如下:typedef struct node{int data;struct node *next;} LinkNode;
设计一个尽可能高效的算法,将两个递增有序单链表ha、hb合并为一个递减有序单链表hc,要求算法空间复杂度为O(1)。
(15分)参考算法如下:void merge(LinkNode *ha, LinkNode *hb, LinkNode *&hc){LinkNode *pa=ha->next,*pb=hb->next,*q;free(hb);hc=ha; hc->next=NULL;//hc利用ha的头结点,并设置为空while (pa!=NULL && pb!=NULL)//扫描ha、hb的数据结点{if (pa->datadata)//将较小结点采用头插法插入到hc中{q=pa->next;pa->next=hc->next;hc->next=pa;pa=q;}else{q=pb->next;pb->next=hc->next;hc->next=pb;pb=q;}}if (pb!=NULL) pa=pb;while (pa!=NULL)//将没有扫描完的结点采用头插法插入到hc中{q=pa->next;pa->next=hc->next;hc->next=pa;pa=q;}}
评分说明:上述算法的时间复杂度为O(m+n)。若设计的算法时间复杂度为O(m*n),至少扣3分,若设计的算法空间复杂度不为O(1),扣2分。
2、(10分)设二叉树中每个结点存放单个字符,其结点类型如下:
typedef struct node{char data; struct node *lchild,*rchild;} BTNode;
设计一个算法求其中单分支的结点个数。 2、(10分)参考算法如下:
int singleodes(BTNode *b){if (b==NULL) return 0; if ((b->lchild==NULL && b->rchild!=NULL) ||//单分支的结点(b->lchild!=NULL && b->rchild==NULL)return singleodes(b->lchild)+ singleodes(b->rchild)+1;elsereturn singleodes(b->lchild)+ singleodes(b->rchild);)
评分说明:可以采用任意一种遍历方法。判断单分支的结点为3分。
标签:
相关推荐:
最新新闻:
- 电脑默认网关如何查询?电脑默认网关查询的小技巧
- IE浏览器不见了怎么办?IE浏览器不见了解决方法
- Win7专业版与Win7旗舰版如何区分?Win7专业版与Win7旗舰版区分方法
- Win7系统安装声卡驱动失败怎么办?声卡驱动安装失败解决方法
- 百度快照如何彻底删除?百度快照正确的删除方法
- 英雄联盟无法全屏显示如何解决?英雄联盟无法全屏显示解决方法
- 如何解决IE浏览器网页图片显示红叉问题?IE浏览器网页图片显示红叉解决方法
- Win7系统安装CAD软件提示缺少dfst.dll怎么办?解决方法
- 内网端口映射怎么设置?内网端口映射定义及设置方法
- 美拍是什么?美拍怎么用?
- 怎么关闭微信的扫脸支付功能?微信的扫脸支付功能关闭步骤
- 基础版本的基础版本 直方图均衡化系列
- 天天要闻:图片或手写签名转电子签名怎么转?手写签名转电子签名教程
- ssm大学生兼职论坛是什么?大学生兼职有哪些?:每日观察
- 许多推倒重建正在发生 | 独家对话索尼互娱中国总裁
- 今日视点:怎么设置交换机?计算机交换机连接设置方法
- 摄氏度和开氏度的换算 开氏度和摄氏度的换算公式 天天亮点
- PSVR2首发获两款老游戏强化!可4K、90帧运行
- 今日热门!数据结构试题有哪些?数据结构试题及评分解析
- 传英伟达RTX 4070Ti首发价899美元 约合RMB 6268元|环球资讯
- 关注:《铁拳8》TGA预热视频 2023年发售
- 天天速看:CDP警告员工《巫师》AR手游停服后将会进行裁员
- 二代接班,一场父与子的「明争暗战」 全球新动态
- 世界观点:看不起英特尔独显?一个驱动更新游戏帧数提升80%
- 游戏玩家抓紧更新!Win 11修复重大性能BUG 帧率显著提升
- 【新要闻】育碧:《纪元1800》于今日返回Steam平台
- 朴叙俊将加盟《惊奇队长2》 演惊奇队长丈夫|当前头条
- 《高达 水星魔女》一阶段最终话暂停 明年1月8日续播
- 泛娱乐出海拉美,茄子科技(海外SHAREit Group)助力企业有效获客
- 《暗黑4》新预告片将在明早1点公开_每日聚焦
- 全球视讯!《微软飞行模拟》玩家达到了1000万
- 【环球时快讯】一起教育科技发布2022年三季度财报:连续四个季度实现盈利
- 国产处理器龙芯发威了 下一代单核性能提升68%
- 在云南沙溪,这群年轻人每天做的事是「什么也不做」 每日视讯
- 2部国产动画获奥斯卡参评资格:豆瓣分别7.0分、5.8分 今日关注
- 【全球聚看点】全球首款8000MHz频率内存开卖 32GB售价4888元
- 4999元 你能买到的最低价12代标压i5+RTX3050游戏本来了|当前报道
- 把iMac按在地上摩擦 4K屏+RTX 3060独显微软Surface一体电脑预售中|重点聚焦
- Windows 11免费升级新招 Windows 7也能用:全球今头条
- 普京表示核战争的风险正在上升,没有继续进行动员的必要
- 世界速看:玩家注意升级:Win11更新补丁修复游戏性能问题
- 焦点热议:想要畅玩《老头环》?高颜值游戏本双十二杀到7599元
- RTX 4080全球销售低迷 网友:太贵了 我再等等_世界速递
- 【环球新视野】抢跑美联储的加拿大央行进一步接近转向:首次暗示可能暂停加息
- VR游戏《进击的巨人VR:牢不可破》明年夏季上市_全球动态
- 当前关注:特斯拉比亚迪等怕吗?苹果汽车曝光:70万元
- 当前快讯:秒杀价3499元 双12临近华硕无畏二合一OLED屏笔记本疯狂促销
- 视频演示创建《暗黑破坏神4》野蛮人法师角色
- 系列制作人确认《勇者斗恶龙3HD》新消息很快公布:当前通讯
- 万代南梦宫注册《破晓传说》《块魂》新商标
- 全球动态:《神秘海域》新作或在开发中 顽皮狗只做协助
- 《死亡空间》原版与重制版早期图像对比视频 全球热门
- 微软表示《微软飞行模拟》已突破1000万玩家-全球热点
- 全新VR农场模拟游戏《横跨山谷》公布
- 快看点丨华尔街裁员潮加速蔓延!摩根士丹利裁员1600人
- 入冬最销魂的一口,莫过于它
- 主动“走失”又归来的小镇少年们
- 2022日本东京大学校花冠军出炉 甜美可爱的学霸妹子-世界头条
- 《刺客信条:英灵殿》Steam遇冷 峰值只有3527人
- 【世界报资讯】网飞联席CEO:还没看到体育赛事直播的盈利模式
- 《毁灭全人类2》公布节日皮肤 免费更新_全球资讯
- 1TB固态SSD再降价 到手限时294元
- 天天快资讯:国产大厂们的开放世界野望,究竟能实现几成?
- “索尼克之父”中裕司又因内幕交易被捕 涉案金额超1亿日元
- 全球快消息!扬州琼都歌舞厅:欢迎来到80年代
- 《阿凡达2》中国内地预售首日总票房突破千万
- 拐点已至!碳酸锂价格连续10日下跌
- 环球资讯:演恶毒女配的北漂演员,已经抢先停止内耗了
- 困在小作坊的农村女工
- 马拉松“抽烟哥”引争议 中国田协紧急倡议:应积极正向 天天微头条
- DOTA2 LGD战队发公告 功勋老将AME暂离休息
- SIE总裁为PS5在日本和亚洲缺货而道歉_今亮点
- 《我的世界》联动《降世神通:最后的气宗》宣传片 目前已上线:世界热消息
- 【新要闻】BTS成员分享直播录屏 竟让《鸭鸭杀》Steam爆火
- 通讯!《艾尔登法环》斗技场已上线 平衡性调整和BUG修复到来