数据结构概论考核题
（第9题配图：数组的下标为0,1,2,3）
10.对于哈希函数H(key)=key%13,被称为同义词的关键字是
A.35和41
B.23和39
C.15和44
D.25和51
全国2012年1月数据结构导论试题课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 1.结点按逻辑关系依次排列形成一条“锁链”的数据结构是( )A.集合 B.线性结构 C.树形结构 D.图状结 构 2.下面算法程序段的时间复杂度为( ) for ( int i=0; i 复习提纲 第一章数据结构概述 基本概念与术语（P3） 1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2．数据元素是数据的基本单位 3．数据对象相同性质的数据元素的集合 4．数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i 数据结构知识点概括 第一章概论 数据就就是指能够被计算机识别、存储与加工处理得信息得载体。 数据元素就是数据得基本单位,可以由若干个数据项组成。数据项就是具有独立含义得最小标识单位。 数据结构得定义: ·逻辑结构:从逻辑结构上描述数据，独立于计算机.·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：就是逻辑结构用计算机语言得实现。·顺序存储结构:如数组。 ·链式存储结构:如链表。 ·索引存储结构：·稠密索引:每个结点都有索引项。 ·稀疏索引：每组结点都有索引项. ·散列存储结构:如散列表。 ·数据运算。 ·对数据得操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用得有:检索、插入、删除、更新、排序。 数据类型:就是一个值得集合以及在这些值上定义得一组操作得总称. ·结构类型:由用户借助于描述机制定义,就是导出类型。 抽象数据类型ＡDＴ:·就是抽象数据得组织与与之得操作。相当于在概念层上描述问题. ·优点就是将数据与操作封装在一起实现了信息隐藏. 程序设计得实质就是对实际问题选择一种好得数据结构，设计一个好得算法.算法取决于数据结构。 算法就是一个良定义得计算过程，以一个或多个值输入,并以一个或多个值输出．评价算法得好坏得因素：·算法就是正确得; ·执行算法得时间; ·执行算法得存储空间(主要就是辅助存储空间); ·算法易于理解、编码、调试。 时间复杂度：就是某个算法得时间耗费，它就是该算法所求解问题规模ｎ得函数. 渐近时间复杂度:就是指当问题规模趋向无穷大时,该算法时间复杂度得数量级。 评价一个算法得时间性能时，主要标准就就是算法得渐近时间复杂度。 算法中语句得频度不仅与问题规模有关,还与输入实例中各元素得取值相关。 时间复杂度按数量级递增排列依次为:常数阶Ｏ（1)、对数阶O（lｏg2n）、线性阶O（n)、线性对数阶O(nｌog2n)、平方阶O(ｎ＾2)、立方阶Ｏ(n^3）、……ｋ次方阶O(ｎ＾k)、指数阶O(2^n)。 空间复杂度:就是某个算法得空间耗费，它就是该算法所求解问题规模n得函数。 算法得时间复杂度与空间复杂度合称算法复杂度。 第二章线性表 线性表就是由n≥0个数据元素组成得有限序列. ｎ=0就是空表；非空表,只能有一个开始结点，有且只能有一个终端结点。 线性表上定义得基本运算: ·构造空表:Initｌist(Ｌ) ·求表长：Ｌiｓtlengｔh(L) ·取结点:GｅtNodｅ(Ｌ，i) ·查找:LoｃａｔeNodｅ(L,ｘ) ·插入:IｎsertＬｉsｔ(L,x,i) ·删除:Ｄeｌｅte（L,i） 顺序表就是按线性表得逻辑结构次序依次存放在一组地址连续得存储单元中。在存储单元中得各元素得物理位置与 逻辑结构中各结点相邻关系就是一致得。地址计算：LOCa(i)=LOCa(1）+(i-1）*d；（首地址为1) 在顺序表中实现得基本运算： ·插入:平均移动结点次数为ｎ/2；平均时间复杂度均为O(n）。 ·删除：平均移动结点次数为(ｎ-1)／２;平均时间复杂度均为O(n)。 线性表得链式存储结构中结点得逻辑次序与物理次序不一定相同，为了能正确表示结点间得逻辑关系,在存储每个结点值得同时,还存储了其后继结点得地址信息(即指针或链）。这两部分信息组成链表中得结点结构。 一个单链表由头指针得名字来命名。 单链表运算: ·建立单链表·头插法：ｓ—〉next=head;heａd=s；生成得顺序与输入顺序相反。平均时间复杂度均为Ｏ(n）。 ·尾插法:heａd=ｒｅar=null;ｉf(head＝nulｌ)hｅaｄ=s;eｌse r—>ｎexｔ=s;ｒ=s; 平均时间复杂度均为O（n) ·加头结点得算法:对开始结点得操作无需特殊处理,统一了空表与非空表。 ·查找·按序号:与查找位置有关，平均时间复杂度均为Ｏ(n）. ·按值：与输入实例有关,平均时间复杂度均为O(ｎ)。 ·插入运算：ｐ=GetNodｅ(Ｌ，i-1);s—〉next=p—〉ｎext;p->ｎext=s；平均时间复杂度均为O(n) 《数据结构与算法》期末复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i 第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（） A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（）。 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（） (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？ A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（） A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（） FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； 《数据结构概论》期末考核试题 一、单项选择题( 每小题 2 分，共 30 分 ) 1.下列编码中属前缀码的是(B) A.{1,01,000,001} B.{1,01,011,010} C.{0,10,110,11} D.{0,1,00,11} 2.设栈 S 和队列 Q的初始状态为空，元素a,b,c,d,e,f依次进栈，一个元素退栈后即进入队列Q，若 6 个元素的出队的序列是 b,d,c,f,e,a，则栈 S 的容量至少应当是 (C) A.6 B.4 C.3 D.2 3.在具有 n 个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是(B) A.O(1) B.O(n) C.O(nlogn) D.O(n 2) 4.要表示省，市，区，街道的有关数据及其关系，选择(B) 比较合适。 A. 线性结构 B. 树结构 C. 图结构 D. 集合结构 5.链栈与顺序栈相比，比较明显的优点是(D) A. 插入操作更加方便 B. 删除操作更加方便 C. 不会出现下溢的情况 D.不会出现上溢的情况 6.二叉树中第 5 层上的结点个数最多为 (C) A.8 B.15 C.16 D.32 7.在表长为ｎ的链表中进行线性查找，查找成功时，它的平均查找长度为 (B) A.ASL=n B.ASL=(n+1)/2 C.ASL= n +1D.ASL≈ log2(n+1)-1 8. 对 22 个记录的有序表进行折半查找，当查找失败时，至少需要比较(B) 次关键字。 A.3 B.4 C.5 D.6 9. 已知图的邻接表如下所示，根据算法，则从顶点0 出发按广度优先遍历的结点序列是(A) A.0321 B.0123 C.0132 D.0312 （第 9 题配图：数组的下标为0,1,2,3 ） 10.对于哈希函数 H(key)=key%13, 被称为同义词的关键字是 (D) A.35 和 41 B.23 和 39 C.15 和 44 D.25 和 51 11.图的深度优先遍历类似于二叉树的(A) A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 12. 下述几种排序方法中，稳定的排序算法是(B) 第一章概论习题 一、选择题 1．数据结构是具有【B 】的数据元素的集合。 A．相同性质B．相互关系C．相同运算D．数据项2．在计算机的存储结构中，逻辑上相邻的结点存储在物理位置上也相邻的连续存储单元里，称之为【 B 】。 A．逻辑结构B．顺序存储结构C．链式存储结构D．散列存储结构3．语句for(i=1;i<=n;i++) x++;的时间复杂度为【B 】。 A．O(1) B．O(n) C．O(n2) D．O(n3) 4．下面不属于数据的存储结构的是【D 】。 A．散列存储B．链式存储C．索引存储D．压缩存储5．数据结构研究的是数据的【 A 】及它们之间的相互关系。 A．存储结构和逻辑结构B．存储和抽象C．理想与抽象D．理想与逻辑6．下面程序段的时间复杂度是【D 】。 for(i=0;i<2*n;i++) for(j=1;j<3*n;j++) A[i][j]=0; A．O(n) B．O(5n) C．O(6n2) D．O(n2) 7．数据的逻辑结构有两大类，分别是【 B 】。 A．顺序存储结构和链式存储结构B．线性结构和非线性结构 C．压缩结构和非压缩结构D．有序结构和无序结构 8．以下与数据的存储结构无关的术语是【D 】。 A．循环队列B．链表C．哈希表D．栈 9．算法分析的两个主要方面是【A 】。 A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 10．下面程序段的时间复杂度是【D 】。 S=0; for(i=0;i 四川大学期末考试试题 （2008-2009学年第1学期） 课程号：课程名称：数据结构与算法分析（B卷）任课教师： 1．数据类型为（）。 A）数据项的集合B）值的集合及定义在其上的一组操作的总称 C）数据元素的集合D）关键字的集合 2．链表不具有的特点是（）。 A）可随机直接访问任一元素B）插入删除不需要移动元素 C）不必事先估计元素个数D）所需空间与线性表长度成正比 3．设一个栈的入栈序列是ABCD，则借助于一个栈所得到的出栈序列不可能是（）。 A）ABCD B）DCBA C）ABCD D）DABC 4．将对称矩阵A nxn压缩存储在一维数组B[m]中，则m的值至少为（）。 A）n(n+1)/2 B）n(n-1)/2 C）n(n+1) D）n2 5．设二叉树中有n2个度为2的结点，n1个度为1的结点，n0个叶子结点，则此二叉树中空指针域个数为（）。 A）n0+n1+n2 B）n2+n1+2n0 C）2n2+n1D）2n0+n1 6．对于具有n个顶点的强连图，其弧条数的最小值为（）。 A）n+1 B）n C）n-1 D）n-2 7．一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（）个结点。 A）2k-1-1 B）2k-1C）2k-1+1 D）2k-1 8．归并排序的时间复杂度是（）。 A）O(1) B）O(n) C）O(n2) D）O(nlogn) 9．每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（）。 A）冒泡排序B）简单选择排序C）希尔排序D）直接插入排序10．按照二叉树的定义，具有3个结点的不同形态（相似）的二叉树有（）种。 A）3 B）4 C）5 D）6 二、（本题10分） 利用两个栈S1、S2模拟一个队列（如客户队列）时，如何用栈的运算实现队列的插入、删除运算，请简述算法思想。 三、（本题10分） 已知一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。 先序序列：ABCDEFGH IJ 中序序列：CBEDAGHFJI 注：试题字迹务必清晰，书写工整。本题2页，本页为第1页 教务处试题编号： 教材：《数据结构》严蔚敏吴伟民清华大学出版社 《数据结构算法实现及解析》高一凡西安电子科技大学出版社 第一部分数据结构概述 一、定义（研究是数据结构的存储和数据的操作的） 如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找某个元素，删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应的操作也叫做算法。 数据结构= 个体的存储（从某个角度而言，可忽略）+ 个体与个体之间关系的存储（核心） 算法= 对存储数据的操作 二、算法 解题的方法和步骤 衡量算法的标准 1.时间复杂度 大概程序要执行的次数，而非执行的时间 2.空间复杂度 算法执行过程中大概所占用的最大内存 3.难易程度（即可读性） 4.健壮性 三、数据结构的地位 数据结构是软件中最核心的内容 程序= 数据的存储+ 数据的操作+ 可以被计算机执行的语言 第二部分预备知识 一、指针 指针的重要性：指针是C语言的灵魂 定义 地址：内存单元的编号 从零开始的非负整数 范围：0--FFFFFFFF（即0--4G-1） 指针： 指针就是地址，地址就是指针 指针变量是存放内存单元地址的变量 指针的本质是一个操作受限的非负整数（只能进行减运算）分类： 1.基本类型的指针 2.指针和一维数组的关系 二、结构体 为什么会出现结构体 为了表示一些复杂的数据，而普通的基本类型变量无法满足要求什么叫结构体 结构体是用户根据实际需要自己定义的数据类型 如何使用结构体 两种方式： struct Student st = {1000, "zhangsan", 20} struct Student * pst = &st; 1.st.sid 2.pst->sid pst所指向的结构体变量中的sid这个成员 第一章数据结构概述 基本概念与术语 1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 2. 数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。 (补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 ) 3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。(有时候也 叫做属性。) 4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 (1)数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。 依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种： 1. 集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 2. 线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 3. 树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素 (根)之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。 4. 图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个(或零个)直接后继。 (2)数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构： 1. 顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 2. 链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5. 时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n 无关系T(n)=O(1) 2. 线性阶：算法的时间复杂度与问题规模 n 成线性关系T(n)=O(n) 3. 平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++ 时间复杂度的大小比较： O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n ) 北京交通大学考试试题（A卷） 课程名称:数据结构与算法2011-2012学年第一学期出题教师:张勇 (请考生注意:（1）本试卷共有六道大题，（2）答案一律写在答题纸上，（3）试卷不得带出考场) 1. 在顺序表中访问任意一个元素的时间复杂度均为，因此顺序表也称为 的数据结构。 2．三维数组a[4][3][2](下标从0开始)，假设a[0][0][0]的地址为50，数据以行序优先方式存储，每个元素的长度为2字节，则a[2][1][1]的地址是。 3. 直接插入排序用监视哨的作用是。 4. 已知广义表Ls=(a, (b, c), (d, e)), 运用head和tail函数取出Ls中的原子d的运算 是。 5．对有14个元素的有序表A[1..14]进行折半查找，当比较到A[4]时算法结束。被比较元素除A[4]外，还有。 6. 在AOV网中，顶点表示，边表示。 7. 有向图G可进行拓扑排序的判别条件是。 8. 若串S1=‘ABCDEFGHIJK’,S2=‘451223’,S3=‘####’,则执行 Substring(S1,Strlength(S3),Index(S2,‘12’,1))的结果是。 二、选择题（每空2分，共20分） 1.在下列存储形式中，哪一个不是树的存储形式？（） A．双亲表示法B．孩子链表表示法 C．孩子兄弟表示法D．顺序存储表示法 2.查找n个元素的有序表时，最有效的查找方法是（）。 A．顺序查找B．分块查找 C．折半查找D．二叉查找 3.将所示的s所指结点加到p所指结点之后，其语句应为（）。 p (A) s->next=p+1 ; p->next=s; (B) (*p).next=s; (*s).next=(*p).next; (C) s->next=p->next ; p->next=s->next; (D) s->next=p->next ; p->next=s; 4. 在有向图的邻接表存储结构中，顶点v 在链表中出现的次数是（ ）。 A. 顶点v 的度 B. 顶点v 的出度 C. 顶点v 的入度 D. 依附于顶点v 的边数 5. 算法的时间复杂度为O （nlog 2n ）、空间复杂度为O(1)的排序算法是（ ）。 A. 堆排序 B. 快速排序 C. 归并排序 D.直接选择 6. 设矩阵A 是一个对称矩阵，为了节省存储，将其 下三角部分（如右图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素ai,j(i ≤j), 在一维数组B 中下标k 的值是（ ）： Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j 7. 由一个长度为11的有序表，按二分查找法对该表进行查找，在表内各元素等概率情 况下，查找成功的平均查找长度是（ ）。 A ．29/11 B. 31/11 C. 33/11 D.35/11 8. AVL 树是一种平衡的二叉排序树，树中任一结点的（ ）。 A. 左、右子树的高度均相同 B. 左、右子树高度差的绝对值不超过1 C. 左子树的高度均大于右子树的高度 D. 左子树的高度均小于右子树的高度 9. 下列四种排序方法中，不稳定的方法是（ ）。 A. 直接插入排序 B. 冒泡排序 C. 归并排序 D. 堆排序 10. 设树的度为4，其中度为1,2,3,4的结点个数分别为4, 2, ,1, 1, 则T 中的叶子数为 （ ）。 A ．5 B ．6 C ．7 D ．8 三、 判断题（10分，每小题1分） 1. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ） 2. 数组不适合作任何二叉树的存储结构。（ ） 3. 广义表的取表尾运算，其结果通常是个表，但有时也可是个原子。（ ） 4. 在含有n 个结点的树中，边数只能是n-1条。（ ） 5. 所谓一个排序算法是否稳定，是指该算法在各种情况下的效率是否相差不大。（ ） 6. 简单选择排序在最好情况下的时间复杂度为O(n)。（ ） 7. 在二叉排序树中插入一个新结点，总是插入到叶结点下面。（ ） 8. 采用线性探测处理冲突，当从哈希表中删除一个记录时，不应将该记录所在位置置 空，因为这会影响以后的查找。（ ） 9. 有n 个数存放在一维数组A[1..n]中，在进行顺序查找时，这n 个数的排列有序或无 ?????? ? ???? ? ??=n n n n a a a a a a A ,2,1,2 ,21,21 ,1Λ Λ 数据结构基础知识 标准化文件发布号：（9312-EUATWW-MWUB-WUNN-INNUL-DQQTY- 复习提纲 第一章数据结构概述 基本概念与术语（P3） 1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2．数据元素是数据的基本单位 3．数据对象相同性质的数据元素的集合 4．数据结构三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i 数据结构概论考核题 C. 0 1 3 2 D.0 3 1 2 （第9题配图：数组的下标为0,1,2,3） 10.对于哈希函数H(key)=key%13,被称为同义词的关键字是( D ) A.35和41 B.23和39 C.15和44 D.25和51 11.图的深度优先遍历类似于二叉树的( A ) A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历 12.下述几种排序方法中，稳定的排序算法是( A ) A.直接插入排序 B.快速排序 C.堆排序 D.希尔排序 13.依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位 置上的方法，称为( C ) A.希尔排序 B.冒泡排序 C.插入排序 D.选择排序 14.二叉树是非线性数据结构，所以 ( A ) A.它不能用顺序存储结构存储 B.它不能用链式存储结构存储 C.顺序存储结构和链式存储结构都能存储 D.顺序存储结构和链式存储结构都不能使用 15.有8个结点的无向图最多有( B )条边。 A.14 B.28 C.56 D.112 二、填空题（每小题1分，共15分） 1 当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的__时间复杂度______。 2 设数组a[M](M为最大空间个数)作为循环队列Q的存储空间，front为队头指针(指向第一个存 （3）重复（2），直到U=V为止。 此时，TE中必含有n-1条边，则T=（V，{TE}）为N的最小生成树。 2. 假设通信电文使用的字符集为{a,b,c,d,e,f,g}，若这些字符在电文中出现的频度分别为：3， 35，13，15，20，5和9，分别求出这些字符的等长编码以及哈夫曼编码，并比较他们的编码长度。 第一章概论练习题 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是的有限集合，R是D上的有限集合。 3. 数据结构包括数据的、数据的和数据的这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是和。 5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6．在线性结构中，第一个结点前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点后续结点，其余每个结点有且只有1个后续结点。 7. 在树形结构中，树根结点没有结点，其余每个结点有且只有个前驱结点；叶子结点没有结点，其余每个结点的后续结点数可以。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是。 10. 数据的运算最常用的有5种，它们分别是。 11. 一个算法的效率可分为效率和效率。 二、单项选择题 （）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. 计算机算法必须具备输入、输出和等5个特性。 A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性 三、简答题 1.数据结构和数据类型两个概念之间有区别吗？ 2. 简述线性结构与非线性结构的不同点。 8576 顺序线性表的基本操作 时间限制:1000MS 内存限制:1000K 提交次数:1714 通过次数:300 题型: 编程题语言: 无限制 Description 编写算法，创建初始化容量为LIST_INIT_SIZE的顺序表T，并实现插入、删除、遍历操作。本题目给出部分代码，请补全内容。 #include for(_________________________) printf("%d ",_________________________); // 请填空 } printf("\n"); return OK; } intListInsert_Sq(SqList&L,inti,int e) { // 算法2.4，在顺序线性表L中第i个位置之前插入新的元素e // i的合法值为1≤i≤L.length +1 // 请补全代码 } intListDelete_Sq(SqList&L,inti, int&e) { // 算法2.5,在顺序线性表L中删除第i个位置的元素，并用e返回其值 // i的合法值为1≤i≤L.length // 请补全代码 } int main() { SqList T; int a, i; ElemType e, x; if(_________________________) // 判断顺序表是否创建成功 { printf("A Sequence List Has Created.\n"); } while(1) { printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n"); scanf("%d",&a); switch(a) { case 1: scanf("%d%d",&i,&x); if(_________________________) printf("Insert Error!\n"); // 判断i值是否合法，请填空 elseprintf("The Element %d is Successfully Inserted!\n", x); 第一章绪论 1、简述下列术语：数据、数据元素、数据对象、数据结构、数据存储、存储结构、数据类型和抽象数据类型。 2、数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么？ 3、什么是算法? 算法的5个特性是什么? 试根据这些特性解释算法与程序的区别。 4、什么叫算法的时间复杂度？怎样表示算法的时间复杂度？ 5、两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有一个运算的定义不一样，它们是否可以认作是同一个数据结构？为什么？ 6、试画出与下列程序段等价的框图 (1)product = 1; i = 1; while(i <= n){ product * = i ; i++; } (2)i = 0; do{ i++; }while ((i!=n)&&(a[i])!=x); 7、已知如下程序段 for(i=n;n>=1;n--) {语句1} { x++； {语句2} for(j=n;j<=i;j--)FOR j:=n {语句3} y++; {语句4} }； 求语句１到语句４的频度。 8、按增长率从小到大的顺序排列下列各组函数： 2100，（3/2）n，（2/3）n，（4/3）n，n，n3/2，n2/3，n!，n n，log2n，n/log2n，log2(log2n)，n log2n 9、试写一算法，自大至小依次顺序读入的三个整数X,Y,Z的值。 10、假设有A,B,C,D,E五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一张表，表中每行的形式为： 项目名称性别校名成绩得分 编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。 11、设求解同一个问题有三种算法，三种算法各自的时间复杂度分别为O(n2)，O(2n)和O(nlg n)，哪种算法最可取？为什么？ 12、设n为已在算法前边定义的整数类型，并已知n为正整数，分析下列各算法中语句的执行次数，并给出各算法的时间复杂度T(n)。 (1) int i = 1, k = 0; while (i < n-1) { k = k + 10 * i; i = i + 1; } (2) int i = 1, k = 0; do { k = k + 10 * i; i = i + 1; }while (i != n); (3) int i = 1, j = 1; while (i <= n && j <= n) { i = i + 1; j = j + 1; } (4) int x = n; /* n > 1 */ int y = 0; while(x >= (y+1)*(y+1)) y++; 选择题： 1、在数据结构中，线性结构中元素之间存在____关系。 A: 一对一 B: 一对多 C: 多对一 D: 多对多 2、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的____和运算等的学科。 A: 结构 B: 关系 C: 操作 D: 算法 3、算法分析的两个主要方面是____。 A: 空间复杂度和时间复杂度 B: 正确性和简明性 C: 可读性和文档性 D: 数据复杂性和程序复杂性 4、顺序表中逻辑上相邻的节点其物理位置也____。 A: 一定相邻 B: 不必相邻 C: 按某种规律排列 D: 无要求 5、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行____。 A: s->next=p->next; p->next=s; B: p->next=s->next; s->next=p; C: q->next=s; s->next=p; D: p->next=s; s->next=q; 6、一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是____。 A: edcba B: decba C: dceab D: abcde 7、循环队列用数组A[0,m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是____。 A: (rear-front+m)%m B: rear-front+1 C: rear-front-1 D: rear-front 8、关于空格串，下列说法中正确的有____。 A: 空格串就是空串 B: 空格串是零个字符的串 C: 空格串的长度为零 D: 空格串的长度就是其包含的空格个数 9、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为____。A: SA+140 B: SA+144 C: SA+222 D: SA+225 10、对于一棵满二叉树，m个树叶，n个节点，深度为h，则____。 A: n=h+m B: h+m=2n C: m=h-1 D: n=2h-1 11、具有65个结点的完全二叉树其深度为____。（根的层次号为1） A: 8 B: 7 C: 6 D: 5 12、满二叉树____二叉树。 A: 一定是完全 B: 不一定是完全 C: 不是 D: 不是完全 13、将一棵有100个节点的完全二叉树从上到下，从左到右依次对节点进行编号，根节点的编号为1，则编号为49的节点的左孩子编号为____。 A: 99 B: 98 C: 50 D: 48 14、如果T2是由森林T转换而来的二叉树，那么T中结点的后序遍历就是T2中结点的____。A: 先序遍历 B: 中序遍历 C: 后序遍历 D: 层次遍历 15、将递归算法转换成对应的非递归算法时，通常需要使用____。 A: 栈 B: 队列 C: 链表 D: 树 16、如果某二叉树的前序为stuwv，中序为uwtvs，那么该二叉树的后序为____。 A: uwvts B: vwuts C: wuvts数据结构复习提纲(整理)
《数据结构(c语言版)》知识点概括
数据结构与算法C语言版期末复习题
数据结构第1章作业
《数据结构概论》A卷.docx
第一章数据结构概论习题
计算机学院数据结构与算法分析期末试题(2007级B)_无答案
数据结构概述
数据结构复习要点(整理版).docx
北京交通大学数据结构与算法期末测验考试参考答案
数据结构基础知识
(完整版)数据结构概论
数据结构C语言版第1章练习题
数据结构第一章
数据结构第一章 概述习题↓
数据结构与算法上海第二工业大学二工大期末考试试卷
相关主题
文本预览