数据结构练习题Word文档下载推荐.docx

数据结构练习题Word文档下载推荐.docx

《数据结构练习题Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《数据结构练习题Word文档下载推荐.docx（18页珍藏版）》请在冰点文库上搜索。

数据元素是数据不可分割的最小单位。

（错）

6.数据结构中评判算法的两个重要指标是算法的时刻复杂度和空间复杂度。

7.四种大体的数据结构为集合线性结构树形结构、图状结构或网状结构

8.算法的五个特性是有穷性确信性、可行性、输入和输出。

9.数据结构在运算机中的表示称为数据的物理结构，又称存储结构

10.数据结构是一门研究非数值计算的程序设计问题中运算机的操作对象和它们之间的关系和操作的学科

第二章

1（1/1分）

顺序存储时，要求内存可用存储单元的地址（）

必然持续必然持续-正确必然不持续不必然持续部份持续，部份不持续

2（1/1分）

以下说法中正确的选项是（）

顺序存储方式只能用于线性结构，不能用于非线性结构

基于某种逻辑结构之上的运算，其实现是唯一的

算法能够用不同的语言描述，那么算法事实上确实是程序了

数据结构的三大组成部份是逻辑结构、存储结构和运算-正确

3（1/1分）

线性表（a1,a2,…,an）以顺序方式存储时，访问第i（1≤i≤n）个位置元素的时刻复杂度为（）。

4（1/1分）

在一个以L为头的单循环链表中，p指针指向链尾的条件是（）。

p->

next==L-正确Bp->

next==NULLCp->

next->

next==LDp->

data==-1

5（1/1分）

链式存储时，要求存储单元的地址（）。

必然持续必然不持续不必然持续-正确部份持续,部份不持续

6（1/1分）

在一个单链表中，已知q所指结点是p所指结点的前驱结点，假设在q和p之间插入s结点，那么执行（）

7（1/1分）

假设某线性表中最经常使用的操作是在最后一个元素以后插入一个元素和删除第一个元素，那么采纳（）存储方式最节省时刻。

8（1/1分）

设指针变量p指向单链表中结点A（结点A不是尾结点），假设删除单链表中结点A，那么需要修改指针的操作序列为（）。

9（1/1分）

在一个以L为头的非循环单链表中，p指针指向链尾的条件是（）。

next==Lp->

next==NULLp->

next==NULL-正确p->

10（1/1分）

链表不具有的特点是（）。

插入、删除不需要移动元素

可随机访问任一元素-正确

没必要事前估量存储空间

所需空间与线性长度成正比

11（1/1分）

假设线性表最经常使用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，那么利用（）存储方式最节省时刻。

顺序表-正确双链表带头结点的双循环链表单循环链表

12（1/1分）

不带头结点的单链表为空的判定条件是（）

head==NULL-正确head->

next==NULLhead->

next==headhead!

=NULL

13（1/1分）

线性表（a1,a2,…,an）以链接方式存储时，访问第i（1≤i≤n）个位置元素的时刻复杂度为（）。

14（1/1分）

判定正误：

线性表中的任一元素都有唯一的前驱和后继。

第三章

输入序列为abc，假设输出序列为bca，通过的栈操作为（）。

push,pop,push,pop,push,poppush,push,push,pop,pop,poppush,push,pop,push,pop,poppush,push,pop,push,pop,pop-正确push,pop,push,push,pop,pop

一个栈的入栈序列为a，b，c，d，e，那么出栈的不可能序列为（）。

edcbadecbadceabd-正确abcde

设有一顺序栈S，元素s一、s二、s3、s4、s五、s6依次入栈，若是6个元素出栈的顺序是s二、s4、s3、s六、s五、s1，那么栈的容量至少应该是（）

23-正确56

一个栈的输入序列为123…n，假设输出序列的第一个元素是n，输出第i（1<

=i<

=n）个元素是（）。

不确信n-i+1n-i+1-正确in-i

假设一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，那么第j个输出元素是（）。

i-j-1i-jj-i+1不确信的不确信的-正确

假设进队列的序列为1,2,3,4那么（）是一个出队列序列。

3,2,1,43,2,4,14,2,3,11,2,3,41,2,3,4-正确

栈和队列的一起特点是（）。

只许诺在端点处插入和删除元素只许诺在端点处插入和删除元素-正确都是先进后出都是先进先出没有一起点

循环队列Q的最大容量为M,循环队列队空的条件是（）

Q.front==Q.rearQ.front==Q.rear-正确Q.front！

