数据结构习题填空判断选择Word文件下载.docx

数据结构习题填空判断选择Word文件下载.docx

《数据结构习题填空判断选择Word文件下载.docx》由会员分享，可在线阅读，更多相关《数据结构习题填空判断选择Word文件下载.docx（20页珍藏版）》请在冰点文库上搜索。

三、填空题

1.数据逻辑结构包括__集合__、__线性__、__树形__和__图状__四种类型,其中树形结构和图形结构合称为__非线性__。

2.在线性结构中,第一个结点__没有__前驱结点,其余每个结点有且只有__1__个前驱结点；

最后一个结点__没有__后续结点,其余每个结点有且只有__1__个后续结点。

3.在树形结构中,树根结点没有__前驱__结点,其余每个结点有且只有__1__个前驱结点；

叶子结点没有__后继__结点,其余每个结点的后续结点可以__任意多个__。

4.在图形结构中,每个结点的前驱结点数和后续结点数可以__任意多个__。

5.线性结构中元素之间存在__一对一__关系,树形结构中元素之间存在__一对多__关系,图形结构中元素之间存在__多对多__关系。

6.算法的五个重要特性是__有穷性__、__确定性__、__可行性__、__输入__、__输出__。

7.数据结构的三要素是指__数据元素__、__逻辑结构__和__存储结构__。

8.链式存储结构与顺序存储结构相比较,主要优点是__插入、删除、合并等操作较方便__。

9.设有一批数据元素,为了最快的存储某元素,数据结构宜用__顺序存储__结构,为了方便插入一个元素,数据结构宜用__链式存储__结构。

四、算法分析题

1.求下列算法段的语句频度及时间复杂度

for（i=1;

i<

=n;

i++）

for（j=1;

j<

=i;

j++）

x=x+1;

分析：

该算法为一个二重循环，执行次数为内、外循环次数相乘，但内循环次数不固定，与外循环有关，因些，时间频度T（n）=1+2+3+…+n=n*（n+1）/2

有1/4≤T（n）/n2≤1，故它的时间复杂度为Ｏ（n2）,即Ｔ（n）与n2数量级相同。

2、分析下列算法段的时间频度及时间复杂度

for（i=1;

i<

i++）

for（j=1;

j<

=i;

j++）

for（k=1;

k<

=j;

k++）

x=i+j-k;

分析算法规律可知时间频度T（n）=1+（1+2）+（1+2+3）+...+（1+2+3+…+n）

由于有1/6≤T（n）/n3≤1，故时间复杂度为Ｏ（n3）

第二章线性表

1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是（B）

（A）110（B）108（C）100（D）120

2.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（C）个元素。

（A）64（B）63（C）63.5　　（D）7

3.线性表采用链式存储结构时，其地址（D）。

（A）必须是连续的（B）部分地址必须是连续的

（C）一定是不连续的（D）连续与否均可以

4.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（B）

（A）s->

next=p;

p->

next=s;

（B）s->

next=p->

next;

（C）s->

p=s;

（D）p->

s->

5.在一个单链表中，若删除p所指结点的后续结点，则执行（A）

（A）p->

next->

（B）p=p->

p->

（C）p->

（D）p=p->

6.下列有关线性表的叙述中，正确的是（A）

（A）线性表中的元素之间隔是线性关系

（B）线性表中至少有一个元素

（C）线性表中任何一个元素有且仅有一个直接前趋

（D）线性表中任何一个元素有且仅有一个直接后继

7.线性表是具有n个（C）的有限序列（n≠0）

（A）表元素（B）字符（C）数据元素　（D）数据项

1.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。

2.如果没有提供指针类型的语言，就无法构造链式结构。

3.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。

4.语句p=p->

next完成了指针赋值并使p指针得到了p指针所指后继结点的数据域值。

5.要想删除p指针的后继结点，我们应该执行q=p->

next；

next=q->

next；

free（q）。

1.已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：

__s->

next;

__。

2.顺序表中逻辑上相邻的元素物理位置__一定__相邻，单链表中逻辑上相邻的元素物理位置__不一定__相邻。

3.线性表L＝（a1，a2，...，an）采用顺序存储，假定在不同的n＋1个位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是__n/2__

4.在非空双向循环链表中，在结点q的前面插入结点p的过程如下：

prior=q->

prior;

q->

prior->

next=q;

