2006年1月自考数据结构导论试题真题

2006年下半年全国自考（数据结构）真题试卷(题后含答案及解析)题型有：1. 单项选择题 2. 填空题 3. 解答题 4. 算法阅读题 5. 算法设计题单项选择题1．数据结构是( )A．一种数据类型B．数据的存储结构C．一组性质相同的数据元素的集合D．相互之间存在一种或多种特定关系的数据元素的集合正确答案：D2．算法分析的目的是( )A．辨别数据结构的合理性B．评价算法的效率C．研究算法中输入与输出的关系D．鉴别算法的可读性正确答案：B3．在线性表的下列运算中，不改变数据元素之间结构关系的运算是( )A．插入B．删除C．排序D．定位正确答案：D4．若进栈序列为1,2,3,4,5,6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为( )A．3,2,6,1,4,5B．3,4,2,1,6,5C．1,2,5,3,4,6D．5,6,4,2,3,1正确答案：B5．设串s1=“Data Structures、with Java”，s2=“it”，则子串定位函数index(s1，s2)的值为( )A．15B．16C．17D．18正确答案：C6．二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为( ) A．1207B．1209C．1211D．1213正确答案：A7．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是( ) A．队列B．栈C．线性表D．有序表正确答案：A8．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系( )A．不一定相同B．都相同C．都不相同D．互为逆序正确答案：B9．若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的( )A．层次遍历算法B．前序遍历算法C．中序遍历算法D．后序遍历算法正确答案：C10．若用邻接矩阵表示一个有向图，则其中每一列包含的”1”的个数为( )A．图中每个顶点的入度B．图中每个顶点的出度C．图中弧的条数D．图中连通分量的数目正确答案：A11．图的邻接矩阵表示法适用于表示( )A．无向图B．有向图C．稠密图D．稀疏图正确答案：C12．在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为( )A．iB．i+1C．n-iD．n-i+1正确答案：D13．下列排序算法中，其时间复杂度和记录的初始排列无关的是( ) A．插入排序B．堆排序C．快速排序D．冒泡排序正确答案：B14．若有序表的关键字序列为(b,c,d,e,f,g,q,r,s,t)，则在二分查找关键字b的过程中，先后进行比较的关键字依次为( )A．f,c,bB．f,d,bC．g,c,bD．g,d,b正确答案：A15．若在文件中查询年龄在60岁以上的男性及年龄在55岁以上的女性的所有记录，则查询条件为( )A．(性别=“男”)OR(年龄＞60)OR(性别=“女”)OR(年龄＞55)B．(性别=“男”)OR(年龄＞60)AND(性别=“女”)OR(年龄＞55)C．(性别=“男”)AND(年龄＞60)OR(性别=“女”)AND(年龄＞55)D．(性别=“男”)AND(年龄＞60)AND(性别=“女”)AND(年龄＞55)正确答案：C填空题16．称算法的时间复杂度为O(f(n))，其含义是指算法的执行时间和______的数量级相同。

