当前位置：文档之家 › 深大数据结构期末复习

深大数据结构期末复习

  • 格式：doc
  • 大小：117.00 KB
  • 文档页数：7

一．判断题 （每题1分） （√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。 （√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。 （ㄨ）（3）数据元素是数据的最小单位。 （ㄨ）（4）数据的逻辑结构和数据的存储结构是相同的。 （ㄨ）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。 （√）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。 （√）（7）数据的存储结构是数据的逻辑结构的存储映像。 （√）（8）数据的物理结构是指数据在计算机内实际的存储形式。 （ㄨ）（9）数据的逻辑结构是依赖于计算机的。 （√）（10）算法是对解题方法和步骤的描述。

二．填空题 （每题1分） 1．数据有逻辑结构和 存储结构 两种结构。 2．数据逻辑结构除了集合以外，还包括：线性结构、树形结构和 图形结构 。 3. 数据结构按逻辑结构可分为两大类，它们是线性结构和 非线性结构 。 4． 树形结构 和 图形结构 合称为非线性结构。 5. 在树形结构中，除了树根结点以外，其余每个结点只有 1 个前趋结点。 6. 在图形结构中，每个结点的前趋结点数和后续结点数可以 任意多个 。 7．数据的存储结构又叫 物理结构 。 8．数据的存储结构形式包括：顺序存储、链式存储、索引存储和 散列存储 。 9．线性结构中的元素之间存在 一对一 的关系。 10．树形结构结构中的元素之间存在 一对多 的关系， 11．图形结构的元素之间存在 多对多 的关系。 12．数据结构主要研究数据的逻辑结构、存储结构和 算法（或运算） 三个方面的内容。 13．数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的 关系 的有限集合。 14．算法是一个 有穷指令 的集合。 15．算法效率的度量可以分为事先估算法和 事后统计法 。 16．一个算法的时间复杂性是算法 输入规模 的函数。 17．一个算法的空间复杂度是指该算法所耗费的 存储空间 ，它是该算法求解问题规模n的函数。 18．若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为 O（nlog2n） 。 19．若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为 O（n2） 。 20.数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 ，以及它们之间的关系和运算的学科。

三．选择题（每题1分） 1． 数据结构通常是研究数据的（ A ）及它们之间的相互联系。 A. 存储结构和逻辑结构 B. 存储和抽象 C. 联系和抽象 D. 联系与逻辑 2． 数据结构中，在逻辑上可以把数据结构分成：（ C ）。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 3． 数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（ C ）。 A. 存储结构 B. 逻辑结构 C. 顺序存储结构 D. 链式存储结构 4．非线性结构中的每个结点（ D ） 1. 无直接前趋结点 2. 无直接后继结点 3. 只有一个直接前趋结点和一个直接后继结点 4. 可能有多个直接前趋结点和多个直接后继结点