__q->

prior=p;

__;

5.已知L是无表头结点的单链表，是从下列提供的答案中选择合适的语句序列，分别实现：

（1）表尾插入s结点的语句序列是_______________6）3）______________

（2）表尾插入s结点的语句序列是___________2）9）1）7）______________

1.p->

2.p=L;

3.L=s;

4.p->

next=s->

5.s->

6.s->

next=L;

7.s->

next=null;

8.while（p->

next!

=Q）?

p=p-next;

9.while（p->

=null）p=p->

第三章栈和队列

1.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（C）。

（A）edcba（B）decba（C）dceab（D）abcde

2.栈结构通常采用的两种存储结构是（A）。

（A）线性存储结构和链表存储结构（B）散列方式和索引方式

（C）链表存储结构和数组（D）线性存储结构和非线性存储结构

3.判定一个栈ST（最多元素为m0）为空的条件是（B）。

（A）ST-〉top!

=0（B）ST-〉top==0

（C）ST-〉top!

=m0（D）ST-〉top=m0

4.判定一个栈ST（最多元素为m0）为栈满的条件是（B）。

（A）ST->

top!

=0（B）ST->

top==0

（C）ST->

=m0-1（D）ST->

top==m0-1

5.一个队列的入列序列是1,2,3,4,则队列的输出序列是（B）。

（A）4,3,2,1（B）1,2,3,4（C）1,4,3,2（D）3,2,4,1

6.循环队列用数组A[0,m-1]存放其元素值,已知其头尾指针分别是front和rear则当前队列中的元素个数是（B）

（A）（rear-front+m）%m（B）rear-front+1（C）rear-front-1（D）rear-front

7.栈和队列的共同点是（C）

（A）都是先进后出（B）都是先进先出

（C）只允许在端点处插入和删除元素（D）没有共同点

8.表达式a*（b+c）-d的后缀表达式是（C）。

（A）abcd*+-（B）abc+*d-（C）abc*+d-（D）-+*abcd

9.4个元素a1，a2，a3和a4依次通过一个栈，在a4进栈前，栈的状态，则不可能的出栈序是（　C　）

（A）a4，a3，a2，a1　（B）a3，a2，a4，a1

（C）a3，a1，a4，a2　（D）a3，a4，a2，a1

10.以数组Q[0..m－1]存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是（　D　）

（A）rear－qulen　（B）rear－qulen＋m　

（C）m－qulen　　（D）1＋（rear＋m－qulen）%m

二、填空题

1.栈的特点是____先进后出____,队列的特点是___先进先出___。

2.线性表、栈和队列都是___线性___结构,可以在线性表的___任何__位置插入和删除元素，对于栈只能在___栈顶__插入和删除元素，对于队列只能在___队尾__插入元素和___对头__删除元素。

3.一个栈的输入序列是12345,则栈有输出序列12345是___正确___。

（正确/错误）

4.设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳__3__个元素。

第五章数组和广义表

1.常对数组进行的两种基本操作是（C）

（A）建立与删除（B）索引和修改（C）查找和修改（D）查找与索引

2.二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串,行下标i的范围从0到4,列下标j的范围从0到5,M按行存储时元素M[3][5]的起始地址与M按列存储时元素（B）的起始地址相同。

（A）M[2][4]（B）M[3][4]（C）M[3][5]（D）M[4][4]

3.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,存放该数组至少需要的单元数是（C）。

（A）80（B）100（C）240（D）270

4.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A[7][4]的起始地址为（C）。

（A）SA+141（B）SA+144（C）SA+222（D）SA+225

5.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A[4][7]的起始地址为（B）。

（A）SA+141（B）SA+180（C）SA+222（D）SA+225

6.稀疏矩阵一般的压缩存储方法有两种,即（C）。

（A）二维数组和三维数组（B）三元组和散列

（C）三元组和十字链表（D）散列和十字链表

7.若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算,这种观点（B）。

（A）正确（B）错误

8.设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B[1,n（n-1）/2]中,对下三角部分中任一元素ai,j（i<

=j）,在一组数组B的下标位置k的值是（B）。

（A）i（i-1）/2+j-1（B）i（i-1）/2+j（C）i（i+1）/2+j-1（D）i（i+1）/2+j

二、填空题

