02142数据结构导论201301试题及答案.doc
2013年1月高等教育自学考试全国统一命题考试数据结构导论试题课程代码：02142考生答题注意事项：1. 本卷所有试卷必须在答题卡上作答。答在试卷和草稿纸上的无效。2. 第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。3. 第二部分为非选择题。必须注明大、小题号，使用0.5毫米黑色字迹笔作答。4. 合理安排答题空间，超出答题区域无效。选择题部分一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。1.数据的基本单位是A.数据元素B.数据项C.字段D.域2.算法的空间复杂度是指A.算法中输入数据所占用的存储空间的大小B.算法本身所占用的存储空间的大小C.算法中所占用的所有存储空间的大小D.算法中需要的辅助变量所占用存储空间的大小3.从一个长度为100的顺序表中删除第30个元素,需向前移动的元素个数为A.29B.30C.70D.714.若线性表最常用的操作是存取第i个元素及其后继的值,则最节省操作时间的存储结构是A.单链表B.双链表C.单循环链表D.顺序表5.判断链栈LS是否为空的条件是A.LS->next= =LSB.LS->next= =NULLC.LS! =NULLD.LS= =NULL6.关于链队列的运算说法正确的是A.入队列需要判断队列是否满B.出队列需要判断队列是否空C.入队列需要判断队列是否空D.出队列需要判断队列是否满7.元素的进栈次序为A,B,C,D,E,则出栈中不可能的序列是A.A,B,C,D,EB.B,C,D,E,AC.E,A,B,C,DD.E,D,C,B,A8.具有63个结点的完全二叉树是A.满二叉树B.二叉排序树C.哈夫曼树D.空树9.将含有80个结点的完全二叉树从根这一层开始,每层从左到右依次对结点编号,根结点的编号为1。则关于编号40的结点的左右孩子的说法正确的是A.左孩子编号为79，右孩子编号为80B.左孩子不存在，右孩子编号为80C.左孩子编号为80，右孩子不存在D.左孩子不存在，右孩子不存在10.将题10图所示的一棵树转换为二叉树，结点D是A.A的右孩子B.B的右孩子C.C的右孩子D.E的右孩子11.无向图的邻接矩阵是 题10图A.对称矩阵B.稀疏矩阵C.对角矩阵D.上三角矩阵12.图的广度优先搜索遍历的过程类似于树的A.前序遍历B.中序遍历C.后序遍历D.按层次遍历13.要解决散列引起的冲突问题，最常用的方法是A.数字分析法、除留余数法、平方取中法B.除留余数法、线性探测法、平方取中法C.线性探测法、二次探测法、链地址法D.除留余数法、线性探测法、二次探测法14.下列表述中，正确的是A.序列（102，81，55，62，50，40，58，35，20）是堆B.序列（102，81，55，62，50，40，35，58，20）是堆C.序列（102，81，55，58，50，40，35，62，20）是堆D.序列（102，71，55，40，50，62，35，58，20）是堆15.下列算法中，不稳定的排序算法是A.冒泡排序B.快速排序C.直接插入排序D.二路归并排序非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。二、填空题(本大题共13小题，每小题2分，共26分)16.下面算法程序段的时间复杂度为_O(n2)_。for(i=1;i<=n;i+)for(j=1;j<=i;j+)x=aij;aij=aji;aji=x;17.设p指向单链表的最后一个结点，要在最后一个结点之后插入q所指的结点，需执行的语句序列是p->next=q;_p=q_;p->next=NULL。18.向一个长度为100的顺序表中第50个元素之前插入一个元素时，需向后移动的元素个数为_51_。19.一个带头结点的链栈LS，现将一个新结点入栈，指向该结点的指针为p，入栈操作为p->next=LS->next和_LS->next=p_。20.队列操作的原则是_先进先出_。21.含有n个顶点的连通图中的任意一条简单路径，其最大长度为_n-1_。22.在一棵度为3的树中，度为3的结点数为1个，度为2的结点数为2个，度为1的结点数为3个，则度为0的结点数为_5_个。23.某二叉树的中序遍历序列为BACDEFGH，后序遍历序列为BCAEDGHF，则根结点F的左子树上共有_5_个结点。24.设有向图G的邻接矩阵为A,如果<Vi,Vj>是图中的一条弧,则Aij的值为_1_。25.一个有序表A含有15个数据元素，且第一个元素的下标为1，按二分查找算法查找元素A14，所比较的元素下标依次是_8，12，14_。26.用n个值构造一棵二叉排序树，它的最大深度为_n_。27.设记录数为n，则冒泡排序算法在最好情况下所作的比较次数为_n-1_。28.二路归并排序算法的时间复杂度为_O(nlog2n)_。三、应用题(本大题共5小题，每小题6分，共30分)29.设有编号为A，B，C，D的四辆列车，顺序进入一个栈式结构的站台，试写出这四辆列车开出站台的所有可能的顺序。答：若列车A最先开出站台，则列车可能的出站顺序有：ABCD、ABDC、ACBD、ACDB、ADCB若列车B最先开出站台，则列车可能的出站顺序有：BACD、BADC、BCAD、BCDA、BDCA若列车C最先开出站台，则列车可能的出站顺序有：CBAD、CBDA、CDBA若列车D最先开出站台，则列车可能的出站顺序有：DCBA综上所述，这四辆列车开出站台的所有可能的顺序共有14种。30.已知一棵二叉树的先序遍历序列为ABCDEFGHK，中序遍历序列为CBEDFAGKH，试建立该二叉树并写出它的后序遍历序列。答：后序遍历序列为：CEFDBKHGA31.利用克鲁斯卡尔（Kruskal）算法构造题31图的最小生成树，画出它的构造过程。题31图答：32.给定表（27，19，50，1，75，12，40，90，66，32，22），试按元素在表中的次序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。答：33.对初始关键字序列48，39，68，95，88，12，27，48的记录进行冒泡排序（升序），给出排序过程。答：初始关键字序列：48，39，68，95，88，12，27，48第一趟排序后：39，48，68，88，12，27，48，95第二趟排序后：39，48，68，12，27，48，88，95第三趟排序后：39，48，12，27，48，68，88，95第四趟排序后：39，12，27，48，48，68，88，95第五趟排序后：12，27，39，48，48，68，88，95第六趟排序后：12，27，39，48，48，68，88，95四、算法设计题(本大题共2小题，每小题7分，共14分)34.试写出判断带头结点的单链表head中的元素值是否是递减的算法。答：35.试写出在有序表T中用二分查找法查找键值为key的元素的算法。答：
