2022年数据结构考试题4 .pdf

《2022年数据结构考试题4 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构考试题4 .pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、要求： 所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。一、单项选择题（每小题2 分，共 15 小题，共计 30 分）1. 以下不属于存储结构是。A.栈B.线索树C.哈希表D.双链表2. 以下算法的时间复杂度为。void fun(int n) int i=1; while (inext,*pb=B-next,*s,*r; C=(LinkList *)malloc(sizeof(LinkList); / 建立 C的头节点r=C; /r始终指向单链表C的尾节点while (pa!=NULL & pb!=NULL) if (pa-datadata) / 仅复制 *p

2、a 节点 s=(LinkList *)malloc(sizeof(LinkList); s-data=pa-data; r-next=s; r=s; pa=pa-next; else if (pa-datapb-data) / 仅复制 *pb 节点 s=(LinkList *)malloc(sizeof(LinkList); s-data=pb-data; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 6 页r-next=s; r=s; pb=pb-next; else s=(LinkList *)malloc(sizeof(Link

3、List); 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;

4、 本算法的时间复杂度为O(m+n)，空间复杂度为O(m+n)，其中 m、n 分别为 A、B 单链表中的节点个数。评分： 算法占 11分，时间和空间复杂度各占2分。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); 评分： 采用先序、中序、后序和层次遍历均可，算法占1

5、3分，时间复杂度占2分。3. 解： 邻接表的类型定义如下：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 6 页typedef char ElemType; typedef int InfoType; typedef struct ANode /边的节点结构类型 int adjvex; /该边的终点位置struct ANode *nextarc; /指向下一条边的指针InfoType info; /该边的相关信息，对于带权图可存放权值 ArcNode; typedef struct Vnode /邻接表头节点的类型 ElemType d

6、ata; /顶点信息ArcNode *firstarc; /指向第一条边 VNode; typedef VNode AdjListMAXV; /AdjList是邻接表类型typedef struct AdjList adjlist; /邻接表int n,e; /分别为图中顶点数和边数 AGraph; /声明图的邻接表类型采用遍历方式求无向图G 中连通分量个数。基于深度优先遍历的算法如下：int visitedMAXV=0; int Getnum(AGraph *G) / 求图 G的连通分量 int i,n=0,visitedMAXVEX; for (i=0;in;i+) if (visited

7、i=0) DFS(G,i); / 对图 G从顶点 i 开始进行深度优先遍历n+; / 调用 DFS的次数即为连通分量数 return n; 基于广度优先遍历的算法如下：int visitedMAXV=0; int Getnum1(AGraph *G) / 求图 G的连通分量 int i,n=0,visitedMAXVEX; for (i=0;in;i+) if (visitedi=0) BFS(G,i); / 对图 G从顶点 i 开始进行广度优先遍历n+; / 调用 BFS的次数即为连通分量数 return n; 评分： 邻接表的类型定义占5 分，求无向图G 的连通分量个数的算法占5 分。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 6 页