搜索
第1页共6页诚信应考考出水平考出风格浙江大学城市学院2011—2012学年第一学期期末考试试卷《数据结构基础》开课单位：计算分院；考试形式：闭卷；考试时间：2012年1月3日；所需时间：120分钟题序一二三四五六总分得分评卷人一．选择题(本大题共15题，每题1分，共15分)1．从逻辑上可以把数据结构分成。A.动态结构和静态结构B.顺序组织和链接组织C.线性结构和非线性结构D.基本类型和组合类型2．执行下面程序段时，执行S语句的频度为。for(inti=1;i=n;i++)for(intj=1;j=i;j++)S;A.n2B.n2/2C.n(n+1)D.n(n+1)/23．若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用下列存储方式最节省运算时间。A.单链表B.仅有指向表头指针的单循环链表C.双链表D.仅有指向表尾指针的单循环链表4．带头结点的单链表L为空的判断条件是。A.L==NULLB.L-next==NULLC.L-next==LD.L!=NULL5．允许对队列进行的操作有。A.对队列中的元素排序B.取出最近入队的元素C.在队头元素之前插入元素D.删除队头元素6．在计算递归函数时，如不用递归过程，应借助于这种数据结构。A.线性表B.栈C.队列D.双向队列得分年级：_____________专业：_____________________班级：_________________学号：_______________姓名：__________________…………………………………………………………..装………………….订…………………..线………………………………………………………第2页共6页7．若用一个大小为6的一维数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是()。A.4和2B.2和4C.1和5D.5和18．在有n个结点的二叉树的二叉链表表示中，空指针数。A.不定B.n+1C.nD.n-19．设x和y是二叉树中的任意两个结点，若在先序遍历中x在y之前，而在后序遍历中x在y之后，则x和y的关系是。A.x是y的左兄弟B.x是y的右兄弟C.x是y的祖先D.x是y的子孙10．设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为m1、m2和m3，则与森林F对应的二叉树根结点的右子树上的结点个数是。A.m1B.m1+m2C.m3D.m2+m311．深度为5的二叉树至多有_______个结点.A.31B.32C.33D.1612．在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的_________。A.出边数B.入边数C.度数D.度数减１13．对某个无向图的邻接矩阵来说，下列叙述错误的是。A.第i行与第i列上的非零元素的总数等于顶点vi的度数B.矩阵中的非零元素个数等于图中的边数的2倍C.第i行上的非零元素个数和第i列上的非零元素个数一定相等D.矩阵是一个n×n的方阵（n为图的顶点数）14．在一个具有n个顶点的有向完全图中，所含的边数为_________。A.nB.n(n-1)C.n(n-1)/2D.n(n+1)/215．对于，从它的某个顶点出发进行一次深度或广度优先搜索就可以访问到该图的每一个顶点。A.无向图B.有向图C.无向连通图D.任何一个图二．填空题(本大题共20空，每空1分，共20分)1．数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括3方面的内容，分别是数据的逻辑结构、⑴和操作（运算）。2．n个元素的线性表，采用顺序存储结构，插入一个元素要平均移动表中⑵个元素，删除一个元素要平均移动表中⑶个元素。3．已知指针P指向单链表中的结点，后继指针域为next，则在P指向结点后插入S指向结点的语句为：⑷；⑸。4．顺序表中逻辑上相邻的元素物理位置⑹相邻，单链表中逻辑上相邻的元素物理位置⑺相邻。5．设栈S的初始状态为空，队列Q的初始状态如图所示：___________________________________________a1a2a3a4___________________________________________↑队头↑队尾得分第3页共6页对栈S和队列Q进行以下两步操作：（1）删除Q中的元素，将删除的元素插入栈S，直到Q为空（2）依次将栈S中的元素插入Q，直到S为空在上述两步操作后，队列Q的状态是⑻。6．如果对完全二叉树中结点从1开始按层进行编号，设最大编号为n；那么，可以断定编号为i(i1)的结点的父结点编号为⑼；所有编号满足⑽的结点为叶子结点。7．有三个结点组成的二叉树共有⑾种不同的结构形态。深度为5的完全二叉树至少有⑿个分支结点。8．n个顶点的有向强连通图至少有⒀条边。若一个无向图有10条边，若要使该无向图是一个非连通图，至少需要⒁个顶点；若要使该无向图是一个连通图，至多可以有⒂个顶点。9．一个有向图的顶点集为{a,b,c,d,e,f},边集为{a,c,a,e,c,f,d,c,e,b,e,d},则出度为０的顶点个数为⒃，入度为１的顶点个数为⒄。10．在有向图的邻接矩阵中，第i行中“1”的个数是第i个顶点的⒅，第i列中“1”的个数是第i个顶点的⒆。在无向图的邻接矩阵中，第i行（列）中“1”的个数是第i个顶点的⒇。三．解答题(本大题共4题，每题5分，共20分)1．一棵二叉树的结点数据采用顺序存储结构存储在如下的数组中。01234567891011121314abdcehfg(1)画出该二叉树的图示(2)写出该二叉树的后序序列(3)把该二叉树转换为森林2．一棵二叉树的先序、中序、后序序列如下，其中一部分未标出，试构造出该二叉树。先序序列：CDEGHIK中序序列：CBFAJKIG后序序列：EFDBJIHA3．已知一个有向图G如题3图所示：(1)写出图中每个顶点的入度和出度；(2)写出该图的邻接矩阵；（3）画出该图的强连通分量题3图题4图得分0V131^1V2420^2V3431^3V420^4V521^②③⑥⑤④①第4页共6页4．已知一个图的邻接矩阵如题4图所示：（1）问该图是无向图还是有向图？（2）设结点v1为访问的第一个结点，按此邻接矩阵存储结构给出该图的深度优先遍历和广度优先遍历的访问序列。四．程序阅读题(本大题共3题，每题5分，共15分)1．设L为List类型的顺序表，说明下面函数的功能：ElemTypefunction(List&L){inti,len，m;ElemTypee;if(Emptylist(L)){printf(“线性表为空！\n”);exit(1);}len=LenthList(L);m=1;for(i=2;i=len;i++)if(GetList(L,m)GetList(L,i))m=i;e=GetList(L,m);DeleteList(L,e,m);returne;}2．说明下面函数的功能：longsum(intn){if(n==0)return0;elsereturnsum(n-1)+n*n;}3．BT为指向二叉树根节点的指针，说明下面函数的功能：intfunction(BTreeNode*BT,ElemTypex){intn=0;if(BT!=NULL){if(BT-data==x)n++;n+=function(BT-left);n+=function(BT-right);}returnn;}得分第5页共6页五．程序填空题(本大题共2题7空，每空2分，共14分)1．下面函数将两个有序的单链表生成一个有序单链表。LNode*MergeLNode(LNode*&La,LNode*&Lb){ElemTypem;LNode*p,*q,*t;while(Lb!=NULL){m=Lb-data;t=Lb-next;p=La;q=NULL;/*在La中找插入位置*/while(p-datam&&p!=NULL){⑴;p=p-next;}/*将Lb结点插入La链表*/if(q==NULL){Lb-next=p;⑵;}else{Lb-next=p;⑶;}⑷;}returnLa;}2．下面函数摘除一棵二叉树上的所有叶子结点后返回一棵新的二叉树。BTreeNode*RemoveLeaves（BTreeNode*BT1）{if(BT1==NULL)returnNULL;elseif(⑸)returnNULL;else{BTreeNode*BT2=newBTreeNode;⑹;BT2-left=RemoveLeaves(BT1-left);⑺;returnBT2;}}得分第6页共6页六．程序设计题(本大题共2题，每题8分，共16分)1．设有一个顺序表L，其元素为整型数据，设计一个算法将L中所有小于0的整数放在前半部分，大于0的整数放在后半部分。要求时间复杂度为O(n)，空间复杂度为O(1)。函数原型为：voidfunc(List&L)。List类型结构如下：structList{intelem[MaxSize];intsize}2．写一算法分别统计出二叉树BT中所有结点数和叶子（度为0）结点的个数。提示：可设置二个全局变量x、y分别用来存储所有结点数和叶子结点数。函数原型为：voidcountnode(BiTreeNode*BT)得分