[精品]软件技术基础期末考A答案(08).doc

《[精品]软件技术基础期末考A答案(08).doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、云南大学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[l,l]的地址是100,则A[6,8]的地址为207。3、一

2、个深度为5的二叉树至多有31个结点。4、在关系模型屮，把数据及数据间关系看成是一个二维表，每一个二维表称为一个从表屮每一行称为无爼，表屮每一列称为属世,5、设循环队列的容量为100(序号从1到100),现经过一系列的入队和退队运算后，有front二50,rear=20,贝lj循环队列屮有70个元素。二、简答题(共12分，每小题3分)1、下列程序段的时间复杂度是多少？y=o；fori=Itonforj=itony=y+1；n+(n-1)+(n-2)+...+1=n(n+1)/2f(n)=O(n2)2、线

3、性表、栈、队列有何异同。相同点；都是狡档詹构；耒同点；狡档素滋在仪何佞置遊行插入、刪除；栈H滋在一端址行插入、刪險；汽列耳滋在一境遊行插入、在另一境遊行刪險。3、对己建好的初始堆(84,76,55,35,46,40)进行堆排序，在输出堆顶元素后，形成的堆是什么？偷出维顶免素％后，形啟的堆足(76,46,55,35,40；4、什么是数据库、数据库管理系统和数据库系统。歎据涼：矗储在针篇机內的韦猪构的歎据集合。赦据殊管理g：g—輪方式管理和施护赦据殊，笄提供彷同叙倨漳接口的怨件。褻据殊系傥勿入褻据殊技术后

4、的针篇机系傥。三、分析题(共21分，每小题7分)1、依次输入序列(20、15、8、25、45、57、16、22),构造一棵二叉排序树。若在这棵二叉排序树屮寻找值为45的结点，需要比较多少次？2、写出下列图G的关联矩阵，点岀发)，给岀遍历序列。D并用纵向优先搜索法和横向优先搜索法对图G进行遍历(从顶A01010BI0I0IC01011E0_1110侬向优屯捜索為列笛；ABODE横向优屯捜索瀋列笛；ABDCE3、将表达式axb4-c/(d+t)-f(x,y,z)用表达式树表示，再转化成二叉树，最后写出其波

5、兰表达式。波罡豢达式务；ab*cdt+/+xyzf-四、(15分)有一个线性单链表(不同结点的数据域值可能相同)，其头指针为head,编写一个算法，计算数据域为x的结点个数。proceduresearch(head,v,next,x)p=head;n=0while(p^O)do{ifv(p)=xthenn=n+l;p=next(p);}returnn;五、(15分)用简单选择排序法对有n个兀素的线性表进行排序，写出其算法。procedureselesort(pzn)fori=lton-1{k=i；fo

6、rj=i+ltonifp(j)>p(k)thenk=j;if(k*j)then{d=p(i);p⑴=p(k);p(k)=d;}}return;六、(15分)设有一个学生选修课程数据库，包括“学生”、“选修”和“课程”三个关系模式:学生(学号，姓名，性别，年龄，系，电话)选修(学号，课程号，分数)课程(课程号，课程名，教师)要求用关系运算实现：(1)、查找年龄大于19岁的男同学的学号、姓名和电话。(2)、查找所有英语成绩在80分及以上的学生姓名及所在的系。⑴、T=C年龄〉］9A性别=“男”(事生)H学号

7、，姓名，电话(T)⑵、KC=学牛X选修X课程T=b谀程名=“英语”A分数＞=8()(KC)Fk：名，系(T)七、(12分)应用SQL语言命令完成下述任务:(1)、执彳亍SQL命令：createtable学生(学号char(5)notnull,姓名char(8)notnull,性别char(2)notnull,学院char(10),高数int,普物int,英语int,总分int,平均分dec(5,2))；画出这张表的空表结构图。(2)、如果丄述学生成绩表已输入了多个记录数据，写出查询总分在180分(包含

8、180分)的所有学生的SQL命令。(3)、写出查询信息学院平均分在90分及以上学生的学号、姓名、高数、普物、英语、总分的SQL命令。曇号普扬总今⑴、该素的猪构务；⑵、select*from学生where总分〉=180;⑶、select学号，姓名，高数，普物，英语，总分from学生where学院=“信息”and平均分〉=90；