郑州大学远程教育学院数据结构试题及答案

1、郑州大学远程教育学院数据结构试题及答案郑州大学现代远程教育 数据结构课程（本科） 学习指导书郭纯一 编课程内容与基本要求“数据结构”在计算机科学中是一门综合性的专业基础课。本课程将主要 介绍数据结构的基本概念和术语、非数值计算中常用的数据结构（线性表、栈 和队列、串、树和图）和基本技术（查找和排序方法）三大部分。本课程要求学生在掌握线性表、栈和队列、串、树和二叉树、图等基本数 据类型的基础上，会分析各种数据结构的特性，会根据应用需求为所涉及的数 据合理选择适当的逻辑结构和存储结构，并能据此设计实现问题的算法；还应 初步掌握算法的时间和空间效率的分析方法。课程学习进度与指导章节课程内容学时分配学

2、习指导（均以课件学习为主）第一章绪论4 学时重点掌握基本概念和时间复杂度的计算方法第二章*线性表10 学时重点掌握顺序结构和链式结构表示线性 表的方法和操作的实现；结合具体例子理 解编程实现一个问题的 2 种方法第三章栈和队列8 学时重点掌握栈和队列的特点以及它们各自 的存储表示，尤其是顺序栈和循环队列的 实现；结合具体例子理解栈和队列的应用第四章串2 学时重点掌握串的术语、串操作结果和不同存储结构的特点第七章*树和二叉树10 学时重点掌握二叉树的定义、存储、性质、遍 历算法（递归）及应用、线索化；掌握树 和森林与二叉树的转换以及 Huffman 树和 Huffman 编码的构造方法第八章图8

3、 学时重点掌握图的术语、存储、遍历算法及应 用；掌握最小生成树的 2 种构造方法及特 点、会求拓扑排序序列和单源最短路径第九章*查找8 学时重点掌握各种动态查找表的构造过程、性 能分析、插入 / 删除方法；掌握静态查找 表的顺序、折半和分块查找及 ASL求法第十章*排序8 学时掌握关于排序的术语及分类方法；重点掌 握插入排序、交换排序、选择排序等内排 序方法及其性能分析方法第一章 绪论一、章节学习目标与要求1、理解数据抽象和信息隐蔽原则2、掌握所有的基本概念和术语、掌握时间复杂度的计算方法、会用C语言描述抽象数据类型和算法；能够熟练使用 C 语言编写程序二、本章重点、难点重点：基本概念和术语，

4、 C 语言描述算法的方式， 简单程序的时间复杂度的求法。 难点：时间复杂度的计算方法和原则。三、 章节练习(一)选择题：1具有线性结构的数据结构是 。A. 图 B. 树 C. 集合 D.栈2计算机算法是指 。A. 计算方法和运算结果 B.调度方法C. 解决某一问题的有限运算系列D. 排序方法3线性结构中，最后一个结点有 个后继结点。A. 0 B. 1 C. 任意多4.算法分析的目的是 。A. 找出数据结构的合理性 B.研究算法中输入和输出的关系C. 分析算法的效率以求改进 D.分析算法的可读性和可行性5.具有非线性结构的数据结构是 。A. 图 B. 线性表 C. 串D. 栈6算法具有 5个特性

