数据结构与算法-考研试题(清华大学 1998年链式队列)

单项选择（1998年清华大学）

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

A、链头

B、链尾

C、链中

答案解析

A

【解析】

队列的队头是队列元素进行删除的一端。

队列的队头在链表的链头位置。

讨论

数据结构与算法

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

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

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

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

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

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

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

栈的输入序列为1,2,3,...,n，输出序列为a1,a2,a3,...,an，若ai=n(1≤i≤n)，则有 ak>ak+1>an。

设栈的输入序列为1,2,3,...,n，输出序列为a1,a2,a3,...,an，若存在1≤k≤n使得 ak=n，则当k≤i≤n时，ai 为【】

没有提供指针类型的语言，无法构造链式结构，该说法【】

队列

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

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

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

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

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

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

顺序队列一般应该组织成为环状队列的形式，而且一般队列头或尾其中之一应该特殊处理。例如，队列为 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*/

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

链式队列

线性表是具有n个【】的有限序列。

如果待排序序列中两个数据元素具有相同的值，在排序前后它们的位置发生颠倒，则称该排序算法是不稳定的，【】就是不稳定的排序算法。

快速排序的最大递归深度是__________，最小递归深度是__________。

如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序序列，用【】方法最快

回答问题并写出推导过程：对50个整数进行快速排序需进行关键字间比较次数可能达到的最大值和最小值各为多少？

写出和下列递归过程等价的非递归过程。void test(int sum){ int a; scanf("%d",&a); if(a==0) sum=1; else{ test(sum); sum=sum*a; } pritf("%d",sum); }

对于一个有向图，不用拓扑排序，如何判断图中是否存在环？

表示一个有 1000 个顶点、1000 条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？

有 n 个顶点的有向强连通图最多有多少条边？最少有多少条边？

设无向图的顶点个数为n，则该无向图最多有【】条边。