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

郑州大学现代远程教育 《数据结构》课程（本科） 学习指导书 郭纯一编 — 课程内容与基本要求 “数据结构” 在计算机科学中是一门综合性的专业基础课。本课程将主要介 绍数据结构的基本概念和术语、非数值计算中常用的数据结构（线性表、栈和队 列、串、树和图）和基本技术（查找和排序方法）三大部分。 本课程要求学生在掌握线性表、栈和队列、串、树和二叉树、图等基本数据 类型的基础上， 会分析各种数据结构的特性，会根据应用需求为所涉及的数据合 理选择适当的逻辑结构和存储结构，并能据此设计实现问题的算法；还应初步掌 握算法的时间和空间效率的分析方法。 课程学习进度与指导 章节 第一章 课程内容 绪论 学时分配 4 学时 10 学时 学习指导 （均以课件学习为主） 重点掌握基本概念和时间复杂度的计算 方法 重点掌握顺序结构和链式结构表示线性 表的方法和操作的实现；结合具体例子理 解编程实现一个问题的 2 种方法 重点掌握栈和队列的特点以及它们各自 的存储表示，尤其是顺序栈和循环队列的 实现；结合具体例子理解栈和队列的应用 重点掌握串的术语、串操作结果和不同存 储结构的特点 重点掌握二叉树的定义、存储、性质、遍 历算法（递归）及应用、线索化；掌握树 和森林与二叉树的转换以及 Huffman 树和 Huffman 编码的构造方法 重点掌握图的术语、存储、遍历算法及应 用；掌握最小生成树的 2 种构造方法及特 点、会求拓扑排序序列和单源最短路径 重点掌握各种动态查找表的构造过程、性 能分析、插入/删除方法；掌握静态查找 表的顺序、折半和分块查找及 ASL 求法 掌握关于排序的术语及分类方法；重点掌 握插入排序、交换排序、选择排序等内排 序方法及其性能分析方法 第二章*线性表 第三章 第四章 栈和队列 串 8 学时 2 学时 第七章*树和二叉树10 学时 第八章图8 学时 第九章*查找8 学时 第十章*排序8 学时 欢迎下载2 — 第一章第一章 一、 章节学习目标与要求 绪论绪论 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(inext==head; D. p==head; 4．若在线性表的任何位置上插入元素的概率是相等的，那么在长度为 n 的顺序 表中插入一个元素时需平均移动________个元素。 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． 顺序表能够以元素在计算机内的物理位置的相邻性来表示线性表中元素之间 的逻辑关系。（ ） 3. 在不带头结点的非空单链表中， 首元结点的存储位置由头指针指示， 除首元结 点外，其它任一元素结点的存储位置由前驱结点的指针域的指针指示。（ ） （三）问答题： 1． 若线性表要求以最快的速度存取而表中元素变动不大， 则应采取什么存储结构 （顺序或链式结构）？为什么？ 2．若线性表经常做插入/删除操作，则应采取什么存储结构？为什么？ 3. 在单链表中设置头结点有什么作用？ （四）算法题： 1.设带头结点的单链表(L 为头指针)中的数据元素递增有序。设计算法，将x 插 入到链表的适当位置上，并仍保持该表的有序性。 欢迎下载5 — 2.设顺序表 va 中的数据元素递增有序。设计算法，将 x 插入到顺序表的适当位 置上，并仍保持该表的有序性。 3.设计算 法， 实现 单链 表的 就地逆 置，即利用 原表的 存储空间将 线性表 （a 1,a2,…,an）逆置为（an ,a n-1,…,a1） 。 第三章第三章 一、章节学习目标与要求 1、理解用栈和队列解决实际问题的方法。 2、掌握栈和队列的定义以及特性、它们的 2 种不同的存储表示方法（特别是顺 序栈和循环队列） 以及各种常见操作 （如入、 出操作） 在不同表示方式上的实现。 二、本章重点、难点 重点：栈和队列的定义、各种表示和实现方法，加深对线性结构的理解 难点：循环队列的表示及为解决循环队列队空、队满判断条件相同而使用的不同 实现方式；能在具体问题中灵活运用栈和队列结构。 三、章节练习 （一）选择题： 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. {3241} 4． 栈的入栈序列是 1， 2， …， n， 输出序列为 p1,p2,…pn,若 p1=n, 则 pi 为_____。 A. i B. n-i C. n-i+1 D. 不确定 5．队列是限定在________进行插入，在________进行删除的线性表。 A. 队头 B. 队尾