2012-2013安徽大学《数据结构》期末试卷

2012~2013安徽大学《数据结构》期末试卷一、单项选择题，在括号内填写所选择的标号（每小题1分，共12分）1.下面程序段的时间复杂度为()。for(inti=0;im;i++)for(intj=0;jn;j++)a[i][j]=i*j;A.O(m2)B.O(n2)C.O(m*n)D.O(m+n)2.在二维数组中，每个数组元素同时处于（）个向量中。A.0个B.1个C.2个D.n个3.设有两个串t和p，求p在t中首次出现的位置的运算叫做（）。A.求子串B.模式匹配C.串替换D.串连接4.利用双向链表作线性表的存储结构的优点是（）。A.便于单向进行插入和删除的操作B.便于双向进行插入和删除的操作C.节省空间D.便于销毁结构释放空间5.设链式栈中结点的结构为（data,link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行()操作。A.top-link=s;B.s-link=top-link;top-link=s;C.s-link=top;top=s;D.s-link=top;top=top-link;6.设有一个递归算法如下intX(intn){if(n=3)return1;elsereturnX(n-2)+X(n-4)+1;}试问计算X(X(5))时需要调用（）次X函数。A．2B．3C．4D．57.一棵具有35个结点的完全二叉树的高度为()。假定空树的高度为-1。A.5B.6C.7D.88.向具有n个结点的堆中插入一个新元素的时间复杂度为()。A.O(1)B.O(n)C.O(log2n)D.O(nlog2n)9.在一棵AVL树中，每个结点的平衡因子的取值范围是()。A.-11B.-22C.12D.0110.一个有n个顶点和n条边的无向图一定是()。A．连通的B．不连通的C．无环的D．有环的11.在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（）辅助结构，判断一条边的两个端点是否在同一个连通分量上。A.位向量B.堆C.并查集D.生成树顶点集合12.设有一个含有200个元素的表待散列存储，用线性探查法解决冲突，按关键码查询时找到一个元素的平均探查次数不能超过1.5，则散列表的长度应至少为（）。（注：平均探查次数的计算公式为Snl={1+1/(1-α)}/2,其中α为装填因子）A.400B.526C.624D.676二、填空题，在横线处填写合适内容（每小题1分，共12分）1.数据结构的逻辑结构包括线性结构和________结构两大类。2.在程序运行过程中不能扩充的数组是__________分配的数组。这种数组在声明它时必须指定它的大小。3.链表只适用于查找。4.设双向循环链表中每个结点的结构为(data,llink,rlink),则结点*p的前驱结点的地址为__________。5.在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有________个结点。6.一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点k的所有祖先的结点数为________个。7.若将一棵树A(B(C,D,E),F(G(H),I))按照左子女-右兄弟表示法转换为二叉树，该二叉树中度为2的结点的个数为________个。8.从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向________继续搜索。9.设图G=(V,E)，其中V={V0,V1,V2,V3}E={(V0,V1),(V0,V2),(V0,V3),(V1,V3)}则从顶点V0开始对图G的深度优先序列总共有________种。10.第i(i=0,1,...,n-2)趟从参加排序的序列中第i个至第n-1个元素中挑选出一个最小元素，把它交换到第i个位置，此种排序方法叫做_____________排序。11.快速排序在最坏情况下的时间复杂度为____________。12.假定对长度n=100的线性表进行索引顺序搜索，并假定每个子表的长度均为n，则进行索引顺序搜索的平均搜索长度为________。三、判断题，在每小题前面打对号表示正确或打叉号表示错误（每小题1分，共10分）1.算法和程序原则上没有区别，在讨论数据结构时二者是通用的。2.插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常被使用。3.栈和队列都是顺序存取的线性表,但它们对存取位置的限制不同。4.将f=1+1/2+1/3+…+1/n转化为递归函数时，递归部分为f(n)=f(n-1)+1/n，递归结束条件为f(1)=1。5.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和中根遍历，则具有相同的结果。6.进行折半搜索的表必须是顺序存储的有序表。7.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。8.对于AOE网络，任一关键活动延迟将导致整个工程延迟完成。9.若将一批杂乱无章的数据按堆结构组织起来,则堆中数据必然按从小到大的顺序排列。10.一棵m阶B树中每个结点最多有m-1个关键码，最少有m/2-1个关键码。四、运算题（前2小题，每小题6分，后3小题，每小题8分，共36分）1.设有一个二维数组A[10][20]，按列为主序存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的存储字地址是多少。2.已知一棵二叉树的静态数组表示（即顺序存储）如下，其中-1表示空，请分别写出该二叉树的前序、中序、后序遍历序列。01234567891011122084651530-1-1-11018-1353.假定一组记录为(38,42,55,15,23,44,30,74,48,26)，按次序插入每个记录生成一棵AVL树，给出最后得到的AVL树中度为2、度为1和度为0的结点个数。4.已知一个带权图的顶点集V和边集G分别为：V={0,1,2,3,4,5,6};E={(0,1)19,(0,2)10,(0,3)14,(1,2)6,(1,5)5,(2,3)26,(2,4)15,(3,4)18,(4,5)6,(4,6)6,(5,6)12};试根据迪克斯特拉(Dijkstra)算法求出从顶点0到其余各顶点的最短路径，即给出所经过的所有顶点。如顶点0到达顶点j需依次经过顶点k1和k2，则最短路径表示为0,k1,k2,j。5.已知有一个四元素的数据表{75,75*,60,18}已经为最大堆，给出在堆排序过程中进行每一趟交换和调整后的数据表变化。五、算法分析题（每小题6分，共18分）1.针对如下算法，回答问题：若数组A[n]={12,24,0,38,0,0,0,0,29,0,45,0},n=12，给出算法执行后数组A[n]的状态。templateclassTvoidunknown(TA[],intn){intfree=0;for(inti=0;in;i++)if(A[i]!=0){if(i!=free){A[free]=A[i];A[i]=0;}free++;}}2.针对如下算法，回答问题：(1)若整型数组A[8]={12,24,33,38,95,83,64,57}，n=8，则给出算法返回的结果。(2)说明算法的功能是什么。intunknown(intA[],intn){if(n==1)returnA[0];inttemp=unknown(A,n-1);returnA[n-1]temp?A[n-1]:temp;}3.已知二叉树中的结点类型BinTreeNode定义为:structBinTreeNode{ElemTypedata;BinTreeNode*left,*right;};其中data为结点值域，left和right分别为指向左、右子女结点的指针域。参数bt指向一棵二叉树，引用参数x一开始具有的值小于树中所有结点的值。试根据下面的函数定义指出此算法的功能。intJB(BinTreeNode*bt,ElemType&x){if(bt==NULL)return1;else{if(JB(bt-left,x)==0)return0;if(bt-datax)return0;x=bt-data;if(JB(bt-right,x)==0)return0;elsereturn1;}}六、算法设计题（每小题6分，共12分）1.设有两个整数类型的顺序表A（有m个元素）和B（有n个元素），其元素均以升序排列。把下面函数补充完整，将这两个顺序表合并成一个顺序表C，要求C的元素也以升序排列（表中允许元素重复）。函数中的参数表给出参加运算的三个顺序表A、B与C。从C中得到执行结果。函数中用到顺序表的4个公有函数：Length()求表的当前长度；maxLength()求表的最大允许长度；getData(intk)提取第k个元素的值；setData(intk,intval)修改第k个元素的值为val。templateclassTvoidmerge(SeqListint&A,SeqListint&B,SeqListint&C){intm=A.Length(),n=B.Length(),mpn=m+n;if(mpnC.maxLength()){cerr“合并后表的长度超出表C的最大允许长度”endl;exit(1);}inti=0,j=0,k=0;intav=A.getData(i),bv=B.getData(j);//向下补充剩余的代码}2.已知二叉树中的结点类型BinTreeNode定义为:structBinTreeNode{chardata;BinTreeNode*left,*right;};其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面函数声明编写出删除一棵二叉树中所有结点的算法，并使树根指针为空。假定引用参数BT初始指向这棵二叉树的根结点。voidClearBTree(BinTreeNode*&BT);