1 / 4
文档名称:

软件技术基础期末考A答案(07).doc

格式:doc   大小:76KB   页数:4页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

软件技术基础期末考A答案(07).doc

上传人:012luyin 2017/10/25 文件大小:76 KB

下载得到文件列表

软件技术基础期末考A答案(07).doc

文档介绍

文档介绍:云南大学2006至2007学年下学期物理科学技术学院物理系2004级
《软件技术基础》期末考试卷A参考答案
任课教师:马琳
一、填空题(共10分,每小题2分)
1、二维数组A[8,10]中的每个元素占2个存储单元,从首地址60开始,采用以行为主的方式
存储,则A[5,3]的地址为 144 。
2、设栈S和队列Q的初始状态为空,元素a1、a2、a3、a4、a5、a6、a7和a8依次通过栈S,
一个元素出栈后即进入队列Q,若8个元素出队的顺序是a4、a6、a5、a7、a3、
a2、a8、a1,则栈的容量至少应该是 5 。
3、已知一个有向图的邻接矩阵表示,第i个结点的入度等于第i行所有非0元素之和。
4、在关系模型中,把数据及数据间关系看成是一个二维表,每一个二维表称为一个关系,
表中每一行称为元组(记录) ,表中每一列称为属性(字段) 。
5、在下面两个关系中,职工号和部门号分别为职工关系和部门关系的主键。
职工(职工号,职工名,部门号,职务,工资)
部门( 部门号,部门名,部门人数,工资总额)
在这两个关系的属性中,只有一个属性是外键,它是职工关系中的部门号。
二、简答题(共12分,每小题4分)
下列程序段的时间复杂度是多少?
y=0;
for i = 1 to n
for j = i to n
y = y + 1;
n+(n-1)+(n-2)+…+1=n(n+1)/2 f(n)=O(n2)
2、对已建好的初始堆(84,79,56,38,46,40)进行堆排序,在输出堆顶元素后,形成的堆是什么?
输出堆顶元素84后,形成的堆是(79,46,56,38,40)
3、在关系模型中,用什么描述事物及事物之间的联系。
在关系模型中,用关系描述事物及事物之间的联系。
三、分析题(共18分)
1、依次输入序列(19、15、7、25、40、54、16、22),构造一棵二叉排序树。若在这棵二叉
排序树中寻找值为25的结点,需要比较多少次?(8分)
19
25
7
16
22
40
54
15
在该排序树中寻找值为25的结点,需要比较2次
写出下列图G的关联矩阵,并用纵向优先搜索法和横向优先搜索法对图G进行遍历(从顶点“A”出发),给出遍历序列(10分)。
A
B
C
D
E
F
A
B
C
D
E
F
B
E
F
D
A
C

纵向优先搜索法遍历序列:ABCDEF
横向优先搜索法遍历序列:ABCFED
四、(15分)设有一线性单链表,试写出一个算法,找出链表中的最小值和最大值并输出,然
后将它们从链表中删除。
procedure smaxmin(head,v,next)
if(head=0) then { print(“空表”) ; return; }
p=maxi=mini=head;
p=next(p);
while(p≠0)do
{ if(V(p)>V(maxi)) then maxi=p ;
if(V(p)<V(mini)) then mini=p ;
}
print(“max=%d , min=%d”, V(maxi), V(mini));
if(max