郑大远程数据结构习题
第一章
第一题、单项选择题（每题1分，5道题共5分）
1、在计算机中,数据的基本单位是 B
A、数据
B、数据元素
C、数据项
D、数据结构
2、网状数据结构中数据元素之间的对应关系是 C
A、1:1
B、1:N
C、M:N
D、N:1
3、一个算法的实现取决于选定的 B
A、逻辑结构
B、存储结构
C、时间复杂度
D、空间复杂度
4、在数据结构的讨论中,可把数据结构从逻辑上分为 D
A、静态结构与动态结构
B、内部结构与外部结构
C、紧凑结构与非紧凑结构
D、线性结构与非线性结构
5、算法的效率一般用什么来度量 A
A、时间复杂度
B、空间复杂度
C、执行的时间
D、占用的空间
第二题、多项选择题（每题2分，5道题共10分）
1、数据结构一般有以下几种类型 ABCD
A、集合
B、线性结构
C、树形结构
D、图形结构
2、算法的重要特征有 ABCD
A、有穷性
B、确定性
C、可行性
D、有输出
3、下列哪写是数据结构的基本操作 ABCD
A、插入
B、删除
C、查找
D、修改
4、对于C语言而言,下列哪些是基本数据类型 ABCD
A、整型
B、实型
C、字符型
D、布尔型
E、结构体类型
5、非线性结构主要是指 ACD
A、集合
B、表
C、树形结构
第三题、判断题（每题1分，5道题共5分）
1、数据是信息的载体,是对客观事物的符号表示 对
正确 错误
2、数据结构是相互之间存在一种或多种特定关系的数据元素的集合 对 正确 错误
3、存储结构是数据结构在计算机中的表示,也称为数据的物理结构. 对 正确 错误
4、树形结构中的数据元素之间存在一个对一个的关系 错 正确 错误
5、图形结构中的元素存在多个对多个的关系. 对 正确
错误
第二章 第一题、单项选择题（每题1分，5道题共5分）
1、对于一个长度为n 的顺序存储的线性表，在表尾插入元素的时间复杂度为 C
A 、O(n)
B 、O(n*n)
C 、O(1)
D 、O(0)
2、在一个长度为n 的顺序存储的线性表中，删除第i 个元素（1≤i≤n）时，需要从前向后依次前移几个元素。 A
A 、n-i
B 、n-i+1
C 、n-i-1
D 、i
3、采用链式结构表示一个线性表时,要求占用的存储空间地址 D A 、必须是连续的 B 、部分地址必须是连续的
C 、一定是不连续的
D 、可连续可不连续 4、设顺序表第一个元素X 的存储地址loc(X)为基地址,则第I 个元素Y 的存储地址为 A
A 、loc(X)+(I-1)*l,其中l 为每个元素的大小
B 、loc(X)+I*l,其中l 为每个元素的大
小
C 、loc(X)+(I+1)*l,其中l 为每个元素的大小
D 、(I-1)*l,其中l 为每个元素的大小 5、单链表插入操作的平均时间复杂度为 B
A 、O(1)
B 、O(n)
C 、O(n*n)
D 、O(n*n*n)
第二题、多项选择题（每题2分，5道题共10分）
1、在顺序表中删除一个元素的步骤主要有 没找到正确答案
A 、检查线性表是否为空
B 、检查删除位置是否合法
C 、使表长减1
D 、删除成功,返回一个表示成功的值
2、顺序表的特点有 ABCD
A 、存储结构简单
C、节省空间
D、可随机存储
3、单链表的节点一般应包括 AB
A、数据域
B、指针域
C、节点域
D、存储域
4、线性表用链式结构来实现,可有哪些形式 ABCD
A、单链表
B、双链表
C、循环链表
D、双向循环链表
5、下列哪些是线性表的常用操作 ABCD
A、插入
B、删除
C、查找
D、判断是否为空
第三题、判断题（每题1分，5道题共5分）
1、对于线性表L,当元素个数为0时,一般称为空表对
正确错误
2、在线性表中插入一个元素后,线性表的长度比插入前增加1 对
正确错误
3、线性表就是指顺序表错
正确错误
4、在线性链表中插入一个元素是不会出现无法插入的情况的错
正确错误
5、单链表中的各个元素如果不存储在连续的空间内,那么从本质上来看它就不是线性结构错
正确错误
第三章
第一题、单项选择题（每题1分，5道题共5分）
1、在队列中,允许删除元素的一端称为 A
A、队首
B、队尾
C、入队
D、出队
2、一个栈的入栈序列为a1,a2,a3,a4,a5,则此栈不可能的输出序列是 C
A、a5,a4,a3,a2,a1
B、a4,a5,a3,a2,a1
C、a4,a3,a5,a1,a2
D、a1,a2,a3,a4,a5
3、在一个链队列中，假设f和r分别为队首和队尾指针，删除一个结点的运算是 C
A、r ＝ f -＞next
B、r ＝ r -＞next
C、f ＝ f -＞next
D、f ＝ r -＞next
4、在一个具有n个单元的顺序栈中，假设栈底是存储地址的低端，现在我们以top 作为栈顶指针，则作退栈操作时，top的变化是 A
A、top ＝top -1 ;
B、top ＝ top +1 ;
C、top 不变
D、top不确定
5、假溢出现象只会出现在哪种数据结构中 D
A、顺序表
B、链表
C、栈
D、队列
第二题、多项选择题（每题2分，5道题共10分）
1、栈的常用操作有 ABCD
A、入栈
B、出栈
C、取栈顶元素
D、清空栈
2、栈的实现方式主要有 AB
A、顺序方式
B、链式方式
C、循环方式
D、递归方式
3、一个栈的入栈序列为a1,a2,a3,a4,a5,则此栈可能的输出序列是 AB
A、a1,a2,a3,a4,a5
B、a5,a4,a3,a2,a1
C、a1,a5,a3,a4,a2
D、a5,a1,a2,a3,a4
4、队列的常用操作有 ABC
A、入队
B、出队
C、取队首元素
D、取队尾元素
5、队列的实现方式主要有 AB
A、顺序方式
B、链式方式
C、循环方式
D、递归方式
第三题、判断题（每题1分，5道题共5分）
1、向栈顶插入一个元素的操作叫入栈对
正确错误
2、由于顺序栈占用连续的存储空间,所以可以随机存取栈中的元素错
正确错误
3、由于队列元素的操作具有"先进先出"的特征,因此队列又称为先进先出表对正确错误
4、在队列中允许删除的一端称为队首对
正确错误
5、队列只能用顺序方式来实现错
正确错误
第四章
第一题、单项选择题（每题1分，5道题共5分）
1、设串s1＝"ABCDEFG",s2＝"PQRST",函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的字符，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1, len(s2),2))的结果串是 D
A、BCDEF
B、BCDEFG
C、BCPQRST
D、BCDEFEF
2、空格串的长度为 D
A、0
B、1
C、大于1
D、大于等于1
3、设s1＝"GOOD"，s2＝"-",s3＝"BYE！"，则s1、s2和s3连接后的结果是 A
A、"GOOD-BYE！"
B、"GOODBYE！"
C、"GOOD BYE！"
D、"GOODBYE"
4、数组A中，每个元素A 的长度为3个字节，行下标i从1到8，列下标j从1到10 ，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起使地址为 C
A、SA+141
B、SA+180
C、SA+222
D、SA+225
5、稀疏矩阵一般的压缩存储方法有两种，即 C
A、二维数组和三维数组
B、三元组和散列
C、三元组和十字链表
D、散列和十字链表
第二题、多项选择题（每题2分，5道题共10分）
1、在一般的程序设计语言中,串中的元素可以是 ABCD
A、字母
B、阿拉伯数字
C、一些特殊符号
D、汉字
2、下列说法正确的是 ABCD
A、数组也是一种线性数据结构
B、一维数组从本质上看就是线性表
C、二维数组是数据元素为一维数组的线性表
D、数组是由值与下标组成的数偶的有序集合
3、常见的特殊矩阵有 ABC
A、对称矩阵
B、三角矩阵
C、对角矩阵
D、二维矩阵
4、稀疏矩阵的存储方法一般有 AB
A、三元组表法
B、十字链表法
C、循环链表法
D、堆方法
5、串的基本操作包括 ABCDE
A、连接
B、求串长
C、串比较
D、子串定位
E、串复制
第三题、判断题（每题1分，5道题共5分）
1、长度为零的串称为空串对
正确错误
2、串中任意个连续的字符组成的子序列称为该串的子串对
正确错误
3、串既可以用顺序方式表示,也可以用链式方式表示对
正确错误
4、数组的存储结构一般都采用顺序存储结构对
正确错误
5、C语言中,数组的实现采用列优先的存储方式错
正确错误
第五章
第一题、单项选择题（每题1分，5道题共5分）
1、在一棵二叉树中，度为零的结点的个数为n0，度为2的结点的个数为n2，则有n0＝ B
A、n2
B、n2+1
C、n2-1
D、n2+2
2、现有按中序遍历二叉树的结果为abc，问有几种不同形态的二叉树可以得到这一遍历结果 D
A、2
B、3
C、4
D、5
3、带权路经长度最小的树称为 C
A、满二叉树
B、完全二叉树
C、哈夫曼树
D、线索二叉树
4、若用10,6,20,23,8,1,5做为权值,构造一棵哈夫曼树,该树的深度为 B
A、4
B、5
C、6
D、7
5、将一棵树转换为一个二叉树后,该二叉树必定 B
A、没有左子树
B、没有右子树
C、所有的节点都没有左子树
D、所有的节点都没有右子树
第二题、多项选择题（每题2分，5道题共10分）
1、二叉树的遍历方法有 ABCD
A、前序法
B、中序法
C、后序法
D、层次遍历法
2、树的逻辑结构表示法有 ABCD
A、树形表示法
B、文氏图表示法
C、凹入表示法
D、括号表示法
3、二叉树的基本操作主要有 ABCD
A、遍历
B、求二叉树的深度
C、求某个节点的左子女
D、求某个节点的左子女
4、二叉树的实现方法主要有 AB
A、顺序方式
B、链式方式
C、循环方式
D、递归方式
5、树的实现方式主要有 AB
A、顺序方式
B、链式方式
C、循环方式
D、递归方式
第三题、判断题（每题1分，5道题共5分）
1、由树转换成二叉树，其根结点的右子树总是空的对
正确错误
2、后根遍历树和中序遍历与该树对应的二叉树，其结果不同错
正确错误
3、后序遍历森林和中序遍历与该森林对应的二叉树，其结果不同错
正确错误
4、用二叉树的前序遍历和中序遍历可以导出二叉树的后序遍历对
正确错误
5、在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没有后继子女结点错正确错误
第六章
第一题、单项选择题（每题1分，5道题共5分）
1、具有6个顶点的无向图至少应有＿＿＿条边才能确保是一个连通图 A
A、5
B、6
C、7
D、8
2、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是＿＿＿ D
A、n
B、(n-1)*(n-1)
C、n-1
D、n*n
3、采用邻接表存储的图的深度优先遍历算法类似于二叉树的 A
A、先序遍历
B、中序遍历
C、后序遍历
D、按层遍历
4、关键路径是事件结点网络中 A
A、从源点到汇点的最长路径
B、从源点到汇点的最短路径
C、最长的回路
D、最短的回路
5、一个图中包含有k个连通分量，若按深度优先搜索的方法访问所有结点，则必须调用＿＿＿＿次深度优先算法 A
A、k
B、1
C、k-1
D、k+1
第二题、多项选择题（每题2分，5道题共10分）
1、完全图包括 AB
A、无向完全图
B、有向完全图
C、连通图
D、完全连通图
2、图的常用存储方法有 BC
A、散列方法
B、邻接矩阵法
C、邻接表法
D、顺序方法
3、图的遍历方法有 AB
A、深度优先方法
B、广度优先方法
C、先根方法
D、后根方法
4、拓扑排序的主要步骤有 ABC
A、在AOV网中,选一个没有后继的节点,并输出
B、在网中删去该顶点,并删去所有指向该顶点的弧
C、重复上述两步,直到网中不再有出度为0的顶点为止
D、删除网中的回路
5、常用的最小生成树算法有 AB
A、普里姆算法
B、克鲁斯卡尔算法
C、哈夫曼算法
D、拓扑算法
第三题、判断题（每题1分，5道题共5分）
1、在N个结点的无向图中，若边数大于N-1，则该图必是连通图错
正确错误
2、任何AOV网的拓扑序列都是唯一的错
正确错误
3、邻接表只能用于存储有向图，而邻接矩阵则可存储有向图和无向图错
正确错误
4、无向图的邻接矩阵是对称的，因此可只存储邻接矩阵的下（或上）三角阵对
正确错误
5、强连通分量是有向图中的极大强连通子图对
正确错误
第七章
AADAB
对错对对错
第一题、单项选择题（每题1分，5道题共5分）
1、如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用＿＿＿查找方法 A
A、分块
B、顺序
C、二分
D、散列
2、一个有序顺序表有255个元素，采用顺序查找法查找，查找长度为 A
A、128
B、127
C、126
D、255
3、在散列函数H（key）＝key％p中，p一般取 D
A、大于1000的数
B、小于1000的数
C、随机数
D、素数
4、对于二叉排序树的查找，若根结点元素的键值大于被查找元素的键值，则应该在二叉树的＿＿＿上继续查找 A
A、左子树
B、右子树
C、左右两棵子树
D、根接点
5、在一棵二叉排序树上实施＿＿＿＿＿＿＿遍历后，其关键字序列是一个有序表 B
A、先序
B、中序
C、后序
D、深度
第二题、多项选择题（每题2分，5道题共10分）
1、根据对查找表中的数据所执行的操作,可将查找表分为 AB
A、静态查找表
B、动态查找表
C、树表
D、链表
2、下列哪些是哈希函数的构造方法 ABCD
A、直接地址法
B、除留余数法
C、平方取中法
D、折叠法
3、下面哪些是处理冲突的方法 AB
A、开发地址法
B、链地址法
C、索引法
D、二分法
4、哈希表的缺点主要有 ABC
A、根据哈希函数计算关键字的地址的过程占用一定的计算时间
B、占用的存储空间多
C、在哈希表中只能按关键字查找
D、不能进行删除操作
5、开发地址法可进一步分为 AB
A、线性探测法
B、二次探测法
C、随机探测法
D、链地址法
第三题、判断题（每题1分，5道题共5分）
1、哈希表的查找效率主要取决于哈希表建立时选取的哈希函数和处理冲突的方法对
正确错误
2、直接定址法构造的哈希函数会发生冲突错
正确错误
3、折半查找是一种在有序表上进行查找的方法对
正确错误
4、由二叉排序树的定义可知,中序遍历二叉树所得到的序列是非递减有序的对
正确错误
5、从哈希表中删除一个数据元素时是不需要使用哈希函数的错
正确错误
第八章
第一题、单项选择题（每题1分，5道题共5分）
1、一组记录的排序码为{46，79，56，38，40，84}，则利用堆排序的方法建立的初始堆为 B
A、79，46，56，38，40，84
B、84,79，56，38，40，46
C、84,79，56，46，40，38
D、84，56，79，40，46，38
2、排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为 D
A、希尔排序
B、归并排序
C、插入排序
D、选择排序
3、一组记录的排序码为{25，48，16，35，79，82，23，40，36，72}，其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一次归并后的结果为 A
A、16 25 35 48 23 40 79 82 36 72
B、16 25 35 48 79 82 23 36 40 72
C、16 25 48 35 79 82 23 36 40 72
D、16 25 35 48 79 23 36 40 72 83
4、在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 D
A、希尔排序
B、起泡排序
C、插入排序
D、选择排序
5、快速排序方法在＿＿＿情况下最不利于发挥其长处 C
A、要排序的数据量太大
B、要排序的数据中含有多个相同值
C、要排序的数据已基本有序
D、要排序的数据个数为奇数
第二题、多项选择题（每题2分，5道题共10分）
1、排序时,可以根据记录的哪些数据项进行排序 ABC
A、主关键字
B、次关键字
C、若干数据项的组合
D、不需要依据任何数据项
2、插入排序方法可分为 AD
A、直接插入排序
B、折半插入排序
C、选择插入排序
D、希尔排序
3、时间复杂度为O(n*n)的排序方法有 AB
A、直接插入排序
B、简单选择排序
C、快速排序
D、堆排序
4、根据排序时存放数据的存储器的类型,可将排序分为 BC
A、快速排序
B、内部排序
C、外部排序
D、简单排序
5、关于冒泡排序，说法正确的是 ACD
A、稳定的
B、不稳定的
C、是一种交换排序方法
D、最坏情况下的时间复杂度是O(n2).
第三题、判断题（每题1分，5道题共5分）
1、对于n个记录的集合进行冒泡排序，在最坏情况下时间复杂度是O (n2 ) 对正确错误
2、对于n个记录的集合进行归并排序，平均时间复杂度是O (nlog2n) 对
正确错误
3、对于n个记录的集合进行快速排序，在最坏的情况下时间复杂度是O(n2 ) 错正确错误
4、对于n个记录的集合进行快速排序，平均时间复杂度是O (nlog2 n) 对
正确错误
5、希尔排序是对直接插入排序的一种改进对
正确错误
郑州大学远程教育学院数据结构试题及答案
郑州大学现代远程教育 《数据结构》课程（本科） 学习指导书 郭纯一编
课程内容与基本要求 “数据结构”在计算机科学中是一门综合性的专业基础课。本课程将主要介绍数据结构的基本概念和术语、非数值计算中常用的数据结构（线性表、栈和队列、串、树和图）和基本技术（查找和排序方法）三大部分。 本课程要求学生在掌握线性表、栈和队列、串、树和二叉树、图等基本数据类型的基础上，会分析各种数据结构的特性，会根据应用需求为所涉及的数据合理选择适当的逻辑结构和存储结构，并能据此设计实现问题的算法；还应初步掌握算法的时间和空间效率的分析方法。 课程学习进度与指导 章节课程内容学时分配 学习指导 （均以课件学习为主） 第一章绪论4学时 重点掌握基本概念和时间复杂度的计算 方法 第二章*线性表10学时重点掌握顺序结构和链式结构表示线性表的方法和操作的实现；结合具体例子理解编程实现一个问题的2种方法 第三章栈和队列8学时重点掌握栈和队列的特点以及它们各自的存储表示，尤其是顺序栈和循环队列的实现；结合具体例子理解栈和队列的应用 第四章串2学时 重点掌握串的术语、串操作结果和不同存 储结构的特点 第七章*树和二叉树10学时重点掌握二叉树的定义、存储、性质、遍历算法（递归）及应用、线索化；掌握树和森林与二叉树的转换以及Huffman树和
第一章绪论 一、章节学习目标与要求 1、理解数据抽象和信息隐蔽原则 2、掌握所有的基本概念和术语、掌握时间复杂度的计算方法、会用C语言描述抽象数据类型和算法；能够熟练使用C语言编写程序 二、本章重点、难点 重点：基本概念和术语，C语言描述算法的方式，简单程序的时间复杂度的求法。难点：时间复杂度的计算方法和原则。 三、章节练习 （一）选择题： 1．具有线性结构的数据结构是__________。 A.图 B. 树 C. 集合 D. 栈 2．计算机算法是指________。 A.计算方法和运算结果 B.调度方法 C. 解决某一问题的有限运算系列 D. 排序方法 3．线性结构中，最后一个结点有________个后继结点。
经典数据结构面试题(含答案)
栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是 __________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________
数据结构试题库答案
数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s 第一章 第一题、单项选择题（每题1分，5道题共5分） 1、在计算机中,数据的基本单位是 B A、数据 B、数据元素 C、数据项 D、数据结构 2、网状数据结构中数据元素之间的对应关系是 C A、1:1 B、1:N C、M:N D、N:1 3、一个算法的实现取决于选定的 B A、逻辑结构 B、存储结构 C、时间复杂度 D、空间复杂度 4、在数据结构的讨论中,可把数据结构从逻辑上分为 D A、静态结构与动态结构 B、内部结构与外部结构 C、紧凑结构与非紧凑结构 D、线性结构与非线性结构 5、算法的效率一般用什么来度量 A A、时间复杂度 B、空间复杂度 C、执行的时间 D、占用的空间 第二题、多项选择题（每题2分，5道题共10分） 1、数据结构一般有以下几种类型 ABCD A、集合 B、线性结构 C、树形结构 D、图形结构 2、算法的重要特征有 ABCD A、有穷性 B、确定性 C、可行性 D、有输出 3、下列哪写是数据结构的基本操作 ABCD A、插入 B、删除 C、查找 D、修改 4、对于C语言而言,下列哪些是基本数据类型 ABCD A、整型 B、实型 C、字符型 D、布尔型 E、结构体类型 5、非线性结构主要是指 ACD A、集合 B、表 C、树形结构 第三题、判断题（每题1分，5道题共5分） 1、数据是信息的载体,是对客观事物的符号表示 对 正确 错误 2、数据结构是相互之间存在一种或多种特定关系的数据元素的集合 对 正确 错误 3、存储结构是数据结构在计算机中的表示,也称为数据的物理结构. 对 正确 错误 4、树形结构中的数据元素之间存在一个对一个的关系 错 正确 错误 5、图形结构中的元素存在多个对多个的关系. 对 正确 错误 第二章 第一题、单项选择题（每题1分，5道题共5分） 1、对于一个长度为n 的顺序存储的线性表，在表尾插入元素的时间复杂度为 C A 、O(n) B 、O(n*n) C 、O(1) D 、O(0) 2、在一个长度为n 的顺序存储的线性表中，删除第i 个元素（1≤i≤n）时，需要从前向后依次前移几个元素。 A A 、n-i B 、n-i+1 C 、n-i-1 D 、i 3、采用链式结构表示一个线性表时,要求占用的存储空间地址 D A 、必须是连续的 B 、部分地址必须是连续的 C 、一定是不连续的 D 、可连续可不连续 4、设顺序表第一个元素X 的存储地址loc(X)为基地址,则第I 个元素Y 的存储地址为 A A 、loc(X)+(I-1)*l,其中l 为每个元素的大小 B 、loc(X)+I*l,其中l 为每个元素的大 小 C 、loc(X)+(I+1)*l,其中l 为每个元素 的大小 D 、(I-1)*l,其中l 为每个元素的大小 5、单链表插入操作的平均时间复杂度为 B A 、O(1) B 、O(n) C 、O(n*n) D 、O(n*n*n) 第二题、多项选择题（每题2分，5道题共10分） 1、在顺序表中删除一个元素的步骤主要有 没找到正确答案 A 、检查线性表是否为空 B 、检查删除位置是否合法 C 、使表长减1 D 、删除成功,返回一个表示成功的值 2、顺序表的特点有 ABCD A 、存储结构简单 数据结构模拟卷(含答案)经典习题 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( ) 操作系统是管理系统资源、控制程序执行、改善人机界面、提供各种服务、合理组织计算机工作流程和为用户有效使用计算机提供良好运行环境的一种系统软件。 资源管理1资源复用(空分复用共享,,时分复用共享)2资源虚化3资源抽象4组合使用抽象和虚化技术 .操作系统中的基础抽象——进程、虚存和文件（1）进程抽象（2）虚存抽象（3）文件抽象（4）其他资源抽象 操作系统的作用:（1）OS作为用户接口和公共服务程序：（2）OS作为扩展计算机或者虚拟计算机（2）OS作为资源的管理者和控制者（4）OS作为程序执行的控制着和管理者从资源管理的角度，看操作系统具有六项主要功能：处理器管理，存储管理，设备管理，文件管理，网络与通信管理，用户接口 操作系统的主要特性：并发性，共享性，异步性 并发性：指两个或两个以上事件或活动在同一时间间隔内发生。 并行性：指两个或两个以上事件或活动在同一时刻发生。 关系：并行活动一定是并发的，反之并发活动未必是并行的，并行性是并发性的特例，并发性是并行性的扩展。 共享性：指操作系统中的资源可被多个并发执行的进程共同使用，而不是被其中某一个程序所独占。 1，透明资源共享：必须妥善解决的问题有资源隔离， 授权访问2，显式资源共享：独占资源是指同一时间段内只允许一个进程访问的资源 异步性：由计算机系统中的资源有限而进程众多，每个进程的执行并非连贯的，而是以“走走停停”的方式向前推进。多道程序设计是指允许多个程序同时进入一个计算机系统的主存储器并启动进行交替计算的方法。从宏观上看，多道程序并发运行，它们都处于运行过程中，但都未运行结束。从微观上看，多道程序的执行是串行的，各道程序轮流占用CPU，交替地执行。好处：1，提高CPU、主存和设备的利用率，2，提高系统的吞吐率，是单位时间内完成的作业数增加。3充分发挥计算机系统部件的并行性 操作系统可分为三种基本类型：批处理操作系统分时操作系统.实时操作系统 通用操作系统：如果某个操作系统兼具批处理、分时、实时处理的全部或两种功能，则为通用OS 操作系统为用户提供两种调用其服务和功能的接口: 程序接口：允许运行程序调用操作系统的服务和功能。 许多操作系统的程序接口由一组系统调用（System Call)）组成，用户程序使用“系统调用”就可获得操作系统的底层服务，使用或访问系统的各种软硬件资源。 操作接口：操作系统为用户提供的操作控制计算机工作和提供服务手段的集合，通常有操作控制命令、图形操作界面、以及批处理系统提供的作业控制语言等实现手段。 内核是一组程序模块，作为可信软件来支持进程并发执行的基本功能和基本操作，通常驻留在内核空间，运行于核心态，具有访问硬件设备和所有主存空间的权限，是仅有的能执行特权指令的程序。分类可分为微内核和单内核两种类型。功能1）资源抽象2）资源分配3）资源共享。 属性1）内核是由中断驱动的2）内核的执行是连续的3）内核在屏蔽中断状态下执行4）内核可以使用特权指令。 从操作系统的运行方式来看，可分成：独立运行的内核模型、在应用进程内执行的模型和作为独立进程运行的模型。 处理器流可以分作以下四类：单指令流单数据流（SISD）：传统的计算机系统。单指令流多数据流（SIMD）和多指令流多数据流（MIMD）都属于并行计算机！ 多指令流单数据流（MISD）：在研究中 处理器现场：处理器包括一组寄存器，用于存放数据、变量和中间结果，这组寄存器所存储的信息与程序的执行有很大关系，构成了处理器现场。 特权指令是指只能提供给操作系统的核心程序使用的指令，如启动I/O设备、设置时钟、控制中断屏蔽位、清内存、建立存储键，加载PSW（程序状态字）等。 非特权指令：指供应用程序使用的、权限较低的指令。 处理器状态分类：核心状态和用户状态。 核心态具体的权限有：1，CPUU运行可信软件2，硬件执行全部机器指令3，可以访问所有内存单元和系统资源4，具体改变处理器状态的能力。 用户态具有的权限有：1，CPU运行非可信软件2，程序无法执行特权指令3，访问权限仅限于当前进程的地址空间4，不具有改变处理器状态的能力 处理器状态之间的转换：(1)用户状态向核心状态的转换：一是程序请求操作系统服务，执行一条系统调用；二是程序运行时，产生了一个中断（或者异常）事件，运行程序被中断，让中断处理程序工作。这两种情况都是通过中断机构发生的。中断（异常）是用户态到核心态转换的唯一途径。(2)核心状态向用户状态的转换：每台计算机通常会提供一条特权指令称作加载程序状态字LPSW（Load PSW），用来实现操作系统向用户程序的转换。 加载程序状态字指令的作用：把哪个程序的程序状态字加载到程序状态字寄存器中，就意味着该程序获得CPU控制权执行。 中断是指程序执行过程中，遇到急需处理的某个事件时，暂时中止CPU上现行程序的运行，转而执行相应的事件处理程序执行的过程，待处理完毕之后再返回断点（继续执行）或者调度其他程序执行。中断源是引起中断的事件。中断装置是发现中断源并产生中断的硬件。 中断源分类：1.从中断事件的性质和激活的手段来分，可以分成两类：强迫性中断事件和自愿性中断事件。2按照中断信号的来源和实现手段来分：可分为硬中断和软中断两类。硬中断可以分为外中断和内中断。 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 1 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位 10. 下列图示的顺序存储结构表示的二叉树是( ) 2 2013-2014学年二学期数据结构期末考试模拟试卷(1~6卷) 一、应用题(3小题，共24分) 1已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3 次、4次和9次，对该字符串用［0,1］进行前缀编码，问该字符串的编码至少有多少位。 【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图所示。其带权路 径长度=2X 5+1X 5+3X 4+5X 3+9X 2+4X 3+4X 3+7X 2=98，所以，该字符串的编码长度至少为98位。 2.已知关键码序列为(Ja n, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec), 散列表的地址空间为0~16,设散列函数为H(x)= ［i/2」(取下整数)，其中i为关键码 中第一个字母在字母表中的序号，采用链地址法处理冲突构造散列表，并求等概率情况下查找成功的平均查找长度。 【解答】H(Ja n)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0 H(May)=13/2=6, H(Ju n)=10/25, H(Jul)=10/25, H(Aug)=1/2=0 H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2 采用链地址法处理冲突，得到的开散列表如下： 平均查找长度=(1 X 7+2X 4+3X 1)/12=18/12 3.分析下面各程序段的时间复杂度 (1)s1(int n) { int p=1,s=0; for (i=1;iv=n;i++) { p*=i;s+=p; } return(s); } ——0(n) (2)s2(int n) x=0;y=0; For (k=1;kv=n;k++) x++; For (i=1;iv=n;i++) For (j=1;jv=n;j++) y++; ——0(n) 1?下述算法的功能是什么？ ListNode *Demo l(LinkList L P ListNode *p) ("L是有头结蛊的单链表 ListNodc *q=L->rLCxt P (1) V ‘V … 」(1 )返回结点*p的直接前趋结点地址。 q=q->nest; if (q) return q, else ?ro< #*p not in L"); I ⑵ i/oid Demo2(LisINode *p ,ListNode +q) 〔//p t*q*8S 表中的 两个结点 (2)交换结点*p和结点*q (p和q的值不变)。 DataTypetemp; temp=p->data, p->data=q->data; q-x^ata^emp, 1.对给定的一组权值W=( 5, 2, 9, 11, 8, 3, 7),试构造相应的哈夫曼树，并计算它的带权路径长度。【解答】构造的哈夫曼树如图所示。 《数据结构》第04章在线测试 《数据结构》第04章在线测试剩余时间：43:12 答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。 第一题、单项选择题（每题1分，5道题共5分） 1、若串S＝"abcdef"，则其非空子串数目为＿＿＿＿＿＿＿＿。 A、6 B、12 C、21 D、22 2、字符串是一种特殊的线性表，其特殊性在于它的数据元素只能是＿＿＿＿＿＿＿＿。 A、字符 B、字符串 C、数字 D、字母 3、设有三个串，s1＝"How", s2＝" are", s3＝" you",则这三个串连接后得到的结果串是＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿。 A、"Howareyou" B、"How are you" C、"How are you." D、" How are you" 4、串是一种特殊的线性表，其特殊性体现在＿＿＿＿＿＿＿＿。 A、可以顺序存储 B、数据元素是一个字符 C、可以链接存储 D、数据元素可以是多个字符 5、空格串的长度为＿＿＿＿＿＿＿＿。 A、0B、1 C、串中空格的个数 D、 第二题、多项选择题（每题2分，5道题共10分） 1、在定长顺序存储表示中，对串长的表示方法有＿＿＿＿＿＿＿＿＿＿。 A、用域变量表示 B、用下标为0的数组分量表示 C、在串值后加结束标记字符 D、无法明确表示 2、以下关于串的存储方式的说法中正确的是＿＿＿＿＿＿＿＿＿＿。 A、定长顺序表示和堆分配表示都是串的顺序存储表示 B、定长顺序表示的串的存储空间是编译时预先分配的一个比较大的连续空间 C、堆分配表示的串的存储空间是在程序执行过程中动态分配的 D、堆分配存储表示时的空串不占用连续的存储区 3、两个串相等的充分必要条件是＿＿＿＿＿＿＿＿＿＿。 A、串长相等且各对应位置字符相等 B、所含字符集合相同 C、所含字符个数相同 D、串值相等 4、串的机内表示方法有＿＿＿＿＿＿＿＿＿＿。 A、定长顺序存储表示 B、堆分配存储表示 C、块链存储表示 D、散列表示 5、以下关于块链结构的说法正确的是＿＿＿＿＿＿＿＿＿＿。 A、结点大小小，则存储密度小 B、结点大小小，则存储密度大 数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #include #define OVERFLOW 0 #define MAXSIZE 100 typedef int ElemType; typedef struct list {ElemType elem[MAXSIZE]; int length; }Sqlist; void Creatlist(Sqlist &L) {int i; printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。 scanf("%d",&L.length); for(i=0;i .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是__________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ 第三章栈和队列 一、判断题： 1、栈和队列都是限制存取点的线性结构(易) 2、栈和队列是两种重要的线性结构。(易) 3、带头结点的单链表形式的队列，头指针F指向队列的头结点，尾指针R指向队列的最后一个结点(易) 4、在对不带头结点的链队列作出队操作时，不会改变头指针的值。(易) 答案：1-4 √√×× 二、选择题： 1、一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是C____。 A、 edcba B、 decba C、 dceab D、 abcde 2、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi 为_C___。 A、 i B、 n=i C、 n-i+1 D、不确定 3、栈结构通常采用的两种存储结构是_A___。 A、顺序存储结构和链式存储结构 B、散列方式和索引方式 C、链表存储结构和数组 D、线性存储结构和非线性存储结构 4、判定一个顺序栈ST（最多元素为m0）为空的条件是_B___。A、top !=0 B、top= =0 C、top !=m0 D、top= =m0-1 5、判定一个顺序栈ST（最多元素为m0）为栈满的条件是D。A、top！=0 B、top= =0 C、top！=m0 D、top= =m0-1 6、队列操作的原则是( A ) A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删 除 7、向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行__ _C_。(不带空的头结点) (易) A、HS—＞next=s;9 B、s—＞next= HS—＞next; HS—＞next=s; C、s—＞next= HS; HS=s; D、s—＞next= HS; HS= HS—＞next 《数据结构》课程设计题目 (程序实现采用C语言) 题目1：猴子选王（学时：3） 一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。 //链表 #include { pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 } void KickFromRing(RingNodePtr pHead, int n) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == n) { // 踢出环 printf("\n%d", pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; 2010级数据结构课程试题（A 卷） 合分人： 复查人： 一、单选题：（每题2分，共20分） 1. 线性表的顺序存储结构是一种________的存储结构。 A . 顺序存取 B . 随机存取 C . 索引存取 2. 下列程序段的时间复杂度是（ ）。 for (i=1; i<=n; i++) for(j=n ; j>=i+1; j--) if(a[j-1]>a[j]) a[j-1] a[j]; A. O(n) B. O(1) C. O(n 2) D. O(i*n) 3. G 是一个有8个顶点的无向连通图，则该图至少有 条边。 A. 6 B . 7 C . 8 D . 9 4. 关于串的存储结构, 以下描述正确的是（ ）。 A. 串的块链存储表示实际上也是顺序存储结构 B. 串使用堆分配存储表示时，实际多少字符，就分配多少空间 C. 串使用定长顺序存储，串操作过程中不会出现丢尾现象 D. 串的定长存储表示是顺序结构，而串的堆分配表示是链式存储结构 5. 有序表｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，折半查找82时，要经过（ ）次比较。 A. 1 B. 2 C. 4 D. 8 6. 任何一棵二叉树的叶子结点在先、中、后序遍历序列中的相对次序_______。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对 7. 若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有 序，则该二叉树是 。 A.二叉排序树 B . Huffman 树 C . 堆 8．________二叉排序树可得到一个关键字的有序序列。 A. 先序遍历 B . 中序遍历 C . 后序遍历 D . 层序遍历 数据结构经典例题 1.设计一个算法将L拆分成两个带头节点的单链表L1和L2。 void split(LinkList *&L,LinkList *&L1,LinkList *&L2) { LinkList *p=L->next,*q,*r1; //p指向第1个数据节点 L1=L; //L1利用原来L的头节点 r1=L1; //r1始终指向L1的尾节点 L2=(LinkList *)malloc(sizeof(LinkList));//创建L2的头节点 L2->next=NULL; //置L2的指针域为NULL while (p!=NULL) { r1->next=p; //采用尾插法将*p(data值为ai)插入L1中 r1=p; p=p->next; //p移向下一个节点(data值为bi) q=p->next; //由于头插法修改p的next域,故用q保存*p的后继节点 p->next=L2->next; //采用头插法将*p插入L2中 L2->next=p; p=q; //p重新指向ai+1的节点 } r1->next=NULL; //尾节点next置空 } 2.查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。 typedef struct LNode {int data; struct LNode *link; } *LinkList; int Searchk(LinkList list,int k) { LinkList p,q; int count=0; p=q=list->link; while (p!=NULL) { if (count 习题二 ⒉１描述以下四个概念的区别：头指针变量，头指针，头结点，首结点（第一个结点）。解：头指针变量和头指针是指向链表中第一个结点（头结点或首结点）的指针；在首结点之前附设一个结点称为头结点；首结点是指链表中存储线性表中第一个数据元素的结点。若单链表中附设头结点，则不管线性表是否为空，头指针均不为空，否则表示空表的链表的头指针为空。 2.2简述线性表的两种存储结构有哪些主要优缺点及各自使用的场合。 解：顺序存储是按索引直接存储数据元素，方便灵活，效率高，但插入、删除操作将引起元素移动，降低了效率；而链式存储的元素存储采用动态分配，利用率高，但须增设表示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入和删除十分简单。顺序存储适用于线性表中元素数量基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素的情况；而链式存储适用于频繁进行元素动态插入或删除操作的场合。 2.3 在头结点为h的单链表中，把值为b的结点s插入到值为a的结点之前，若不存在a，就把结点s插入到表尾。 Void insert(Lnode *h,int a,int b) {Lnode *p,*q,*s; s=(Lnode*)malloc(sizeof(Lnode)); s->data=b; p=h->next; while(p->data!=a&&p->next!=NULL) {q=p; p=p->next; } if (p->data==a) {q->next=s; s->next=p;} else {p->next=s; s->next=NULL; } } 2.4 设计一个算法将一个带头结点的单链表A分解成两个带头结点的单链表A和B，使A中含有原链表中序号为奇数的元素，而B中含有原链表中序号为偶数的元素，并且保持元素原有的相对顺序。 Lnode *cf(Lnode *ha) {Lnode *p,*q,*s,*hb; int t; p=ha->next; q=ha; t=0; hb=(Lnode*)malloc(sizeof(Lnode)); s=hb; while(p->next!=NULL) {if (t==0) {q=p;p=p->next;t=1;} else {q->next=p->next; p->next=s->next; s->next=p; s=p; p=p->next; t=0; } } s->next=NULL; return (hb); } 数据结构习题 习题一 一、选择题 1、算法分析的两个主要方面是：（） A．正确性和简明性B．时间复杂度和空间复杂度 C．数据复杂性和程序复杂性D．可读性和文档性 2、在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．逻辑结构和存储结构 3、计算机算法具备输入、输出和（）等5个特性： A．有穷性、确定性和稳定性B．可行性、可移植性和可扩充性 C．有穷性、确定性和可行性D．易读性、稳定性和安全性 4、算法分析的目的是（）。 A．找出算法的合理性 B．研究算法的输人与输出关系 C．分析算法的有效性以求改进 D．分析算法的易懂性 二、填空题 1、数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。 2、线性结构中元素之间存在的关系，树形结构中元素之间存在的关系， 图形结构中元素之间存在的关系。 3、________是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为________。 4、数据的________指数据元素及其关系在计算机存储器内的表示。_________是逻辑结构在计算机里的实现，也称之为映像。 5、所谓算法（Algorithm）是对特定问题求解方法和步骤的一种描述，它是指令的一组__________，其中每个指令表示一个或多个操作。 三、问答题 1、用大O形式写出下面算法的时间复杂度： i＝0； s=0； while(s＜n） ｛ i++; s+=i; ｝ 2、写出以下算法的时间复杂度： for（i＝0; i＜m; i＋＋） for（j＝0 ; j＜t; j＋＋） c[i][j]=0； for（i=0；i＜m；i＋＋） for（j=o; j 郑州大学现代远程教育 《数据结构》课程(本科) 学习指导书 郭纯一编 ?课程内容与基本要求 “数据结构”在计算机科学中就是一门综合性的专业基础课。本课程将主要介绍数据结构的基本概念与术语、非数值计算中常用的数据结构(线性表、栈与队列、串、树与图)与基本技术(查找与排序方法)三大部分。 本课程要求学生在掌握线性表、栈与队列、串、树与二叉树、图等基本数据类型的基础上,会分析各种数据结构的特性,会根据应用需求为所涉及的数据合理选择适当的逻辑结构与存储结构,并能据此设计实现问题的算法;还应初步掌握算法的时间与空间效率的分析方法。 ?课程学习进度与指导 第一章绪论 一、章节学习目标与要求 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; 基本概念典型例题 一、单项选择题 [例6-1]数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。其中，D是( ①)的有穷集合，R是D上( ②)的有限集合。 ①A.算法B. 数据元素C. 数据操作D. 逻辑结构 ②A. 操作B. 映像C. 存储D．关系 解析：由数据结构的集合形式化定义可知，本题答案为：①B；②D。 [例6-2]数据的常用存储结构中不包括( )。 A．顺序存储结构B．线性结构C．索引存储结构D．散列存储结构 解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储 方法和散列存储方法。由此可知，本题答案为：B。 [例6-3] 算法指的是( ①)，它必须具备( ②)这三个特性。 ①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法 ②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性D．易读性、稳定性、安全性 解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。它 必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。由此可知，本 题答案为：①㈠②B。 [例6-4] 在下面的程序段中，对x的赋值语句的执行频度为( )。 for(i=0；i郑大远程数据结构习题
数据结构模拟卷(含答案)经典习题培训讲学
郑州大学操作系统期末考试重点整理
数据结构模拟卷(含答案)经典习题
数据结构题库教材
郑州大学远程教育数据结构考试
经典数据结构上机题_答案解析
经典数据结构面试题(含答案)
数据结构相关题库及答案
数据结构经典题目c语言代码
郑州大学中澳班2010数据结构试卷
数据结构经典例题
数据结构上机例题及答案
数据结构题库汇总
郑州大学远程教育学院数据结构试题及答案
数据结构典型例题
- 郑州大学远程教育学院数据结构试题及答案
- 数据结构(信息管理) 郑州大学 网考资料及答案
- 郑州大学操作系统期末考试重点整理
- 2014郑州大学远程教育软件工程期末考试
- 郑大远程数据结构习题
- 郑大远程教育混凝土结构与砌体结构考试资料2017版
- 郑大远程数据结构习题
- 郑州大学中澳班2010数据结构试卷
- 郑大远程_数据结构
- 郑州大学远程教育数据结构考试.
- 郑州大学远程教育学院数据结构试题及答案
- 郑大远程数据结构习题
- 郑州大学远程教育学院数据结构试题及答案
- 郑州大学远程教育C语言考试试卷
- 郑大远程数据结构习题
- 郑大远程数据结构习题
- 郑州大学计算机专科网络测试及答案6
- 数据结构 2020年 郑州大学机考资料及答案
- 郑大远程_数据结构
- 郑州大学远程教育学院数据结构试题(卷)与答案解析