数据结构试题汇总

您所在位置：数据结构网络教学平台>>> 试卷汇粹>>数据结构试题汇总

一、选择题

第一二章

1．数据结构是一门研究计算机中____对象及其关系的学科。 （1）数值运算 （2）非数值运算 （3）集合 （4）非集合

2．数据结构的定义为(K，R)，其中K是____的集合。 （1）算法 （2）数据元素 （3）数据操作 （4）逻辑结构 3．算法分析的目的是____。 （1） 找出数据结构的合理性 （2） 研究算法中输入和输出的关系 （3） 分析算法的效率以求改进

（4） 分析算法的易懂性和文档性

4．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行___。 （1）s->link=p;p->next=s;

（2）s->link=p->link;p->link=s; （3）s->link=p->link;p=s;

（4）p->link=s;s->link=p;

5．在循环链表中first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是____。

（1）current->link=NULL (2)first->link=current

（3）first=current (4)current->link=first

6．从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较____个结点。 （1）n （2）n/2

（3）（n-1）/2 （4）(n+1)/2

7．在一个具有n个结点的有序单链表中，插入一个新结点并仍然有序的时间复杂度为____。 （1）O(1) （2）O(n)

（3）O(n2) （4）O(nlog2n)

8、（ ）是具有相同特性数据元素的集合，是数据的子集。 A 数据符号 B 数据对象 C 数据 D 数据结构

9 与数据元素本身的形式、内容、相对位置、个数无关的是数据的 ( )。 A. 存储结构 B. 逻辑结构 C. 算法 D. 操作 10 用链表表示线性表的优点是 ( )。

A. 便于随机存取 B. 花费的存储空间比顺序表少

C. 便于插入与删除 D. 数据元素的物理顺序与逻辑顺序相同 11、数据结构是研究数据的（ C ）及它们之间的相互联系。 A、理想结构，物理结构 b、理想结构，逻辑结构 C、物理结构，逻辑结构 d、抽象结构，逻辑结构

12、线性表是（ A ）。

a、一个有限系列，可以为空 b、一个有限系列，不能为空 c、一个无限系列，可以为空 d、一个无限系列，不能为空 13、组成数据的基本单位是 （ C ） 。

a、数据项 b、数据类型 c、数据元素 d、数据变量 14、线性表的链接实现有利于（ A ）运算。 A、插入 b、读表元 c、查找 d、定位 15 线性表采用链式存储时，其地址（ d ）

A 必须是连续的 B 部分地址是连续的 C 一定是不连续的 D 连续与否均可以

16、设单链表中指针p指着结点a，若要删除a之后的结点（若存在），则需要修改指针的操作为（ A ）。 A、p->next=p->next->next b、p=p->next C、 p= p->next->next d、p->next=p

17向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动（ ）个元素。 A、8 B、63.5 C、63 D、7

18．若将两个各有 n个元素的有序表归并成一个有序表，则最少比较次数是（ ）。 A n B 2*n-1 C 2n D n-1

第三章

1．输入序列为（A,B,C,D）不可能的输出有（ ）。

A (A,B,C,D) B (D,C,B,A) C (A,C,D,B) D (C,A,B,D) 2 链式栈与顺序栈相比，一个比较明显的优点是 ( )。

A. 插入操作更加方便 B. 通常不会出现栈满的情况 C. 不会出现栈空的情况 D. 删除操作更加方便 3 在一个顺序存储的循环队列中，队头指针指向队头元素的 ( )。 A. 前一个位置 B. 后一个位置

C. 队头元素位置 D. 队尾元素的前一位置

4、若一个栈的输入序列是1，2，3……n，则输出序列的第一个元素是n，则第i个输出元素是（ ）。

A n-i B i C n-i+1 D n-i-1

5．栈的数组表示中，top为栈顶指针，栈空的条件是____。 （1） top=0 （2）top=maxSize （2） top=maxSize（4）top=-1

6．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是____。 （1） front=maxSize （2）(rear+1)%maxSize=front （2） rear=maxSize （4）rear=front 7．栈和队列的共同特点是____。

（1） 都是先进后出 （2）都是先进先出