5、： 、 、输入和输出。A. 稳定性、确定性、可行性 B.有穷性、确定性、可行性C. 有穷性、安全性、可行性 D有穷性、确定性、可移植性7设 n 为正整数。则下面程序段的时间复杂度为 i=1; k=0;while(i=n-1) k+=10*i;i+;A. O(1) B. O(n) C. O(nlogn) D. O(n2)8设 n 为正整数。则下面程序段的时间复杂度为 。k=0; for(i=1;i=n;i+) for(j=i;jnext=NULL; B. p=NULL; C. p-next=head; D. p=head;4若在线性表的任何位置上插入元素的概率是相等的，那么在长度为n 的顺序表中

6、插入一个元素时需平均移动 个元素。A. n B. （n-1）/2 C.n/2 D. （n+1）/2 5在带头结点的非空单链表中，头结点的位置由 指示，首元结点的存储位置由 指示，除首元结点外，其它任一元素结点的存储位置由指示。A. 头指针 B. 头结点的指针域的指针 C. 前驱结点的指针域的指 针6. 单链表的头指针为 p，若有头结点，则表空的判断条件是 ；若不带头结点，则表空的判断条件是 。A. p=NULL B. p-next=NULL C. p-next-next=NULL（二）判断题： 1在单链表中插入或删除元素时是以结点的指针变化来反映逻辑关系的变化，因 此不需要移动元素。 （ ）2

7、 顺序表能够以元素在计算机内的物理位置的相邻性来表示线性表中元素之间 的逻辑关系。 （ ）3. 在不带头结点的非空单链表中，首元结点的存储位置由头指针指示，除首元结 点外，其它任一元素结点的存储位置由前驱结点的指针域的指针指示。 （ ） （三）问答题：1若线性表要求以最快的速度存取而表中元素变动不大，则应采取什么存储结构 （顺序或链式结构）？为什么？2若线性表经常做插入 / 删除操作，则应采取什么存储结构？为什么？3. 在单链表中设置头结点有什么作用？四）算法题：1. 设带头结点的单链表 （L 为头指针）中的数据元素递增有序。 设计算法，将 x 插 入到链表的适当位置上，并仍保持该表的有序性。

8、2. 设顺序表 va中的数据元素递增有序。设计算法，将 x 插入到顺序表的适当位 置上，并仍保持该表的有序性。3. 设计算法，实现单链表的就地逆置，即利用 原表的 存储空间将 线性表 （a1,a 2, ,a n）逆置为（ an ,a n-1, ,a 1）。第三章 栈和队列一、章节学习目标与要求1、理解用栈和队列解决实际问题的方法。2、掌握栈和队列的定义以及特性、它们的 2 种不同的存储表示方法（特别是顺 序栈和循环队列）以及各种常见操作（如入、出操作）在不同表示方式上的实 现。、本章重点、难点 重点：栈和队列的定义、各种表示和实现方法，加深对线性结构的理解 难点：循环队列的表示及为解决循环队列

9、队空、 队满判断条件相同而使用的不同 实现方式；能在具体问题中灵活运用栈和队列结构。三、章节练习（一）选择题：1 一个栈的入栈序列是a,b,c,d,e, 则栈的不可能的输出序列是A. edcba B.decba C.dceab D.abcde 2栈和队列的共同点是 。A. 都是后进先出 B. 都是先进先出C. 都是只允许在端点处插入和删除元素 D. 无共同点3一个队列的入队序列是 1,2,3,4, 则队列的输出序列是 。A. 4321 B. 1234 C. 1432 D. 32414栈的入栈序列是 1，2，n，输出序列为 p1,p2, pn,若 p1=n, 则 pi 为A. i B. n-i

10、C. n-i+1 D. 不确定5队列是限定在 进行插入，在 进行删除的线性表。A. 队头 B. 队尾 C. 任意位置 6循环队列中，设队列元素依次存放在 Q0.m 中，f 、r 分别指示队头元素位 置和队尾元素的下一个位置，约定存储 m 个元素时为队满。则队列空的判定方 法是 ,队列满的判定方法是 。A.f=r B. （f+1）%（m+1）=r C. （r+1）%（m+1）=f D. （r+1）% m=f （二）判断题： 1若用户无法估计所用队列的最大长度，则最好采用链队列。（）2在链队列上删除队头元素时， 只需修改头结点中的指针， 不必修改尾指针。 （ ）3. 栈是限定仅在栈顶进行插入或删除

11、操作的线性表。（）4. 队列是限定在队尾插入元素，在队头删除元素的线性表。（）（三）问答与算法题： 1对于一个栈，若输入序列依次为 A,B,C, 试给出所有可能的输出序列。 2假设将循环队列定义为：以整型域变量 front 和 length 分别指示循环队列中 队头元素位置和队列中元素个数， 指针 elem 指示存放队列元素的连续空间的首地 址，写出相应的入队列和出队列的算法。第四章 串一、章节学习目标与要求1、理解串的抽象数据类型的定义以及相关术语、理解串在文本编辑中的作用。2、掌握字符串的定义及各种基本操作的运算结果以及串的各种存储表示的特 点。二、本章重点、难点 重点：串的基本运算、串的

12、各种存储表示和特点。继续加深对线性结构的理解 难点：串的不同存储结构，区分它们和高级语言中串的存储方式的不同。三、章节练习 （一）选择题：1设串 s=I AM A STUDENT, 则其串长是 。A. 13 B. 14 C. 15 D. 162. 设 s =HE IS A WORKER,t=WORKE。R则 StrIndex（s,t,5） 的返回值是 。A. 4 B. 5 C. 6 D. 9 E. 103. 串是一种特殊的线性表，其特殊性体现在 。A. 可以顺序存储 B. 数据元素是一个字符C. 可以链接存储 D. 数据元素可以是多个字符4. 已知串 s=ABCDEFGH,则 s的所有不同子串

13、的个数为 A. 8 B. 9 C. 36 D. 375. 设串s=I ama teacher. ,则s的第8个字符起、长度为 7的子串为6. 设串 s=student.,t=A. teacher. B. teacher C. a teacher D. teachergood , 则执行 StrInsert(s,1,t)后， s 为A. good student.B. good studentC. goodstudentD. good teacher二）判断题：1空串和空格串是相同的2.如果两个串含有相同的字符，则它们是相同的3.串的基本操作和线性表的一样， 都是以“单个元素”作为操作对象的4.

14、第七章树和二叉树在串的链式存储结构中，结点大小与存储密度之间没有关系。、章节学习目标与要求1、理解树、二叉树和森林的概念，理解线索化二叉树的特性、创建方法及在线索二叉树上寻找某结点的前驱和后继的方法；理解树与森林的存储方法。2、掌握二叉树的性质及表示； 掌握二叉树的各种遍历方法 （尤其是递归形式的）以及遍历在实际问题中的应用；掌握树及森林与二叉树的转换及遍历方式的对应；掌握 Huffman 树的构造方法以及构造 Huffman 编码的方法。、本章重点、难点重点：二叉树的性质（及证明） 、存储结构及各种遍历算法，二叉树的线索化过程，树和森林与二叉树的转换关系，Huffman 树及 Huffman

15、 编码的构造方法难点：各种遍历算法的递归实现以及在具体问题中能灵活运用遍历思想解题 三、章节练习一）选择题：1下列关于二叉树的说法中，正确的有 。A. 二叉树的度为 2 B. 二叉树的度可以小于 2C. 二叉树中至少有一个结点的度为 2 D. 二叉树中任一个结点的度都为 22任何一棵二叉树的叶子结点在先、中、后序遍历序列中的相对次序A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对 3下面几个符号串编码集合中，不是前缀编码的是 。A. 0 ，10，110，1111 B. 11 ，10，001，101， 0001C. 00 ， 010， 0110， 1000 D. b,c,aa,

16、ac,aba,abb,abc 4二叉树按某种顺序线索化后，任意结点均有指向其前驱和后继的线索，这种 说法 。A. 正确 B. 不正确 C. 无法确定二）判断题：1. 哈夫曼 树是带权叶子 数目固定的 二叉 树中带 权路 径长 度 最小 的。（）2. 根据二叉树的定义，具有 3个结点的二叉树有 5种不同的形态。（ ）3. 深度为 k 的完全二叉树至少有 2k-1个结点，至多有 2k1 个结点。（ ）4. 具有 n 个结点的满二叉树，其叶子结点个数为 n 1 个。 （ ）25. 在哈夫曼树中， 通常权值较大的结点离根较远。 （ ） 三）问答题：1下图所示森林转化为相应的二叉树，并在其上标出中序全线

17、索。2证明：深度为 k的二叉树上至多有 2k-1 个结点（ k1）3. 证明：任何一棵满二叉树中的分支数 B满足 B=2（n01） ，其中 n0为叶子结点 个数。4. 以数据集 15，3，14，2，6，9，16，17为叶子的权值构造 Huffman 树，画 出此树并计算其带权路径长度。（四）算法题：1. 假设二叉排序树（ t 为指向根结点的指针）中各元素值均不相同，设计一个 递归算法按递增顺序输出树上各元素值。2编写递归算法 , 交换二叉链表存储的二叉树中每个结点的左、右子树。3. 编写递归算法，求以二叉链表存储的二叉树的深度。4. 设计递归算法计算以二叉链表存储的二叉树的叶子结点数目。第八章

18、 图一、章节学习目标与要求1、理解图的基本概念和术语。2、掌握图的邻接矩阵和邻接表 2 种表示方法；掌握图的两种遍历算法及其求解 连通性问题的方法；掌握用 Prim 算法和 Kruskal 算法构造最小生成树的过程和 性能分析；掌握 AOV网的拓扑排序方法 （ 不要求算法 ） ，掌握用 Dijkstra 方法 求解单源最短路径问题的方法 （不要求算法 ）。二、本章重点、难点 重点：图的数组表示法和邻接表表示法存储结构以及图的两种遍历方式，求最小 生成树的两种方法， AOV网的拓扑排序方法，掌握单源最短路径的求法 难点：图的两种遍历算法的实现以及在图的连通性问题中的应用三、章节练习（一）选择题：

19、1. 4 个顶点的无向完全图有 条边。A. 6 B. 12 C. 16 D. 202无向图的邻接矩阵是一个 。A. 对称矩阵 B. 零矩阵 C. 对角矩阵 D. 上三角矩阵 3图的广度优先遍历算法类似于二叉树的 ，图的深度优先遍历算法类似于二叉树的 。A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层序遍历4. 对 ，用 Prim 算法求最小生成树较为合适，而 Kruskal 算法适于构造图的最小生成树。A. 完全图 B. 连通图 C. 稀疏图 D. 稠密图5. 对于含 n 个顶点、 e 条边的无向连通图，利用 Prim 算法构造最小生成树的时6. 连通分量是无向图的极大连通子图， 而生

20、成树是无向图的极小连通子图。 （ ） 三）问答及算法题：0101. 一个图的邻接矩阵 G.arcs= 1 0 1 ， 011是有向图，该图共有多少条弧？如果是无向图，2. 已知如右图所示的有向图，写出该图的 :（1） 邻接矩阵 （2 ）一个可能的拓扑有序序列 出从 1 出发的深度优先遍历序列 （4）写出从 5 出发 的广度优先遍历序列。3. 假设有 5 项活动 C1C5，每项活动要求的前驱活动如下：C1 ：无； C2：C1，C3； C3 ：C1； C4 ：C3，C5 C5 ：C2；该图有多少个顶点？如果该图共有多少条边间复杂度 ，用 Kruskal 算法构造最小生成树的时间复杂度为试根据上述关

21、系，画出相应的有向图，再写出一个拓扑排序序列4. 基于图的深度优先遍历策略写一算法， 判断以邻接表方式存储的无向图中连通 分量的个数。第九章 查找一、章节学习目标与要求1、理解各种查找表的定义、 各种查找方法的思想以及构造查找表所依据的原则。2、掌握线性表表示的静态查找表的顺序查找和折半查找算法及其性能分析方 法；掌握二叉排序树的创建、查找、插入、删除算法及其性能分析方法；掌握 AVL 树的平衡化旋转方法及其性能分析；掌握 B-树的插入和删除时结点的分裂 和合并方法；掌握 Hash法的查找、构造方法平均查找长度的计算方法。二、本章重点、难点重点：各种树结构表示的动态查找表和 Hash 表的构造

22、方法 难点：二叉排序树的删除、 AVL树的旋转处理、 B-树的插入和删除、 Hash 法的构 造以及各种查找表的平均查找长度的计算方法三、章节练习(一)选择题：1. 二叉排序树可得到一个关键字的有序序列。A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层序遍历2用链地址法处理冲突构造的散列表中，每个地址单元所链接的同义 词表中结点的 相同。A. 关键字 B. 元素值 C. 散列地址 D. 含义3利用折半查找方法在长度为 n 的有序表中查找一个元素的平均查找 长度是 。A.O(n 2) B.O(nlogn) C.O(n) D. O(logn)4散列表的装填因子越大，则发生冲突的可能性就 。

23、A. 越小 B. 越大 C. 不确定5线性表中共有 256 个元素，采用分块查找，若查找每个元素的概率 相等，用顺序查找确定结点所在的块， 每块有 个元素时查找效率最佳。A. 16 B. 20 C. 25 D. 2566用折半查找对长度为 7 的有序表进行查找，则等概率下查找成功时 的平均查找长度为 。A. 15/7 B. 17/7 C. 18/7 D. 19/77有序表（ 1，32， 41，45， 62，75，77，82，95， 100），使用折半查找关键 字为 95 的元素时，需要经过 次比较后才能查找成功。A. 2 B. 3 C. 4 D.5二）判断题：1. 折半查找和二叉排序树的查找时

24、间性能一样。 （ ）2. 在任意一棵非空的二叉排序树中， 删除某结点后又将其插入， 则所得的二叉排 序树与删除前的二叉排序树形态相同。 （ ）3. 根据 B-树的定义，在 9 阶 B-树中，除根以外的任何一个非叶子结点中的关键 字数目均在 59 之间。（ ）4. 折半查找时，要求线性表必须是有序的且以顺序结构存储。（ ）三）问答题：1. 设有一组关键字序列 19 ，1，23，14，55，20，84，27，68，11，40，（ 1） 按表中元素顺序构造一棵二叉排序树，画出这棵树，并求其在等概 率情 况下查找成功时的平均查找长度。（2）从空树开始，按表中元素顺序构造一棵 2_3 树（3 阶 B_树

25、） ，若此后再删除 55，84，画出每一步执行后 2_3 树的状态。2. 设散列函数 H（key）=key MOD 7, 用线性探测再散列法解决冲突。对关键字序 列 13 ，28，72，5，16，8，7，11 在地址空间为 0-10 的散列区中建散列 表，画出此表，并求等概率情况下查找成功时的平均查找长度。3. 关键字序列： 13，28，72，5，16，18，7，11，24，h （key） = key mod 11, 表长为 11，用线性探测再散列处理冲突， 试填写下表并计算每个关键字的比 较次数和等概率情况下查找成功时的平均查找长度。0 1 2 3 4 5 6 7 8 9 10哈希表比较 次

26、数ASL=4. 在地址空间为 0-16 的散列区中，对以下关键字序列 (Jan,Feb,Mar,Apr,May, June,July,Aug,Sep,Oct,Nov,Dec) 按链地址法处理冲突构造散列表，设散列函 数 H(x)=i/2, 其中 i 为关键字中第一个字母在字母表中的序号。 画出该散列表并 求在等概率情况下查找成功时的平均查找长度。第十章 排序一、章节学习目标与要求 1、理解排序相关的定义以及排序方法的各种分类，理解各种排序方法的基本思 想和依据原则。2、掌握内部排序的基本概念和性能分析方法；掌握插入排序、交换排序、选择 排序等内排序的方法及其性能分析方法。二、本章重点、难点 重

27、点：各类内部排序方法所依据的原则、特点及典型算法。 难点：希尔排序、快速排序、堆排序三、章节练习(一)选择题：1. 下列方法中， 是稳定的排序方法。A堆排序 B. 希尔排序 C. 快速排序 D. 折半插入排序2. 设有 1000 个无序的元素，希望用最快的速度选出其中前 20 个最大的 元素，最好用 排序方法。A. 冒泡排序 B. 快速排序 C. 堆排序 D. 希尔排序 3下列序列中， 是堆。A. 12 ，35，20，60，40，30 B. 100 ，85，120，38，10，9，36C. 1 ，5，6，24，7，3，4 D. 38，24，15，20，30，464在待排序的元素序列基本有序时，

28、效率最高的排序方法是 _ 。A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序 5在下列排序方法中，某一趟结束后未必能选出一个元素放在其最终位置上的A. 堆排序 B. 起泡排序 C. 快速排序 D. 直接插入排序6 对序列22,86,19,49,12,30,65,35,18进行一趟排序后得到的结 果为18,12,19,22,49,30,65,35,86 ，则其使用的排序方法为 。A. 插入排序 B. 选择排序 C. 快速排序 D. 起泡排序7. 下列方法中， 算法的时间复杂度为 O(n2) 。A. 堆排序 B. 希尔排序 C. 快速排序 D. 直接插入排序8. 对 n 个记录的序列

29、进行堆排序，最坏情况下的时间复杂度为 。A. O(logn) B. O(nlogn) C. O(n) D.O(n2)二)判断题：1. 快速排序的速度在所有排序方法中是最快的，而且所需的附加空间也最少。()2. 对一个堆按层次遍历，不一定能得到一个有序序列。 ( )3. 由于希尔排序的最后一趟与直接插入排序过程相同，所以前者一定比后者花 费的时间多。 ( )4. 快速排序算法在待排序数据有序时最不利于发挥其长处。 ( )三) 问答题：1. 在快速排序过程中，通常取序列中的第 1 个记录作为枢轴，以它为“分界线” 重排其余记录。但当初始记录序列按关键字有序或基本有序时，快速排序将蜕 化为起泡排序，

