第3章 数据类型——指针习题(有答案)
- 格式:doc
- 大小:48.50 KB
- 文档页数:4
第3章栈和队列一、选择题1.栈结构通常采用的两种存储结构是(A )。
A、顺序存储结构和链表存储结构B、散列和索引方式C、链表存储结构和数组D、线性链表结构和非线性存储结构2.设栈ST 用顺序存储结构表示,则栈ST 为空的条件是( B )A、ST.top-ST.base<>0B、ST.top-ST.base==0C、ST.top-ST.base<>nD、ST.top-ST.base==n3.向一个栈顶指针为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;4.从一个栈顶指针为HS 的链栈中删除一个结点,用x 保存被删除结点的值,则执行( C)A 、x=HS;HS=HS->next;B 、HS=HS->next;x=HS->data;C 、x=HS->data;HS=HS->next;D 、s->next=Hs;Hs=HS->next;5.表达式a*(b+c)-d 的后缀表达式为( B )A、abcdd+-B、abc+*d-C、abc*+d-D、-+*abcd6.中缀表达式A-(B+C/D)*E 的后缀形式是( D )A、AB-C+D/E*B、ABC+D/E*C、ABCD/E*+-D、ABCD/+E*-7.一个队列的入列序列是1,2,3,4,则队列的输出序列是( B )A、4,3,2,1B、1,2,3,4C、1,4,3,2D、3,2,4,18.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值,已知其头尾指针分别是front 和rear,则判定此循环队列为空的条件是()A、Q.rear-Q.front==nB、Q.rear-Q.front-1==nC、Q.front==Q.rearD、Q.front==Q.rear+19.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值,已知其头尾指针分别是front 和rear,则判定此循环队列为满的条件是()A、Q.front==Q.rearB、Q.front!=Q.rearC、Q.front==(Q.rear+1)%nD、Q.front!=(Q.rear+1)%n10.若在一个大小为6 的数组上实现循环队列,且当前rear 和front 的值分别为0 和3,当从队列中删除一个元素,再加入两个元素后,rear 和front 的值分别为()A、1,5B、2, 4C、4,2D、5,111.用单链表表示的链式队列的队头在链表的()位置A、链头B、链尾C、链中12.判定一个链队列Q(最多元素为n 个)为空的条件是()A、Q.front==Q.rearB、Q.front!=Q.rearC、Q.front==(Q.rear+1)%nD、Q.front!=(Q.rear+1)%n13.在链队列Q 中,插入s 所指结点需顺序执行的指令是()A 、Q.front->next=s;f=s;B 、Q.rear->next=s;Q.rear=s;C 、s->next=Q.rear;Q.rear=s;D 、s->next=Q.front;Q.front=s;14.在一个链队列Q 中,删除一个结点需要执行的指令是()A、Q.rear=Q.front->next;B、Q.rear->next=Q.rear->next->next;C、Q.front->next=Q.front->next->next;D、Q.front=Q.rear->next;15.用不带头结点的单链表存储队列,其队头指针指向队头结点,队尾指针指向队尾结点,则在进行出队操作时()A、仅修改队头指针B、仅修改队尾指针C、队头尾指针都要修改D、队头尾指针都可能要修改。
数据结构习题及解答第1章概述【例1-1】分析以下程序段的时间复杂度。
for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;解:该程序段的时间复杂度为O(m*n)。
【例1-2】分析以下程序段的时间复杂度。
i=s=0; ①while(s<n){ i++; ②s+=i; ③}解:语句①为赋值语句,其执行次数为1次,所以其时间复杂度为O(1)。
语句②和语句③构成while循环语句的循环体,它们的执行次数由循环控制条件中s与n的值确定。
假定循环重复执行x次后结束,则语句②和语句③各重复执行了x次。
其时间复杂度按线性累加规则为O(x)。
此时s与n满足关系式:s≥n,而s=1+2+3+…+x。
所以有:1+2+3+…+x ≥n,可以推出:x=x与n之间满足x=f(),所以循环体的时间复杂度为O(),语句①与循环体由线性累加规则得到该程序段的时间复杂度为O()。
【例1-3】分析以下程序段的时间复杂度。
i=1; ①while(i<=n)i=2*i; ②解:其中语句①的执行次数是1,设语句②的执行次数为f(n),则有:。
得:T(n)=O()【例1-4】有如下递归函数fact(n),分析其时间复杂度。
fact(int n){ if(n<=1)return(1); ①elsereturn(n*fact(n-1)); ②}解:设fact(n)的运行时间函数是T(n)。
该函数中语句①的运行时间是O(1),语句②的运行时间是T(n-1)+ O(1),其中O(1)为常量运行时间。
由此可得fact(n)的时间复杂度为 O(n)。
习题1一、单项选择题1. 数据结构是指(1. A )。
A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义2. 数据在计算机存储器内表示时,物理地址与逻辑地址不相同的,称之为(2. C )。
A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构3. 树形结构是数据元素之间存在一种(3. D )。
第3章栈和队列习题1.选择题(1)若让元素1,2,3,4,5依次进栈,则出栈次序不可能出现在()种情况。
A.5,4,3,2,1 B.2,1,5,4,3 C.4,3,1,2,5 D.2,3,5,4,1(2)若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi为()。
A.i B.n-i C.n-i+1 D.不确定(3)数组Q[n]用来表示一个循环队列,f为当前队列头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数小于n,计算队列中元素个数的公式为()。
A.r-f B.(n+f-r)%n C.n+r-f D.(n+r-f)%n (4)链式栈结点为:(data,link),top指向栈顶.若想摘除栈顶结点,并将删除结点的值保存到x中,则应执行操作()。
A.x=top->data;top=top->link; B.top=top->link;x=top->link;C.x=top;top=top->link; D.x=top->link;(5)设有一个递归算法如下int fact(int n) { //n大于等于0if(n<=0) return 1;else return n*fact(n-1); }则计算fact(n)需要调用该函数的次数为()。
A. n+1 B. n-1 C. n D. n+2 (6)栈在()中有所应用。
A.递归调用 B.函数调用 C.表达式求值 D.前三个选项都有(7)为解决计算机主机与打印机间速度不匹配问题,通常设一个打印数据缓冲区。
主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。
该缓冲区的逻辑结构应该是()。
A.队列 B.栈 C.线性表 D.有序表(8)设栈S和队列Q的初始状态为空,元素e1、e2、e3、e4、e5和e6依次进入栈S,一个元素出栈后即进入Q,若6个元素出队的序列是e2、e4、e3、e6、e5和e1,则栈S的容量至少应该是()。