数据结构单元练习参考答案

1、单元测验4一判断题<下列各题，正确的请在前面的括号内打；错误的打）<）<1）队列是限制在两端进行操作的线性表。<）<2）判断顺序队列为空的标准是头指针和尾指针都指向同一个结点。<×）<3）在链队列上做出队操作时，会改变front指针的值。<）<4）在循环队列中，若尾指针rear大于头指针front，其元素个数为rear- front。<×）<5）在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是p=h。<）<6）链队列在一定范围内不会出现队满的情况。<×）<7）在

2、循环链队列中无溢出现象。<×）<8）栈和队列都是顺序存储的线性结构。<×）<9）在队列中允许删除的一端称为队尾。<×）<10）顺序队和循环队关于队满和队空的判断条件是一样的。二填空题（1） 在队列中存取数据应遵循的原则是先进先出。（2） 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。（3） 在队列中，允许插入的一端称为队尾。（4） 在队列中，允许删除的一端称为队首<或队头）。（5） 队列在进行出队操作时，首先要判断队列是否为 空。（6） 顺序队列在进行入队操作时，首先要判断队列是否为 满。（

3、7） 顺序队列初始化后，front=rear= -1 。（8） 解决顺序队列“假溢出”的方法是采用循环队列。（9） 循环队列的队首指针为front，队尾指针为rear，则队空的条件为 front = rear 。b5E2RGbCAP（10） 链队列LQ为空时，LQ->front->next= NULL 。（11） 设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为 O<n）。（12） 设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复杂度为 0<1）。（13） 在一个链队列中，若队首指针与队尾指针的值相同，则表示该队列为空。（1

