全国2023年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所指结点的后继结点的正确操作是( )
next >next=p->next >next=p->next->next >next=p
5.栈和队列( )
a.共同之处在于二者都是先进先出的特殊的线性表
b.共同之处在于二者都是先进后出的特殊的线性表。
c.共同之处在于二者都只允许在顶端执行删除操作 d.没有共同之处。
6.二维数组a［5］［6］采用按列为主序的存储方式，每个元素占3个存储单元，若a［0］［0］的存储地址是100，则a［4］［3］的存储地址是( )a.127 b.
142 c.150 d.157
7．深度为k的二叉树最多有（）个结点。
8.对于如图所示二叉树采用中根遍历，正确的遍历序列应为( )
题8图题10图。
9.下面关于生成树的描述中，不正确的是( )
a.生成树是树的一种表现形式 b.生成树一定是连通的 c.生成树一定不含有环
d.若生成树顶点个数为n，则其边数一定为n-1
10.图的邻接表如下所示，从顶点v1出发采用深度优先搜索法遍历该图，则可能的顶点序列是( )
a v1v2v3v4v5 b v1v2v3v5v4 c v1v4v3v5v2 d v1v3v4v5v2
11.下列查找方法中，不属于动态的查找方法是( )
a.二叉排序树法b.平衡树法 c.散列法 d.斐波那契查找法。
12.要解决散列引起的冲突问题，常采用的方法有( )
a.数字分析法、平方取中法 b.数字分析法、线性探测法。
c.二次探测法、平方取中法 d.二次探测法、链地址法。
13.用于外存储器的数据组织结构散列文件，主要适用于( )
a.顺序存取 b.随机存取 c.索引存取d.以上三种都可以。
14.堆排序属于一种选择排序，其时间复杂性为( )
15.下列排序方法中，属于不稳定的排序方法是( )
a.直接插入排序法 b.冒泡排序法 c.基数排序法d.归并排序法。
二、填空题(本大题共13小题，每小题2分，共26分)
16.根据不同的描述方式，对数据的操作运算通常可分为加工型运算和___两种基本类型。
17.数据结构中的算法，通常采用最坏时间复杂度和___两种方法衡量其效率。
18.判断带头结点head的单链表为空的条件是。
19.若顺序表每个元素长度均为5，其中第一个元素的存储地址为30，则第6个元素的存储地址为___
20.若front和rear分别表示循环队列q的头指针和尾指针，m0表示该队列的最大容量，则判断循环队列为满的条件是___
21.对于顺序存储结构的二维数组，通常采用两种存放方式存储数据元素。
22.若某二叉树的先根遍历序列为cedba，中根遍历序列为debac，则其后根遍历序列为___
23.具有n个结点的完全二叉树，其深度为。
24.图主要采用两种存储结构存放。
25.索引顺序查找通常分两个阶段进行，首先采用顺序查找法或二分法确定所要查找的块，然后再用___法在块中找到具体的元素值。
26.二叉排序树是一种特殊的有序表，若要保证输出序列其键值完全按递增排列，则应对二叉排序树采用___法遍历。
27.文件常见的存储结构有顺序文件、链接文件、 索引文件和___四种。
28.在各种内部排序中，占用存储空间较大的排序通常是排序。
三、应用题(本大题共5小题，每小题6分，共30分)
29．已知某二叉树的顺序存储结构如图所示，试画出该二叉树。
30．试用prim算法构造下图的最小生成树，要求分步给出构造过程。
31.已知散列函数为h(key)=key%7，散列表长度为7(散列地址空间为0..6)，待散列序列为：(25，48，32，50，68)。要求：
1)根据以上条件构造一散列表，并用线性探测法解决有关地址冲突；
2)若要用该散列表查找元素68，给出所需的比较次数。
32.已知一组键值序列为(38，64，73，52，40，37，56，43)，试采用快速排序法对该组序列作升序排序，并给出每一趟的排序结果。
33.已知一组键值序列(26，21，32，56，78，89，90)，试采用二路归并排序法对该组序列作升序排序，并给出每一趟的排序结果。
四、设计题(本大题共2小题，每小题7分，共14分)
34.试编写一算法，以完成在带头结点单链表l中第i个位置前插入元素x的操作。
35.二叉树是由所有度数不大于2的结点构成的一种特定树，若某结点度为2，则该结点有左右两个孩子，请编写算法计算一二叉树所有度数为2的结点个数。
数据结构导论06年01月
全国2006年1月高等教育自学考试数据结构导论试题课程 02142 一 单项选择题 本大题共15小题，每小题2分，共30分 1.数据结构中所定义的数据元素，是用于表示数据的 a.最小单位 b.最大单位 c.基本单位 d.不可分割的单位。2.数据的四种基本存储结构是指 a.顺序存储结构 索引存储结构 ...
数据结构导论
7.不稳定的排序方法是 a.直接插入排序 b.冒泡排序。c.堆排序 d.二路归并排序。8.设散列表表长m 14，散列函数为h k k 11，表中已有4个记录，如果用二次探测法处理冲突，关键字为49的记录的存储位置是 a.3 b.5 c.8 d.9 9.若元素1，2，3依次进栈，则退栈不可能出现的次序...
数据结构导论试题
一 单项选择题。1.若给定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是 二00一年下半年全国高等教育自学考试。数据结构导论试卷。一 单项选择题。1.若给定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是 2.在一个具有n个结点的单链表达中查找值为m的某结点，若查找成功，则...