=Q.rearQ.front==（Q.rear+1）%MQ.front!

=（Q.rear+1）%M

循环队列Q的最大容量为M,循环队列队满的条件是（）

Q.front==Q.rearQ.front！

=Q.rearQ.front==（Q.rear+1）%MQ.front==（Q.rear+1）%M-正确Q.front!

栈式结构的铁路调度站,入栈顺序为1,2,3的三列车,并在任何时候许诺出栈,那么出栈顺序有（）种。

2355-正确6

假设用一个大小为6的数组来实现循环队列，且当前rear和front的值别离为0和2。

当从队列中删除3个元素，再插入上2个元素后，rear和front的值别离为（）。

5和22和52和5-正确3和22和3

第四章

下面关于串的表达中，哪个是不正确的？

（）

串是字符的有限序列空串是由空格组成的串空串是由空格组成的串-正确模式匹配是串的一种重要运算　串既可采纳顺序存储，也可采纳链式存储

显示答案揭露答案您已经利用了1次中的1次提交

串的长度是指（）。

串中所含不同字母的个数串中所含字符的个数串中所含字符的个数-正确串中所含不同字符的个数串中所含非空格字符的个数

假设串S="

abcdefghi"

，不考虑空串时其子串数量为（）。

444545-正确4647

>

index（"

DATASTRUCTURE"

"

STR"

）=_____（请以中文数字作答）

五-正确

KMP算法求模式串S="

abaabc"

的next[j]函数值为_____（请以中文数字作答）

零一一二二三-正确

第五章

广义表L1=（a,（b,c,d）），gethead（gethead（gettail（L）））=（）

bb-正确c（b,c,d）d

显示答案揭露答案您已经利用了2次中的2次提交

设有一个10阶的对称矩阵A，采纳紧缩存储方式，以行序为主序存储，a11为第一个元素，其存储地址为1，每一个元素占一个地址空间，那么a85的地址为（）

133333-正确1840

广义表A=（a,e,A），长度和深度别离是（）

3，13,33，∞3，∞-正确1，1

对稀疏矩阵进行紧缩存储的目的是（）

便于进行矩阵运算便于输入和输出节省存储空间节省存储空间-正确降低运算的时刻复杂度

特殊矩阵紧缩存储后仍可实现随机存取。

对对-正确错

6（此题共有1分）

数组M[8][10]中每一个元素占4个字节，首地址LOC（M00）=1000假设按行优先寄存，元素M[7][5]的首地址是________。

（一三零零）

第六章

给定n个权值，构造哈夫曼树，那么哈夫曼树的结点总数为（）

不确信2n2n+12n-12n-1-正确

一棵深度为k的完全二叉树最多有（）个结点。

在完全二叉树中，假设一个结点的编号为i，若是它有右小孩，那么右小孩的编号必为（）

2*i2*i+12*i+1-正确2*i-1不能确信

以下数据结构中，哪个是线性结构？

树二叉树图串串-正确

一棵具有1025个结点的二叉树的高度h为（）

111011至1025之间11至1025之间-正确11至1024之间

深度为h的满m叉树的第k层有（）个结点（1≤k≤h）。

7.在完全二叉树中，假设一个结点的编号为i,那么它的双亲结点的编号为（）

2*i2*i+1i/2i/2-正确不能确信

8.具有1000个结点的二叉树，其高度至少为（）

91010-正确1112

9.假设一棵二叉树具有10个度为2的结点，5个度为1的结点，那么度为0的结点个数是（）

91111-正确15不确信

10.第6层有4个结点的完全二叉树，其结点总数为，其叶子结点共有（）个。

36,1635,2036，1535，1835，18-正确

已知一棵二叉树的前序遍历的结果是ABECDF,中序遍历的结果是EBCADF,那么其后序遍历的结果是（）

ECBFDAECBFDA-正确FEDCBAEBCDFAECBADF

已知某二叉树有50个叶子结点，那么该二叉树的总结点数至少是（）（请以中文数字作答。

如：

八七）

九九-正确

给定一组数据{6,2,7,10,3,12}，以它构造一棵哈夫曼树，那么带权途径长度WPL的值为（）（请以中文数字作答。

九六-正确

n个结点的二叉树的二叉链表有（）个空链域

n+1-正确

15（1/1分）

3个结点的二叉树有（）种不同形态。

（请以中文数字作答。

二）

16（此题共有1分）

有k个叶子结点的带权途径长度最小的二叉树共有（2k--）个结点（答案中数字请以中文数字代替。

三k+五）

第七章

