数据结构复习资料(专)

选择题1.数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运算等的学科。（①A②B）①A．操作对象Ｂ．计算方法Ｃ．逻辑存储Ｄ．数据映象②A．结构Ｂ．关系Ｃ．运算Ｄ．算法2.数据结构被形式地定义为（K，R），其中K是①的有限集合，R是K上的②有限集合。（①B②D）①A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．逻辑结构②A．操作Ｂ．映象Ｃ．存储Ｄ．关系3.在数据结构中，从逻辑上可以把数据结构分成①。（C）A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构4.线性表的顺序存储结构是一种①A的存储结构，线性表的链式存储结构是一种②B的存储结构。A．随机存取B．顺序存取C．索引存取D．散列存取5.算法分析的两个主要方面是（A）。A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性6.计算机算法指的是①，它必具备输入、输出和②等五个特性。（①C②B）①A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法②A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法①。（B）A.正确B.不正确8.线性表若采用链式存储结构时，要求内存中可用存储单元的地址①。（D）A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续或不连续都可以9.在以下的叙述中，正确的是①。（B）A.线性表的线性存储结构优于链表存储结构B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式和先进后出10.下列排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关？____A.直接选择排序B.起泡排序C.快速排序D.直接插入排序11.下列排序算法中，____算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。A.堆排序B.冒泡排序C.快速排序D.归并排序12.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法①。（A）A.正确B.不正确13.在一个单链表中，若删除p所指结点的后续结点，则执行_______A.p-next=p-next-nextB.p=p-next-nextC.p-next=p-nextD.p=p-next;p-next=p-next-next14.下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(log2n)的是____。A.堆排序B.冒泡排序C.直接选择排序D.快速排序15.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是____。(B)A.110B.108C.100D.12016.一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是____。(C)A.edcbaB.decbaC.dceabD.abcde17.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为__(C)_。A.iB.n-iC.n-i+1D.不确定18.栈结构通常采用的两种存储结构是____。(A)A.顺序存储结构和链式存储结构B.散列方式和索引方式C.链表存储结构和数组D.线性存储结构和非线性存储结构19.判定一个栈ST（最多元素为m0）为空的条件是____。(B)A.ST—top!=0B.ST—top==0C.ST—top!=m0D.ST—top==m020.判定一个栈ST（最多元素为m0）为栈满的条件是____。(D)A.ST—top！=0B.ST—top==0C.ST—top！=m0D.ST—top==m021.栈的特点是__(B)__，队列的特点是__(A)__。A.先进先出B.先进后出22.一个队列的入列序列是1，2，3，4，则队列的输出序列是__(B)__。A.4，3，2，1B.1，2，3，4C.1，4，3，2D.3，2，4，123.判定一个循环队列QU（最多元素为m0）为空的条件是____。(A)A.QU—front==QU—rearB.QU—front！=QU—rearC.QU—front==（QU—rear+1）%m0D.QU—front！=（QU—rear+1）%m024.判定一个循环队列QU（最多元素为m0）为满队列的条件是____。(C)A.QU—front==QU—rearB.QU—front！=QU—rearC.QU—front==（QU—rear+1）%m0D.QU—front！=（QU—rear+1）%m025.循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是____。(A)A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-front26.栈和队列的共同点是____。(C)A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点27.设循环队列中数组的下标范围是1～n，其头尾指针分别为f和r，则其元素个数为____。A.(r-f+n)modnB.r-f+1C.(r-f)modn+1D.r-f28.不带头结点的单链表head为空的判定条件是____。(A)A.head==NULLB.head—＞next==NULLC.head—＞next==headD.head!=NULL29.带头结点的单链表head为空的判定条件是____。(B)A.head==NULLB.head—＞next==NULLC.head—＞next==headD.head!=NULL30.非空的循环单链表head的尾结点（由p所指向）满足____。(C)A.p—＞next==NULLB.p==NULLC.p—＞next==headD.p==head31.在一个单链表HL中,若要在当前由指针P指向的结点后面插入一个由q指向的结点,则应执行的语句为()A.p=q；p-next=q；B.q-next=p-next；p-next=q；C.p-next=q-next；p=q；D.p-next=q；q-next=p；32.在循环双链表的p所指结点之后插入s所指结点的操作是____。(D)A.p—＞right=s;s—＞left=p;p—＞right—＞left=s;s—＞right=p—＞right;B.p—＞right=s;p—＞right—＞left=s;s—＞left=p;s—＞right=p—＞right;C.s—＞left=p;s—＞right=p—＞right;p—＞right=s;p—＞right—＞left=s;D.s—＞left=p;s—＞right=p—＞right;p—＞right—＞left=s;p—＞right=s;33.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行_(C)_。A.s—＞next=p—＞next;p—＞next=s;B.p—＞next=s—＞next;s—＞next=p;C.q—＞next=s;s—＞next=p;D.p—＞next=s;s—＞next=q;34.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行____。(B)A.s—＞next=p;p—＞next=s;B.s—＞next=p—＞next;p—＞next=s;C.s—＞next=p—＞next;p=s;D.p—＞next=s;s—＞next=p;35.在一个单链表中，若删除p所指结点的后续结点，则执行____。(A)A.p—＞next=p—＞next—＞next；B.p=p—＞next;p—＞next=p—＞next—＞next；C.p—＞next=p—＞next;D.p=p—＞next—＞next；36.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较____个结点。A.nB.n/2C.(n-1)/2D.(n+1)/237.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是____。(B)A.O（1）B.O（n）C.O(n2)D.O(nlog2n)11.11.若线性表最常用的操作是存取第i个元素及其前趋的值，则采用__D__存储方式最节省时间。A.单链表B.双链表C.单循环链表D.顺序表38.向一个栈顶指针为HS的链栈(不带空的头结点)中插入一个s所指结点时，执行_(C)_。A.HS—＞next=s;B.s—＞next=HS—＞next;HS—＞next=s;C.s—＞next=HS;HS=s;D.s—＞next=HS;HS=HS—＞next;39.从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行____。(不带空的头结点)(D)A.x=HS;HS=HS—＞next;B.x=HS—＞data;C.HS=HS—＞next;x=HS—＞data;D.x=HS—＞data;HS=HS—＞next;40.空串与空格串是相同的，这种说法____。BA.正确B.不正确41.串是一种特殊的线性表，其特殊性体现在____。DA.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符42.设有两个串p和q，求q在p中首次出现的位置的运算称作____。BA.连接B.模式匹配C.求子串D.求串长43.设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是____。DA.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF44.常对数组进行的两种基本操作是____。CA.建立与删除B.索引和修改C.查找和修改D.查找与索引45.二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要__①D__个字节；M的第8列和第5行共占__②B__个字节。①A.90B.180C.240D.540②A.108B.114C.54D.6046.数组A中，A的每个元素长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是____。CA.80B.100C.240D.27047.数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为__C__。A.SA+141B.SA+144C.SA+222D.SA+22548.数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[5][8]的起始地址为__B__。A.SA+141B.SA+180C.SA+222D.SA+22549.1.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法__A__。A.正确B.错误50.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法_B___。A.正确B.错误51.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____。(参考：2^(h-1)+1)A.2^hB.2^(h-1)C.2^(h+1)D.h+152.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是__D__。A.acbedB.decabC.deabcD.cedba53.设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是B。A．a在b的右方B．a在b的左方C．a是b的祖先