30、为改进之，应如何选取枢轴记录？2. 判断以下序列是否是堆，若不是，把它调整为堆(要求记录交换次数最少) ， 写出调整后的序列。1) 5 ，26，20，60，80，35，53，70 2) 26 ，33，35，29，19，12，22 3. 已知关键字序列 70，83，100，65，10，9，7，32，写出直接插入排序和快 速排序每一趟结束时的关键字状态。4. 设关键字集合为 10，2，14，8，12，13，(1) 写出用希尔排序方法对序列排序时每一趟结束时的关键字状态。(2) 用堆排序方法对其从小到大排序，画出堆排序的初态、建堆和排序过程中重 建堆的过程。考试模拟题客观题部分一、单项选择题：(每空

31、 2分，共 20 分)1. 单链表是线性表的一种 的存储结构。A. 顺序存取 B. 随机存取 C. 索引存取2. 栈和队列的共同点是 。A. 都是后进先出 B. 都是先进先出C. 都是只允许在端点处插入和删除元素 D. 无共同点3. 设 s=HE IS A WORKER,t=WORKER。 则index(s,t,5) 的返回值是 。A. 4 B. 5 C. 6 D. 9 E. 104. 串是一种特殊的线性表，其特殊性体现在 。A. 可以顺序存储 B. 数据元素是一个字符C. 可以链接存储 D. 数据元素可以是多个字符5树最适合用来表示 。A. 有序数据元素 B. 无序数据元素C素之间具有分支层

