数据结构与算法-考研试题(复旦大学 1998年顺序队列)

单项选择（1998年复旦大学）

若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后， rear和加front的值分别为多少？

A、1和5

B、2和4

C、4和2

D、5和1

答案解析

B初始化创建空队列时，令front=rear=0，每当插入新的队列尾元素时，rear增1，每当删除一个队列首元素时，front增1。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾...

查看完整答案

讨论

数据结构与算法

在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应念是一个【】结构。

若用单链表来表示队列则应该选用【】

用单链表表示的链式队列的队头在链表的【】位置。

对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为__________。

在深度为7的满二叉树中，叶子结点的个数为【】

下列描述中，正确的是【】

按照“后进先出”原则组织数据的数据结构是【】

某二叉树中度为2的结点有18个，则该二叉树中有__________个叶子结点。

有n个数顺序（依次）进栈，则出栈顺序有Cn种。Cn=×

设栈的输入序列是（1，2，3，4），则【】不可能是其出栈序列。

队列

设一单项链表的头指针为head，链表的记录中包含整数类型的key域，试设计算法，将此链表的记录按照key递增的顺序进行就地排序。

用数组表示的循环队列的队首和队尾位置分别为1和 max_size，试给出判断队列为空和为满的边界条件。

用数组 Q（其下标在 0 . . n-1 中，共有n个元素）表示一个环形队列， f 为当前队头元素的前一位置， r 为队尾元素的位置。假定队列中元素个数总小于 n ,求队列中元素个数的公式是__________。

顺序队列一般应该组织成为环状队列的形式，而且一般队列头或尾其中之一应该特殊处理。例如，队列为 listarray [ 0 ... n-1] ，队列头指针为front ，队列尾指针为 rear ，则 listarray[rear]表示下一个可以插入队列的位置。请解释其原因。

队列采用如下图所示的循环单链表表示，左图表示队列为空，右图为e1、e2、e3依次入队列后的状态，其中，rear指针指向队尾元素所在结点，size为队列长度。以下叙述中，正确的是【】。

阅读以下说明和C函数，填补函数代码中的空缺(1)~(5)。队列是一种常用的数据结构，其特点是先入先出，即元素的插入在表头、删除在表尾进行。下面采用顺序存储方式实现队列，即利用一组地址连续的存储单元存放队列元素，同时通过模运算将存储空间看作一个环状结构(称为循环队列)。设循环队列的存储空间容量为 MAXQSIZE，并在其类型定义中设置base、rear和 length三个域变量，其中，base为队列空间的首地址，rear为队尾元素的指针， length表示队列的长度。#define MAXQSIZE 100typedef struct{ QElemType *base;/*循环队列的存储空间首地址* int real;/*队尾元素索引*/ int ength;/*队列的长度*/} SqQueue;例如，容量为8的循环队列如下图所示，初始时创建的空队列如图(a)所示，经过一系列的入队、出队操作后，队列的状态如图(b)所示(队列长度为3)。下面的C函数1、C函数2和C函数3用于实现队列的创建、插入和删除操作，请完善这些代码。【C函数1】创建一个空的循环队列int InitQueue (SqQueue *Q){ /*创建容量为 MAXQSIZE的空队列，若成功则返回1;否则返回0*/ Q->base =(QElemType *)malloc( MAXQSIZE*__ (1)__); if (! Q->base) return 0： Q->length=0; Q->rear =0; return 1;}/* InitQueue*/【C函数2】元素插入循环队列。int EnQueue( SqQueue *Q， QElemType e){/*元素e入队，若成功则返回1;否则返回0*/ if( Q->length>=MAXQSIZE) return 0; Q->rear=__(2)__; Q->base [Q->rear]=e; __(3)__; return 1;}/*EnQueue*/【C函数3】元素出循环队列。int DeQueue (SqQueue *Q，QElemType *e){ /*若队列不空，则删除队头元素，由参数e带回其值并返回1;否则返回0*/ if(__(4)__)return 0; *e=Q-base[(Q->rear-Q->length+1+MAXQSIZE)%MAXQSIZE]; __(5)__; return 1;}/*DeQueue*/

在解决计算机与打印机之间速度不匹配的问题时，通常设置一个打印数据缓冲区，计算机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区取出数据。因此，该缓冲区的数据结构应该是【】。

堆排序是不是一种稳定的排序方法？为什么？

如果G是一个具有n个顶点的连通无向图，那么G最多有__________条边，最少有__________条边。

对于一个具有n个结点的连通无向图，如果它有且只有一个简单回路，那么此图有__________条边。

顺序队列

一个具有n个结点的弱连通图至少有__________条边。

如果一棵huffman树T有n0个叶子结点，那么，树T有多少个结点？要求给出求解过程。

对于二叉树T 的两个结点 n1 和 n2 ，我们应该选择树 T 结点的前序、中序和后序中哪两个序列来判断结点 n1 必定是结点 n2的祖先，并给出判断的方法。不需证明判断方法的正确性。

若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后， rear和加front的值分别为多少？

若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后， rear和加front的值分别为多少？

若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后， rear和加front的值分别为多少？

若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后， rear和加front的值分别为多少？

若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后， rear和加front的值分别为多少？

若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后， rear和加front的值分别为多少？

若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后， rear和加front的值分别为多少？