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

全国2009年1月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.数据的不可分割的最小标识单位是（A）A.数据项 B.数据记录 C.数据元素(数据和运算基本单位) 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；k<n；k++）c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；上列程序的时间复杂度为（C）A.O（m+n×t） B.O（m+n+t）C.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—>nextC.p=p—>next—>next D.p—>next=pHsSHs5.向一个栈顶指针为hs的链栈中插入一个*s结点时，应执行的操作为（B）A.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的值为25，则rear应指向的元素是（A）A.Q［4］ B.Q［5］ C.Q［14］ D.Q［15］30-25-1=47.定义二维数组A［1‥8，0‥10］，起始地址为LOC，每个元素占2L个存储单元，在以行序为主序的存储方式下，某数据元素的地址为LOC+50L，则在以列序为主序的存储方式下，该元素的存储地址为（D）具有n个结点的二叉树有n-1个孩子有n+1空指域NULL有2n个指针域A.LOC+28L具有n个结点的二叉树有n-1个孩子有n+1空指域NULL有2n个指针域C.LOC+50L D.LOC+52L

8.具有n个结点的二叉树，拥有指向孩子结点的分支数目是（A）A.n-1 B.n C.n+1（指针域为NULL） D.2n（指针域）9.对一棵有100个结点的完全二叉树按层序编号，则编号为49的结点，它的左孩子的编号为（B）若，m*2>n,则无左孩子若，m*2+1>n,则无右孩子。若有n个结点的完全二叉树；已知编号m若，m*2>n,则无左孩子若，m*2+1>n,则无右孩子。若有n个结点的完全二叉树；已知编号m其左孩子为m*2其右孩子为m*2+1C.97 D.5010.有m个叶子结点的哈夫曼树，其结点总数是（A）A.2m-1 B.2m C.2m+1 D.2（m+1）11.有n个结点的无向图的边数最多为（B）A.n+1 B.C.n（n+1） D.2n（n+1）注：有向图为：n*（n—1）01210323012.设图的邻接矩阵为，则该图为（A）012103230A.有向图（杂乱矩阵） B.无向图 （为对称矩阵）如：C.强连通图 D.完全图13.二分查找算法的时间复杂度是（D）A.O（n2）（冒泡排序（平均复杂时间程度）） B.O（nlog2n）（快速排序） C.O（n）（冒泡排序（最好情况下时间复杂程度）） D.O（log2n）14.已知8个元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（B）A.4 B.5 注：1.二次排序树的规则：C.6 D.7左小又大，连续一致原则规律：左面的总小于右面的差值最小原则eq\o\ac(○,34)1规律：左面的总小于右面的差值最小原则eq\o\ac(○,18)eq\o\ac(○,76)2eq\o\ac(○,26)eq\o\ac(○,45)eq\o\ac(○,92)3 eq\o\ac(○,54)4eq\o\ac(○,65)515.采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是（C）A.插入和快速 B.冒泡和快速 C.选择和插入 D.选择和冒泡二、填空题（本大题共13小题，每小题2分，共26分）请在每小题的空格中填上正确答案。错填、不填均无分。16.在数据结构中，数据的存储结构有顺序存储方式、链式存储方式、_索引存储方式_____和散列存储方式等四种。17.作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为_算法输入的规模或问题的规模____。18.在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向_直接前趋_和__直接后继__。19.在有n个元素的链队列中，入队和出队操作的时间复杂度分别为__O（1）______和___O（n）____。20.在栈结构中，允许插入的一端称为_栈顶_____；在队列结构中，允许插入的一端称为___队尾______。21.在循环队列中，存储空间为0~n-1。设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front，队满标志为_（rear+1）%maxsize=front__。22.深度为k的二叉树至多有_____2k-1__个结点，最少有____2k-1_____个结点。23.设有一稠密图G，则G采用__邻接矩阵_存储结构较省空间。设有一稀疏图G，则G采用__邻接表__存储结构较省空间。24.在一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较_（n+1）/2__个元素结点。25.假定对线性表R［0…59］进行分块检索，共分为10块，每块长度等于6。若检索索引表和块均用顺序检索的方法，则检索每一个元素的平均检索长度为___9_____。分块查找的平均查找长度为：ASLbs=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小题，每小题6分，共30分）解题过程：前：ABCD解题过程：前：ABCDEFG中：CBDAEGF前：BCD前：EFG中：CBD中：EGFCD前：FG中：GF答：eq\o\ac(○,A)eq\o\ac(○,B)eq\o\ac(○,E)eq\o\ac(○,C)eq\o\ac(○,D)eq\o\ac(○,F)eq\o\ac(○,G)后序遍历为：CDBGFEA解题说明：解题说明：前序遍历的第一个为“root”后续遍历的最后一个为“root”中序遍历为控制左右孩子的分界点。总体思路：先找root，然后到对应的中续遍历或后续遍历中找到该元素，对应着该元素的左边的所有元素到前序或者后续里找到对应元素，再确定root，依次类推即可。前序：中左右中续：左中右后续：左右中30.将题30图所示的由三棵树组成的森林转化为一棵二叉树。解题思路：除保留第一个兄弟结点外解题思路：除保留第一个兄弟结点外，其它连接父节点的兄弟结点全部断开，变为其兄弟结点的右孩子。（如红箭头所示）为垂直线的顺时针旋转45度（不旋转就挤到一起啦。）（如黄箭头所示）割裂后的结点，左孩子是谁的，还是谁的，不改变。（如绿箭头）解：eq\o\ac(○,A)eq\o\ac(○,B)eq\o\ac(○,H)eq\o\ac(○,E)eq\o\ac(○,C)eq\o\ac(○,I)eq\o\ac(○,O)eq\o\ac(○,F)eq\o\ac(○,D)eq\o\ac(○,J)eq\o\ac(○,P)eq\o\ac(○,G)eq\o\ac(○,K)eq\o\ac(○,Q)eq\o\ac(○,L)eq\o\ac(○,R)eq\o\ac(○,M)eq\o\ac(○,N)““^”代表结束符号31.已知某图的邻接表存储结构如题31图所示：注：解题思路：1.深度优先搜索法是按照每一选定的顶点出发，走“一路到底原则”（但不能走相同路径），但走完后包括所有节点。（选择路径不同，其最后结果不一样，答案不唯一。）注：解题思路：1.深度优先搜索法是按照每一选定的顶点出发，走“一路到底原则”（但不能走相同路径），但走完后包括所有节点。（选择路径不同，其最后结果不一样，答案不唯一。）2.广度优先搜索法是指的从某点出发能够辐射到的最大范围选的点。题31图画出该图。 （2）根据该邻接表从顶点A出发，分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。答：根据该邻接表从顶点出发1.深度优先搜索法为：A-B-C-F-G-H-E-D2.广度优先搜索法为:A-B-D-C-E-F-H-G32.假定采用H（k）=kmod7计算散列地址，引用线性探测的开放定址法解决冲突，试在0~6的散列地址空间中，对关键字序列（38，25，74，63，52，48）构造散列表，并求出等概率情况下查找成功的平均查找长度。答：由题意可知关键字构成的散列表如下图。下标0123456634838257452探查次数131124等概况下的查找成功的平均查找长度为：（1+3+1+1+2+4）/7=1.71题中给出多少长度范围，就有多少个空间。（注意，一般是从0开始，所以有N+1个空格）题中给出多少长度范围，就有多少个空间。（注意，一般是从0开始，所以有N+1个空格）按照关键字顺序依次进行余数运算。（题目已给出公式），按照余数放在对应下表内，若冲突，往后放。注意，最后的次数算的是每一个格都要计算到的。33.用快速排序法对数据序列（49，38，65，97，16，53，134，27，39）进行排序，写出其第一趟排序的全过程。答：初始关键字[4938659716531342739]第1趟排序后[39 38 27 16] 49[531349765]第2趟排序后[163827 ]39 49[531349765] 第3趟排序后 16[38 27]39 49[531349765] 第4趟排序后16273839 49[531349765] 第5趟排序后162738394953[1349765] 第6趟排序后162738394953[6597]134第7趟排序后1627383949536597134解题经验：对第一个数字初始解题经验：对第一个数字初始然后将这个数字与中间的数字进行比较，若大于这个数字，那么这个数字往前推一个，若小于这个数字，那么这个数字往后退一个。然后以关键字为分界点，1.若分界点左的数小于分界点，分界点右的数大于分界点，那么这个数字不动。2.第三找出分界点左面大于分界点的数，按照从后往前的顺序写。再找出分界点