高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考全国20１1年1月自学考试数据结构导论试题课程代码:０214２一、单项选择题(本大题共15小题,每小题２分,共3０分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内
错选、多选或未选均无分
在顺序表中查找第i个元素,时间效率最高的算法的时间复杂度为()Ａ
O(1)ﻩB．O（)ﻩC．O（log2n）Ｄ
Ｏ(n）2．树形结构中,度为0的结点称为()A．树根ﻩＢ
路径Ｄ．二叉树3
已知有向图G=(V,E），其中Ｖ={Ｖ１,Ｖ2，Ｖ3,V４,V５,V6,V7},E={,＜V１,V3＞，，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
如果结点A有３个兄弟结点,而且Ｂ为A的双亲,则B的度为（）A
5１5．数据表Ａ中每个元素距其最终位置较近,则最省时间的排序算法是(）A
堆排序B．插入排序Ｃ
直接选择排序ﻩＤ
快速排序二、填空题(本大题共１3小题，每小题2分,共26分)请在每小题的空格中填上正确答案
错填、不填均无分