32、次关系的数据 D. 元素之间无关联的数据64 个顶点的无向完全图有 条边。A. 6 B. 12 C. 16 D. 207散列表的装填因子越大，则发生冲突的可能性就 。A. 越小 B. 越大 C. 不确定8. 在长度为 n 的有序表中折半查找一个元素的平均查找长度是 。A.O(n2) B.O(nlogn) C.O(n) D. O(logn)9. 下列方法中， 是不稳定的排序方法。A. 折半插入排序 B. 直接插入排序 C. 冒泡排序 D. 堆排序 10二叉排序树可得到一个关键字的有序序列。A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层序遍历 二、是非题：(每题 1分，共 10 分)(说

33、明：正确的选“ A”, 错误选“ B” ) 1线性表的顺序存储结构优于链式存储结构。( )2 空 串和空格串是相同的。（）3 图 结构中，每个结点的前驱和后续都可以有任意多个。（）4 快 速排序算法在待排序数据有序时最不利于发挥其长处。（）5 连 通网的最小生成树是唯一的。（）6栈是 FIFO的线性表。 （ ） 7 由 二叉树的先序和后序遍历序列不能唯一确定这棵二叉树。 （ ） 8若从无向图的一个顶点出发进行广度优先遍历可访问到图中的所有顶点， 则该图一定是连通图。（ ）9折半查找方法要求查找表必须是关键字的有序表，但是对存储结构没有限 制。（ ）10在一棵非空二叉树的中序遍历序列中， 根结点

