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

1云南大学2004至2005学年下学期数理学院物理系2002级《软件技术基础》期末考试卷(闭卷)试卷B满分100分考试时间:120分钟任课教师:马琳学院专业学号姓名题号一二三四五六七总分得分一、简答题(本大题共5小题,每小题2分,共10分)1、当分E-R图合并为初步E-R图时,可能会出现冲突,冲突可能会出现在那几个方面?。2、一组序列为{46、79、56、38、40、84},利用堆排序的方法建立的初始堆是什么?3、下列程序段的时间复杂性是多少?Sum=0;fori=1Ton{p=1;forj=1Toip=p*j;sum=sum+p;}4、设有8个顶点的无向图,该图至少应有几条边才能确保是一个连通?5、数据结构的存储方式有几种?它们之间的本质区别是什么?二、填空题(本大题共5小题,每小题2分,共10分)1、已知一个有向图的邻接矩阵表示,计算第i个结点的入度的方法是________________。2、在双向链表中,每个结点有两个指针域,一个指向_________,另一个指向_________。3、如要求一个线性表既能很快地查找,又能适应动态变化的要求,在分块查找法、顺序查找法和二分查找法中最好采用哪种方法______________。4、根据所用数据模型的不同,数据库系统可以分为______________、________________、_________________三类。5、将递归算法转换为非递归算法时,通常需要使用_____来存储尚待处理的元素。2三、(15分)试用三列二维数组和十字链表分别表示如下稀疏矩阵。四、(20分)设有一个学生选修课程数据库,包括“学生XS”、“选修XX”和“课程KC”三个关系模式:XS(学号,姓名,性别,年龄,系,年级,)XX(学号,课程号,学分,分数)KC(课程号,课程名,教师名)现要求:(1)在课程关系中插入元组(W1,物理,张明)(2)