资源描述:
《软件技术基础期末考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[1,1]的地址是100,则A[6,8]的地址为207。3
2、、一个深度为5的二叉树至多有31个结点。4、在关系模型中,把数据及数据间关系看成是一个二维表,每一个二维表称为一个关系,表中每一行称为元组,表中每一列称为属性。5、设循环队列的容量为100(序号从1到100),现经过一系列的入队和退队运算后,有front=50,rear=20,则循环队列中有70个元素。二、简答题(共12分,每小题3分)1、下列程序段的时间复杂度是多少?y=0;fori=1tonforj=itony=y+1;n+(n-1)+(n-2)+…+1=n(n+1)/2f(n)=O(n2)2
3、、线性表、栈、队列有何异同。相同点:都是线性结构;不同点:线性表能在任何位置进行插入、删除;栈只能在一端进行插入、删除;队列只能在一端进行插入、在另一端进行删除。3、对已建好的初始堆(84,76,55,35,46,40)进行堆排序,在输出堆顶元素后,形成的堆是什么?输出堆顶元素84后,形成的堆是(76,46,55,35,40)4、什么是数据库、数据库管理系统和数据库系统。数据库:存储在计算机内的有结构的数据集合。数据库管理系统:以统一的方式管理和维护数据库,并提供访问数据库接口的软件。数据库系统:
4、引入数据库技术后的计算机系统。三、分析题(共21分,每小题7分)1、依次输入序列(20、15、8、25、45、57、16、22),构造一棵二叉排序树。若在这棵二叉排序树中寻找值为45的结点,需要比较多少次?202581622455715在这棵二叉排序树中寻找值为45的结点,需要比较3次1、写出下列图G的关联矩阵,并用纵向优先搜索法和横向优先搜索法对图G进行遍历(从顶ABEDC点“A”出发),给出遍历序列。ABCDEABCED纵向优先搜索序列为:ABCDE横向优先搜索序列为:ABDCE3、将表达式a
5、×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=0while(p≠0)do{ifv(p)=xthenn=n+1;p=next(p);}re
6、turnn;五、(15分)用简单选择排序法对有n个元素的线性表进行排序,写出其算法。procedureselesort(p,n)fori=1ton-1{k=i;forj=i+1tonifp(j)>p(k)thenk=j;if(k≠j)then{d=p(i);p(i)=p(k);p(k)=d;}}return;六、(15分)设有一个学生选修课程数据库,包括“学生”、“选修”和“课程”三个关系模式:学生(学号,姓名,性别,年龄,系,电话)选修(学号,课程号,分数)课程(课程号,课程名,教师)要求用关系
7、运算实现:(1)、查找年龄大于19岁的男同学的学号、姓名和电话。(2)、查找所有英语成绩在80分及以上的学生姓名及所在的系。(1)、T=s年龄>19L性别=“男”(学生)Õ学号,姓名,电话(T)(2)、KC=学生选修课程T=s课程名=“英语”L分数>=80(KC)Õ姓名,系(T)七、(12分)应用SQL语言命令完成下述任务:(1)、执行SQL命令:createtable学生(学号char(5)notnull,姓名char(8)notnull,性别char(2)notnull,学院char(10),
8、高数int,普物int,英语int,总分int,平均分dec(5,2));画出这张表的空表结构图。(2)、如果上述学生成绩表已输入了多个记录数据,写出查询总分在180分(包含180分)的所有学生的SQL命令。(3)、写出查询信息学院平均分在90分及以上学生的学号、姓名、高数、普物、英语、总分的SQL命令。学号姓名性别学院高数普物英语总分平均分(1)、该表的结构为:(2)、select*from学生where总分>=180;(3)、select学号,姓名,高数,普物,英语,总分fro