第3章自测卷空题--数据结构课件(吴伟民-严蔚敏编著).doc

第3章栈和队列自测卷姓名班级题号一二三四五六总分题分 15 10 20 20 20 15 100 得分一、填空题(每空 1分,共 15分) 1. 向量、栈和队列都是结构,可以在向量的位置插入和删除元素;对于栈只能在插入和删除元素;对于队列只能在插入和删除元素。 2. 栈是一种特殊的线性表, 允许插入和删除运算的一端称为。不允许插入和删除运算的一端称为。 3. 是被限定为只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表。 4. 在一个循环队列中,队首指针指向队首元素的位置。 5. 在具有 n 个单元的循环队列中,队满时共有个元素。 6. 向栈中压入元素的操作是先,后。 7. 从循环队列中删除一个元素时,其操作是先,后。 8. 带表头结点的空循环双向链表的长度等于。二、判断正误(判断下列概念的正确性,并作出简要的说明。)(每小题 1分,共 10分) ()1. 线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。()2. 在表结构中最常用的是线性表,栈和队列不太常用。() 3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是一种后进先出型结构。()4. 对于不同的使用者,一个表结构既可以是栈,也可以是队列,也可以是线性表。() 5. 栈和链表是两种不同的数据结构。()6. 栈和队列是一种非线性数据结构。() 7. 栈和队列的存储方式既可是顺序方式,也可是链接方式。() 8. 两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机会,应把两个栈的栈底分别设在这片内存空间的两端。() 9. 队是一种插入与删除操作分别在表的两端进行的线性表,是一种先进后出型结构。() 10. 一个栈的输入序列是 12345 ,则栈的输出序列不可能是 12345 。三、单项选择题(每小题 1分,共 20分) ()1. 栈中元素的进出原则是 ()2. 若已知一个栈的入栈序列是 1,2,3,…,n, 其输出序列为 p1, p2, p3,…, pn ,若 p1=n , 则 pi为 A. i B. n=i C. n-i+1 ()3. 判定一个栈 ST (最多元素为 m0 )为空的条件是 A. ST->top<>0 B. ST->top=0 C. ST->top<>m0 D. ST->top=m0 () 4. 判定一个队列 QU (最多元素为 m0 )为满队列的条件是 A. QU->rear - QU->front == m0 B. QU->rear - QU->front -1== m0 C. QU->front == QU->rear D. QU->front == QU->rear+1 ()5 .数组Q[n]用来表示一个循环队列,f为当前队列头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数小于n,计算队列中元素的公式为(A) r- f; (B )(n+f-r)% n; (C) n+r- f; (D )(n+r-f)%n 6. 设有 4 个数据元素 a1、 a2、 a3和 a4, 对他们分别进行栈操作或队操作。在进栈或进队操作时,按 a1、 a2、 a3、 a4 次序每次进入一个元素。假设栈或队的初始状态都是空。现要进行的栈操作是进栈两次, 出栈一次, 再进栈两次,