《数据结构导论》考纲、试题、答案一、考试说明本课程为闭卷考试（开卷考试、上交论文、上交作品等考查类课程无考试指导）（根据课程考核实际方式选择），考试时间90分钟，考试题型包括以下题型中的三种（根据每门课程的实际确定题型及分值所占比例）：1、判断题（正确打√，错误打×，每题3分，共15分）2、填空（每空2分，共20分）3、选择题（每题3分，共15分）4、名词解释（每小题4分，共20分）5、简答题（每题6分，共30分）备注：以上题型供参考二、课程知识要点第一章◆数据结构◆实例第二章◆银行排队顺序存储◆学生健康登记表第三章◆栈和队列◆回文◆杨辉三角第四章◆串◆文本加密第五章◆内部排序◆查找◆二叉树第六章◆树◆图◆数组第七章◆文件◆外部排序备注：根据教材实际章节汇总要点，突出需要掌握的重点内容三、重点习题1、判断题◆具有n 个结点的线索二叉树上，含有n+1个线索。
◆三叉链表属于二叉树存储结构。
◆哈夫曼树不存在度为1的结点。
◆栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
◆栈和队列的存储方式既可是顺序方式，也可是链接方式。
◆二叉树中每个结点的两棵子树是有序的。
2、填空◆数据的逻辑结构指◆一个算法的时间复杂度◆单链表中，增加头结点的目的◆表长为0的线性表◆串的长度◆若两个串的长度相等且对应位置上的字符也相等◆常用的插入排序◆常用的处理冲突的方法◆常用的选择排序方法◆衡量一个算法的优劣主要考虑◆在有n个结点的二叉链表中，空链域的个数◆常用的选择排序方法◆具有10个顶点的无向图，边的总数最多为◆堆排序◆已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有多少个叶子结点◆树有三种常用形式◆深度为5的二叉树至多有多少个结点3、选择题◆串是一种特殊的线性表，其特殊性体现在◆数据的逻辑结构◆算法◆在数据结构中，从逻辑上可以把数据结构分成◆算法分析的目的◆链接存储的存储结构所占存储空间◆链表◆非线性结构是数据元素之间存在一种4、名词解释◆数据◆运算与运算实现的相同点◆串变量◆连通分量◆头指针5、简答题◆数据逻辑结构的特点◆假定一棵二叉树广义表表示为a(b(c,d)),c(((,8))),分别给出先序，中序后序和后序的遍历结果◆假定一组记录的排序码为(46，79，56，38，40，84，50，42)，则利用堆排序方法建立的初始堆为◆从一维数组A[n)中二分查找关键字为K的元素的递归算法，若查找成功则返回对应元素的下标，否则返回一1。
数据结构导论自考题模拟9(总分100, 做题时间90分钟)一、单项选择题在每小题列出的四个备选项中只有一个是符合题目要求的1.关于算法的描述，不正确的是______SSS_SINGLE_SELA 算法最终必须由计算机程序实现B 所谓最坏时间复杂度是指最坏情况下，估算算法执行时间的一个上界C 健壮的算法不会因非法的输入数据而出现莫名其妙的运行结果D 算法的优劣与算法描述语言无关分值: 2答案:A2.线性表若采用链表存储结构，则要求内存中可用存储单元的地址______SSS_SINGLE_SELA 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 连续不连续都可以分值: 2答案:D[考点] 本题主要考查的知识点是线性表。
由于线性表的顺序存储方式要求占用连续的空间，存储分配只能预先进行，为了克服顺序表的缺点，采用链接方式存储线性表。
3.以下属于逻辑结构的是______SSS_SINGLE_SELA 顺序表B 哈希表C 有序表D 单链表分值: 2答案:C[考点] 本题主要考查的知识点是逻辑结构。
只有有序表属于逻辑结构，其他选项都属于存储结构。
本题答案为C。
4.已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为______SSS_SINGLE_SELA 5B 6C 16D 17分值: 2答案:C5.对特殊矩阵采用压缩存储的目的主要是为了______SSS_SINGLE_SELA 表达变得简单B 对矩阵元素的存取变得简单C 去掉矩阵中多余元素D 减少不必要的存储空间分值: 2答案:D6.将一棵有1000个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的分支结点的编号为______SSS_SINGLE_SELA 48B 49C 50D 51分值: 2答案:C[考点] 本题主要考查的知识点是完全二叉树。
浙江省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.对线性表进行二分查找时，要求线性表必须( )。
《数据结构导论》课程考核形式：闭卷考试需用时间：100分钟层次：专科班级：计应专朗沃姓名：学号：1．在数据结构中，与所使用的计算机无关的是（）。
A.存储结构B.物理结构C.物理和存储结构D.逻辑结构2．线性表采用链式存储结构时，其地址是（）。
A.必须是连续的B.一定是不连续的C.部分地址必须是连续的D.连续与否均可以3．在下列链表中不能从当前结点出发访问到其余各结点的是（）。
A.单链表B.单循环链表C.双向链表D.双向循环链表4．设一个栈的进栈序列是 a，b，c，d，进栈的过程中可以出栈，不可能的出栈序列是（）A.d，c，b，aB.c，d，b，aC.d，c，a，bD.a，b，c，d 5．设循环队列中数组的下标是0～N-1，其头尾指针分别为f 和r ，则其元素个数为（）A. r-fB.r-f-1C.(r-f)%N+1D.(r-f+N)%N6．广义表((a),a)的表头和表尾分别是：A. a, ((a))B. (a), (a)C. b, (a)D. ((a)), a 7．对稀疏矩阵采用压缩存储，其缺点之一是（）。
A.无法判断矩阵有多少行和多少列B.无法根据行列号查找某个矩阵元素C.无法根据行列号计算矩阵元素的存储地址D.使矩阵元素之间的逻辑关系更加复杂8．以下说法错误的是（）。
A.一般在哈夫曼树中，权值越大的叶子离根结点越近B.哈夫曼树中没有度数为 1 的分支结点C.若初始森林中共有 n 棵二叉树，最终求得的哈夫曼树中共有 2n-1个结点D.若初始森林中共有 n 棵二叉树，进行 2n-1 次合并后才能剩下最终的哈夫曼树9．任何一个无向连通图（）最小生成树。
A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在10．树最适合用来表示（）：A. 有序数据元素B. 无序数据元素C. 元素之间具有分支层次关系的数据D. 元素之间无联系的数据二、填空题（本大题共9小题，每空2 分，共20分）1．在双向链表中，每个结点包含两个指针域，一个指向__ __结点，另一个指向_ ___结点。
