自考数据结构导论20040年01月试卷

数据结构自考试题和答案一、单项选择题（每题2分，共20分）1. 在数据结构中，算法的时间复杂度是指（）。

A. 执行算法所需要的时间B. 执行算法所需要的指令条数C. 算法执行过程中所需要的基本操作次数D. 算法执行过程中所需要的存储空间答案：C2. 线性表的顺序存储结构和链式存储结构相比，其优点是（）。

A. 存储密度高B. 存储密度低C. 插入和删除操作快D. 存储空间可以动态分配答案：A3. 在二叉树的遍历过程中，若某结点的左孩子为空，则其右孩子（）。

A. 一定为空B. 一定为非空C. 可能为空，也可能为非空D. 以上说法都不对答案：C4. 哈希表的构造方式是（）。

A. 数组B. 树C. 链表D. 数组和链表5. 一个长度为n的线性表，若采用顺序存储结构，则其在表中第i个位置的元素（1≤i≤n）的存储地址为（）。

A. 100+iB. 100+(i-1)×2C. 100+(i-1)×3D. 100+(i-1)×4答案：B6. 在二叉排序树中，若某结点的左子树非空，则其左子树中任一结点的值（）。

A. 都小于该结点的值B. 都大于该结点的值C. 都等于该结点的值D. 都大于等于该结点的值7. 对于图的遍历，以下说法正确的是（）。

A. 深度优先搜索只能使用递归实现B. 广度优先搜索只能使用队列实现C. 深度优先搜索和广度优先搜索都可以使用递归和非递归方式实现D. 深度优先搜索和广度优先搜索都必须使用栈实现答案：C8. 在一个具有n个顶点的无向图中，若该图是连通图，则其边数最少为（）。

A. n-1B. nC. n+1D. 2n9. 一个栈的入栈序列为1, 2, 3, 4, 5，则可能的出栈序列为（）。

A. 1, 3, 5, 2, 4B. 4, 5, 3, 2, 1C. 5, 4, 3, 2, 1D. 2, 4, 1, 3, 5答案：C10. 在一个有向图中，若存在从顶点v到顶点w的有向路径，则称v可达w，若存在从顶点v到图中每一个顶点的路径，则称v是（）。

自学考试数据结构试题全国1月自学考试数据结构试题课程代码：02331请考生按规定用笔将所有试题的答案涂、写在答题纸上。

选择题部分注意事项：1．答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。

2．每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。

如需改动，用橡皮擦干净后，再选涂其它答案标号。

不能答在试题卷上。

一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。

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

1．数据的逻辑结构能够分为A．动态结构和静态结构 B.顺序结构和链式结构C．线性结构和非线性结构 D.简单结构和构造结构2．线性表是一个有限序列，组成线性表的基本单位是A．数据项 B.数据元素C．数据域 D.字符3．栈中有a、b和c三个元素，a是栈底元素，c是栈顶元素，元素d等待进栈，则不可．．能．的出栈序列是A．dcba B.cbdaC．cadb D.cdba4．稀疏矩阵的三元组表是A．顺序存储结构 B.链式存储结构C．索引存储结构 D.散列表存储结构5．已知广义表G，head(G)与tail(G)的深度均为6，则G的深度是A．5 B.6C．7 D.86．下列编码集合中，属于前缀编码的一组是A.{11,10,001,101,0001}B.{00,010,0110,1000}C.{11,01,001,0101,0001}D.{0,10,110,1011}7.如题7图所示二叉树的中序序列为A．ACDBB．DCBAC．CDBAD．ABCD题7图8．有向图中所有顶点入度之和与所有顶点出度之和的比是A．1/2 B.1C．2 D.49．含有n个顶点和e条边的有向图的邻接矩阵中，零元素的个数是A.eB.2eC.n2-2eD.n2-e10.n个顶点的无向连通图，其生成树的边数为A.n-lB.nC.n+lD.nlogn11．用自底向上的冒泡排序方法对序列(8,13,26,55,29,44)从大到小排序，第一趟排序需进行交换的次数为A．2 B.3C．4 D.512．对序列(8,13,26,55,29,44)从小到大进行基数排序，第一趟排序的结果是A.(13,44,55,26,8,29)B.(13,26,55,44,8,29)C.(8,13,26,29,44,55)D.(29,26,8,44,55,13) 13．采用分块查找时，要求数据A．块内有序 B.分块有序C．分块无序 D.每块中数据个数必须相同。

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

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