4、4） 设循环队列的头指针front指向队首元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，则队满标志为：front=(rear+1>%MAXLEN 。p1EanqFDPw（15） 在一个链队列中，若队首指针为front，队尾指针为rear，则判断该队列只有一个结点的条件为： front=rear && front !NULL 。DXDiTa9E3d(或 front=rear && front <>NULL >（16） 向一个循环队列中插入元素时，首先要判断队尾指针，然后再向指针所指的位置写入新的数据。（17

5、） 读队首元素的操作 不改变<或不影响） 队列元素的个数。 <18） 设循环队列的容量为40<序号从0到39），现经过一系列的入队和出队运算后，有 front=11，rear=19，则循环队列中还有 8 个元素。RTCrpUDGiT<L= (Nrearfront>% N=<401911）% 40=8）<19）队列Q，经过下列运算：InitQueue(Q>(初始化队列>。InQueue(Q,a>。 InQueue(Q,b>。OutQueue(Q,x>。 ReadFront(Q,x>。QEmpty(Q>。后的值是0

6、 。5PCzVD7HxA<20）队列Q经过InitQueue(Q>(初始化队列>。InQueue(Q,a>。InQueue(Q,b>。 ReadFront(Q,x>后，x的值是 a 。jLBHrnAILg三选择题<1）队列是限定在<D）进行操作的线性表。 A中间 B队首 C队尾 D端点<2）队列中的元素个数是( B >。A不变的 B可变的 C任意的 D0<3）同一队列内各元素的类型( A >。A必须一致 B不能一致 C可以不一致 D不限制<4）队列是一个( C >线性表结构。A不加限制的B推广了的 C加了限制的

7、 D非<5）当利用大小为n的数组顺序存储一个队列时，该队列的最后一个元素的下标为< B ）。 An-2 Bn-1CnDn+1<6）一个循环队列一旦说明，其占用空间的大小<A）。 A已固定B可以变动 C不能固定D动态变化<7）循环队列占用的空间( A >。A必须连续 B不必连续 C不能连续D可以不连续<8）存放循环队列元素的数组data有10个元素，则data数组的下标范围是( B >。A0.10 B0.9 C1.9D1.10<9）若进队的序列为：A，B，C，D，则出队的序列是< C ）。 AB，C，D，A BA，C，B，DCA，B，C

8、，D DC，B，D，A<10）四个元素按：A，B，C，D顺序连续进队Q，则队尾元素是< D ）。 A AB BC CD D<11）四个元素按：A，B，C，D顺序连续进队Q，执行一次OutQueue(Q>操作后，队头元素是< B ）。xHAQX74J0X A AB BC C D D<12）四个元素按：A，B，C，D顺序连续进队Q，执行四次OutQueue(Q>操作后，再执行QEmpty(Q>。后的值是< B ）。LDAYtRyKfE A 0B 1 C 2 D 3<13）队列Q，经过下列运算后，x 的值是<B）。InitQueue(

9、Q>(初始化队列>。InQueue(Q,a>。 InQueue(Q,b>。OutQueue(Q,x>。Zzz6ZB2LtkReadFront (Q,x>。AaBbC0D1<14）循环队列SQ队满的条件是( B >。ASQ->rear=SQ->front B(SQ->rear+1>% MAXLEN =SQ->frontdvzfvkwMI1CSQ->rear=0 DSQ->front=0<15）设链栈中结点的结构：data为数据域，next为指针域，且top是栈顶指针。若想在链栈的栈顶插入一个由指针s所

10、指的结点，则应执行下列< A ）操作。rqyn14ZNXI As->next=top->next；top->next=s； Btop->next=s；Cs->next=top；top=top->next； Ds->next=top；top=s；EmxvxOtOco<16）带头结点的链队列LQ示意图如下，链队列的队头元素是< A ）LQ->frontHABCDLQ->rearAA BB CCDD<17）带头结点的链队列LQ示意图如下，指向链队列的队头指针是< C ）LQ->frontHABCDLQ->

11、rearALQ->front BLQ->rearCLQ->front->next DLQ->rear->next<18）带头结点的链队列LQ示意图如下，在进行进队运算时指针LQ->front< A ） LQ->frontHABCDLQ->rearA始终不改变B有时改变C进队时改变 D出队时改变<19）队列Q，经过下列运算后，再执行QEmpty(Q> 的值是<C）。InitQueue(Q> (初始化队列>。InQueue(Q,a>。 InQueue(Q,b>。OutQueue(Q,x>

12、;。SixE2yXPq5ReadQueue(Q,x>。AaBbC0 D1<20）若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为( B >。6ewMyirQFLA5和1B4和2 C2和4 D1和5四 写出程序运行的结果写出下列程序段的输出结果<队列中的元素类型为char）。void main( >Queue Q。 InitQueue (Q>。/ 初始化队列char x="E"。 y="C"。InQueue (Q,

13、"H">。InQueue (Q, "R">。InQueue (Q, y>。OutQueue (Q,x>。 InQueue (Q,x>。 OutQueue (Q,x>。 InQueue (Q, "A">。 while(!QEmpty(Q>>OutQueue (Q,y>。printf(y>。 。printf(x>。答：输出为“CHAR”。五程序填空1假定用一个循环单链表表示一个循环队列，该队列只设一个队尾指针rear，试填空完成向循环队列中插入一个元素为x的结点的函数

14、。kavU42VRUstypedef struct queuenode / 定义队列的存储结构int data。struct queuenode *next。qu。InQueue(rear,x> / 向队列插入元素为x的函数qu *rear；int x； qu *head,*s。 s= new qu 。 s->data= x 。 if (rear=NULL> / 循环队列为空，则建立一个结点的循环队列y6v3ALoS89 rear=s。 rear->next。 else head= rear->next 。 / 循环队列非空，则将s插到后面rear->nex

15、t= s 。rear=s。rear->next =head。六. 算法设计题1设一个循环队列Queue，只有头指针front，不设尾指针，另设一个含有元素个数的记数器cont，试写出相应的入队算法和出队算法。M2ub6vSTnP2用一个循环数组Q0.MAXLEN-1表示队列时，该队列只有一个头指针front，不设尾指针，而改置一个记数器count用以记录队列中结点的个数。试编写一个能实现：初始化队列、判队空、读队头元素、入队操作和出队操作的算法。0YujCfmUCw3一个用单链表组成的循环队列，只设一个尾指针rear，不设头指针，请编写他如下算法：（1） 向循环队列中插入一个元素为x的结

16、点；（2） 从循环队列中删除一个结点。1 解：用一个循环数组Queue0，n-1表示该循环队列，头指针为front，计数器count用来记录队列中结点的个数。eUts8ZQVRd<1）入队算法： void inqueqe(int x> int temp。if (count=n> printf("队列上溢出n">。else count+ temp=(front+count>%n。 Queuetemp=x <2）出队算法： int outqueue(> int temp。if (count=0> printf("队列下溢

17、出n">。else temp=Queuefront。 front=(front+1>%n。 count-。 return temp。 2解：队列为空：count=0队列为满：count=MAXLEN队尾第一个元素位置=(front+count>%MAXLEN队首第一个元素位置=(front+1>%MAXLENconst MAXLEN=100。int queueMAXLEN。int front,count。 / 定义队头和计数器count<1）初始化队列void init(> front=1。 count=0。<2）判定队空int QEmpty

18、(> if (count=0>return(1>。 else return(0>。 <3）读队头元素void ReadFront(int queue,x> if (count=0> printf("下溢出n">。 else front=(front+1>%MAXLEN。x=queuefront。 <4）入队操作 void InQueue(int queue,int x> int place。 if (count=MAXLEN>printf("上溢出n">。 else count+。place=(front+count>%MAXLEN。queueMAXLEN=x。 <5）出队操作 void OutQueue(int queue> / 删除队列头元素 if (count=0> printf("队列下溢出n">。 else front=(front+1&