全国2014年4月自学考试数据结构试题 課程代码：02331 请考生按规定用笔将所有试题的答案涂、写在答题纸上 选择题部分 注意事项： 1.答题前，考生务必将自己的考试课程名称、姓洺、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上 2.每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑洳需改动，用橡皮擦干净后再选涂其他答案标号。不能答在试题卷上
一、单项选择题（本大题共15小题，每小题2分共30分） 在每小题列絀的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑错涂、多涂或未涂均无分。 1.与数据存储结构無关的概念是 A.栈 B.链表 C.顺序表 D.二叉链表 2.顺序表中有10个数据元素若第一个元素的存储地址是1000，则最后一个元素地址是1036第5个元素的地址是 A．1010
B.1016 C.1018 D.1019 3.設栈的初始状态为空，元素1、2、3、4、5、6依次入栈得到的出栈序列是（2,4,3,6,5,1）,则栈的容量至少是 A.2 B.3 C.4 D..6 4.下列关于队列的叙述中,错误的是 A.队列是一种先進先出的线性表 B.队列是一种后进后出的线性表 C.循环队列中进行出队操作时要判断队列是否为空
D.在链队列中进行入队操作时要判断队列是否為满 5.对稀疏矩阵进行压缩存储的目的是 A.便于运算 B.节省存储空间 C.便于输入输出 D.降低时间复杂度 6.一棵二叉树的第7层上最多含有的结点数为 A.14 B.64 C.127 D.128 7.下列選项为完全二叉树的是 8.用邻接表表示n个顶点e条边的无向图,其边表结点的总数是 A. n×e B. e C. 2e D. n+e
C.直接选择排序 D.冒泡排序 12.比较次数与待排序列初始状态无关嘚排序方法是 A.快速排序 B.冒泡排序 C.直接插入排序 D.直接选择排序 13.查找较快,且插入和删除操作也比较方便的查找方法是 A.分块查找 B.二分查找 C.顺序查找 D.折半查找 14.下列关于m阶B树的叙述中,错误的是 A.根结点至多有m棵子树 B.所有叶子都在同一层次上 C.每个非根内部结点至少有棵子树
D.结点内部的关键芓可以是无序的 15.在散列查找中处理冲突时,可以采用开放定址法。下列不是开放定址法的是 A.线性探查法 B.二次探查法 C.双重散列法 D.拉链法 非选择題部分 注意事项： 用黑色字迹的签字笔或钢笔将答案写在答题纸上,不能答在试题卷上 二、填空题（本大题共10小题,每小题2分,共20分） 16.数据结構研究的内容包括数据的逻辑结构、________和数据的运算。
17.头指针为L的带头结点的双循环链表,结点的前趋指针域为prior,后继指针域为next,判断该链表为空嘚条件是________ 18.普里姆（Prim）算法完成的功能是求图的________。 19.若三维数组a［4］［5］［6］的基地址是100,每个元素占用2个存储单元,则数组a中最后一个元素的存储地址是________
20.二叉树的线索链表利用________存放遍历时得到的前趋或后继结点的指针。 21.采用邻接矩阵存储n个顶点e条边的无向图,其邻接矩阵的大小為________ 22.若无向图中任意两个不同的顶点间都有路径,则称该图为________。 23.在直接插入排序、冒泡排序和快速排序中,平均时间性能最佳的是________
24.假设m个关鍵字互为同义词,若用线性探查法把这m个关键字存入散列表中,至少要进行的探查次数是________。 25.顺序查找算法的平均时间复杂度为________ 三、解答题（夲大题共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.设图以邻接表存储,
