文档介绍：云南大学2005至2006学年下学期物理科学技术学院物理系2003级《软件技术基础》期末考试卷(闭卷)试卷B满分100分考试时间:120分饼任课教师:马琳学院 专业学号 得分得分题号—二三•■五总分得分•、填空题(共10分,每小题2分)1、 在顺序链表中,一个元索占用一个存储单元,若一个元索所在结点的地址为p,则其后继结点的地址为 O2、 矩阵A是一个对称矩阵,为节省空间,将其下三角部分按行为主存储在一维数组B[l..n(n-1)/2]'P,对任一下三角部分元素Wj(i2j),在一维数组B的下标位置k的值是 □3、 在无向图G的邻接矩阵A屮,若A[i,j]二1,则A[j,i]等于 。4、设栈S的初始状态为空,若元索的入栈顺序为81、边、、a5、a6,出栈顺序为迪、a5、a6、a4、a2、al,则栈的容量至少应该是 。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=1tornl{y=y+i;forj=1to2*nx=x+1:}2、已知一个图的关联矩阵表示,删除所有从第i个结点出发的边的方法是什么。3、在观念世界屮,用什么描述事物及事物之间的联系。4、数据结构的存储方式有几种?它们Z间的本质区别是什么?5、设线性哈希表的长度为=8,哈希函数为H(i)=mod(k,n),将关键字系列(12,09,04,16,19,20,45,26)依次填入线性哈希表屮,并注明冲突次数。得分三、分析题(共30分)1、已知一棵二叉树的前序遍历序列为DGKLNM,屮序遍历序列为KNLMGD,请画出该二叉树,并写出它的后序遍历序列。(8分)2、用希尔排序法对线性表{81,57,22,96,42,04,78,60}进行排序,要求给出其中每一步的结果。(10分)3、应用SQL语言命令完成下述任务:(12分)(1) 、执彳亍SQL命令:createtable学生(学号char(8)notnull,姓名char(8)notnull,性别char(2),出生日期datetime,籍贯char(10),专业char(⑵)画出这张表的空表结