下载文档原格式
《数据结构》期末考试试题及答案一、单项选择题1. 数据结构是计算机科学的基础学科之一。
下列哪个选项正确描述了数据结构的定义？A. 数据结构是一种计算机程序B. 数据结构是一种存储和组织数据的方法C. 数据结构是一种人工智能技术D. 数据结构是一种操作系统答案：B2. 链表和数组是常见的数据结构，它们之间的主要区别是：A. 数组可以存储不同类型的数据，而链表只能存储相同类型的数据B. 数组的元素在内存中是连续存储的，而链表的元素在内存中是分散存储的C. 链表可以随机访问元素，而数组只能顺序访问元素D. 链表的插入和删除操作更高效，而数组的访问操作更高效答案：B3. 在二叉树中，每个节点最多可以有多少个子节点？A. 1B. 2C. 3D. 无限多个答案：B二、填空题1. 假设有一组数据 [5, 8, 3, 2, 9]，按照从小到大的顺序进行冒泡排序的过程中，经过三次交换后的结果是__2__，__3__，__5__，__8__，__9__。
2. 请完成以下代码，实现栈的入栈和出栈操作：```pythonclass Stack:def __init__(self):self.stack = []def push(self, item):self.stack.append(item)def pop(self):if not self.is_empty():return self.stack.pop()def is_empty(self):# 示例代码s = Stack()s.push(1)s.push(2)s.push(3)print(s.pop()) # 输出 3print(s.pop()) # 输出 2print(s.is_empty()) # 输出 False ```答案：```pythonclass Stack:def __init__(self):self.stack = []def push(self, item):self.stack.append(item)def pop(self):if not self.is_empty():def is_empty(self):return len(self.stack) == 0# 示例代码s = Stack()s.push(1)s.push(2)s.push(3)print(s.pop()) # 输出 3print(s.pop()) # 输出 2print(s.is_empty()) # 输出 False```三、简答题1. 请简要介绍树的基本概念及常见的树结构。
《数据结构与算法》复习题一、选择题。
1．在数据结构中，从逻辑上可以把数据结构分为 C 。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构2．数据结构在计算机内存中的表示是指 A 。
A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。
A．逻辑 B．存储 C．逻辑和存储 D．物理4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。
A．数据的处理方法 B．数据元素的类型C．数据元素之间的关系 D．数据的存储方法5．在决定选取何种存储结构时，一般不考虑 A 。
A．各结点的值如何 B．结点个数的多少C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。
6．以下说法正确的是 D 。
A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。
（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性C．可读性和文档性 D．数据复杂性和程序复杂性8．下面程序段的时间复杂度是 O(n2) 。
s =0;for( I =0; i<n; i++)for(j=0;j<n;j++)s +=B[i][j]; sum = s ;9．下面程序段的时间复杂度是 O(n*m) 。
for( i =0; i<n; i++)for(j=0;j<m;j++)A[i][j] ＝ 0;10．下面程序段的时间复杂度是 O(log3n) 。
i ＝ 0；while（i<=n）i = i * 3；11．在以下的叙述中，正确的是 B 。
数据结构期末考试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，算法的时间复杂度是指（）。
A. 执行算法所需要的计算工作量B. 执行算法所需要的存储空间C. 执行算法所需要的时间D. 执行算法所需要的内存大小答案：A2. 线性表的顺序存储结构和链式存储结构相比，其优点是（）。
A. 插入和删除操作快B. 存储密度高C. 存储空间可以动态分配D. 存储空间利用率高答案：B3. 栈的基本运算中，不包括（）。
A. 入栈B. 出栈C. 取栈顶元素D. 排序答案：D4. 在二叉树的遍历中，先序遍历的顺序是（）。
A. 先根后子B. 先子后根C. 先左后右D. 先右后左答案：A5. 哈希表解决冲突的方法不包括（）。
A. 分离链接法B. 线性探测法C. 链地址法D. 二分查找法答案：D6. 一个图的邻接矩阵表示法中，若第i行第j列的元素为1，则表示（）。
A. 顶点i和顶点j之间有一条边B. 顶点i和顶点j之间没有边C. 顶点i和顶点j之间有n条边D. 顶点i和顶点j之间有m条边答案：A7. 在查找算法中，二分查找法适用于（）。
A. 线性表B. 哈希表C. 树形结构D. 图结构答案：A8. 快速排序算法的时间复杂度在最坏情况下是（）。
A. O(n)B. O(nlogn)C. O(n^2)D. O(2^n)答案：C9. 一个有n个顶点的无向图，其边数最多为（）。
A. nB. n(n-1)/2C. n(n+1)/2D. 2n答案：B10. 以下哪个不是排序算法（）。
A. 冒泡排序B. 选择排序C. 插入排序D. 归并排序答案：D二、填空题（每题2分，共20分）1. 在数据结构中，一个算法的空间复杂度是指算法执行过程中所需要的___________。
答案：存储空间2. 线性表的链式存储结构中，每个节点包含___________和___________。
答案：数据元素，指针3. 栈的特点是___________，___________。
课程测试试题（A 卷）一、 一、 单选题（每题 分，共 分） 对一个算法的评价，不包括如下（ ）方面的内容。
．健壮性和可读性 ．并行性 ．正确性 ．时空复杂度 在带有头结点的单链表 中，要向表头插入一个由指针 指向的结点，则执行 。
对线性表，在下列哪种情况下应当采用链表表示？ 经常需要随机地存取元素 经常需要进行插入和删除操作 表中元素需要占据一片连续的存储空间 表中元素的个数不变 一个栈的输入序列为 ，则下列序列中不可能是栈的输出序列的是 网是一种（ ）。
．有向图 ．无向图 ．无向无环图 ．有向无环图 采用开放定址法处理散列表的冲突时，其平均查找长度（ ）。
．低于链接法处理冲突 高于链接法处理冲突 ．与链接法处理冲突相同 ．高于二分查找 若需要利用形参直接访问实参时，应将形参变量说明为（ ）参数。
．值 ．函数 ．指针 ．引用 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（ ）。
．行号 ．列号 ．元素值 ．非零元素个数 快速排序在最坏情况下的时间复杂度为（ ）。
． ． ． ． 从二叉搜索树中查找一个元素时，其时间复杂度大致为 。
二、 二、 运算题（每题 分，共 分） 数据结构是指数据及其相互之间的 。
当结点之间存在 对 （ ： ）的联系时，称这种结构为 。
队列的插入操作是在队列的 进行，删除操作是在队列的 进行。
当用长度为 的数组顺序存储一个栈时，假定用 表示栈空，则表示栈满的条件是 。
对于一个长度为 的单链存储的线性表，在表头插入元素的时间复杂度为 ，在表尾插入元素的时间复杂度为 。
设 为一个二维数组，其每个数据元素占用 个字节，行下标 从 到 ，列下标 从 到 ，则二维数组 的数据元素共占用＿ ＿个字节。
中第 行的元素和第 列的元素共占用＿ ＿个字节。
若按行顺序存放二维数组 ，其起始地址为 ，则二维数组元素 ， 的起始地址为＿ ＿。
广义表 则它的深度为 ，它的长度为 。
课程测试试题（卷）---------------------- 以下为教师填写 --------------------I、命题院（部）：数学与计算机科学学院II 、课程名称：数据结构III 、测试学期：20－ 20学年度第学期IV 、测试对象：学院专业级班V、问卷页数（A4 ）：页VI 、答卷页数（A4）：页VII 、考试方式：闭卷（开卷、闭卷或课程小论文，请填写清楚）VIII 、问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号）一、一、单选题（每题 2 分，共 20 分）1. 1. 对一个算法的评价，不包括如下（ B ）方面的内容。
A ．健壮性和可读性B．并行性C．正确性D．时空复杂度2. 2. 在带有头结点的单链表 HL 中，要向表头插入一个由指针 p 指向的结点，则执行 ( A )。
A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3. 3. 对线性表，在下列哪种情况下应当采用链表表示？ ( B )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4. 4. 一个栈的输入序列为 1 2 3，则下列序列中不可能是栈的输出序列的是(C )A.231B.321C.312D.1235. 5. AOV 网是一种（ D ）。
A ．有向图B ．无向图C ．无向无环图D ．有向无环图6. 6. 采用开放定址法处理散列表的冲突时，其平均查找长度（B ）。
A ．低于链接法处理冲突 B. 高于链接法处理冲突 C ．与链接法处理冲突相同D ．高于二分查找7. 7. 若需要利用形参直接访问实参时， 应将形参变量说明为 （ D ）参数。
绝密★考试结束前全国2013年10月高等教育自学考试数据结构试题课程代码：02331请考生按规定用笔将所有试题的答案涂、写在答题纸上。
选择题部分注意事项：1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。
2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。
如需改动，用橡皮擦干净后，再选涂其他答案标号。
不能答在试题卷上。
一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。
错涂、多涂或未涂均无分。
1．算法的时间复杂度表征的是A．算法的可读性B．算法的难易程度C．执行算法所耗费的时间D．执行算法所耗费的存储空间2．对需要频繁插入和删除结点的线性表，适合的存储方式是A．顺序储存B．链式存储C．索引存储D．散列存储3．在头指针为head的循环链表中，判断指针变量P指向尾结点的条件是A．p->next->next==head B．p->next==headC．p->next->next==NULL D．p->next==NULL4．迪杰斯特拉(Dijkstra)算法的功能是A．求图中某顶点到其他顶点的最短路径B．求图中所有顶点之间的最短路径C．求图的最小生成树D．求图的拓扑排序序列5．若栈的进栈序列为1，2，3，4，5，则经过出入栈操作不可能．．．获得的出栈序列是A．4，5，3，2，1 B．4，3，5，1，2C．1，2，3，4，5 D．5，4，3，2，16．A是7×4的二维数组，按行优先方式顺序存储，元素A[0][0]的存储地址为1 000，若每个元素占2个字节，则元素A[3][3]的存储地址为A．1015 B．1016C．1028 D．10307．深度为4的完全二叉树的结点数至少为A．4 B．8C．13 D．158．若采用邻接矩阵A存储有向图G，则结点k的入度等于A中A．结点k对应行元素之和B．结点k对应列元素之和C．结点k对应行和列元素之和D．非零元素之和9．无向图G的邻接矩阵一定是A．对称矩阵B．对角矩阵C．三角矩阵D．单位矩阵10．下列关于有向带权图G的叙述中，错误．．的是A．图G的任何一棵生成树都不含有回路B．图G生成树所含的边数等于顶点数减1C．图G含有回路时无法得到拓扑序列D．图G的最小生成树总是唯一的11．在下列排序算法中，关键字比较次数与初始排列次序无关的是A．冒泡排序B．希尔排序C．直接插入排序D．直接选择排序1 2．对下图进行拓扑排序，可以得到的拓扑序列是A．a b c d e B．b a c d eC．b c a d e D．a b d c e13．下列线性表中，能使用二分查找的是A．顺序存储(2,12,5,6,9,3,89,34,25) B．链式存储(2,12,5,6,9,3,89,34,25) C．顺序存储(2,3,5,6,9,12,25,34,89) D．链式存储(2,3,5,6,9,12,25,34,89) 14．在下列查找方法中，平均查找长度与结点数量无直接关系的是A．顺序查找B．分块查找C．散列查找D．基于B树的查找15．下列排序算法中，时间复杂度为O(nlog2 n)的算法是A．快速排序B．冒泡排序C．直接选择排序D．直接插入排序非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。
绪论一、填空题1、数据的逻辑结构是数据元素之间的逻辑关系，通常有下列4类：集合＿、线性结构＿、树型结构＿、图状结构＿。
2、数据的存储结构是数据在计算机存储器里的表示，主要有4种基本存储方法：顺序存储＿、链式存储＿、索引存储＿、散列存储＿。
二、选择题1、一个算法必须在执行有穷步之后结束，这是算法的（B ）。
A、正确性B、有穷性C、确定性D、可行性2、算法的每一步必须有确切的定义，也就是说，对于每步需要执行的动作必须严格、清楚地给出规定，这是算法的（A）。
A、正确性B、有穷性C、确定性D、可行性3、算法原则上都是能够有机器或人所完成的。
整个算法好象是一个解决问题的“工作序列”，其中的每一步都是我们力所能及的一个动作，这是算法的（D）A、正确性B、有穷性C、确定性D、可行性三、简单题1、什么是数据结构？什么是算法？两者有什么关系？什么是数据结构？数据结构是按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。
什么是算法？广义地说,为解决一个问题而采取的方法和步骤,就称为“算法”两者有什么关系？算法与数据结构关系密切。
选择的数据结构是否恰当直接影响算法的效率；而数据结构的优劣由算法的执行来体现。
2、什么是复杂度和空间复杂度？时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。
3、数据的逻辑结构分几种？存储结构又有哪几种？数据的逻辑结构：结构定义中的“关系”，描述的是数据元素之间的逻辑关系；包括线性结构（线性表、栈、队、串、数组）和非线性结构（图形结构、树形结构）；数据的存储结构（物理结构）：数据结构在计算机中的表示（又称映像），包括数据元素的表示和关系德表示。
有顺序存贮（向量存贮）、链式存贮、索引存贮、散列存贮。
线性表1、一个线性表第一个元素的存储地址是100，每个元素的长度为2，则第5 个元素的地址是( B)。
试题一一、单项选择题（每小题2分，共20分）（1）以下数据结构中哪一个是线性结构？（）A）有向图B）队列C）线索二叉树D）B树（2）在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下（）语句序列。
A）p=q; p->next=q; B）p->next=q; q->next=p;C）p->next=q->next; p=q; D）q->next=p->next; p->next=q;（3）（）不是队列的基本运算。
A）在队列第i个元素之后插入一个元素 B）从队头删除一个元素C）判断一个队列是否为空D）读取队头元素的值（4）字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（）个不同的字符串。
A）14 B）5 C）6 D）8（5）由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（）。
A）11 B）35 C）19 D）53以下6-8题基于下图：（6）该二叉树结点的前序遍历的序列为（）。
A）E、G、F、A、C、D、B B）E、A、G、C、F、B、DC）E、A、C、B、D、G、F D）E、G、A、C、D、F、B（7）该二叉树结点的中序遍历的序列为（）。
A）A、B、C、D、E、G、F B）E、A、G、C、F、B、DC）E、A、C、B、D、G、F D）B、D、C、A、F、G、E（8）该二叉树的按层遍历的序列为（）。
A）E、G、F、A、C、D、B B）E、A、C、B、D、G、FC）E、A、G、C、F、B、D D）E、G、A、C、D、F、B（9）下面关于图的存储的叙述中正确的是（）。
A）用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B）用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关C）用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关D）用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关（10）设有关键码序列(q,g,m,z,a,n,p,x,h)，下面哪一个序列是从上述序列出发建堆的结果?（）A）a,g,h,m,n,p,q,x,z B）a,g,m,h,q,n,p,x,zC）g,m,q,a,n,p,x,h,z D）h,g,m,p,a,n,q,x,z二、（本题8分）对于序列{8,18,6,16,29,28}，试写出堆顶元素最小的初始堆。
诚信应考考出水平考出风格Array XX大学城市学院2013— 2014学年第一学期期末考试试卷《数据结构基础》开课单位：计算分院；考试形式：闭卷；考试时间：20XX 1月14日；所需时间：120 分钟1. 数据的包括集合、线性结构、树形结构和图形结构四种基本类型。
A. 存储结构B. 逻辑结构C. 基本运算D. 算法描述2. 中任何两个结点之间都没有逻辑关系。
A. 树形结构B. 集合C. 图形结构D. 线性结构3. 下面的程序段违反了算法的原则。
void fun(){ int x=2;while (!(x%2)) x=x*2;printf(“%d〞,x);}A. 健壮性B. 确定性C. 可行性D. 有穷性4. 算法分析的两个主要方面是。
A. 空间复杂性和时间复杂性B. 正确性和简明性C. 可读性和文档性D. 数据复杂性和程序复杂性5. 用数组表示线性表的优点是。
A. 便于插入和删除操作B. 便于随机存取C. 可以动态地分配存储空间D. 不需要占用一片相邻的存储空间6. 循环链表的主要优点是。
A. 节约存储空间B. 已知某个结点的位置后，能够很容易找到它的直接前驱C. 在进行插入、删除运算时，能更好的保证链表不断开D. 从表中的任意结点出发都能访问到任何一个结点7. 可以用带表头附加结点的链表表示线性表，也可以用不带头结点的链表表示线性表，前者最主要的好处是。
A. 可以加快对表的遍历B. 节省存储空间C. 使空表和非空表的处理统一D. 可以提高存取表元素的速度8. 在头指针为h且表长大于1的单向循环链表中，指针p指向表中的某个结点，若p->next->next==h，则。
A. p指向头结点B. p指向尾结点C. *p的直接后继是头结点D. *p的直接后继是尾结点9. 线性表中，只有直接前驱而无后继的元素是。
A. 首元素B. 尾元素C. 中间元素D. 全部元素10. 以下不是栈的基本运算的是。
数据结构与算法考试（答案见尾页）一、选择题1. 什么是数据结构？请列举几种常见的数据结构。
A. 数组B. 链表C. 栈D. 队列E. 图2. 算法的时间复杂度是如何表示的？请简述其计算方式。
A. 用大O符号表示B. 用大O符号表示C. 用大O符号表示D. 用大O符号表示3. 什么是递归？请举例说明递归在算法中的实现。
A. 一个函数调用自身B. 一个函数调用自身的过程C. 一个函数调用自身的过程D. 一个函数调用自身的过程4. 什么是排序算法？请列举几种常见的排序算法，并简要描述它们的特点。
A. 冒泡排序B. 选择排序C. 插入排序D. 快速排序E. 归并排序5. 什么是哈希表？请简述哈希表的原理和优点。
A. 一种数据结构，它通过将键映射到数组索引来存储和检索数据B. 一种数据结构，它通过将键映射到数组索引来存储和检索数据C. 一种数据结构，它通过将键映射到数组索引来存储和检索数据D. 一种数据结构，它通过将键映射到数组索引来存储和检索数据6. 什么是树形结构？请列举几种常见的树形结构，并简要描述它们的特点。
A. 二叉树B. 二叉树C. B树D. B+树E. 无7. 什么是图数据结构？请列举几种常见的图算法，并简要描述它们的特点。
A. 广度优先搜索B. 深度优先搜索C. 最短路径算法（Dijkstra算法）D. 最长路径算法（Floyd算法）E. 最小生成树算法（Kruskal算法，Prim算法）8. 什么是动态规划？请简述动态规划的基本思想和应用场景。
A. 一种通过分解问题为更小的子问题来求解的方法B. 一种通过分解问题为更小的子问题来求解的方法C. 一种通过分解问题为更小的子问题来求解的方法D. 一种通过分解问题为更小的子问题来求解的方法9. 请简述贪心算法的基本思想以及在哪些问题上可以应用贪心算法。
A. 一种通过局部最优解来达到全局最优解的策略B. 一种通过局部最优解来达到全局最优解的策略C. 一种通过局部最优解来达到全局最优解的策略D. 一种通过局部最优解来达到全局最优解的策略10. 什么是算法的时间复杂度和空间复杂度？请简述它们的含义以及如何计算它们。
第一章数据结构与算法一.算法的基本概念计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。
1.算法的基本特征：可行性，确定性，有穷性，拥有足够的情报。
2.算法的基本要素：算法中对数据的运算和操作、算法的控制结构。
3.算法设计的基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。
4.算法设计的要求：正确性、可读性、茁壮性、效率与低存储量需求二.算法的复杂度1.算法的时间复杂度：指执行算法所需要的计算工作量2.算法的空间复杂度：执行这个算法所需要的内存空间三.数据结构的定义1.数据的逻辑结构：反映数据元素之间的关系的数据元素集合的表示。
数据的逻辑结构包括集合、线形结构、树形结构和图形结构四种。
2.数据的存储结构：数据的逻辑结构在计算机存储空间种的存放形式称为数据的存储结构。
常用的存储结构有顺序、链接、索引等存储结构。
四.数据结构的图形表示：在数据结构中，没有前件的结点称为根结点；没有后件的结点成为终端结点。
插入和删除是对数据结构的两种基本运算。
还有查找、分类、合并、分解、复制和修改等。
五.线性结构和非线性结构根据数据结构中各数据元素之间先后件关系的复杂程度，普通将数据结构分为两大类型：线性结构和非线性结构。
线性结构：非空数据结构满足：有且惟独一个根结点；每一个结点最多有一个前件，最多惟独一个后件。
非线性结构：如果一个数据结构不是线性结构，称之为非线性结构。
常见的线性结构：线性表、栈、队列六.线性表的定义线性表是n 个元素构成的有限序列 (A1，A2，A3 ) 。
表中的每一个数据元素，除了第一个以外，有且惟独一个前件。
除了最后一个以外有且惟独一个后件。
即线性表是一个空表，或者可以表示为(a1,a2,……an) , 其中ai(I=1,2, n是)属于数据对象的元素，通常也称其为线性表中的一个结点。
非空线性表有如下一些特征：(1) 有且惟独一个根结点a1,它无前件；(2) 有且惟独一个终端结点an，它无后件；(3) 除根结点与终端结点外，其他所有结点有且惟独一个前件，也有且惟独一个后件。
1 / 46）（ 至 学年第课程名称： 数据结构一、判断选择填空 (10分)1、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。
....( )2、用树的前序遍历和中序遍历可以导出树的后3、单链表从任何一个结点出发，都能访问到所有结点。
.....( )4、外部排序是在排序过程中，只使用外存储器的排序。
.....( )5、设串S 的长度为n,则S 的子串个数为n(n+1)/2。
.....( ) 6、若二叉树中的一个叶子结点是某子树中序序列的最后一个结点，则它必是该子树的先序序列的最后一个结点。
..... ( )7、设h 是一散列函数，key1和key2为关键码值，且 key1<>key2，但h （key1）=h （key2），这种现象称为（ ）。
8、若入栈序列的元素顺序是A 、B 、C 、D 、E ，判断下列哪一个出栈序列是不可能的（ ）⑴. A 、B 、C 、D 、E ⑵. B 、C 、D 、E 、A ⑶.E 、A 、B 、C 、D ⑷.D 、C 、B 、A 、E9、设i 为n 个结点的完全二叉树结点编，i=1，2，3...n ；若i ≤（n-1）/2时，结点i 的右孩子为（ ）⑴. 2i ⑵. 2i+1 ⑶. 2i-1⑷. i+110、若S1=‘China'，S2='$Beijing',则S1//S2=( )。
二、（5分）简述顺序存储结构和链式存储结构的优缺点。
三、（5分）简述使用顺序存储表示循环队列时，判定队列“空”和“满”的方法。
四、（5分）编写子串位置定位函数Index(S,T,pos)；五、（5分）假设字符a,b,c,d,e,f的使用频度分别是0.07,0.09,0.12,0.22,0.23,0.27，画出相应的Huffman树，并写出a,b,c,d,e,f的Huffman编码。
六、（5分）假设一棵二叉树的后序序列为GDBEHFCA和中序序列为DGBAECHF，请画出该二叉树，并写出先序遍历序列。
《数据结构》期末考试试卷附答案一、单项选择题（本大题共10小题，每小题3分，共30分）1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。
(A)、正确性 (B). 可行性 (C). 健壮性 (D). 输入性2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。
for(i=n-1；i>=0；i--)for(j=0；j<i；j++) S；(A). n2 (B). O(nlgn) (C). O(n) (D). O(n2)3．折半查找法适用于（）。
（A）、有序顺序表（B）、有序单链表（C）、有序顺序表和有序单链表都可以（D）、无限制4．顺序存储结构的优势是（）。
（A）、利于插入操作（B）、利于删除操作（C）、利于顺序访问（D）、利于随机访问5．深度为k的完全二叉树，其叶子结点必在第（）层上。
（A）、k-1 （B）、k （C）、k-1和k （D）、1至k6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（）（A）、11 （B）、13 （C）、48 （D）、377．图的Depth-First Search(DFS)遍历思想实际上是二叉树（）遍历方法的推广。
（A）、先序（B）、中序（C）、后序（D）、层序8．在下列链队列Q中，元素a出队的操作序列为（）（A）、p=Q.front->next; p->next= Q.front->next;（B）、p=Q.front->next; Q.front->next=p->next;（C）、p=Q.rear->next; p->next= Q.rear->next;（D）、p=Q->next; Q->next=p->next;9．Huffman树的带权路径长度WPL等于（）（A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和（C）、各叶子结点的带权路径长度之和（D）、根结点的值10．线索二叉链表是利用（）域存储后继结点的地址。
2014年春季北大《数据结构与算法B》期末考试模拟试卷(本试卷只是给同学们看看考题形式和范围，难度与真实考卷稍有差别)学号______________ 姓名_______________ 教师/教室_____________(注：如米标明，本试卷题屮的下标、位.胃.都从o开始计数)一、填空题(共32分)1.设有字符串变量String A = “This”，C=“just”，D=“ajest”，请计算下列表达式：(1)A+B+D= “Thisisajest” ；(2) D.IndexOf(“t’’) = _2_:(求字符在字符串中的第一个位置)(3) B.StrlengthQ = __ 2 __(4) D.SubStr(U2)= _ _________ (注：1为起始下标，2为子串长度)【4分】2.顺序査找n个元素的顺序表，若查找成功，则比较关键字的次数S多为n 次;若查找失败，则比较关键字的次数最多为_n_,最少力_次。
【3分】3.在散列函数H (key) =key%p中，p值最好取_____ 质数(或素数) _____ 。
【1分】4.对于下图邻接表所对应的有向图，试写出：【2分】(1)从顶点①出发进行深度优先遍历结果_1，2, 3, 4, 5_;(2)从顶点①出发进行广度优先遍历结果_1，2, 3, 4, 55.当图中各条边上的权值_都相等_时，宽度优先搜索算法可用来解决单源最短路径问题？【2分】6.—棵有n个结点的满二叉树有i个度为1的结点、有(n-1)/2个分支 <非终端)结点；该满二叉树的深度最大为_(n-l)/2_,最小为int(log2n)gcLlog2nJo (独根树深度为0)【4分】7.对于给定的n个元素，可以构造出的逻辑结构有线性结构，树形结构，阁形结构，_集合_四种。
【2分】8.下面程序段的时间复杂度力_O(n)_。
(n〉l)［大O表示法］【2分】sum=l；for (i=0;sum<n;i++) sum十=1;9.对于最大堆65 43 59 24 37 48 57 12 23 28 5 3,删除掉最大元素后，堆中元素为59,43,57,24,37,48,3,12,23,28,5【2 分】6510.从空二叉树开始，严格按照二叉搜索树的插入算法（不进行旋转平衡），逐个插入关键码｛18,73,10,5,68,99,27,41,51,32,25 ｝构造出一棵二叉搜索树，该二叉树转换为森林，则该森林的层次遍历序列为18 73 99 10 68 5 27 41 51 25 32【4分】11.用S表示入栈操作，X表示岀栈操作，若元素入栈的顺序为12345,为了得到13542出栈顺序，相应的S和X的操作串为_SXSSXSSXXX_。
《数据结构与算法》复习题一、填空题1、在树形结构中，树根结点没有，其余每个结点有且只有个前驱结点；叶子结点没有，其余每个结点的后续结点数可以任意多个。
2、在图形结构中，每个结点的前驱结点数和后续结点数可以。
3、在一个单链表中删除p所指结点的后继结点时，应执行以下操作：q = p->next;p->next= ;4、稀疏矩阵的压缩存储方式有：和。
5、n个顶点的连通图至少有边。
6、设一棵完全二叉树有700 个结点，则共有个叶子结点。
7、快速排序平均情况下的时间复杂度为。
8、数据的运算最常用的有5 种，它们分别是、、、、。
9、设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6 依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1 ，则栈的容量至少应该是。
10、已知循环队列的存储空间大小为20，且当前队列的头指针和尾指针的值分别为8和3，且该队列的当前的长度为____。
11、具有n个结点的完全二叉树的深度是。
12、在具有n 个单元的循环队列中，队满时共有个元素。
13、快速排序其最坏情况下的时间复杂度为。
二、选择题1、非线性结构是数据元素之间存在一种：( )A.一对多关系B.多对多关系C.多对一关系D.一对一关系2、数据结构中，与所使用的计算机无关的是数据的（）结构；A. 存储B. 物理C. 逻辑D. 物理和存储3、若以{4,5,6,7,8} 作为权值构造哈夫曼树，则该树的带权路径长度为（）。
A. 67B. 68C. 69D. 704、将一棵有100 个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49 的结点的左孩子编号为（）。
A. 98B. 99C. 50D. 485、在线索二叉树中， t 所指结点没有左子树的充要条件是（B ）。
A. t->left==NULLB. t->ltag==1C. t17->ltag==1&&t->left==NULLD. 以上都不对6、表达式A*(B+C)/(D-E+F) 的后缀表达式是（ C ）。
电脑科学与技术、网络工程本科《数据结构》期末考试试卷一、选择题〔单项选择题，每题3分，共33分〕1．已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA，则该二叉树的后序序列为。
A．BCDEAF B．ABDCEF C．DBACEF D．DABECF 2．在11个元素的有序表A[1…11]中进行折半查找〔⎣⎦2/)low+〕，查找元素(highA[11]时，被比较的元素的下标依次是。
A．6，8，10，11 B．6，9，10，11 C．6，7，9，11 D．6，8，9，113．由元素序列〔27，16，75，38，51〕构造平衡二叉树，则首次出现的最小不平衡子树的根〔即离插入结点最近且平衡因子的绝对值为2的结点〕为。
A．27 B．38 C．51 D．754．利用逐点插入法建立序列〔50，72，43，85，75，20，35，45，65，30〕对应的二叉排序树以后，查找元素30要进行次元素间的比较。
A．4 B．5 C．6 D．75．循环链表的主要优点是。
A．不再需要头指针了B．已知某个结点的位置后，很容易找到它的直接前驱结点C．在进行删除后，能保证链表不断开D．从表中任一结点出发都能遍历整个链表6．已知一个线性表〔38，25，74，63，52，48〕，假定采用散列函数h〔key〕=key%7计算散列地址，并散列存储在散列表A[0…6]中，假设采用线性探测方法解决冲突，则在该散列表上进行等概率查找时查找成功的平均查找长度为。
A．1．5 B．1．7 C．2．0 D．2．37．由权值为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为。
A．23 B．37 C．44 D．468．在最好和最坏情况下的时间复杂度均为O〔nlogn〕且稳定的排序方法是。
A．基数排序B．快速排序C．堆排序D．归并排序9．无向图G=(V，E)，其中V={a，b，c，d，e，f}，E={(a，b)，〔a，e〕，(a，c)，〔b，e〕，〔c，f〕，(f，d)，〔e，d〕}。
《数据结构与算法》期末练习一选择题1．以下与数据的存储结构无关的术语是（A．循环队列 B.链表 C.D ）。
哈希表 D.栈2.算法的时间复杂度取决于（ A ）A．问题的规模 B.待处理数据的初态 C. A 和 B D.计算机 cpu3.一个栈的输入序列为 1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ B ）。
A. 2 3 4 1 5B. 5 4 1 3 2C. 2 3 1 4 5D. 1 54 3 24.有关静态链表的叙述： (1) 静态链表既有顺序存储的优点，又有动态链表的优点。
所以，它存取表中第 i 个元素的时间与 i 无关。
(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。
(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。
以上错误的是（ B ）A ．（1），（2）B．（1）C．（1），（2）,(3)D.（2）5．对于有 n 个结点的二叉树 , 其高度为（ D ）A．nlog 2n B．log2n C．? log2n? |+1D．不确定6．从下列有关树的叙述中, 选出正确的叙述（ C ）A．二叉树中每个结点有两个子结点, 而树无此限制 , 因此二叉树是树的特殊情况。
B．当 K≥1 时高度为 K 的二叉树至多有2k-1个结点。
C．哈夫曼树是带权路径最短的树, 路径上权值较大的结点离根较近。
D．在二叉树中插入结点, 该二叉树便不再是二叉树。
7．设无向图的顶点个数为n，则该图最多有（ B ）条边。
A． n-1 B ．n(n-1)/2 C ． n(n+1)/2D．0E．n28．已知有向图 G=(V,E)，其中 V={V1,V 2,V 3,V 4,V 5,V 6,V 7} ，E={<V1,V 2>, <V1,V 3>, <V1,V 4 >, <V2,V 5>, <V3,V 5>, <V3,V 6>, <V4,V 6>,<V5,V 7>, <V6,V 7>},G 的拓扑序列是（ A ）。
