文档介绍：云南大学2007至2008学年下学期物理科学技术学院物理系2005级
《软件技术基础》期末考试卷(闭卷)试卷A
满分100分 考试时间：120分钟 任课教师：马琳
学院 专业 学号 姓名
题号
—*
二
四
五
七
总分
得分
得分| 一、填空题(共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[l, 1]
的地址是100,则A[6,8]的地址为 o
3、 一个深度为5的二叉树至多有 个结点。
4、 在关系模型中，把数据及数据间关系看成是一个二维表，每一个二维表称为一个
表中每一行称为,表中每一歹U称为 o
5、 设循环队列的容量为100(序号从1到100),现经过一系列的入队和退队运算后，有
front=50, rear=20,则循环队列中有 个元素。
得分 二、简答题(共12分，每小题3分)
1、 下列程序段的时间复杂度是多少？
y=o；
for i = 1 to n
for j = i to n
y = y +1；
2、 线性表、栈、队列有何异同。
3、对已建好的初始堆(84,76,55,35,46,40)进行堆排序，在输出堆顶元素后，形成的堆是什么？
4、什么是数据库、数据库管理系统和数据库系统。
得分 三、分析题（共21分，每小题7分）
1、依次输入序列（20、15、8、25、45、57、16、22）,构造一棵二叉排序树。若在这棵二叉 排序树中寻找值为45的结点，需要比较多少次？
2、写出下列图G的关联矩阵，并用纵向优先搜索法和横向优先搜索法对图G进行遍历（从顶
点“A”出发），给出遍历序列。
3、将表达式axb+c/（d+t）-f（x,y,z）用表达式树表示，再转化成二叉树，最后写出其波兰表达式。
得分 四、（15分）有一个线性单链表（不同结点的数据域值可能相同），其头指针 为head,编写一个算法，计算数据域为x的结点个数。
得分 五、（15分）用简单选择排序法对有n个元素的线性表进行排序，写出其算法。
得分
六、(15分