（2） 只允许在端点处插入和删除 （4）没有共同点

第四章

6．设有串t=’I am a good student ’，那么Substr(t,6,6)=（ ）。 A student B a good s C good D a good

第五章

1设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则 a85地址为（ b ）。

A 23 B 33 C 18 D 40

2已知广义表 LS=(A,(B,C,D),E)运用head和tail函数，取出LS中原子b的运算（ c ）。

A Gethead(Gethead(LS)) B Gettail(Gethead(LS)) C Gethead(Gethead(Gettail(LS))) D Gethead(Gettail(LS))

3．设有一个矩阵A8×6，采用压缩存储方式，以行序为主序存储，a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则 a56地址为（ ）。

A 23 B 30 C 31 D 45

4．一个数组第一个元素的存储地址是100，每个数组元素的长度为2，则第5个元素的地址是____。 （1）110 （2）108 （3）100 （4）120

5 若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个 ( )。 A. 上三角矩阵 B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵

6设有一个二维数A[m][n],假设A[0][0]存放位置在644(10),A[2][2]存放位置在676(10),每个元素占一个空间，则A[4][5]在（ ）位置，(10)表明用10进数表示。

A、692(10) B、626(10) C、709(10) D、724(10)

7、一个n*n对成矩阵，如果以行或列为主序存入内存，则其容量为（ ）。 A n*n B n*n/2 C n*（n+1）/2 D （n+1）*（n+1）/2 8、已知A=(a,b), B=(A,A),那么GetHead(GetHead(GetTail(B)))=( )。

A (a) B A C a D (A) 第六章

1、若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为(a) A CDBGFEA B CDBFGEA C CDBAGFE D BCDAGFE 2、二叉树第i(i>=1)层上至多有（ C ）结点。

A、２i b、２i c、２i－１ d、２i－１

3、如果结点a有三个兄弟，而且b为a的双亲，则b的度为（ D ）。 A、３ b、 ４ c、５ d、２

4、具有2000个结点的二叉树，其高度至少为（ C ）。

A、９ b、１０ c、１１ d、１２

5、中序遍历一棵二叉排序树所得到的结点序列是键值的（ C ）序列。 A、递增或递减 b、递减 c、递增 d、无序

6．在一棵具有5层的满二叉树中结点总数为 ( )。 A. 31 B. 32 C. 33 D. 16

7含5个结点（元素值均不相同）的二叉搜索树有（ ）种。 A、54 B、42 C、36 D、65

8一个二叉树按顺序方式存储在一个维数组中，如图 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G H I J 则结点E在二叉树的第（ ）层。 A、1 B、2 C、3 D、4

9下列存储形式中，( ) 不是树的存储形式。

A. 双亲表示法 B. 左子女右兄弟表示法 C. 广义表表示法 D. 顺序表示法

第七章

2．具有 n 个顶点的有向完全图有（ ）条弧。 A n B n*(n-1) C n*(n+1) D n*n 3 n 个顶点的连通图至少有（ ）条边。 A、n-1 B 、n C、n+1 D、0 第九章

1排序趟数与序列的原始状态(原始排列)有关的排序方法是（ d ）排序方法。 A 插入 B 选择 C 冒泡 D 快速

2．设有100个数据元素，采用折半搜索时，最大比较次数为 ( )。

A. 6 B. 7 C. 8 D. 10

3 对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是 ( )。

A. 直接选择排序 B. 直接插入排序 C. 快速排序 D. 起泡排序

4 对5个不同的数据元素进行直接插入排序，最多需要进行 ( ) 次比较。 A. 8 B. 10 C. 15 D. 25

5一个有序顺表有255个对象，采用顺序搜索法查表，搜索长度为（ ）。 A、128 B、127 C、126 D、255

6在分析析半搜索的性能时时常加入失败结点，即外结点，从而形成扩充的二叉树。若设失败结点?所在层次为,那么搜索失败到达失败点时所做的数据比较次数是（ ）。

A、Li+1 B、Li+2 C、Li-1 D、Li