34、的右边只有其右子树上的所有结点主观题部分一、简答题：（ 50 分）则应采取什么存储1. 若线性表要求以最快的速度存取而表中元素变动不大， 结构（顺序或链式结构）？为什么？（ 10 分）2. 将下图所示森林转化为二叉树并在其上标出中序全线索。 （10分）10 分）3. 已知如右图所示的有向图，写出该图的（1） 邻接矩阵 （2 ）一个可能的拓扑有序序列4设散列函数 H（key）=key MOD 7, 用线性探测再散列法解决冲突。对关键字 序列 13 ，28，72，5，16，8，7，9，11，29 在地址空间为 0-10 的散列区 中建散列表，画出此表，并求等概率情况下查找成功时的平均查找长度。 （

35、 10 分）5对于序列 26 ，33，35，29，19，12，22 ， （1）判断它是否是堆，若是，写出其是大顶堆还是小顶堆；若不是，把它调 整为堆，写出调整的过程和调整后的序列。（5 分）（2）写出对该序列进行直接插入排序每一趟结束时的关键字状态。 （5 分）二、算法设计题：（20 分）1、编写递归算法，计算二叉链表存储的二叉树的结点数目。 （10 分）2、基于图的深度优先遍历策略写一算法，判断以邻接表方式存储的无向图中 连通分量的个数。 （10 分）附：答案或答案要点第一章章节练习答案 一）选择题： 1D 2C 3 A ）判断题： 1第二章章节练习答案一）选择题： 1 B, 二）判断题：

