数据结构复习题及答案(12级)

一、选择题。(每小题2分，共40分)(1)计算机识别.存储和加工处理的对象被统称为____A____。A.数据B.数据元素C.数据结构D.数据类型(2)数据结构通常是研究数据的____A_____及它们之间的联系。A.存储和逻辑结构B.存储和抽象C.理想和抽象D.理想与逻辑(3)不是数据的逻辑结构是____A______。A.散列结构B.线性结构C.树结构D.图结构(4)数据结构被形式地定义为D,R,其中D是____B_____的有限集，R是____C_____的有限集。A.算法B.数据元素C.数据操作D.逻辑结构(5)组成数据的基本单位是____A______。A.数据项B.数据类型C.数据元素D.数据变量(6)设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={1，2，2，3，3，4，4，1}，则数据结构A是____A______。A.线性结构B.树型结构C.图型结构D.集合(7)数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为___C____。A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构(8)在数据结构的讨论中把数据结构从逻辑上分为___A____。A.内部结构与外部结构B.静态结构与动态结构C.线性结构与非线性结构D.紧凑结构与非紧凑结构(9)对一个算法的评价，不包括如下____B_____方面的内容。A.健壮性和可读性B.并行性C.正确性D.时空复杂度(10)算法分析的两个方面是__A____。A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性(11)线性表是具有n个___C_____的有限序列（n≠0)。A.表元素B.字符C.数据元素D.数据项(12)线性表的存储结构是一种____B____的存储结构。A.随机存取B.顺序存取C.索引存取D.HASH存取(13)在一个长度为n的顺序表中，向第i个元素（1≤i≤n＋１）之前插入一个新元素时，需要向后移动____B____个元素。A.n-iB.n-i+1C.n-i-1D.i(14)链表是一种采用____B____存储结构存储的线性表；A.顺序B.链式C.星式D.网状(15)下面关于线性表的叙述错误的是___D_____。A.线性表采用顺序存储必须占用一片连续的存储空间B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现(16)设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B之间插入结点X的操作序列为__B______。A.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；(17)设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为___A_____。A.p-next=p-next-nextB.p=p-nextC.p=p-next-nextD.p-next=p(18)下列说法哪个正确？____D______A.堆栈是在两端操作、先进后出的线性表B.堆栈是在一端操作、先进先出的线性表C.队列是在一端操作、先进先出的线性表D.队列是在两端操作、先进先出的线性表(19)栈和队列的共同点是_____C_______。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点(20)栈与一般线性表的区别主要在_____D______。A、元素个数B、元素类型C、逻辑结构D、插入、删除元素的位置(21)链栈与顺序栈相比，比较明显的优点是_____D_____。A、插入操作更加方便B、删除操作更加方便C、不会出现下溢的情况D、不会出现上溢的情况(22)以下数据结构中哪一个是非线性结构___D______。A.队列B.栈C.线性表D.二叉树(23)若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为_____C______。A.iB.B.n=iC.n-i+1D.不确定(24)当利用大小为N的一维数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行____B______语句修改top指针。A.top++B.top--C.top=0D.top(25)4个元素进S栈的顺序是A,B,C,D，经运算POP(S)后，栈顶元素是___C_______。A.AB.BC.CD.D(26)一个栈的输入序列是a,b,c,d,e,则栈的不可能的输出序列是____C_____。A.edcbaB.decbaC.dceabD.abcde(27)设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是____C______。A.n-iB.n-1-iC.n+1-iD.不能确定(28)字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成___B___个不同的字符串？A.15B.14C.16D.21(29)设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为____D_______。A.top=top+1;B.top=top-1;C.top-next=top;D.top=top-next;(30)设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是____C_____。A.6B.4C.3D.2(31)若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为____B_____。A.1和5B.2和4C.4和2D.5和1(32)设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为____C_____。A.R-FB.F-RC.(R-F+M)%MD.(F-R+M)%M(33)设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为____C_____。A.front-next=s；front=s；B.s-next=rear；rear=s；C.rear-next=s；rear=s；D.s-next=front；front=s；(34)如下陈述中正确的是___A______。A.串是一种特殊的线性表B.串的长度必须大于零C.串中元素只能是字母D.空串就是空白串(35)下列关于串的叙述中，正确的是___D______。A.串长度是指串中不同字符的个数B.串是n个字母的有限序列C.如果两个串含有相同的字符，则它们相等D.只有当两个串的长度相等，并且各个对应位置的字符都相符时才相等(36)字符串的长度是指___C______。A.串中不同字符的个数B.串中不同字母的个数C.串中所含字符的个数D.串中不同数字的个数(37)两个字符串相等的充要条件是____C______。A.两个字符串的长度相等B.两个字符串中对应位置上的字符相等C.同时具备(A)和(B)两个条件D.以上答案都不对(38)串是一种特殊的线性表，其特殊性体现在____B_______。A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符(39)设有两个串p和q，求q在p中首次出现的位置的运算称作____B______。A.连接B.模式匹配C.求子串D.求串长(40)设串sI=ABCDEFG,s2=PQRST,函数con(x,y)返回x和y串的连接串,subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,1en(s2))，subs(sl,len(s2)，2))的结果串是__D___。A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF(41)函数substr(“DATASTRUCTURE”，5，9)的返回值为___A______。A.“STRUCTURE”B.“DATA”C.“ASTRUCTUR”D.“DATASTRUCTURE”(42)设串S=”IAMATEACHER!”，其长度是____D______。A.16B.11C.14D.15(43)假定在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶子结点数为____B____。A.15B.16C.17D.47(44)假定一棵二叉树的结点数为18个，则它的最小高度____B____。A.4B.5C.6D.18(45)在一棵二叉树中第五层上的结点数最多为____C____。A.8B.15C.16D.32(46)在一棵具有五层的满二叉树中，结点总数为____A____。A.31B.32C.33D.16(47)已知8个数据元素为(34、76、45、18、26、54、92、65)，按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为____B____。A.1B.2C.D.4(48)由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为____C____。A.23B.37C.44D.46(49)在树中除根结点外，其余结点分成m(m≥0)个____A____的集合T1,T2,T3...Tm,每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点(1≤i≤m)。A.互不相交B.可以相交C.叶结点可以相交D.树枝结点可以相交(50)如果结点A有三个兄弟，而且B是A的双亲，则B的出度是____B____。A.3B.4C.5D.1(51)在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____B____倍。A.1/2B.1C.2D.4(52)具有n个顶点的无向完全图，边的总数为____D____条。A.n-1B.nC.n+1D.n*(n-1)/2(53)在无向图G的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于____C____。A.i+jB.i-jC.1D.0(54)图的深度优先或广度优先遍历的空间复杂性均为____A____。(访问标志位数组空间)A.O(n)B.O(e)C.O(n-e)D.O(n+e)(55)请指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用折半法查找关键码12需做____C___次关键码比较。A.2B.3C.4D.5(56)对线性表进行折半查找时，必须要求线性表____C____。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列(57)设二叉排序树中有n个结点，则在二叉排序树的平均查找长度为___B_____。A.O(1)B.O(log2n)C.O(n)D.O(n2)(58)依次插入序列(50，72，43，85，75，20，35，45，65，30)后建立的二叉搜索树中，查找元素35要进行__A___元素间的比较。A.4次B.5次C.7次D.10次(59)设散列表中有m个存储单元，散列函数H(key)=key%p，则p最好选择___B_____。A.小于等于m的最大奇数B.小于等于m的最大素数C.小于等于m的最大偶数D.小于等于m的最大合数(60)____D_____是HASH查找的冲突处理方法。A.求余法B.平方取中法C.二分法D.开放地址法(61)当α的值较小时，散列存储通常比其他存储方式具有_____B______的查找速度。A.较慢B.较快C.相同D.不确定(62