全国2006年1月高等教育自学考试数据库及其应用试题课程代码：02120一、单项选择题（本大题共20小题，每小题2分，共40分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1.以下不．是数据库技术所具备的特点是（）A.数据结构化B.数据冗余小C.有较高的数据独立性D.数据联系弱2.在信息模型的“学生”实体中，对每个学生的具体情况的描述，称为（）A.实体值B.实体型C.属性值D.属性型3.可用于区别实体集中不同个体的属性或属性组合，称为该实体的（）A.属性型B.键C.外部键D.实体型4.设一个体育项目可以有多个运动员报名，一个运动员可参加多个项目，运动员与体育项目之间是（）A.一对一的联系B.一对多的联系C. 多对一的联系D. 多对多的联系5.实体完整性约束可以通过（）A.定义外部键来保证B.定义主键来保证C. 用户定义的完整性来保证D. 定义字段类型来保证6.下面结论不．正确的是（）A.若A→B，B→C，则A→CB.若A→B，A→C，则A→（B,C）C. 若B→A ，C→A ，则（B,C ）→AD. 若（B,C ）→A ，则B →A ，C →A7.设R为k1度关系，S为k2度关系，则R和S的笛卡尔积的度为（）A.k1B.k2C.k1+k2D.k1 ×k28.将E—R图转换为关系模型，属于数据库设计的（）A.事务设计阶段B.物理设计阶段C. 逻辑设计阶段D. 应用程序设计阶段9.数据库系统开发完成以后，不．需要提供给用户的文档资料是（）A.系统说明书 B.技术说明书C.使用说明书D.可行性说明书10.使用SQL语句在学生成绩表（学号，课程号，成绩）中，查询平均成绩大于60分的学生时，不．必使用的子句是（）A.SELECTB.GROUP BYC.WHERED.HAVING11.定义内存变量时，不．能使用的数据类型是（）A.数值型B.日期型C.通用型D.字符型12.下列函数中，返回非逻辑型值的函数是（）A.BOFB.RECNOC.FOUNDD.EOF13.在FoxPro中，对数函数LOG（n）是以（）A.10 为底B.2 为底C.e 为底D.n 为底14.在FoxPro中定义字段变量时，允许用户自行定义数据长度的是（）A. 逻辑型B. 数值型C. 日期型D. 通用型15.下列命令中，不．与用户进行交互方式操作的命令是（）A.BROWSEB.REPLACEC.EDITD.MODIFY16.在数据库文件已打开、而索引文件尚未打开时，打开索引文件的命令是（）E< 索引文件名>B.INDEX TO< 索引文件名>C.INDEX ON< 索引文件名>D.SET INDEX TO< 索引文件名>17. 下列叙述中，正确的是（）A. 创建数据库文件的索引文件时，只能按关键字表达式的值升序排列B.一个数据库文件可以在不同工作区中同时打开C.字段变量不受工作区的约束，任意使用D.在一个工作区中可以同时打开由JOIN命令生成的库文件以及原来的库文件18.设x=123.456，执行命令@10，10 SAY＂x=＂GET x PICTURE ＂99999.99＂输出结果是（其中：表示一个空格）（）A.x=123.456B.x= 123.45C.x= 123.46D.x=123.4519.存盘并关闭命令文件编辑窗口的按键是（）A.CTRL+KSB.CTRL+WC.CTRL+KDD.CTRL+S20.生成屏幕程序后，要对其进行修改，必须首先修改的文件的扩展名是（）A.SCXB.SCTC.SPRD.SPX二、填空题（本大题共10小题，每小题1分，共10分）请在每小题的空格中填上正确答案。

2010 01一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1.下述文件中适合于磁带存储的是（）A.顺序文件B.索引文件C.散列文件D.多关键字文件2.某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（）A.acbedB.becabC.deabcD.cedba3.含有n个结点的二叉树用二叉链表表示时，空指针域个数为( )A.n-1B.nC.n+1D.n+24.在一个图中，所有顶点的度数之和与图的边数的比是( )A.1∶2B.1∶1C.2∶1D.4∶15.长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为( )A.O(1)B.O(1og2n)C.O(n)D.O(n2)6.下述几种排序方法中，要求内存量最大的是( )A.插入排序B.快速排序C.归并排序D.选择排序7.对n个不同值进行冒泡排序，在元素无序的情况下比较的次数为( )A.n-1B.nC.n+1D.n(n-1)／28.对线性表进行二分查找时，要求线性表必须( )A.以顺序方式存储B.以链式方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列9.在表长为n的顺序表上做删除运算，其平均时间复杂度为( )A.O(1)B.O(n)C.O(nlog2n)D.O(n2)10.当利用大小为n的数组顺序存储一个队列时，该队列的最大容量为( )A.n-2B.n-1C.nD.n+111.有关插入排序的叙述，错误的．．．是( )A.插入排序在最坏情况下需要O(n2)时间B.插入排序在最佳情况可在O(n)时间内完成C.插入排序平均需要O(nlog2n)时间D.插入排序的空间复杂度为O(1)12.有关树的叙述正确的是( )A.每一个内部结点至少有一个兄弟B.每一个叶结点均有父结点C.有的树没有子树D.每个树至少有一个根结点与一个叶结点。

