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

软件技术基础期末考B(08).doc云南大学2007至2008学年下学期物理科学技术学院物理系2005级《软件技术基础》期末考试卷(闭卷)试卷B满分100分考试时间:120分排任课教师:马琳学院专业学号姓名得分得分二、简答题(共12分,每小题3分)题号・▲.♦,五七总分得分•、填空题(共10分,每小题2分)1、 在顺序链表中,一个元素占用一个存储单元,若一个元素所在结点的地址为p,则其后继结点的地址为O2、 一,个长度为n的线性表,采用顺序存储结构,删除第i个元素(IWiWn)时,需向前移动 个元素。3、 在无向图G的邻接矩阵A中,若A[i,j]=l,则A[j,i]等于o4、 设栈S的初始状态为空,若元素的入栈顺序为al、a2、a3、a4、a5、a6,出栈顺序为a3、a5、a6、a4、a2、al,则栈的容量至少应该是5、关系模型用来表示实体本身及其相互之间的联系。1、下列程序段的时间复杂度是多少?y=10;x=2;fori=1ton-1(y=y+i;forj=1to2*nX=X4-1;2、己知一个图的关联矩阵表示,删除所有从第i个结点出发的边的方法是什么。3、在观念世界中,用什么描述事物及事物之间的联系。4、数据结构的存储方式有几种?它们之间的本质区别是什么?得分三、分析题(共21分,每小题7分)1、已知一棵二叉树的前序遍历序列为DGKLNM,中序遍历序列为KNLMGD,请画出该二叉树,并写出它的后序遍历序列。2、用希尔排序法对线性表{81,57,22,96,42,04,78,60}进行排序,要求给出其中每一步的结果。3、有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当用二分查找法查找值为45的结点时,经过几次比较后查找成功。得分I四、(域的值从键盘上输入,得分I五、(找元素X的算法。15分)编写一•个算法,产生一个有5个结点的单链表,这些结点数据且表头结点指针是head□分)设L(l:n)是一个包含n个元素的有序表,写出用对分查找法查得分|六、(15分)设有一数据库,包括供应商表S、零件表P、工程项目表J和供应情况表SPJ四个