软件技术基础期末考答案B(06)

1云南大学2005至2006学年下学期物理科学技术学院物理系2003级《软件技术基础》期末考试卷试卷B参考答案任课老师：马琳一、填空题（共10分，每小题2分）1、在顺序链表中，一个元素占用一个存储单元，若一个元素所在结点的地址为p，则其后继结点的地址为p+1。2、矩阵A是对称矩阵，为节省空间，将其下三角部分按行为主存储在一维数组B[1..n(n-1)/2]中，对任一下三角部分元素aij(i≥j)，在一维数组B的下标位置k的值i(i-1)/2+j。3、在无向图G的邻接矩阵A中，若A[i,j]=1，则A[j,i]等于1。4、设栈S的初始状态为空，若元素的入栈顺序为a1、a2、a3、a4、a5、a6，出栈顺序为a3、a5、a6、a4、a2、a1，则栈的容量至少应该是______4_________。5、有一种数据结构B=(D,R)，其中D={a,b,c,d,e}，R={(a,b),(a,c),(b,c),(c,d),(c,e),(d,e)}，它是什么类型的数据结构（线性表、树还是图）图。二、简答题（共15分，每小题3分）1、下列程序段的时间复杂度是多少？y=10;x=2;fori=1ton-1{y=y+1；forj=1to2*nx=x+1；}(n-1)×2n=2n2-2nf(n)=O(n2)2、已知一个图的关联矩阵表示，删除所有从第i个结点出发的边的方法是什么。在关联矩阵中将第i行所有列置03、在观念世界中，用什么描述事物及事物之间的联系。在观念世界中用实体描述事物，用概念模型描述事物之间的联系。4、数据结构的存储方式有几种？它们之间的本质区别是什么？数据结构的存储方式有两种，它们之间的本质区别是存储联系R的方式不同。25、设线性哈希表的长度为=8，哈希函数为H（i）=mod(k，n)，将关键字系列（12，09，04，16，19，20，45，26）依次填入随机哈希表中，并注明冲突次数。12345678092619120420451600001220三、分析题（共30分）1、已知一棵二叉树的前序遍历序列为DGKLNM，中序遍历序列为KNLMGD，请画出该二叉树，并写出它的后序遍历序列。（8分）二叉树如图所示其后序遍历序列为：NMLKGD2、用希尔排序法对线性表{81，57，22，96，42，04，78，60}进行排序，要求给出其中每一步的结果。（10分）第一遍调整后序列(h=4)：42，04，22，60，81，57，78，96第二遍调整后序列(h=2)：22，04，42，57，78，60，81，96第三遍调整后序列(h=1)：04，22，42，57，60，78，81，963、应用SQL语言命令完成下述任务：（12分）（1）、执行SQL命令：createtable学生(学号char(8)notnull,姓名char(8)notnull,性别char(2),出生日期datetime,籍贯char(10),专业char(12))画出这张表的空表结构图（4分）（2）、如果上述学生成绩表已输入了多个记录数据，写出查询籍贯为“昆明”全部学生的SQL命令（4分）（3）、写出查询物理专业的全体男生学号和姓名的SQL命令（4分）（1）该表的结构为：学号姓名性别出生日期籍贯专业（2）、select*from学生where籍贯=“昆明”;（3）、select学号，姓名from学生where专业=“物理”and性别=“男”；四、（15分）编写一个算法，产生一个有5个结点的单链表，这些结点数据域的值从键盘上输入，且表头结点指针是head。GDKLNM3procedurecreatehead(head,v,next)fori=0to4do{readx;new(p);v(p)=x;next(p)=0;ifi=0thenhead=p;else{next(p)=head;head=p;}}return;五、（15分）设L(1:n)是一个包含n个元素的有序表，写出用对分查找法查找元素x的算法。proceduresearch(v,n,x,k)i=1;j=n;while(i=j)do{k=(i+j)/2;ifv(k)=xthenreturn;ifv(k)xthenj=k-1;elsei=k+1;}ifijthenk=-1return;六、（15分）设有一数据库，包括供应商表S、零件表P、工程项目表J和供应情况表SPJ四个关系模式：S(供应商代码，供应商名，供应商电话，供应商所在城市)；P(零件代码，零件名，颜色，重量)；J(工程项目代码，工程项目名，工程项目所在城市)；SPJ(供应商代码，零件代码，工程项目代码，供应量)；其中供应量表示某供应商供应某种零件给某工程项目的数量。现要求用关系运算实现：（1）、查找地址在昆明的供应商名和电话；（7分）（2）、查找在上海的工程项目使用红色零件的工程项目代码。（8分）（1）、T=供应商所在城市=“昆明”（S）供应商名，供应商电话（T）（2）、PJ=PSPJJT=工程项目所在城市=“上海”颜色=“红色”（PJ）工程项目代码（T）