数据结构期末练习题

1.数据的不可分割的基本单位是(A)。A．元素B．结点C．数据类型D．数据项2.计算机处理数据的最小单位是（D）。A．元素B．结点C．数据类型D．数据项3.算法是指(C)。A．计算方法B．排序方法C．解决问题的有限运算步骤D．查找方法4.顺序存储结构中数据元素之间的逻辑关系是由（C）表示的A线性结构B非线性结构C存储位置D指针5.单循环链表的主要优点是（B）。A不再需要头指针了B从表中任一结点出发都能扫描到整个链表；C已知某个结点的位置后，能够容易找到它的直接前趋；D在进行插入、删除操作时，能更好地保证链表不断开。6.一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是(C)。A54321B45321C43512D123457.常对数组进行的两种基本操作是(B)A．建立和删除B．索引和修改C．插入和修改D．插入和索引8.算法分析的两个主要方面是（A）。A空间性能和时间性能B正确性和简明性C可读性和文档性D数据复杂性和程序复杂性9.在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（B）结构。//需满足先进先出原则A栈B队列C数组D线性表10.二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9，则存放A至少需要（D）个字节。A90B180C240D54011.讨论树、森林和二叉树的关系，目的是为了（B）。此题的解决步骤是如果出现一个三元素顺序是a、b、c，且acb,则为不可能序列A借助二叉树上的运算方法去实现对树的一些运算B将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题C将树、森林转换成二叉树D体现一种技巧，没有什么实际意义12.算法在发生非法操作时可以作出处理的特性称为（A）。A健壮性B确定性C可行性D正确性13.二叉排序树中，最小值结点的（A）。A左指针一定为空B右指针一定为空C左、右指针均为空D左、右指针均不为空14.算法指的是（A）。A对特定问题求解步骤的一种描述，是指令的有限序列。B计算机程序C解决问题的计算方法D数据处理15.算法分析的目的是(C)。A．找出数据结构的合理性B．研究算法中输入和输出的关系C．分析算法的效率以求改进D．分析算法的易读性和文档性16.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋，则采用（A）存储方法最节省时间。A顺序表B单链表C双链表D单循环链表17.在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（B）操作。As-next=p-next;p-next=s;Bq-next=s;s-next=p;Cp-next=s-next;s-next=p;Dp-next=s;s-next=q;(1)s-next=p-next;(2)p-next=s;(3)s=p-next;分别代表什么含义？1)把p的下一个节点接到s的下一个节点上2)把s接到p的下一个节点上3)把p的一下个节点赋值给s18.若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（D）。A不确定Bn-iCn-i-1Dn-i+119.设有两个串p和q，求q在p中首次出现的位置的运算称作（B）。A连接B模式匹配C求子串D求串长20.将数组称为随机存取结构是因为（B）。A数组元素是随机的B对数组任一元素的存取时间是相等的C随时可以对数组进行访问D数组的存储结构是不定的21.一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（D）成立。An=h+mBh+m=2nCm=h-1Dn=2m-122.队列的操作原则是（B）。A．先进后出B．先进先出C．只能进行插入D．只能进行删除23.散列技术中的冲突指的是（D）。A两个元素具有相同的序号B两个元素的键值不同，而其他属性相同C数据元素过多D不同键值的元素对应于相同的存储地址24.在栈中，栈顶指针top指示(B)。A．栈底元素的位置B．栈顶元素的位置C．栈中任何元素的位置D．以上均不对25.将数组称为随机存取结构是因为（B）。A．数组元素是随机的B．对数组任一元素的存取时间是相等的C．随时可以对数组进行访问D．数组的存储结构是不定的26.下面（C）不是算法所必须具备的特性。A有穷性B确切性C高效性D可行性27.在一棵树中，（B）没有后继结点。A．根结点B．叶子结点C．分支结点D．所有结点28.若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（D）存储方法最节省时间。A单链表B带头指针的单循环链表C双链表D带尾指针的单循环链表29.设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（C）。A6B4C3D230.二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9,A的第8列和第5行共占（C）个字节。A114B54C108D54031.在一棵树中，每个结点最多有(B)个前驱结点。A．0B．1C．2D．任意多个32.一个队列的入队顺序是1，2，3，4，则队列的输出顺序是（B）。A4321B1234C1432D324133.下面的说法中，不正确的是（C）。A数组是一种线性结构B数组是一种定长的线性结构C除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等D数组的基本操作有存取、修改、检索和排序等，没有插入与删除操作34.队列的操作原则是(B)。A．先进后出B．先进先出C．只能进行插入D．只能进行删除35.如果结点A有3个兄弟，B是A的双亲，则结点B的度是（D）。A1B2C3D436.静态查找与动态查找的根本区别在于（B）。A它们的逻辑结构不一样B施加在其上的操作不同C所包含的数据元素的类型不一样D存储实现不一样37.在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为栈底，以top作为栈顶指针，当出栈时，top的变化为（B）。A不变Btop=top-1Ctop=0Dtop=top+138.算法是指（C）A．计算方法B．排序方法C．解决问题的有限运算步骤D．查找方法39.算法能正确地实现预定功能的特性称为(A)。A．正确性B．易读性C．健壮D．高效率40.线性表的顺序存储结构是一种（A）的存储结构。A随机存取B顺序存取C索引存取D散列存取41.假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（B）。A树B图C线性表D集合42.数组通常具有两种基本运算，即（B）A．创建和删除B．读取和修改C．插入和删除D．排序和查找43.线性表采用链接存储时，其地址（D）。A必须是连续的B部分地址必须是连续的C一定是不连续的D连续与否均可以44.下面（C）不属于特殊矩阵。A对角矩阵B三角矩阵C稀疏矩阵E对称矩阵45.线性表的第一个元素叫做（A）。A．表头元素B．表尾元素C．前驱元素D．后继元素46.线性表的最后一个元素叫做（B）。A．表头元素B．表尾元素C．前驱元素D．后继元素47.设二叉树有n个结点，则其深度为（C）。An-1BnClog2n向下取整D不能确定48.G是一个非连通无向图，共有28条边，则该图至少有（D）个顶点。A6B7C8D949.在以下哪种情况下，不能执行出栈操作？（B）取出一个点作为一个无向图，其余点作为另一个无向图，则其点连线最多，使用的点最少，8282)1(282nnnCn，共需9个点当深度（高度）为h时，结点数n满足：hhn221,可知hnh2log1，所以其深度h为n2log向下取整+1A．栈满B．栈空C．任何情况均可D．任何情况均不可50.下列数据结构中，（D）不是线性结构。A．栈B．队列C．数组D．树51.栈又称为（B）表。A．先进先出B．后进先出D．不进不出D．以上均不对52.在以下哪种情况下，不能执行入栈操作？（A）A．栈满B．栈空C．任何情况均可D．任何情况均不可53.下面（C）不属于特殊矩阵。A．对角矩阵B．三角矩阵C．稀疏矩阵D．对称矩阵54.一个队列的入队顺序是1，2，3，4，则队列的输出顺序是（B）。A．4321B．1234C．1432D．324155.在一棵树中，每个结点最多有（B）个前驱结点。A．0B．1C．2D．任意多个56.非空树有（B）个根结点。A．0B．1C．2D．任意多个57.串是一种特殊的线性表，其特殊性体现在(B)A．可以顺序存储B．数据元素是一个字符C．可以链接存储D．数据元素可以是多个字符58.在以下哪种情况下，不能执行出栈操作？(B)A．栈满B．栈空C．任何情况均可D．任何情况均不可59.数组中的数据元素的类型（A）。A．必须相同B．不必相同C．一定不能相同D．以上都不对60.下列数据结构中，(D)不都是线性结构。A．栈和队列B．队列和数组C．数组和串D．树和队列61.关于空串与空格串，下面说法正确的是(C)。A．空串与空格串是相同的B．空串与空格串长度是相同的C．空格串中存放的都是空格D．空串中存放的都是NULL62.递归可采用下面哪种结构实现（B）//栈实现了递归A．队列B．栈C．树D．图63.栈操作的原则是(B)A．先进先出B．后进先出C．只能进行插入D．只能进行删除64.在关键字序列(4,12,23,55,56，67，88)中，使用折半查找法查找56，需要比较多少次（C）A.1B.2C.3D.465.如果一个函数在其函数体中调用自己本身，则该函数叫做(B)。A．重载函数B．递归函数C．普通函数D．成员函数66.线性表若采用链式存储结构时，要求内存中可用存储单元的地址(D)A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续或不连续都可以67.设计一个判别表达式中左右括号是否配对的算法，采用（B）数据结构最佳。A顺序表B栈C队列D链表68.下面的说法中，不正确的是（D）。A对称矩阵只须存放包括主对角线元素在内的下（或上）三角的元素即可。B对角矩阵只须存放非零元素即可。C稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储。D稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储。69.按（B）遍历二叉排序树得到的序列是一个有序序列。A前序B中序C后序D层次二．应用题1.计算下列式子的时间复杂度。(1)2n3+100log2n+12)(3nO(2)5+n2+n!)!(nO(3)10+20n+2n)2(nO2.有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，列出所有可能的出栈序列。abc,acb,bca,bac,cba3.栈S=(a，b，c)，在栈中插入1个元素d，再从栈中删除一个元素，请写出S的变化过程。S=(a,b,c,d)-S=(a,b,c)4.队列Q=(a，b，c)，在队列中插入1个元素d，再从队列中删除一个元素，请写出Q的变化过程。Q=(a,b,c,d)-Q=(b,c,d)5.假设下图是一棵二叉树，请根据下图回答下列问题①哪个是根结点?A②哪些是叶子结点?DEG③哪个是结点C的双亲?A④哪些是结点C的孩子?EF⑤C的兄弟是哪个结点？B⑥F的堂兄弟是哪个结点？D⑦哪些结点是C的子孙结点？EFG⑧树的深度是多少?4⑨树的度是多少？2⑩请写出该树的先根遍历序列、中根序列、后根序列、层次遍历序列。先序：ABDCEFG中序：BDAECGF后序：DBEGFCA层序：ABCDEFG6.分别用prim算法和kruskal算法构造下图的最小生成树。√7.若对序列(56，23，67，4，88，12，55)采用直接插入排序法和冒泡排序法ABCGFED进行排序，请写出每一趟的结果。直接插入排序法：（23,56）67,4,88,12,55（23,56,67）4,88,12,55（4,23,56,67）88,12,55（4,23,56,6