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

郑州大学现代远程教育数据结构课程（本科）学习指导书郭纯一一编课程内容与基本要求“数据结构”在计算机科学中是一门综合性的专业基础课。 本课程将主要介 绍数据结构的基本概念和术语、 非数值计算中常用的数据结构（线性表、栈和队 列、串、树和图）和基本技术（查找和排序方法）三大部分。本课程要求学生在掌握线性表、栈和队列、串、树和二叉树、图等基本数据类型的基础上，会分析各种数据结构的特性，会根据应用需求为所涉及的数据合 理选择适当的逻辑结构和存储结构， 并能据此设计实现问题的算法；还应初步掌 握算法的时间和空间效率的分析方法。课程学习进度与指导早节课程内容学时分配学习指导（均以课件学习为主）氏U 第一早绪论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. 0 B. 1 C. 任意多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. 105 B. 110 C. 116 D. 1203 .非空循环单链表（head为头指针）的尾结点（由指针p所指示）应满足。A. p->next=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. 在带头结点的非空单链表中，头结点的位置由 指示，首元结点的存储位置由 指示，除首元结点外，其它任一元素结点的存储位置由指示。A. 头指针 B. 头结点的指针域的指针 C. 前驱结点的指针域的指针6. 单链表的头指针为p,若有头结点，则表空的判断条件是 ；若不带头结点，则表空的判断条件是 。A. p=NULL B. p->next=NULL C. p->next->next=NULL（二）判断题：1. 在单链表中插入或删除元素时是以结点的指针变化来反映逻辑关系的变化，因此不需要移动元素。（ ）2. 顺序表能够以元素在计算机内的物理位置的相邻性来表示线性表中元素之间的逻辑关系。（ ）3. 在不带头结点的非空单链表中， 首元结点的存储位置由头指针指示， 除首元结点外，其它任一元素结点的存储位置由前驱结点的指针域的指针指示。（ ）（三）问答题：1. 若线性表要求以最快的速度存取而表中元素变动不大，则应采取什么存储结构 （顺序或链式结构）？为什么？2. 若线性表经常做插入 / 删除操作，则应采取什么存储结构？为什么？3. 在单链表中设置头结点有什么作用？（四）算法题：1. 设带头结点的单链表（L为头指针）中的数据元素递增有序。设计算法，将 x插 入到链表的适当位置上，并仍保持该表的有序性。2. 设顺序表 va 中的数据元素递增有序。设计算法，将 x 插入到顺序表的适当位 置上，并仍保持该表的有序性。3. 设计算法，实现 单链表的就地逆置，即利用 原表的 存储空间将 线性表 （ai,a2,a n）逆置为（ an ,a n-i,.,a i） o第三章 栈和队列一、章节学习目标与要求1、理解用栈和队列解决实际问题的方法。2、掌握栈和队列的定义以及特性、它们的2 种不同的存储表示方法（特别是顺序栈和循环队列） 以及各种常见操作 （如入、出操作） 在不同表示方式上的实现。二、本章重点、难点重点：栈和队列的定义、各种表示和实现方法，加深对线性结构的理解 难点：循环队列的表示及为解决循环队列队空、 队满判断条件相同而使用的不同 实现方式；能在具体问题中灵活运用栈和队列结构。三、章节练习（一）选择题： 1一个栈的入栈序列是 a,b,c,d,e, 则栈的不可能的输出序列是 。A. edcba B.decbaC.dceabD.abcde2栈和队列的共同点是 。A. 都是后进先出 B. 都是先进先出C. 都是只允许在端点处插入和删除元素 D. 无共同点 3一个队列的入队序列是 1,2,3,4, 则队列的输出序列是 。A. 4321 B. 1234 C. 1432 D. 32414栈的入栈序列是1,2,，n,输出序列为p1,p2,pn,若p仁n,则pi为<A. i B. n-i 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. 栈是限定仅在栈顶进行插入或删除操作的线性表。（）4. 队列是限定在队尾插入元素，在队头删除元素的线性表。（）（三）问答与算法题：1对于一个栈，若输入序列依次为 A,B,C, 试给出所有可能的输出序列。 2假设将循环队列定义为：以整型域变量 front 和 length 分别指示循环队列中 队头元素位置和队列中元素个数， 指针 elem 指示存放队列元素的连续空间的首地 址，写出相应的入队列和出队列的算法。第四章 串一、章节学习目标与要求1、理解串的抽象数据类型的定义以及相关术语、理解串在文本编辑中的作用。2、掌握字符串的定义及各种基本操作的运算结果以及串的各种存储表示的特点。二、本章重点、难点 重点：串的基本运算、串的各种存储表示和特点。继续加深对线性结构的理解 难点：串的不同存储结构，区分它们和高级语言中串的存储方式的不同。三、章节练习（一）选择题：1设串 s="I AM A STUDENT", 则其串长是 。A. 13 B. 14 C. 15 D. 162. 设 s ="HE IS A WORKER",t="WORKER则 Strlndex（s,t,5）的返回值是。A. 4 B. 5 C. 6 D. 9 E. 103. 串是一种特殊的线性表，其特殊性体现在 。A. 可以顺序存储B.数据元素是一个字符C. 可以链接存储D.数据元素可以是多个字符4. 已知串 s="ABCDEFG'H, 则 s 的所有不同子串的个数为 。A. 8 B. 9 C. 36 D. 375.设串s="I ama teacher.,则s的第8个字符起、长度为7的子串为A. "teacher. " B. "teacher" C. "a teacher" D. " teacher"6.设串 s="student.",t=“good ",则执行 Strlnsert(s,1,t)后，sA. "good student."B. "good student"C. "goodstudent"D. " good teacher"二）判断题：1空串和空格串是相同的。（）2.