笔试数据结构与算法1

1、三级数据库技术第2章 数据结构与算法本部分占总分的15%主要内容：数据结构与算法基本概念线性表的定义、存储和运算树型结构的定义、存储和运算查找排序22.1基本概念考点1 数据结构基本概念1、数据 采用计算机能识别、存储和处理的符号总称。是对现实世界事务的描述 数据元素 数据的基本单位，数据集合的个体 一个数据元素由一个或多个数据项组成 数据项是数据的最小单位42、数据结构 数据之间的关系 数据结构包括三方面内容： 逻辑关系、在计算机中的存储方式、在数据上定义的运算集合5数据结构数据的逻辑结构数据的存储结构数据的运算线性结构线性表栈和队列非线性结构树形结构(二叉树、树的遍历)顺序结构链式结构索引

2、结构散列结构插入删除查找顺序查找、二分法查找排序6数据的逻辑结构什么是数据的逻辑结构？数据的逻辑结构是指数据元素之间的逻辑关系，与数据的存储无关，是独立于计算机的。数据的逻辑结构可分成2类线性结构非线性结构春夏秋冬父亲儿子女儿7数据的存储结构什么是数据的存储结构？数据的存储结构又称为物理结构，是指数据元素及其关系在计算机内存中的表示，即数据的逻辑结构在计算机存储器中的实现。数据的存储结构可分为哪4类？顺序结构、链式结构、索引结构、散列结构数据的存储结构与逻辑结构的关系同一逻辑结构可以采用不同的存储结构8数据的运算定义在逻辑结构上，实现在存储结构上9考点2 主要的数据存储方式顺序存储方式和链式存

3、储方式是最主要的内种存储方式 顺序存储方式，主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。 （逻辑上相邻物理上也相邻）10线性表（K1,K2,K3,K4,K5)逻辑相邻物理相邻示意图顺序存储结构的主要特点如下：结点中没有链接信息域，只有自身的信息域，存储密度大，空间利用串高。数据结构中第i个结点的存储地址Li可由下述公式计算求得。 LiL1十(i1)m其中，L1为第一个节点的存储地址，m为每个节点所占用的存储单元个数。插入、删除运算会引起相应结点的大量移动。112链式存储方式线性表（K1,K2,K3,K4,K5)逻辑相邻

4、物理相邻示意图12链式存储方式特点：有表示链接信息的指针,存储空间利用率低,存储密度小，逻辑上相邻的结点在物理上不必邻接，可用于线性表、树和图等多种逻辑结构的存储表示插入、删除操作灵活方便13算法分析与设计 算法的五个特征 输入（0个或多个输入） 输出（1个或多个输出）有穷性（在有限时间内完成）确定性（执行结果确定的）有效性（程序是可以实现的）算法分析-时间代价和空间代价14考题1、下列哪些是数据结构研究内容I、数据的采集与清洗 II、数据的逻辑组织III、数据的集成V、数据传输 IV、数据的检索 A、仅II和III B、II和VC、仅I、II、IV D、I、III和IVB 2009.042、

5、下列哪个术语与数据存储结构无关？A、顺序表 B、双链表 C、线性表 D、散列表C153、下列与算法有关的叙述中，哪个不正确？A、运算是数据结构的一个重要方面，运算的实现步骤用算法描述B、算法是精确定义的一系列规则，它指出怎样从给定输入信息经过有限步骤产生输出C、算法设计采用由粗到细，由抽象到具体逐步求精的方法D、对于算法的分析，指的是分析算法运行所要占用的机器时间，即算法的时间代价D 2008.094、下列关于链式存储结构叙述中，哪个选项正确？I、逻辑相邻物理上不必相邻II、每个节点都包含恰好一个指针域III、用指针体现元素逻辑联系IV、结点中的指针都不能为空 V、可以通过计算直接确定某个结点

6、的存储地址A、仅I和II B、仅I和III C、仅I、III和V D、仅II、IV和VB 2008.04165、下列关于数据结构基本概念的叙述中，哪一条是不正确的？A） 数据是采用计算机能够识别、存储和处理的方式，对现实世界的事物进行的描述B）数据元素（或称结点、记录等）是数据的基本单位C）一个数据元素至少由两个数据项组成D）数据项是有独立含义的数据最小单位C 2007.046、下列关于链式存储结构的叙述中，哪些是正确的？I逻辑上相邻的结点物理上不必邻接II 每个结点都包含恰好一个指针域III 用指针来体现数据元素之间逻辑上的联系IV 可以通过计算机直接确定第 i 个结点的存储地址V 存储密度

7、小于顺序存储结构A）I、II和III B）I、II、III和IVC）II、IV和V D）I、III和VD 2007.04177、下列关于数据运算的叙述中，哪条不正确？ A、数据运算是数据结构的一个重要方面 B、数据运算的具体实现在数据的逻辑结构上进行 C、检索是一种常用的运算 D、插入是一种常用的运算B18填空题1、数据结构包括三方面的内容：数据的逻辑结构、数据的存储结构、数据的【3】运算 2006.092、散列存储的基本思想是由节点的【1】决定节点的存储位置关键码值 192.2线性表（重点）顺序表链表栈队列串不同的存储结构的线性表叫法不同顺序存储的线性表：顺序表链式存储的线性表：链表散列方式