全国2018年1月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1.数据的四种基本逻辑结构是指( )A.数组、链表、树、图形结构B.线性表、链表、栈队列、数组广义表C.线性结构、链表、树、图形结构D.集合、线性结构、树、图形结构2.数据结构中，通常采用两种方法衡量算法的时间复杂性，即( )A.最大时间复杂性和最小时间复杂性B.最好时间复杂性和最坏时间复杂性C.部分时间复杂性和总体时间复杂性D.平均时间复杂性和最坏时间复杂性3.下列关于线性表的叙述中，不正确的是( )A.线性表是n个结点的有穷序列B.线性表可以为空表C.线性表的每一个结点有且仅有一个前趋和一个后继D.线性表结点间的逻辑关系是1:1的联系4.在一个单链表中，若p所指结点不是最后结点，则删除p所指结点的后继结点的正确操作是( )A.p=p->nextB.p->next=p->nextC.p->next=p->next->nextD.p->next=p5.栈和队列( )A.共同之处在于二者都是先进先出的特殊的线性表B.共同之处在于二者都是先进后出的特殊的线性表C.共同之处在于二者都只允许在顶端执行删除操作D.没有共同之处6.二维数组A［5］［6］采用按列为主序的存储方式，每个元素占3个存储单元，若A［0］［0］的存储地址是100，则A［4］［3］的存储地址是( )A.127B.142C.150D.1577.深度为k的二叉树至多有( )A.2k个结点B.2k-1个结点C.2k-1个结点D.2k-1-1个结点8.对于如图所示二叉树采用中根遍历，正确的遍历序列应为( )A.ABCDEFB.ABECDFC.CDFBEAD.CBDAEF129.下面关于生成树的描述中，不正确的是( )A.生成树是树的一种表现形式B.生成树一定是连通的C.生成树一定不含有环D.若生成树顶点个数为n ，则其边数一定为n-110.图的邻接表如下所示，从顶点V 1出发采用深度优先搜索法遍历该图，则可能的顶点序列 是()A.V 1V 2V 3V 4V 5B.V 1V 2V 3V 5V 4C.V 1V 4V 3V 5V 2D.V 1V 3V 4V 5V 211.下列查找方法中，不属于动态的查找方法是( )A.二叉排序树法B.平衡树法C.散列法D.斐波那契查找法12.要解决散列引起的冲突问题，常采用的方法有( )A.数字分析法、平方取中法B.数字分析法、线性探测法C.二次探测法、平方取中法D.二次探测法、链地址法13.用于外存储器的数据组织结构散列文件，主要适用于( )A.顺序存取B.随机存取C.索引存取D.以上三种都可以14.堆排序属于一种选择排序，其时间复杂性为( )A.O(1)B.O(nlog 2n)C.O(n)D.O(n 2)15.下列排序方法中，属于不稳定的排序方法是( )A.直接插入排序法B.冒泡排序法C.基数排序法D.归并排序法二、填空题(本大题共13小题，每小题2分，共26分)请在每小题的空格中填上正确答案。

全国2001年10月高等教育自学考试数据结构试题课程代码：02331第一部分选择题(30分)一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。

