文档介绍：云南大学2007至2008学年下学期物理科学技术学院物理系2005级《软件技术基础》期末考试卷A参考答案任课教师:马琳一、填空题(共10分,每小题2分)1、数据结构B=(D,R),其中D={a,b,c,d,e,f,g,h},R={(a,b),(a,c),(a,d),(b,e),(c,f),(c,g),(c,h)},它是什么类型的数据结构(线性表、树还是图)树2、二维数组A[10,20]采用以行为主的方式存储,每个元素占1个存储单元,首元素A[1,1]的地址是100,则A[6,8]的地址为207。3、一个深度为5的二叉树至多有31个结点。4、在关系模型中,把数据及数据间关系看成是一个二维表,每一个二维表称为一个关系,表中每一行称为元组,表中每一列称为属性。5、设循环队列的容量为100(序号从1到100),现经过一系列的入队和退队运算后,有front=50,rear=20,则循环队列中有70个元素。二、简答题(共12分,每小题3分)下列程序段的时间复杂度是多少? y=0; fori=1tonforj=iton y=y+1;n+(n-1)+(n-2)+…+1=n(n+1)/2f(n)=O(n2)2、线性表、栈、队列有何异同。相同点:都是线性结构;不同点:线性表能在任何位置进行插入、删除;栈只能在一端进行插入、删除;队列只能在一端进行插入、在另一端进行删除。3、对已建好的初始堆(84,76,55,35,46,40)进行堆排序,在输出堆顶元素后,形成的堆是什么?输出堆顶元素84后,形成的堆是(76,46,55,35,40)4、什么是数据库、数据库管理系统和数据库系统。数据库:存储在计算机内的有结构的数据集合。数据库管理系统:以统一的方式管理和维护数据库,并提供访问数据库接口的软件。数据库系统:引入数据库技术后的计算机系统。三、分析题(共21分,每小题7分)1、依次输入序列(20、15、8、25、45、57、16、22),构造一棵二叉排序树。若在这棵二叉排序树中寻找值为45的结点,需要比较多少次?202581622455715在这棵二叉排序树中寻找值为45的结点,需要比较3次写出下列图G的关联矩阵,并用纵向优先搜索法和横向优先搜索法对图G进行遍历(从顶ABEDC点“A”出发),给出遍历序列。ABCDEABCED纵向优先搜索序列为:ABCDE 横向优先搜索序列为:ABDCE3、将表达式a×b+c/(d+t)-f(x,y,z)用表达式树表示,再转化成二叉树,最后写出其波兰表达式。-f*/xzy+bac+dt-*/x+bac+dtyzf表达式树为:二叉树为:波兰表达式为:ab*cdt+/+xyzf-四、(15分)有一个线性单链表(不同结点的数据域值可能相同),其头指针为head,编写一个算法,计算数据域为x的结点个数。proceduresearch(head,v,next,x) p=head; n=0 while(p≠0)do { ifv(p)=xthenn=n+1; p=next(p); } returnn;五、(15分)用简单选择排序法对有n个元素的线性表进行排序,写出其算法。procedureselesort(p,n) fori=1ton-1 { k=i; forj=i+1ton ifp(j)>p(k)thenk=j; if(k≠j)then { d=p(i);