2014年4月自考数据结构导论试题及答案….doc

全国2014年4月高等教育自学考试 数据结构导论试题 课程代码：02142 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1.答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2.每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1.下列几种算法时间复杂度中，最小的是 A.O(log2n) B.O(n) C.O(n2) D.O(1) 2.数据的存储方式中除了顺序存储方式和链式存储方式之外，还有 A.索引存储方式和树形存储方式 B.线性存储方式和散列存储方式 C.线性存储方式和索引存储方式 D.索引存储方式和散列存储方式 3.表长为n的顺序表中做删除运算的平均时间复杂度为 ( C ) A. B.O(log2n) C.O(n) D.O(n2) 4.顺序表中定位算法(查找值为x的结点序号最小值)的平均时间复杂度为 A.O(1) B.O(log2n) C.O(n) D.O(n2) 5.元素的进栈次序为A，B，C，D，E，出栈的第一个元素为E，则第四个出栈的元素为 A.D B.C C.B D.A 6.带头结点的链队列中，队列头和队列尾指针分别为front和rear，则判断队列空的条件为 A.front==rear B.front!=NULL C.rear!==NULL D.front==NULL 7.深度为5的二叉树，结点个数最多为 A.31个 B.32个 C.63个 D.64个 8.如果结点A有2个兄弟结点，结点B为A的双亲，则B的度为 A.1 B.3 C.4 D.5 9.将题9图所示的一棵树转换为二叉树，结点C是 A.A的左孩子 B.A的右孩子 C.B的右孩子 D.E的右孩子 10.n为图的顶点个数，e为图中弧的数目，则图的拓扑排序算法的时间复杂度为 A.O(n) B.O(e) C.O(n-e) D.O(n+e) 11.无向图的邻接矩阵是 A.对角矩阵 B.稀疏矩阵 C.上三角矩阵 D.对称矩阵 12.在具有101个元素的顺序表中查找值为的元素结点时，平均比较元素的次数为 A.50 B.51 C.100 D.101 13.构造散列函数的方法很多，常用的构造方法有 A.数字分析法、除留余数法、平方取中法 B.线性探测法、二次探测法、除留余数法 C.线性探测法、除留余数法、链地址法 D.线性探测法、二次探测法、链地址法 14.就平均时间性能而言，快速排序方法最佳，其时间复杂度为 A.O(n) B.O(nlog2n) C.O(n2) D.O(1og2n) 15.下述算法中，不稳定的排序算法是 A.直接插入排序 B.冒泡排序 C.堆排序 D.归并排序 非选择题部分 注意事项： 用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。 二、填空题(本大题共13小题，每小题2分，共26分) 16.数据的基本单位是。 17.双向循环链表中，在所指结点的后面插一个新结点*t，需要修改四个指针，分别为 tprior=P；tnext=p-next；；pnext=t；。 18.在带有头结点的循环链表中，尾指针为rear，判断指针P所指结点为首结点的条件是 19.若线性表中最常用的操作是求表长和读表元素，则顺序表和链表这两种存储方式中，较节省时间的是。 20.不含任何数据元素的栈称为。 21.稀疏矩阵一般采用的压缩存储方法是。 22.100个结点的二叉树采用二叉链表存储时，用来指向左、右孩子结点的指针域有个。 23.已知完全二叉树的第5层有5个结点，则整个完全二叉树有个结点。 24.n个顶点的有向图G用邻接矩阵A1..n，1..n]存储，其第i列的所有元素之和等于顶点 Vi的 25.具有1个顶点的有向完全图的弧数为。 26.要完全避免散列所产生的“堆积’’现象，通常采用解决冲突。 27.在长度为n的带有岗哨的顺序表中进行顺序查找，查找不成功时，与关键字的比较次数为28.归并排序算法的时间复杂度是 三、应用题(本大题共5小题，每小题6分，共30分) 29.稀疏矩阵A如题29图所示，写出该稀疏矩阵A的三元组表示法。30.设二叉树的中序遍历序列为BDCEAFHG，后序遍历序列为DECBHGFA，试画出该二叉树。 31.写出题31图所示无向图的邻接矩阵，并写出每个顶点的度。 题31图 32.已知散列表的地址空间为0至13，散列函数H(k)kmod11，(mod为求余运算)，待散列序列为(26，61，38，84，49)，用二次