数据结构习题及答案

第1章数据结构一、选择题1.算法指的是（）。A计算机程序B解决问题的计算方法C排序方法D解决问题的有限运算序列2.在数据的树形结构中，数据元素之间为（）的关系。A0:0B1:1C1:nDm:n3.数据的存储结构包括顺序、链接、散列和（）4种基本类型。A索引B数组C集合D向量4.一个数组元素a[i]与（）的表示等价。A&a+iB*(a+i)C*a+iDa+i5.若只需要利用形参间接访问实参指针所指向的对象，而形参本身具有相应的存储空间，则应把形参变量说明为（）参数。A指针B引用C值D指针引用6.若只需要利用形参实现对实参值的拷贝，函数体操作形参时与实参无关，则应把形参变量说明为（）参数。A指针B引用C值D指针引用7.下面程序的时间复杂性的量级为（）。inti=0，s1=，s2=0；while（i++n）{if(i%2)s1+=i;elses2+=i;}A.O(1)B.O(1bn)C.O（n）D.O(2n)8.下面程序段的时间复杂度为（）。for(inti=0;im;i++)for(intj=0;jn;j++)a[i][j]=i*j;A.O(m2)B.O(n2)C.O(m+n)D.O(m*n)9.执行下面程序段时，S语句的执行次数为（）。for(inti=1;i=n;i++)for(intj=1,j=i;j++)S;A.n(n-1)/2B.n(n+1)/2C.n2/2D.n10.在一个长度为n的顺序存储结构的线性表中，向第i个元素（1≤i≤n+1）位置插入一个元素时，需要从后向前依次后移（）个元素。A.n-iB.n-i+lC.n-i-lD.i11.在一个长度为n的顺序存储结构的线性表中，删除第i个元素（1≤i≤n+1）时，需要从前向后依次后移（）个元素。A.n-iB.n-i+lC.n-i-lD.i12.在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（）。A.(n+1)/2B.n/2C.nD.n+113.在一个顺序表的表尾插入一个元素的时间复杂度为（）。A.O(n)B.O(1)C.O(n*n)D.O(lbn)14.在一个顺序表中的任何位置插入一个元素的时间复杂度为（）。A.O(n)B.O(n/2)C.O(1)D.O(n2)15.在一个单链表中删除p所指向结点的后继结点时，其算法的时间复杂度为（）。A.O(n)B.O(n/2)C.O(1)D.O(n2)16.线性表的链式存储比顺序存储更有利于进行（）操作。A.查找B.表尾插入和删除C.按值插入和删除D.表头的插入和删除17.线性表的顺序存储比链式存储更有利于进行（）操作。A.查找B.表尾插入和删除C.按值插入和删除D.表头的插入和删除18.在一个单链表中，若要在P所指向的结点之后插入一个新结点，则需要相继修改（）个指针域的值.A.1B.2C.3D.419.在一个带头结点的循环双向链表中，若要在P所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。A.2B.3C.4D.620.在一个表头指针为ph的单链表中，若要向表头插入一个由指针p指向的结点，则应执行（）操作。A.ph=p;p-next=ph;B.p-next=ph;ph=p;C.p-next=ph;p=ph;D.p-next=ph-next;ph-next=p;21.在一个表头指针为ph的单链表中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（）操作。A.q-next=p-next;p-next=q;B.p-next=q-next;q=p;C.q-next=p-next;p-next=q;D.p-next=q-next;q-next=p;22.在一个单链表HL中，若要删除由指针q所指向结点的后继结点（若存在的话），则执行（）操作。A.p=q-next;p-next=q-next;B.p=q-next;q-next=p;C.p=q-next;q-next=p-next;D.q-next=q-next-next;q-next=q;23.在一个带头结点的循环双向链表中，若要在指针p所指向的结点之后插入一个q指针所指向的结点，则需要对q-next赋值为（）。A.P-priorB.p-nextC.p-next-nextD.p-prior-prior24.在一个带头结点的循环双向链表中，若要在指针p所指向的结点之前插入一个q指针所指向的结点，则需要对p-prior-next赋值为（）。A.qB.pC.p-nextD.p-prior25.在一个带头结点的循环双向链表中，若要删除指针p所指向的结点则执行（）操作。A.p-prior-next=p-next;p-next-prior=p-prior;B.p-next-prior=p;p-next=p-next-next;C.p-prior-next=p;p-next=p-next-prior;D.p=p-next;p-prior-next=p-prior;26.栈的插入和删除操作在（）进行。A.栈顶B.栈底C.任意位置D.指定位置27.当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。A.top++B.top--C.top=0D.top=N-128.假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，用top=N+1表示栈空，该数组所存储的栈的最大长度为N，则表示栈满的条件为（）。A.top==1B.top==-1C.top=0D.top=N-129.假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，用top==-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作为（）。A.a[--top]=xB.a[top--]=xC.a[++top]=xD.a[top++]=x30.假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，用top==-1表示栈空，并已知栈未空，当退栈并返回栈顶元素时所执行的操作为（）。Areturna[--top]Breturna[top--]Creturna[++top]Dreturna[top++]31.假定一个链式栈的栈顶指针用top表示，该链式栈为空的条件（）。A.top！=NULL;B.top==top-next;C.top==NULL;D.top！=top-next;32.假定一个链式栈的栈顶指针用top表示，每个结点结构为,当p所指向的结点进栈时，执行的操作为（）。A.p-next=top;top=top-next;B.top=p;p-next=top;C.p-next=top-next;top-next=p;D.p-next=top;top=p;33.假定一个链式栈的栈顶指针用top表示，每个结点结构为,退栈时所执行的操作为（）。A.top-next=top；B.top=top-data;C.top=top-next;D.top-next=top-next-next;34.若让元素1，2，3，4依次进栈，则出栈次序不可能出现（）的情况。A.3，2，1，4B.2，1，4，3C.4，3，2，1D.1，4，2，3.35.在一个顺序循环队列中，队首指针指向队首元素的（）位置。A前一个B后一个C当前D最后36.当利用大小为N的数组循环存储一个队列时，该队列的最大长度为（）。A.N-2B.N-1C.ND.N+137.从一个顺序循环队列中删除元素时，首先需要（）。A.前移队首指针B.后移队首指针C.取出队首指针所指位置上的元素D.取出队尾指针所指位置上的元素38.假定一个顺序循环队列的队首和队尾指针分别用f和r表示，则判断队空的条件为（）。A.f+1==rB.r+1==fC.f==0D.f==r39.假定一个顺序循环队列存储于数组a[N]，其队首和队尾指针分别用f和r表示，则判断队满的条件为（）。A.（r-1）%N==fB.（r+1）%N==fC.（f-1）%N==rD.（f+1）%N==r40.假定利用数组a[N]循环顺序存储一个队列，其队首和队尾指针分别用f和r表示，并已知队列未满，当元素x入列时所执行的操作为（）。A.a[++r%N]=xB.a[r++%N]=xC.a[--r%N]=xD.a[r--%N]=x41.假定利用数组a[N]循环顺序存储一个队列，其队首和队尾指针分别用f和r表示，并已知队列未空，当出列并返回队首元素时所执行的操作为（）。A.returna[++r%N]B.returna[--r%N]C.returna[++f%N]D.returna[f++%N]42.假定一个链式队列的队首和队尾指针分别为front和rear，则判断队空的条件为（）。A.front==rearB.front！=NULLC.rear！=NULLD.front==NULL43.假定一个链式队列的队首和队尾指针分别为front和rear，每个结点结构为,当出列时所进行的操作为（）。A.front=front-nextB.rear=rear-nextC.front-next=rear；rear=rear-nextD.front=front-next；front-next=rear；44.假定一个带头结点的循环链式队列的队首和队尾指针分别用front和rear表示，则判断对空的条件为（）。A.front=rear-nextB.rear==NULLC.front==NULLD.front==rear45.假定一个链式队列的队首和队尾指针分别为front和rear，每个结点结构为包含值域data和指针域next,则使p所指结点入列所执行的操作为（）。A.p-next=NULL；rear=rear-next=p；B.p-next=rear-next；rear=rear-next=p；C.p-next=front；front=p；D.p-next=front-next；front-next=p；46.在一个长度为N的数组空间中，循环顺序存储着一个队列，该队列的队首和队尾指针分别用front和rear表示，则该队列中数组元素个数为（）。A.（rear-front）%NB.（rear-front+N）%NC.（rear+N）%ND.（front+N）%N47.二维数组A[12,10]采用行优先存储，每个数据元素占用4个存储单元，该数组的首地址（即A[0，0]的地址）为1200，则A[6，5]的地址为（）。A.1400B.1404C.1372D.146048.有一个M×N的矩阵A，若采用行优先进行顺序存储，每个元素占用8个字节，则Aij(1≤i≤M,1≤j≤N)元素的相对字节地址（相对首元素地址而言）为（）。A.（（i-1）×N+j）×8B.（（i-1）×N+j-1）×8C.（i×N+j-1）×8D.（（i-1）×N+j+1）×849.有一个N×N的下三角矩阵A，若采用行优先进行顺序存储，每个元素占用k个字节，则Aij(1≤i≤N,1≤j≤i)元素的相对字节地址（相对首元素地址而言）为（）。A.（i×（i+1）/2+j-1）×4B.（i×i/2+j）×4C.（i×（i-1）/2+j-1）×4D.（i×（i-1）/2+j）×450.树中所有结点的度等于所有结点数加（）。A.0B.1C.-1D.251.在一棵树中，（）没有前驱结点。A.树枝结点B.叶子结点C.树根结点D.空结点52.在一棵树中，每个结点最多有（）个前驱结点。A.0B.1C.2D.任意多个53.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。A.2B.1C.0D.-154.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）。A.nB.n-1C.n+1D.2n55.在一棵具有n个结点的二叉树的第i层上，最多具有（）个结点。A.2iB.2i+1C.2i-1D.2n56.