《全国2010年10月自考数据结构导论考试试题,答案,笔记》由会员分享，可在线阅读，更多相关《全国2010年10月自考数据结构导论考试试题,答案,笔记（6页珍藏版）》请在金锄头文库上搜索。
1、全国2010年10月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1下列描述中正确的是( C )A.数据元素是数据的最小单位-数据项是数据的最小单位B.数据结构是具有结构的数据对象C.数据结构是指相互之间存在一种或多种特定关系的数据元素的集合D.算法和程序原则上没有区别，在讨论数据结构时两者是通用的1. 冒泡，选择，直接插入-O(n2)2. 希尔，归并，快速,堆-O(nlog2n)3. 二分法- O（log2n）2归并排序的时间
2、复杂度是( B )AO（n2）B.O（nlog2n）C.O（n）D.O（log2n）3二分查找的时间复杂度是( D )AO（n2）B.O（nlog2n）C.O（n）D.O（log2n）4顺序存储的表中有90000个元素，已按关键字值升序排列，假设对每个元素进行查找的概率相同，且每个元素的关键字值皆不相同，用顺序查找法查找时，需平均比较的次数为( C )A25000B.30000C.45000D.90000 注：为元素的一半5散列文件是一种( D )A顺序文件B.索引文件C.链接文件D.计算寻址文件6两个矩阵A：mn，B：np相乘，其时间复杂度为( B )AO(n)B.O(mnp)C.O(n2)
3、D.O（mp） 注：不同字母的乘积7.常用于函数调用的数据结构是( A )A.栈B.队列 （常用于广度优先搜索）C.链表D.数组8二维数组Anm以列优先顺序存储，数组A中每个元素占用1个字节，A11为首元素，其地址为0，则元素Aij的地址为( B )A.（i-1）m+(j-1)-行B.(j-1)n+(i-1) 注意是以1开头，因此-1. C.(j-1)n+iD.jn+I 行前*后+后 列-后*前+前 9.图的广度优先搜索使用的数据结构是( A )A队列B.树C.栈（常用与函数调用）D.集合10序列（21,19,37,5,2）经冒泡排序法由小到大排序，在第一次执行交换后所得结果为( A )A(1
4、9，21，37，5，2)B.(21，19，5，37，2) C.(21，19，37，2，5)D.(2，21，19，37，5) 注：从前往后交换11数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为( D )A索引存储方法(还需要增加附加索引)B.顺序存储方法(一组连续的存储单元存储线性表)C.链式存储方法(任意的存储单元，可以不连续)D.散列存储方法12在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点的( B )A直接前趋（数据域）B.直接后继C.开始结点D.终端结点13在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的
5、时间复杂度为( C )AO（1） (出队)B.O（log2n）C.O（n）D.O（n2）14在链队列中执行入队操作，( D )A需判别队是否空B.需判别队是否满C.限制在链表头p进行D.限制在链表尾p进行15一整数序列26，59，77，31，51，11，19，42，以二路归并排序从小到大排序，第一阶段的归并结果为( B )A.31，51，11，42，26，77，59，19B.26，59，31，77，11，51，19，42C.11，19，26，31，42，59，51，77D.26，11，19，31，51，59，77，42注：归并过程1: 初始关键字：26 59 77 31 51 11 19 42
6、 2.第一次归并：26 59 31 77 11 51 19 42 3.第二次归并：16 31 59 77 11 19 42 51 3.第三次归并：11 16 19 31 42 51 59 77时间复杂程度小技巧：1. 首先看有几个条件句，若2，时间复杂度为不同字母相乘。2. 若只有一个条件句，那么最后的表达式若为”+”-那么时间复杂度为O(n). 若为”x”-那么时间复杂度为（log2n）.二、填空题(本大题共13小题，每小题2分，共26分)请在每小题的空格中填上正确答案。错填、不填均无分。16下列程序段的时间复杂度为_O(n0.5)_。i=0；s=0；while（snext=top和_top
7、=p _操作。23有m个叶结点的哈夫曼树所具有的结点数为_2m-1_。24在一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右地给所有结点编号。设根结点编号为1。若编号为i的结点有右孩子，那么其右孩子的编号为_2i+1_。 左孩子为2i25在一棵树中，_根_结点没有前驱结点。26一个具有n个顶点的有向完全图的弧数是_n(n-1)_。27n个顶点的无向图G用邻接矩阵Ann存储，其中第i列的所有元素之和等于顶点Vi的_度_。4. 冒泡，选择，直接插入-O(n2)5. 希尔，归并，快速,堆-O(nlog2n)6. 二分法- O（log2n）28选择排序的平均时间复杂度为_O(n2)_。三、
8、应用题(本大题共5小题，每小题6分，共30分)29在栈的输入端元素的输入顺序为1，2，3，4，5，6，进栈过程中可以退栈，则退栈时能否排成序列3，2，5，6，4，1和1，5，4，6，2，3，若能，写出进栈、退栈过程，若不能，简述理由。（用push（x）表示x进栈，pop(x)表示x退栈）解题技巧剖析：1. 根据后进先出原则。3.把原始字符串与要改变次序的字符串写成如下格式。2.写一点，划一点原则。2. 1，2，3，4，5，6 3，2，5，6，4，1 3. 例如：enter- 1,2,3 exit -3,2 此时，剩下 1。 对应着，把里已输入的 1 2 3，删掉。然后把标明已产生排序，然后以此
9、类推。Push(-)push(3)pop(3) 注：退的时候，从后往前划。注：若有两个连续的数连续，那么这个两个数若给出的时候也为挨着，若在末端，那么根据栈的原则，是不行的。30已知一棵二叉树的中根遍历序列为CBEDFAGH，后根遍历序列为CEFDBHGA，画出该二叉树。解题说明：1. 前序遍历的第一个为“root”2. 后续遍历的最后一个为“root”3. 中序遍历为控制左右孩子的分界点。4. 总体思路：先找root，然后到对应的中续遍历或后续遍历中找到该元素，对应着该元素的左边的所有元素到前序或者后续里找到对应元素，再确定root，依次类推即可。5. 前序：中左右 中续：左中右 后续 ：左
10、右中答：31给定表（15，11，8，20，14，13），试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树。画出插入完成后的二叉排序树，并判断该二叉排序树是否为平衡二叉排序树，若为非平衡二叉排序树，将它调整为平衡二叉排序树。二叉树构造法：1. 依次插入二叉排序树，按照左小又大，差值最小原则依次构造即可。2. 从根节点看，总结点总比左面的任何值大，比右面任何值的值小。3. 兄弟节点总比左孩子大比右孩子小。4. 上一个兄弟节点总比下一个子节点任意值大。非平衡二叉树：1. 概念通俗化：就是root两边有高差，发育不全。它的左右子树的高度之差不能超过1（可以为1）例如本题有2个高差，那么就调
11、整2次。2. 如果左面的圈密集，那么从左面开始，若右面的圈密集，从右边开始。3. 不平衡，进行旋转。从最低下开始，若为左圈多，那么从最低开始，把最底部的结点与上部的前接前趋结点互换，由于可知，那么就把左孩子给上一个结点当做又孩子，若有又孩子，那么跟着旋转即可，不给。15答：二叉树排序为：1120148 113 214不平衡，调整后的二叉排序树为： 15111382032如题32图所示无向图，（1）写出其邻接矩阵；（2）写出三种以顶点A为起点的深度优先搜索顶点序列。由题意可得邻接矩阵为： A B C D E F G HA 0 1 1 0 0 0 0 1B 1 0 0 1 1 0 0 0C 1 0 0 0 0 1 0 0D 0 1 0 0 0 0 1 0E 0 1 0 0 0 0 1 0F 0 0 1 0 0 0 0 0G 0 0 0 1 1 0 0 0H 1 0 0 0 0 0 0 0 0H题32图答：AHBDGECF AHBEGDCF ACFBE
