全国2009年1月自考数据结构导论考试试题,答案,笔记

1、全国2009年1月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.数据的不可分割的最小标识单位是（ A ）A.数据项 B.数据记录C.数据元素(数据和运算基本单位)D.数据变量2. for（i=0；im；i+）for（j=0；jt；j+）cij=0；for（i=0；im；i+）for（j=0；jt；j+）for（k=0；knext=pnextnext（下一个，下一个原则）B.p=pnextC.p=pnextnextD.pnex

2、t=pHsSHs5.向一个栈顶指针为hs的链栈中插入一个*s结点时，应执行的操作为（ B ）A.hsnext=s；B.snext=hs；hs=s；（下一个，赋值原则）C.snext=hsnext；hsnext=s；D.snext=hs；hs=hsnext；6.设循环队列的元素存放在一维数组Q030中，队列非空时，front指示队头元素的前一个位置，rear指示队尾元素。如果队列中元素的个数为11，front的值为25，则rear应指向的元素是（ A ）A.Q4B.Q5C.Q14D.Q15 30-25-1=47.定义二维数组A18，010，起始地址为LOC，每个元素占2L个存储单元，在以行序为主

3、序的存储方式下，某数据元素的地址为LOC+50L，则在以列序为主序的存储方式下，该元素的存储地址为（ D ）具有n个结点的二叉树1. 有n-1个孩子2. 有n+1空指域NULL3. 有2n个指针域A.LOC+28LB.LOC+36LC.LOC+50LD.LOC+52L8.具有n个结点的二叉树，拥有指向孩子结点的分支数目是（ A ）A.n-1B.nC.n+1（指针域为NULL）D.2n（指针域）9.对一棵有100个结点的完全二叉树按层序编号，则编号为49的结点，它的左孩子的编号为（ B ）1. 若，m*2n,则无左孩子2. 若，m*2+1n,则无右孩子。若有n个结点的完全二叉树；1. 已知编号m

4、2. 其左孩子为m*23. 其右孩子为m*2+1A.99B.98（49*2）C.97D.5010.有m个叶子结点的哈夫曼树，其结点总数是（ A ）A.2m-1B.2mC.2m+1D.2（m+1）11.有n个结点的无向图的边数最多为（ B ）A.n+1B.C.n（n+1）D.2n（n+1） 注：有向图为：n*（n1）0 1 2 1 0 32 3 012.设图的邻接矩阵为，则该图为（ A ）A.有向图（杂乱矩阵）B.无向图（为对称矩阵）如：C.强连通图D.完全图13.二分查找算法的时间复杂度是（ D ）A.O（n2）（冒泡排序（平均复杂时间程度） B.O（nlog2n） （快速排序）C.O（n）（

5、冒泡排序（最好情况下时间复杂程度）D.O（log2n）14.已知8个元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（ B ）A.4B.5 注：1.二次排序树的规则：C.6D.7 左小又大，连续一致原则 规律：1. 左面的总小于右面的2. 差值最小原则 1 2 3 4 515.采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是（ C ）A.插入和快速B.冒泡和快速C.选择和插入D.选择和冒泡二、填空题（本大题共13小题，每小题2分，共26分）请在每小题的空格中填上正确答案。错填、不填均无分。16.在数据结构中，数

6、据的存储结构有顺序存储方式、链式存储方式、_索引存储方式 _和散列存储方式等四种。17. 作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为 _算法输入的规模或问题的规模_。18.在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向 _直接前趋_和 _直接后继_。19.在有n个元素的链队列中，入队和出队操作的时间复杂度分别为_O（1）_和_O（n）_。20.在栈结构中，允许插入的一端称为 _栈顶_；在队列结构中，允许插入的一端称为 _队尾_。21.在循环队列中，存储空间为0n-1。设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那

7、么其队空标志为rear=front，队满标志为 _（rear+1）%maxsize=front_。22.深度为k的二叉树至多有 _2k -1 _个结点，最少有 _2k-1_个结点。23.设有一稠密图G，则G采用 _邻接矩阵_存储结构较省空间。设有一稀疏图G，则G采用 _邻接表_存储结构较省空间。24.在一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较_（n+1）/2_个元素结点。25.假定对线性表R059进行分块检索，共分为10块，每块长度等于6。若检索索引表和块均用顺序检索的方法，则检索每一个元素的平均检索长 度为_9_。分块查找的平均查找长度为：ASLbs=

