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

郑州大学现代远程教育《数据结构》课程（本科）学习指导书郭纯一编课程内容与基本要求“数据结构”在计算机科学中是一门综合性的专业基础课。本课程将主要介绍数据结构的基本概念和术语、非数值计算中常用的数据结构（线性表、栈和队列、串、树和图）和基本技术（查找和排序方法）三大部分。本课程要求学生在掌握线性表、栈和队列、串、树和二叉树、图等基本数据类型的基础上，会分析各种数据结构的特性，会根据应用需求为所涉及的数据合理选择适当的逻辑结构和存储结构，并能据此设计实现问题的算法；还应初步掌握算法的时间和空间效率的分析方法。课程学习进度与指导章节课程内容学时分配学习指导（均以课件学习为主）第一章绪论4学时重点掌握基本概念和时间复杂度的计算方法第二章*线性表10学时重点掌握顺序结构和链式结构表示线性表的方法和操作的实现；结合具体例子理解编程实现一个问题的2种方法第三章栈和队列8学时重点掌握栈和队列的特点以及它们各自的存储表示，尤其是顺序栈和循环队列的实现；结合具体例子理解栈和队列的应用第四章串2学时重点掌握串的术语、串操作结果和不同存储结构的特点第七章*树和二叉树10学时重点掌握二叉树的定义、存储、性质、遍历算法（递归）及应用、线索化；掌握树和森林与二叉树的转换以及Huffman树和Huffman编码的构造方法第八章图8学时重点掌握图的术语、存储、遍历算法及应用；掌握最小生成树的2种构造方法及特点、会求拓扑排序序列和单源最短路径第九章*查找8学时重点掌握各种动态查找表的构造过程、性能分析、插入/删除方法；掌握静态查找表的顺序、折半和分块查找及ASL求法第十章*排序8学时掌握关于排序的术语及分类方法；重点掌握插入排序、交换排序、选择排序等内排序方法及其性能分析方法第一章绪论一、章节学习目标与要求1、理解数据抽象和信息隐蔽原则2、掌握所有的基本概念和术语、掌握时间复杂度的计算方法、会用C语言描述抽象数据类型和算法；能够熟练使用C语言编写程序二、本章重点、难点重点：基本概念和术语，C语言描述算法的方式，简单程序的时间复杂度的求法。难点：时间复杂度的计算方法和原则。三、章节练习（一）选择题：1．具有线性结构的数据结构是__________。A.图B.树C.集合D.栈2．计算机算法是指________。A.计算方法和运算结果B.调度方法C.解决某一问题的有限运算系列D.排序方法3．线性结构中，最后一个结点有________个后继结点。A.0B.1C.任意多4.算法分析的目的是________。A.找出数据结构的合理性B.研究算法中输入和输出的关系C.分析算法的效率以求改进D.分析算法的可读性和可行性5.具有非线性结构的数据结构是__________。A.图B.线性表C.串D.栈6．算法具有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;j=n;j++)@k++;}A.O(1)B.O(n)C.O(nlogn)D.O(n2)（二）判断题：1．在数据结构中，从逻辑上可以把数据结构分为动态结构和静态结构两大类。（）2．任何一个算法的设计取决于数据的逻辑结构，而算法的实现则依赖于所采用的存储结构。（）3.数据元素是数据的不可分割的最小单位。（）4.算法分析的两个主要方面是时间复杂度和空间复杂度。（）第二章线性表一、章节学习目标与要求1、理解线性表的逻辑结构特性、顺序表和链表表示线性表的优缺点、循环链表和双向链表的特点。2、掌握线性表的两种存储方式及其实现：熟练掌握顺序表和链表的创建、插入元素、删除元素以及定位等常用操作的实现算法并会求相应算法的时间复杂度。二、本章重点、难点重点：线性表的特点、两种表示方式及它们的运算实现，会求算法的时间复杂度。难点：单链表结构、特点及其实现三、章节练习（一）选择题：1．顺序表是一种________的存储结构，单链表是________的存储结构。A.顺序存取B.随机存取C.索引存取2．顺序表中第一个元素的起始存储地址为100，每个元素的长度为4，则第五个元素的起始地址是_______。A.105B.110C.116D.1203．非空循环单链表(head为头指针)的尾结点（由指针p所指示）应满足________。A.p-next==NULL;B.p==NULL;C.p-next==head;D.p==head;4．若在线性表的任何位置上插入元素的概率是相等的，那么在长度为n的顺序表中插入一个元素时需平均移动________个元素。A.nB.(n-1)/2C.n/2D.(n+1)/25．在带头结点的非空单链表中，头结点的位置由________指示，首元结点的存储位置由________指示，除首元结点外，其它任一元素结点的存储位置由________指示。A.头指针B.头结点的指针域的指针C.前驱结点的指针域的指针6.单链表的头指针为p，若有头结点，则表空的判断条件是______________；若不带头结点，则表空的判断条件是______________。A.p==NULLB.p-next==NULLC.p-next-next==NULL（二）判断题：1．在单链表中插入或删除元素时是以结点的指针变化来反映逻辑关系的变化，因此不需要移动元素。（）2．顺序表能够以元素在计算机内的物理位置的相邻性来表示线性表中元素之间的逻辑关系。（）3.在不带头结点的非空单链表中，首元结点的存储位置由头指针指示，除首元结点外，其它任一元素结点的存储位置由前驱结点的指针域的指针指示。（）（三）问答题：1．若线性表要求以最快的速度存取而表中元素变动不大，则应采取什么存储结构（顺序或链式结构）？为什么？2．若线性表经常做插入/删除操作，则应采取什么存储结构？为什么？3.在单链表中设置头结点有什么作用？（四）算法题：1.设带头结点的单链表(L为头指针)中的数据元素递增有序。设计算法，将x插入到链表的适当位置上，并仍保持该表的有序性。2.设顺序表va中的数据元素递增有序。设计算法，将x插入到顺序表的适当位置上，并仍保持该表的有序性。3.设计算法，实现单链表的就地逆置，即利用原表的存储空间将线性表（a1,a2,…,an）逆置为（an,an-1,…,a1）。第三章栈和队列一、章节学习目标与要求1、理解用栈和队列解决实际问题的方法。2、掌握栈和队列的定义以及特性、它们的2种不同的存储表示方法（特别是顺序栈和循环队列）以及各种常见操作（如入、出操作）在不同表示方式上的实现。二、本章重点、难点重点：栈和队列的定义、各种表示和实现方法，加深对线性结构的理解难点：循环队列的表示及为解决循环队列队空、队满判断条件相同而使用的不同实现方式；能在具体问题中灵活运用栈和队列结构。三、章节练习（一）选择题：1．一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是________。A.edcbaB.decbaC.dceabD.abcde2．栈和队列的共同点是_______。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.iB.n-iC.n-i+1D.不确定5．队列是限定在________进行插入，在________进行删除的线性表。A.队头B.队尾C.任意位置6．循环队列中，设队列元素依次存放在Q[0..m]中，f、r分别指示队头元素位置和队尾元素的下一个位置，约定存储m个元素时为队满。则队列空的判定方法是_______,队列满的判定方法是_______。A.f==rB.(f+1)%(m+1)==rC.(r+1)%(m+1)==fD.(r+1)%m==f（二）判断题：1．若用户无法估计所用队列的最大长度，则最好采用链队列。（）2．在链队列上删除队头元素时，只需修改头结点中的指针，不必修改尾指针。（）3.栈是限定仅在栈顶进行插入或删除操作的线性表。（）4.队列是限定在队尾插入元素，在队头删除元素的线性表。（）（三）问答与算法题：1．对于一个栈，若输入序列依次为{A,B,C},试给出所有可能的输出序列。2．假设将循环队列定义为：以整型域变量front和length分别指示循环队列中队头元素位置和队列中元素个数，指针elem指示存放队列元素的连续空间的首地址，写出相应的入队列和出队列的算法。第四章串一、章节学习目标与要求1、理解串的抽象数据类型的定义以及相关术语、理解串在文本编辑中的作用。2、掌握字符串的定义及各种基本操作的运算结果以及串的各种存储表示的特点。二、本章重点、难点重点：串的基本运算、串的各种存储表示和特点。继续加深对线性结构的理解难点：串的不同存储结构，区分它们和高级语言中串的存储方式的不同。三、章节练习（一）选择题：1．设串s=IAMASTUDENT,则其串长是______。A.13B.14C.15D.162.设s=HEISAWORKER,t=WORKER。则StrIndex(s,t,5)的返回值是_____。A.4B.5C.6D.9E.103.串是一种特殊的线性表，其特殊性体现在_____。A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符4.已知串s=ABCDEFGH’,则s的所有不同子串的个数为________。A.8B.9C.36D.375.设串s=Iamateacher.’,则s的第8个字符起、长度为7的子串为_______。A.teacher.B.teacherC.ateacherD.teacher6.设串s=student.,t=“good,则执行StrInsert(s,1,t)后，s为____。A.goodstudent.B.goodstudentC.goodstudentD.goodteacher（二）判断题：1．空串和空格串是相同的。（）2.如果两个串含有相同的字符，则它们是相同的。（）3.串的基本操作和线性表的一样，都是以“单个元素”作为操作对象的。（）4.在串的链式存储结构中，结点大小与存储密度之间没有关系。（）第七章树和二叉树一、章节学习目标与要求1、理解树、二叉树和森林的概念，理解线索化二叉树的特性、创建方法及在线索二叉树上寻找某结点的前驱和后继的方法；理解树与森林的存储方法。2、掌握二叉树的性质及表示；掌握二叉树的各种遍历方法（尤其是递归形式的）以及遍历在实际问题中的应用；掌握树及森林与二叉树的转换及遍历方式的对应；掌握Huffman树的构造方法以及构造Huffman编码的方法。二、本章重点、难点重点：二叉树的性质（及证明）、存储结构及各种遍历算法，二叉树的线索化过程，树和森林与二叉树的转换关系，Huffman树及Huffman编码的构造方法难点：各种遍历算法的递归实现以及在具体问题中能灵活运用遍历思想解题三、章节练习（一）选择题：1．下列关于二叉树的说法中，正确的有_______。A.二叉树的度为2B.二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任一个结点的度都为22．任何一棵二叉树的叶子结点在先、中、后序遍历序列中的相对次序_______。A.不发生改变B.发生改变C.不能确定D.以上都不对3．下面几个符号串编码集合中，不是前缀编码的是_____。A.{0，10，110，1111}B.{11，10，001，101，0001}C.{00，010，0110，1