资源描述：
《数据结构44月份历真题附答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、全国2014年4月高等教育自学考试数据结构试卷课程代码：02331本试卷满分100分，考试时间150分钟.考生答题注意事项：1.本卷所有试卷必须在答题卡上作答。答在试卷上无效。试卷空白处和背面均可作草稿纸。2.第一部分为选择题。必须对应试卷上的题号使用28铅笔将“答题卡”的相应代码涂黑。3.第二部分为非选择题。必须注明大、小题号，使用0．5毫M黑色字迹签字笔作答。4.合理安排答题空间。超出答题区域无效。第一部分选择题一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相
2、应代码涂黑。错涂、多涂或未涂均无分。1.与数据存储结构无关的概念是A.栈B.链表C.顺序表D.二叉链表2.顺序表中有10个数据元素，若第一个元素的存储地址是1000，则最后一个元素地址是1036，第5个元素的地址是A．1010B.1016C.1018D.10193.设栈的初始状态为空，元素1、2、3、4、5、6依次入栈，得到的出栈序列是（2,4,3,6,5,1）,则栈的容量至少是A.2B.3C.4D..64.下列关于队列的叙述中,错误的是A.队列是一种先进先出的线性表B.队列是一种后进后出的线性表C.循环队列中进行出队操作时要判断队列是否为空D.在链
3、队列中进行入队操作时要判断队列是否为满5.对稀疏矩阵进行压缩存储的目的是A.便于运算B.节省存储空间C.便于输入输出D.降低时间复杂度6.一棵二叉树的第7层上最多含有的结点数为A.14B.64C.127D.1287.下列选项为完全二叉树的是9/98.用邻接表表示n个顶点e条边的无向图,其边表结点的总数是A.n×eB.eC.2eD.n+e9.无向图中所有顶点的度数之和与所有边数之比是A.1/2B.1C.2D.410.采用邻接矩阵存储图时,广度优先搜索遍历算法的时间复杂度为A.O（n）B.O（n+e）C.O（n2）D.O（n3）11.对序列（15,9,7
4、,8,20,-1,4）进行排序,若一趟排序后的结果为（-1,15,9,7,8,20,4）,则采用的排序方法是A.归并排序B.快速排序C.直接选择排序D.冒泡排序12.比较次数与待排序列初始状态无关的排序方法是A.快速排序B.冒泡排序C.直接插入排序D.直接选择排序13.查找较快,且插入和删除操作也比较方便的查找方法是A.分块查找B.二分查找C.顺序查找D.折半查找14.下列关于m阶B树的叙述中,错误的是A.根结点至多有m棵子树B.所有叶子都在同一层次上C.每个非根内部结点至少有棵子树D.结点内部的关键字可以是无序的15.在散列查找中处理冲突时,可以采
5、用开放定址法。下列不是开放定址法的是A.线性探查法B.二次探查法C.双重散列法D.拉链法非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上,不能答在试卷卷上。9/9二、填空题（本大题共10小题,每小题2分,共20分）16.数据结构研究的内容包括数据的逻辑结构、________和数据的运算。17.头指针为L的带头结点的双循环链表,结点的前趋指针域为prior,后继指针域为next,判断该链表为空的条件是________。18.普里姆（Prim）算法完成的功能是求图的________。19.若三维数组a［4］［5］［6］的基地址是100,每
6、个元素占用2个存储单元,则数组a中最后一个元素的存储地址是________。20.二叉树的线索链表利用________存放遍历时得到的前趋或后继结点的指针。21.采用邻接矩阵存储n个顶点e条边的无向图,其邻接矩阵的大小为________。22.若无向图中任意两个不同的顶点间都有路径,则称该图为________。23.在直接插入排序、冒泡排序和快速排序中,平均时间性能最佳的是________。24.假设m个关键字互为同义词,若用线性探查法把这m个关键字存入散列表中,至少要进行的探查次数是________。25.顺序查找算法的平均时间复杂度为______
7、__。三、解答题（本大题共4小题,每小题5分,共20分）26.用X代表进栈操作,S代表出栈操作。给出利用栈将字符串"a*b-c"改变为"ab*c-"的操作步骤。例如：将"ABC"改变为"BCA",则其操作步骤为XXSXSS。27.假定电文字符集为{A,B,C,D,E,F,G,H},它们在电文中出现的次数分别为{19,6,12,5,38,3,13,4）,为这8个字符设计哈夫曼编码。画出哈夫曼树并给出编码。要求在构造哈夫曼树的过程中,权值较小结点放在左侧,编码时左分支生成代码0,右分支生成代码1。28.设图以邻接表存储,如题28图所示。（1）写出从顶点v
8、1出发图的深度优先搜索遍历序列。（2）写出从顶点v1出发图的广度优先搜索遍历序列。29.（1）一个排序方法稳