1.逻辑上通常可以将数据结构分为（ ）A.动态结构和静态结构B.顺序结构和链式结构C.线性结构和非线性结构D.初等结构和组合结构2.在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（ ）A.访问第i 个元素的前驱（1<n i ≤）B.在第i 个元素之后插入一个新元素(n i 1≤≤)C.删除第i 个元素(n i 1≤≤)D.对顺序表中元素进行排序3.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（ ）A.head= =NULLB.head –>next= =NULLC.head!=NULLD.head –>next= =head4.已知栈的最大容量为4。

若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ ）A.5，4，3，2，1，6B.2，3，5，6，1，4C.3，2，5，4，1，6D.1，4，6，5，2，35.与线性表相比，串的插入和删除操作的特点是（ ）A.通常以串整体作为操作对象B.需要更多的辅助空间C.算法的时间复杂度较高D.涉及移动的元素更多6.假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（ ）A.⎪⎪⎪⎪⎪⎭⎫ ⎝⎛--00405000000000706080 B.⎪⎪⎪⎪⎪⎭⎫ ⎝⎛--000000040530007060802 C.⎪⎪⎪⎪⎪⎭⎫ ⎝⎛--00405000073000006080 D.⎪⎪⎪⎪⎪⎭⎫⎝⎛--000003040500007060807.以下有关广义表的表述中，正确的是（ ）A.由0个或多个原子或子表构成的有限序列B.至少有一个元素是子表C.不能递归定义D.不能为空表8.树的先根序列等同于与该树对应的二叉树的（ ）A.先序序列B.中序序列C.后序序列D.层序序列9.假设有．向图含n 个顶点及e 条弧，则表示该图的邻接表中包含的弧结点个数为（） A.n B.eC.2eD.n ·e10.如图所示的有向无环图可以得到的不同拓扑序列的个数为（ ）A.1B.2C.3D.411.下列排序方法中，稳定的排序方法为（ ）A.希尔排序B.堆排序C.快速排序D.直接插入排序12.对下列关键字序列进行快速排序时，所需进行比较次数最少的是（ ）A.（1，2，3，4，5，6，7，8）B.（8，7，6，5，4，3，2，1）C.（4，3，8，6，1，7，5，2）D.（2，1，5，4，3，6，7，8）13.含n 个关键字的二叉排序树的平均查找长度主要取决于（ ）A.关键字的个数B.树的形态C.关键字的取值范围D.关键字的数据类型14.下列查找算法中，平均查找长度与元素个数n 不直接相关的查找方法是（ ）A.分块查找B.顺序查找C.二分查找D.散列查找15.可有效提高次关键字查找效率的文件是（）A.顺序文件B.倒排文件C.散列文件D.VSAM文件二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。

数据结构导论自考题-1(总分100,考试时间90分钟)一、单项选择题在每小题列出的四个备选项中只有一个是符合题目要求的。