1．算法指的是（ D ）A．计算机程序B．解决问题的计算方法C．排序算法D．解决问题的有限运算序列2．线性表采用链式存储时，结点的存储地址（ B ）A．必须是不连续的B．连续与否均可C．必须是连续的D．和头结点的存储地址相连续3．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（C）A．O（1）B．O（n）C．O（m）D．O（m+n）4．由两个栈共享一个向量空间的好处是：（ D ）A．减少存取时间，降低下溢发生的机率B．节省存储空间，降低上溢发生的机率C．减少存取时间，降低上溢发生的机率D．节省存储空间，降低下溢发生的机率5．设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ B ）A．front=front+1 B．front=(front+1)%(m-1)C．front=(front-1)%m D．front=(front+1)%m6．如下陈述中正确的是（ A ）A．串是一种特殊的线性表B．串的长度必须大于零C．串中元素只能是字母D．空串就是空白串7．若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（C ）A．O（n3）B．O（n）C．O（n2）D．O（n3）8．一个非空广义表的表头（ D ）A．不可能是子表B．只能是子表C．只能是原子D．可以是子表或原子9．假设以带行表的三元组表表示稀疏矩阵，则和下列行表0 2 3 3 5对应的稀疏矩阵是（ A ）A.08067000000050400000--⎡⎣⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥B.08067000504000000300--⎡⎣⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥C.08060000020050400000--⎡⎣⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥D.08060000700050400300--⎡⎣⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥10．在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( C )A．4 B．5 C．6 D．711．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( D ) A．e B．2e C．n2－e D．n2－2e12．假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点v i相关的所有弧的时间复杂度是( C )A．O(n) B．O(e) C．O(n+e) D．O(n*e)13．用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是（ D ）A．选择排序B．希尔排序C．归并排序D．快速排序14．适于对动态查找表进行高效率查找的组织结构是（ C ）A．有序表B．分块有序表C．三叉排序树D．线性链表15．不定长文件是指（ B ）A．文件的长度不固定B．记录的长度不固定C．字段的长度不固定D．关键字项的长度不固定第二部分非选择题（共70分）二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）不写解答过程，将正确的答案写在每小题的空格内。

《数据结构》-1一、判断题 (每小题1分，共10分)1、线性表的逻辑顺序与物理顺序总是一致的。

( )2、线性表只能采用顺序存储结构或者链式存储结构。

( )3、线性表的顺序存储表示优于链式存储表示。

( )4、不管堆栈采用何种存储结构，只要堆栈不空，可以任意删除一个元素。

( )5、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。

( )6、已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。

( )7、一般树和二叉树的结点数目都可以为0。

( )8、序列初始为逆序时，冒泡排序法所进行的元素之间的比较次数最多。

( )9、每种数据结构都应具备三种基本运算：插入、删除和搜索。

( )10、若某堆栈的输入序列为1,2,3,4，则4,3,1,2不可能是堆栈的输出序列之一。

( )二、单项选择题 (每小题2分，共20分)1、算法分析的目的是( )A.研究算法的输入与输出之间的关系B.找出数据结构的合理性C.分析算法的效率以求改进算法D.分析算法的可读性与可移植性2、已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作( )A. s->link = p； p->link = s；B. s->link = p->link； p->link = s；C. s->link = p->link； p = s；D. p->link = s； s->link = p；3、图的深度优先搜索类似于树的（）次序遍历。

A.先根B.中根C.后根D.层次4、一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列（）A. 1，3，2，4B. 2，3，4，1C. 4，3，1，2D. 3，4，2，15、若深度为5的完全二叉树的第5层有3个叶结点，则该二叉树一共有( )个结点。

A.15B.16C.17D.186、下列排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关（）A. 直接插入排序B. 起泡排序C. 快速排序D. 直接选择排序7、对数据元素序列(49，72，68，13，38，50，97，27)进行排序，前三趟排序结束时的结果依次为：第一趟：13，72，68，49，38 ,50，97，27；第二趟：13，27，68，49，38，50，97，72；第三趟：13，27，38，49，68，50，97，72；该排序采用的方法是( )A.插入排序法B.选择排序法C.冒泡排序法D.堆积排序法8、对于循环队列，存储空间大小为n，头指针为F，尾指针为R。

全国2002年10月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题(在下列每小题四个备选答案中选出一个正确答案，并将其字母标号填入题干的括号内。

每小题2分，共30分)1．下列数据组织形式中，（）的结点按逻辑关系依次排列形成一个“锁链”。

A.集合B.树形结构C.线性结构D.图状结构2．数据结构可以形式化地定义为（S，△），其中S指某种逻辑结构，△是指（）A.S上的算法B.S的存储结构C.在S上的一个基本运算集D.在S上的所有数据元素3．下列说法正确的是（）A.线性表的逻辑顺序与存储顺序总是一致的B.线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可以不连续C.线性表的线性存储结构优于链式存储结构D.每种数据结构都具有插入、删除和查找三种基本运算4．设非空单链表的数据域为data，指针域为next，指针p指向单链表中第i个结点，s指向已生成的新结点，现将s结点插入到单链表中，使其成为第i个结点，下列算法段能正确完成上述要求的是（）A.s->next=p->next;p->next=s；B.p->next=s;s->next=p->next；C.s->next=p->next;p->next=s;交换p->data和s->data；D.p=s;s->next=p；5．稀疏矩阵一般采用（）方法压缩存储。

