软件技术基础期末考A(06).doc

云南大学2005至2006学年下学期物理科学技术学院物理系2003级
《软件技术基础》期末考试卷(闭卷)试卷A
满分100分考试时间:120分钟 任课教师:马琳
学院专业学号姓名
题号
一
二
三
四
五
六
总分
得分
得分
一、填空题(共10分,每小题2分)
1、在线性单链表中,若一个元素所在结点的地址为p,则其后继结点的地址为。
2、二维数组A[10,20]采用以行为主的方式存储,每个元素占一个存储单元,并且A[1,1]的存储地址是100,则A[6,8]的地址为。
3、一个深度为4的二叉树至多有个结点。
4、采用邻接矩阵表示一个具有n个顶点的图,该矩阵大小应为。
5、设循环队列的容量为100(序号从1到100),现经过一系列的入队和退队运算后,有
front=50,rear=20,则循环队列中有个元素。
得分
二、简答题(共15分,每小题3分)
下列程序段的时间复杂度是多少?
y=0;
for i = 1 to n
for j = 1 to i
y = y + 1;
2、数组是一种什么类型的数据结构,它进行的主要操作是什么?
EA
FCA
DCA
A
CA
BA
3、如图是一个数据结构的图形表示,给出它的数据结构定义。
4、有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},
当用二分查找法查找值为82的结点时,经过几次比较后查找成功。
5、什么是数据库、数据库管理系统和数据库系统。
得分
三、分析题(共30分)
1、依次输入序列(18、12、9、23、45、57、16、22),构造一棵二叉排序树。若在这棵二叉
排序树中寻找值为45的结点,需要比较多少次?(8分)
写出下列图G的关联矩阵,并用纵向优先搜索法和横向优先搜索法对图G进行遍历(从顶
A
B
E
D
C
点“A”出发),给出遍历序列(10分)。
3、应用SQL语言命令完成下述任务:(共12分)
(1)、执行SQL命令:create table 学生(学号 char(5) not null , 姓名 char(8) not null,
性别 char(2) not null, 学院 char(10), 数学 int , 物理 int , 外语 int , 总分 int ,