10月自考数据结构02331试题及答案解析

10月自考数据结构02331试题及答案解析

lO月高等教育自学考试全国统一命题考试

数据结构试卷

(课程代码02331)

本试卷共8页。满分l00分。考试时间l50分钟。考生答题注意事项：

1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸. 2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。3．第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。

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

第一部分选择题

一、单项选择题(本大题共l5小题，每小题2分，共30分)

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”

的相应代码涂黑。未涂、错涂或多涂均无分。1．下列选项中，不属于线性结构的是

A．网 B．栈 C．队列D．线性表

2．长度为n的顺序表，删除位置i上的元素

(0≤i≤n一1)，需要移动的元素个数为

A．n—i B．n—i—l C．i D．i+1

3．栈采用不同的存储方式时，下列关于出栈过

程的叙述中，正确的是

A．顺序栈需要判定栈空，链栈也需要判定

B．顺序栈需要判定栈空，而链栈不需要判定

C．顺序栈不需要判定栈空，而链栈需要判定

D．顺序栈不需要判定栈空，链栈也不需要判

定

4．若一个栈以数组V[0．．n-1]存储，初始栈顶

指针top为n，则x入栈的正确操作是

A．top=top+1；V[top]=x B．V[top]=x；top=top+1

C．top=top一1；V[mp]=x D．V[top]=x；top=top—l

5．在二维数组a[9][10]中：每个数组元素占用

3个存储空间，从首地址SA开始按行优先

连续存放，则元素a[8][5]的起始地址是

A．SA+141 B．SA+144 C．SA+222 D．SA+255

6．广义表A=(x，((y)，((a))，A))的深度是

A．2 B．3 C．4 D．∞

7．一棵左子树为空的二叉树在前序线索化后，

其空指针域个数为

A．0 B．1 C．2 D．不确定

8．下列关于哈夫曼树的叙述中，错误的是

A．用n个结点构造的哈夫曼树是唯一的

B．哈夫曼树中只有度为0或度为2的结点

C．树中两个权值最小的结点可能是兄弟结点

D．同一结点集构造的二叉树中，哈夫曼树的

WPL最小

9．6个顶点的强连通图中，含有的边数至少是

A．4 B．5 C．6 D．7

10．对题l0图进行深度优先搜索遍历，下列选

项中，正确的遍历序列是

12．有向图采用邻接矩阵存储，某一行中非零元素的个数等于

A．对应顶点v的度

B．对应顶点v的出度

C．对应顶点v的入度

D．依附于对应顶点v的边数

13．下列选项中，符合堆定义的是

A．{102，24，55，60，89，93}

B．{24，89，55，60，93，102}

C．{102，93，55，60，89，24}

D．{102，60。89，93，55，24}

14．已知关键字序列为{66，82，25，51，98，108}，利用快速排序方法，以第一个元素为基准得到的一趟排序结果为

A．{25，51，66，82，98，108}

B．{25，51，66，98，82，108}

C．{51，25，66，108，98，82}

D．{51，25，66，82，98，108}

15．下列选项中，其平均查找性能与基于二叉排序树的查找相当的是

A．二分查找 B．顺序查找 C．分块查找 D．索引顺序查找

第二部分非选择题

二、填空题 (本大题共l0小题，每小题2分，共20分)

请在答题卡上作答。

16．线性表(a

1，a

2

，…，a

n

)中，除_______外，

每个元素都有唯一的直接前趋。

17．指针P指向单链表中某个结点，在P所指结点后插入指针s所指的结点，正确的操作序列是_______。

18．设Push，、Pop分别表示人栈和出栈操作，x=10，y=20，z=30。依次进行下列操作：

Push(y)、Push(z)、Push(z)、X=Pop()、Y=Pop()，x,y的值分别是_______。

19．广义表L=(a，(b，e，(e，f，g，h)))，head(L)= _______。

20．设树T的度为3，其中度为1、2和3的结点个数分别为3、2和1，则T中叶子结点的个数为_______。

21．由一棵二叉树的后序遍历序列和_______遍历序列能够唯一确定该二叉树。

22．在有n个顶点的无向图中，任一顶点的度不大于_______。

23．借助于一个栈来实现的图的遍历算法是_______。

24. 若有向图中存在拓扑排序序列，则该图一定不存在_______。

25．已知关键字序列为{66，82，25，51，98，108}，一趟二路归并排序的结果为

_______。

三、简答题(本大题共4小题，每小题5分。共20分)

请在答题卡上作答。

26．已知n阶对称矩阵A的元素为a

