全国自学考试数据结构导论试题答案与解析4套

.PAGE.全国20XX1月自学考试数据结构导论试题课程代码：02142一、单项选择题<本大题共15小题,每小题2分,共30分>在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。1.在顺序表中查找第i个元素,时间效率最高的算法的时间复杂度为<>A.O<1> B.O<> C.O<log2n> D.O<n>2.树形结构中,度为0的结点称为<>A.树根 B.叶子 C.路径 D.二叉树3.已知有向图G=<V,E>,其中V={V1,V2,V3,V4,V5,V6,V7},E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,,<V6,V7>},则图G的拓扑序列是<>A.V1,V3,V4,V6,V2,V5,V7 B.V1,V3,V2,V6,V4,V5,V7C.V1,V3,V4,V5,V2,V6,V7 D.V1,V2,V5,V3,V4,V6,V74.有关图中路径的定义,表述正确的是<>A.路径是顶点和相邻顶点偶对构成的边所形成的序列B.路径是不同顶点所形成的序列C.路径是不同边所形成的序列D.路径是不同顶点和不同边所形成的集合5.串的长度是指<>A.串中所含不同字母的个数 B.串中所含字符的个数C.串中所含不同字符的个数 D.串中所含非空格字符的个数6.组成数据的基本单位是<>A.数据项 B.数据类型 C.数据元素 D.数据变量7.程序段i=n；x=0；do{x=x+5*i；i--；}while〔i>0；的时间复杂度为<>A.O〔1 B.O〔n C.O〔n2 D.O<n3>8.与串的逻辑结构不同的数据结构是<>A.线性表 B.栈 C.队列 D.树9.二叉树的第i〔i≥1层上所拥有的结点个数最多为<>A.2i B.2i C.2i-1 D.2i-110.设单链表中指针p指向结点A,若要删除A的直接后继,则所需修改指针的操作为<>A.p->next=p->next->next B.p=p->nextC.p=p->next->next D.p->next=p11.下列排序算法中,某一趟结束后未必能选出一个元素放在其最终位置上的是<>A.堆排序 B.冒泡排序 C.直接插入排序 D.快速排序12.设字符串S1=″ABCDEFG″,S2=″PQRST″,则运算S=CONCAT<SUBSTR<S1,2,LENGTH<S2>>,SUBSTR<S1,LENGTH<S2>,2>>后S的结果为<>A.″BCQR″ B.″BCDEF″C.″BCDEFG″ D.″BCDEFEF″13.在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并且A的左孩子的平衡因子为-1,右孩子的平衡因子为0,则使其平衡的调整方法为<>A.LL型 B.LR型 C.RL型 D.RR型14.如果结点A有3个兄弟结点,而且B为A的双亲,则B的度为<>A.1 B.3 C.4 D.515.数据表A中每个元素距其最终位置较近,则最省时间的排序算法是<>A.堆排序 B.插入排序C.直接选择排序 D.快速排序二、填空题<本大题共13小题,每小题2分,共26分>请在每小题的空格中填上正确答案。错填、不填均无分。16.下列程序段的时间复杂度为___________。i=1；while〔i<ni=i*2；17.向一个长度为n的顺序表中第i〔1≤i≤n个元素之前插入一个元素时,需向后移动___________个元素。18.在循环双链表中,删除最后一个结点,其算法的时间复杂度为___________。19.队列的插入操作在队列的___________部分进行。20.一个栈的输入序列是1,2,3,…,n,输出序列的第一个元素是n,则第i个输出元素为___________。21.一个10阶对称矩阵A,采用行优先顺序压缩存储下三角,a00为第一个元素,其存储地址为1,每个元素占有1个存储地址空间,则a85的地址为___________。22.设字符串S=″I□AM□A□STUDENT″〔其中□表示空格字符,则S的长度为___________。23.在树形结构中,没有后继的结点是___________结点。24.一棵深度为n<n>1>的满二叉树中共有___________个结点。25.在无向图中,如果从顶点v到顶点v′有路径,则称v和v′是___________。26.无向完全图G采用___________存储结构较省空间。27.在顺序查找、二分查找、索引查找和散列查找四种查找方法中,平均查找长度与元素个数没有关系的查找方法是___________。28.快速排序最好情况下的时间复杂度为___________。三、应用题<本大题共5小题,每小题6分,共30分>29.稀疏矩阵A如下,写出矩阵A的三元组表及矩阵A的转置矩阵的三元组表。30.一棵二叉树的前根遍历序列为ABCDEFG,中根遍历序列为CBDAEGF,试构造出该二叉树。31.下述矩阵表示一个无向连通网,试画出它所表示的连通网及该连通网的最小生成树。32.给定表〔80,90,50,70,75,60,40,100,试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树,画出插入完成后的二叉排序树。33.试写出一组键值〔46,58,15,45,90,18,10,62应用直接插入排序算法从小到大排序后各趟的结果。四、算法设计题<本大题共2小题,每小题7分,共14分>34.试分别写出二叉树的先根遍历和中根遍历的递归算法。35.试编写以单链表为存储结构实现直接选择排序的算法。20XX1月全国自考数据结构导论参考答案全国20XX10月自学考试数据结构导论试题课程代码：02142一、单项选择题<本大题共15小题,每小题2分,共30分>在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。1．下列描述中正确的是<>A.数据元素是数据的最小单位B.数据结构是具有结构的数据对象C.数据结构是指相互之间存在一种或多种特定关系的数据元素的集合D.算法和程序原则上没有区别,在讨论数据结构时两者是通用的2．归并排序的时间复杂度是<>A．O〔n2 B.O〔nlog2nC.O〔n D.O〔log2n3．二分查找的时间复杂度是<>A．O〔n2 B.O〔nlog2nC.O〔n D.O〔log2n4．顺序存储的表中有90000个元素,已按关键字值升序排列,假设对每个元素进行查找的概率相同,且每个元素的关键字值皆不相同,用顺序查找法查找时,需平均比较的次数为<>A．25000 B.30000C.45000 D.900005．散列文件是一种<>A．顺序文件 B.索引文件C.链接文件 D.计算寻址文件6．两个矩阵A：m×n,B：n×p相乘,其时间复杂度为<>A．O<n> B.O<mnp>C.O<n2> D.O〔mp7.常用于函数调用的数据结构是<>A.栈 B.队列C.链表 D.数组8．二维数组A［n］［m］以列优先顺序存储,数组A中每个元素占用1个字节,A［1］［1］为首元素,其地址为0,则元素A［i］［j］的地址为<>A.〔i-1×m+<j-1> B.<j-1>×n+<i-1>C.<j-1>×n+i D.j×n+i9.图的广度优先搜索使用的数据结构是<>A．队列 B.树C.栈 D.集合10．序列〔21,19,37,5,2经冒泡排序法由小到大排序,在第一次执行交换后所得结果为<>A．<19,21,37,5,2> B.<21,19,5,37,2>C.<21,19,37,2,5> D.<2,21,19,37,5>11．数据在计算机存储器内表示时,根据结点的关键字直接计算出该结点的存储地址,这种方法称为<>A．索引存储方法 B.顺序存储方法C.链式存储方法 D.散列存储方法12．在单链表中,存储每个结点有两个域,一个是数据域,另一个是指针域,指针域指向该结点的<>A．直接前趋 B.直接后继C.开始结点 D.终端结点13．在已知头指针的单链表中,要在其尾部插入一新结点,其算法所需的时间复杂度为<>A．O〔1 B.O〔log2nC.O〔n D.O〔n214．在链队列中执行入队操作,<>A．需判别队是否空 B.需判别队是否满C.限制在链表头p进行 D.限制在链表尾p进行15．一整数序列26,59,77,31,51,11,19,42,以二路归并排序从小到大排序,第一阶段的归并结果为<>A.31,51,11,42,26,77,59,19 B.26,59,31,77,11,51,19,42C.11,19,26,31,42,59,51,77 D.26,11,19,31,51,59,77,42二、填空题<本大题共13小题,每小题2分,共26分>请在每小题的空格中填上正确答案。错填、不填均无分。16．下列程序段的时间复杂度为_______。i=0；s=0；while〔s<n{i++；s=s+i；}17．数据的存储结构被分为顺序存储结构、_______、散列存储结构和索引存储结构4种。18．从一个长度为n的顺序表中删除第i个元素〔1≤i≤n时,需向前移动_______个元素。19．在单链表中,插入一个新结点需修改_______个指针。20．在队列结构中,允许插入的一端称为_______。21．稀疏矩阵采用的压缩存储方法是_______。22．向一个栈顶指针为top的链栈中插入一个新结点*p时,应执行p->next=top和_______操作。23．有m个叶结点的哈夫曼树所具有的结点数为_______。24．在一棵具有n个结点的完全二叉树中,从树根起,自上而下、自左至右地给所有结点编号。设根结点编号为1。若编号为i的结点有右孩子,那么其右孩子的编号为_______。25．在一棵树中,_______结点没有前驱结点。26．一个具有n个顶点的有向完全图的弧数是_______。27．n个顶点的无向图G用邻接矩阵A［n］［n］存储,其中第i列的所有元素之和等于顶点Vi的_______。28．选择排序的平均时间复杂度为_______。三、应用题<本大题共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退栈30．已知一棵二叉树的中根遍历序列为CBEDFAGH,后根遍历序列为CEFDBHGA,画出该二叉树。31．给定表〔15,11,8,20,14,13,试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树,画出插入完成后的二叉排序树,并判断该二叉排序树是否为平衡二叉排序树,若为非平衡二叉排序树,将它调整为平衡二叉排序树。32．如题32图所示无向图,〔1写出其邻接矩阵；〔2写出三种以顶点A为起点的深度优先搜索顶点序列。题32图33．用冒泡排序法对数据序列〔49,38,65,97,76,134,27,49进行排序,写出排序过程。并说明冒泡排序是否为稳定排序。四、算法设计题<本大题共2小题,每小题7分,共14分>34.编写计算二叉树中叶子结点数目的算法。35.开散列表的类型定义如下：typedefstructtagnode{keytypekey;structtagnode*next;}*pointer,node;typedefpointeropenhash［n］;试写出开散列表上的查找算法。20XX10月自考数据结构导论参考答案20XX10月自考试卷数据结构导论.............PAGE.20XX10月自考数据结构导论答案...PAGE.全国20XX10月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题〔本大题共15小题,每小题2分,共30分在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。1.要将现实生活中的数据转化为计算机所能表示的形式,其转化过程依次为〔A.逻辑结构、存储结构、机外表示 B.存储结构、逻辑结构、机外表示C.机外表示、逻辑结构、存储结构 D.机外表示、存储结构、逻辑结构2.若评价算法的时间复杂性,比较对数阶量级与线性阶量级,通常〔A.对数阶量级复杂性大于线性阶量级B.对数阶量级复杂性小于线性阶量级C.对数阶量级复杂性等于线性阶量级D.两者之间无法比较3.下列关于线性表的基本操作中,属于加工型的操作是〔A.初始化、求表长度、插入操作 B.初始化、插入、删除操作C.求表长度、读元素、定位操作 D.定位、插入、删除操作4.在一个单链表中,若p所指结点不是最后结点,s指向已生成的新结点,则在p之后插入s所指结点的正确操作是〔A.s–>next=p–>next;p–>next=s; B.p–>next=s–>next;s–>next=p;C.s–>next=p;p–>next=s; D.s–>next=p–>next;p=s;5.若有三个字符的字符串序列执行入栈操作,则其所有可能的输出排列共有〔A.3种 B.4种C.5种 D.6种6.C语言对数组元素的存放方式通常采用〔A.按行为主的存储结构 B.按列为主的存储结构C.按行或列为主的存储结构 D.具体存储结构无法确定7.根据定义,树的叶子结点其度数〔A.必大于 0 B.必等于0C.必等于1 D.必等于28.二叉树若采用二叉链表结构表示,则对于n个结点的二叉树一定有〔A.2n个指针域其中n个指针为NULLB.2n个指针域其中n+1个指针为NULLC.2n-1个指针域其中n个指针为NULLD.2n-1个指针域其中n+1个指针为NULL9.在一个无向图中,所有顶点的度数之和等于边数的〔A.1倍 B.2倍C.3倍 D.4倍10.若采用邻接表存储结构,则图的广度优先搜索类似于二叉树的〔A.先根遍历 B.中根遍历C.后根遍历 D.层次遍历11.采用顺序查找法,若在表头设置岗哨,则正确的查找方式通常为〔A.从第0个元素开始往后查找该数据元素B.从第1个元素开始往后查找该数据元素C.从第n个元素开始往前查找该数据元素D.从第n+1个元素开始往前查找该数据元素12.下列查找中,效率最高的查找方法是〔A.顺序查找 B.折半查找C.索引顺序查找 D.分块查找13.索引文件通常由索引表和主文件两部分构成,其中〔A.索引表和主文件均必须是有序文件B.索引表和主文件均可以是无序文件C.索引表必须是有序文件D.主文件必须是有序文件14.直接插入排序算法,其时间复杂性为〔A.O<1>B.O<n>C.O<nlog2n> D.O<n2>15.下列排序方法中,属于稳定的排序方法是〔A.直接插入排序法 B.快速排序法C.冒泡排序法 D.堆排序法二、填空题〔本大题共13小题,每小题2分,共26分请在每小题的空格中填上正确答案。错填、不填均无分。16.从数据结构的观点,数据通常可分为三个层次,即：数据、数据元素和___________。17.用程序设计语言、伪程序设计语言并混合自然语言描述的算法称为___________算法。18.对顺序表执行插入操作,其插入算法的平均时间复杂性为___________。19.在具有n个单元、且采用顺序存储的循环队列中,队满时共有___________个元素。20.若front和rear分别表示循环队列Q的头指针和尾指针,m0表示该队列的最大容量,则循环队列为空的条件是___________。21.二维数组A[10][20]采用按行为主序的存储方式,每个元素占4个存储单元,若A[0][0]的存储地址为300,则[A][10][10]的地址为___________。22.树的遍历主要有先根遍历、后根遍历和___________三种。23.深度为k的完全二叉树至少有___________个结点。24.若图的邻接矩阵是一个对称矩阵,则该图一定是一个___________。25.对于具有n个元素的数据序列,采用二叉排序树查找,其平均查找长度为___________。26.要完全避免散列所产生的"堆积"现象,通常采用___________法。27.ISAM其中文含义为___________