数据结构期末考试题

千里之行，始于足下让知识带有温度。第第2页/共2页精品文档推荐数据结构期末考试题

一、推断题：（共10分，每题1分）

1.挨次表和一维数组一样，都可以按下标随机（或直接）拜访。（）

2.数据的规律结构是指各数据元素之间的规律关系，是用户按照应用需要建立的。（）

3.惟独用面对对象的计算机语言才干描述数据结构算法。（）

4.在对双向循环链表做删除一个结点操作时，应先将被删除结点的前驱结点和后继结点链

接好再执行删除结点操作。（）

5.递归的算法容易、易懂、简单编写，而且执行效率也高。（）

6.在AOE网络中一定惟独一条关键路径。（）

7.二叉树是一棵无序树。（）

8.在任何状况下，迅速排序需要举行关键码比较的次数都是O(nlog2n)。（）

9.图的深度优先搜寻是一种典型的回溯搜寻的例子，可以通过递归算法求解。（）

10.当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把

它逐层向下调节，直到调节到合适位置为止。（）

二、填空题（20分，每题2分）

1.假定一棵二叉树的结点个数为32，则它的最小深度为______。

2.在一棵二叉树中，度为2的结点有5个，度为1的结点有6个，那么叶子结点有______

个。

3.一棵深度为5的满二叉树的结点总数为______个。

4.假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则结点H的双亲结点为

______。

5.对于一个具有n个顶点的图，若采纳邻接矩阵表示，则矩阵大小为______。

6.若要对某二叉排序树举行遍历，保证输出元素的值序列按增序罗列，应对该二叉排

序树采纳____________遍历法。

7.元素关键字转换为该元素存储位置的函数f称为____________。

8.每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序办法叫

做____________排序。

9.假定一组数据的关键字为{46,79,56,38,40,84}，则利用堆排序办法建立的初始大

顶堆为__________________。

10.对20个记录举行归并排序时，共需要举行______趟归并。

三、挑选题（共20分，每题2分）

1.树中全部结点的度数之和等于结点总数加______。

A.0

B.1

C.-1

D.2

2.在一棵树中，每个结点最多有______个直接前驱结点。

A.0

B.1

C.2

D.随意多个

3.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加______。

A.2

B.1

C.0

D.-1

4.顶点个数为n的无向图最多有______条边。

A.n-1

B.n(n-1)/2

C.n(n+1)/2

D.n(n-1)

5.n个顶点的连通图至少有______条边。

A.n-1

B.n

C.n+1

D.0

6.在一个无向图中，全部顶点的度数之和等于全部边数的______倍。

A.3

B.2

C.1

D.1/2

7.对于挨次存储的有序表(5,12,20,26,37,42,46,50,64)，为查找元素26，若采

用挨次查找，需要比较______次才干查找胜利。

A.3

B.4

C.5

D.6

班

级

：

专

业

：

姓

密

封

8.设哈希表长为14，哈希函数f（k）=k％11，已知表中已有4个元素，关键字分离为15，

38，61，84，存储位置分离为4，5，6，7，其它存储位置为空，如用二次探测再散列处理矛盾，关键字为49的存储位置是______。

A.8

B.3

C.5

D.9

9.在对n个元素举行容易挑选排序的过程中，需要举行______趟挑选和交换。

A.n/2

B.n-1

C.n

D.n+1

10.在对n个元素举行迅速排序的过程中，第一趟排序最多需要交换______对元素。

A.n/2

B.n-1

C.n

D.n+1

四、应用题（共30分，每题6分）

1.已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，…，nk个度为k

的结点，问该树有多少个叶子结点？（6分）

2.对于下面两个图，求出：

（1）无向图中每个顶点的度，有向图中每个顶点的入度，出度和度。（2）是否是连通图/强连通图，假如不是，画出连通重量/强连通重量。（6分）

3.分离画出在线性表(a,b,c,d,e,f,g)中举行折半查找，以查关键字等于e、f

和g的过程。（6分）

4.已知一组元素的关键字{46,74,16,53,14,26,40,38,86,65,27,34}，利用直接插入

排序法，写出每次向前面的有序表插入一个元素后的罗列结果。（6分）

5、将下图转换为二叉树，对转换后的二叉树举行先序、中序、后序遍历序列。（6分）

五、程序题（20分）

1.将下面算法填完整。（10分，每空2分）

intSearch_Bin(SSTableST,KeyTypekey){

//在有序表ST中折半查找其关键字等于key的数据元素，若找到，则返回该元素//在表中的位置，否则返回0

low=1;high=ST.length;

while(low<=high){

mid=____________;

if(EQ(key,ST.elem[mid].key))return____________;

elseif(LT(key,ST.elem[mid].key))high=____________;

elselow=____________;

}

return____________;

}

2.将下面算法填完整。（10分，每空2分）

