文档介绍:云南大学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分