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

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

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

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

4、式，简单程序的时间复杂度的求法。难点：时间复杂度的计算方法和原则。三、 章节练习（一）选择题：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(inext=NULL; B. p=NULL; C. p-next=head; D. p=head;4若在线性表的任何位置上插入元素的概率是相等的，那么在长度为 n 的顺序表中插入一个元素时需平均移动_个元素。A. n B. (n-1)/2 C.n/2 D. (n+1)/25在带头结点的非空单链表中，头结点的位置由_指示，首元结点的存储位置由_指示，除首元结点外，其它任一元素结点的

6、存储位置由_指示。A. 头指针 B. 头结点的指针域的指针 C.前驱结点的指针域的指针6. 单链表的头指针为 p，若有头结点，则表空的判断条件是_；若不带头结点，则表空的判断条件是_。A. p=NULL B. p-next=NULL C. p-next-next=NULL（二）判断题：1在单链表中插入或删除元素时是以结点的指针变化来反映逻辑关系的变化，因此不需要移动元素。 （ ）2 顺序表能够以元素在计算机内的物理位置的相邻性来表示线性表中元素之间的逻辑关系。 （ ）3. 在不带头结点的非空单链表中，首元结点的存储位置由头指针指示，除首元结点外，其它任一元素结点的存储位置由前驱结点的指针域的指

7、针指示。 （ ）（三）问答题：1若线性表要求以最快的速度存取而表中元素变动不大，则应采取什么存储结构（顺序或链式结构）？为什么？2若线性表经常做插入/删除操作，则应采取什么存储结构？为什么？3. 在单链表中设置头结点有什么作用？（四）算法题：1.设带头结点的单链表(L 为头指针)中的数据元素递增有序。设计算法，将 x插入到链表的适当位置上，并仍保持该表的有序性。2.设顺序表 va 中的数据元素递增有序。设计算法，将 x 插入到顺序表的适当位置上，并仍保持该表的有序性。3.设计算法，实现单链表的就地逆置，即利用原表的存储空间将线性表（a 1,a2,an）逆置为（a n ,an-1,a1） 。第三

8、章 栈和队列一、 章节学习目标与要求1、理解用栈和队列解决实际问题的方法。2、掌握栈和队列的定义以及特性、它们的 2 种不同的存储表示方法（特别是顺序栈和循环队列）以及各种常见操作（如入、出操作）在不同表示方式上的实现。二、本章重点、难点重点：栈和队列的定义、各种表示和实现方法，加深对线性结构的理解难点：循环队列的表示及为解决循环队列队空、队满判断条件相同而使用的不同实现方式；能在具体问题中灵活运用栈和队列结构。三、章节练习（一）选择题：1一个栈的入栈序列是 a,b,c,d,e,则栈的不可能的输出序列是_。A. edcba B.decba C.dceab D.abcde2栈和队列的共同点是_。

9、 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 C. n-i+1 D. 不确定5队列是限定在_进行插入，在_进行删除的线性表。A. 队头 B. 队尾 C. 任意位置6循环队列中，设队列元素依次存放在 Q0.m中，f、r 分别指示队头元素位置和队尾元素的下一个位置，约定存储 m 个元素时为队满。则队列空的判定方法是_

10、,队列满的判定方法是_。A.f=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 分别指示循环队列中队头元素位置和队列中

11、元素个数，指针 elem 指示存放队列元素的连续空间的首地址，写出相应的入队列和出队列的算法。第四章 串一、 章节学习目标与要求1、理解串的抽象数据类型的定义以及相关术语、理解串在文本编辑中的作用。2、掌握字符串的定义及各种基本操作的运算结果以及串的各种存储表示的特点。二、本章重点、难点重点：串的基本运算、串的各种存储表示和特点。继续加深对线性结构的理解难点：串的不同存储结构，区分它们和高级语言中串的存储方式的不同。三、章节练习（一）选择题：1设串 s=“I AM A STUDENT“, 则其串长是_。A. 13 B. 14 C. 15 D. 162. 设 s =“HE IS A WORKER

12、“,t=“WORKER“。则 StrIndex(s,t,5)的返回值是_。A. 4 B. 5 C. 6 D. 9 E. 103. 串是一种特殊的线性表，其特殊性体现在_。A. 可以顺序存储 B. 数据元素是一个字符C. 可以链接存储 D. 数据元素可以是多个字符4.已知串 s=“ABCDEFGH,则 s 的所有不同子串的个数为_。A. 8 B. 9 C. 36 D. 375.设串 s=“I am a teacher.,则 s 的第 8 个字符起、长度为 7 的子串为_。A. “teacher. “ B. “teacher“ C. “a teacher“ D. “ teacher“6. 设串 s

13、=“student.“,t=“good “,则执行 StrInsert(s,1,t)后，s 为_。A. “good student.“ B. “good student“ C. “goodstudent“ D. “ good teacher“（二）判断题：1空串和空格串是相同的。 （ ）2. 如果两个串含有相同的字符，则它们是相同的。 （ ）3. 串的基本操作和线性表的一样，都是以“单个元素”作为操作对象的。 （ ）4. 在串的链式存储结构中，结点大小与存储密度之间没有关系。 （ ）第七章 树和二叉树一、章节学习目标与要求1、理解树、二叉树和森林的概念，理解线索化二叉树的特性、创建方法及在线索

14、二叉树上寻找某结点的前驱和后继的方法；理解树与森林的存储方法。2、掌握二叉树的性质及表示；掌握二叉树的各种遍历方法（尤其是递归形式的）以及遍历在实际问题中的应用；掌握树及森林与二叉树的转换及遍历方式的对应；掌握 Huffman 树的构造方法以及构造 Huffman 编码的方法。二、本章重点、难点重点：二叉树的性质（及证明） 、存储结构及各种遍历算法，二叉树的线索化过程，树和森林与二叉树的转换关系，Huffman 树及 Huffman 编码的构造方法难点：各种遍历算法的递归实现以及在具体问题中能灵活运用遍历思想解题三、章节练习（一）选择题：1下列关于二叉树的说法中，正确的有_。A. 二叉树的度为

15、 2 B. 二叉树的度可以小于 2 C.二叉树中至少有一个结点的度为 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,ac,aba,abb,abc4二叉树按某种顺序线索化后，任意结点均有指向其前驱和后继的线索，这种说法_。 A. 正确 B. 不正确 C. 无法确定（二）判断题：1.哈夫曼树是带

16、权叶子数目固定的二叉树中带权路径长度最小的。 （ ）2.根据二叉树的定义，具有 3 个结点的二叉树有 5 种不同的形态。 （ ）3. 深度为 k 的完全二叉树至少有 2k-1 个结点，至多有 2k1 个结点。 （ ）4. 具有 n 个结点的满二叉树，其叶子结点个数为 个。 （ n）5. 在哈夫曼树中，通常权值较大的结点离根较远。 （ ）（三）问答题：1下图所示森林转化为相应的二叉树，并在其上标出中序全线索。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. 设计递归算法计算以二叉链表存储的二叉树的叶子结点数目。第八章 图一、章节学习目标与要求1、理解图的基本概念和术语。