voidInsertSort(SqListi<=L.length;++i)

if(LT(L.r[i].key,L.r[i-1].key)){

L.r[0]=____________;

L.r[i]=____________;

for(j=____________;LT(L.r[0].key,L.r[j].key);--j)

L.r[j+1]=____________;

L.r[j+1]=____________;

}

}

班

级：

专业：姓

信息技术学院2022-2022学年其次学期期末考试

数据结构试卷2（适用班级：）

（答题时光：120分钟，满分：100分）

一、推断题（10分，每题1分）

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

2.算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。（）

3.挨次表和一维数组一样，都可以按下标随机（或直接）拜访。（）

4.链式栈与挨次栈相比,一个显然的优点是通常不会浮现栈满的状况。（）

5.一个广义表((a),((b),c),(((d))))的长度为3，深度为4。（）

6.在一棵二叉树中，假定每个结点惟独左子女，没有右子女，对它分离举行中序遍历和后序遍历，则具有相同的结果。（）

7.举行折半搜寻的表必需是挨次存储的有序表。（）

8.用邻接矩阵存储一个图时，在不考虑压缩存储的状况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。（）9.直接挑选排序是一种稳定的排序办法。（）

10.对于AOE网络，加速任一关键活动就能使囫囵工程提前完成。（）

二、填空题（20分，每题2分）

11.假定一棵二叉树的结点个数为32，则它的最大深度为______。

12.在一棵二叉树中，度为2的结点有5个，度为1的结点有6个，那么叶子结点有______

个。

13.一棵深度为5的满二叉树的结点总数为______个。

14.假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则结点H的孩子结点为

______。

15.对于一个具有n个顶点的图，若采纳邻接矩阵表示，则矩阵大小为______。16.若要对某二叉排序树举行遍历，保证输出元素的值序列按增序罗列，应对该二叉排

序树采纳____________遍历法。

17.元素关键字转换为该元素存储位置的函数f称为____________。

18.先将囫囵待排序列分割成若干子序列分离举行直接插入排序，待囫囵序列“基本有

序”时，再对全体举行一次直接插入排序，此种排序办法叫做____________排序。19.假定一组数据的关键字为{46,79,56,38,40,84}，则利用堆排序办法建立的初始小

顶堆为__________________。

20.假定一组数据的关键字为{46,79,56,38,40,84}，则以第一个记录为枢轴，对其进

行第一趟迅速排序的结果为__________________。

三、挑选题（20分，每题2分）

11.在一棵具有n个结点的二叉树中，全部结点的空子树个数等于______。A.nB.n-1C.n+1D.2*n

12.在一棵二叉树的第5层上，最多具有______个结点。A.14B.16C.31D.32

13.在一棵深度为h的彻低二叉树中，所含结点个数不少于______。A.2hB.2h+1C.2h-1D.2h-1

14.有向图的一个顶点的度为该顶点的______。

A.入度

B.出度

C.入度与出度之和

D.(入度＋出度)/215.一个连通图的生成树是包含图中全部顶点的一个______子图。A.微小B.连通C.微小连通D.无环

16.具有e条边无向图，它的邻接表中有______个边结点。A.e-1B.eC.2(e-1)D.2e

密

封

17.长度为m的哈希表，采纳线性探测再散列处理矛盾，假定对一个元素第一次计算的存储

地址为d，则下一次的存储地址为______。

A.d

B.d+1

C.(d+1)/m

D.(d+1)%m

18.适于对动态查找表举行高效率查找的组织结构是______。

A.有序表

B.挨次表

C.二叉排序树

D.链表

19.在对n个元素举行容易挑选排序的过程中，需要举行______趟挑选和交换。

A.n/2

B.n-1

C.n

D.n+1

20.若对n个元素举行直接插入排序，在举行i趟(2≤i≤n)排序时，为寻觅插入位置最多

需要举行______次元素的比较。

A.i+1

B.i-1

C.i

D.1

三、应用题（30分，每题6分）

1.写出下图所示二叉树的先序、中序、后序序列。（6分）

先序序列：

中序序列：

后序序列：

2.对于下面两个图，求出：（3）无向图中每个顶点的度，有向图中每个顶点的入度，出度和度。（4）每个图的邻接矩阵。（6分）

3.已知一组关键字{26,38,12,45,73,64,30,56}

1)试依次插入关键字生成一棵二叉排序树

2)画出分离删除38和73后树的结构（6分）

4.已知一组元素的关键字{46,74,16,53,14,26,40,38,86,65,27,34}，利用起泡排序法，

写出每趟排序后的罗列结果。（6分）

5、什么是赫夫曼（Huffman）树？有一组数值14、21、32、15、28，画出赫夫曼树，并计算其WPL。（6分）四、程序题（20分）

3.将下面算法填完整。（10分，每空2分）

intSearch_Bin(SSTableST,KeyTypekey){