数据结构复习题

数据结构复习题Tag内容描述：<p>1、第九章 查找 一、 选择题 1.若查找每个记录的概率均等，则在具有 n 个记录的连续顺序文件中采用顺序查找法查找 一个记录，其平均查找长度 ASL 为( )。 A (n-1)/2 B. n/2 C. (n+1)/2 D. n 2. 下面关于二分查找的叙述正确的是 ( ) A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且 只能从小到大排列 B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表 只能以顺序方式存储 3. 用二分（对半）查找表的元素的速度比用顺序法( ) A必然快 B. 必然慢 C. 相等 D. 不能确定 4. 具有 12 个关键字的有。</p><p>2、数据结构（本）期末综合练习期末综合练习一一、单项选择题1数据的物理结构（ D ）。A与数据的逻辑结构无关 B仅仅包括数据元素的表示C只包括数据元素间关系的表示 D包括数据元素的表示和关系的表示2数据元素是数据的基本单位，它（ C ）。A只能有一个数据项组成 B至少有二个数据项组成C可以是一个数据项也可以由若干个数据项组成D至少有一个数据项为指针类型3从n个数中选取最大元素，（ C ）。A基本操作是数据元素间的交换 B算法的时间复杂度是O(n2)C算法的时间复杂度是O(n) D需要进行(n+1)次数据元素间的比较4线性表的顺序结构中，（ C ）。</p><p>3、一判断题（下列各题，正确的请在前面的括号内打；错误的打）第1章（）（1）数据的逻辑结构与数据元素本身的内容和形式无关。（）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（）（3）数据元素是数据的最小单位。（）（4）数据项是数据的基本单位。（）（5）数据的逻辑结构和数据的存储结构是相同的。（）（6）数据的逻辑结构是各数据元素之间的逻辑关系，是用户按使用需要而建立的。（）（7）数据的物理结构是指数据在计算机内实际的存储形式。（）（8）从逻辑关系上讲，数据结构主要分为线性结构和。</p><p>4、一、选择题。(每小题2分，共40分)(1) 计算机识别.存储和加工处理的对象被统称为____A____。A.数据 B.数据元素 C.数据结构 D.数据类型(2) 数据结构通常是研究数据的____ A _____及它们之间的联系。A.存储和逻辑结构 B.存储和抽象 C.理想和抽象 D.理想与逻辑(3) 不是数据的逻辑结构是____ A ______。A.散列结构 B.线性结构 C.树结构 D.图结构 (4) 数据结构被形式地定义为,其中D是____ B _____的有限集，R是____ C _____的有限集。A.算法 B.数据元素 C.数据操作 D.逻辑结构(5) 组成数据的基本单位是____ A ______。 A.数据项 B.数据类型C。</p><p>5、数据结构练习题习题1 绪论1.1 单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的 、数据信息在计算机中的 以及一组相关的运算等的课程。 A操作对象计算方法逻辑结构数据映象 A存储结构 关系 运算 算法2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是 的有限集合，R是D上的 有限集合。 A算法 数据元素 数据操作 数据对象 A操作 映象 存储 关系3. 在数据结构中，从逻辑上可以把数据结构分成 。A动态结构和静态结构 紧凑结构和非紧凑结构 线性结构和非线性结构 内部结构和外部结构4. 算法分析的目的。</p><p>6、第一章概论 自测题答案 一、填空题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。2. 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。3. 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。4. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。6在线性结构中，第一个。</p><p>7、1 绪论沈阳理工大学应用技术学院信息与控制学院计算机科学与技术教研室2011-5-8数据结构复习题：绪论单选题1、在数据结构中，与所使用的计算机无关的数据叫____结构。A存储|B物理|C逻辑|D物理和存储2、在数据结构中，从逻辑上可以把数据结构分成______。A动态结构和静态结构|B紧凑结构和非紧凑结构|C线性结构和非线性结构|D内部结构和外部结构图3、数据结构在计算机内存中的表示是指_______。数据的存储结构|数据结构|数据的逻辑结构|数据元素之间的关系4、在数据结构中，与所使用的计算机无关的是数据的______结构。逻辑|存储|逻辑和存储。</p><p>8、数据结构试题一、 单选题1、 在数据结构的讨论中把数据结构从逻辑上分为 （）A 内部结构与外部结构 B 静态结构与动态结构C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。2、采用线性链表表示一个向量时，要求占用的存储空间地址（）A 必须是连续的 B 部分地址必须是连续的C 一定是不连续的 D 可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ ）。A n B n/2 C (n-1)/2 D (n+1)/24、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ ）。A slink = plink; plink = s; B 。</p><p>9、第一章 绪 论一，选择题1组成数据的基本单位是（）A数据项B数据类型C数据元素D数据变量2数据结构是研究数据的（）以及它们之间的相互关系。A理想结构，物理结构 B理想结构，抽象结构C物理结构，逻辑结构 D抽象结构，逻辑结构3算法分析的两个主要方面是（ ）A正确性和简单性 B可读性和文档性C数据复杂性和程序复杂性 D时间复杂度和空间复杂度4算法分析的目的是（）。A 找出数据结构的合理性 B研究算法中的输入和输出的关系C分析算法的效率以求改进D分析算法的易懂性和文档性5. 算法的时间复杂度取决于（ ）A问题的规模 B. 待处理数据的初态。</p><p>10、华育国际清华IT学习认证中心二年考试题A卷注意事项：1）除了需要在试卷封皮写明考生的姓名信息之外，整个试卷中不得做任何形式的书写或标记，否则试卷成绩做废；2）考试完毕，不得将所有考卷、答题卡、草稿纸带离考场，否则试卷成绩做废；3）作弊雷同考卷，成绩一律为0分；4）考试完毕交卷时，必须与监考老师确认考试提交内容后方可离开考场。1.DotNet题目用C#语言开发的源代码文件被C#编译器编译成。(选择1项)A) 中间语言（IL）代码B)C#代码C)机器码D)以上都不是2.DotNet题目在C#语言中，使用下列哪种访问修饰符的方法，可以被同一程序集。</p><p>11、第一章 概论一、选择题1、研究数据结构就是研究（ D ）。A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是（ A ）。A. 空间复杂度和时间复杂度B. 正确性和简单性C. 可读性和文档性 D. 数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ）。A. 图 B. 树C. 广义表 D. 栈4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（ B ）等5个特性。A. 可执行性、可移植性和可扩充性B. 可执行性、有穷性和确定性C. 确定性。</p><p>12、数据结构复习答案一、选择填空1. 下面关于线性表的叙述中，错误的是哪一个？（ ）A）线性表采用顺序存储，必须占用一片连续的存储单元。B）线性表采用顺序存储，便于进行插入和删除操作。C）线性表采用链接存储，不必占用一片连续的存储单元。D）线性表采用链接存储，便于插入和删除操作。2. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。A）顺序表 B）双链表 C）带头结点的双循环链表 D）单循环链表3. 链表不具有的特点是（ ）。 A）插入、删除不需要移动元素 B）可随机。</p><p>13、第1章 绪论1、填空题1.常见的数据结构有_线性__结构，__树形___结构，__图形__结构等三种。2.常见的存储结构有__顺序存储_______结构，__链式存储____结构等两种。3.数据的基本单位是_数据元素___，它在计算机中是作为一个整体来处理的。4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，__线性结构____和__非线性结构___。2、应用题1、给出以下算法的时间复杂度.void fun(int n)int i=1,k=100;while(in)k=k+1;i=i+2;时间复杂度为____O（n）_____。2、给出以下算法的时间复杂度.void fun2(int n)int i=1,k=100;while(in)。</p><p>14、一、 算法设计题（每题15分，共60分）答题要求：用自然语言说明所采用算法的思想；给出每个算法所需的数据结构定义，并做必要说明；写出对应的算法程序，并做必要的注释。1、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域next。假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留一个。3、约瑟夫环问题（Josephus问题）是指编号为1、2、，n的n（n0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的。</p><p>15、第3章 栈和队列答案：一、选择题1-5 BCBCB 6-10 BCCDD 11-15 BDBBD 16-20 CCBDB16题解释:一般只需修改队头指针，不过当队列里面只有一个结点时，需要同时修改队尾指针。二、判断题1-5 6-10 11-16 三、填空题1.栈顶、栈底 2. 入栈、出栈 3. 队列、先进先出 4. 栈 5. 队列 6.先进先出 7. (R-P+N) % N 8. n-1 牺牲一个存储单元、设标记 栈底、两栈顶指针相邻（即值之差的绝对值为1）1.没有、一 2. 数据域、指针域 3. 前驱 4. 前驱、后继 5. 前驱、后继 6.头结点 7. 循环链表 8. n-1 9. 栈 后进先出 10.SXSSXSXX 11.3，1，2 12. 牺牲一个存储。</p><p>16、第10章 内部排序一、选择题（每小题1分，共10分）1.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后放在已排序序列的合适位置，该排序方法称为（ A ）排序法。A.插入排序 B.选择排序 C.希尔排序 D.二路归并排序2.下列排序算法中( C )排序在一趟结束后不一定能选出一个元素放在其最终位置上。A.选择 B.冒泡 C.归并 D.堆3.若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ C ）。A. 38, 40, 46, 56, 79, 84 B. 40, 38, 46, 79, 56, 84 C. 40, 38，。</p><p>17、第四章 串一、选择题1下面关于串的的叙述中，哪一个是不正确的？（ ）【北方交通大学 2001 一、5（2分）】A串是字符的有限序列 B空串是由空格构成的串C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储2 若串S1=ABCDEFG, S2=9898 ,S3=#,S4=012345,执行concat(replace(S1,substr(S1,length(S2),length(S3),S3),substr(S4,index(S2,8),length(S2)其结果为（ ）【北方交通大学 1999 一、5 （25/7分）】AABC#G0123 BABCD#2345 CABC#G2345 DABC#2345EABC#G1234 FABCD#1234 GABC#012343设有两个串p和q，其中q是p的子串，。</p><p>18、第一课 绪论一、选择题1算法的计算量的大小称为计算的（ ）。A效率 B复杂性 C现实性 D难度参考答案：B2算法的时间复杂度取决于（ ）。A问题的规模 B待处理数据的初态 CA和B参考答案：C3计算机算法指的是（ ）。A计算方法 B排序方法 C解决问题的步骤序列 D调度方法参考答案：C4计算机算法必须具备（ ）这三个特性。A可执行性、可移植性、可扩充性 B可执行性、确定性、有穷性C确定性、有穷性、稳定性 D易读性、稳定性、安全性参考答案：B5下面关于算法说法错误的是（ ）。A算法最终必须由计算机程序实现B为解决某问题的算法同为该问题编写的。</p><p>19、数据结构习题一、名词解释1.数据、数据元素、数据项、数据结构、数据的逻辑结构、数据物理结构、顺序存储、链式存储、算法、时间复杂度、空间复杂度 。2.线性表、顺序表、单链表 、双向链表 、循环链表 、双向循环链表 、三个概念的区别：头指针、头结点、首元结点(第1个元素结点)。3.栈（顺序栈、链栈）、队列（顺序队、链队）、循环队列、递归、稀疏矩阵、三元组。4.树、叶子结点、结点的度、树的度、树的高(深)度、二叉树、遍历、满二叉树、完全二叉树 、哈夫曼树、WPL、哈夫曼编码。5.图（有向、无向）、网、边、弧、度、入度、出度、。</p>