i,j

(0≤i，j≤n 一1)，采用“按行优先”将下三角部分的元素(含主对角线)保存在一维数组sa中，且约定元

素a

0,0保存在sa[0]中，元素a

i,j

(≤i，j≤n-1)

保存在sa[k]中，请给出由下标i，j计算下标k 的计算公式。

27.己知二又树T如题27图所示。

请问答下列问题：

(1)画出该二叉树对应的森林。

(2)写出对森林进行前序遍历的遍历序列i 28．题28图所示为一棵含2个关键字的3阶B 树T。现将关键字序列{40，60，70，20，10}依次插入到T中，画出每插入一个关键字后得到的树型。

29．给定无向带权连通图G如题29图所示，从开始，使用普里姆(Prim)算法，求G

顶点v

的最小生成树T。请回答下列问题。

(1)画出最小生成树T。

(2)计算T中各边权值之和。

四、算法阅读题(本大题共4小题，每小题5分，共20分)

请在答题卡上作答。

30．请写出下列程序段的输出结果。

31．己知存储稀疏矩阵三元组表的类型定义如下：

32．已知二叉树的二叉链表类型定义如下：

为完成指定功能，请在空白处填写适当内容，使其功能完整。

33．函数f33的参数t指向题33图所示的二叉排序树的根，阅读程序，回答下列问题。

(1)若连续3次调用函数f33，参数K的值依次取10、25、10，写出每次调用后函数的输出结果；

(2)说明函数f33的功能。

五、算法设计题(本大题共l小题。共l0分)

请在答题卡上作答。

34．已知顺序表SeqList定义如下：

typedef struct{

KeyType key；

InfoType otherinf0；

}RecType：

typedef RecType SeqList[MAXSIZE+1]；

编写函数，用冒泡排序法将n个元素的待排序列R按关键字降序排序。函数原型为：

int f34(SeqList R，int n)。

自考《数据结构》真题和答案