8、存储的线性表：散列表在线性表上运算不同叫法不同插入和删除在线性表一端，栈插入和删除在线性表两端进行，队列21考点1 顺序表和一维数组顺序表元素位置计算机 元素n元素i元素2元素1起始位置LoLo+mLo+(i-1)*mLo+(n-1)*mLi=L0+(i-1)*mi从1开始1、所有元素所占的存储空间是连续的2、各元素在存储空间中是按逻辑顺序存放的22顺序表的插入和删除元素移动次数插入算法的效率(数据元素的移动次数)最好情况：最坏情况：平均情况：0nn/2删除算法的时间复杂度(数据元素的移动次数)最好情况：最坏情况： 平均情况：0n-1(n-1)/223考点2 链表（这两年没有考这个类型题）链式

9、存储方式就是在每个结点中至少包括一个指针域（存放下个结点的地址），用指针来体现数据元素之间逻辑上的联系。链表分为线性链表和非线性链表1536元素21400元素11346元素3元素41345数据域指针域hh空指针链表中指针指向后继结点，最后的结点指针为空(,nil)需要一个指针head指向第一个结点链表的重要特点：插入和删除灵活，只需修改指针24链表的查找、插入和删除操作infolink指针数据结点25dhppp查找结束线性链表的查找操作查找C26dh线性链表的插入操作abdchPQ1、Mlink=Q2、P link=M或者1、Mlink=Plink2、P link=M27线性链表的删除操作删除

10、Q指向结点dhabdchPQP link=Q link或P link=Plink link28循环链表a1ana2h双向链表a1a2anha1a2ana3h线性链表29双链表 在单链表中只有一个指针指向后继，要找前驱很困难，在单链表结点再增加一个指针指向前驱建立了双向链表flinkinforlink指针指向后继数据结点指针指向前驱30双向链表插入pq1、qrlink=prlink2、qflink=p3、prlinkflink=q4、prlink=q执行顺序不能调换31考点3 栈栈是一种特殊的线性表，是限定在一端进行插入和删除的线性表（后进先出，LIFO。栈顶和栈底入栈和出栈（只能在栈顶进行）a

11、 aaa入栈出栈栈顶n-1n21栈底栈可以顺序存储，也可以链式存储32栈的操作 push(s，x)：往栈s中插入(或推入)一个位为x的元素。pop(s，x)：从栈s中删除(或弹出)一个位为x的元素。top(s，x)：把栈s的栈顶儿素读到变量x中，栈保持不变。empty(s)：判断栈s是否为空栈，是则返问值为真。Makempty(s)：将栈s置为空栈33考点4 队列队列是一种特殊的线性表，允许在一端进行插入操作，在另一端进行删除操作，FIFO(LILO)。队头和队尾入队和出队出队 a1 a2 an 入队队头队尾34zh队列：可能出现假溢出现象解决：采用循环队列（依然为顺序存储）队列的存储方式也有

12、顺序存储方式和链式存储方式两种35考点 5 串串(字符串)，是由零个或多个字符组成的有限序列注意：空串和空格串是不同的36考题1、基于以下描述：有一个初始为空的栈和输入序列A、B、C、D、E、F、G：现发过如下操作：push, push, top, pop, push, push,top, push, pop, pop, pop.（10）下列哪一个是正确的从栈中删除元素的序列？ A）BE B）BD C）BEDC D）BDECA进栈，B进栈，读B，B出栈，C进栈，D进栈，读D，E进栈，E出栈，D出栈，C出栈C（11）下列哪一个是上述操作序列完成后栈中的元素列表（从底到顶） A）A B）BD C）

13、ABCE D）ABCDEA （2007.04）372、栈S最多容纳4个元素，现有6个元素A、B、C、D、E、F顺序入栈，下列哪个序列是可能的出栈序列A、EDCBAF B、BCEFAD C、CBEDAF D、ADFEBCA答案：只有4个元素，出栈的不可能为EB答案：A在D之后D答案：B在C之后C （2006.09）383、在包含1000个元素的线性表中实现如下各运算，哪一个所需的执行时间最短？A线性表按顺序方式存储，查找关键码值为666的结点B线性表按链接方式存储，查找关键码值为666的结点C线性表按顺序方式存储，查找线性表中第900个结点D线性表按链接方式存储，查找线性表中第900个结点C 顺

14、序存储适合随机访问 （2005.09）4、在包含1000个元素的线性表中实现如下各运算，哪一个所需的执行时间最长？A线性表按顺序方式存储，在线性表的第100个结点后面插入一个新结点B线性表按链接方式存储，在线性表的第100个结点后面插入一个新结点C线性表按顺序方式存储，删除线性表的第900个结点D线性表按链接方式存储，删除指针P所指向的结点A 移动元素时间长 （2007.09，2005.09）395、双链表的每个结点包括两个指针域。其中rlink指向结点的后继，llink指向结点的前驱。如果要在p所指结点前面插入q所指的新结点，下列哪一个操作序列是正确的？ Ap.rlink.llink:=q；p.rlink:=q；q.llink:=p；q.rlink:=p.rlink； Bp.llink.rlink:=q；p.llink:=q；q.rlink:=p；q.llink:=p.llink； Cq.llink:=p；q.rlink:=p.rlink；p.rlink.llink:=q；p.rlink:=q； Dq.rlink:=p；q.llink:=p.llink；p.llink.rlink: