试题(张艳玲)-6

学院领导审批并签名AB卷广州大学学年第学期考试卷课程数据结构与算法考试形式（闭卷，考试）信息学院系专业级班学号：姓名：题次一二三四五六总分评卷人分数201010302010100评分一、填空题：（每空2分，共20分）1.抽象数据类型的特点是________、________、使用与实现分离。2.算法的一个特性是________，即算法必须执行有限步就结束。3、一维数组所占用的空间是连续的。但数组元素不一定顺序存放，而是按元素的_________存放的。4、将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则一维数组需要存储_________个矩阵元素。5、在单链表中设置表头结点的作用是在插入和删除表中第一个元素时不必对________进行特殊处理。6、中缀表达式3*(x+2)-5所对应的后缀表达式为________。7、广义表A((a,b,c),(d,e,f))的表尾为________。8、假定一棵三叉树（即度为3的树）的结点个数为50，则它的最小高度为______。假定根结点的高度为0。9、101个顶点的连通网络N有100条边，其中权值为1,2,3,4,5,6,7,8,9,10的边各10条，则网络N的最小生成树各边的权值之和为_________。二、单项选择题（每空1分，共10分）1.一个数组元素a[i]与（）的表示等价。A.*(a+i)B.a+iC.*a+iD.&a+i2.一种抽象数据类型包括数据和（）两个部分。A.数据类型B.操作C.数据抽象D.类型说明3.以下说法错误的是（）。A.抽象数据类型具有封装性。B.抽象数据类型具有信息隐蔽性。C.抽象数据类型的用户可以自己定义对抽象数据类型中数据的各种操作。D.抽象数据类型的一个特点是使用与实现分离。4、在一个长度为n的顺序表中顺序搜索一个值为x的元素时，在等概率的情况下，搜索成功的数据平均比较次数为（）。A.nB.n/2C.(n+1)/2D.(n-1)/25、在一个长度为n的顺序表中向第i个元素（0≤i≤n）位置插入一个新元素时，需要从后向前依次后移（）个元素。A.n-iB.n-i+1C.n-i-1D.i6、不带头结点的单链表first为空的判定条件是：A.first==NULL;B.first-link==NULL;C.first-link==first;D.first!=NULL;7、栈的插入和删除操作在（）进行。A.栈顶B.栈底C.任意位置D.指定位置8、在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形，需为对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（），在被调用程序中可直接操纵实际参数。A.空间B.地址C.返回地址D.副本9、在一棵树中，（）没有前驱结点。A.分支结点B.叶结点C.根结点D.空结点10、在一个带权连通图G中，权值最小的边一定包含在G的（）生成树中。A.某个最小B.任何最小C.广度优先D.深度优先三、判断题（在括号内填上“√”或“╳”，每题1分，共10分，做错不倒扣）1.（）数据结构是具有结构的数据对象。2、（）数据结构是指相互之间存在一种或多种关系的数据元素的全体。3、（）数组是一种静态的存储空间配置，就是说，在程序设计时必须预先定义数组的数据类型和存储空间大小，由编译程序在编译时进行配置。4、（）n阶三对角矩阵总共n2个矩阵元素中最多只有3n-2个非零元素，因此它是稀疏矩阵。5、（）链式存储在插入和删除时需要保持数据元素原来的物理顺序，不需要保持原来的逻辑顺序。6、（）若让元素1,2,3依次进栈，则出栈次序3,1,2是不可能出现的情况。7、（）递归调用算法与相同功能的非递归算法相比，主要问题在于重复计算太多，而且调用本身需要分配额外的空间和传递数据和控制，所以时间与空间开销都比较大。8、（）在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的遍历结果。9、（）如果无向图中各个顶点的度都大于2，则该图中必有回路。10、（）当输入序列已经有序时，起泡排序需要的排序码比较次数比快速排序要少。四、计算题/画图题/证明题（30分）1.指出算法的功能并求出其时间复杂度。voidmatrimult(inta[][],intb[][],intc[][],intM,intN,intL){//数组a[M][N]、b[N][L]、c[M][L]均为整型数组inti,j,k;for(i=0;iM;i++)for(j=0;jL;j++){c[i][j]=0;for(k=0;kN;k++)c[i][j]+=a[i][k]*b[k][j];}}2、对于一个nn的矩阵A的任意矩阵元素a[i][j]，按行存储时和按列存储时的地址之差是多少。（若设两种存储的开始存储地址LOC(0,0)及元素所占存储单元数d相同）3、设散列表的长度m=13；散列函数为H(K)=K%m，给定的关键码序列为19,14,23,01,68,20,84,27,55,11，试画出用线性探查法解决冲突时所构造的散列表。并求出在等概率的情况下，这种方法的搜索成功时的平均搜索长度和搜索不成功时的平均搜索长度。4、设一有向图如下所示，请问该有向图是否为强连通图，并画出该有向图所有的强连通分量。gfecabd五、程序填空/写程序结果或程序功能（20分）1、针对如下算法，回答问题：(1)说明若数组A[]={12,24,0,38,0,0,0,0,29,0,45,0},n=12，算法执行的结果。(2)说明算法的功能是什么。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、若设单链表结点的结构为ListNode=(data,link)，阅读以下函数：voidunknown(LinkListHa){//Ha为指向带头结点的单链表的头指针,且头结点的data域中含元素oif(Ha!=NULL){unknown(Ha-link);coutHa-data)endl;}}若线性表L=(a,b,c,d,e,f,g)，则执行语句unknown(L)之后输出的结果是_________________。3、写出下列程序段的输出结果:voidmain(){queueQ;charx='e',y='c';Q.EnQueue('h');Q.EnQueue('r');Q.EnQueue(y);Q.DeQueue(Q,x);Q.EnQueue(x);Q.DeQueue(x);Q.EnQueue('a');while(!Q.IsEmpty()){Q.DeQueue(y);couty;}coutyendl;}输出结果：______________________4、已知二叉树中的结点类型用BinTreeNode表示，被定义为:structBinTreeNode{chardata;BinTreeNode*leftChild,*rightChild;};其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。假定一棵二叉树采用链接存储，它的广义表表示为r(b(,d(f,g)),t(e))，rt,bt,dt和et指针变量分别保存指向r,b,d和e结点的指针值，则：(1)执行BTM(rt)调用后，得到的函数值为________;(2)执行BTM(bt)调用后，得到的函数值为________;(3)执行BTM(dt)调用后，得到的函数值为________;(4)执行BTM(et)调用后，得到的函数值为________;charBTM(BinTreeNode*BT){staticcharmax=0;if(BT!=NULL){chark1,k2;k1=BTM(BT-leftChild);k2=BTM(BT-rightChild);if(k1max)max=k1;elseif(k2max)max=k2;elseif(BT-datamax)max=BT-data;}returnmax;}六、算法设计（10分）写出二路归并排序的算法程序。