最新自考02331数据结构试题及答案含评分标准资料

格式：doc
大小：1.23 MB
文档页数：10

下载文档原格式

/ 10

02331 数据结构资料

02331数据结构第一章概论1.数据是信息的载体。

2.数据元素是数据的基本单位。

3.一个数据元素可以由若干个数据项组成。

4.数据结构指的是数据之间的相互关系，即数据的组织形式。

5.数据结构一般包括以下三方面内容：数据的逻辑结构、数据的存储结构、数据的运算①数据元素之间的逻辑关系，也称数据的逻辑结构，数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。

②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。

数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。

③数据的运算，即对数据施加的操作。

最常用的检索、插入、删除、更新、排序等。

6.数据的逻辑结构分类:线性结构和非线性结构①线性结构：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。

线性表是一个典型的线性结构。

栈、队列、串等都是线性结构。

②非线性结构：一个结点可能有多个直接前趋和直接后继。

数组、广义表、树和图等数据结构都是非线性结构。

7.数据的四种基本存储方法:顺序存储方法、链接存储方法、索引存储方法、散列存储方法（1）顺序存储方法：该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。

通常借助程序语言的数组描述。

（2）链接存储方法：该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。

通常借助于程序语言的指针类型描述。

（3）索引存储方法：该方法通常在储存结点信息的同时，还建立附加的索引表。

索引表由若干索引项组成。

若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引，稠密索引中索引项的地址指示结点所在的存储位置。

若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引稀疏索引中索引项的地址指示一组结点的起始存储位置。

索引项的一般形式是：(关键字、地址)关键字是能唯一标识一个结点的那些数据项。

023310903数据结构

数据结构（02331）一、选择题1．具有100个结点的二叉树中，若用二叉链表存储，其部分指针域用来指向结点的左、右孩子，其余_______个指针域为空。

【】A．50 B．99 C．100 D．1012．下面关于图的存储的叙述中，哪一个是正确的【】A．用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，与边数无关B．用邻接矩阵法存储图，占用的存储空间数只与图中边数有关，与结点个数无关C．用邻接表存储图，占用的存储空间数只与图中结点个数有关，与边数无关D．用邻接表存储图，占用的存储空间数只与图中边数有关，与结点个数无关3．设某一无向图有6个结点，该图至少应有_______条边才能确保该图是一个连通图。