8、1/2*(s/n+s)+1 ,其中，S表示为元素个总数。n，表示为每个块中的元素。 1/2(60/6+6)+1=926.文件在外存储器上的组织结构主要有三种：顺序文件、散列文件和索引文件，其中 _顺序_特别适应磁带存储器，也适应磁盘存储器。27.在插入排序、冒泡排序、快速排序、归并排序等排序算法中，占用辅助空间最多的是 _归并排序_。28.冒泡排序最好的时间复杂度为 _O（n）_，平均时间复杂度为 _O（n2）_，是一种稳定的排序算法。注：1.快速排序是不稳定的，时间复杂度为：O（nlog2n）但在最坏情况下，近似于O（n2） 2.二分法的时间复杂程度为：O（log2n）三、应用题（本大题共5

9、小题，每小题6分，共30分）1. 解题过程：前：A B C D E F G 中：C B D A E G F 前：B C D 前：E F G 中：C B D 中：E G FC D 前：F G 中：G F29.已知一棵二叉树的前序序列是ABCDEFG，中序序列是CBDAEGF。请构造出该二叉树，并给出该二叉树的后序序列。答： 后序遍历为：C D B G F E A解题说明：1. 前序遍历的第一个为“root”2. 后续遍历的最后一个为“root”3. 中序遍历为控制左右孩子的分界点。4. 总体思路：先找root，然后到对应的中续遍历或后续遍历中找到该元素，对应着该元素的左边的所有元素到前序或者后续

10、里找到对应元素，再确定root，依次类推即可。5. 前序：中左右 中续：左中右 后续 ：左右中30.将题30图所示的由三棵树组成的森林转化为一棵二叉树。解题思路：1. 除保留第一个兄弟结点外，其它连接父节点的兄弟结点全部断开，变为其兄弟结点的右孩子。（如红箭头所示）2. 为垂直线的顺时针旋转45度（不旋转就挤到一起啦。）（如黄箭头所示）3. 割裂后的结点，左孩子是谁的，还是谁的，不改变。（如绿箭头）题30图解： “”代表结束符号31.已知某图的邻接表存储结构如题31图所示：注：解题思路：1.深度优先搜索法是按照每一选定的顶点出发，走“一路到底原则”（但不能走相同路径），但走完后包括所有节点。（

11、选择路径不同，其最后结果不一样，答案不唯一。）2.广度优先搜索法是指的从某点出发能够辐射到的最大范围选的点。题31图（1） 画出该图。 （2）根据该邻接表从顶点A出发，分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。答：根据该邻接表从顶点出发1.深度优先搜索法为：A-B-C-F-G-H-E-D 2.广度优先搜索法为: A-B-D-C-E-F-H-G32.假定采用H（k）=k mod 7计算散列地址，引用线性探测的开放定址法解决冲突，试在06的散列地址空间中，对关键字序列（38，25，74，63，52，48）构造散列表，并求出等概率情况下查找成功的平均查找长度。答：由题意可知关键字构

12、成的散列表如下图。 下标 0 1 2 3 4 5 6634838257452 探查次数 1 3 1 1 2 4等概况下的查找成功的平均查找长度为：（1+3+1+1+2+4）/7=1.711. 题中给出多少长度范围，就有多少个空间。（注意，一般是从0开始，所以有N+1个空格）2. 按照关键字顺序依次进行余数运算。（题目已给出公式），按照余数放在对应下表内，若冲突，往后放。3. 注意，最后的次数算的是每一个格都要计算到的。33.用快速排序法对数据序列（49，38，65，97，16，53，134，27，39）进行排序，写出其第一趟排序的全过程。答：初始关键字49 38 65 97 16 53 134

13、 27 39 第1趟排序后3938271649 53 134 97 65 第2趟排序后16 38 27 3949 53 134 97 65第3趟排序后16 3827 3949 53 134 97 65第4趟排序后16 27 38 3949 53 134 97 65第5趟排序后16 27 38 39 49 53 134 97 65第6趟排序后16 27 38 39 49 53 65 97 134 第7趟排序后 16 27 38 39 49 53 65 97 134解题经验：1. 对第一个数字初始2. 然后将这个数字与中间的数字进行比较，若大于这个数字，那么这个数字往前推一个，若小于这个数字，那么

14、这个数字往后退一个。3. 然后以关键字为分界点，1.若分界点左的数小于分界点，分界点右的数大于分界点，那么这个数字不动。2.第三找出分界点左面大于分界点的数，按照从后往前的顺序写。再找出分界点右面的大于分界点的数，也是倒着写。4. 最后，分别对分好的块前后比较，前大于后，调换，小于不动，依次类推。先左后右原则。四、算法设计题（本大题共2小题，每小题7分，共14分）34.完善下列折半插入排序算法。Void binasort（struct node rMAXSIZE，int n）for（i=2；i=n；i+）r0=ri；low=1；high=i-1；while（low=high）mid=（1）_(low+high)/2_；if（r0.key=low；j- -）（4）rhigh=_Aj+1=Aj_；rlow=r0 ；35.下列算法的功能是求出指定结点在给定的二叉排序树中所在的层次。请完善该算法。Void