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

20132014学年第二学期闽江学院期末试卷考试课程：数据结构与算法试卷类别：A卷 B卷 考试形式：闭卷 开卷适用专业年级：13级金融服务、13级软件服务 装 订 线班级 姓名 学号 题号一二三总分得分一、单项选择题60%（请将答案填入答题卡相应位置，30题，每题2分，共60分）得分1、计算机算法必须具备输入、输出和（ ）等5个特性。 A可行性、可移植性和可扩充性 B可行性、确定性和有穷性 C确定性、有穷性和稳定性 D易读性、稳定性和安全性 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; 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顺序表 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-nextarc=_(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) Ai B. j C. v1 D. v2(5) AG-verticesi.firstarc B. G-verticesj.firstarcC. G-verticesi.nextarc D. G-verticesj.nextarc三、填空题30%（请将答案填入答题卡相应位置，除第3题第一空为4分外，其余都为2分，共30分）得分1、已知记录 (46,74,53,14,26,38,86,65,27,34)，请给出归并排序的第一趟排序结果(以第一个元素作为基准)：_2、从一棵二叉排序树中查找一个元素时，若元素的值大于根结点的值，则继续向_查找。3、假设一棵二叉树的后序序列为DCEGBFHKJIA，中序序列为DCBGEAHFIJK，请画出该二叉树_(4分)，并写出该二叉树的先序遍历序列_。4、已知二叉树的二叉链表表示法定义如下：typedef char TElemType;typedef struct BiTnode TElemType 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(p=_(1)_; p; _(2)_)/