1. 算法的便于阅读和理解的特性称为( )A．正确性 B．易读性C．健壮性 D．时空性2. 给定有n个元素，建立一个有序单链表的时间复杂度为( )A．O(1) B．O(n)C．O(n2) D．O(nlog2n)3. 在双链表中某结点(已知其地址)前插入一新结点，其时间复杂度为( )A．O(n) B．O(1)C．O(n2) D．O(log2n)4. 顺序栈s中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e 进栈操作的主要语句为( )A．s.elem[top]=e;s.top=s.top+1;B．s.elem[top+1]=e;s.top=s.top+1;C．s.top=s.top+1;s.elem[top+1]=e;D．s.top=s.top+1;s.elem[top]=e;5. 一个数组的第一个元素的存储地址是100，每个元素占2个存储单元，则第5个元素的存储地址是( )A．110 B．108C．100 D．1206. 已知某完全二叉树采用顺序存储结构，结点数据的存放顺序依次为A、B、C、D、E、F、G、H，该完全二叉树的后序遍历序列为( )A．HDBEFCGA B．HDEBFGCAC．DHEBFGACA D．DEHBFGCA7. 除根结点外，树上每个结点( )A．可有任意多个孩子、一个双亲 B．可有任意多个孩子、任意多个双亲C．可有一个孩子、任意多个双亲 D．只有一个孩子、一个双亲8. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )A．250 B．500C．501 D．5059. 设有6个结点的无向图，若要确保此图是一个连通图，则至少应有边的条数是( )A．5 B．6C．7 D．810. 在含有n个顶点e条边的无向图的邻接矩阵中，零元素的个数为( )A．e B．2eC．n2-e D．n2-2e11. 设有无向图G=(V，E)和(G'=(V'，E')，如G'为G的生成树，则下面说法不正确的是( )A．G'为G的子图 B．G'为G的连通分量C．G'为G的极小连通子图且V'=V D．G'是G的无环子图12. 利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素35要进行元素间比较的次数是( )A．4次 B．5次C．7次 D．10次13. 采用二分查找法，若当前取得的中间位置MID的元素值小于被查找值，则表明待查元素可能在表的后半部分，下次查找的起始位置通常应( )A．从MID/2位置开始 B．从MID位置开始C．从MID-1位置开始 D．从MID+1位置开始14. 当待排序序列中记录数较少或基本有序时，最适合的排序方法为( )A．直接插入排序法 B．快速排序法C．堆排序法 D．归并排序法15. 一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )A．(38，40，46，56，79，84) B．(40，38，46，79，56，84)C．(40，38，46，56，79，84) D．(40，38，46，84，56，79)二、填空题16. 算法的空间性能是指算法需要的______。

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

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

1.数据结构中所定义的数据元素，是用于表示数据的（）A.最小单位B.最大单位C.基本单位D.不可分割的单位2.数据的四种基本存储结构是指（）A.顺序存储结构、索引存储结构、直接存储结构、倒排存储结构B．顺序存储结构、索引存储结构、链式存储结构、散列存储结构C．顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构D.顺序存储结构、链式存储结构、树型存储结构、图型存储结构3.对于长度为n的顺序表执行删除操作，则其结点的移动次数（）A.最少为0，最多为nB.最少为1，最多为nC.最少为0，最多为n-1D.最少为1，最多为n-14.在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的正确操作是（）A. p->next=q B. p->next=q->nextC. p=q->nextD. p->next=q->next->next5.有关栈的描述，正确的是（）A.栈是一种先进先出的特殊的线性表B.只能从栈顶执行插入、删除操作C.只能从栈顶执行插入、栈底执行删除D.栈顶和栈底均可执行插入、删除操作6.二维数组A［10］［20］采用按行为主序的存储方式，每个元素占4个存储单元，若A［0］［0］的存储地址为300，则A［10］［10］的地址为（）A.700B.1120C.1180D.11407.关于二叉树性质的描述，正确的是（）1A.二叉树结点的个数可以为0B.二叉树至少含有一个根结点C.二叉树若存在两个结点，则必有一个为根，另一个为左孩子D.二叉树若存在三个结点，则必有一个为根，另两个分别为左、右孩子8.具有4个结点的二叉树可有（）A.4种形态B.7种形态C.10种形态D.11种形态9.若采用邻接表存储结构，则图的深度优先搜索类似于二叉树的（）A.先根遍历B.中根遍历C.后根遍历D.层次遍历10.具有n个顶点的无向图，若要连通全部顶点，至少需要（）A.（n-1）条边B. n条边C. n(n-1)条边D. n(n-1)/2条边11.下列四种基本的逻辑结构中，结构结点间不存在．．．任何逻辑联系的是（）A.集合B.线性结构C.树形结构D.图形结构12.闭散列表中由于散列到同一个地址而引起的“堆积”现象，是由（）A.同义词之间发生冲突引起的B.非同义词之间发生冲突引起的C.同义词与非同义词之间发生冲突引起的D.散列地址“溢出”引起的13.ISAM文件组织方式是一种（）A.专门适用于磁带的存取方法B.专门适用于磁盘的存取方法C.专门适用于光盘的存取方法D.可适用于磁带、磁盘、光盘等多用途的存取方法14.当待排序序列中记录数较多时，速度最快的排序方法是（）A.冒泡排序法B.快速排序法C.堆排序法D.归并排序法15.若对序列（15，30，26，22，69，50，53，87）采用二路归并法排序，则进行一趟归并后产生的序列为（）A.15，22，26，30，50，53，69，87B.15，30，22，26，50，69，53，87C.15，26，30，22，50，69，53，87D.15，26，22，30，50，53，69，87二、填空题(本大题共13小题，每小题2分，共26分)2请在每小题的空格中填上正确答案。

数据结构自考试题及答案一、单项选择题（每题1分，共10分）1. 在数据结构中，从逻辑上可以把数据结构分为（）。

A. 动态结构和静态结构B. 线性结构和非线性结构C. 顺序结构和链式结构D. 内部结构和外部结构答案：B2. 线性表的顺序存储结构和链式存储结构相比，它的优点是（）。

A. 存储密度大B. 存储密度小C. 插入和删除操作快D. 可以进行随机访问答案：D3. 下列关于栈的描述中，错误的是（）。

A. 栈是先进后出（LIFO）的线性表B. 栈允许在一端进行插入和删除操作C. 栈是具有记忆功能的线性表D. 栈的插入和删除操作必须在栈顶进行答案：C4. 在二叉树的遍历过程中，若某结点的左子树为空，则该结点的左孩子直接与（）相连。

A. 右孩子B. 右兄弟C. 父节点D. 子节点答案：C5. 哈希表的构造方式是（）。

A. 数组B. 树C. 链表D. 图答案：A6. 在图的遍历过程中，深度优先搜索（DFS）和广度优先搜索（BFS）的主要区别在于（）。

A. 遍历顺序B. 是否使用栈C. 是否使用队列D. 是否使用递归答案：C7. 快速排序算法的时间复杂度在最坏情况下是（）。

A. O(n)B. O(nlogn)C. O(n^2)D. O(2^n)答案：C8. 以下排序算法中，时间复杂度为O(nlogn)的是（）。

A. 冒泡排序B. 选择排序C. 快速排序D. 插入排序答案：C9. 在数据库管理系统中，索引的作用是（）。

A. 存储数据B. 提高查询效率C. 维护数据完整性D. 实现数据加密答案：B10. 以下不属于查找算法的是（）。

A. 顺序查找B. 二分查找C. 哈希查找D. 归并排序答案：D二、填空题（每题2分，共20分）11. 在数据结构中，线性表的顺序存储结构通常使用___________来实现。

答案：数组12. 一个长度为n的顺序表，若在第i个位置插入一个元素（1≤i≤n+1），需要向后移动___________个元素。

全国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分)请在每小题的空格中填上正确答案。

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

