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

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

2、； k<n ； k+ ）c i j =c i j +a i k *b k j ；上列程序的时间复杂度为（C）A.O （ m+n× t）C.O（ m× n× t）B.O （ m+n+t ）D.O （ m× t+n ）3.若线性表最常用的操作是存取第i 个元素及其前趋的值，那么最节省操作时间的存储方式是（B）A. 单链表B. 双链表C.单循环链表D. 顺序表4.设单链表中指针 p 指向结点 A，要删除 A 之后的结点（若存在） ，则修改指针的操作为（A）A.p >next=p >next >next（下一个，下一个原则 ） B.p=p

3、 >nextC.p=p >next >nextD.p >next=p5.向一个 栈顶指针 为 hs 的链栈中 插入一个 *s 结点时，应执行的操作为（B ）HsSHsA.hs >next=s ；B.s >next=hs； hs=s；（下一个，赋值原则）C.s >next=hs >next ；hs >next=s ；D.s >next=hs；hs=hs >next ；6.设循环队列的元素存放在一维数组Q 0 30中，队列非空时， front指示队头元素的前一个位置，rear 指示队尾元素。如果队列中元素的个数为11， front

4、的值为 25，则 rear 应指向的元素是（A）A.Q 4B.Q 5C.Q 14D.Q 1530-25-1=47.定义二维数组A 1 8， 0 10，起始地址为LOC ，每个元素占2L 个存储单元，在以行序为主序的存储方式下，某数据元素的地址为LOC+50L ，则在以列序为主序的存储方式下，该元素的存储地址为（D）A.LOC+28LB.LOC+36L具有 n 个结点的二叉树C.LOC+50LD.LOC+52L1.有 n-1 个孩子8.具有 n 个结点 的二叉树，拥有指向孩子结点的分支数目是（A）有 n+1 空指域 NULLA.n-1B.n2.3.有 2n 个指针域C.n+1 （指针域为 NUL

5、L ）D.2n （指针域）9.对一棵有 100 个结点的 完全二叉树 按层序编号，则编号为49 的结点，它的左孩子的编号为（B）A.99B.98 （ 49*2 ）若有 n 个结点的完全二叉树；C.97D.501.若， m*2>n, 则1.已知编号 m无左孩子10.有 m 个叶子结点的 哈夫曼树 ，其结点总数是（A）2.其左孩子为 m*22.若，m*2+1>n,A.2m-1B.2m3.其右孩子为 m*2+1则无右孩子。C.2m+1D.2 （m+1）11.有 n 个结点的 无向图 的边数最多为（B）A.n+1B.n(n - 1)2C.n （ n+1）D.2n （n+1 ） 注：有向图为

6、： n* （n 1）01112.设图的邻接矩阵为001 ，则该图为（A）0 1 2010A. 有向图 （杂乱矩阵）B. 无向图 （为对称矩阵）如：1 0 3C.强连通图D. 完全图2 3 013.二分查找算法的 时间复杂度 是（D）A.O （ n2）（冒泡排序（平均复杂时间程度）B.O（ nlog 2n） （快速排序）C.O（ n）（冒泡排序（最好情况下时间复杂程度）D.O（ log2 n）14.已知 8 个元素（ 34， 76， 45， 18， 26， 54， 92， 65），按照依次插入结点的方法生成一棵二叉排序树 ，则该树的深度为（B ）A.4B.5注： 1.二次排序树的规则：C.6D.

7、7左小又大，连续一致原则341规律：187621.左面的总小于右面的26459232.差值最小原则54465515.采用排序算法对 n 个元素进行排序，其排序趟数肯定为 n-1 趟的排序方法是（C）A. 插入和快速B.冒泡和快速C. 选择和插入D. 选择和冒泡二、填空题（本大题共13 小题，每小题 2 分，共26 分）请在每小题的空格中填上正确答案。错填、不填均无分。16.在数据结构中，数据的存储结构有顺序存储 方式、 链式存储 方式 、_索引 存储 方式 _和散列存储 方式等四种。17.作为一个 算法输入的数据 所含数据元素的数目，或与此数目有关的其他参数，称为_算法输入 的规模或 问题 的

8、规模 _。18.在双链表中， 存储一个结点有三个域， 一个是 数据域 ，另两个是 指针域 ，分别指向_直接前趋 _和 _直接后继 _。19.在有 n 个元素的 链队列 中， 入队 和出队 操作的时间复杂度分别为 _O（ 1）_和_O（ n） _。20.在栈结构中，允许插入的一端称为_栈顶 _；在队列结构中，允许插入的一端称为_队尾 _。21.在循环队列中，存储空间为0n-1。设队头指针front 指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front ，队满标志为 _（ rear+1） %maxsize=front_ 。22.深度为 k 的二叉树至多有_2k -

9、1 _个结点 ，最少有_2k-1 _个结点 。23.设有一 稠密图 G，则 G 采用_邻接矩阵 _存储结构较省空间。设有一稀疏图 G，则 G 采用_邻接表 _存储结构较省空间。24.在一个具有n 个结点 的单链表中查找其值等于x 的结点时，在查找成功的情况下，需平均比较_（ n+1）/2_个元素结点。25.假定对线性表R 0,59进行分块检索，共分为10 块，每块长度等于法，则检索每一个元素的平均检索长度为 _9_。6。若检索索引表和块均用顺序检索的方分块查找的平均查找长度为：ASL bs=1/2*(s/n+s)+1,其中，S 表示为元素个总数。n，表示为每个块中的元素。1/2(60/6+6)

10、+1=926.文件在 外存储器上 的组织结构 主要有三种：顺序文件、 散列 文件和 索引 文件，其中_顺序 _特别适应磁带存储器，也适应磁盘存储器。27.在插入 排序、 冒泡 排序、 快速 排序、 归并 排序等排序算法中，占用辅助空间最多的是_归并排序_。28.冒泡排序最好的时间复杂度为_O（ n）_，平均时间复杂度为_O（ n2） _，是一种稳定的排序算法。注： 1.快速排序是不稳定的，时间复杂度为：2.二分法的时间复杂程度为：O（ log 2n）O（ nlog 2n）但在最坏情况下，近似于O（ n2）三、应用题（本大题共5 小题，每小题6 分，共 30 分）29.已知一棵二叉树的前序序列

11、是 ABCDEFG ，中序序列 是 CBDAEGF 。请构造出该二叉树，并给出该二叉树的后序序列。答：1. 解题过程：A前：ABCDEFG中：CBDAEGFBE前：BCD前：EFGCDF中：CBD中：EGFCDG前：FG后序遍历为： CDBGFEA中：GF解题说明：1. 前序遍历的第一个为“ root”2. 后续遍历的最后一个为“ root”3. 中序遍历为控制左右孩子的分界点。4. 总体思路：先找 root，然后到对应的中续遍历或后续遍历中找到该元素，对应着该元素的左边的所有元素到前序或者后续里找到对应元素，再确定root，依次类推即可。5.前序：中左右中续：左中右后续：左右中30.将题 3

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

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

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

15、后 3938271649531349765第 2 趟排序后 163827 3949531349765第 3 趟排序后 16 38273949531349765第 4趟排序后 1627383949531349765第 5趟排序后 162738394953 1349765第 6趟排序后 16273839495365 97134第 7趟排序后 1627383949536597134解题经验：1. 对第一个数字初始2. 然后将这个数字与中间的数字进行比较，若大于这个数字，那么这个数字往前推一个，若小于这个数字，那么这个数字往后退一个。3.然后以关键字为分界点，1.若分界点左的数小于分界点，分界点右的数

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