数据结构习题册修订版.docx
《数据结构习题册修订版.docx》由会员分享，可在线阅读，更多相关《数据结构习题册修订版.docx（26页珍藏版）》请在冰点文库上搜索。
数据结构习题册修订版
数据结构习题册
中南民族大学计算机科学学院
软件基础教研室
目录
第一章绪论3
第二章线性表5
第三章栈与队列9
第四章串12
第五章数组和广义表13
第六章树和二叉树14
第七章图18
第九章查找22
第十章内部排序24
第一章绪论
一、选择题
1、数据结构被形式定义为二元组（D，S），其中D是（）的有限集合，S是D上的（）有限集合。
A、算法B、数据元素C、逻辑关系D、存储映像
2、数据结构是一门研究非数值计算的程序设计问题中计算机的（
（1））以及它们之间的（
（2））和运算（或操作）的学科。
（1）A、操作对象B、计算方法C、逻辑存储D、数据映象
（2）A、结构B、关系C、运算D、算法
3、算法分析的目的是（），算法分析的二个主要方面是（）。
A、给出数据结构的合理性B、研究算法中输入输出的关系
C、分析算法的易懂性和文档性D、分析算法的效率以求改进
E、正确性和简明性F、空间复杂性和时间复杂性
4、在数据结构中，从逻辑上可以把数据结构分成（）两大类。
A、动态和静态结构B、紧凑接和非紧凑结构
C、线性与非线性结构D、内部结构和外部结构
5、计算机算法指的是（），它必具备输入、输出和（）5个特性。
A、计算方法B、排序方法C、解决某个特定问题的有限运算序列
D、可行性、可移植性和可扩充性E、可行性、确定性和有穷性
二、填空题
1、所谓数据的逻辑结构指的是数据元素之间的（）。
数据的逻辑结构一般可包括（、、、）四种类型。
2、数据对象是性质相同的（）的集合。
3、线性结构中的数据元素之间存在着（）关系，树型结构中的数据元素之间存在着（）关系，图型结构中的数据元素之间存在（）关系。
三、综合题
1、指出下列两个算法的时间复杂度。
（1）intsum1（intn）
{intp=1,sum=0,i;
for（i=1;i<=n;i++）
{p*=i;sum+=p;}
return（sum）;
}
（2）intsum2（intn）
{intsum=0,i,j;
for（i=1;i<=n;i++）
{p=1;
for（j=1;j<=i;j++）
p*=j;
sum+=p;
}
returm（sum）;
}
3、有下列几种用二元组表示的数据结构，画出它们对应的逻辑图形表示，并指出它们属于哪种结构。
（1）A=（K，R），其中：
K={a,b,c,d,e,f,g,h}R=（r）
r={,,,,,,}
（2）B=（K,R）,其中：
K={a,b,c,d,e,f,g,h}R=（r）r={,,,,,,}
4、逻辑结构与存储结构是什么关系?
第二章线性表
一、选择题
1
2
3
4
5
6
7
8
9
10
11
1、表长为N的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（），删除一个元素需要移动的元素平均个数为（）。
A.（N-1）/2B.NC.N-1D.N/2
2、线性表采用链式存储结构时，要求内存中可用存储单元的地址（）。
A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以。
3、带头结点的单链表（head为头指针）为空表的判定条件是（）。
A、head==NULLB、head->next==NULLC、head->next==headD、head!
=NULL
4、不带头结点的单链表（head为头指针）为空表的判定条件是（）。
A、head==NULLB、head->next==NULLC、head->next==headD、head!
=NULL
5、非空的单向循环链表（head为头指针）的尾结点P满足（）。
A、P->NEXT=NULLB、p=NULLC、p->next==headD、p==head
6、在一个单链表中，若删除P所指结点的后继结点，则执行（ ）。
Ａ、p->next=p->next->nextＢ、p=p->next;p->next=p->next->next
Ｃ、p->next=p->next;Ｄ、p=p->next->next;
7、在一个单链表中，若在Ｐ所指结点之后插入Ｓ所指结点，则执行（ ）。
Ａ、s->next=p;p->next=s;Ｂ、s->next=p->next;p->next=s;
Ｃ、s->next=p->next;p=s;Ｄ、p->next=s;s->next=p;
8、对于顺序表的优缺点，以下说法错误的是（）
A、无需为表示结点间的逻辑关系而增加额外的存储空间
B、可以方便地随机存取表中的任一结点
C、插入和删除运算较方便
D、由于顺序表要求占用连续的空间，存储分配只能预先进行（静态分配）
9、已知Ｌ是无表头结点的单链表，试从下列提供的答案中选择合适的语句序列，分别实现：
（１）表首插入Ｓ结点的语句序列是（ ）。
（２）表尾插入Ｓ结点的语句序列是（ ）。
Ａ、Ｐ->next=S;Ｂ、P=L;Ｃ、L=S;Ｄ、P->next=S->next;
Ｅ、S->next=P->next;Ｆ、S->next=L;Ｇ、S->next=NULL;
Ｈ、while（P->next!
=NULL）P=P->next;
10、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。
A、顺序表B、单链表C、双链表D、单循环链表
11、循环链表主要优点是（）
A、不再需要头指针了
B、已知某个结点的位置后，能够容易找到它的直接前趋
C、在进行插入、删除运算时，能更好地保证链表不断开
D、从表中任一结点出发都能扫描到整个链表
二、综合题
1、若线性表的元素总数基本稳定，且很少进行插入删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构。
为什么？
2、若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用哪种存储结构？
为什么？
3、下列算法的功能是什么？
LinkedListtest1（LinkedListL）//L是无头结点的单链表
{ListNode*q,*p;
if（L&&L->next）
{q=L;L=L->next;p=L;
while（p->next）p=p->next;
p->next=q;q->next=NULL;
}
returnL;
}
4、设计算法
（1）将一个非空的不带头结点的单链表L逆置，要求自定义结点结构，不再另申请存储空间。
（2）将一个带头结点的单链表A分解为两个具有相同结构的链表B和C。
其中B表中的结点为A表中值为奇数的结点，而C表中的结点为A表中值为偶数的结点。
（要求利用原表的结点，即除了头结点外不再另申请存储空间。
）
单链表的结点类型定义如下：
typedefstructnode{
intdata;
structnode*next;
}LinkNode,*LinkList;
算法的函数原型给定为：
voidfunc3（linklist&A,linklist&B,linklist&C）
（3）已知线性表中的元素按增值排序，并以带表头结点的单链表作存储结构。
试编写一个函数，删除表中所有值大于m1且小于m2的元素（若表中存在这样的元素），m1和m2是给定的两个参变量，它们的值为任意的整数。
第三章栈与队列
一、选择题
1
2
3
4
5
6
7
8
9
10
1、栈和队列的共同点是（）
A、都是先进后出B、都是先进先出
C、只允许在端点处插入和删除元素D、没有共同点
2、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1，则栈的容量至少应该是（）
A、2B、3C、5D、6
3、若一个栈的输入序列是a,b,c，则通过入、出栈操作可能得到a,b,c的不同排列个数为（）
A、4B、5C、6D、7
4、设有一顺序栈已经含有3个元素，如下图所示。
元素a4正等待进栈。
下列不可能出现的出栈序列是（）
A、a3,a1,a4,a2B、a3,a2,a4,a1C、a3,a4,a2,a1D、a4,a3,a2,a1
0maxsize-1
a1
a2
a3
5、若一个栈的输入序列是1,2,3,4,…,n，输出序列的第一个元素是n，则第i个输出元素是（）
A、不确定B、n-iC、n-i+1D、n-i-1
6、一个队列的入列序列是1，2，3，4，则队列的输出序列是（）
A、4，3，2，1B、1，2，3，4C、1，4，3，2D、3，2，4，1
7、循环队列Q采用数组空间Q.base[n]存放其元素值，已知其头尾指针分别是Q.front和Q.rear，则判定此循环队列为空的条件是（）
A、Q.rear-Q.front==nB、Q.rear-Q.front-1==n
C、Q.front==Q.rearD、Q.front==Q.rear+1
8、循环队列Q采用数组空间Q.base[n]存放其元素值，已知其头尾指针分别是Q.front和Q.rear，则判定此循环队列为满的条件是（）
A、Q.front==Q.rearB、Q.front!
=Q.
C、Q.front==（Q.rear+1）%nD、Q.front!
=（Q.rear+1）%n
9、若在一个大小为6的数组上实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）
A、1，5B、2,4C、4，2D、5，1
10、设栈S和队列Q的初始状态为空，元素a,b,c,d,e,f依次通过栈S，一个元素出栈后即进入队列Q。
若这6个元素出队列的顺序是b,d,c,f,e,a则栈S的容量至少应该是（）。
A、2B、3C、4D、5
二、填空题
1、线性表、栈、队列都是（）结构，但线性表可以在（）位置插入和删除元素；但栈只能在（）插入和删除元素，故栈的特点是先进（）；而队列只能在（）插入元素和在（）位置删除元素，故队列的特点是先进（）。
2、有程序如下，则此程序的输出结果（栈的元素类型是SelemType为char）是（）。
voidmain（）
{stacks;charx,y;
initstack（s）;
x=’c’;y=’k’;
push（s,x）;push（s,’a’）;push（s,y）;
pop（s,x）;push（s,’t’）;push（s,x）;
pop（s,x）;push（s,’s’）;
while（!
stackempty（s））
{pop（s,y）;printf（y）;}
printf（x）;}
3、有程序如下，则此程序的输出结果（队列的元素类型是QSelemType为char）是（）。
voidmain（）
{charx=’e’,y=’c’;
enqueue（q,’h’）;enqueue（q,’r’）;
enqueue（q,y）;dequeue（q,x）;
enqueue（q,x）;degueue（q,x）;
enqueue（q,’a’）;
while（!
queueempty（q））
{dequeue（q,y）;printf（y）;}
printf（x）;
}
三、综合题
1、简述以下算法的功能（栈的元素类型是SelemType为int）。
（1）statusalgo1（stacks）
{intI,n,a[255];n=0;
while（!
stackempty（s））
{n++;pop（s,a[n]）;}
for（I=1;I<=n;I++）
push（s,a[I]）;
}
（2）statusalgo2（stacks,inte）
{stackt;intd;
initstack（t）;
while（!
stackempty（s））
{pop（s,d）;if（d!
=e）push（t,d）;}
while（!
stackempty（t））
{pop（t,d）;push（s,d）;}}
2、简述以下算法的功能（栈和队列的元素类型均为int）
voidalgo（queue&q）
{stacks;intd;initstack（s）;
while（!
queueempty（q））{dequeue（q,d）;push（s,d）;}
while（!
stackempty（s））{pop（s,d）;enqueue（q,d）;}
}
第四章串
一、选择题
1
2
3
4
5
1、串是一种特殊的线性表，其特殊性体现在（）。
A、可以顺序存储B、数据元素限定是一个字符
C、可以链接存储D、数据元素可以是多个字符
2、设有两个串p和q，求q在p中首次出现的位置的运算称为（）。
A、连接B、模式匹配C、求子串D、求串长
3、下面关于串的的叙述中，哪一个是不正确的？
（）
A．串是字符的有限序列B．空串是由空格构成的串
C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储
4、串的长度是指（）
A．串中所含不同字母的个数B．串中所含字符的个数
C．串中所含不同字符的个数D．串中所含非空格字符的个数
5、两个串相等的充分必要条件是（）
A．串中所含的字符相同B．串中所含字符的个数相同，且对应位置上的字符也相同
C．串中所含的字符个数相同D．串中对应位置上的字符相同
二、综合题
1.设串s1=’ABCDEFG’，s2=’PQRST’，函数Concat（x,y）返回x和y串的连接串，Substr（s,i,j）返回串s从序号i开始的j个字符组成的子串，length（s）返回串s的长度，则Concat（Substr（s1,2,length（s2））,Substr（s1,length（s2）,2））的结果串是什么？
2.已知下列字符串（假设采用定长存储结构）
a=’this’,b=’‘,c=’good’,d=’ne’,
f=’asample’,g=’is’
顺序执行以下操作后的结果各是什么？
Concat（a,concat（Substr（f,2,7）））
Index（v,g）
第五章数组和广义表
一、选择题
1
2
3
4
5
6
1、二维数组SA[7][9]中，每个元素占用2个字节，该数组按行序为主序存放时，元素A[4][7]的起始地址为（）。
A、SA+86B、SA+74C、SA+84D、SA+88
2、将一个A[15][15]的下三角矩阵（第一个元素为A[1][1]），按行优先存入一维数组B[120]中，A中元素A[6][5]在B数组中的下标位置K为（）。
A、19B、26C、21D、15
3、广义表（（a）,a）的表头是（），表尾是（）。
A、aB、bC、（a）D、（（a））
4、广义表（（a））的表头是（），表尾是（）。
A、aB、（a）C、（）D、（（a））
5、对矩阵压缩存储是为了（）
A、方便运算B、节省空间C、方便存储D、提高运算速度
6、稀疏矩阵一般的压缩存储方法有两种，即（）
A、二元数组和三元数组B、三元组和散列
C、三元组和十字链表D、散列和十字链表
二、填空题
1、一个n阶对称矩阵A[n][n],采用一维数组S[N*（N+1）/2]按行序为主序存放其下三角各元素，写出S[k]与A[i,j]的关系公式（）
2、已知一个稀疏矩阵为
，则对应的三元组表表示为（）。
第六章树和二叉树
一、选择题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1、按照二叉树的定义，具有3个结点的二叉树有（）种不同形态。
A、3B、4C、5D、6
2、对一棵含有n个结点的满二叉树，共有m个叶子结点，深度为h，则（）
A、n=m+hB、h+m=2nC、m=h-1D、n=2h-1
3、在一棵二叉树上第5层的结点数最多为（）（假设根结点的层数为1）
A、8B、16C、15D、32
4、深度为5的二叉树至多有（）个结点。
A、16B、32C、31D、10
5、在下图中的二叉树中，（）不是完全二叉树。
A、B、C、D、
6、一棵有124个叶结点的完全二叉树，最多有（）个结点
A、247B、248C、249D、250
7、假定有一棵二叉树，双分支结点数为15，单分支结点数为30，则叶子结点数为（）个。
A、15B、16C、17D、47//n2+1=n0
8、下列叙述中正确的是（）
A、二叉树是度为2的有序树B、二叉树中结点只有一个孩子时无左右之分
C、二叉树中必有度为2的结点D、二叉树中结点最多有两棵子树且有左右之分
9、森林的中序遍历序列等同于该树对应的二叉树的（）。
A、先序遍历B、中序遍历C、后序遍历D、层次遍历
10、下列说法正确的是（）
A、树的先根遍历序列与其对应的二叉树的先根遍历序列相同
B、树的先根遍历序列与其对应的二叉树的后根遍历序列相同
C、树的后根遍历序列与其对应的二叉树的先根遍历序列相同
D、树的后根遍历序列与其对应的二叉树的后根遍历序列相同
11、以下说法错误的是（）
A、一般在哈夫曼树中，权值越大的叶子离根结点越近
B、哈夫曼树中没有度数为1的分支结点
C、若初始森林中共有n棵二叉树，最终求得的哈夫曼树共有2n-1个结点
D、若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树
12、哈夫曼树的带权路径长度是（）
A、所有结点权值之和 B、所有叶结点带权路径长度之和
C、带权结点的值 D、除根以外所有结点权值之和
13、在线索二叉树上，线索是（）
A、两个标志域B、指向结点前驱和后继的指针
C、数据域D、指向左、右子树的指针
14、已给出如下图所示哈夫曼树，若左分支放0，右分支放1，那么电文CDAA的编码是（）
A、110100B、11011100C、010110111D、11111100
二、综合题
1、将算术表达式（（a+b）+c*（d+e）+f）*（g+h）转化为二叉树。
2、分别说明满足下列条件的二叉树的特点。
（1）前序和中序遍历序列相同。
（2）中序和后序遍历序列相同。
（3）前序和后序遍历序列相同。
3、已知一棵二叉树的中序遍历序列为CDBAEGF，前序遍历序列为ABCDEFG，问能否唯一确定一棵树，请画出。
若给定前序和后序遍历序列，能否唯一确定，请说明理由。
4、将下图所示的树分别转换成一棵二叉树，分别写出各二叉树的前序、中序和后序序列。
5、设某密码电文由8个字母组成，每个字母在电文中的出现频率分别是7，19，2，6，32，3，21，10，试为这8个字母设计相应的哈夫曼编码（要求按每个结点的左子树根结点的权值小于或等于右子树根结点的权值的次序构造），并计算其带权路径长度。
6、算法设计：
二叉树中结点的存储结构定义为：
typedefstructnode
{intdata;
structnode*lch,*rch;
}BTNode；
（1）编写一个算法，在已知的二叉树（Root为根指针）中查找值为x的结点，找到后返回其指针，否则返回NULL。
（2）编写一个算法，在已知的二叉树（Root为根指针）中求二叉树的高度。
（3）编写一个算法，在已知的二叉树（Root为根指针）中求二叉树的叶子结点个数。
第七章图
一、选择题
1
2
3
4
5
6
7
8
9
10
11
12
1、一个有n个顶点的无向图最多有（）条边。
A、nB、n（n-1）C、n（n-1）/2D、2n
2、具有4个顶点的无向完全图有（）条边。
A、6B、12C、16D、20
3、具有n个顶点的无向图至少有（）条边才能保证是一个连通图。
A、nB、n-1C、n+1D、n（n-1）/2
4、设连通图G的顶点数为n，则G的生成树的边数为（）。
A、n-1B、nC、2nD、2n-1
5、采用邻接表存储的图的深度和广度优先搜索遍历算法类似于二叉树的（）和（）。
A、中序遍历B、先序遍历C、后序遍历D、层次遍历
6、已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先搜索遍历算法，从顶点v1出发，得到的顶点序列分别为（）和（）。
A、v1,v2,v3,v4,v5B、v1,v3,v2,v4,v5C、v1,v2,v3,v5,v4D、v1,v4,v3,v5,v2
7、在一个图中，所有顶点的度数之和等于所有边数的（）倍。
A、1/2B、1C、2D、4
8、下面结论中正确的是（）
A、在无向图中，边的条数是顶点度数之和。
B、在图结构中，顶点可以没有任何前驱和后继。
C、在n个顶点的无向图中，若边数大于n-1，则该图必定是连通图
D、图的邻接矩阵必定是对称矩阵。
9、已知一个图如下，则由该图得到的一种拓扑序列为（）。
A、v1,v4,v6,v2,v5,v3B、v1,v2,v3,v4,v5,v6
C、v1,v4,v2,v3,v6,v5D、v1,v2,v4,v6,v3,v5
10、下面结论不正确的是（）。
A、无向图的连通分量是该图的极大连通子图。
B、有向图用邻接矩阵表示容易实现求顶点度数的操作。
C、无向图用邻接矩阵表示，图中的边数等于邻接矩阵元素之和的一半。
D、无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。
11、下面结论中正确的是（）。
A、按深度优先搜索遍历图时，与始点相邻的顶点先于不与始点相邻的顶点访问。
B、一个图按深度优先搜索遍历的结果是唯一的。
升级会员 