下12软件工程《数据结构》 期末试卷(b) 2

《下12软件工程《数据结构》 期末试卷(b) 2》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、班级姓名学号考试时间考场（教室）装订线巢湖学院2012—2013学年度第二学期计算机与信息工程学院12级软件工程专业《数据结构》期末考试试卷(B)命题人武彬统分人复核人题号一二三四五总分得分得分评卷人一、判断题：（正确者在括号内打“√”，错误者打“×”。每小题1分，共10分）1．链表的每个结点中都恰好包含一个指针。（）2．栈和队列的存储方式既可是顺序方式，也可是链接方式。（）3．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（）4．线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。（）5．算法

2、的时间复杂度取决于问题的规模和待处理数据的初态。（）6．具有20个记录的序列，采用冒泡排序至少的比较次数是20。（）7．用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。（）8．邻接多重表是无向图和有向图的链式存储结构。（）9．不同的求最小生成树的方法最后得到的生成树是相同的。（）10．在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。（）得分评卷人二、选择题：（将每小题正确答案的选项填写在题后的横线上，每小题2分，共20分）1．算法必须具备输入、输

3、出和___________。A）计算方法　　　　　　　　　B）排序方法C）解决问题的有限运算步骤　　D）程序设计方法2．下面关于串的的叙述中，哪一个是不正确的？___________。A）串是字符的有限序列B）空串是由空格构成的串C）模式匹配是串的一种重要运算D）串既可以采用顺序存储，也可以采用链式存储3．最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是___________。A）(rear+1)MODn=frontB）rear=frontC）rear+1=frontD）(rear-l)M

4、ODn=front4．具有50个记录的序列，采用冒泡排序至少的比较次数是___________。A）1B）49C）50D）5295设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是？___________。A）6B）4C）3D）26.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为___________。A）q=p->next；p->data=q->d

5、ata；p->next=q->next；free(q)；B）q=p->next；q->data=p->data；p->next=q->next；free(q)；C）q=p->next；p->next=q->next；free(q)；D）q=p->next；p->data=q->data；free(q)；7.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为___________。A）(n-1)/2B）n/2C）(n+1)/2D）n8．若有18个元素的有序表存放

6、在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为___________。A）1，2，3B）9，5，2，3C）9，5，3D）9，4，2，39．设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为___________。A）40，50，20，95B）15，40，60，20C）15，20，40，45D）45，40，15，2010．排序趟数与序列的原始状态有关的排序方法是___________排序

7、法。A）插入排序B）选择排序C）冒泡排序D）堆积排序第5页、共6页第6页、共6页班级姓名学号考试时间考场（教室）装订线得分评卷人三、填空题：（每小题2分,共20分）1．数据的逻辑结构分为两大类，它们是线性结构和。2．数据结构在物理上可以分为存储结构和链式存储结构。3．对于n个记录的集合进行冒泡排序，其最坏情况下所需的时间复杂度是。4．按排序过程中依据的不同原则对内部排序方法进行分类，主要有：___________、交换排序、选择排序、归并排序等四类。5．链接存储的特点是利用___________来表示数据元素之间的逻

8、辑关系。6．中序遍历二叉排序树所得到的序列是___________序列（填有序或无序）。。7．INDEX（‘DATASTRUCTURE’，‘STR’）=。8．设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是。