关于具有n个极点的图，假设采纳邻接矩阵表示，那么该矩阵的大小为（n的平方）。

2.若是从无向图的任一极点动身进行一次深度优先搜索即可访问所有极点，那么该图必然是（）。

完全图连通图连通图-正确有回路一棵树

3（0.5/0.5分）

关键途径是事件结点网络中（）。

从源点到汇点的最长途径　从源点到汇点的最长途径　-正确从源点到汇点的最短途径最长的回路最短的回路

4（0.5/0.5分）

下面（）能够判定出一个有向图中是不是有环（回路）。

广度优先遍历拓扑排序拓扑排序-正确求最短路径求关键路径

5（0.5/0.5分）

带权有向图G用邻接矩阵A存储，那么极点i的入度等于A中（）。

第i行非无穷的元素之和　第i列非无穷的元素个数之和第i列非无穷的元素个数之和-正确第i行非无穷且非0的元素个数第i行与第i列非无穷且非0的元素之和

6（0.5/0.5分）

无向图的邻接矩阵是一个（）。

对称矩阵对称矩阵-正确零矩阵上三角矩阵对角矩阵

7（0.5/0.5分）

邻接表是图的一种（）。

顺序存储结构链式存储结构链式存储结构-正确索引存储结构散列存储结构

8（0.5/0.5分）

下面有向图所示的拓扑排序的结果序列是（）。

125634516234516234-正确123456521643

9（0.5/0.5分）

在无向图中概念极点vi与vj之间的途径为从vi到vj的一个（）。

极点序列极点序列-正确边序列权值总和边的条数

10（0.5/0.5分）

在有向图的逆邻接表中，每一个极点邻接表链接着该极点所有（）邻接点。

入边入边-正确出边入边和出边不是出边也不是入边

11（0.5/0.5分）

设G1=（V1,E1）和G2=（V2,E2）为两个图，若是V1Í

V2,E1Í

E2那么称（）。

G1是G2的子图G1是G2的子图-正确G2是G1的子图G1是G2的连通分量G2是G1的连通分量

12（0.5/0.5分）

已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应（）。

将邻接矩阵的第i行删除将邻接矩阵的第i行元素全数置为0将邻接矩阵的第i行元素全数置为0-正确将邻接矩阵的第i列删除将邻接矩阵的第i列元素全数置为0

13（0.5/0.5分）

任一个有向无环图的拓扑序列（）。

不存在有一个必然有多个有一个或多个有一个或多个-正确

14（0.5/0.5分）

在一个有向图中，所有极点的入度之和等于所有极点的出度之和的（）倍。

1/211-正确24

15（0.5/0.5分）

以下关于图遍历的说法不正确的选项是（）。

连通图的深度优先搜索是一个递归进程图的广度优先搜索中邻接点的寻觅具有“先进先出”的特点非连通图不能用深度优先搜索法非连通图不能用深度优先搜索法-正确图的遍历要求每一极点仅被访问一次

16（0.5/0.5分）

一个具有n个极点的有向图最多有（）条边。

17（0.5/0.5分）

已知一个有向图的邻接表存储结构如下图，依照深度优先遍历算法，从极点v1动身，所取得的极点序列是（）。

v1,v2,v3,v5,v4v1,v2,v3,v4,v5v1,v3,v4,v5,v2v1,v3,v4,v5,v2-正确v1,v4,v3,v5,v2

18（0.5/0.5分）

以下说法正确的选项是（）。

连通分量是无向图中的极小连通子图强连通分量是有向图中的极大强连通子图强连通分量是有向图中的极大强连通子图-正确在一个有向图的拓扑序列中若顶点a在顶点b之前，则图中必有一条弧对有向图G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图

19（0.5/0.5分）

假设有向图含n个极点及e条弧，那么表示该图的邻接表中包括的弧结点个数为（）。

nee-正确2en*e

20（0.5/0.5分）

设图的邻接矩阵为以下图，那么该图为（）。

有向图有向图-正确无向图强连通图完全图

21（0.5/0.5分）

任何一个无向连通图的最小生成树（）种。

只有一棵有一棵或多棵有一棵或多棵-正确必然有多棵可能不存在

22（0.5/0.5分）

关于一个有向图，假设一个极点的入度为k1,、出度为k2，那么对应邻接表中该极点单链表中的结点数为（）。

k1k2k2-正确k1+k2k1-k2

23（0.5/0.5分）

一个具有8个极点的有向图中，所有极点的入度之和与所有极点的出度之和的差等于（）。

16400-正确2