36、1 三）问答题： 1 应采用顺序结构。4 C 5A 6B2 3. 47B8 DA2 C3C4C235A, B, C6.B, A因为顺序表是随机存取的存储结构，元素所花的时间都一样。而链表是顺序存取的存储结构在顺序表中存取任何2 应采用链式结构。因为在链表中是以结点的指针变化来反映逻辑关系的变 化，因此不需要移动元素，效率高。3头结点在位置上可视为首元结点的前驱，则做插入 /输出操作时， i=1（即插 入或删除的位置是 1）时不需要做特别处理，否则 i=1 时需要修改头指针。四）算法题：1 status insert_L (LinkList L, ElemType x)/* 带头结点*/Link

37、List p,s;for (p=L; p-next & p-next-datanext);s=(LinkList )malloc(sizeof(LNode); if (!s) return OVERFLOW;s-data=x; s-next=p-next; p-next=s;return OK;2status insert_Sq(SqList *va,ElemType x)int i;if( va-length=va-listsize) exit OVERFLOW; for( i=va-length-1;i=0 & va-elemix;-i)va-elemi+1= va-elemi;va-el

38、emi+1=x; va-length+;return OK;3void reverse(LinkList L)/* 带头结点 */LinkList p;p=L-next; L-next=NULL;for(; p; p=p-next)q=p-next;p-next=L-next;L-next=p;第三章章节练习答案(一) 选择题： 1.C 2.C 3. B 4.C 5. B, A6. A，C(二) 判断题： 123 4 (三) 问答与算法题：1 所有可能的输出序列有： ABC、 ACB、BAC、BCA、 CBA 2算法：#define MAXQSIZE 100typedef struct Ele

39、mType *elem;int front;int length;CycQueue;status EnQueue(CycQueue *Q, ElemType e)if (Q-length=MAXQSIZE) return ERROR; Q-elem(Q-front+Q-length) % MAXQSIZE=e; Q-length+;return OK;status DeQueue(CycQueue *Q, ElemType *e)if (Q-length=0) return ERROR;*e= Q-elemQ-front;Q-length - -; return OK;3. B 4. D 5.

40、 B 6. A第四章章节练习答案一）选择题： 1. B 2. D)判断题： 1. 2. 3. 4. 第七章章节练习答案（一）选择题： 1. B 2. A 3. B 4. B二）判断题： 1. 2. 3. 4. 5.三）问答题：12证明：由于深度为 k 的二叉树的最大结点数为二叉树上每一层的最大结点数 之和，而二叉树上第 i 层的最大结点数为 2i-1。则kk（第i层的最大结点数 ）2i-1 2 k 1i 1 i 13. 证明：设 n0为叶子结点个数， n2为度为 2 的结点个数， 则由二叉树的性质 2可知： n2= n01 又：满二叉树中只有度为 2 的结点和叶子结点， 所以满二叉树中的结点总

