发布时间 : 星期一 文章1数据结构习题及参考答案更新完毕开始阅读b9320a082cc58bd63086bd2d
数据结构习题
习题2
2.1选择题
（1）线性表是具有n个 __________的有限序列（n!=0）。 A.表元素 B.字符 C.数据元素 D.数据项
（2）顺序表的存储结构是一种__________的存储结构。 A.随机存取 B.顺序存取 C.索引存取 D.HASH存取
（3）在一个长度为n的顺序表中，向第i个元素（1<=i<=n+1）之前插入一个新元素时，需要向后移动____________个元素。
A.n-i B.n-i+1 C.n-i-1 D.i
(4)链表是一种采用____________存储结构存储的线性表。 A.顺序 B链式 C.星式 D.网状
（5）下面关于线性表的叙述错误的是_____________。 A.线性表采用顺序存储方式，必须占用一片连续的存储空间 B.线性表采用链式存储方式，不必占用一片连续的存储空间 C.线性表采用链式存储方式，便于插入和删除操作的实现 D.线性表采用顺序存储方式，便于插入和删除操作的实现
（6）设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用____________存储方式最节省运算时间。
A.单项链表 B.单向循环链表 C.双向链表 D.双向循环链表
(7)设指针q指向单链表中的结点A，指针p指向单链表中的结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B之间插入结点X的操作序列为____________。 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;
(8)设指针变量p指向单链表结点A，则删除结点A的后继结点B的操作为___________。 A.p->next=p->next->next B.P=P->next C.p=p->next->next D.P->next=p
(9)在一个以h为头的单循环链表中，p指针指向链尾的条件是__________. A.P->next=h B.p->next=NULL C.p->next->next=h D.p->data=-1
(10)对于只在首尾两端进行插入操作的线性表，宜采用的存储结构为___________。 A.顺序表 B.用头指针表示的单循环链表 C.单链表 D.用尾指针表示的单循环链表 2.2填空题
（1）线性表是n个元素的_____________________________。 （2）线性表的存储结构有______________________________。
（3）设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________________，在链式存储结构上实现顺序查找的平均时间复杂度为___________________。
（4）设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中___________个数据元素；删除第i个位置上的数据元素需要移动表中___________个元素。 （5）若频繁地对线性表进行插入与删除操作，该线性表应采用_________________存储结构。 （6）链式存储结构中的结点包含________________域和_________________域。
（7）在双链表中，每个结点有两个指针域，一个指向____________，另一个指向_______________。
（8）对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为______________，在表尾插入时间的复杂度为_________________。
（9）设指针变量p指向单链表中的结点A，指针s指向被插入结点B，则在结点A的后面插入结点B的操作序列为_________________________________________________。
（10）设指针变量p指向单链表中的结点A，则删除结点A的后继结点（假设存在）的语句序列我为：
S=p->next; p->next=___________________；free(s)；
习题2参考答案 2.1选择题
(1). C. (2). B. (3). B. (4). B. 5. D. 6. B. 7. B. 8. A. 9. A. 10. D. 2.2.填空题 (1). 有限序列
(2). 顺序存储和链式存储 (3). Ｏ(n) O(n) (4). n-i+1 n-i (5). 链式
(6). 数据 指针 (7). 前驱 后继 (8). Ο(1) Ο(n)
(9). s->next=p->next; p->next=s ; (10). s->next
习题三 3.1选择题
1）下列说法正确的是（）
A.堆栈是在两端操作、先进后出的线性表 B.堆栈是在一端操作、先进先出的线性表 C.队列是在一端操作、先进先出的线性表 D.队列是在两端操作、先进先出的线性表 2）栈和队列的共同点是（） A.都是先进先出 B.都是先进先出
C.只允许在端点出插入和删除元素 D.没有共同点
3）以下数据结构中（）是非线性结构。 A.队列 B.栈
C.线性表 D.二叉树
4）若一个栈的入栈序列是1，2,3，，n。其输出序列为p1,p2,p3,?pn,,,p1=n,则pi为（） ?A. I B. N-i C. N-i+1 D. 不确定
5）当利用大小为N的一位素组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。 A.top++ B.Top-- C.Top=0 D.Top
6）4个元素s栈的顺序是A,B,C,D,经运算，pop(s)后栈顶元素是（） A. A B. B C. C D.D
7)一个栈的输入序列是a，b，c，d，e，则栈的不可能的输出序列是（） A. adcba B. decba C. dceab D. abcde 8)设输入序列是1,2,3，?n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（） A.n-i B.n-1-i C.n+1-i D.不能确定
9）字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（）个不同的字符串
A.15 B.14 C.16 D.21
10)递归函数f(n)=f(n-1)+n(n>1)的递归出口是（） A.f(1)=0 B.f(1)=1 C.f(0)=1 D.f(n)=n
11)设指针变量top指向当前链式栈的栈顶，则删除栈顶的元素的操作序列为（） A.top=top+1 B.top=top-1
C.top->next=top D.top = top->next 12)中缀表达式A-(B+C/D)*E的后缀表达式是（） A.ABC+D/*E- B.ABCD/+E*- C.AB-C+D/E* D.ABC-+D/E*
13)用front和rear分别表示顺序循环队列的队首和队尾指针，判断队空的条件是（） A.front+1==rear B.(rear+1)%maxsize == front C.front==0 D.front==rear
14)判定一个循环队列QU（最多元素为m0）为满队列的条件是（） A.QU->front==QU->rear B.QU->front!=QU->rear
C.QU->front==（QU->rear+1）%m0 D.QU->front!=（QU->rear+1）%m0
15）设栈s和队列Q的初始状态为空。元素E1，E2,E3,E4,E5和E6依次通过栈S，一个元素出栈后即进入队列Q。若6个元素出列的顺序为E2，E4，E3,E6，E5和E1。则栈S的容量至少应该是（）
A. 6 B.4 C. 3 D.2
16）用链接式存储的队列。在进行插入运算时，（） A.仅修改头指针
B.头、尾指针都要修改 C.仅修改尾指针
D.头、尾指针可能都要修改
17）若用一个大小为6的数组实现循环队列，且当前rear和front的值分别为0和3.当从队列中删除一个元素再加入两个元素后。Rear 和front 的值分别为（） A.1和5 B.2和4 C.4和2 D.5和1
18）设顺序循环队列Q[0;M-1]的头指针分别为F和R，头指针F总是指向头元素的前一位置。尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（） A.R-F B.F-R
C.(R-F+M)%M D.(F-R+M)%M
19)设指针变量front便是链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点x，则入队列的操作序列为（） A.front->next=s;front=s B.s-next=rear;rear=s C.rear=>next=s;rear=s D.s-next=front;rear=s
20)当利用大小为N的数组顺序存储的一个队列是，该队列的最大长度为（） A.n-2 B.n-1 C.n D.n+1 3.2填空题 1）栈的插入和删除只能在栈顶栈顶进行，后进栈的元素必定先出栈，所以又把栈称为_______表；队列的插入和删除操作分别在队列的两端进行。先进队列的元素必定先出队列，所以又把队列称为_____表。
2）后缀算式9 2 3+ - 10 2 / -的值为_____中缀算式（3+4X）- 2Y/3 对应的后缀算式为____________________
3）下面程序段的功能实现数据X进栈，要求在下划线处填上真确的语句。 Typedef struct {int s [100]； int top;} sqstack Void push(sqstack & stack , int x ) {
If(stack.top==m-1) printf(“overflow”); Else{__________,___________;} }
4)设指针变量P指向双向循环链表中的结点X。则删除结点X需要执行的语句序列为_________________,_____________________,(设结点中的两个指针域分别为llink 和 rlink ). 5)设有一个顺序循环队列中有M个存储单元。则该循环队列中最多能够存储M-1个队列元素；当前实际存储________个队列元素（设头指针F指向当前队头元素的前一个位置，尾