24（0.5/0.5分）

无向图中一个极点的度是指图中（）。

通过该极点的简单途径数与该极点相邻接的极点数与该极点相邻接的极点数-正确与该极点连通的极点数通过该极点的回路数

25（0.5/0.5分）

在有n个极点的有向图中，每一个极点的度最大可达（）

n-12（n-1）2（n-1）-正确n（n-1）/2n（n-1）

26（0.5/0.5分）

采纳邻接表存储的图的深度优先遍历算法类似于二叉树的（）。

先序遍历先序遍历-正确中序遍历后序遍历按层遍历

27（0.5/0.5分）

采纳邻接表存储的图的宽度优先遍历算法类似于二叉树的（）。

先序遍历中序遍历后序遍历按层遍历按层遍历-正确

28（0.5/0.5分）

8个极点的生成树有（）条边。

7-正确

29（0.5/0.5分）

10个极点的连通无向图至少（）条边。

9-正确

30（0.5/0.5分）

具有4个极点的无向完全图有（）条边。

6-正确

31（0.5/0.5分）

具有n个极点的有向图，假设是强连通图，至少需要（）条弧。

n-正确

32（0.5/0.5分）

在有10个极点的无向图中，每一个极点的度最大可达（）。

33（0.5/0.5分）

一个有向图以邻接矩阵表示，计算第I个结点的出度的表方式是求矩阵第I（行）非零元素之和。

第八章

1（0.5/0.5分）

顺序查找法适合于存储结构为（）的线性表。

散列存储顺序存储或链接贮存顺序存储或链接贮存-正确紧缩存储索引存储

2（0.5/0.5分）

对线性表进行二分查找时，要求线性表必需（）

以顺序方式存储以链式方式存储以顺序方式存储，且结点按关键字有序排列以顺序方式存储，且结点按关键字有序排列-正确以链接方式存储,且结点按关键字有序排列

采纳顺序查找方式查找长度为n的线性表时，每一个元素的平均查找长度为

nn/2（n+1）/2（n+1）/2-正确（n-1）/2

采纳二分查找方式查找长度为N的线性表时，每一个元素的平均查找长度为（）

有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，（）次比较后查找成功。

1244-正确8

有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情形下查找成功所需的平均查找长度为（）

35/1237/1237/12-正确39/1243/12

若是要求一个线性表既能较快地查找，又能适宜动态转变的要求，能够采纳（）查找方式

分块分块-正确顺序二分散列

在各类查找方式中，平均查找长度与结点个数n无关的查找方式是（）

分块顺序二分哈希表查找法哈希表查找法-正确

在分块查找方式中，第一查找（），然后再查找相应的（）。

索引-正确

块-正确

10（1.5/1.5分）

假设在有序线性表A[1，20]上进行二分查找，那么比较一次查找成功的结点数为（），那么比较二次查找成功的结点数为（），那么比较三次查找成功的结点数为（），那么比较四次查找成功的结点数为（），那么比较五次查找成功的结点数为（），平均查找长度为（）。

1-正确

2-正确

4-正确

8-正确

5-正确

3.7-正确

第九章

在所有排序方式中，关键字比较的次数与记录的初始排序顺序无关的是（）

希尔排序起泡排序插入排序选择排序选择排序-正确

设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用（）排序法。

起泡排序快速排序堆排序堆排序-正确基数排序

在待排序的元素序列大体有序的前提下，效率最高的排序方式是（A）。

插入排序插入排序-正确选择排序快速排序归并排序

一组记录的排序码为（46，79，56，38，40，84），那么利用堆排序的方式成立的初始堆为（）。

79，46，56，38，40，8084，79，56，38，40，4684，79，56，38，40，46-正确84，79，56，46，40，3884，56，79，40，46，38

一组记录的关键码为（46，79，56，38，40，84），那么利用快速排序的方式，以第一个记录为基准取得的一次划分结果为（）。

38，40，46，56，79，8440，38，46，79，56，8440，38，46，56，79，8440，38，46，56，79，84-正确40，38，46，84，56，79

一组记录的排序码为（25，48，16，35，79，82，23，40，36，72），其中含有5个长度为2的有序表，按归并排序的方式对该序列进行一趟归并后的结果为（）

1625354823407982367216253548234079823672-正确162535487982233640721625483579822336407216253548792336407282

排序方式中，从未排序序列中依次掏出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方式，称为（）

希尔排序起泡排序插入排序插入排序-正确选择排序

排序方式中，从未排序序列中挑选元素，并将其依次放入已