41、数 n= n2+ n0=2 n01 又：二叉树中的分支数 B=n 1所以： B=2 n011=2（n01）4.wpl=(16+17)*2+(9+14+15)*3+6*4+(2+3)*5=229四) 算法题：1void output(BiTree t)if (t)output(t-lchild); printf(t-data); output(t-rchild);2. void exchange(BiTree t)BiTree temp;if (t)temp=t-lchild; t-lchild= t-rchild; t-rchild=temp; exchange (t- lchild);exc

42、hange (t-rchild);3. int depth(BiTree t)int l,r;if (!t) return 0;l= depth (t-lchild);r= depth (t-rchild);return (l=r?l:r)+1;4. void leaf(BiTree t) if (!t) return 0;if (!t-lchild & !t-rchild) return 1;return leaf(t-lchild)+leaf(t-rchild);第八章章节练习答案（一）选择题： 1.A 2.A 3.D, A 4.D, C 5.B, D二）判断题 : 1. 2. 3. 4.

43、 5. 6. 三）问答及算法题：1. 图中共有 3 个顶点，如果是有向图，该图共有 5 条弧；如果是无向 图，该图共有 3 条边。0100000010000001002.（ 1）邻接矩阵： 0000000010001000100（2）可能的拓扑序列为：156234（注意 4一定是最后一个， 2 一定在 1 和 5 后）3)1234564)5624313. 一个拓扑排序序列： C1 C3 C2 C5 C44算法：int count (AlGraph G)for (i=0; iG .vexnum; i+) visitedi=false; sum=0;for (i=0; inextarc) k=p-

