数据结构考试题目及答案.pdfVIP

数据结构考试题⽬及答案

数据结构试题6

⼀、单项选择题（每⼩题3分，共30分）

1．设栈的输⼊序列是1、2、3、4，则______不可能是其出栈序列。()

[A]1234[B]2134[C]1432[D]4312

2．在⼀个具有n个结点的线性链表中查找某个结点，若查找成功，需要平均⽐较_____个结点。()

[A]n[B]n/2[C](n+1)/2[D](n-1)/2

3．设每个字符占⼀个字节，⼆维数组A中每个元素有6个字符组成，其⾏下标从0到9，列下标从0到3，元素_____当A按⾏优先存储起始地址与当A按列优先

存储的起始地址相同。()

[A]A[3][0][B]A[3][1][C]A[3][2][D]A[2][3]

4．具有2000个结点的⾮空⼆叉树的最⼩深度为_______。()

[A]9[B]10[C]11[D]12

5．已知某⼆叉树的后根序列是dabec，中根序列是debac，则先根序列是_____。

()

[A]acbed[B]decab[C]deabc[D]cedba

6.⽆向图中所有边的数⽬等于所有顶点的度数之和的_____倍。()

[A]1[B]2[C]1/2[D]不⼀定

7．递归函数F(n)=F(n-1)+n+1(n1)的递归体是_______。()

[A]F(0)=0[B]F(1)=1[C]F(n)=n+1[D]F(n)=F(n-1)+n+1

8.若需要在O(nlog2n)的时间内完成对n个元素的排序，且要求排序是稳定的,

则可选择的排序⽅法是_______。()

[A]快速排序[B]堆排序[C]归并排序[D]直接插⼊排序9．在对n个元素的序列进⾏排序时,堆排序所需要的附加存储空间是__。()

[A]O(1)[B]O(log2n)[C]O(n)[D]O(nlog2n)

10．假定有K个关键字互为同义词，若⽤线性探查法把这K个关键字存⼊散列表中，则总的探查次数⾄少为______。()

[A]K-1[B]K[C]K+1[D]K（K+1）/22

⼆、填空题（每⼩题2分，共20分）

1．对于⼀个长度为n的顺序存储的线性表，在表头插⼊元素的时间复杂度为______，在表尾插⼊元素的时间复杂度为________。

2.在⼀棵⼆叉树中，第5层(根结点为1层)上的结点数最多为____________。

3.⼀棵⾼度为h的理想平衡树中，最少含有______个结点，最多含有________

个结点。

4.在⼀个⼩根堆中，堆顶结点的值是所有结点中的_________，在⼀个⼤根堆中，

堆顶结点的值是所有结点中的_________。

5.在⼀个具有n个顶点的⽆向图中，要连通所有顶点则⾄少需要_________条边。6．假定⼀个图具有n个顶点和e条边，贝采⽤邻接矩阵、邻接表表⽰时，其

相应的空间复杂度分别为__________和___________。

7．以⼆分查找⽅法查找⼀个线性表时，此线性表必须是_________存储的________表。

8．在线性表的散列存储中，处理冲突有___________和___________两种⽅法。9．快速排序在平均情况下的空间复杂度为_____，在最坏情况下的空间复

杂度为_____。

10．在⼀棵20阶B_树中，每个⾮树根结点的关键字数⽬最少为_______个,最多为____。

三、判断题（认为对的，在题后的括号内打“√”，错的打“ⅹ”，每⼩题１分，

共１０）

1．线性表中，每个结点都有⼀个前驱和⼀个后继。（）2．有向图的邻接表和逆邻接表中的结点数⼀定相同。（）3.单链表中要取得某个元素，只要知道该

元素的指针即可，因此单链表是随机

存取的存储结构。（）

4.在快速排序、归并排序和shell排序中，稳定的是shell排序。（）

5.对不同的存储结构，检索的⽅法不同。（）

6.在散列表中，负载因⼦值越⼩则存元素时发⽣冲突的可能性就越⼤。（）

7.由于⼆叉树中每个结点的度最⼤为2，所以⼆叉树是⼀种特殊的树。（）

8.若⼀棵⼆叉树的树叶是某⼦树对称序周游序列中的第⼀个结点，则它必是该

⼦树后序周游序列中的第⼀个结点。（）

9.⼆叉树按线索化后，任⼀结点均有指向其前驱和后继的线索。（）

10.在采⽤线性探查法处理冲突的散列表中，所有同义词在表中相邻。（）

四、简答题（每题10分，共60分）

1．说明数组和链表的区别，各有何优缺点？

2．回答下列关于堆的