【】A、5B、6C、7D、84．有4个顶点的无向完全图的边数为【】A．4 B．6 C．12 D．165.设二叉排序树中关键字由1至1000的整数构成，现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树上查找到的序列？【】A．2，252，401，398，330，344，397，363B．924，220，911，244，898，258，362，363C．925，202，911，240，912，245，363D．2，399，387，219，266，382，381，278，3636．在算法性能分析中，通常所说的时间复杂度指【】A．语句的频度和B．最坏时间复杂度C．渐近时间复杂度D．算法的时间消耗7．数据的四种基本逻辑结构是指【】A．数组、链表、树、图形结构B．线性表、链表、栈队列、数组广义表C．线性结构、链表、树、图形结构D．集合、线性结构、树、图形结构8．从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是【】A．n-i B．n-i+1 C．n-i-1 D．i9．在一个单链表中，若p所指结点不是最后结点，则删除p所指结点的后继结点的正确操作【】A．p=p->next B．p->next=p->next C．p->next=p->next->next D．p->next=p10．假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域，现要把一个指针s所指的新结点作为非空双链表中q所指地点(中间结点)的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是【】A．q->right=s; s->left=q; q->right->left=s; s->right=q->right;B．s->left=q; s->right=q->right; q->right->left=s; q->right=s;C．s->left=q; q->right=s; q->right->left=s; s->right=q->right;D．以上都不对11．______是数据的基本单位【】A．数据结构B．数据元素 C．数据项D．数据类型12．数据结构中，通常采用两种方法衡量算法的时间复杂性，即【】A．最大时间复杂性和最小时间复杂性B．最好时间复杂性和最坏时间复杂性C．部分时间复杂性和总体时间复杂性D．平均时间复杂性和最坏时间复杂性13．下列关于线性表的叙述中，不正确的是【】A．线性表是n个结点的有穷序列B．线性表可以为空表C．线性表的每一个结点有且仅有一个前趋和一个后继D．线性表结点间的逻辑关系是1:1的联系14．假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域，现要把一个指针s所指的新结点，插入到一个非空双向链表中，s结点作为q所指结点(中间结点)的直接后继结点，则下列算法段能正确完成上述要求的是【】A．q->right=s; s->left=q; q->right->left=s; s->right=q->right;B．s->left=q; s->right=q->right; q->right->left=s; q->right=s;C．s->left=q; q->right=s; q->right->left=s; s->right=q->right;D．以上都不对15．设一个栈的输入序列是a，b，c，d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是【】A．a，b，c，d B．a，b，d，c C．d，c，b，a D．c，d，a，b 16．在具有m个单元的循环队列中，front指示队头元素的前一个位置，rear指示队尾元素的当前位置，则队满的条件是【】A．front==rear B．(front+1)%m==rear C．rear+1==front D．(rear+1)%m==front 17．设串s1='ABCDEFG'，s2='PQRST'，函数con(x，y)返回x和y串的连接串，subs(s，I，j)返回串s 的从序号i的字符开始连续j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1，2，len(s2))，subs(s1，len(s2)，2)))的结果串是【】A．BCDEFEF B．BCDEFG C．BCPQRST D．BCDEF 18．设矩阵A是一个对称矩阵，为了节省空间，将其下三角部分按行优先存放在一维数组B中，A[0][0]存放在B[0]中，则对下三角矩阵中任一元素a ij(i>=j)，在一维数组B中下标K的值是【】A．i(i-1)/2+j-1 B．i(i+1)/2+j C．i(i+1)/2+j-1 D．i(i-1)/2+j1 9．高度为h的完全二叉树中，结点数最多为【】A．2h-1 B．2h+1 C．2h-1 D．2h20．按二叉树的定义，具有3个结点的二叉树有_______种【】A．3 B．4 C．5 D．621．以下说法正确的是【】A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．数据元素之间的逻辑关系称为数据的逻辑结构22．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为【】A．O(log2n) B．O(1) C．O(n) D．O(n2)23．算法分析的两个主要方面是【】A．空间复杂性和时间复杂性B．正确性和简明性C．可读性和文档性D．时间复杂性和程序复杂性24．设栈的输入序列为1、2、3、4，则不可能是其出栈序列【】A．1243 B．2134 C．1432 D．431225．若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0和3。

数据结构自考试题及答案

数据结构自考试题及答案一、单项选择题（每题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），需要向后移动___________个元素。

全国自学考试数据结构试题02331试题及答案

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

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