A.三维数组B.单链表C.三元组表D.散列表6．树若用双亲链表表示，则（）A.可容易地实现求双亲及子孙的运算B.求双亲及子孙的运算均较困难C.可容易地实现求双亲运算，但求子孙运算较困难D.可容易地实现求子孙运算，但求双亲运算较困难7．将一棵有50个结点的完全二叉树按层编号，则对编号为25的结点x，该结点（）A.无左、右孩子B.有左孩子，无右孩子C.有右孩子，无左孩子D.有左、右孩子8．用邻接表作为有向图G的存储结构。

全国自学考试数据结构导论试题及答案4套第一套试题一、选择题（每题4分，共40分）1. 下列哪个数据结构是一种非线性结构？A. 数组B. 栈C. 队列D. 树2. 下列哪种算法不适用于解决排序问题？A. 冒泡排序B. 快速排序C. 深度优先搜索D. 归并排序3. 在数据结构中，堆的底层实现通常采用哪种数据结构？A. 数组B. 栈C. 链表D. 队列4. 下列哪个选项是描述图结构的准确说法？A. 图结构是一种线性结构B. 图结构由节点和指向节点的边构成C. 图结构不能存储数据D. 图结构不支持插入和删除操作5. 下列哪个排序算法具有最坏时间复杂度为O(nlogn)？A. 冒泡排序B. 插入排序C. 选择排序D. 希尔排序二、填空题（每题4分，共40分）1. 在二叉树中，每个节点最多有____个子节点。

2. 图的两个顶点之间的路径长度是指连接这两个顶点所需的____数。

3. 链表是一种____结构。

4. 快速排序算法的核心思想是____。

5. 栈和队列都属于线性结构，其主要区别在于____操作的限制。

三、简答题（每题10分，共30分）1. 请简要描述栈的特点以及栈的应用场景。

2. 请简要介绍图的基本概念，并说明图的应用领域。

3. 请解释递归算法的原理，并给出一个使用递归算法解决问题的例子。

四、编程题（共30分）请使用任意编程语言实现一个简单的栈数据结构，并编写测试代码进行验证。

第二套试题一、选择题（每题4分，共40分）1. 在二叉搜索树中，中序遍历的结果是____。

A. 升序排列B. 降序排列C. 随机排序D. 不确定的排序2. 在哈希表结构中，解决冲突问题的常用方法是____。

A. 线性探测B. 链地址法C. 开放地址法D. 扩容法3. AVL树是一种____。

A. 二叉搜索树B. 哈希表C. B树D. 红黑树4. 以下哪个算法不是用于解决查找问题？A. 二分查找B. 深度优先搜索C. 广度优先搜索D. 哈希查找5. 以下哪个数据结构不支持随机访问元素？A. 数组B. 栈C. 链表D. 哈希表二、填空题（每题4分，共40分）1. 在二叉树中，每个节点最多有____个子节点。