1.己知二维数组A[m][n]采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOC（A[0][0]）,则A[0][0]的地址是__loc（A[0][0]）+（n*i+j）*k__。

2.二维数组A[10][20]采用列序为主方式存储,每个元素占一个存储单元,并且A[0][0]的存储地址是200,则A[6][12]的地址是__332__。

3.有一个10阶对称矩阵A,采用压缩存储方式（以行序为主,且A[0][0]=1）,则A[8][5]的地址是__42__。

4.设n行n列的下三角矩阵A已压缩到一维数组S[1..n*（n+1）/2]中,若按行序为主存储,则A[i][j]对应的S中的存储位置是__i*（i+1）/2+j+1__。

5.若A是按列序为主序进行存储的4×

6的二维数组,其每个元素占用3个存储单元,并且A[0][0]的存储地址为1000,元素A[1][3]的存储地址为__1039__,该数组共占用___72__个存储单元。

第六章树和二叉树

1.在线索化二叉树中,t所指结点没有左子树的充要条件是（B）

（A）t-〉left==NULL（B）t-〉ltag==1

（C）t-〉ltag=1且t-〉left=NULL（D）以上都不对

2.二叉树按某种顺序线索化后,任一结点均有指向其前趋和后继的线索,这种说法B

（A）正确（B）错误（C）不同情况下答案不确定

3.二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法（A）

4.由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树,这种说法（B）

5.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为（B）。

（A）2h（B）2h-1（C）2h+1（D）h+1

6.已知某二叉树的后序遍历序列是dabec。

中序遍历序列是debac,它的前序遍历序列是（D）。

（A）acbed（B）decab（C）deabc（D）cedba

7.如果T2是由有序树T转换而来的二叉树,那么T中结点的前序就是T2中结点的（A）

（A）前序（B）中序（C）后序（D）层次序

8.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是（D）。

（A）bdgcefha（B）gdbecfha（C）bdgaechf（D）gdbehfca

9.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。

这种说法（B）

（A）正确（B）错误（C）不同情况下答案不确定

10.按照二叉树的定义,具有3个结点的二叉树有（C）种。

（A）3（B）4（C）5（D）6

11.在一非空二叉树的中序遍历序列中,根结点的右边（A）

（A）只有右子树上的所有结点（B）只有右子树上的部分结点

（C）只有左子树上的部分结点（D）只有左子树上的所有结点

12.树最适合用来表示（C）。

（A）有序数据元素（B）无序数据元素

（C）元素之间具有分支层次关系的数据（D）元素之间无联系的数据

13.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（A）

（A）不发生改变（B）发生改变（C）不能确定D.以上都不对

14.实现任意二叉树的后序遍历的非递归算法而不使用栈结构,最佳方案是二叉树采用（C）存储结构。

（A）二叉链表（B）广义表存储结构（C）三叉链表（D）顺序存储结构

15.对一个满二叉树,m个树叶,n个结点,深度为h,则（D）

（A）n=h+m（B）h+m=2n（C）m=h-1（D）n=2h-1

16.如果某二叉树的前序为stuwv,中序为uwtvs,那么该二叉树的后序为（C）

（A）uwvts（B）vwuts（C）wuvts（D）wutsv

17.具有五层结点的二叉平衡树至少有（C）个结点。

（A）10（B）12（C）15（D）17

1.二叉树中任何一个结点的度都是2。

）

2.由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树。

3.一棵哈夫曼树中不存在度为1的结点。

（√）

4.平衡二叉排序树上任何一个结点的左、右子树的高度之差的绝对值不大于2（√）

1.指出树和二叉树的三个主要差别__树的结点个数至少为1，而二叉树的结点个数可以为0__,__树种结点的最大读书没有限制，而二叉树结点的最大度数不能超过2__,__树的结点无左右之分，而二叉树的结点有左右之分__。

2.从概念上讲,树与二叉树是两种不同的数据结构,将树转化为二叉树的基本目的是___树可采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题___

3.若结点A有三个兄弟（包括A本身）,并且B是A的双亲结点,B的度是___4___

4.若一棵具有n个结点的二叉树采用标准链接存储结构,那么该二叉树所有结点共有__n+1__个空指针域。

5.已知二叉树的前序序列为ABDEGCFHIJ,中序序列为DBGEAHFIJC,写出后序序列__DGEBHJIFCA__。