1.下列选项中与数据存储结构无关的术语是（ D ）P3A.顺序表B.链表C.链队列D.栈2.将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是（ B ）A.n-1B.nC.2n-1D.2n3.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（ D ）A.rear=(rear-1)%m;B.front=(front+1)%m;C.front=(front-1)%m;D.rear=(rear+1)%m;4.递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是（ A ）A.堆栈B.多维数组C.队列D.线性表5.设有两个串p和q，其中q是p的子串，则求q在p中首次出现位置的算法称为（ C ）A.求子串B.串联接C.串匹配D.求串长6.对于广义表A，若head(A)等于tail(A)，则表A为（ B ）P67A.( )B.(( ))C.(( ),( ))D.(( ),( ),( ))7.若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是（ C ）A.结点均无左孩子的二叉树B.结点均无右孩子的二叉树C.高度为n的二叉树D.存在度为2的结点的二叉树8.若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是（ B ）P73A.4B.5C.7D.89.下列叙述中错误的是（ C ）A.图的遍历是从给定的源点出发对每一个顶点访问且仅访问一次P107B.图的遍历可以采用深度优先遍历和广度优先遍历第 1 页C.图的广度优先遍历只适用于无向图D.图的深度优先遍历是一个递归过程10.已知有向图G=(V，E)，其中V={V1，V2，V3，V4}，E={<V1，V2>，<V1，V3>，<V2，V3>，<V2，V4>，<V3，V4>}，图G的拓扑序列是（）A.V1,V2,V3,V4B.V1,V3,V2,V4C.V1,V3,V4,V2D.V1,V2,V4,V311.平均时间复杂度为O(n log n)的稳定排序算法是（ C ）P136 P164 8-2A.快速排序B.堆排序C.归并排序D.冒泡排序12.已知关键字序列为(51，22，83，46，75，18，68，30)，对其进行快速排序，第一趟划分完成后的关键字序列是（ D ）A.(18,22,30,46,51,68,75,83)B.(30,18,22,46,51,75,83,68)C.(46,30,22,18,51,75,68,83)D.(30,22,18,46,51,75,68,83)13.某索引顺序表共有元素395个，平均分成5块。

自考数据结构试题及答案

自考数据结构试题及答案一、选择题（每题2分，共10分）1. 在数据结构中，线性表的顺序存储结构通常使用什么数据类型来存储元素？A. 数组B. 链表C. 栈D. 队列答案：A2. 下列关于栈的描述中，错误的是：A. 栈是一种后进先出（LIFO）的数据结构B. 栈顶元素可以被访问和修改C. 栈底元素可以被访问和修改D. 栈可以进行插入和删除操作答案：C3. 在二叉树的遍历算法中，先访问根节点，然后访问左子树，最后访问右子树的遍历方式是：A. 前序遍历B. 中序遍历C. 后序遍历D. 层序遍历答案：A4. 哈希表的冲突解决方法中，链地址法的基本思想是：A. 将冲突的元素存储在同一个数组位置B. 将冲突的元素存储在不同的数组位置C. 将冲突的元素存储在链表中D. 将冲突的元素存储在树中答案：C5. 下列算法中，不属于排序算法的是：A. 冒泡排序B. 快速排序C. 深度优先搜索D. 归并排序答案：C二、填空题（每题2分，共10分）1. 在数据结构中，_________是指元素之间存在一对一关系的线性结构。

答案：线性表2. 递归算法的基本思想是将问题分解为若干个规模更小的相同问题，然后_________。

答案：递归求解3. 在图的遍历算法中，广度优先搜索（BFS）通常使用_________数据结构来实现。

答案：队列4. 一个长度为n的有序数组，使用二分查找算法查找一个元素的时间复杂度为_________。

答案：O(log n)5. 哈夫曼编码是一种用于数据压缩的编码方法，它是一种_________编码。

答案：可变长三、简答题（每题5分，共20分）1. 请简述链表和数组在存储结构上的主要区别。

答案：链表的存储结构是动态的，每个元素包含数据和指向下一个元素的指针，而数组的存储结构是静态的，元素在内存中连续存储。

2. 什么是图的深度优先搜索（DFS）算法？请简述其基本步骤。

答案：深度优先搜索（DFS）算法是一种遍历图的算法，它从一个顶点开始，尽可能深地搜索图的分支。

02331数据结构答案

2017年10月高等教育自学考试全国统命题考试数据结构试题答案及评分参考(课程代码02331)一、单项选择题：本大题共I 5小题，每小题2分，共30分。

1.B2.C3.B4.B5.C6.A7.B8.A9.A 10.C ll.D 12.B 13.B 14.D 15.C二、填空题：本大题其1 0小题，每小题2分．共20分。

16.无关（或不同） 17.q->next=p->next18.递归函数 19.((b ，c,d), e f,(g ，h)20.不变 21.有向无环图22.兄弟 23.)(2n O24.装填因子 25.37/12，约为3.08三、解答题：本犬题共4小题，每小题5分，共20分。

【评分说明】本题答案不唯一。

若考生给出的答案正确，同样给分27.(1) ABCEGDF ACEGBDF ADFGBCE (3分)(2) ABCDEFG ADCBFEG (2分)【评分说明】本题答案不唯一。

若考生给出的答案正确，同样给分。

28.(1)12，11,10, 01, 19, 14. 23, 27, 55, 20， 84, 79, 68 (3分)(2)4 ，2，1(2分)【评分说明】增量序列答案不唯一。

若考生给出的增量序列是递减序列，且最后一个增量是1．同样给分。

29.(1)agebfde （或其他等价答案）（4分）(2)4个（1分）四、算法阅读题：本大题共4小题，每小题5分，共202分。

30.（1）SL1->data中的数据是{25，4，256，15，29，47，128，256，64}，SL2->data 中的数据是{22，4，-63，9，-38，34.42，3}（4分）(2)该算法比较两十线性表中相同下标位置的两个元素，较大者放到较长的线性表中，较小者放到较短的线性表中。

(1分)31.(1) ACCABB （3分）(2) O(n),其中n是二叉树中所含结点个数。

（2分）32（1)j>i，j-- （2分）(2)j=1+1;j<n-i-l （2分）(3)i++ (1分)33.(1) 15 16 18 20 30 40 （3分）(2)查找二叉排序树T中所有满足kl≤key≤k2的元素，井按升序输出。

数据结构自考试题及答案

数据结构自考试题及答案一、单项选择题（每题1分，共10分）1. 在数据结构中，最基本的数据结构是（）。

A. 线性结构B. 非线性结构C. 顺序结构D. 链式结构答案：A2. 线性表的顺序存储结构和链式存储结构相比，其主要优点是（）。

A. 存储密度高B. 存储密度低C. 存储空间少D. 插入和删除操作快答案：A3. 在一个长度为n的顺序表中，删除第i个元素（1≤i≤n）时，需要移动的元素个数为（）。

A. i-1B. n-iC. n-i+1D. n-1答案：C4. 栈的基本运算中，不包括（）。

A. 入栈B. 出栈C. 读栈顶元素D. 判断栈空答案：D5. 队列的特点是（）。

A. 先进先出B. 先进后出C. 后进先出D. 后进后出答案：A6. 树的深度为5，其中度为3的结点最多有（）个。

A. 3B. 7C. 9D. 15答案：D7. 在二叉树的前序遍历序列、中序遍历序列、后序遍历序列中，唯一与树的形态一一对应的序列是（）。

A. 前序遍历序列B. 中序遍历序列C. 后序遍历序列D. 无法确定答案：A8. 在图的遍历过程中，若某结点的入度为0，则该结点（）。

A. 一定为起点B. 一定为终点C. 可以为起点或终点D. 既不是起点也不是终点答案：C9. 哈夫曼编码是一种（）。

A. 定长编码B. 变长编码C. 唯一编码D. 非唯一编码答案：B10. 用邻接矩阵表示图时，若该图是无向图，则其邻接矩阵一定是（）。

A. 对称矩阵B. 非对称矩阵C. 稀疏矩阵D. 密集矩阵答案：A二、填空题（每题2分，共20分）1. 在数据结构中，算法的时间复杂度是指算法执行过程中所需要的基本运算次数与输入数据量之间的关系。

算法的时间复杂度通常用大O符号表示，例如，O(n)表示时间复杂度与输入数据量成______关系。

答案：线性2. 线性表的两种存储结构分别是顺序存储结构和______存储结构。

答案：链式3. 在栈中，栈顶元素是最后被插入的元素，遵循______原则。

02331数据结构