每小题1分，共14分)1.计算机算法指的是( )。

A.计算方法B.排序方法C.解决某一问题的有限运算序列D.调度方法2.在一个单链表中，若p↑结点不是最后结点，在p↑之后插入s↑结点，则实行( )。

A. s↑.next:=p；p↑.next=s;B. s↑.next:=p↑.next;p↑.next:=s；C. s↑.next:=p↑.next;p:=s;D. p↑.next:=s;s↑.next=p;3.某个向量第一元素的存储地址为100，每个元素的长度为2，则第五个元素的地址是( )。

A.110B.108C.100D.1204.循环队列用数组A［0..m-1］存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是( )。

A.(rear-front+m) MOD mB.rear-front+1C.rear-front-1D.rear-front5.栈和队列的共同特点是( )。

A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点6.深度为n的二叉树中所含叶子结点的个数最多为( )个。

A.2nB.nC.2n-1D.2n-17.树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据8.下面的二叉树中，( )不是完全二叉树。

9.下列说法错误的是( )。

A.一个图的邻接矩阵表示是唯一的B.一个图的邻接表表示是不唯一的C.一个图的生成树必为该图的极小连通子图D.一个无环有向图的拓扑排序序列必唯一10.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A.5B.6C.7D.811.对线性表进行二分查找时，要求线性表必须( )。

更多优质自考资料尽在百度贴吧自考乐园俱乐部（/club/5346389）欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........2004年下半年全国自考数据结构真题一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

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