44、adjvex;if (!visitedk) dfs(G , k); 第九章章节练习答案（一）选择题： 1.B 2.C 3.D 4.B 5.A 6. B 7. B 二）判断题： 1. 2. 3. 4. 三）问答题：1.（1）ASL=(1+2*2+3*3+3*4+2*5)/11=36/11(2) 2_3 树:删除 84:(3) 删除 55:2ASL=(1+1+1+2+5+1+1+4)/8=16/8=23.3、012345678910哈希表1113245287216187比较112112434次数ASL= (1+1+2+1+1+2+4+3+4)/9=19/94. 用链地址法处理冲突 : （注意链表的

45、有序性）ASL=(7*1+4*2+1*3)/12=18/12第十章章节练习答案（一）选择题： 1.D 2.C 3.A 4.A 5.D 6.C 7.D 8.B二）判断题： 1. 2. 3. 4. 三）问答题：1 应依据“三者取中”的原则，比较第一个、最后一个和中间位置处记录的关键字，取关键字居中值的记录作为枢轴记录。2第一个序列是堆第二个序列不是堆。调整为堆后的序列为 35，33，26，29，19，12， 223初始序列： 70，83，100，65，10，9， 7，32直接插入排序每一趟结束时的关键字状态：第一趟：（70，83），100，65，10，9，7，32第二趟：（70，83，100），65，10，9，7，32第三趟：（65，70，83，100），10，9，7，32第四趟：（10，65，70，83，100），9，7，32第五趟：（9，10，65，70，83，100），7，32第六趟：（7，9，10，65，70，83，100），32第七趟：（7，9，10，32，6