2023年数据结构与算法期末试卷B.doc

第二学期闽江学院期末试卷考试课程：数据构造与算法试卷类别：A卷 B卷þ 考试形式：闭卷þ 开卷合用专业年级：13级金融服务、13级软件服务 装 订 线班级 姓名 学号 题号一二三总分得分一、单项选取题60%（请将答案填入答题卡相应位置，30题，每题2分，共60分）得分1、计算机算法必要具有输入、输出和（ ）等5个特性。 A可行性、可移植性和可扩充性 B可行性、拟定性和有穷性 C拟定性、有穷性和稳定性 D易读性、稳定性和安全性 2、设语句x+时间是单位时间，则如下语句时间复杂度为（）。 for(i=1；i<=n；i+) x+； AO(1) BO (n2) CO(n) DO (n3)3、如下哪种逻辑构造关系最松散（ ）A集合 B线性 C树 D图4、如下哪种线性表存储地址一定是连续（ ） A有序表 B顺序表 C单链表 D双链表5、带头指针循环链表在表尾插入，时间复杂性 ( ) AO(1) BO(n） CO (n2) DO (n3)6、设结点构造为(data，next)，L是带头结点和尾指针单循环链表，L->last是表尾结点指针。若想删除链表首元结点，则应执行下列（）操作？ 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<=i<=n+1)时，需向前移动（）个元素。An-i Bn-i+1 Cn-i-1 Di11、假定对元素序列（7，3，5，9，1，12）进行堆排序，并且采用小根堆，则由初始数据构成初始堆为（ ）。 A1，3，5，7，9，12 B1，3，5，9，7，12 C1，5，3，7，9，12 D1，5，3，9，12，7 12、假定一种初始堆为(1，5，3，9，12，7，15，10)，则进行第一趟堆排序后得到成果为（ ）。A3，5，7，9，12，10，15，1 B. 3，5，9，7，12，10，15，1C. 3，7，5，9，12，10，15，1 D. 3，5，7，12，9，10，15，113、在平均状况下速度最快排序办法为（ ） A直接选取排序 B归并排序 C基数排序 D迅速排序 14、若一种元素序列基本有序，则选用（ ）办法较快。 A直接插入排序 B简朴选取排序 C归并排序 D迅速排序 15、对1000个元素进行排序，规定既快又省空间，则如下（）算法比较好。 A直接插入排序 B堆排序 C归并排序 D迅速排序 16、设元素进栈顺序为1，2，3，那么如下哪种是不也许出栈序列。 A123 B132 C312 D312 17、栈插入和删除操作在（ ）进行。 A栈顶 B栈底 C中间 D任意位置18、队列中元素进出原则为（）。 A先进先出 B后进先出 C大数先出 D小数先出 19、对二叉排序树进行如下哪种遍历会得到一种有序序列。A. 先序遍历 B. 中序遍历C. 后序遍历 D. 层序遍历20、由权值分别为3,8,6,2,5叶子结点生成一棵哈夫曼树，它带权途径长度为（ ）。A. 24B. 48C. 72D. 5321、在一棵度为3树中，度为3结点数为3个，度为2结点数为2个，度为1结点数为3个，则度为0结点数为（ ）个。A. 8B. 9C. 6D. 722、在一棵二叉树上第3层结点数最多为（ ）。A. 2B. 4 C. 6D. 823、用顺序存储办法将完全二叉树中所有结点逐级存储在数组中R1.n，结点Ri若有右孩子，其右孩子编号为结点（ ）。A. R2i+1B. R2iC. Ri/2D. R2i-124、已知图中某条途径上有k个顶点，则该途径长度为（）。Ak-1 Bk Ck+1 D2k25、如下( )算法用于在有向网中求单源最短途径。 A普里姆算法 B克鲁斯卡尔算法 C迪杰斯特拉算法 D弗洛伊德算法 26、在一张有向图中，若一种顶点入度为k1，出度为k2，则相应邻接表中该标点单链表中结点数为( )。Ak1 Bk2 Ck1+k2 D2(k1+k2)27、设有7个结点无向图，该图至少应用( )条边能保证是一种连通图。A5 B6 C7 D828、10个顶点构成无向完全图中，有( )条弧。A45 B90 C100 D20029、对于顺序存储有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素12比较次数为()。A. 2 B. 3 C. 4 D. 530、假定对线性表(38,25,74,52,48)进行哈希存储，采用H(k)=k%7作为哈希函数，采用开放定址法解决冲突，则在建立哈希表过程中，将会碰到( )次存储冲突。A. 4 B. 5 C. 6 D. 7二、程序完型填空题10%（请将答案填入答题卡相应位置，1题5空，每空2分，共10分）得分已知图邻接表定义如下：const MAX_VERTEX_NUM=20;typedef struct ArcNodeint adjvex;struct ArcNode *nextarc;int info;/InfoType *info;ArcNode；/边结点typedef char VertexType;typedef struct VNodeVertexType data;ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM；/顶点数组中顶点结点typedef struct AdjList vertices;int vexnum,arcnum;ALGraph；/图请将下列有向图创建算法补充完整：void CreateUDG(ALGraph *G)/假设所需变量皆已经定义scanf("%d,%d"，&(G->vexnum)，&(G->arcnum);/输入图顶点数与弧数/构造顶点数组for(i=0；i<G->vexnum；i+)getchar();/吸取输入回车符scanf("%c"，_(1)_);/输入图顶点信息_(2)_;/构造边结点for(k=0；k<G->arcnum；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(floor>0)/若在左子树中找到return _(3)_;floor = LocateElem(_(4)_);if(floor>0)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)_)/for(用p指向第一种邻接顶点；若该邻接顶点存在；p指向下一种邻接顶点) w=p->_(3)_;/用w记录邻接顶点编号if(_(4)_)/若该邻接顶点未被访问过 _(5)_;/从邻接顶点开始递归深度优先搜索遍历