全国自考《数据结构导论》真题及答案解析-卷面总分：86分答题时间：60分钟试卷题量：43题一、单选题（共30题，共60分）1.在顺序表中查找第i个元素，时间效率最高的算法的时间复杂度为（）A.O(1)B.O(√n)C.O(log2n)D.O(n)正确答案：A您的答案：本题解析：暂无解析2.树形结构中，度为0的结点称为（）A.树根B.叶子C.路径D.二叉树正确答案：B您的答案：本题解析：暂无解析3.已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={}，则图G的拓扑序列是（）A.V1,V3,V4,V6,V2,V5,V7B.V1,V3,V2,V6,V4,V5,V7C.V1,V3,V4,V5,V2,V6,V7D.V1,V2,V5,V3,V4,V6,V7正确答案：A您的答案：本题解析：暂无解析4.有关图中路径的定义，表述正确的是（）A.路径是顶点和相邻顶点偶对构成的边所形成的序列B.路径是不同顶点所形成的序列C.路径是不同边所形成的序列D.路径是不同顶点和不同边所形成的集合正确答案：A您的答案：本题解析：暂无解析5.串的长度是指（）A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数正确答案：B您的答案：本题解析：暂无解析6.组成数据的基本单位是（）A.数据项B.数据类型C.数据元素D.数据变量正确答案：C您的答案：本题解析：暂无解析7.程序段的时间复杂度为（）A.O（1）=B.O（n）C.O（n2D.O(n3)正确答案：B您的答案：本题解析：暂无解析8.与串的逻辑结构不同的数据结构是（）A.线性表B.栈C.队列D.树正确答案：D您的答案：本题解析：暂无解析9.二叉树的第i(i≥1)层上所拥有的结点个数最多为（）A.B.2iC.D.正确答案：C您的答案：本题解析：暂无解析10.设单链表中指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为（）A.p-&gt;next=p-&gt;next-&gt;nextB.p=p-&gt;nextC.p=p-&gt;next-&gt;nextD.p-&gt;next=p正确答案：A您的答案：本题解析：暂无解析11.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（）A.堆排序B.冒泡排序C.直接插入排序D.快速排序正确答案：C您的答案：本题解析：暂无解析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″正确答案：D您的答案：本题解析：暂无解析13.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并且A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则使其平衡的调整方法为()A.LL型B.LR型C.RL型D.RR型正确答案：B您的答案：本题解析：暂无解析14.如果结点A有3个兄弟结点，而且B为A的双亲，则B的度为（）A.1B.3C.4D.5正确答案：C您的答案：本题解析：15.数据表A中每个元素距其最终位置较近，则最省时间的排序算法是（）A.堆排序B.插入排序C.直接选择排序D.快速排序正确答案：B您的答案：本题解析：暂无解析16.在表长为n的顺序表上做插入运算，平均要移动的结点数为（）A.n/4B.n/3C.n/2D.n正确答案：C您的答案：本题解析：暂无解析17.顺序表中有19个元素，第一个元素的地址为200，且每个元素占一个字节，则第14个元素的存储地址为()A.212B.213C.214D.215正确答案：B您的答案：本题解析：暂无解析18.由顶点V1，V2，V3构成的图的邻接矩阵为，则该图中顶点V1的出度为(C)A.0B.1C.2D.3正确答案：C您的答案：本题解析：暂无解析19.元素的进栈次序为A，B，C，D，E，则退栈中不可能的序列是（）A.A，B，C，D，EB.B，C，D，E，AC.E，A，B，C，DD.E，D，C，B，A正确答案：C本题解析：暂无解析20.由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（）A.23B.37C.44D.46正确答案：C您的答案：本题解析：暂无解析21.在已知尾指针的单循环链表中，插入一个新结点使之成为首结点，其算法的时间复杂度为（）A.O（1）B.（log2n）C.O（n）D.O(n2)正确答案：A您的答案：本题解析：暂无解析22.已知一个有序表为(13，18，24，35，47，50，62，83，90，115，134)，当二分查找值为90的元素时，查找成功时需比较的次数为（）A.1B.2C.3D.4正确答案：B您的答案：本题解析：暂无解析23.在查找顺序表各结点概率相等的情况下，顺序按值查找某个元素的算法时间复杂度为（）A.O(1)B.O(n)C.O(√n)D.O(log2n)正确答案：B您的答案：本题解析：暂无解析24.下列各项键值序列中不是堆的为（）A.{5，23，16，68，94，72，71，73}B.{5，16，23，68，94，72，71，73}C.{5，23，16，73，94，72，71，68}D.{5，23，16，68，73，71，72，94}正确答案：C您的答案：本题解析：暂无解析25.在线性表的下列存储结构中进行插入、删除运算，花费时间最多的是（）A.单链表B.双链表C.顺序表D.单循环链表正确答案：C您的答案：本题解析：暂无解析26.在栈中进行插入和删除操作的一端称为（）A.栈顶B.栈底C.任意位置D.指定位置正确答案：A您的答案：本题解析：暂无解析27.用n个值构造一棵二叉排序树，它的最大高度为A..n/2B.nC.√nD.log2n正确答案：B您的答案：本题解析：暂无解析28.冒泡排序的时间复杂度是（）A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)正确答案：A您的答案：本题解析：暂无解析29.设无向图的邻接表如题14图所示，则该图的边数为（）A.4B.5C.10D.20正确答案：B您的答案：本题解析：暂无解析30.带表头结点链队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）A.front==rearB.front!=NULLC.rear!=NULLD.front==NULL正确答案：A您的答案：本题解析：暂无解析二、填空题（共13题，共26分）31.下列程序段的时间复杂度为________正确答案：O(n)您的答案：32.数据的逻辑结构被分为集合结构、________、树形结构和图状结构4种。