5． 链接存储的存储结构所占存储空间（ A ）。 A． 分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针 B． 只有一部分，存放结点值 C． 只有一部分，存储表示结点间关系的指针 D． 分两部分，一部分存放结点值，另一部分存放结点所占单元素 6．算法的计算量大小称为计算的（ C ） A. 现实性 B. 难度 C. 时间复杂性 D. 效率 7．数据的基本单位是（ B ） A. 数据结构 B. 数据元素 C. 数据项 D. 文件 8．每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储区里，这种存储结构称为（ A ）结构。 A. 顺序存储 B. 链式存储 C. 索引存储 D. 散列存储 9．每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（ B ）存储方式 A. 顺序 B. 链式 C. 索引 D. 散列 10．以下任何两个结点之间都没有逻辑关系的是（ D ） A. 图形结构 B. 线性结构 C. 树形结构 D. 集合 11．在数据结构中，与所使用的计算机无关的是（ C ） A. 物理结构 B. 存储结构 C. 逻辑结构 D. 逻辑和存储结构 12．下列四种基本逻辑结构中，数据元素之间关系最弱的是（ A ） A. 集合 B. 线性结构 C. 树形结构 D. 图形结构 13．与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ A ） A. 逻辑结构 B. 存储结构 C. 逻辑实现 D. 存储实现 14．每一个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明结点存储位置的表，该存储方式是（ C ）存储方式 A. 顺序 B. 链式 C. 索引 D. 散列 15．算法能正确的实现预定功能的特性称为（ A ） A. 正确性 B. 易读性 C. 健壮性 D. 高效性 16．算法在发生非法操作时可以作出处理的特性称为（ C ） A. 正确性 B. 易读性 C. 健壮性 D. 高效性 17．下列时间复杂度中最坏的是（ D ） A. O（1） B. O（ n） C. O（log2n） D. O（n2） 18．下列算法的实际复杂度是（ D ） for (i=0;ifor (j=0;ic[i][j]=i+j; A. O（1） B. O（ n） C. O（log2n） D. O（n2） 19. 算法分析的两个主要方面是（ A ）。 A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 20．计算机算法必须具备输入、输出和（ C ） A. 计算方法 B. 排序方法 C. 解决问题的有限运算步骤 D. 程序设计方法

四．分析下面各程序段的时间复杂度(每小题5分，共20分) 1. for (i=0; ifor (j=0; jA[i][j] 解： O（n*m） （2） s=0; for (i=0; ifor (j=0; js+=B[i][j]; sum=s; 解： O（n2） （3） T=A； A=B； B=T； 解： O（1） （4） x=0;y=o; for (k =1; k <=n; k ++) x++; for (i =1; i <=n; i ++) for (j=1;j<=n;j++ y++; 解： O（n2）

五． 根据二元组关系，指出它们属于何种数据结构。 (每小题10分，共30分) 1． A=（D，R），其中： D={a，b，c，d，e，f}， R={r} R={，，，，} （上式中尖括号表示括号内的结点之间关系是有向的） 解：线性结构

2． B=（D，R），其中： D={1，2，3，4，5，6}， R={（1,2）,（2,3）,（2,4）,（3,4）,（3,5）,（3,6）,（4,5）,（4,6）} 解：属于图结构 3．C=（D，R），其中： D={a，b，c，d，e，f，g，h}， R={,,,, ,,} 解：属于树结构 第一章 绪论 一、判断题 (1）数据的逻辑结构与数据元素本身的内容和形式无关。 (2）数据元素是数据的最小单位。 (3）算法是对解题方法和步骤的描述。 (4）程序和算法原则上没有区别，在讨论数据结构时可以通用。 (5）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。 (6）数据的存储结构是数据的逻辑结构的存储映像。 二、填空题 (1） 数据逻辑结构包括：______、______、______、______四种类型，树形结构和图形结构合称为：_______。 (2）数据的存储结构形式包括：_______、______、______、______。 (3) 数据元素是数据的基本单位，在某些情况下也可以称为 和 。 (4）线性结构中的元素之间存在______________的关系，树形结构中的元素之间存在__________的关系，图形结构的元素之间存在_____________的关系。 (5）算法的五个重要特性是：_______、_______、_______、_______、_______。 (6）数据结构被定义为（D,R) ，其中D是_______的有限集合，R是D上的_________的有限集合。 (7）数据结构主要研究数据的_________、___________和___________。 (8）算法是一个_______的集合；算法效率的度量可以分为_______和________。 (9) 以下程序段的时间复杂度 T ( n ) = 。 sum=0； for(i=0;i for(j=0;j sum=sum+a[i][j]; printf(“%d\n”,sum);

(10) 以下计算 2 个 n 阶矩阵乘积的算法的时间复杂度是 。 for ( i = l ; i < = n ; i + + ) { for(j=1; j < = n ; j + + ) { c[i][j]=0; for ( k = l ; k < = n ; k + + ) c[i][j]=c[i][j] + a [i][k] * b[k][j]; } } 三、选择题 (l）数据结构通常是研究数据的（ ）及它们之间的相互联系。 A．存储结构和逻辑结构 B．存储和抽象 C．联系和抽象 D．联系与逻辑 (2) 下列与数据元素有关的叙述中错误的是（ ）。 A．数据元素是有独立含义的数据最小单位 B．数据元素是描述数据的基本单位 C．数据元素可以称做结点 D．数据元素可以称做记录 (3）数据结构中，在逻辑上可以把数据结构分成：( ）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 (4）数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为 ( ）。 A．存储结构 B．逻辑结构 C．顺序存储结构 D．链式存储结构 (5）非线性结构的数据元素之间存在（ ）。 A．一对一关系 B．一对多关系 C．多对多关系 D. B 或 C (6）在非线性结构中，每个结点（ ）。 A. 无直接前驱 B．只有一个直接前驱和个数不受限制的直接后继 C．只有一个直接前驱和直接后继 D．有个数不受限制的直接前驱和直接后继 (7）除了考虑存储数据结构本身所占用的空间外，实现算法所用的辅助空间的多少称为算法的（ ）。 A．时间效率 B．空间效率 C．硬件效率 D．软件效率

合集下载

数据结构期末复习要点

数据结构期末复习要点

若需要利用形参直接访问实参，则应把形参变量说明为( )参数。

A. 指针B. 引用C. 传值D. 常值设有一个递归算法如下int fact(int n) { //n大于等于0if(n<=0) return 1;else return n*fact(n-1);}则计算fact(n)需要调用该函数的次数为（）次。

A．n B．n+1 C．n+2 D．n-1向具有n个结点的、结构均衡的二叉搜索树中插入一个元素的时间复杂度大致为( )。

A.O(1) C. O(n)B. O(nlog2n). D. O(log2n )具有n个顶点的有向无环图最多可包含( )条有向边。

A．n-1 B．n C．n(n-1)/2 D．n(n-1)图的广度优先搜索类似于树的（）次序遍历。

A. 先根B. 中根C. 后根D. 层次如果将所有中国人按照生日（不考虑年份，只考虑月、日）来排序，那么使用下列排序算法中( )算法最快。

A. 归并排序B. 希尔排序C. 快速排序D. 基数排序让元素1若，2，3依次进栈，则出栈次序不可能出现（）种情况。

A．3，2，1 B．2，1，3 C．3，1，2 D．1，3，2在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）A．n B．n-1 C．n+1 D．2*n如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（）方法最快。

A．起泡排序B．快速排序C．堆排序D．直接选择排序设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列表项应能够至少容纳（）个表项。

（设搜索成功的平均搜索长度为Snl={1+1/(1-α)}/2其中α为装填因子）A．400 B．526 C．624 D．6761、在程序运行过程中可以扩充的数组是__________分配的数组。

这种数组在声明它时需要使用数组指针。

2、栈是一种限定在表的一端进行插入和删除的线性表，又被称为___________表。

数据结构期末复习

数据结构期末复习


3.队列中元素的进出原则为 _____________________ 。 4.设数组A[1..10,1..8]的基地址为2000,每个元素占2个存储单元,若以 行序为主序顺序存储,则元素A[4,5]的存储地址为_____；若以列序为 主序顺序存储,则元素A[4,5]的存储地址为______。 5.一棵深度为4的满二叉树有______个非终端结点。 6.若一棵二叉树中有11个度为2的结点,则它有_____个叶子。 7.顺序查找1000个元素的顺序表,当使用监视哨时,若查找成功,比较关键 字的次数至少为____次, 最多为____次；若查找失败,比较关键字的次 数为____次。 8.对长度为400的表采用分块(区)查找,最理想的块长为____。 三、回答下列问题 (每小题5分,共10分) 1.线性表的存储结构,在什么情况下采用顺序结构? 为什么? 2.二叉树有哪几种基本形态? 画图说明之。 四、试画出下列存储结构图(每小题4分,共20分) 1.数组A[1..2,0..2] 的以列序为主序的顺序存储结构。 2.依次将元素 A,C,D,B 插入一个初始状态为空的链式栈中,试画出所有 插入完成之后的链式栈。 3.二叉树的顺序存储结构:
} } 七：算法设计 1：设有1000个无序的元素，需排出前10个最大（小）的元素，你认为 采用哪种排序方法最快？为什么？ 2：试用C或类C语言编写一高效算法，将一顺序存储的线性表（设元素 均为整型量）中所有零元素向表尾集中，其他元素则顺序向表头方向集 中
一、单项选择题 1.数据的不可分割的基本单位是____。 A.元素 B.结点 C.数据类型 D.数据项 2.下列算法suanfa2的时间复杂度为____。 int suanfa2(int n) { int t=1； while(t<=n) t=t*2； return t； } A.O(log2n) B.O(2n) C.O(n2) D.O(n) 3.____又称为FIFO表。 A.队列 B.散列表 C.栈 D.哈希表 4.若6行8列的数组以列序为主序顺序存储,基地址为1000,每个元素占2 个 存储单元,则第5行第3列的元素(假定无第0行第0列)的地址是____。 A.1086 B.1032 C.1068 D.答案A,B,C都不对 **5.广义表(a,((b,( )),c),(d,(e)))的深度是____。 A.5 B.4 C.3 D.2 **7.与中缀表达式a+b*c-d等价的前缀表达式是____。 A.+a-*bcd B.*+-abcd C.-+a*bcd D.abcd+*二、填空 1.一个数据结构在计算机中的表示(映象)称为 ________________。 2.线性表中 ____________________________ 称为表的长度。
数据结构期末考试复习总结

数据结构期末考试复习总结

《数据结构》期末考试题型及分值（1）简答题6题*5分=30分简要回答要点（2）分析题6题*5分=30分给出结果（3）设计题1题*10分=10分设计思想及结果（4）编程题1题*10分=10分完整代码（5）综合题1题*20分=20分抽象数据类型的定义、表示、实现、算法分析{定义=功能（ADT）表示=存储结构体实现=算法（基本操作）算法分析=时间、空间复杂度}考试概念有：1.数据结构{一、线性表（栈-队-列-串-数组-广义表-逻辑结构-存储结构-运算结构）二、非线性表（集合-树-图）}2.抽象数据类型数据对象-数据关系-基本操作3.算法性质-要求（设计）-效率（度量）4.实例查找：高效查找算法排序：高效的排序算法分析题考试题目参考（1）1-2-3-4-5-6顺序建BBST（2）6-5-4-3-2-1顺序建BBST简答题实例设计题：（1）（2）数据结构试卷（一）三、计算题（每题 6 分，共24分）1. 在如下数组A 中存储了一个线性表，表头指针为A [0].next ，试写出该线性表。

A 0 1 2 3 4 5 6 7data 60 50 78 90 34 40 next357241线性表为：（78，50，40，60，34，90）⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0111010*******110101011102.请画出下图的邻接矩阵和邻接表。

3. 已知一个图的顶点集V 和边集E 分别为：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。

用克鲁斯卡尔算法得到的最小生成树为：(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)204.画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。

数据结构期末复习指导.doc

数据结构期末复习指导.doc

数据结构期末复习指导考试题型及分值：1.单项选择题（每题3分，共15分）2.填空题（每空3分，共45分）3.运算题（每小题8分，共16分）4.算法应用题（每小题8分，共16分）5.编写算法（8分）一、单选题1.若需要利用形参胃接访问实参，则应把形参变量说明为（）参数。

A指针B引用C值D函数2.假定利用数31 a[N]顺序存储一个栈，用top表示栈顶指针，top==-1表示栈空，并已知栈未空，当退栈并返回栈顶元索时所执行的操作为（）。

A return a[—top];B return a[top--];C return a[++top];D return a[top++];3.假定一个链队的队首和队尾指针分别为f和r,则判断队空的条件为（）。

A f==rB f!=NULLC r!=NULLD f=NULL4.在一棵具有n个结点的二叉树屮，所有结点的空指针数等于（）。

A nB n-1C n+1D 2n5.从堆中删除一个元素的时间复杂度为（）。

A 0（1）B 0（n ）C 0（log2n ）D 0（ n log2n）6.利用n个值作为叶子结点的权牛成的哈夫曼树屮共包含有（）个结点。

An B n+1C 2nD 2n~l7.在一个带权连通图G'P，劝值最小的边一定包含在6的（）中。

A最小生成树B生成树C广度优先生成树D深度优先生成树& 一个有n个顶点和n条边的无向图一定是（）A连通的B不连通的C无回路D有回路9.在一个长度为n的顺序存储的线性表屮，删除第i个元素（lWiWn）时，需要从前向后依次前移（）个元素。

A.n-iB. n-i+1C. n-i-1D. i10.设一个广义表中结点的个数为n,则求广义表深度算法的时间复杂度为（）。

A. 0（1）B. 0（n）C. 0（n2）D. 0（log2n）11.假定一个顺序队列的队首和队尾指针分别为f和“则判断队空的条件为（）。

A. f+l==rB. r+l=fC.仁二0D. f=r12.从堆中删除一个元素的时间复杂度为（）。