02331数据结构《02331 数据结构》在当今数字化的时代，数据结构作为计算机科学中的重要基石，对于解决各种实际问题起着至关重要的作用。

02331 数据结构这一特定的课程或者领域，涵盖了丰富而深入的知识体系，让我们一同来探索它的奥秘。

数据结构是什么？简单来说，它是组织和存储数据的方式，以便于能够高效地访问、操作和管理这些数据。

就好比我们整理自己的房间，如果东西随意堆放，找起来会非常麻烦，但如果我们把书籍放在书架上，衣服放进衣柜，杂物放进抽屉，那么就能迅速找到我们需要的东西。

在计算机中，数据结构就是为了让数据的存储和操作变得有序和高效。

在02331 数据结构中，常见的数据结构包括数组、链表、栈、队列、树和图等。

数组是一种最简单也最常见的数据结构。

它就像一排连续的格子，每个格子都有固定的位置和编号。

优点是可以通过索引快速访问元素，但缺点是插入和删除元素比较麻烦，因为可能需要移动大量的数据。

链表则与数组不同，它的元素不是连续存储的，每个元素都包含了指向下一个元素的指针。

这使得链表在插入和删除元素时非常方便，只需要修改指针的指向即可，但访问特定位置的元素就需要从头开始遍历。

栈和队列是两种特殊的线性结构。

栈遵循“后进先出”的原则，就像往一个桶里放东西，最后放进去的会最先被拿出来。

而队列则是“先进先出”，就像排队买票，先到的先买。

树是一种分层的数据结构，其中最常见的是二叉树。

二叉树的每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉搜索树则是一种特殊的二叉树，它的左子树中的节点值都小于根节点的值，右子树中的节点值都大于根节点的值。

这使得在二叉搜索树中查找、插入和删除元素的效率很高。

图是一种更为复杂的数据结构，用于表示对象之间的关系。

图由顶点和边组成，边可以有权重，表示顶点之间的连接强度或距离。

学习 02331 数据结构，不仅仅是了解这些数据结构的定义和特点，更重要的是要学会如何在实际问题中选择合适的数据结构。

自考02331数据结构真题及答案(2009-2018)

while (p ! = NULL) {
if ( ! visited[p -> adjvex] )
DFS( G, p - > adjvex) ;
p = p->next;
}
}
}
void f32 ( ALGraph * G) {
int i;
for (i = 0; i < G->n; i ++)
visited [ i ] = FALSE ;
A.先进先出B.后进先出
C.进优于出D.出优于进
4.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为( )
A.(rear-front-1)％nB.(rear-front)％n
(1)（1+8）*8/2=36 存放次对角线以上的零为37
(2)12
27.对关键字序列(5，8，1，3，9，6，2，7)按从小到大进行快速排序。
(1)写出排序过程中前两趟的划分结果；
(2)快速排序是否是稳定的排序方法?
(1)
第一趟划分结果；(2，3，1)，5，(9，6，8，7)
第二趟划分结果；(1，2，3)，5，(9，6，8，7)
if ((2)) {R[k].key<R[k-l].key
t = R[k];
R[k] = R[k-1];
R[k-1] = t;
}
(3);i++
}
}
(1)
(2)
(3)
五、算法设计题(本大题10分)
34.假设以带头结点的单链表表示线性表，单链表的类型定义如下：

自考02331数据结构真题及答案(2009-2018)

