文档介绍：该【软件技术基础期中(07) 】是由【薛定谔的猫】上传分享，文档一共【4】页，该文档可以免费在线阅读，需要了解更多关于【软件技术基础期中(07) 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。云南大学2006至2007学年下学期物理科学技术学院物理系2004级
《软件技术基础》期中考试卷(闭卷)
满分100分 考试时间:120分钟 任课教师:马琳
学院专业学号姓名
题号
一
二
三
四
五
六
七
总分
得分
得分
一、填空题(10分,每题2分):
1、在算法是正确的前提下,评价一个算法的两个标准是和。
2、数据逻辑结构可分为两大类,它们分别是和。
3、数据结构的存储应存储两方面的内容,它们分别是和;数据存
储结构也可分为两大类,它们分别是和。
4、一个栈的输入序列是12345,如果栈的输出序列为43512,是否可能;一个栈
的输入序列是12345,如果栈的输出序列为21345,是否可能;
5、矩阵A是对称矩阵,为节省空间,将其下三角部分按行为主存储在一维数组B[1..n(n-1)/2]
中,对任一下三角部分元素aij(i≥j),在一维数组B的下标位置k的值。
得分
二、简答题(21分,每题3分)
下列程序段的时间复杂度是多少?
y=0;
fori=1Ton
forj=1Toi
y=y+1;
BA
A
DCA
CA
EA
FCA
如图是一个数据结构的图形表示,给出它的数据结构定义。
3、有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当用二分查找法
查找值为82的结点时,经过几次比较后查找成功。
4、已知一棵二叉树的前序遍历序列为DGKLNM,中序遍历序列为KNLMGD,请画出该二叉
树,并写出它的后序遍历序列。
5、数据结构的存储方式有几种?它们之间的本质区别是什么?
6、已知一个图的关联矩阵表示,删除所有从第i个结点出发的边的方法是什么。
7、数组是一种什么类型的数据结构,它进行的主要操作是什么?
得分
三、(14分)试用三列二维数组和十字链表分别表示如下稀疏矩阵。
ú
ú
ú
ú
ú
ú
û
ù
ê
ê
ê
ê
ê
ê
ë
é
-
0
2
7
0
6
0
1
0
0
0
0
0
00
4
0
7
0
0
0
0
0
3505
050
0
98
得分
四、(10分)设线性哈希表的长度n=8,哈希函数H(i)=mod(k,n),将关键字系列(12,09,04,16,19,20,45,26)依次填入线性哈希表,并指出各关键字元素在填入过程中冲突次数。
得分
五、(15分)编写一个算法,产生一个有5个结点的单链表,这些结点数据域的值从键盘上输入,表头结点指针是head。
得分
六、(15分)编写一个算法,计算一个以顺序存储结构存放的循环队列中元素的
个数(s=0队空;s=1且front=rear时队满)。
得分
七、(15分)设L(1:n)是一个包含n个元素的有序表,写出用对分查找法查找元
素x的算法。