发布时间 : 星期一 文章数据结构习题及答案更新完毕开始阅读
第1章 数据结构
一、选择题
1.算法指的是（）。
A计算机程序 B解决问题的计算方法
C排序方法 D解决问题的有限运算序列
2.在数据的树形结构中，数据元素之间为（ ）的关系。 A 0:0 B 1:1 C 1:n D m:n
3.数据的存储结构包括顺序、链接、散列和（ ）4种基本类型。 A索引 B数组 C集合 D向量 4.一个数组元素a[i]与（ ）的表示等价。
A &a+i B *(a+i) C *a+i D a+i
5.若只需要利用形参间接访问实参指针所指向的对象，而形参本身具有相应的存储空间，则应把形参变量说明为（ ）参数。 A指针 B引用 C值 D指针引用
6.若只需要利用形参实现对实参值的拷贝，函数体操作形参时与实参无关，则应把形参变量说明为（ ）参数。
A指针 B引用 C值 D指针引用 7.下面程序的时间复杂性的量级为（）。 int i=0，s1=，s2=0； while（i++ else s2+=i; } A.O(1) B.O(1bn) C.O（n） D.O(2n) 8.下面程序段的时间复杂度为（ ）。 for(int i=0;i a[i][j]=i*j; A.O(m2) B.O(n2) C.O(m+n) D.O(m*n) 9.执行下面程序段时，S语句的执行次数为（）。 for(int i=1;i<=n;i++) for(int j=1,j<=i;j++) S; A.n(n-1)/2 B.n(n+1)/2 C.n2/2 D.n 10.在一个长度为n的顺序存储结构的线性表中，向第i个元素（1≤i≤n+1）位置插入一个元素时，需要从后向前依次后移（）个元素。 A.n-i B.n-i+l C.n-i-l D.i 11. 在一个长度为n的顺序存储结构的线性表中，删除第i个元素（1≤i≤n+1）时，需要从前向后依次后移（）个元素。 A.n-i B.n-i+l C.n-i-l D.i 12.在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（）。 A.(n+1)/2 B.n/2 C.n D.n+1 13.在一个顺序表的表尾插入一个元素的时间复杂度为（）。 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.1 B.2 C.3 D.4 19.在一个带头结点的循环双向链表中，若要在P所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。 A.2 B.3 C.4 D.6 20.在一个表头指针为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->prior B. p->next C. p->next->next D.p->prior->prior 24.在一个带头结点的循环双向链表中，若要在指针p所指向的结点之前插入一个q指针所指向的结点，则需要对p->prior->next赋值为（）。 A. q B. p C. p->next D. p->prior 25. 在一个带头结点的循环双向链表中，若要删除指针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=0 D.top=N-1 28.假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，用top=N+1表示栈空，该数组所存储的栈的最大长度为N，则表示栈满的条件为（）。 A.top==1 B.top==-1 C.top=0 D.top=N-1 29. 假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，用top==-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作为（）。 A.a[--top]=x B.a[top--]=x C.a[++top]=x D.a[top++]=x 30. 假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，用top==-1表示栈空，并已知栈未空，当退栈并返回栈顶元素时所执行的操作为（）。 A return a[--top] B return a[top--] C return a[++top] D return a[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，4 B.2，1，4，3 C.4，3，2，1 D.1，4，2，3. 35.在一个顺序循环队列中，队首指针指向队首元素的（）位置。 A前一个 B后一个 C当前 D最后 36.当利用大小为N的数组循环存储一个队列时，该队列的最大长度为（）。 A.N-2 B.N-1 C.N D.N+1 37.从一个顺序循环队列中删除元素时，首先需要（）。 A.前移队首指针 B.后移队首指针 C.取出队首指针所指位置上的元素 D.取出队尾指针所指位置上的元素 38.假定一个顺序循环队列的队首和队尾指针分别用f和r表示，则判断队空的条件为（）。 A.f+1==r B.r+1==f C.f==0 D.f==r 39.假定一个顺序循环队列存储于数组a[N]，其队首和队尾指针分别用f和r表示，则判断队满的条件为（）。 A.（r-1）%N==f B.（r+1）%N==f C.（f-1）%N==r D.（f+1）%N==r 40.假定利用数组a[N]循环顺序存储一个队列，其队首和队尾指针分别用f和r表示，并已知队列未满，当元素x入列时所执行的操作为（）。 A.a[++r%N]=x B.a[r++%N]=x C.a[--r%N]=x D.a[r--%N]=x 41.假定利用数组a[N]循环顺序存储一个队列，其队首和队尾指针分别用f和r表示，并已知队列未空，当出列并返回队首元素时所执行的操作为（）。 A.return a[++r%N] B.return a[--r%N] C.return a[++f%N] D.return a[f++%N] 42.假定一个链式队列的队首和队尾指针分别为front和rear，则判断队空的条件为（）。 A.front==rear B.front！=NULL C.rear！=NULL D.front==NULL 43.假定一个链式队列的队首和队尾指针分别为front和rear，每个结点结构为,当出列时所进 行的操作为（）。 A.front=front->next B.rear=rear->next C.front->next =rear；rear=rear->next D.front=front->next；front->next =rear； 44.假定一个带头结点的循环链式队列的队首和队尾指针分别用front和rear表示，则判断对空的条件为（）。 A.front=rear->next B.rear==NULL C. front==NULL D. front ==rear 45.假定一个链式队列的队首和队尾指针分别为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）%N B.（rear-front+N）%N C.（rear+N）%N D.（front+N）%N 47.二维数组A[12,10]采用行优先存储，每个数据元素占用4个存储单元，该数组的首地址（即A[0，0]的地址）为1200，则A[6，5]的地址为（）。 A.1400 B.1404 C.1372 D.1460 48.有一个M×N的矩阵A，若采用行优先进行顺序存储，每个元素占用8个字节，则Aij(1≤i≤M,1≤j≤N)元素的相对字节地址（相对首元素地址而言）为（）。 A.（（i-1）×N+j）×8 B.（（i-1）×N+j-1）×8 C.（i×N+j-1）×8 D.（（i-1）×N+j+1）×8 49.有一个N×N的下三角矩阵A，若采用行优先进行顺序存储，每个元素占用k个字节，则Aij(1≤i≤N,1≤j≤i)元素的相对字节地址（相对首元素地址而言）为（）。 A.（i×（i+1）/2+j-1）×4 B.（i×i/2+j）×4 C.（i×（i-1）/2+j-1）×4 D.（i×（i-1）/2+j）×4 50.树中所有结点的度等于所有结点数加（）。 A.0 B.1 C.-1 D.2 51.在一棵树中，（）没有前驱结点。 A.树枝结点 B.叶子结点 C.树根结点 D.空结点 52.在一棵树中，每个结点最多有（）个前驱结点。 A.0 B.1 C.2 D.任意多个 53.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。 A.2 B.1 C.0 D.-1 54.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）。 A.n B.n-1 C.n+1 D.2n 55.在一棵具有n个结点的二叉树的第i层上，最多具有（）个结点。 A.2i B.2i+1 C.2i-1 D.2n 56.在一棵深度为h的完全二叉树中，所含结点个数不小于（）。 A.2h B.2h+1 C.2h-1 D.2h-1 57.在一棵深度为h的完全二叉树中，所含结点个数不大于（）。 A.2h B.2h+1 C.2h-1 D.2h-1