{ int i,j,k;
NodeType t;
i =0;
j =n-l;
while (i < j) {
for ((1))k=i;k<j;k++
if (R[k].key > R[k +l].key) {
t = R[k];
R[k] = R[k +1];
R[k +1] = t;
}
j--;
for (k =j; k > i; k -- )
23.对关键字序列(15，18，11，13，19，16，12，17，10，8)进行增量为5的一趟希尔排序的结果为_________。
15，12，11，10，8，16，18，17
24.索引顺序查找的索引表由各分块中的最大关键字及各分块的_____起始位置____构成。173
25.VSAM文件的实现依赖于操作系统中的_____分页____存取方法的功能。215
11.如图所示有向图的一个拓扑序列是( )
A.ABCDEF
B.FCBEAD
C.FEDCBA
D.DAEBCF
12.下列关键字序列中，构成大根堆的是( )
A.5，8，1，3，9，6，2，7B.9，8，1，7，5，6，2，33
C.9，8，6，3，5，l，2，7D.9，8，6，7，5，1，2，3
13.对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为( )172
(1)
(2)
29.已知3阶B—树如图所示，
非根【1，2】P184
根【1，2】
(1)画出将关键字6插入之后的B—树；
(2)画出在(1)所得树中插入关键字2之后的B—树。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

2018年10月高等教育自学考试全国统一命题考试
数据结构试卷
(课程代码02331)
本试卷共7页，满分l00分，考试时间l50分钟。

考生答题注意事项：
1．本卷所有试题必须在答题卡上作答。

答在试卷上无效，试卷空白处和背面均可作草稿纸。

2．第一部分为选择题。

必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。

3．第二部分为非选择题。

必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。

4．合理安排答题空间，超出答题区域无效。

第一部分选择题
一、单项选择题：本大题共l5小题，每小题2分，共30分。

在每小题列出的备选项中
只有一项是最符合题目要求的。

请将其选出。

1．下列数据结构中，逻辑结构不同的是
A．线性表 B．栈 C．队列 D．二叉树
2．将l6个数据元素的线性表按顺序存储方式存储在数组中，若第一个元素的存储地址是l000，第6个元素的存储地址是1040，则最后一个元素的存储地址是
A．1112 B．1120 C．1124 D．1128
3．设栈的初始状态为空，元素1，2，3，4，5依次入栈，不能得到的出栈序列是
A．1，2，3，4，5 B．4，5，3，2，1 C．1，2，5，4，3 D．1，2，5，3，4 4．设指针变量P指向非空单链表中的结点，next是结点的指针域，则判断P所指结点为尾结点前一个结点的逻辑表达式中，正确的是
A. p->next!=NULL&&p->next一>next->next == NULL
B．p->next!=NULL&&p->next->next—NULL
C．p->next->next==NULL
D．p->next—NULL
5．已知广义表LS=(((a，b，c)，d)，(e，(fg，(h i)))，LS的深度是
A．2 B．3 C．4 D．5
6．已知一棵完全二叉树T的第5层上共有5个叶结点，则T中叶结点个数最少是
A．5 8．8 C．10 D．27
7．已知二叉树T的前序遍历序列为a，b，c，e，d，中序遍历序列为C，e，b，d，a，则T 的后序遍历序列为
A．c，e，d,b，a B．d，e，c，b，a C．e，c，d，b，a D．e，c，b，a，d 8．有向图G有玎个顶点和e条边，G保存在邻接矩阵M中，M中0与1的个数差是
A．n(n+1)／2-e B．n(n+1)／2-2e C．n×n-e D．n×n-2e
9．有向图G中所有顶点的度数之和是24，则G中弧的数量是
A．10 B．12 C．14 D．16
10．设有向图G含有n个顶点、e条边，使用邻接表存储。

对G进行深度优先搜索遍历算法的时间复杂度是
A．O(n) B．O(口) C．O(n+e) D．O(n×e)
11．对数据序列(26，14，17，12，7，4，3)采用二路归并排序进行升序排序，两趟排序后，得到的排序结果为
A．14，26，17，l2，4，7，3 B．12，l4，l7，26，3，4，7
C．14，26，12，l7，3，4，7 D．14，26，l2，l7，3，7，4
12．下列选项中，不稳定的排序方法是
A．希尔排序 B．归并排序 C．直接插入排序 D．冒泡排序
13．一组记录的关键字为(35，48，47，23，44，88)，利用堆排序算法进行降序排序，建立的初始堆为
A．23，35，48，47，44，88 B．23，35，47，48，44，88
C．35，23，47，48，44，88 D．35，23，47，44，48，88
14．一棵二叉排序树中，关键字n所在结点是关键字m所在结点的孩子，则
A．n一定大于m B．n一定小于m
C．n一定等于m D．n与m的大小关系不确定
15．设敖列表长m=16，散列函数H(key)=key％15。

表中已保存4个关键字：addr(18)=3，· addr(35)=5，addr(51)=6，addr(22)=7，其余地址均为开放地址。

存储关键字36时存在冲突，采用线性探测法来处理。

则查找关键字36时的探查次数是
A．1 B．2 C．3 D．4
第二部分非选择题
二、填空题：本大题共l0小题，每小题2分，共20分。

16．数据项是具有独立含义的______标识单位。

17．指针P和q分别指向单链表L中的两个相邻结点，即q->next=P。

若要在q所指结点后插入指针r所指结点，则执行的语句是r->ne处=p；_________。

18．递归算法设计中的最小子问题称为递归的_________。

19．广义表((a，b)，(c，d)，e，(f (g,h)))的表尾是_________。

20．已知二叉树的前序遍历序列和后序遍历序列，则对应的二叉树_________确定。

21．如果有向无环图G中仅有一个顶点的入度为0，若要求G的拓扑序列不唯一，则G 中必须存在一个出度至少为_________的顶点。

22．将森林T转换为一棵二叉树T1，在T中结点A是结点B的右邻的兄弟(下一个兄弟)，则在T1中，A是B的_________结点。

23．对含玎个元素的数据序列采用快速排序算法进行排序，平均时间复杂度
是_________。

24．散列存储中，常用的解决冲突的方法有开放地址法和_________两大类。

25．假设顺序存储的有序表R含有8个关键字，进行二分查找时，平均查找长度
为_________。

三、解答题：本大题共4小题，每小题5分，共20分。

26．设电文字符集是{el，e2，e3，e4，e5)，各字符出现的次数分别为{36，l3，26，l8，23}。

现要为该字符集设计哈夫曼编码。

请回答下列问题。

(1)给出构造的哈夫曼树。

(2)给出各字符的哈夫曼编码。

(3)计算电文编码总长。

27．已知图G采用邻接矩阵存储，邻接矩阵如题27图所示。

(1)根据邻接矩阵画出图G。

(2)根据图G写出从顶点A开始图G的1个深度优先搜索遍历序列。

(3)根据图G写出从顶点A开始图G的1个广度优先搜索遍历序列。

28．有数据序列(12，l7，O5，l0，20，24，45，ll，l0，l2)，使用希尔排序方法将其排成升序序列。

请回答下列问题。

(1)分别写出增量为3和1的希尔排序结果。

(2)计算第一趟希尔排序中数据元素之间的总交换次数(两个 (a)
元素之间的交换记l次)。

29．设有二叉排序树T如题29图所示。

现需在T中删除结点e，请
回答下列问题。

(1)画出删除后的二叉排序树(仅需画出一棵)。

(2)在你实现的删除过程中，指针域更新的次数是多少?
四、算法阅读题：本大题共4小题，每小题5分，共20分。

30．顺序表类型定义如下：。

最新自考02331数据结构试题及答案含评分标准资料

合集下载

02331 数据结构资料

023310903数据结构

最新1月自学考试数据结构试题及答案解析

数据结构自考试题及答案

全国自学考试数据结构试题02331试题及答案

自考数据结构试题及答案

02331数据结构答案

数据结构自考试题及答案

02331数据结构

最新02331数据结构4-月份历年真题附答案资料

自考02331数据结构真题及答案(2009-2018)

最新全国自考数据结构（02331）试题及答案

自考02331数据结构真题及答案(2009-2018)

文档推荐

最新文档