1.A. AB. BC. CD. D答案：D2.若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是（）A.s->next=p->next;p->next=s;B.p->next=s;s->next=p->next;C.p->next=s->next;s->next=p;D.s->next=p;p->next=s->next;答案：A3.若要在O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向（）A.各自的头结点B.各自的尾结点C.各自的第一个元素结点D.一个表的头结点，另一个表的尾结点答案：B4.栈的两种常用存储结构分别为（）A.顺序存储结构和链式存储结构B.顺序存储结构和散列存储结构C.链式存储结构和索引存储结构D.链式存储结构和散列存储结构答案：A5.已知循环队列的存储空间为数组data［21］，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为（）A. 5B. 6C.16D.17答案：C6.已知在如下定义的链串结点中，每个字符占1个字节，指针占4个字节，则该链串的存储密度为typedef struct node {char data［8］;struct node *next;} LinkStrNode;（）A.1/4B.1/2C.2/3D.3/4答案：C7.应用简单的匹配算法对主串s=″BDBABDABDAB″与子串t=″BDA″进行模式匹配，在匹配成功时，进行的字符比较总次数为（）A.7B.9C.10D.12答案：C8.二维数组A［20］［10］采用列优先的存储方法，若每个元素占2个存储单元，且第1个元素的首地址为200，则元素A［8］［9］的存储地址为（）A.574B.576C.578D.580答案：B9.对广义表L=((a,b),c,d)进行操作tail(head(L))的结果是（）A.（c,d）B.(d)C. bD.(b)答案：D10.已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为（）A.ABCDEFB.ABCEFDC.ABFCDED.ABCDFE答案：D11.一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为（）A. AB. BC. CD. D答案：A12.在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为（）A.4，4，3B.4，3，3C.3，4，4D.3，3，4答案：B13.下列排序方法中，最好与最坏时间复杂度不相同的排序方法是（）A.冒泡排序B.直接选择排序C.堆排序D.归并排序答案：A14.已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于（）A. 1.0B. 2.9C. 3.4D. 5.5答案：B15.在下列各种文件中，不能进行顺序查找的文件是（）A.顺序文件B.索引文件C.散列文件D.多重表文件答案：C二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。

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

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

1．根据数据元素的关键字直接计算出该元素存储地址的存储方法是（）A．顺序存储方法B．链式存储方法C．索引存储方法D．散列存储方法2．下述程序段中语句①的频度是（）s=0;for(i=1;i<m;i++)for(j=0;j<=i;j++)①s+=j;A．211)m)(m(-+B．21)m (m-C．212)m)(m(-+D．21)m(m+3．求单链表中当前结点的后继和前驱的时间复杂度分别是（）A．O（n）和O（1）B．O（1）和O（1）C．O（1）和O（n）D．O(n)和O（n）4．非空的单循环链表的头指针为head,尾指针为rear，则下列条件成立的是（）A．rear->next= =head B．rear->next->next= =headC．head->next= =rear D．head->next->next= =rear5．若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是（）A．栈B．线性表C．队列D．二叉排序树6．已知主串s=″ADBADABBAAB″，模式串t=″ADAB″，则应用朴素的串匹配算法进行模式匹配过程中，无效位移的次数是（）A．2 B．3C．4 D．57．串s=″Data Structure″中长度为3的子串的数目是（）1A．9 B．11C．12 D．148．假设以行优先顺序存储三维数组R[6][9][6]，其中元素R[0][0][0]的地址为2100，且每个元素占4个存储单元，则存储地址为2836的元素是（）A．R[3][3][3] B．R[3][3][4]C．R[4][3][5] D．R[4][3][4]9．除第一层外，满二叉树中每一层结点个数是上一层结点个数的（）A．1/2倍B．1倍C．2倍D．3倍10．对于含n个顶点和e条边的图，采用邻接矩阵表示的空间复杂度为（）A．O（n）B．O(e)C．O(n+e) D．O(n2)11．如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（）A．深度优先搜索算法B．广度优先搜索算法C．求最小生成树的prim算法D．拓扑排序算法12．快速排序在最坏情况下的时间复杂度是（）A．O(n2log2n) B．O(n2)C．O(nlog2n) D．O(log2n)13．能进行二分查找的线性表,必须以（）A．顺序方式存储,且元素按关键字有序B．链式方式存储,且元素按关键字有序C．顺序方式存储,且元素按关键字分块有序D．链式方式存储,且元素按关键字分块有序14．为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,第一个插入的关键字应为（）A．05 B．37C．41 D．6215．ISAM文件的周期性整理是为了空出（）A．磁道索引B．柱面索引C．柱面基本区D．柱面溢出区二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。