《数据结构习题库》由会员分享，可在线阅读，更多相关《数据结构习题库（101页珍藏版）》请在金锄头文库上搜索。
1、- 1 -1 绪论绪论沈阳理工大学应用技术学院信息与控制学院计算机科学与技术教研室2011-5-8- 2 -数据结构复习题：绪论数据结构复习题：绪论 单选题 1、在数据结构中，与所使用的计算机无关的数据叫_结构。 A 存储|B 物理|C 逻辑|D 物理和存储 2、在数据结构中，从逻辑上可以把数据结构分成_。 A 动态结构和静态结构|B 紧凑结构和非紧凑结构|C 线性结构和非线性结构|D 内部结构和外部结构图 3、数据结构在计算机内存中的表示是指_。 数据的存储结构|数据结构|数据的逻辑结构|数据元素之间的关系 4、在数据结构中，与所使用的计算机无关的是数据的_结构。 逻辑|存储|逻辑和存储|物
2、理 5、在以下的叙述中，正确的是_。 线性表的线性存储结构优于链表存储结构|二维数组是其数据元素为线性表的线性表|栈的操作方式是先进 先出|队列的操作方式是先进后出 6、在决定选取何种存储结构时，一般不考虑_。 各结点的值如何|结束个数的多少|对数据有哪些运算|所用编程语言实现这种结构是否方便 7、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储_。 数据的处理方法|数据元素的类型|数据元素之间的关系|数据的存储方法 8、下面说法错误的是_。 (1) 算法原地工作的含义是指不需要任何额外的辅助空间 (2) 在相同的规模 n 下，复杂度 O(n)的算法在时间上总是优于复杂度 O(2n)的
3、算法 (3) 所谓时间复杂度是指最坏情况下，估计算法执行时间的一个上界 (4) 同一个算法，实现语句的级别越高，执行效率越低 (1)|(1)、(2)|(1)、(4)|(3) 9、通常要求同一逻辑结构中的所有数据元素具有相同的特性。这意味着_。 数据元素具有同一特点|不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致|每 个数据元素都一样|数据元素所包含的数据项的个数要相等 10、以下说法正确的是_。 数据元素是数据的最小单位|数据项是数据的基本单位|数据结构是带结构的数据项的集合|一些表面上很不 相同的数据可以有相同的逻辑结构 11、_是数据的最小单元,_是数据的基本单位.
4、数据项|数据元素|信息项|表元素 12、数据结构是指_以及它们之间的_. (1)数据元素 (2)结构|(1)计算方法 (2)关系|(1)逻辑存储 (2)运算|(1)数据映像 (2)算法 13、计算机所处理的数据一般具备某种内在的关系,这是的指_. 数据和数据之间存在的某种关系|元素和元素之间存在某种关系|元素内部具有某种结构|数据项和数据项之 间存在某种关系 14、数据的逻辑结构可以分为_两类. 动态结构和表态结构|紧凑结构和非紧凑结构|线性结构和非线性结构|内部结构和外部结构 15、数据的逻辑结构是指_关系的整体. 数据元素之间逻辑|数据项之间逻辑|数据类型之间|存储结构之间 16、在存储数
5、据时,通常不仅要存储各数据元素的值,而且还要存储_.- 3 -数据的处理方法|数据元素的类型|数据元素之间的关系|数据的存储方法 17、在数据的存储结构中,一个存储结点存储一个_. 数据项|数据元素|数据结构|数据类型 18、在计算机的存储器中表示时,物理地址和逻辑地址直接对应并且是连续的,称之为_. 逻辑结构|顺序存储结构|链式存储结构|以上都对 19、数据采用链式存储结构时,要求_. 每个结点用占一片连续的存储区域|所有结点占用一片连续的存储区域|结点的最后一个数据域是指针类型| 每个结点有多少个后继,就设多少个指针域 20、数据的运算_. 效率与采用何种存储结构有关|是根据存储结构来定义
6、的|有算术运算和关系运算两大类|必须用程序设计语 言来描述 21、下列说法中,不正确的是_. 数据元素是数据的基本单位|数据项是数据中不可分割的最小可标识单位|数据可由若干个数据元素构成|数 据项可由若干个数据元素构成 22、_不是算法的基本特性. 可行性|长度有限|在规定的时间内完成|确定性 23、计算机中算法指的是解决某一问题的有限运算序列,它必须具备输入、输出、_. 可行性、可移植性和可扩充性|可行性、有穷性和确定性|确定性、有穷性和稳定性|易读性、稳定性和确定 性 24、以下不属于算法特性的是_. 可行性|有输入|确定性|健壮性 25、下面关于算法的说法正确的是_. 算法最终必须由程序
7、实现|算法的有穷性是对于任意的一组输入值必须在有穷步骤后结束|算法的可行性是 指指令不能有二义性|以上几个都是错误的 26、算法的时间复杂度与_有关 问题规模|计算机硬件性能|编译程序质量|程序设计语言 27、算法分析的主要任务是分析_. 算法是否具有较好的可读性|算法中是否存在语法错误|算法的功能是否符合设计要求|算法的执行时间和问 题规模之间的关系 28、某算法的时间复杂度为 O(n2),表明该算法的_. 问题规模是 n2|执行时间等于 n2|执行时间与 n2成正比|问题规模与 n2成正比 29、算法分析的目的是_. 找出数据结构的合理性|研究算法中输入和输出关系|分析算法的效率以求改进|
8、分析算法的易读性和文档性 30、线性表是具有 n 个_的有限序列。 表元素|字符|数据元素|数据项 31、线性表是_。 一个有限序列，可以为空|一个有限序列，不可以为空|一个无限序列，可以为空|一个无限序列，不可以为 空 32、线性表采用链表存储时，其地址_。 必须是连续的|一定是不连续的|部分地址必须是连续的|连续与否均可以 33、链表不具备的特点是_。 可随机访问任一结点|插入删除不需要移动元素|不必事先估计存储空间|所需空间与其长度成正比 34、线性表的静态存储结构与顺序存储结构相比优点是_。 所有的操作算法实现简单|便于随机存取|便于插入和删除|便于利用零散的存储器空间- 4 -35、
9、设线性表有 n 个元素，以下操作中，_在顺序表上实现比在链表上实现效率更高。 输出第 i(1sqrt(n)printf “是一素数“;else printf “不是一素数“; (2) sum1(int n)- 10 -int p=1,sum=0,i;for (i=1;ilink=f 即可。 8、在双向链表存储结构中，删除 p 所指的结点时需修改指针_。 9、在双向链表存储结构中，删除 p 所指的结点的前趋结点（若存在）时需修改指针_。 10、根据线性表的链式存储结构，每个结点所含指针的个数，链表分为单链表和_。 11、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上_。 12、链表不具备
10、的特点是_。 13、不带头结点的单链表 head 为空的判定条件是_。 14、带头结点的单链表的 head 为空的判定条件是_。 15、带头结点的双循环表 L 为空表的条件是_。 16、非空的循环单链表 head 的尾结点(由 p 所指向)满足_。 17、在循环双链表的 p 所指结点之前插入 s 所指结点的操作是_。 18、若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用_存储方 式最节省运算时间。 19、某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用_存储方式 最节省运算时间。 20、需要分配较大空间，插入和删除不需要移动元素的线性表
11、，其存储结构是_。 21、如果最常用的操作是取第 i 个结点及其前驱，则采用_存储方式最节省时间。 22、在一个具有 n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是_。 23、在一个长度为 n(n1)的单链表上，设有头和尾两个指针，执行_操作与链表的长度有关。 24、设线性表有 n 个元素，以下算法中，_在顺序表上实现比在链表上实现效率更高。 25、设线性表中有 2n 个元素，算法_，在单链表上实现要比在顺序表上实现效率更高。 26、与单链表相比，双链表的优点之一是_。 27、如果对线性表的运算只有 4 种，即删除第一个元素，删除最后一个元素，在第一个元素前面插入新元 素，
12、在最后一个元素的后面插入新元素，则最后使用_。 28、如果对线性表的运算只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用 _。 29、设有两个长度为 n 的单链表，结点类型相同。若以 h1 为表头指针的链表是非循环的，以 h2 为表头指 针的链表是循环的，则_。 30、在长度为 n 的_上，删除第一个结点，其算法的时间复度为 O(n)。 31、将两个各有 n 个元素的有序顺序表归并成一个有序顺序表，其最少的比较次数是_。 32、带头结点的单链表 L 为空的判定条件是_。- 15 -33、在一个具有 n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是_。 3
13、4、在一个长度为 n(n1)的带头结点的单链表 h 上， ，另设有尾指针 r(指向尾结点)，执行_操作与链 表的长度有关。 35、在一个双链表中，在*p 结点之后插入结点*q 的操作是_。 36、在一个双链表中，在*p 结点之前插入*q 结点的操作是_。 37、在一个双链表达式，删除*p 结点的操作是_。 38、在一个双链表中，删除*p 结点之后的一个结点的操作是_。 39、非空的循环单链表 L 的尾结点(由 p 所指向)满足_。 40、带头结点的双循环链表 L 为空表的条件是_。 41、若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用_存储 方式最节省运算时间。
14、42、如果对含有 n(n1)个元素的线性表的运算只有 4 种:删除第一个元素；删除最后一个元素；在第一个元 素前面插入新元素；在最后一个元素的后面插入新元素，则最好使用_。 43、某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，则采用_存储方 式最节省运算时间。 44、设有两个长度为 n 的单链表，结点类型相同，若以 h1 为头结点的链表是非循环的，以 h2 为头结点指 针的链表是循环的，则_。 45、在长度驎 n(n1)的_上，删除第一个元素，其算法的时间复杂度为 O(n)。 46、元素 A、B、C、D 依次进顺序栈后，栈顶元素是_，栈底元素是_。 47、经过以下栈运算
15、后，X 的值是_。 InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s,x);48、经过以下的栈运算后，StackEmpty(s)的值是_。 InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y)49、设一个栈的输入序列为 A、B、C、D，则借助一个栈所得到的输出序列不可能是_。 50、若线性表最常用的运算是存取第 i 个元素及其前驱的值,则采用_存储方式节省时间. 51、链表不具备的特点是_. 52、在一个长度为 n 的顺序存储的线性表中，向第 i 个元素(1next=p-next; p-next=s;|p-next=s-next; s-next=p;|q-next=s; s-next=p;|p-next=s; s
