高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考全国20１1年1月自学考试数据结构导论试题课程代码:０214２一、单项选择题(本大题共15小题,每小题２分,共3０分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.在顺序表中查找第i个元素,时间效率最高的算法的时间复杂度为()Ａ.O(1)ﻩB．O（)ﻩC．O（log2n）Ｄ.Ｏ(n）2．树形结构中,度为0的结点称为()A．树根ﻩＢ.叶子C.路径Ｄ．二叉树3.已知有向图G=(V,E），其中Ｖ={Ｖ１,Ｖ2，Ｖ3,V４,V５,V6,V7},E={,＜V１,V3＞，，<Ｖ3，V5＞,<Ｖ3,Ｖ６＞，,},则图G的拓扑序列是（)A.V１,V３,V4,V6,V２,V５,V7Ｂ．Ｖ１，V３,V2，V６，V4,V5,V7C.Ｖ1,V３，Ｖ4，Ｖ5,V2,V6,V7D.Ｖ1,V2,V５,V3,Ｖ４,V６，V７4.有关图中路径的定义,表述正确的是()A.路径是顶点和相邻顶点偶对构成的边所形成的序列B.路径是不同顶点所形成的序列C．路径是不同边所形成的序列D.路径是不同顶点和不同边所形成的集合5.串的长度是指(）A.串中所含不同字母的个数B.串中所含字符的个数C．串中所含不同字符的个数ﻩD.串中所含非空格字符的个数６.组成数据的基本单位是（)A．数据项B.数据类型ﻩC.数据元素ﻩＤ．数据变量7．程序段i=n；x=0;do{x=x＋５＊i;i--;｝ｗｈilｅ（ｉ＞0)；的时间复杂度为()A.Ｏ（1)B.O(n)C.O（n２）ﻩＤ．O(n３)8.与串的逻辑结构不同的数据结构是（)Ａ.线性表ﻩB．栈ﻩC．队列ﻩD.树第1页高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考9.二叉树的第i（i≥1)层上所拥有的结点个数最多为()A.2iB.2iﻩC.2i-1D.2ｉ－110．设单链表中指针ｐ指向结点A，若要删除A的直接后继，则所需修改指针的操作为(）A.p->neｘt=p->ｎexｔ－>nextﻩB.p=p－>ｎextC.ｐ＝ｐ-＞next->nextＤ.ｐ->next=p11.下列排序算法中,某一趟结束后未必能选出一个元素放在其最终位置上的是（)A.堆排序Ｂ.冒泡排序ﻩC.直接插入排序D.快速排序１２.设字符串Ｓ１＝″AＢCDＥFG″，S2=″PQRST″,则运算S=CＯNCAT(SUBSＴR(Ｓ1,2,LＥNＧＴH(S2）),SＵBSＴR(S１,LENGTH(S２）,2)）后S的结果为()A．″BＣＱR″ﻩB.″ＢCＤEＦ″C.″BCDＥFG″ﻩD.″BＣDＥFEF″１3.在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并且A的左孩子的平衡因子为－1，右孩子的平衡因子为0，则使其平衡的调整方法为(）A.LL型B.ＬR型C.RL型ﻩD.ＲR型１4.如果结点A有３个兄弟结点,而且Ｂ为A的双亲,则B的度为（）A.１ﻩB.3Ｃ.4ﻩＤ.5１5．数据表Ａ中每个元素距其最终位置较近,则最省时间的排序算法是(）A.堆排序B．插入排序Ｃ.直接选择排序ﻩＤ.快速排序二、填空题(本大题共１3小题，每小题2分,共26分)请在每小题的空格中填上正确答案。错填、不填均无分。16.下列程序段的时间复杂度为___＿＿＿__＿__。ｉ=１；wｈｉle（i
