软件技术基础期末考B(07).doc

软件技术基础期末考B(07).doc云南大学2006至2007学年下学期物理科学技术学院物理系2004级《软件技术基础》期末考试卷(闭卷)试卷B满分100分考试时间:120分排任课教师:马琳学院专业学号姓名得分2、如图是一个数据结构的图形表示,给出它的数据结构定义。3、什么是数据库、数据库管理系统和数据库系统。题号.■■五六七总分W7T•、填空题(共10分,每小题2分)1、 在线性单链表中,一个元素占用一个存储单元,若一个元素所在结点的地址为p,则其后继结点的地址为 next(p)o2、 在算法是正确的前提下,评价一•个算法的两个标准是时间复杂度和室间复杂度。3、 在无向图G的邻接矩阵A中,若A[i,j]=L则A[j,i]等于1。4、 设栈S的初始状态为空,若元素的入栈顺序为al、a2、a3、a4、a5、a6,出栈顺序为&3、a5、a6、a4、a2、al,则栈的容量至少应该是。5、 在数据库中拥关系模型来表示实体和实体间联系。关系模型的结构是".维表结构。得分|二、简答题(共12分,每小题4分)1、下列程序段的时间复杂度是多少?y=10; x=2;fori=1ton-1(y=y+i;forj=1tonx=x4-I;}(n-1)X2n=2n?-2nf(n)=0(n2)得分三、分析题(共18分)1、已知一棵二叉树的前序遍历序列为DGKLNM,中序遍历序列为KNLMGD,请画出该二叉树,并写出它的后序遍历序列。(8分)二叉树如图所示其后序遍历序列为:NMLKGD2、用希尔排序法对线性表{81,57,22,96,42,04,'步的结果。(10分)第一遍调整后序列(h=4):42,04,22,60,81,57,78,96第二遍调整后序列(h=2):22,04,42,57,78,60,81,96第三遍调整后序列(h=l):04,22,42,57,60,78,81,96DGN丑行at炒,要求给出其中每一得分四、(15分)编写一个算法,计算线性单链表的长度,并考虑表为空的情况。得分五、(15分)设L(l:n)是一个包含n个元素的线性表,用简单选择排序法对该线性表进行排序,写出其算法。得分|六、(15分)设有一数据库,包括供应商表S、零件表P、工程项目表J和供应情况表SPJ四个关系模式:S(供应商代码,供应商名,供应商电话,供应商所在城市);P(零件代码,零件名,颜色,重量);J(工程项目代码,工程项目名,工程项目所在城市);SPJ(供应商代码,零件代码,工程项目代码,供应量);其中供应量表