2016年10月高等教育自学考试全国统一命题考试 数据结构试卷 (课程代码02331) 本试卷共7页，满分l00分，考试时间l50分钟。 考生答题注意事项： 1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。3．第二部分为非选择题。毖须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。4．合理安排答题空间，超出答题区域无效。 第一部分选择题(共30分) 一、单项选择题(本大题共l5小题，每小题2分，共30分> 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题 卡”的相应代码涂黑。错涂、多涂或未涂均无分。 1．下列选项中，不属于线性结构特征的是 A．数据元素之间存在线性关系 B．结构中只有一个开始结点 C．结构中只有一个终端结点 D．每个结点都仅有一个直接前趋 2．设l7个元素的顺序表中，若将第个元素e移动到第个位置，

不改变除e外其他元素之间的相对次序，则需移动的表中元素个数是 3．若用一个大小为7的数组作为循环队列的存储结构，且当前rew和盘0nt的值分别 为2和4，在此之前的操作是从队列中删除了一个元素及加入两个元素，请问这3 个操作之前rear和矗0nt的值分别是 A．0和l B．0和3 C．3和6 D．4和5 4．已知广义表LS=(((a))，((b，(c))，(d，(e，f)))，0)，LS的长度是 A．2 B．3 C．4 D. 5 5．一棵完全二叉树T的全部k个叶结点都在同一层中且每个分支结点都有两个孩子结点。于中包含的结点数是 A．k B. 2k-1 C．k2 D．2k-1 6．如果某二叉树的前序遍历序列为abced，中序遍历序列为cebda，则该二叉树的后序 遍历序列是 A．cedba B．decba C．ecdba D．ecbad 7．一个森林有m棵树，顶点总数为n，则森林中含有的总边数是 A．m B. n-l C．n-m D．n+m 8．设图的邻接矩阵A如下所示。各顶点的度依次是

数据结构-数据结构历年考题及答案2

中国矿业大学2011-2012学年 《数据结构》试卷（A卷）（考试时间：100分钟） 一. 填空（每空2分，共40分） 1. 数据结构式具有相同性质的数据元素的（1）。 2. 通常程序在调用另一个程序时，都需要使用一个（2）来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。 3. 有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）为1000，在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为__（3）_____,_____(4)____。 4. 完全二叉树第4 个节点的父节点是第 (5) 节点，左孩子是第 (6) 个节点。如果该二叉树有10层，则共有 (7) 个节点。 5. 请描述在循环队列Q中，队头和队尾指针分别由front和rear表示，该队列有10个存储空间，判断队空和队满的条件分别分：_____(8)________,_______(9)_________。 6. 字符串t=”child”，s=”cake”，请写出下列函数的结果：StrLength(t) =（10）__;Concat(SubString(s,3,1)，SubString(t,2,2))=____（11）___。 7. 一棵二叉树为 则后序序列为（12），中序序列为（13），先序序列为__（14）____。 8. 请用数据序列{53，17，12，66，58，70，87，25，56，60 }构造一棵二叉排序树_(15）_。 9.。一个栈输入的序列式1,2,3，则可能的且以2为开头的输出序列是 (16) ，不可能的序列是____（17）____。 10. 有n个结点的无向完全图的边数分别为_______(18)_______。 11. 要从数据：2，3，4，8，9，11，13查找11，若采用折半查找法，则在（19）次比较后，才找到该数据。 12. 在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下（20）_____最快。 二简答题： 1给定{15,3,14,2,6,9,16,17}，试为这8个数设计哈夫曼编码，并计算其带权路径长度。 2请对下图的无向带权图按克鲁斯卡尔算法求其最小生成树。（要求使用图画出每一步过程）。 C G E D F B H A

02331数据结构200710

2007年10月高等教育自学考试全国统一命题考试 数据结构试卷 (课程代码2331) 本试卷共12页，满分100分；考试时间150分钟。 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下面程序段的时间复杂度为 A．O(1) B．O(log n) C．O(n) D．O(n2) 2．已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在8所指结点之后插入上述链表应执行的语句为【】 3．在计算机内实现递归算法时所需的辅助数据结构是【】 A．栈B．队列 C．树D．图 4．假设以数组A[m]存放循环A[m]的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置。则队头元素所在的存储位置为【】 5．通常将链串的结点大小设置为大于l是为了【】 A．提高串匹配效率B．提高存储密度 C．便于插入操作D．便于删除操作 6．带行表的三元组表是稀疏矩阵的一种【】 A．顺序存储结构B．链式存储结构 C．索引存储结构D．散列存储结构 7．表头和表尾均为空表的广义表是【】 A．( ) B．( ( ) ) C．( ( ( ) ) ) D．( ( )，( ) ) 8．用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为【】A．n-1 B．n C．n+l D．2n 9．为便于判别有向图中是否存在回路，可借助于【】

A．广度优先搜索算法B．最小生成树算法 C．最短路径算法D．拓扑排序算法 10．连通网的最小生成树是其所有生成树中【】 A．顶点集最小的生成树B．边集最小的生成树 C．顶点权值之和最小的生成树D．边的权值之和最小的生成树 11．按排序过程中依据的原则分类，快速排序属于【】 A．插入类的排序方法B．选择类的排序方法 C．交换类的排序方法D．归并类的排序方法 12．下列关键字序列中。构成小根堆的是【】 A．{84，46，62，41，28，58，15，37} B．{84，62，58，46，4l，37，28，15} C．{15，28，46，37，84，41，58，62} D．{15，28，46，37，84，58，62，41} 13．在长度为32的有序表中进行二分查找时，所需进行的关键字比较次数最多为【】A．4 B．5 C．6 D．7 14．假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为【】 A．n-1 B．n C．n+l D．n+2 15．散列文件也称为【】 A．顺序文件B．索引文件 C．直接存取文件D．间接存取文件 二、填空题(本大题共10小题，每小题2分，共20分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16．数据的逻辑结构描述数据元素之间的________________________，与存储方式无关。17．在一个长度为100的顺序表中删除第10个元素时，需移动________________________个元素。 18．队列的队尾位置通常是随着________________________操作而变化的。 19．两个空串联接得到的串的长度为________________________。 20．设对称矩阵A压缩存储在一维数组B中，其中矩阵的第一个元素a11存储在B[0]，元素a52存储在B[11]，则矩阵元素a36存储在B[________________________]中。 21．已知一棵哈夫曼树含有60个叶子结点，则该树中共有________________________个非叶子结点。 22．如图所示的有向图中含有________________________个强连通分量。 23．已知一组关键字为{15，36，28，97，24，78，47，52，13，86}，其中每相邻两个关键字构成一个有序子序列。对这些子序列进行一趟两两归并的结果是

计算机专业基础综合数据结构(栈和队列)历年真题试卷汇编6

计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编6 (总分：60.00，做题时间：90分钟) 一、单项选择题(总题数：14，分数：28.00) 1.为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( )。【2009年 全国试题1(2)分】 A.栈 B.队列√ C.树 D.图 2.设栈S和队列Q的初始状态均为空，元素a，b，c，d,e,j,g=g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b，d，c，f，e，a，g，则栈S的容量至少是( )。【2009年全国试题2(2)分】 A.1 B.2 C.3 √ D.4 按元素出队顺序计算栈的容量。b进栈时栈中有a，b出栈，cd进栈，栈中有acd，dc出栈，ef进栈，栈 中有aef,fea出栈，栈空，g进栈后出栈。所以栈S的容量至少是3。 3.若元素a，b，c，d,e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是( )。【2010年全国试题1(2)分】 A.d,c，e，b，f,a B.c，b，d,a，e，f C.b，c，a，e，f，d D.a,f，e,d,c，b √ 4.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a，b，c，d，e依次入此队列后再进行出队操作，则不可能得到的出队序列是( )。【2010年全国试题2(2)分】 A.b，a，c，d, e B.d,b，a，c，e C.d，b,c，a，e √ D.e，c，b，a，d a先入队，b和c可在a的任一端入队，选项A、B、D都符合要求，只有选项C不可能出现。双端队列出队结果的分析可参见四、36。 5.元素a，b，c，d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是( )。【2011年全国试题2(2)分】 A.3 B.4 √ C.5 D.6 元素d进栈时，元素a，b，c已在栈中，d出栈后，P可以在a，b，c任一元素的前面进栈并出栈，也可以在元素a后出栈，c，b，a必须依次出栈，所以元素d开头的序列个数是4。 6.已知循环队列存储在一维数组A[0．n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是( )。[2011年全国试题3(2)分】 A.0，0 B.0，n—1 √ C.n一1，0

02331数据结构课后练习题

第1章概论 练习题 一、单项选择题 1．在数据结构中，从逻辑上可以把数据结构分为（B）A．紧凑结构和非紧凑结构B．线性结构和非线性结构 C．内部结构和外部结构D．动态结构和静态结构2．若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为（D）A．顺序存储结构B．链式存储结构 C．索引存储结构D．散列存储结构 3．算法分析的两个主要方面是（B）A．正确性和简明性B．时间复杂性和空间复杂性 C．可读性和可维护性D．数据复杂性和程序复杂性4．线性表采用链式存储结构时，要求内存中可用存储单元地址（A）A．不一定连续的B．部分地址必须是连续的 C．必须是连续的D．一定是不连续的 5．算法指的是（C）A．计算机程序B．解决问题的计算方法 C．解决问题的有限运算序列D．排序算法 二、填空题 6．数据结构一般包括逻辑结构、存储结构和数据运算三个方面的内容． 7．数据的逻辑结构可分为线性结构、非线性结构两大类． 8．数据的存储结构（物理结构）一般可以用顺序存储结构、链式存储结构、索引存储结构及散列存储结构等四种存储方法表示． 9．在选用求解一个问题的算法时，除了首先考虑算法是“正确的”之外，还主要考虑执行算法所需要的时间、执行算法所需要的存储空间及算法应易于理解、易于编程、易于调试等三点。 10．设有一批数据元素，为了最快地存取某元素，宜用顺序结构存储，为了方便的插入一个元素，宜用链式结构存储． 三、应用题 设n为正整数，利用大“O”记号，写出下列各程序段的时间复杂度． 11．for (i = 1; i <= n; i++){ y = y + 1; for (j = 1; j <= 2 * n; j++) x = x + 1; } 分析：语句“y = y + 1;”执行n次，语句“x = x + 1;”各执行2 2n次，故该程序段的时间复杂度为O(2n)．12．s = 0; while (n >= (s + 1) * (s + 1)) s = s + 1; 分析：语句“s = s + 1;．

计算机专业基础综合数据结构(树和二叉树)历年真题试卷汇编6

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 6 (总分：88.00，做题时间：90分钟) 一、单项选择题(总题数：33，分数：66.00) 1.一棵完全二叉树又是一棵( )。【华中科技大学2006一、7(2分)】 A.平衡二叉树 B.堆√ C.二叉排序树 D.哈夫曼(Huffman)树 完全二叉树的叶子至多在下面两层上，且一个结点若无左子树，绝不能有右子树。平衡二叉树任何结点的左右子树的高度差的绝对值不超过1，但其结点的值符合二叉排序树的定义。平衡二叉树(包括二叉排序树)的树形不一定是完全二叉树。堆是一个序列，有大堆和小堆，编号为i的结点，其父结点、左右子女结点之间位置的关系，符合完全二叉树父结点、左右子女结点之间的关系，从这点上说，可以把堆看成完全二叉树。哈夫曼树是二叉树，但树形不一定满足完全二叉树的定义。 2.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是( )。【合肥工业大学1999一、5(2分)】 A.不确定 B.0 C.1 D.2 √ 左子树为空的二叉树的根结点的左线索为空(无前驱)，先序序列的最后结点的右线索为空(无后继)，共2个空链域。 3.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( )。【合肥工业大学2000一、5(2分)】 A.0 B.1 √ C.2 D.不确定 4.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为( )。【南京理工大学1996 一、6(2分)】 A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点√ D.X的左子树中最右叶结点 5.引入二叉线索树的目的是( )。【南京理工大学1998一、5(2分)】 A.加快查找结点的前驱或后继的速度√ B.为了能在二叉树中方便地进行插入与删除 C.为了能方便地找到双亲 D.使二叉树的遍历结果唯一 6.线素二叉树是一种( )结构。【西安电子科技大学1996一、9(2分)】 A.逻辑 B.逻辑和存储 C.物理√ D.线性 7.甩个结点的线索二叉树上含有的线索数为( )。【中山大学1998二、8(2分)】

全国2012年10月自考数据结构(02331)试题及答案

全国2012年10月高等教育自学考试 数据结构试题 课程代码：02331 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共l5小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题 纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1．一个算法的时间耗费的数量级称为该算法的 A．效率B．难度 C．可实现性D．时间复杂度 2．顺序表便于 A．插入结点B．删除结点 C．按值查找结点D．按序号查找结点 3．设带头结点的单循环链表的头指针为head，指针变量P指向尾结点的条件是 A．p->next->next==head B．p->next==head C．p->next->next==NULL D．p->next==NULL 4．设以数组A[0..m-1]存放循环队列，front指向队头元素，rear指向队尾元素的下一个位置，则当前队列中的元素个数为 A．(rear-front+m)％m B．rear-front+1 C．(front-rear+m)％m D．(rear-front)％m 5．下列关于顺序栈的叙述中，正确的是 A．入栈操作需要判断栈满，出栈操作需要判断栈空 B．入栈操作不需要判断栈满，出栈操作需要判断栈空 C．入栈操作需要判断栈满，出栈操作不需要判断栈空

数据结构历年真题收集第1章 绪论(含答案)

第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】4．一个算法应该是（）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1]

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

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

计算机专业基础综合数据结构(概论)历年真题试卷汇编3

计算机专业基础综合数据结构（概论）历年真题试卷汇编3 (总分：70.00，做题时间：90分钟) 一、单项选择题(总题数：15，分数：30.00) 1.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。【2011年全国硕士研究生入学计算机学科专业基础综合试题】简称【201 1年全国试题1(2分)】 x=2； while(x *x； （分数：2.00） A.O(log 2 n) √ B.O(n) C.O(nlog 2 n) D.O(n 2 ) 解析： 2.求整数n(n≥0)阶乘的算法如下，其时间复杂度是( )。【2012年全国试题1(2分)】int fact(int n){if(n<=i) return i；return n*fact(n一1)； （分数：2.00） A.O(log 2 n) B.O(n) √ C.O(nlog 2 n) D.O(n 2 ) 解析： 3.已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是( )。【2013年全国试题1(2)分】 （分数：2.00） A.O(n) B.O(m×n) C.O(min(m，n)) D.O(max(m，n)) √ 解析： 4.下列程序段的时间复杂度是( )。【2014年全国试题1(2分)】count=0;for(k=1；k<=n；k*=2)for(j=1；j<=n；j++)count++； （分数：2.00） A.O(log 2 n) B.O(n) C.O(nlog 2 n) √ D.O(n 2 ) 解析： 5.在数据结构中，数据的最小单位是( )。【北京理工大学2006九、1(1分)】 （分数：2.00） A.数据元素 B.字节 C.数据项√ D.结点 解析： 6.在数据结构中，数据的基本单位是( )。【北京理工大学2004五、1(1分)】 （分数：2.00） A.数据项 B.数据类型 C.数据元素√

02331数据结构2014年4 月份历年真题附答案

全国2014年4月高等教育自学考试 数据结构试题 课程代码：02331 本试卷满分100分，考试时间150分钟. 考生答题注意事项： 1.本卷所有试题必须在答题卡上作答。答在试卷上无效。试卷空白处和背面均可作草稿纸。 2.第一部分为选择题。必须对应试卷上的题号使用28铅笔将“答题卡”的相应代码涂黑。 3.第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。 4.合理安排答题空间。超出答题区域无效。 第一部分选择题 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1.与数据存储结构无关 ．．的概念是 A.栈 B.链表 C.顺序表 D.二叉链表 2.顺序表中有10个数据元素，若第一个元素的存储地址是1000，则最后一个元素地址是1036，第5个元素的地址是 A．1010 B.1016 C.1018 D.1019 3.设栈的初始状态为空，元素1、2、3、4、5、6依次入栈，得到的出栈序列是（2,4,3,6,5,1）,则栈的容量至少是 A.2 B.3 C.4 D..6 4.下列关于队列的叙述中,错误 ．．的是 A.队列是一种先进先出的线性表 B.队列是一种后进后出的线性表 C.循环队列中进行出队操作时要判断队列是否为空 D.在链队列中进行入队操作时要判断队列是否为满 5.对稀疏矩阵进行压缩存储的目的是 A.便于运算 B.节省存储空间 C.便于输入输出 D.降低时间复杂度 6.一棵二叉树的第7层上最多含有的结点数为 A.14 B.64 C.127 D.128 7.下列选项为完全二叉树的是

计算机考研数据结构统考历年真题

目前刚整理了2009-2015的试题过几天2016的也会上传上去 希望对你有帮助。。。。。。。 2009 1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是 A.栈 B.队列 C.树 D.图 2.设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是 A．1 B.2 C.3 D.4 3.给定二叉树图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是 A．LRN B.NRL C.RLN D.RNL 4.下列二叉排序树中，满足平衡二叉树定义的是 5.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是 A．39 B.52 C.111 D.119 6.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的

父结点，则在原来的森林中，u和v可能具有的关系是I．父子关系 II.兄弟关系 III.u的父结点与v的父结点是兄弟关系 A.只有II B.I和II C.I和III D.I、II和III 7.下列关于无向连通图特性的叙述中，正确的是 I．所有顶点的度之和为偶数 II.边数大于顶点个数减1 III.至少有一个顶点的度为1 A.只有I B.只有II C.I和II D.I和III 8.下列叙述中，不符合m阶B树定义要求的是 A．根节点最多有m棵子树 B.所有叶结点都在同一层上 C．各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接 9.已知关键序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后得到的小根堆是 A．3，5，12，8，28，20，15，22，19 B.3，5，12，19，20，15，22，8，28 C．3，8，12，5，20，15，22，28，19 D.3，12，5，8，28，20，15，22，19 10.若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是 A．起泡排序 B.插入排序 C.选择排序 D.二路归并排序 41.（10分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：

计算机专业基础综合数据结构(图)历年真题试卷汇编3

计算机专业基础综合数据结构（图）历年真题试卷汇编3 (总分：58.00，做题时间：90分钟) 一、综合题(总题数：23，分数：58.00) 1.给出从顶点v1开始，对图G用深度优先搜索法进行遍历时的顶点序列；(2)给出从顶v1，1开始，对图G用广度优先搜索法进行遍历时的顶点序列。【复旦大学1998六(10分)】 __________________________________________________________________________________________ 正确答案：(正确答案：(1)v 1 v 2 v 4 v 3 v 5 v 6 (2) v 1 v 2 v 3 v 4 v 5 v 6) 给出图G 4.00） (1).画出G的邻接表表示图； __________________________________________________________________________________________ 正确答案：( (2).根据你画出的邻接表，以顶点①为根，画出G的深度优先生成树和广度优先生成树。【南开大学1997五(14分)】【烟台大学2007四、3(15分)】 __________________________________________________________________________________________ 正确答案：( 2.已知一个有向图如图所示，则从顶点a出发进行深度优先遍历，写出所有可能得到的DFS 京交通大学2006四、4(5分)】 __________________________________________________________________________________________ 正确答案：(正确答案：共8个：adbcfe，adbfce，adcbfe，adcebf adcefb，adebcj,adebfc，adefbc) 2000计算机应用六(10分)】（分数：4.00） (1).如果每个指针需要4字节，每个顶点的标号占2字节，每条边的权值占2字节。下图采用哪种表示法所需的空间较多?为什么? __________________________________________________________________________________________ 正确答案：(正确答案：邻接矩阵：(6*6个元素)*2字节／元素=72字节邻接表：表头向量6*(4+2)+边结点9*(2+2+4)*2=180字节邻接多重表：表头向量6*(4+2)+边结点9*(2+2+2+4+4)=162字节邻接表占用空间较多，因为边较多，边结点又是边数的2倍，一般来说，邻接矩阵所占空间与边个数无关(不考虑压缩存储)，适合存储稠密图，而邻接表适合存储稀疏图。邻接多重表边结点个数等于边数，但结点中增加了一个顶点下标域和一个指针域。) (2).写出下图从顶点1开始的：DFS树。 __________________________________________________________________________________________ 正确答案：(正确答案：因未确定存储结构，从顶点1开始的DFS 3.如下所示的连通图，请画出：(1)以顶点①为根的深度优先生成树；(5分)(2)如果有关节顶点，请找出 所有的关节顶点。(5分)【清华大学l 998七(10分)】 __________________________________________________________________________________________ 正确答案：(正确答案：(1)未确定存储结构，其DFS树不唯一，其中之一(按邻接点逆序排列) 关节顶点有3，1，8，7，2。)

全国2014年4月自考数据结构真题

绝密★考试结束前 全国2014年4月高等教育自学考试 数据结构试题 课程代码：02331 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1.答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2.每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸” 的相应代码涂黑。错涂、多涂或未涂均无分。 1.与数据存储结构无关 ．．的概念是 A.栈 B.链表 C.顺序表 D.二叉链表 2.顺序表中有10个数据元素，若第一个元素的存储地址是1000，则最后一个元素地址是1036，第5个元素的地址是 A．1010 B.1016 C.1018 D.1019 3.设栈的初始状态为空，元素1、2、3、4、5、6依次入栈，得到的出栈序列是（2,4,3,6,5,1）,则栈的容量至少是 A.2 B.3 C.4 D..6 4.下列关于队列的叙述中,错误 ．．的是 A.队列是一种先进先出的线性表 B.队列是一种后进后出的线性表 C.循环队列中进行出队操作时要判断队列是否为空 1

D.在链队列中进行入队操作时要判断队列是否为满 5.对稀疏矩阵进行压缩存储的目的是 A.便于运算 B.节省存储空间 C.便于输入输出 D.降低时间复杂度 6.一棵二叉树的第7层上最多含有的结点数为 A.14 B.64 C.127 D.128 7.下列选项为完全二叉树的是 8.用邻接表表示n个顶点e条边的无向图,其边表结点的总数是 A. n×e B. e C. 2e D. n+e 9.无向图中所有顶点的度数之和与所有边数之比是 A.1/2 B.1 C.2 D.4 10.采用邻接矩阵存储图时,广度优先搜索遍历算法的时间复杂度为 A. O（n） B. O（n+e） C. O（n2） D. O（n3） 11.对序列（15,9,7,8,20,-1,4）进行排序,若一趟排序后的结果为（-1,15,9,7,8,20,4）,则采用的排序方法是 A.归并排序 B.快速排序 C.直接选择排序 D.冒泡排序 12.比较次数与待排序列初始状态无关的排序方法是 A.快速排序 B.冒泡排序 C.直接插入排序 D.直接选择排序 13.查找较快,且插入和删除操作也比较方便的查找方法是 A.分块查找 B.二分查找 C.顺序查找 D.折半查找 14.下列关于m阶B树的叙述中,错误 ．．的是 2

全国硕士研究生入学统一考试计算机科学与技术学科联考数据结构考点归纳与典型题(含历年真题)详解-第一章

第1章绪论 1.1考点归纳 【考纲指定考点】 本章初步了解数据结构的基本概念。分析算法的时间复杂度和空间复杂度是本章的重点。 一、数据结构的基本概念 1．基础概念和术语 （1）数据（Data）：数据是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。 （2）数据元素（Data Element）：数据元素是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。 （3）数据项（Data Item）：数据项是数据的不可分割的最小单位，数据项是对客观事物的某一方面的数据描述。一个数据元素可由若干个数据项（Data Item）组成。 （4）数据对象（Data Object）：数据对象是性质相同的数据元素的集合，是数据的一个子集。如字符集合C＝{‘A’，‘B’，‘C’，…}。 （5）数据结构（Data Structure）：数据结构是指相互之间存在一定联系（关系）的数据元素的集合。元素之间的相互联系（关系）称为逻辑结构。 2．数据结构的形式定义

数据结构的形式定义是一个二元组： Data Structure＝（D，S） 其中D是数据元素的有限集，S是D上关系的有限集。 数据元素之间的关系可以是元素之间本身代表的某种自然关系，也可以是为了处理问题方便而人为定义的关系，这种自然或人为定义的关系称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。 3．数据结构的组成 数据结构的三个组成部分： （1）逻辑结构 数据元素之间的逻辑关系的描述。数据元素之间的逻辑结构有四种基本类型： ①集合：结构中的数据除了“同属于一个集合”外，没有其它关系。 ②线性结构：结构中的数据元素之间存在一对一的关系。 ③树形结构：结构中的数据元素之间存在一对多的关系。 ④图形结构或网状结构：结构中的数据元素之间存在多对多的关系。 （2）存储结构 数据结构在计算机中的实际表达方式，它包括对数据元素的表示和对关系的表示。存储结构主要有：顺序存储、链式存储、索引存储和散列存储。 ①顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构。数据元素存放的地址是连续的。其优点是可以实现随机存取，存储空间小；缺点是只能使用相邻的一整块存储单元，容易产生碎片。 ②链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针，用该指针

02331数据结构 全国13年10月自考 试题

全国2013年10月高等教育自学考试 数据结构试题 课程代码：02331 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1．算法的时间复杂度表征的是 A．算法的可读性B．算法的难易程度 C．执行算法所耗费的时间D．执行算法所耗费的存储空间 2．对需要频繁插入和删除结点的线性表，适合的存储方式是 A．顺序储存B．链式存储 C．索引存储D．散列存储 3．在头指针为head的循环链表中，判断指针变量P指向尾结点的条件是 A．p->next->next==head B．p->next==head C．p->next->next==NULL D．p->next==NULL 4．迪杰斯特拉(Dijkstra)算法的功能是 A．求图中某顶点到其他顶点的最短路径B．求图中所有顶点之间的最短路径 C．求图的最小生成树D．求图的拓扑排序序列 5．若栈的进栈序列为1，2，3，4，5，则经过出入栈操作不可能 ．．．获得的出栈序列是A．4，5，3，2，1 B．4，3，5，1，2 C．1，2，3，4，5 D．5，4，3，2，1 6．A是7×4的二维数组，按行优先方式顺序存储，元素A[0][0]的存储地址为1 000，若每个元素占2个字节，则元素A[3][3]的存储地址为 A．1015 B．1016 C．1028 D．1030 7．深度为4的完全二叉树的结点数至少为 A．4 B．8 C．13 D．15 8．若采用邻接矩阵A存储有向图G，则结点k的入度等于A中 A．结点k对应行元素之和B．结点k对应列元素之和 C．结点k对应行和列元素之和D．非零元素之和 9．无向图G的邻接矩阵一定是 A．对称矩阵B．对角矩阵

数据结构历年试题及答案

一、单项选择题 1．算法指的是（ D ） D ．解决问题的有限运算序列 2．线性表采用链式存储时，结点的存储地址（ B ）B ．连续与否均可 3．将长度为n 的单链表链接在长度为m 的单链表之后的算法的时间复杂度为（ C ） A ．O （1） B ．O （n ） C ．O （m ） D ．O （m+n ） 4．由两个栈共享一个向量空间的好处是：（ B ） B ．节省存储空间，降低上溢发生的机率 5．设数组data[m]作为循环队列SQ 的存储空间，front 为队头指针，rear 为队尾指针，则执 行出队操作后其头指针front 值为（ D ） D ．front=(front+1)%m 6．如下陈述中正确的是（ A ） A ．串是一种特殊的线性表 7．若目标串的长度为n ，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的 时间复杂度是（ C ） C ．O （n 2） 8．一个非空广义表的表头（ D ） D ．可以是子表或原子 9 对应的稀疏矩阵是（ A ） ????????????? ???--0000040 5000000076080.A 10．在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个 数为( C ) C ．6 11．在含n 个顶点和e 条边的无向图的邻接矩阵中,零元素的个数为( D ) D ．n 2－2e 12．假设一个有n 个顶点和e 条弧的有向图用邻接表表示,则删除与某个顶点v i 相关的所有 弧的时间复杂度是( C ) C ．O(n+e) 13．用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时， 序列的变化情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（ D ） D ．快速排序 14．适于对动态查找表进行高效率查找的组织结构是（ C ） C ．三叉排序树 15．不定长文件是指（B ） B ．记录的长度不固定 二、填空题 16．数据的逻辑结构是从逻辑关系上描述数据，它与数据的 存储（存储结构） 无关，是独立于计算机的。 17．在一个带头结点的单循环链表中，p 指向尾结点的直接前驱，则指向头结点的指针head 可用p 表示为head= p->next->next 。 18．栈顶的位置是随着 进栈和退栈 操作而变化的。 19．在串S=“structure ”中，以t 为首字符的子串有 12 个。