7设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列存储空间应能够至少容纳（ ）个表项。（设搜索成功的平均搜索长度为Snl=(n+1/(1-a))/2,其中a 为装填因子） A、400 B、526 C、624 D、676

9、采用折半查找方法进行查找，数据文件应为（ ），且限于（ ）。 A 有序表 顺序存储结构 B 有序表 链式存储结构 C 随机表 顺序存储结构 D 随机表 链式存储结构

10、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其存放在已排序序列的合适位置，该排序方法称为（ ）排序法。

A 插入 B 选择 C 希尔 D 二路并归

11、就平均查找速度而言，下列几种查找速度从慢至快的关系是（ ） A 顺序 折半 哈西 分块 B 顺序 分块 折半 哈西 C 分块 折半 哈西 顺序 D 顺序 哈西 分块 折半

12．将递归算法转换成对应的非递归算法时，通常需要使用____。 （1）栈 （2）队列 （3）链表 （4）数组

13、在下列算法中，（ ）算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。 A 堆排序 B 冒泡排序 C 插入排序 D 快速排序

二、填空题

第一二章

1、算法是指令的有限序列，其中每一条指令表示一个或多个操作，此外，一个算法还具有五个重要特性，它们分别是 有穷性 、 确定性 、 可行性 、有零或多个输入和有一或多个输出。 2、循环链表的主要优点是 从任何一个结点出发可以遍历所有结点 。 3．为度量一个搜索算法的性能，需要在_____________和空间复杂度方面进行权衡。 4． 算法优劣的五个标准是正确性、可使用性、____、____、____。 5． 下面程序段的时间复杂度是_____。 For(i=0;i

For(j=0;j

6． 用顺序存储方式实现的线形表，称为________。 7． 单链表是______的链接存储表示。

8． 在一个单链表中删除p所指结点的下一个结点时，应执行以下操作： q=p->link;

p->link=______ Delete q

9． 将适当的语句添入单链表搜索函数find中。

templateListNode*List::find(Type value){ current=frist->link while(current!=NULL)

if(current->data=value)break else current=current->link;

return _______ }

10．算法是指令的有限序列，其中每一条指令表示一个或多个操作，此外，一个算法还具有五个重要特性，它们分别是 、 、可行性、有零或多个输入和有一或多个输出。

11．为度量一个搜索算法的性能，需要在时间复杂度和空间复杂度方面进行权衡。

12数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间__________的等等的学科。

第三四章

1设有串t=’I am a student ’，s=’good’，那么Concat(t,s)= ’I am a student good’，Substr(t,8,7)= ‘student’ 。

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

3对于一个以顺序实现的循环队列Q[0…m-1]，队头、队尾指针分别为f、r，其判空的条件是 r=f ，判满的条件是 (r+1)%m=f 。

4． 设有两个串p和q，求p在q中首次出现的位置的运算称为_________。 5． 栈、队列逻辑上都是________结构。

6． 在具有n个单元的循环队列中，队满时共有_______个元素。

第五章

1． 创建动态数组，可用________声明数组。

2． 广义表((a),a)的表头是_______，表尾是_______。

3． 广义表((a)，((b)，c)，(((d)))的长度是______，深度为_______。

4．设有一个矩阵A8×6，采用压缩存储方式，以行序为主序存储，a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则 a56地址为__________。

第六章

1具有n个叶子的二叉树，每个叶子的权值为wi(1≤i≤n)其中带权路径最小的二叉树被称为 霍夫曼树 。 2若已知一棵二叉树的深度为k(k≥1)，则这棵树至多有 2k-1 个结点，这棵树的第i (1≤i≤k)层上至多有 2i-1 个结点，若这是一棵具有n结点的完全二叉树，则k与n的关系为 k=┗log2n┛+1 。

3．具有64个结点的完全二叉树的深度为7。

4．若已知一棵二叉树的先序序列为 – + a * b – c d / e f，中序序列为a + b * c – d – e / f，则其后序序列为___________。 5已知一棵完全二叉树存放于一个一维数组T[n]中，T[n]中存放的是各结点的值。下面算法的功能是：从T[0]开始顺序读出各结点的值，建立该二叉树的二叉链表表示。

此算法有5处缺失，请根据算法的功能补充之。 (10分)

template istream& operator >> ( istream& in, BinaryTree& t ) { int n;

cout << \in >> n; Type *A = new Type[n+1];

①

for ( int i = 0; i < n; i++ ) ;

t. ConstructTree( T, n, 0, ptr ); //以数组建立一棵二叉树

②

;

return in; }

template void BinaryTree ::

ConstructTree ( Type T[ ], int n, int i, BinTreeNode *& ptr ) {

//将用T[n]顺序存储的完全二叉树, 以i为根的子树转换成为用二叉链表表示的

③

//以ptr为根的完全二叉树。利用引用型参数ptr将形参的值带回实参。

if ( i >= n ) ;

else {

ptr = new BinTreeNode ( T[i] ); //建立根结点

⑤

④

ConstructTree ( T, n, 2*i+1, );

ConstructTree ( T, n, , ptr->rightChild );

} }

缺失的语句为：①②③④⑤

第七章

1、在有n个顶点的有向图中，每个顶点的度最大可达 2（n-1） 。

2、有向图g用邻接矩阵a［１…m,1…m］来存储，其第i行的所有元素之和等于顶点i的3．关键路径是指途中从原点到会点的路径长度最长的路径。 4一个具有n个结点的无向图，至多有n(n-1)/2条边。

5．具有n个顶点的有向图最多有__________条边。

6．若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个________矩阵。 下面给出的算法是建立AOV网络并对其进行拓扑排序的算法，其中有多个语句缺失。 void Graph::TopologicalSort ( ) { Edge * p, q; int i, j, k; for ( i = 0; i < n; i++ ) {

。 出度 NodeTable[i].adj = NULL;

? ;

}

cin >> j >> k; //输入有向边 while ( j && k ) {

p = new Edge (k); //建立边结点, dest域赋为k

p→link = NodeTable[j].adj; //链入顶点j的边链表的前端

cin >> j >> k; }

int top = -1;

for ( i = 0; i < n; i++ ) //建立入度为零顶点的链栈 if ( count[i] == 0 ) { count[i] = top; ? }

for ( i = 0; i < n; i++ ) if ( top == -1 )

{ cout << \return; } else {

j = top;

ˉ ;

cout << NodeTable[j].data << endl; q = NodeTable[j].adj;

while ( q ) { k = q→dest; if ( -- count[k] == 0 ) { count[k] = top; top = k; }

° }

}

}

(1) 请将缺失的语句补上： （10分） ? ? ˉ

;

count[k]++; //顶点k入度加一

;

;

(2) 请给出对于下面AOV网络，使用上述算法进行拓扑排序的结果，以及在count数组中建立的链式栈的变化。（top是栈顶指针） （10分）

top→ A B C D E F

初始 第九章

1．设有100个数据元素，采用折半搜索时，最大比较次数为__________。

2．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是___________。

3．将5个不同数据进行排序，至少需要比较4次，至多需要比较10次。 4．二分查找的平均查找长度为[(n+1)/n]log2(n+1)-1。 log2(n+1)-1

5常用的构造哈希函数的方法有 、 、 、折叠法、随机数法和数字分析法。 6、直接选择排序算法在最好情况下所作的交换元素的次数为0。

7、有n个球队参加的足球联赛按主客场制进行比赛，共需进行 n(n-1) 场比赛。８、8、8、在含有n个元素的顺序表中，用顺序查找方法，查找不成功的查找长度为 n+1 。

9． 在程序设计中那三种情况下，常常要用到递归：定义是递归的、_______、_______. 10． 将函数F=1+1/2+1/3+.....+1/n用递归运算，其递归体是______。

三、判断题

1、数据元素是数据的最小单位。（ × ）

2、顺序表用一维数组作为存储结构，因此顺序表是一维数组。（）

3、算法的运行时间涉及加、减、乘、除、转移、存、取等基本运算。要想准确地计算总运算时间是不可行的。（） 4、数据结构、数据元素、数据项在计算机中映像（或表示）分别称为存储结构、结点、数据域。（Y ） 5、在单链表中，要取得某个元素，只要知道该元素指针即可，因此单链表是随机存储结构（ N ）。 1、栈的特点是后进先出。（ √ ）

2、使用三元组表示稀疏矩的元素，有时并不能节省空间。（ √ ）

3、栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。

4、在使用后缀表示实现计算器类时用到一个栈的实例，其作用是暂存运算对象。

4、已知二叉数的前序遍历和后序遍历并不能唯一的确定这棵树，因为并不知道树的根结点是哪一个。（ × ） 5、栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。 使用三元组表示稀疏矩的元素，有时并不能节省空间。（ Y ） 串的联接不满足交换律，满足结合律。（ Y ）

6、二维数组是数组元素为一维数组的线性表，因此它是线性结构。

7、磁盘上读写一块信息所需的时间有查询时间、延迟时间和等待时间。（ × ） 8、顺序表用一维数组作为存储结构，因此顺序表是一维数组。

1、已知一棵树的先序序列和后序序列，一定能构造出该树。 （ √ ）

2、设由一棵树T转化的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。 （ × ） 3、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（ × ）

4．已知二叉数的前序遍历和后序遍历并不能唯一的确定这棵树，因为并不知道树的根结点是哪一个。（n）

5．（ ） 有n个结点的不同的二叉树有n！棵。1、对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。 （ × ）

6、具有n个结点的完全二叉树的高度为 ?log2 n? +1。（n ? 0, 根在第0层）

7、 在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有 n0 = nk + 1。

8、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。

9、用相邻矩阵法存储一个图时，再不考虑压缩存储的情况下，所占存储空间的大小只于图中结点的个数有关，而与图的边数无关。（Y ）

1、图G的最小生成树的代价一定小于其它生成树的代价。 （ × ）

2、任一AOV网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条。 （ √ ） 3、连通分量是无向图中的极小连通子图。

1、在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的个数有关，而且与每一块中的元素个数有关。 （ √ ）

2、只有在初始数据为逆序，冒泡排序所执行的比较次数最多。 （ × ） 3、快速排序是排序算法中最快的一种。 （ × ）

4、闭散列法通常比开散列法时间效率更高。

5、一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。

6．对于不同关键字可能得到同一哈希地址,即key1≠key2，而f(key1)= f(key2)，这中现象称为冲突。 7．（ ） 折半搜索适用于有序的顺序表，不适用于有序的链表。

哈西表的查找效率主要决于哈西表造表时选取的哈西函数和处理冲突的方法。（Y） 8、直接选择排序是一种不稳定的排序方法。

9、在2048个互不相同的关键码中选择最小的5个关键码，用堆排序比用锦标赛排序更快。 10、当3阶B 树中有255个关键码时，其最大高度（包括失败结点层）不超过8。 11、一棵3阶B 树是平衡的3路搜索树，反之，一棵平衡的3路搜索树是3阶B 树。

12、在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。在设计再散列函数时，要求计算出的值与表的大小m互质。

四、应用题

1、若一棵二叉树终端结点数为m，度为2的结点数为n，试证明m=n+1。(8’)

2、某乡有a,b,c,d,e五个村庄，地理位置分布如下图所示，弧上的数值表示两村之间的距离，若要在乡内建立一所医院，则设在哪个村庄才能使各村离医院的距离最近，为什么？(10’)

2 4

1 2 3

1 5

3、已知一关键字序列为（40，11，16，31，23，55，13，45，50），试生成一棵平衡的二叉排序树,再从生成的平衡的二叉排序树中删除关键字45。（12’）

4、已知一组元素为（ 45，62，25，78，81，36，47，25，79 ），画出按元素排列顺序输入生成的一棵二叉排序树。 有9个带权结点 a、b、c、d、e、f、g、h、I，分别带权 4，2，7，12，6，10，5，9，3，试以他们为叶子结点构造一棵哈夫曼树（请按照左子树根结点的权小于等于右子树根结点的权的次序构造）。 如下图1，求v1到其它各顶点最短路径以及运算过程。（用表格画出来）

6

本文来源：https://www.bwwdw.com/article/thzg.html