13级数据结构与算法期末试卷B

1、 共10 PAGE 5*2 页 第 = PAGE 5*2-1 9 PAGE 5*2-1 页 共10 PAGE 5*2 页 第 PAGE 5*2 PAGE 5*2-1 页20232023学年第二学期闽江学院期末试卷考试课程：?数据结构与算法?试卷类别：A卷 B卷 考试形式：闭卷 开卷适用专业年级：13级金融效劳、13级软件效劳 装 装 订 线题号一二三总分得分一、单项选择题60%请将答案填入答题卡相应位置，30题，每题2分，共60分得分1、计算机算法必须具备输入、输出和 等5个特性。 A可行性、可移植性和可扩充性 B可行性、确定性和有穷性 C确定性、有穷性和稳定性 D易读性、稳定性和平安性 2、

2、设语句x+的时间是单位时间，那么以下语句的时间复杂度为。 for(i=1; ilast是表尾结点指针。假设想删除链表的首元结点，那么应执行以下操作？ As = L-last; L-last= L-last-next; free(s); BL-last= L-last-next; free(L-last); CL-last= L-last-next-next; free(L-last); Ds = L-last-next-next; L-last-next-next = s-next; free(s);7、带头结点的单链表L为空的判定条件是 AL-next = NULL; BL!= NULL;

3、CL-next= L; DL= NULL; 8、设结点结构为(prior,data,next)，L是不带头结点循环双链表，L是表头结点指针。假设想删除循环双链表中p结点的后继结点(假设存在)，那么应执行以下操作？ Ap-next =p-next-next; Bp-next = p-next-next; p-next-prior = p; Cp-next = p-next-next; p-next-next-prior = p;Dp-next-prior = p; p-next = p-next-next;9、假设在线性表中经常涉及插入删除操作，那么采用以下哪种表进行元素存储比较好？A有序表 B

4、顺序表 C链表 D栈10、在一个长度为n的顺序表中插入第i个元素(1=ivexnum), &(G-arcnum);/输入图的顶点数与弧数/构造顶点数组for(i=0; ivexnum; i+)getchar();/吸收输入的回车符scanf(%c, _(1)_);/输入图的顶点信息_(2)_;/构造边结点for(k=0; karcnum; k+)getchar();/吸收回车符scanf(%c,%c, &v1,&v2);/输入弧的两个端点i=LocateVex(G,v1);/起点的编号j=LocateVex(G,v2);/终点的编号pi=_(3)_; pi-adjvex=_(4)_;pi-ne

5、xtarc=_(5)_;G-verticesi.firstarc=pi;(1) A&(G-verticesj.data) B. &(G-verticesi.data)C. &(G-verticesj.adjvex) D. &(G-verticesi.adjvex)(2) AG-vexnum+ B.此处不需要添加代码C. G-datai.firstarc=NULL D. G-verticesi.firstarc=NULL(3) Anew Node B. new VNodeC. new ArcNode D. new ALGraph(4) AiB.j C.v1 D.v2(5) AG-vertices

6、i.firstarcB. G-verticesj.firstarcC. G-verticesi.nextarcD. G-verticesj.nextarc三、填空题30%请将答案填入答题卡相应位置，除第3题第一空为4分外，其余都为2分，共30分得分1、记录 (46,74,53,14,26,38,86,65,27,34)，请给出归并排序的第一趟排序结果(以第一个元素作为基准)：_2、从一棵二叉排序树中查找一个元素时，假设元素的值大于根结点的值，那么继续向_查找。3、假设一棵二叉树的后序序列为DCEGBFHKJIA，中序序列为DCBGEAHFIJK，请画出该二叉树_(4分)，并写出该二叉树的先序遍

7、历序列_。4、二叉树的二叉链表表示法定义如下：typedef char TElemType;typedef struct BiTnodeTElemType data; struct BiTnode *lchild, *rchild;BiTNode, *BiTree;请将以下二叉树的查找算法补充完整：int LocateElem(BiTree T, TElemType e)/e为要查找的元素int floor;/用于记录层数if(T)/假设树不空if(_(1)_)/假设在根处找到return 1;floor = LocateElem(_(2)_);/在左子树查找if(floor0)/假设在左子树中找到return _(3)_;floor = LocateElem(_(4)_);if(floor0)return _(5)_;return 0;/假设树为空，那么直接返回0，说明找不到5、图的邻接表定义如第二题所示，以下程序段为图的深度优先搜索算法，请将算法中缺失的语句补充完整：void DFS (ALGraph G,int v) /从编号为v的顶点出发进行深度优先搜索遍历 /假设所有变量、函数皆已定义 visitedv=true;/访问标志数组，true表示访问过，false表示未被访问过 VisitFunc(v); /访问v标点for(