数据结构(1)
- 格式:docx
- 大小:910.26 KB
- 文档页数:3
第八章查找一、判断题1.用二分查找法对一个顺序表进行查找,这个顺序表可以是按各键值排好序的,也可以是没有按键值排好序的。
()2.哈希表的查找不用进行关键字的比较。
()3.哈希表的定义函数H(key)=key%p(p<=m)这种方法是直接定址法。
()4.装填因子α的值越大,就越不容易发生冲突。
( )5.选择hash函数的标准为:随机性好、均匀性好和尽量避免冲突。
( )参考答案:1、×2、×3、×4、×5、√二、填空题1.顺序查找法的平均查找长度为__________,二分查找法的平均查找长度为________,分块查找法(以顺序查找确定块)的平均查找长度为__________,分块查找法(以二分查找确定块〉的平均查找长度为_________,哈希表查找法采用链接法处理冲突时的平均查找长度为_________。
(n+1)/2;((n+1)*log2(n+1))/n-1;(s2+2s+n)/2s;log2(n/s+1)+s/2;1+α2.在各种查找方法中,平均查找长度与结点个数n无关的查法方法是_________哈希表查找3.二分查找的存储结构仅限于_________,且是__________。
顺序;有序的4.在分块查找方法中,首先查找__________,然后再查找相应的___________。
索引;块5.长度为255的表,采用分块查找法,每块的最佳长度是____________。
156.在散列函数H(key)=key%p中,p应取_______________。
小于表长的最大素数7.假设在有序线性表A[1..20]上进行二分查找,则比较一次查找成功的结点数为_________,则比较二次查找成功的结点数为__________,则比较三次查找成功的结点数为_________,则比较四次查找成功的结点数为________,则比较五次查找成功的结点数为_________,平均查找长度为_________。
数据结构试题(一)一、选择1.评价一个算法时间性能的主要标准是(D)A 算法易于调试B 算法易于理解C 算法的稳定性和正确性D 算法的时间复杂度2.可用带表头结点的链表来表示表,也可用不带表头结点的链表来表示表,前者的主要好处是(B)A 可以加快对表的遍历B 使空表和非空表的处理统一C 提高存取结点的速度D 节省存储空间3.稀疏矩阵一般的压缩存储有两种,即(D)。
A 一维数组和二维数组B 一维数组和三元组C 二维数组和十字链表D 三元组和十字链表4.若进栈序列为a,b,c,d,进栈过程中可以出栈,则( D)不可能是一个出栈序列。
A cbadB bdcaC cdbaD adbc5.将一棵有100个结点的完全二叉树从根的这一层开始,每一层从左到右依次对结点进行编号,根结点编号为1,则编号为49的结点的左孩子的编号为(A)A 98B 99C 50D 486.任何一个无向连通图的最小生成树(B)。
A 只有一棵B 有一棵或多棵C 一定有多棵D 可能不存在7.对于如图所示的带权有向图,从顶点1到顶点5的最短路径为(D)A (1,4,5)B (1,2,3,5)C (1,4,3,5)D (1,2,4,3,5)8.下列排序方法中,要求附加的内存容量最大的是(D )。
A 冒泡排序B 快速排序C 堆排序D 归并排序9.( C)不是哈希查找中的冲突处理方法。
A 链地址法B 再哈希法C 除留余数法D 随机探测法10.在一棵7阶的B-树中,除根结点外,每个结点中的最多有( A )个关键字。
A 6B 5C 4D 3第1题正确答案为D第2题正确答案为B第3题正确答案为D第4题正确答案为D第5题正确答案为A第6题正确答案为B第7题正确答案为D第8题正确答案为D第9题正确答案为C第10题正确答案为D二、填空题1.在长度为n的顺序表中删除一个元素时,等概率情况下的平均移动元素的次数是n-1/22. 仅允许在表的同一端进行插入和删除运算的线性表被称为栈3.大小为M的顺序存储的循环队列sq队满的条件为(sq.rear+1)%M ==sq.fpont4.已知一棵二叉树的先根序列为ABDFCE,中根序列为DFBACE,后序序列为FDBECA5.在无向图G的邻接矩阵表示中,第j列中非零元的个数等于该顶点的度6.克鲁斯卡尔算法适用于求边稀疏的网的最小生成树。
数据结构试题一、单选题1、在数据结构的讨论中把数据结构从逻辑上分为(C )A 内部结构与外部结构B 静态结构与动态结构C 线性结构与非线性结构D 紧凑结构与非紧凑结构。
2、采用线性链表表示一个向量时,要求占用的存储空间地址(D )A 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时,搜索成功的平均搜索长度为( D )。
A nB n/2C (n-1)/2D (n+1)/24、在一个单链表中,若q结点是p结点的前驱结点,若在q与p之间插入结点s,则执行( D )。
A s→link = p→link; p→link = s;B p→link = s; s→link = q;C p→link = s→link; s→link = p;D q→link = s; s→link = p;5、如果想在4092个数据中只需要选择其中最小的5个,采用( C )方法最好。
A 起泡排序B 堆排序C 锦标赛排序D 快速排序6、设有两个串t和p,求p在t中首次出现的位置的运算叫做( B )。
A 求子串B 模式匹配C 串替换D 串连接7、在数组A中,每一个数组元素A[i][j]占用3个存储字,行下标i从1到8,列下标j从1到10。
所有数组元素相继存放于一个连续的存储空间中,则存放该数组至少需要的存储字数是( C )。
A 80B 100C 240D 2708、将一个递归算法改为对应的非递归算法时,通常需要使用( A )。
A 栈B 队列C 循环队列D 优先队列9、一个队列的进队列顺序是1, 2, 3, 4,则出队列顺序为( C )。
10、在循环队列中用数组A[0..m-1] 存放队列元素,其队头和队尾指针分别为front和rear,则当前队列中的元素个数是( D )。
A ( front - rear + 1) % mB ( rear - front + 1) % mC ( front - rear + m) % mD ( rear - front + m) % m11、一个数组元素a[i]与( A )的表示等价。
数据结构(一)目录第1章序论 (1)1.1 什么是数据? (1)1.2 什么是数据元素? (1)1.3 什么是数据结构及种类? (1)1.4 数据的逻辑结构 (1)1.5 数据的物理结构 (1)1.6 算法和算法分析 (1)1.7 算法的五个特性 (1)1.8 算法设计的要求 (2)1.9 算法效率的度量 (2)第2章线性表 (3)2.1 线性表举例 (3)2.2 线性表的存储 (4)2.3 线性表-栈 (4)2.4 队列 (4)2.5 双端队列 (6)第3章树和二叉树 (6)3.1 树 (6)3.1.1 树的基本概念 (6)3.1.2 树的常用存储结构 (6)3.1.3 树的遍历 (7)3.2 二叉树 (7)3.2.1 二叉树的基本概念 (7)3.2.2 二叉树与树的区别 (7)3.2.3 树及森林转到二叉树 (7)3.2.4 二叉树的性质 (8)3.2.5 满二叉树 (8)3.2.6 完全二叉树 (8)3.2.7 完全二叉树的性质 (9)3.2.8 二叉树的四种遍历 (9)3.2.9 二叉排序树 (10)3.2.10 平衡二叉树 (11)3.2.11 m阶B-树 (11)3.2.12 最优二叉树 (11)3.2.13 二叉树的存储结构 (12)3.3 广义表 (13)3.4 矩阵的压缩存储 (14)3.4.1 特殊矩阵 (14)3.4.2 压缩存储 (14)第4章历年真题讲解 (15)4.1 2009年上半年 (15)4.2 2009年下半年 (15)4.3 2010年上半年 (15)4.4 2011年上半年 (16)4.5 2011年下半年 (16)4.6 2012年上半年 (17)4.7 2012年下半年 (17)4.8 2013年上半年 (18)4.9 2013年下半年 (18)4.10 2014年上半年 (18)4.11 2014年下半年 (19)4.12 2015年上半年 (19)4.13 2015年下半年 (19)4.14 2016年上半年 (20)第1章序论什么是数据?所有能输入到计算机中并能够被计算机程序处理的符号的总称,它是计算机程序加工的原料。
一、填空题01、数据结构是一门研究非数值计算的程序设计问题中计算机的(操作对象)以及它们之间的(关系和运算)等的学科。
02、数据结构被形式地定义为(D,R),其中D是(数据元素)的有限集合,R是D上的(关系)有限集合。
03、数据结构包括数据的(逻辑结构)、数据的(存储结构)和数据的(运算)这三个方面的内容。
04、数据结构按逻辑结构可分为两大类,它们分别是(线性结构)和(非线性结构)。
05、线性结构中元素之间存在(一对一)关系,树形结构中元素之间存在(一对多)关系,图形结构中元素之间存在(多对多)关系。
06、在线性结构中,第一个结点(没有)前驱结点,其余每个结点有且只有1个前驱结点;最后一个结点(没有)后续结点,其余每个结点有且只有1个后续结点。
07、在树形结构中,树根结点没有(前驱)结点,其余每个结点有且只有(1)个前驱结点;叶子结点没有(后续)结点,其余每个结点的后续结点数可以(任意多个)。
08、在图形结构中,每个结点的前驱结点数和后续结点数可以(任意多个)。
09、数据的存储结构可用四种基本的存储方法表示,它们分别是(顺序)、(链式)、(索引)、(散列)。
10、对于给定的n个元素,可以构造出的逻辑结构有(集合)、(线性结构)、(树形结构)、(图状结构)四种。
11、数据的运算最常用的有5种,它们分别是(插入)、(删除)、(修改)、(查找)、(排序)。
12、一个算法的效率可分为(时间)效率和(空间)效率。
13、数据结构中评价算法的两个重要指标是算法的(时间复杂度)和(空间复杂度)。
14、一个数据结构在计算机中的(映射)称为存储结构。
15、算法的五个重要特性是(有穷性)、(确定性)、(可行性)、输入、输出。
16、已知如下程序段for (i=n; i>=1; i--) //语句1{ x++; //语句2for (j=n; j>=i; j--) //语句3y++; //语句4}语句 1 执行的频度为(n+1);语句2执行的频度为(n);语句3执行的频度为(n(n+3)/2);语句4执行的频度为(n(n+1)/2)。
数据结构-1(总分100,考试时间90分钟)一、单项选择题在每小题列出的四个选项中只有一个选项是符合题目要求的1. 设数组data[0..m]作为循环队列SQ的存储空间,front为队头指针,rear为队尾指针,则执行出队操作的语句为( )A. front:=front+1B. front:=(front+1)mod mC. rear:=(rear+1)mod mD. front:=(front+1)mod(m+1)2. 在Hash函数H(k)=k MOD m中,一般来讲,m应取( )A. 奇数B. 偶数C. 素数D. 充分大的数3. 实现任意二叉树的后序遍历的非递归算法而不使用栈结构,最佳方案是二叉树采用( )存储结构。
A. 二叉链表B. 广义表C. 三叉链表D. 顺序4. 向一个栈顶指针为Top的链栈中插入一个s所指结点时,其操作步骤为( )A. Top—>next=s;B. s—>next=Top—>next;Top—>next=s;C. s—>next=Top;top=s;D. s—>next=Top; Top=Top—>next;5. 快速排序在最坏情况下的时间复杂度是( )A. O(nlogB. O(n2)C. O(n3)D. 都不对6. 内部排序的方法有许多种,( )方法是从未排序序列中依次取出元素,与已排序序列中的元素作比较,将其放入已排序序列的正确位置上。
A. 归并排序B. 插入排序C. 快速排序D. 选择排序7. 对于一个具有N个顶点的图,如果我们采用邻接矩阵法表示,则此矩阵的维数应该是( )A. (N-1)×(N-1)B. N×NC. (N+1)×(N+1)D. 不确定8. 在一个长度为n的顺序表(顺序存储的线性表)中,向第i个元素(1≤i≤n+1)之前插入一个新元素时,需向后移动( )个元素。
A. n-iB. n-i+1C. n-i-1D. i9. 下面四种排序方法中,平均查找长度最小的是( )A. 插入排序B. 选择排序C. 快速排序D. 归并排序10. 如果我们采用二分查找法查找一个长度为n的有序表,则查找每个元素的平均比较次数( )对应的判定树的高度(假设树高h≥2)。
《数据结构》实验指导书郑州轻工业学院2016.02.20目录前言 (1)实验01 顺序表的基本操作 (3)实验02 单链表的基本操作 (11)实验03 栈的基本操作 (19)实验04 队列的基本操作 (21)实验05 二叉树的基本操作 (23)实验06 哈夫曼编码 (24)实验07 图的两种存储和遍历 (26)实验08 最小生成树、拓扑排序和最短路径 (29)实验09 二叉排序树的基本操作 (31)实验10 哈希表的生成 (32)实验11 常用的内部排序算法 (34)附:实验报告模板 (36)前言《数据结构》是计算机相关专业的一门核心基础课程,是编译原理、操作系统、数据库系统及其它系统程序和大型应用程序开发的重要基础,也是很多高校考研专业课之一。
它主要介绍线性结构、树型结构、图状结构三种逻辑结构的特点和在计算机内的存储方法,并在此基础上介绍一些典型算法及其时、空效率分析。
这门课程的主要任务是研究数据的逻辑关系以及这种逻辑关系在计算机中的表示、存储和运算,培养学生能够设计有效表达和简化算法的数据结构,从而提高其程序设计能力。
通过学习,要求学生能够掌握各种数据结构的特点、存储表示和典型算法的设计思想及程序实现,能够根据实际问题选取合适的数据表达和存储方案,设计出简洁、高效、实用的算法,为后续课程的学习及软件开发打下良好的基础。
另外本课程的学习过程也是进行复杂程序设计的训练过程,通过算法设计和上机实践的训练,能够培养学生的数据抽象能力和程序设计能力。
学习这门课程,习题和实验是两个关键环节。
学生理解算法,上机实验是最佳的途径之一。
因此,实验环节的好坏是学生能否学好《数据结构》的关键。
为了更好地配合学生实验,特编写实验指导书。
一、实验目的本课程实验主要是为了原理和应用的结合,通过实验一方面使学生更好的理解数据结构的概念和常用的几种数据结构在计算机中的存储和实现的方法,加强学生动手能力;另一方面培养学生从实际问题中抽象出对应的抽象数据类型,进而找到合适的计算机存储方法和算法,为以后课程的学习、大型软件的开发、实际工程问题打下良好的软件开发基础。
第 1 章 绪 论1.1 数据结构的兴起和发展一、数据结构起源于程序设计。
·程序设计的新问题:应如何组织待处理的数据以及数据之间的关系(结构)。
·70年代初,数据结构作为一门独立的课程开始进入大学课堂。
二、数据结构随着程序设计的发展而发展。
程序设计经历了三个阶段:无结构阶段、结构化阶段和面向对象阶段,相应地,数据结构的发展也经历了三个阶段:三、数据结构的发展并未终结。
1. 数据结构将继续随着程序设计的发展而发展;2. 面向各专门领域的数据结构得到研究和发展,各种空间数据结构也在探索中。
应用领域:科学计算;程序设计面向计算机 应用领域:科学计算与非数值处理;算法+数据结构=程序 应用领域:更多地应用于非数值处理;(算法+数据结构)=程序1.2 数据结构的研究对象例1-1 学籍管理问题例1-2 人——机对弈问题例1-3 教学计划编排问题表1-1 学生学籍登记表 (a) 井字棋的一个格局 (b) 对弈树的局部 图1-2 对弈问题中格局之间的关系1.3 数据结构的基本概念1.3.1 数据结构1. 数据:在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号集合。
2. 数据元素:是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。
构成数据元素的不可分割的最小单位称为数据项。
3. 数据对象:是具有相同性质的数据元素的集合,是数据的子集。
4. 数据结构:是指相互之间存在一定关系的数据元素的集合。
按照视点的不同,数据结构分为逻辑结构和存储结构。
数据的逻辑结构是指数据元素之间逻辑关系的整体。
根据数据元素之间逻辑关系的不同,数据结构分为四类:⑴集合数据元素之间的关系是。
⑵线性结构数据元素之间的关系是。
⑶树结构数据元素之间的关系是。
⑷图结构数据元素之间的关系是。
数据的存储结构又称为物理结构,是数据及其逻辑结构在计算机中的表示。
有两种存储结构:顺序存储结构和链接存储结构。
第1章绪论5.选择题(1)在数据结构中,从逻辑上可以把数据结构分成()。
A.动态结构和静态结构 B.紧凑结构和非紧凑结构C.线性结构和非线性结构 D.内部结构和外部结构(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.栈第2章线性表1.选择题(1)一个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是()。
A.110 B.108 C.100 D.120说明:计算公式:A+(i-1)*L,A为起始地址,i是元素序号,L是元素长度。
(2)在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是()。
A.访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)B.在第i个结点后插入一个新结点(1≤i≤n)C.删除第i个结点(1≤i≤n)D.将n个结点从小到大排序(3)向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动的元素个数为()。
第一章绪论一、选择题1.一个算法应该是()。
A.程序B问题求解步骤的描述C 要满足5个基本特性D.A和c2 计算机算法必须具备输入、输出、()等5个特性。
A 可行性、可移植性和可扩展性B 可行性、确定性和有穷性C 确定性、有穷性和稳定性D 易读性、安全性和稳定性3 在数据结构中,从逻辑上可以把数据结构分为()A 动态结构和静态结构B 紧凑结构和非紧凑结构C 内容结构和外部结构D 线性结构和非线性结构4 下面程序段的时间复杂性的量级为()for (i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;A O(1)B O(n)C O(n2)D O(n3)5 在数据结构中,与所使用的计算机无关的是数据的()结构A 逻辑B 存储C 逻辑和存储D 物理6 数据结构在计算机中的表示是指()A 数据的逻辑结构B 数据结构C 数据的存储结构D 数据元素之间的关系7 下面()的时间复杂性最好,即执行时间最短。
A O(n)B O(logn)C O(nlogn)D O(n2)8 下面程序段的时间复杂性的量级为()。
int fun(int n){i=1,s=1;while(s<n)s+=++i;return i;}A O(n/2)B O(logn)C O(n)D O(n1/2)9 下面程序段的时间复杂性的量级为()。
for(int i=0;i<m;i++)for(int j=0;j<n;j++)A[i][j]=i*j;A O(m3)B O(n2)C O(m*n)D O(m+n)10 执行下面程序段时,S 语句的执行次数为()。
for(int i=1;i<n-1;i++)for(int j=i+1;j<=n;j++)S;A n(n-1)/2B n2/2C n(n+1)/2D n11、研究数据结构就是研究( )。
A、数据的逻辑结构B、数据的存储结构C、数据的逻辑结构和存储结构D、数据的逻辑结构、存储结构及其数据在运算上的实现12、以下属于逻辑结构的是( )。
一.填空题
1. _集合__、线性结构、__树形结构____ 、图形结构
2.p->next!=NULL
3.时间复杂度和空间复杂度
4.随机存取
5..队尾
6. n-1
二、单选题、
1-5DAACC 6-10DBDDB 11-15DCABD
三,简答题
1、
2、数据是对客观事物的描述形式和编码形式的统称,是算法和程序的处理对象和计算结构。
数据元素又称数据结点,简称结点,通常一个数据结点由用来描述一个独立事的名称、数量、特性、性质的一组相关信息。
多数情况下,一个结点包含有多个数据项,每个数据项是结点的一个域,能够用来唯一标识结点的域称为关键字域。
算法:有穷规则的集合,而规则规定了解决某一特定问题的运算序列。
有穷性:必须在执行有穷步后终止。
确定性:每一步必须具有确定的定义,不能含糊不清,不带二义性。
可行性:所有运算都可以精确地实现。
输出数据:必须有输出数据,包括输出某种动作或控制信号。
输入数据:作为执行前的初始量。
不是必须。
算法有两种表现形式:描述形式和程序形式。
计算时间复杂的的方法:
•支配性语句度量法:在一段程序中,往往有一条语句执行次数最多,话费时间也就是最多,其他语句执行次数的和将不超过这套语句执行次数的常数倍,那么就称这条语句在话费时间上是起支配性作用的典型语句,于是可选这条语句的执行次数作为度量这段程序花费时间的阶。
•
四、应用题
1、
2、、对给定的n个权值bai{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn},其中du每棵二叉树Ti中只有一个权值zhi为Wi的根结点,
它的左右子树均为空。
(为方便在计算机上实现算法,一般还要求以Ti的权值Wi的
升序排列。
)二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和。
三、从F中删除这
两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中。
四、重复二和三两步,直到集合F中只有一棵二叉树为止。
树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL
WPL=∑Wi*Li (i=1到n)
WPL=(2+4)*3+(6+8+10)*2
=66。