软件技术基础期末考A答案(08)

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、一个深度为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、对已建好的初始堆（84,76,55,35,46,40）进行堆排序，在输出堆顶元素后，形成的堆是什么？输出堆顶元素84后，形成的堆是（76,46,55,35,40）4、什么是数据库、数据库管理系统和数据库系统。数据库：存储在计算机内的有结构的数据集合。数据库管理系统：以统一的方式管理和维护数据库，并提供访问数据库接口的软件。数据库系统：引入数据库技术后的计算机系统。20101010101010111010101110三、分析题（共21分，每小题7分）1、依次输入序列（20、15、8、25、45、57、16、22），构造一棵二叉排序树。若在这棵二叉排序树中寻找值为45的结点，需要比较多少次？在这棵二叉排序树中寻找值为45的结点，需要比较3次2、写出下列图G的关联矩阵，并用纵向优先搜索法和横向优先搜索法对图G进行遍历(从顶点“A”出发)，给出遍历序列。纵向优先搜索序列为：ABCDE横向优先搜索序列为：ABDCE3、将表达式a×b+c/(d+t)-f(x,y,z)用表达式树表示，再转化成二叉树，最后写出其波兰表达式。表达式树为：二叉树为：波兰表达式为：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);}returnn;ABEDC202581622455715ABCDEABCDE-f*/xzy+bac+dt-*/x+bac+dtyzf3五、（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分）设有一个学生选修课程数据库，包括“学生”、“选修”和“课程”三个关系模式：学生（学号，姓名，性别，年龄，系，电话）选修（学号，课程号，分数）课程（课程号，课程名，教师）要求用关系运算实现：（1）、查找年龄大于19岁的男同学的学号、姓名和电话。（2）、查找所有英语成绩在80分及以上的学生姓名及所在的系。（1）、T=年龄19性别=“男”（学生）学号，姓名，电话（T）（2）、KC=学生选修课程T=课程名=“英语”分数=80（KC）姓名，系（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分(包含180分)的所有学生的SQL命令。（3）、写出查询信息学院平均分在90分及以上学生的学号、姓名、高数、普物、英语、总分的SQL命令。（1）、该表的结构为：（2）、select*from学生where总分=180;（3）、select学号，姓名，高数，普物，英语，总分from学生where学院=“信息”and平均分=90；学号姓名性别学院高数普物英语总分平均分