6.已知二叉树的后序序列为FGDBHECA,中序序列为BFDGAEHC,并写出前序序列___ABDEGCEH___。

7.找出满足下列条件的二叉树

1）先序和中序遍历，得到的结点访问顺序一样。

____无左子树____

2）后序和中序遍历，得到的结点访问顺序一样。

_____无右子树____

3）先序和后序遍历，得到的结点访问顺序一样。

____仅一个结点的二叉树___

8.一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各是多少？

__最大n,最小┕log2n┙+1__

9.一棵二叉树有67个结点，这些结点的度要么是0，要么是2。

这棵二叉树中度为2的结点有____22____个。

10.含有100个结点的树有______99______条边。

第七章图

一、判断题

1.一个无向图的邻接矩阵中各非零元素之和与图中边的条数相等。

2.一个有向图的邻接矩阵中各非零元素之和与图中边的条数相等。

3.一个对称矩阵一定对应着一个无向图。

4.一个有向图的邻接矩阵一定是一个非对称矩阵。

二、选择题

1.在一个图中,所有顶点的度数之和等于所有边数的（C）倍。

（A）1/2（B）1（C）2（D）4

2.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的（B）倍。

3.一个有n个顶点的无向图最多有（C）条边。

（A）n（B）n（n-1）（C）n（n-1）/2（D）2n

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

（A）6（B）12（C）16（D）20

5.具有6个顶点的无向图至少应有（A）条边才能确保是一个连通图。

（A）5（B）6（C）7（D）8

6.在一个具有n个顶点的无向图中,要连通全部顶点至少需要（C）条边。

（A）n（B）n+1（C）n-1（D）n/2

7.对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小（B）

（A）n（B）（n-1）2（C）n-1（D）n2

8.对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为（A），所有邻接表中的结点总数是（C）。

①（A）n（B）n+1（C）n-1（D）n+e

②（A）e/2（B）e（C）2e（D）n+e

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

（A）先序遍历（B）中序遍历（C）后序遍历（D）按层遍历

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

11.判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用（D）.

（A）求关键路径的方法（B）求最短路径的Dijkstm方法

（C）宽度优先遍历算法（D）深度优先遍历算法

12.用Prim算法求下列连通的带权图的最小代价生成树，在算法执行的某刻，已选取的顶点集合U＝{1，2，5}，边的集合TE＝{（1，2），（2，5）}，要选取下一条权值最小的边，应当从（B）组中选取。

（A）{（1，4），（3，4），（3，5），（2，5）}

（B）{（5，4），（5，3），（5，6）}　　　

（C）{（1，2），（2，3），（3，5）}　　　

（D）{（3，4），（3，5），（4，5），（1，4）}

1.n个顶点的连通图至少___n-1____条边。

2.在一个无环有向图G中，若存在一条从顶点i到顶点j的弧，则在顶点的拓扑序列中，顶点i与顶点j的先后次序是___i在前，j在后___。

3.在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是___m/24__条。

4.如果从一个顶点出发又回到该顶点，则此路径叫做___回路___。

5.如果从一无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是___强连通图___。

6.若采用邻接表的存储结构，则图的广度优先搜索类似于二叉树的__按层__遍历。

7.一个连通图的生成树是该图的__极大__连通子图。

若这个连通图有n个顶点,则它的生成树有____n-1____条边。

第九章查找

1.用二分查找法对一个顺序表进行查找，这个顺序表可以是按各键值排好序的，也可以是没有按键值排好序的。

）

2.哈希表的查找不用进行关键字的比较。

3.哈希表的定义函数H（key）=key%p（p<

=m）这种方法是直接定址法。

4.装填因子α的值越大，就越不容易发生冲突。

5.选择hash函数的标准为：

随机性好、均匀性好和尽量避免冲突。

1.顺序查找法的平均查找长度为___（n+1）/2__，二分查找法的平均查找长度为__（（n+1）*log2（n+1））/n-1_，分块查找法（以顺序查找确定块）的平均查找长度为__（s2+2s+n）/2s__，分块查找法（以二分查找确定块〉的平均查找长度为__log2（n/s+1）+s/2__，哈希表查找法采用链接法处理冲突时的平均查找长度为__1+α__。

2.在各种查找方法中,平均查找长度与结点个数n无关的查法方法是__哈希表查找__

3.二分查找的存储结构仅限于___顺序__,且是___有序的__。