数据结构栈和队列测验
《数据结构》栈和队列测试题
一、填空题（12*1=12分）
1. 栈是操作受限的线性表，
2. 栈的工作原理：队列的工作原理：
3. 队列是操作受限的线性表：可以在
4. 能够从任意一个结点出发直接访问到所有结点的是：;
5. 设有栈S 和队列Q ，初始状态均为空。首先依次将A,B,C,D,E,F 入栈，然后从栈中退出三个元素依次入队，再将X,Y,Z 入栈后，将栈中所有元素退出并依次入队，最后将队列中所有元素退出，则退队元素的顺序为： ;
6. 循环队列判断队空的条件：
7. 顺序队列判断队空的条件：顺序队列判断队满的条件：二. 选择题（2*5=10分）
1. 下列数据结构中，属于非线性结构的是( )
A. 双向链表 B. 循环链表 C. 二叉链表 D. 循环队列
2. 下列与栈结构有关联的是( )
A. 数组的定义与使用 B. 操作系统的进程调度 C. 函数的递归调用 D. 选择结构的执行
3. 下列关于算法复杂度叙述正确的是( )
A. 最坏情况下的时间复杂度一定高于平均情况的时间复杂度
B. 时间复杂度与所用的计算工具无关 C. 时间复杂度与采用的算法描述语言有关
D. 对同一问题，采用不同的算法，则它们的时间复杂度是相同的
4. 下列叙述正确的是( )
A. 有两个指针域的链表称为二叉链表； B. 循环链表是循环队列的链式存储结构；
C. 带链的栈有栈顶指针和栈底指针，因此又称为双重链表
D. 节点中具有多个指针域的链表称为多重链表
5. 下列叙述中正确的是( )
A. 节点中具有两个指针域的链表一定是二叉链表
B. 节点中具有两个指针域的链表可以是线性结构，也可以是非线性结构
C. 二叉树只能采用链式存储结构 D. 循环链表是非线性结构
三、程序填空：（10*2=20分）
1. 已知顺序栈定义如下，请将元素d 入栈的代码补充完整
/*定义栈的数据类型*/
typedef struct{
int *base;//栈底指针 int *top;//栈顶指针 int stack_size;//栈的大小
}SqStack;
/*功能：将元素d 入栈返回值：1:成功 0：失败*/
,int d){
} //判断栈是否已满，如果满，入栈失败 >=s->stack_size) { } //把d 放入top 指针所指的位置 //top指针上移（++） return ; printf("栈已满，入栈失败！\n"); return 0;
2. 已知顺序队列定义如下，请将下列代码补充完整：
typedef struct{
int queue[MAX_QUEUE_SIZE];
int front;//队头
int rear;//队尾
}SqQueue;
/*功能：出队（把队首元素删除）参数：sq 指向一个顺序队列，d ：保存删除元素 返回值：1：成功 0：失败*/
int deQueue(SqQueue *sq,int *d){
//如果sq 为NULL ，输出“队列未创建，出队失败！”, 返回0
}
} //如果队列为空(没有元素) ，输出“队列为空，出队失败！”, 返回0 printf("队列为空，出队失败！\n"); return 0; } ; //否则，把front 所指的元素放到d 里 //返回1 return 1; { printf("队列未创建，出队失败!\n");
参考答案：
一. 填空题
1. 栈底 栈顶
2. 先进后出FILO (后进先出 ) 先进先出（FIFO ）
3. 队尾 队首（队头）
4. 循环链表
5.FEDZYXCBA
6. 队首指针==队尾指针（rear==front） (rear+1)%MAX_QUEUE_SIZE==front
7. 队首指针==队尾指针（rear==front） rear>MAX_QUEUE_SIZE-1
二. 选择题
CCBBB
三. 填空题
1. SqStack *s
2.sq==NULL s->top return 0; s->top (s->top)++ 1 == sq->queue[sq->front] sq->front+1