3.设计算法，实现单链表的就地逆置，即利用原表的存储空间将线性表（a1,a2,…,an）逆置为（an ,an-1,…,a1）。
第三章
一、 章节学习目标与要求
1、理解用栈和队列解决实际问题的方法。
2、掌握栈和队列的定义以及特性、它们的2种不同的存储表示方法（特别是顺序栈和循环队列）以及各种常见操作（如入、出操作）在不同表示方式上的实现。 二、本章重点、难点
重点：栈和队列的定义、各种表示和实现方法，加深对线性结构的理解 难点：循环队列的表示及为解决循环队列队空、队满判断条件相同而使用的不同实现方式；能在具体问题中灵活运用栈和队列结构。 三、章节练习 （一）选择题：
1．一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是________。
A. edcba 2．栈和队列的共同点是_______。
A. 都是后进先出 B. 都是先进先出
C. 都是只允许在端点处插入和删除元素 D.无共同点 3．一个队列的入队序列是{1,2,3,4},则队列的输出序列是______。 A. {4321} B. {1234} C. {1432} D. {3241}
4．栈的入栈序列是1，2，…，n，输出序列为p1,p2,…pn,若p1=n, 则pi为_____。
A. i B. n-i C. n-i+1 D. 不确定
5．队列是限定在________进行插入，在________进行删除的线性表。
A. 队头 B. 队尾 C. 任意位置
6．循环队列中，设队列元素依次存放在Q[0..m]中，f、r分别指示队头元素位置和队尾元素的下一个位置，约定存储m个元素时为队满。则队列空的判定方法是_______,队列满的判定方法是_______。
==r B. (f+1)%(m+1)==r C. (r+1)%(m+1)==f D. (r+1)% m==f （二）判断题：
栈和队列
1．若用户无法估计所用队列的最大长度，则最好采用链队列。 （ ）
2．在链队列上删除队头元素时，只需修改头结点中的指针，不必修改尾指针。 （ ）
3. 栈是限定仅在栈顶进行插入或删除操作的线性表。 （ ） 4. 队列是限定在队尾插入元素，在队头删除元素的线性表。 （ ） （三）问答与算法题：
1．对于一个栈，若输入序列依次为{A,B,C}, 试给出所有可能的输出序列。 2．假设将循环队列定义为：以整型域变量front和length分别指示循环队列中队头元素位置和队列中元素个数，指针elem指示存放队列元素的连续空间的首地址，写出相应的入队列和出队列的算法。
第四章
一、 章节学习目标与要求
1、理解串的抽象数据类型的定义以及相关术语、理解串在文本编辑中的作用。 2、掌握字符串的定义及各种基本操作的运算结果以及串的各种存储表示的特点。 二、本章重点、难点
重点：串的基本运算、串的各种存储表示和特点。继续加深对线性结构的理解 难点：串的不同存储结构，区分它们和高级语言中串的存储方式的不同。 三、章节练习 （一）选择题：
1．设串s=\则其串长是______。 A. 13 B. 14 C. 15 D. 16
2. 设s =\。则StrIndex(s,t,5)的返回值是_____。
A. 4 B. 5 C. 6 D. 9 E. 10 3. 串是一种特殊的线性表，其特殊性体现在_____。
A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符 4.已知串s=\’,则s的所有不同子串的个数为________。
A. 8 B. 9 C. 36 D. 37
5.设串s=\’,则s的第8个字符起、长度为7的子串为_______。
A. \ B. \ C. \ D. \
串
6. 设串s=\“good \则执行StrInsert(s,1,t)后，s为____。
A. \ B. \ C. \ D. \ （二）判断题：
1．空串和空格串是相同的。 （ ） 2. 如果两个串含有相同的字符，则它们是相同的。（ ）
3. 串的基本操作和线性表的一样，都是以“单个元素”作为操作对象的。 （ ） 4. 在串的链式存储结构中，结点大小与存储密度之间没有关系。 （ ）
第七章 树和二叉树
一、章节学习目标与要求
1、理解树、二叉树和森林的概念，理解线索化二叉树的特性、创建方法及在线索二叉树上寻找某结点的前驱和后继的方法；理解树与森林的存储方法。 2、掌握二叉树的性质及表示；掌握二叉树的各种遍历方法（尤其是递归形式的）以及遍历在实际问题中的应用；掌握树及森林与二叉树的转换及遍历方式的对应；掌握Huffman树的构造方法以及构造Huffman编码的方法。 二、本章重点、难点
重点：二叉树的性质（及证明）、存储结构及各种遍历算法，二叉树的线索化过程，树和森林与二叉树的转换关系，Huffman树及Huffman编码的构造方法 难点：各种遍历算法的递归实现以及在具体问题中能灵活运用遍历思想解题 三、章节练习 （一）选择题：
1．下列关于二叉树的说法中，正确的有_______。 A. 二叉树的度为2 B. 二叉树的度可以小于2
C.二叉树中至少有一个结点的度为2 D. 二叉树中任一个结点的度都为2 2．任何一棵二叉树的叶子结点在先、中、后序遍历序列中的相对次序_______。
A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对 3．下面几个符号串编码集合中，不是前缀编码的是_____。
A. {0，10，110，1111} B. {11，10，001，101，0001} C. {00，010，0110，1000} D. {b,c,aa,ac,aba,abb,abc}
4．二叉树按某种顺序线索化后，任意结点均有指向其前驱和后继的线索，这种说法_______。
A. 正确 B. 不正确 C. 无法确定 （二）判断题：
1.哈夫曼树是带权叶子数目固定的二叉树中带权路径长度最小的。 （ ） 2.根据二叉树的定义，具有3个结点的二叉树有5种不同的形态。 （ ） 3. 深度为k的完全二叉树至少有2k-1个结点，至多有2k－1个结点。 （ ） 4. 具有n个结点的满二叉树，其叶子结点个数为
n?1个。 （ ） 25. 在哈夫曼树中，通常权值较大的结点离根较远。 （ ） （三）问答题：
1．下图所示森林转化为相应的二叉树，并在其上标出中序全线索。
2．证明：深度为k的二叉树上至多有2k-1个结点（k≥1）。
3. 证明：任何一棵满二叉树中的分支数B满足B=2(n0－1)，其中n0为叶子结点个数。
4. 以数据集{15，3，14，2，6，9，16，17}为叶子的权值构造Huffman树，画出此树并计算其带权路径长度。 （四）算法题：
1. 假设二叉排序树（t为指向根结点的指针）中各元素值均不相同，设计一个递归算法按递增顺序输出树上各元素值。
2．编写递归算法, 交换二叉链表存储的二叉树中每个结点的左、右子树。 3. 编写递归算法，求以二叉链表存储的二叉树的深度。 4. 设计递归算法计算以二叉链表存储的二叉树的叶子结点数目。
第八章 图
一、章节学习目标与要求 1、理解图的基本概念和术语。
2、掌握图的邻接矩阵和邻接表2种表示方法；掌握图的两种遍历算法及其求解连通性问题的方法；掌握用Prim算法和Kruskal算法构造最小生成树的过程和性能分析；掌握AOV网的拓扑排序方法 (不要求算法)，掌握用Dijkstra方法求解单源最短路径问题的方法(不要求算法)。 二、本章重点、难点
重点：图的数组表示法和邻接表表示法存储结构以及图的两种遍历方式，求最小生成树的两种方法，AOV网的拓扑排序方法，掌握单源最短路径的求法 难点：图的两种遍历算法的实现以及在图的连通性问题中的应用 三、章节练习 （一）选择题：
1. 4个顶点的无向完全图有_______条边。
A. 6 B. 12 C. 16 D. 20 2．无向图的邻接矩阵是一个_____。
A. 对称矩阵 B. 零矩阵 C. 对角矩阵 D. 上三角矩阵 3．图的广度优先遍历算法类似于二叉树的_____，图的深度优先遍历算法类似于二叉树的_____。
A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层序遍历 4. 对________，用Prim算法求最小生成树较为合适，而Kruskal算法适于构造____________图的最小生成树。
A. 完全图 B. 连通图 C. 稀疏图 D.稠密图
5. 对于含n个顶点、e条边的无向连通图，利用Prim算法构造最小生成树的时间复杂度______________，用Kruskal算法构造最小生成树的时间复杂度为______________。
A. O(n) B. O(n2) C. O(e) D. O(eloge) F. O(e2) （二）判断题：
1. 若从无向图的一个顶点出发进行广度优先遍历可访问到图中所有顶点，则该图
郑州大学远程教育学院数据结构试题及答案