全国2018年1月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题（在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。

错选、多选或未选均无分。

每小题2分，共30分）1. 下列数据结构中，（）不都是线性结构。

A. 栈和队列B.队列和数组C.数组和串D.文件和队列2. 为了最快地对线性结构的数据进行某数据元素的读取操作，则其数据存储结构宜采用（）方式。

A. 顺序存储B.链式存储C.索引存储D.散列存储3. 设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，则删除双链表中指针s所指结点的操作为（）A. s->t1->r1=s->t1;s->r1->t1=s->r1;B. s->t1->r1=s->r1;s->r1->t1=s->t1;C. s->r1=s->t1->r1;s->t1=s->r->t1;D. s->t1=s->t1->r1;s->r1=s->r->t1;4. 假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域，现要把一个指针s所指的新结点作为非空双链表中q所指地点（中间结点）的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是（）A. q->right=s; s->left=q; q->right->left=s; s_>right=q_>right;B. s->left=q; q->right=s; q->right->left=s; s->right=q->right;C. s->left=q; s->right=q->right; q->right->left=s; q->right=s;D. 以上都不对5. 由下列三棵树组成转的森林换成一棵二叉树为（）6•具有100个结点的完全二叉树的深度为 （）A.6B.7C.8D.9（1，2, 3），（1，6，1），（3，1, 5），（3，2,-1），（4，5,4），（5，1，-3），则其转置矩阵的三元组表中第 3个三元组为（ A.（2，1，3） B.（3，1，5）8.无向图的邻接矩阵是一个（ ）A.对称矩阵B.零矩阵9.下列说法中正确的是（ ）A.一个具有n 个顶点的无向完全图的边数为 n （n-1）B. 连通图的生成树是该图的一个极大连通子图C. 图的广度优先搜索是一个递归过程D.对于非连通图的遍历过程中每调用一次深度优先搜索算法都得到该图的一个连通分量 10. 顺序查找法与二分查找法对存储结构的要求是（ ）A. 顺序查找与二分查找均只适用于顺序表B. 顺序查找与二分查找既适用于顺序表，也适用于链表C. 顺序查找只适用于顺序表D. 二分查找只适用于顺序表 11. 在开散列表上，每个地址单元所链接的同义词表（）A.其键值相同B.其元素值相同C.其散列地址相同D.其含义相同12. 散列文件中的记录通常成组存放，若干个记录组成一个存储单位，这个存储单位称为（ ）A.磁道B.块C.柱面D.桶13.索引非顺序文件中的索引表是 （ ）A.非稠密索引B.稠密索引C.主索引D.多级索引14. 对n 个记录的文件进行堆排序，最坏情况下的执行时间为 （ ）A.O （log 2n ）B.0（nlog 2n ）C.0（n ）D.O （n 2）15. 一组记录的关键码为（46, 79, 56, 38, 40, 84），则利用快速排序方法，以第一个记录为基准得到的一次划分结果为 （ ）A.38 , 40, 46, 56, 79, 84B.40, 38, 46, 79, 56, 84C.40, 38, 46, 56, 79, 84D.40, 38, 46, 84, 56, 79二、填空题（每小题 2分，共26分）请在每小题的空格中填上正确答案。