搜索
1/51数据结构习题集（自编）第一章绪论一、选择题1．数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（）和运算的学科。A．结构B．关系C．运算D．算法2．在数据结构中，从逻辑上可以把数据结构分成（）。A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．逻辑结构和存储结构3．线性表的逻辑顺序和存储顺序总是一致的，这种说法（）。A．正确B．不正确C．无法确定D．以上答案都不对4．算法分析的目的是（）。A．找出算法的合理性B．研究算法的输人与输出关系C．分析算法的有效性以求改进D．分析算法的易懂性5.算法的时间复杂度取决于（）A．问题的规模B待处理数据的初态C.A和B6．一个算法应该是（）。A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.7.下面关于算法说法错误的是（）A．算法最终必须由计算机程序实现B.为解决某问题的算法与为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上几个都是错误的8．以下与数据的存储结构无关的术语是（）。A．循环队列B.链表C.哈希表D.栈9．在下面的程序段中，对x的赋值语句的频度为（）for（i=0;in;i++）for(j=0;jn;j++)x=x+1;A．2nB．nC．n2D．log2n10．以下数据结构中，（）是非线性数据结构A．树B．字符串C．队列D．栈11.下列数据中，（）是线性数据结构。A．哈夫曼树B.有向无环图C.二叉排序树D.栈12．以下属于逻辑结构的是（）。A．顺序表B.哈希表C.有序表D.单链表二、填空题1、_______是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，________是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。（数据、数据）2、数据元素是数据的______，有些情况下也称为元素、结点、顶点、记录等。（基本单位）3、________是数据不可分割的最小单元，是具有独立含义的最小标识单位。2/51例如构成一个数据元素的字段、域、属性等都可称之为________。（数据项、数据项）4、数据的逻辑结构是指数据之间的________。逻辑结构是从________上描述数据，它与具体存储无关，是独立于计算机的。因此逻辑结构可以看作是从具体问题抽象出来的______________。（逻辑关系、逻辑关系、数学模型）5、数据的________指数据元素及其关系在计算机存储器内的表示。_________是逻辑结构在计算机里的实现，也称之为映像。（存储结构、存储结构）6、数据逻辑结构可以分为四种基本的类型，_______结构中的元素除了仅仅只是同属于一个_________________，不存在什么关系。（集合、集合）7、数据逻辑结构的四种基本类型中，________中的元素是一种一对一的关系，这种结构的特征是：若结构是非空集，则有且只有一个开始结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。（线性结构）8、数据逻辑结构的四种基本类型中，____________中的元素是一种一对多的关系。（树形结构）9、图型结构或图状结构是一种________的关系。在这种逻辑结构中，所有结点均可以有多个前驱和多个后继。（多对多）10、有时也可将树型结构、集合和图型结构称为__________，这样数据的逻辑结构就可以分为__________和________两大类。（非线性结构、线性结构、非线性机构）11、____________方式是指逻辑上相邻的结点被存储到物理上也相邻的存储单元中。这种存储结构只存储结点的数值，不存储结点之间的关系，结点之间的关系是通过存储单元的相邻关系隐含的表示出来的。（顺序存储）12、_______方式是种存储方法，不要求逻辑上相邻的结点在物理上也相邻，即数据元素可以存储在任意的位置上。（链式存储）13、_________方式是利用结点关键字的值直接计算出该结点存储单元地址，然后将结点按某种方式存人该地址的一种方法。（散列存储或哈希存储）14、所谓算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的其中每个指令表示一个或多个操作。算法的五个重要特性是__________、__________、__________、__________和__________。（有限序列、有穷性、确定性、可行性、输入、输出）15、算法的_______性是指算法必须能够在执行有限个步骤之后结束，并且每个步骤都必须在有穷的时间内完成。（有穷性）16、算法的________性是指算法中的每一个步骤必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。并且，在任何条件下，算法只能有惟一的一条执行路径，即只要输人是相同的就只能得到____________的输出结果。（确定性、相同）17、算法的____________性又称为算法的能行性，是指算法中描述的操作是可以通过已经实现的基本运算执行有限次来实现。（可行性）18、判断一个算法的好坏主要以下几个标准：________、________、________、_________。（正确性、可读性、健壮性、时间效率和空间效率）19、算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机_________的长短和___________________的大小。（运行时间、所占据空间）20、空间复杂度（SPaceComPlexity）也是度量一个算法好坏的标准，它所描述的是算法在运行过程中所占用_____________的大小。（存储空间）3/51三、判断题1．顺序存储方式只能用于存储线性结构。（×）2．数据元素是数据的最小单位。（×）3．算法的优劣与算法描述语言无关，但与所用计算机有关。(×)4．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。()5．数据的逻辑结构是指各元素之间的逻辑关系，是根据用户需要而建立的。6．数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。（）7．数据的物理结构是指数据在计算机中实际的存储形式。（）8．具有存取任一元素的时间相等这一特点的存储结构称为随机存取结构。9．算法实际上就是程序，程序也一定是算法。(×)10.在顺序存储结构中，有时也存储数据结构中元素之间的关系。(×)11.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(×)12.数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。()13.数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。(×)14.判断一个算法的好坏主要以下几个标准：正确性、有穷性、健壮性和可行性。(×)15．算法的时间复杂度T（n）=O(f(n))表示随问题规模n的增大，算法执行时间的增长率与函数f(n)的增长率相同。（）四、综合题1．用大O形式表示下面算法的时间复杂度：for（i=0；i＜m；i十十）for（j=0；j＜n；j＋＋）A[i][j]=i*j；2．写出下面算法的时间复杂度：i＝0；s=0；while(s＜n）｛i++;s+=i;｝3．写出以下算法的时间复杂度：for（i＝0;i＜m;i＋＋）for（j＝0;j＜t;j＋＋）c[i][j]=0；for（i=0；i＜m；i＋＋）for（j=o;jt;j++）for（k=0；k＜n；k＋＋）c［i］［j］＋＝a［i］［k］*b[k][j];4．写出下面算法的时间复杂度：i=1;while（i＜＝n）i=i*3;5．求下面函数中各条语句的频度和算法的时间复杂度：4/51prime（intn）｛inti＝2；while((n％i）！=0＆＆i＜sqrt(n))i++;if（i＞sqrt(n))printf（”％disaprimenumber.＼n”，n）；elseprintf（”％disnotaprimenumber.＼n”，n）；｝1.该算法的时间复杂度为：O(m×n)。2.该算法的时间复杂度为：O(n)3.该算法的时间复杂度为：O(m×n×t)。4.该算法的时间复杂度为：log3(n)。5.该算法的时间复杂度为：O(n)。6．将下列函数，按它们在n→∝时的无穷大阶数，从小到大排序。n,n-n3+7n5,nlogn,2n/2,n3,logn,n1/2+logn,(3/2)n,,n!,n2+logn从小到大排列为：logn,n1/2+logn,n,nlogn,n2+logn，n3,n-n3+7n5,2n/2,(3/2)n,n!,5/51第二章线性表一、选择题1．在一个长度为n的顺序表中删除第i个元素（0i=n）时，需要向前移动()个元素。A．n-iB．n-i+1C．n-i-1D．i+12．从一个具有n个元素的线性表中查找其值等于x的结点时，在查找成功的情况下，需平均比较()个元素结点。A．n/2B．nC．(n-1)/2D．(n+1)/23．对一个具有n个元素的线性表，建立其单链表的时间复杂度为()。A．O(n)B．O(1)C．O(n2）D．O（long2n）4．线性表采用链式存储时，其地址()。A．必须是连续的B．一定是不连续的C．部分地址必须连续D．连续与否均可以5．在一个具有n个结点的有序单链表中插人一个新的结点，使得链表仍然有序，该算法的时间复杂度是()。A．O（long2n）B．O（l）C．O（n2）D．O（n）6．线性表是()。A．一个有限序列，可以为空B．一个有限序列，不可以为空C．一个无限序列，可以为空D．一个无限序列，不可以为空7．在一个长度为n的顺序表中，向第i个位置（0一1＜n＋1）插入一个新元素时，需要向后移动()个元素。A．n-iB．n-i＋1C．n－i－1D．i＋18．如果某链表中最常用的操作是取第i个结点及其前驱，则采用()存储方式最节省时间。A．单链表B．双向链表C．单循环链表D．顺序表9．一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（）。A．98B．100C．102D．10610．在顺序存储的线性表（a1……an）中，删除任意一个结点所需移动结点的平均移动次数为()A．nB．n／2C．(n-1)/2D．（n＋l）/211．在线性表的下列存储结构中，读取第i个元素花费的时间最少的是（）。A．单链表B．双链表C．循环链表D．顺序表12．若某链表中最常用的操作为在最后一个结点之后插入一个结点和删除最后一个结点，则采用（）存储方式最节省时间。A．双链表B．单链表C．单循环链表D．带头结点的双循环链表13．在单链表中删除指针p所指结点的后继结点，则执行（）操作。A．p-next=p-next-nextB．p-next=p-nextC．p=p-next-nextD．p=p-next;p-next=p-next-next14．在一个单链表中，已知q所指结点是p所指结点的前驱，若在q和p之间插入s所指的结点，则执行（）操作。6/51A．s-next=p-next;p-next=s;B．q-next=s;s-next=p;C．p-next=s-next;s-next=p;D．p-next=s;s-next=q;15．在单链表中附加头结点的目的是为了（）。A．保证单链表中至少有一个节点B．标识单链表中首结点的位置C．方便运算的实现D．说明单链表是线性表的链式存储16．循环单链表的主要优点是（）。A．不再需要头指针了B．从表中任意一个结点出发都能扫描到整个链表C．已知某个结点的位置后，能够容易找到它的前驱D．在进行插入、删除操作时，能更好地保证链表不断开17．非空的循环单链表L的尾结点p满足（）。A．p-next=NULLB．p=NULLC．p-next=LD．p=L18．在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是()。注:双向链表的结点结构为(prior,data,next)。供选择的答案：A．p-prior=q；q-ne