下载文档原格式
数据结构与算法复习题库含答案1. 问题描述：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
答案：可以使用哈希表来解决此问题。
首先初始化一个空的哈希表，然后遍历数组中的每个元素。
对于每个元素，首先计算目标值与当前元素的差值，然后在哈希表中查找该差值。
如果找到了该差值，则说明存在两个数的和等于目标值，返回这两个数的下标；否则，将当前元素插入到哈希表中。
时间复杂度为O(n)，其中n为数组的长度。
2. 问题描述：给定一个字符串，找出其中不含重复字符的最长子串的长度。
答案：可以使用滑动窗口来解决此问题。
维护一个窗口，其中包含没有重复字符的子串。
遍历字符串中的每个字符，如果该字符不在窗口中，将其加入窗口；如果该字符在窗口中，移动窗口的左边界直到窗口中不包含重复字符。
记录窗口的最大长度。
时间复杂度为O(n)，其中n为字符串的长度。
3. 问题描述：给定一个字符串和一个单词列表，找出字符串中可以由单词列表中的单词组成的所有子串的起始位置。
答案：可以使用滑动窗口和哈希表来解决此问题。
首先统计单词列表中每个单词的出现次数。
然后遍历字符串中的每个位置作为子串的起始位置，维护一个滑动窗口。
在窗口中依次取出长度和单词列表中单词总长度相等的子串，在哈希表中统计子串中每个单词出现的次数。
如果窗口中的子串与单词列表中的单词出现次数一致，则记录该子串的起始位置。
时间复杂度为O(n*m)，其中n为字符串的长度，m为单词列表中的单词个数。
4. 问题描述：给定一个无序的整数数组，找出其中缺失的第一个正整数。
答案：可以使用原地哈希表来解决此问题。
遍历数组中的每个元素，将每个正整数放到数组中对应的位置上。
遍历数组中的每个元素，如果该位置上的数不等于数组索引加一，则该索引加一即为缺失的第一个正整数。
时间复杂度为O(n)，其中n为数组的长度。
5. 问题描述：给定一个字符串s，找到s中最长的回文子串。
答案：可以使用动态规划来解决此问题。
算法与数据结构习题及参考答案一、选择题1. 在算法分析中，时间复杂度表示的是：A. 算法执行的时间B. 算法的运行速度C. 算法执行所需的操作次数D. 算法的内存消耗答案：C2. 哪种数据结构可以在常数时间内完成插入和删除操作？A. 数组B. 栈C. 队列D. 链表答案：B3. 单链表的逆置可以使用哪种算法实现？A. 冒泡排序B. 归并排序C. 快速排序D. 双指针法答案：D4. 常用的查找算法中，哪种算法的时间复杂度始终为O(log n)？A. 顺序查找B. 二分查找C. 广度优先搜索D. 深度优先搜索答案：B5. 哪种排序算法的时间复杂度最坏情况下仍为O(n log n)？A. 冒泡排序B. 插入排序C. 快速排序D. 堆排序答案：C二、填空题1. 下面哪个数据结构先进先出？A. 栈B. 队列C. 堆D. 链表答案：B2. 在快速排序的基本步骤中，需要选取一个元素作为________。
答案：枢纽元素3. 广度优先搜索使用的数据结构是________。
答案：队列4. 二分查找是基于_________的。
答案：有序数组5. 哈希表的查找时间复杂度为_________。
答案：O(1)三、解答题1. 请简要说明冒泡排序算法的原理及时间复杂度。
答：冒泡排序是一种简单直观的排序算法。
它的基本思想是通过相邻元素之间的比较和交换来将最大（或最小）的元素逐渐“冒泡”到数列的一端。
冒泡排序的过程如下：1）比较相邻的元素，如果前面的元素大于后面的元素，则交换它们的位置；2）对每一对相邻元素重复进行比较和交换，直到最后一对元素；3）针对剩下的元素重复上述步骤，直到整个数列有序。
冒泡排序的时间复杂度为O(n^2)，其中n为待排序数列的长度。
在最坏情况下，冒泡排序需要进行n-1次比较和交换操作，因此时间复杂度为O(n^2)。
在最好情况下，如果待排序数列已经有序，冒泡排序只需进行n-1次比较，没有交换操作，时间复杂度为O(n)。
数据结构与算法一选择题1．算法的计算量的大小称为计算的（）。
A．效率 B. 复杂性 C. 现实性 D. 难度2．下面说法错误的是（）(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)3. 连续存储设计时，存储单元的地址（）。
A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续4. 下述哪一条是顺序存储结构的优点？（）A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示5．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表6．下面的叙述不正确的是（）A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关7．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。
A. O(0)B. O(1)C. O(n)D. O(n2)8．双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（）(^.相当于—>)A. p＾.llink:=q; q＾.rlink:=p; p＾.llink＾.rlink:=q; q^.llink:=p^.llink;B. q＾.llink:=p^.llink; p＾.llink^.rlink:=q; q＾.rlink:=p; p^.llink:=q^.rlink;C. q^.rlink:=p; p^.rlink:=q; p^.llink^.rlink:=q; q^.rlink:=p;D. p^.llink^.rlink:=q; q^.rlink:=p; q^.llink:=p^.llink; p^.llink:=q;9．下列排序算法中，其中（）是稳定的。
三、写一个算法合并两个已排序的线性表。
〔用两种方法：数组表示的线性表〔顺序表〕和指针表示的线性表〔链表〕〕要求：1、定义线性表节点的结构，并定义节点的型和位置的型。
2、定义线性表的基本操作3、在1，2的基础上，完成此题。
4、在main 函数中进行测试：先构建两个有序的线性表，然后合并这两个线性表。
四、已知一个单向链表，试给出复制该链表的算法。
要求：1、定义线性表的节点的结构以及节点的型和位置的型。
2、定义线性表的基本操作3、在1，2的基础上，完成此题。
4、在main 函数中进行测试：先构建一个线性表，并定义一个空线性表，然后进行复制。
五、写出从一个带表头的单链表中删除其值等于给定值x 的结点的算法函数：int delete(LIST &L, int x);如果x 在该链表中，则删除对应结点，并返回其在链表中的位置〔逻辑位置，第一个结点的逻辑位置为1〕，否则返回-1。
要求：1、定义线性表的节点的结构以及节点的型和位置的型。
2、定义线性表的基本操作3、在1，2的基础上，完成此题。
4、在main 函数中进行测试：先构建一个线性表，然后调用函数删除值等于给定值的节点。
六、写出一个将两个静态链表〔属于同一个存储池〕合并的算法函数：void Merge(cursor M, cursor N); 合并的方法是将N 链表中的所有结点添加到M 链表的后面，并将N 链表的表头结点添加到空闲结点链表中。
要求：1、定义静态链表的结点的结构以及结点的型SPACE 以及位置〔position 〕和游标〔cursor 〕的型。
2、定义静态链表的基本操作：void Initialize(); 初始化，将所有存储池中的结点设置为空闲；cursor GetNode(); 从空闲链中获取一个结点；void FreeNode(cursor q); 将结点q 加入到空闲链； void Insert ( elementtype x, position p, cursor M ); 在链表M 中的位置为p 的元素后面添加一个值为x 的结点；void Delete (cursor M, position p ); 在链表M 中删除位置为p 的元素的后一个元素。
数据结构与算法练习试卷1(题后含答案及解析) 题型有：1. 选择题选择题（每小题1分，共60分）下列各题A、B、C、D四个选项中，只有一个选项是正确的，请将正确选项涂写在答题卡相应位置上。
下列各题基于下面的叙述：某二叉树节点的对称序序列为A、B、C、D、E、P、G，后序序列为B、D、C、A、F、G、E。
1．该二叉树节点的先序序列为______。
A．E、G、F、A、C、D、BB．E、A、C、B、D、G、FC．E、A、G、C、F、B、DD．E、G、A、C、D、F、B正确答案：B 涉及知识点：数据结构与算法2．该二叉树对应的树林包括多少棵树? ______。
A．1B．2C．3D．4正确答案：B 涉及知识点：数据结构与算法3．该二叉树对应的树林节点的层次次序序列为______。
A．E、G、F、A、C、D、BB．E、A、C、B、D、G、FC．E、A、G、C、F、B、DD．E、G、A、C、D、F、B正确答案：C 涉及知识点：数据结构与算法4．有6个元素6，5，4，3，2，1顺序进栈，问下列哪一个不是合法的出栈序列______。
A．5，4，3，6，1，2B．4，5，3，2，1，6C．3，4，6，5，2，1D．2，3，4，1，5，6正确答案：A 涉及知识点：数据结构与算法5．下面关于串的叙述中，哪一个是不正确的? ______。
A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储正确答案：B 涉及知识点：数据结构与算法6．下列排序方法中，哪一个是稳定的排序方法? ______。
A．直接选择排序B．二分法插入排序C．希尔排序D．快速排序正确答案：B 涉及知识点：数据结构与算法7．下面关于B和B+树的叙述中，不正确的是______。
A．B树和B+树都是平衡的多分树B．B树和B+树都可用于文件的索引结构C．B树和B+树都能有效地支持顺序检索D．B树和B+树都能有效地支持随机检索正确答案：C 涉及知识点：数据结构与算法8．下面关于线性表的叙述中，错误的是______。
数据结构与算法试题及答案数据结构与算法试题及答案在计算机科学领域，数据结构与算法是非常重要的基础知识。
数据结构是一种组织和存储数据的方式，而算法则是解决问题的方法和步骤。
掌握好数据结构与算法，有助于提高程序的运行效率和解决实际问题。
下面是一些关于数据结构与算法的试题及其答案，希望能够帮助大家更好地理解和应用这方面的知识。
试题一：什么是数据结构？请举例说明。
答案一：数据结构是一种组织和存储数据的方式。
它可以使数据的操作更加高效。
常见的数据结构有数组、链表、栈、队列、树和图等。
举个例子，数组是一种线性数据结构，可以存储一组相同类型的元素。
试题二：什么是算法？请举例说明。
答案二：算法是一种解决问题的方法和步骤。
它是一个精确的描述，用于解决特定问题。
常见的算法有排序算法、查找算法、递归算法等。
例如，冒泡排序算法是一种比较简单的排序算法，通过不断交换相邻元素的位置来达到排序的目的。
试题三：什么是时间复杂度和空间复杂度？答案三：时间复杂度和空间复杂度是衡量算法性能的两个指标。
时间复杂度是指算法执行所需要的时间，通常用大O符号表示。
空间复杂度是指算法执行所需要的额外空间，通常也用大O符号表示。
它们都是描述算法随着输入规模增大而变化的趋势。
试题四：介绍一下常见的数据结构和相应的操作。
答案四：常见的数据结构有数组、链表、栈、队列、树和图等。
- 数组是一种线性数据结构，可以随机访问元素，并且在插入和删除元素时需要移动其他元素。
- 链表是一种动态数据结构，不需要固定的内存空间，但只能通过指针进行元素的访问。
- 栈是一种后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除元素的操作。
- 队列是一种先进先出（FIFO）的数据结构，只能在队尾插入元素，在队头删除元素。
- 树是一种非线性数据结构，由节点和指向子节点的边组成。
常见的树有二叉树、二叉搜索树和AVL树等。
- 图是一种复杂的数据结构，由节点和边组成，可以表示各种关系。
一、选择题1. 在逻辑上能够把数据结构分红（A）A. 线性结构和非线性结构B. 动向结构和静态结构C.紧凑结构和非紧凑结构D.内部结构和外面结构2. 单链表中各结点之间的地点（C）A. 一定连续B.部分一定连续C.不必定连续D.以上均不对3. 在一个长度为 n 的次序表中向第 i 个元素（ 0<i<=n+1 ）以前插入一个新元素时，需向后挪动（B ）个元素。
A 、n-iB、n-i+1C、n-i-1D、 i4. 插入和删除操作只好在一端进行的线性表，称为（C ）。
A. 行列B. 线性表C. 栈D.循环行列5、行列是仅同意在（）进行插入，而在（）进行删除。
(A )A. 队尾，队首B. 队尾，队尾C. 队首，队尾D. 队首，队首6. 链表合适于（A ）查找。
A. 次序B.二分C.随机D.次序或二分7. 数据的基本单位是（A ）。
A. 数据元素B.数据结构C.数据项D.数据对象8. 以下哪个不是算法的特征（B ）。
A. 有穷性B. 可数性C.可行性D.确立性9. 在表长为 n 的次序表中进行线性查找，它的均匀查找长度为（B ）。
A.ASL=nB.ASL=(n+1)/2C.ASL=n+1 D.ASL=log2n10. 一个线性表第一个元素的储存地点是 320，每个元素的长度为 3，则第五个元素的地点是(C ）。
11. 设 front 、rear 分别为循环双向链表结点的左指针和右指针，则指针 P 所指的元素是双循环链表 L 的尾元素的条件是（D ）。
A.P==LB.P->front==LC.P==NULLD.P->rear==L12. 已知 P 为单链表中的非首尾结点，删除 P 结点的后继结点 Q 的语句为（A ）。
A.P->NEXT=Q->NEXT;FREE(Q);B.Q->NEXT=P; FREE(Q);C.Q->NEXT=P->NEXT;FREE(Q);D.P->NEXT=S;S->NEXT=P; B第1页共16页 1A.SQ->rear==SQ->frontB. (SQ->rear+1)%MAXLEN==SQ->frontC.SQ->rear==0D. SQ->front==014. 一组记录的排序码为（ 46， 79，56， 38， 40， 84），则利用堆排序的方法成立的初始堆 为(B )。
数据结构与算法习题及答案1.下列叙述中正确的是（）。
BA）所谓算法就是计算方法B）程序可以作为算法的一种描述方法C）算法设计只需考虑得到计算结果D）算法设计可以忽略算法的运算时间3.深度为5的完全二叉树的结点数不可能是（）。
AA）15B）16C）17D）184.设二叉树如下：则前序序列为（）。
AA）ABDEGCFH5.下列叙述中正确的是（）。
AA）循环队列是顺序存储结构B）循环队列是链式存储结构C）循环队列是非线性结构D）循环队列的插入运算不会发生溢出现象7.下列关于算法的描述中错误的是（）。
DA）算法强调动态的执行过程，不同于静态的计算公式B）算法必须能在有限个步骤之后终止C）算法设计必须考虑算法的复杂度D）算法的优劣取决于运行算法程序的环境8.设二叉树如下：则中序序列为（）。
BA）ABDEGCFH9.线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有（）。
B A）节省存储空间B）插入与删除运算效率高C）便于查找D）排序时减少元素的比较次数11.下列叙述中正确的是（）。
CA）所谓有序表是指在顺序存储空间内连续存放的元素序列B）有序表只能顺序存储在连续的存储空间内C）有序表可以用链接存储方式存储在不连续的存储空间内D）任何存储方式的有序表均能采用二分法进行查找12.设二叉树如下：则后序序列为（）。
CA）ABDEGCFH13.下列叙述中正确的是（）。
BA）结点中具有两个指针域的链表一定是二叉链表B）结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构 C）二叉树只能采用链式存储结构D）循环链表是非线性结构15.带链的栈与顺序存储的栈相比，其优点是（）。
CA）入栈与退栈操作方便B）可以省略栈底指针C）入栈操作时不会受栈存储空间的限制而发生溢出D）以上都不对17.下列关于算法复杂度叙述正确的是（）。
BA）最坏情况下的时间复杂度一定高于平均情况的时间复杂度B）时间复杂度与所用的计算工具无关C）对同一个问题，采用不同的算法，则它们的时间复杂度是相同的D）时间复杂度与采用的算法描述语言有关19.下列叙述中正确的是（）。
数据结构与算法的练习题集在学习数据结构与算法的过程中，练习题是巩固知识、提升技能的重要手段。
接下来，为大家整理了一系列具有代表性的练习题，涵盖了常见的数据结构和算法类型。
一、数组相关练习题1、给定一个整数数组，找出其中最大的连续子数组和。
例如，对于数组｀－2, 1, －3, 4, －1, 2, 1, －5, 4 ｀，最大连续子数组和为 6 ，对应的子数组是｀ 4, －1, 2, 1 ｀。
2、旋转数组。
给定一个整数数组｀nums` ，将数组中的元素向右移动｀k` 个位置，其中｀k` 是非负数。
比如，对于数组｀ 1, 2, 3, 4, 5, 6, 7 ｀，如果｀k ＝ 3` ，则旋转后的数组为｀ 5, 6, 7, 1, 2, 3, 4 ｀。
二、链表相关练习题1、反转链表。
给定一个单链表，将其反转。
例如，对于链表｀1 ＞ 2 ＞ 3 ＞ 4 ＞ 5` ，反转后为｀5 ＞ 4 ＞ 3 ＞2 ＞ 1` 。
2、合并两个有序链表。
给定两个有序链表｀l1` 和｀l2` ，将它们合并成一个新的有序链表。
三、栈和队列相关练习题1、用两个栈实现队列。
实现一个队列，使用两个栈来完成入队和出队操作。
2、有效的括号。
给定一个只包含｀＇（＇｀、｀＇）＇｀、｀＇｛＇｀、｀＇｝＇｀、｀＇＇｀、｀＇＇｀的字符串，判断括号是否有效。
四、树相关练习题1、二叉树的前序遍历、中序遍历和后序遍历。
给定一个二叉树，分别实现前序遍历、中序遍历和后序遍历的算法。
2、二叉搜索树的查找、插入和删除操作。
五、图相关练习题1、深度优先搜索和广度优先搜索。
对于给定的图，实现深度优先搜索和广度优先搜索算法。
2、最短路径问题。
例如，在一个有权图中，找到从一个顶点到其他所有顶点的最短路径。
六、排序算法相关练习题1、冒泡排序、插入排序、选择排序的实现和性能分析。
2、快速排序和归并排序的实现及时间复杂度分析。
3、给定一个乱序的整数数组，使用至少两种排序算法对其进行排序，并比较它们的性能。
算法与数据结构试题及答案一、算法试题1. 请解释什么是算法？算法是一系列确定的步骤，用于解决问题或执行特定任务的方法。
2. 请列举几种常见的算法分类。
- 搜索算法：如二分搜索、广度优先搜索、深度优先搜索。
- 排序算法：如冒泡排序、插入排序、快速排序。
- 图算法：如最短路径算法、最小生成树算法。
- 字符串匹配算法：如KMP算法、Boyer-Moore算法。
3. 请描述递归算法的特点及适用场景。
递归算法是指在解决问题时，将大问题划分成一个或多个与原问题类似但规模减小的子问题，并通过递归调用这些子问题来解决原问题。
递归算法的特点包括简洁，易于理解和实现，但可能存在性能上的问题。
适用场景包括树结构的问题、分治算法等。
4. 请解释时间复杂度和空间复杂度的概念。
- 时间复杂度是指算法执行所需要的时间，通常用大O符号表示。
表示算法运行时间与问题规模的增长率之间的关系。
- 空间复杂度是指算法在执行过程中所需的额外空间，通常也用大O符号表示。
表示算法所需的空间与问题规模的增长率之间的关系。
二、数据结构试题1. 请解释什么是数据结构？数据结构是指为组织和存储数据而设计的一种特定方式。
它定义了数据的逻辑关系和操作方法。
2. 请列举几种常见的数据结构。
- 数组：一种连续存储数据的线性数据结构。
- 栈：一种具有后进先出（LIFO）特性的线性数据结构。
- 队列：一种具有先进先出（FIFO）特性的线性数据结构。
- 链表：一种通过指针连接各个节点的数据结构。
- 树：一种由节点和边组成的非线性数据结构。
3. 请解释树的常见术语：节点、根节点、叶子节点、父节点、子节点、深度、高度。
- 节点：树中的基本元素，包含数据和指向其他节点的指针。
- 根节点：树的顶部节点，没有父节点。
- 叶子节点：没有子节点的节点。
- 父节点：有子节点的节点。
- 子节点：一个节点的直接后继节点。
- 深度：从根节点到当前节点所经过的边的数量。
- 高度：树中任意节点最大深度的值。
1 / 7 一、单项选择题 ：（本大题共20小题，每题 2 分，共 30 分） （说明：将答案写在试卷后面的答题纸上） 分数 评卷人
1.计算机识别、存储和加工处理的对象被统称为( ) A.数据 B.数据元素 C.数据结构 D.数据类型 2.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是( ) A.O(1) B.O(n) C.O(nlogn) D.O(n2) 3.队和栈的主要区别是( ) A.逻辑结构不同 B.存储结构不同 C.所包含的运算个数不同 D.限定插入和删除的位置不同 4.链栈与顺序栈相比，比较明显的优点是( ) A.插入操作更加方便 B.删除操作更加方便 C.不会出现下溢的情况 D.不会出现上溢的情况 5.下列说法中正确的是（） A. 二叉树中任何一个结点的度都为2 B. 二叉树的度为2 C. 任何一棵二叉树中至少有一个结点的度为2 D. 一棵二叉树的度可以小于2 6.在一非空二叉树的中序遍历序列中，根结点的右边（） A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的所有结点 D. 只有左子树上的部分结点 7.在一个具有N个顶点的无向完全图中，包含的边的总数是（） A. N(N-1)/2 B. N(N-1) C. N(N+1) D. N(N+1)/2 8.下面的程序在执行时，S语句共执行的（）次。 i=1; while (i<=n) {for(j=i;j{S; } i=i+1; }
A. n(n+1)/2 B. n(n-1)/2 C. n! D. 2n 9.设二叉树有n个结点，则其深度为（） A. n-1 B. n C. 5log2n+1 D. 不确定 2 / 7
10.已知一棵二叉树结点的先根序列为ABDGCFK，中根序列为DGBAFCK，则结点的后根序列为（） A. ACFKBDG B. GDBFKCA C. KCFAGDB D. ABCDFKG 11.任何一个带权的无向连通图的最小生成树（） A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 12.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，则它的前序遍历序列是（） A. acbed B. decab C. deabc D. cedba 13.设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数量是（C）个 A. k+1 B. 2k C. 2k-1 D. 2k+1 14.下面程序的时间复杂性是（） For(i=1;i<=n;i++) For(j=1;j<=n;j++) {a[i][j]=i*j; }
A. O(2m) B. O(2n) C. O(m*n) D. O(m+n) 15.含N个顶点的连通图中的任意一条简单路径，其长度不可能超过（） A. 1 B. N/2 C. N-1 D. N 16. 下列说法正确的是（A） A.树的先根遍历序列与其对应的二叉树的先根遍历序列相同 B.树的先根遍历序列与其对应的二叉树的后根遍历序列相同 C.树的后根遍历序列与其对应的二叉树的先根遍历序列相同 D.树的后根遍历序列与其对应的二叉树的后根遍历序列相同 17.对于一个具有N个结点和E条边的无向图，若采用邻接表示，则表头向量的大小是(A) A. N B. N+1 C. N-E D. N-1 18.判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用（） A.求关键路径的方法 B.求最短路径的Dijkstra方法 C.广度优先遍历方法 D. 深度优先遍历方法 19.一个队列的输入序列是1,2,3,4，则队列的输出序列是（） A,4,3,2,1 B.1,2,3,4 C.1,4,3,2 D.3,2,4,1 20.任何一个带权的无向连通图的最小生成树（B） A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在
得分 评卷人 复查人 一、 二、填空题（本大题共10小题，每小题1分，共10分） 请在每小题的空格中填上正确答案。错填、不填均无分。
（1）在线性表中插入或删除一个元素，需要平均移动 元素，具体移动的元素个数与 有关。 （2）顺序表中逻辑上相邻的元素的物理位置 紧邻，单链表中逻辑上相邻的元素物理位置 紧邻。 （3）在单链表中，除了首元结点外，任意结点的存储位置由 指示。 （4）记录的 结构是数据在物理存储器上的存储方式。 3 / 7
（5）在非空队列中，头指针始终指向 ，而尾指针始终指向 。 （6）N个顶点的连通图，至少有 条边。 （7）对于一个长度为n的线性表，假设表中各结点的查找概率相同，则在查找成功的情况下，平均查找长度为 ，如果k不在表中，则需要进行 次比较后才能确定查找失败。 (8)在二叉排序树中，其左子树中任何一个结点的关键字一定 其右子树的各结点的关键字。 （9）已知无向图G的结点数为n，边数为e，其邻接表表示中的表结点数与表头结点数之和为 。 （10）若二叉树的一个叶子是某子树的中序遍历序列中的第一个结点，则它必是孩子树的后序遍历序中的 个结点。 （11）有m个叶子结点(又称外结点)的哈夫曼树，其结点总数是 。 （12）如果一个图中有n条边，则此图的生成树含有 条边，所以生成树是图的边数 最少 的连通图 （13）由权值为1，2，3，4，5，6的六个叶子结点构成一棵哈夫曼树，则带权的路径的长度为 。 （14）在顺序队列中，应该有队头和队尾两个指针来指示，队头指针和队尾指针的初值在队列的初始化时均应该设置为 ，当对队列进行插入和删除的操作后，如果头指针和尾指针相等时，队列为 。 （15）树有三种常用的存储结构，即孩子链表法、孩子兄弟链表法和 。 （16）无向图的邻接矩阵是 的，并且主对角线上的元素的值为 。 （17）在结点数目相同的二叉树中， 的路径长度最短。 （18）栈和队列均可视为特殊的线性表，所不同的在于对这二种特殊线性表 和 运算的限定不一样。 16.当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的____时间复杂度____。
17.下面程序段的时间复杂度为___________。 sum=1； for（i=0；sumsum+=1； 18.已知链表结点定义如下： typedef struct node{ char data［16］； struct node *next; } LinkStrNode； 如果每个字符占1个字节，指针占4个字节，则该链表的存储密度是___________。 19.使用一个100个元素的数组存储循环队列，如果采取少用一个元素空间的方法来区别循环队列的队空和队满，约定队头指针front等于队尾指针rear时表示队空。若为front=8，rear=7，则队列中的元素个数为___________。 20.3个结点可以组成___________种不同树型的二叉树。 4 / 7
21.用5个权值{3, 2，4，5，1}构造的哈夫曼(Huffman)树的带权路径长度是___________。 22.若无向图G中有n个顶点m条边，采用邻接矩阵存储，则该矩阵中非0元素的个数为___________。 23.影响排序效率的两个因素是关键字的___________次数和记录的移动次数。 24.对任一m阶的B树，每个结点中最多包含___________个关键字。 25.在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作________。
26.已知链栈的结点结构为 栈顶指针为top，则实现将指针p所指结点插入栈顶的语句依次为________和________。 27.空串的长度是________；空格串的长度是________。 28.在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是________。
得分 评卷人 复查人 三、名词解释（本大题共4小题，每小题3分，共12分） （1）栈：。 （2）树：。 （3）森林：。 （4）满二叉树：。 （5）数据：。
（6）数据对象：。 （7）数据结构：。 （8）算法： 得分 评卷人 复查人 四、简答题（本大题共4小题，每小题5分，共20分）
（1）简述算法的五个重要特性 （2）算法设计的基本要求
date next 5 / 7
（3）试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别 （4）简述二叉树的特点 （5）已知一棵度为k的树中有1n个度为1的结点，2n个度为2的结点，。。。kn个度为k的结点，问该树中有多少个叶子节点？ （7）写出下列树的先根序列和后根序列
A
CEFGHIJKBD
（8）已知如图所示的有向图，请给出该图的： （1） 每个顶点的入/出度 （2） 邻接矩阵
15
246
3 答案： 得分 评卷人 复查人 五、程序阅读题（本大题共4小题，每小题5分，共20分）
（1）简述以下算法的功能： status A (linkedlist L) { if (L&&L->next) {Q=L;L=L->next;P=L;
