哪里有数据结构期末考题?
发布网友
发布时间：2022-04-23 08:43
共2个回答
热心网友
时间：2022-06-18 12:28
1．简述顺序存储结构和链式存储结构的特点
答：顺序存储结构的优点无需为表示元素间的逻辑关系而增加额外的指针空间；可以随机存取表中的任一元素。缺点是必须事先进行空间分配，表的容量难以扩充；插入和删除操作时需移动大量结点，效率较低。
链式存储结构的优点是结点的存储采用动态存储，表的容量很容易扩充；插入和删除操作方便，不必移动结点，只要修改结点中的指针即可。缺点是每个结点中需要有指针空间，比顺序存储结构的存储密度小；只能进行顺序查找结点。
2．链表中为何要引入头结点？
答：链表进行插入和删除操作时要判断是否在链表的首端操作，若在第一结点前插入新结点和删除第一个结点则会引起首指针head值的改变；否则head的值不会改变。在链表前加一个头结点（只用指针域指向链表的首结点）就避免了两种情况的判断，使程序设计简单了，程序的结构更清楚。
2． 简述由二叉树的前序、中序和后序遍历序列确定二叉树
答：在三种遍历序列中，前序序列和中序序列、中序序列和后序序列能唯一确定一棵二叉树，因为前序序列或后序序列能确定二叉树的根结点而中序序列能确定根的左、右子树。前序序列和后序序列不能唯一确定一棵二叉树，但注意树的先根序列和后根序列能唯一的确定该树，因为树的后根序列就是二叉树的中序序列。
4．快速排序最坏情况的改进
答：当待排序的序列为有序序列时快速排序的效率很低，蜕变为冒泡排序了，为了避免这种情况，选序列的首元素为枢轴元素（或称基准元素）改为选序列的首元素、中间元素和末元素三个元素中中间大的元素为基准元素（简单的就用中间元素为基准），这可大大改善快速排序的性能。例如：
8，0，4，9，6，3，5，2，7，1
以中间大元素6为基准，基准元素与最后元素交换后为：
8，0，4，9，1，3，5，2，7，6
↑ ↑
i j
将i,j指的内容比较，若i的内容比基准小，i推进，否则i停下，开始进行j的比较；若j的内容比基准大，j推进,，否则j停下，将i的内容与j的内容交换，重复上述过程，直至j<I< SPAN>止，将基准与i的内容交换，一次分段完成。,如下所示：
8，0，4，9，1，3，5，2，7，6
2，0，4，9，1，3，5，8，7，6
2，0，4，5，1，3，9，8，7，6
2，0，4，5，1，3，6，8，7，9
5．简述动态规划法的基本思想
答：为了节约重复求相同子问题的时间，引入一个表（数组），不管它们是否对最终解有用，把新的子问题的解答存于该表中，待以后遇到同样子问题时，就不再重复求该子问题，而直接从表中取出该子问题的解答，这就是动态规划法所采用的基本思想。
（四）选择题
1．循环队列用数组A[0…m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是 。
A．(rear-front+m)% m B．read-front+1
C．read-front-1 D．read-front
n 参* A
2．递归算法的执行过程一般来说，可分成 (1) 和 (2) 两个阶段。
(1)A．试探 B．递推 C．枚举 D．分析
(2)A．回溯 B．回归 C．返回 D．合成
n 参* (1) B (2) B
3．设哈希表长m=11，哈希函数H（key）=key%11。表中已有4个结点：addr（15）=4， addr（38）=5，addr（61）=6，addr（84）=7，其余地址为空，如果二次探测再散列处理冲突，关键字为49的结点地址是 。
A．8 B．3 C．5 D．9
n 参* D
4．m阶B-树中所有非终端（除根之外）节点中的关键字个数必须大于或等于 。
A． －1 B． +1 C． －1 D．m
n 参* C
5．一组记录的关键码为（46，79，56，38，40，84），则采用快速排序的方法，以第一个记录为基准得到的一次划分结果为 。
A．38，40，46，56，79，84 B．40，38，46，79，56，84
C．40，38，46，56，79，84 D．40，38，46，84，56，79
n 参* C
6．若一个问题的求解既可以用递归算法，也可以用递推算法，则往往用 (1) 算法，因为 (2) 。
（1）A．先递归后递推 B．先递推后递归 C．递归 D．递推
（2）A．递推的效率比递归高 B．递归宜于问题分解
C．递归的效率比递推高 D．递推宜于问题分解
n 参* （1）D （2）A
7．将一棵有100节点的完全二叉树从上到下、从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为 。
A． 99 B．98 C．50 D．48
n 参* B
8．二叉树在线索化后，仍不能有效求解的问题是 。
A．前序线索二叉树中求前序后继 B．中序线索二叉树中求中序后继
C．中序线索二叉树中求中序前趋 D．后序线索二叉树中求后序后继
n 参* D
9．判断线索二叉树中某结点P有左孩子的条件是 （1） 。若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是 （2） 。
（1）A．P！=null B．P->lchild！=null C．P->ltag=0 D．P->ltag=1
（2）A．根结点无右子树的二叉树 B．根结点无左子树的二叉树
C．根结点可能有左子树和右子树 D．各结点只有一个孩子的二叉树
n 参* （1）C （2）C
10．在一个单链表head中，若要在指针p所指结点后插入一个q指针所指结点，则执行_____。
A． p->next=q->next; q->next=p;
B． q->next=p->next; p=q;
C． p->next=q->next; p->next=q;
D． q->next=p->next; p->next=q;
n 参* D
11．设二维数组a[0…m-1][0…n-1]按列优先顺序存储在首地址为loc(a[0][0])的存储区域中，每个元素占d个单元，则a[i][j]的地址为________。
A． loc(a[0][0]) +(j×n+i) ×d B． loc(a[0][0]) +(j×m+i) ×d
C．loc(a[0][0]) +((j-1)×n+i-1) ×d D． loc(a[0][0]) +((j-1)×m+i-1) ×d
n 参* B
12．如果一个栈的进栈序列是1,2,3,4且规定每个元素的进栈和退栈各一次,那么不可能得到的退栈序列_____。
A 4,3,2,1 B 4,2,1,3 C 1,3,2,4 D 3,4,2,1
n 参* B
13．对n个元素进行快速排序时，最坏情况下的时间复杂度为 。
A．O（log2n） B．O（n） C．O（nlog2n） D．O（n2）
n 参* D
14．任何一个基于“比较”的内部排序的算法，若对6个元素进行排序，则在最坏情况下所需的比较次数至少为 。
A．10 B．11 C ．21 D．36
n 参* A
四、模拟试题
1．二叉树的前序、中序和后序遍历法最适合采用 （1） 来实现。
查找树中，由根结点到所有其它结点的路径长度的总和称为 （2） ，而使上述路径长度总和达到最小的树称为 （3） 。它一定是 （4） 。
在关于树的几个叙述中，只有 （5） 是正确的。
（1）A．递归程序 B．迭代程序 C．队列操作 D．栈操作
（2）A．路径和 B．内部路径长度 C．总深度 D．深度和
（3）A．B-树 B．B+树 C．丰满树 D．穿线树
（4）A．B-树 B．平衡树 C．非平衡树 D．穿线树
（5）A．用指针方式存储有n个结点的二叉树，至少要有n+1个指针
B．m阶B-树中，每个非叶子结点的后件个数≥
C．m阶B-树中，具有k个后件的结点，必含有k-1个键值
D．平衡树一定是丰满树
n 参*（1）A （2）B （3）C （4）B （5）C
2．一棵查找二叉树，其结点A、B、C、D、E、F依次存放在一个起始地址为n（假定地址以字节为单位顺序编号）的连续区域中，每个结点占4个字节：前二个字节存放结点值，后二个字节依次放左指针、右指针。若该查找二叉树的根结点为E，则它的一种可能的前序遍历为 （1） ，相应的层次遍历为 （2） 。在以上两种遍历情况下，结点C的左指针Lc的存放地址为 （3） ，Lc的内容为 （4） 。结点A的右指针Ra的内容为 （5） 。
（1）A．EAFCBD B．EFACDB C．EABCFD D．EACBDF
（2）A．EAFCBD B．EFACDB C．EABCFD D．EACBDF
（3）A．n+9 B．n+10 C．n+12 D．n+13
（4）A．n+4 B．n+8 C．n+12 D．n +16
（5）A．n+4 B．n+8 C．n+12 D．n +16
n 参* （1）D （2）A （3）B （4）A （5）B
3．对于给定的一组关键字（12，2，16，30，8，28，4，10，20，6，18），按照下列算法进行递增排序，写出每种算法第一趟排序后得到的结果：希尔排序（增量为5）得到 （1） ，快速排序（选第一个记录为基准元素）得到 （2） ，基数（基数为10）排序得到 （3） ，二路归并排序得到 （4） ，堆排序得到 （5） 。
（1）A．2,4,6,8,10,12,16,18,20,28,30 B．6,2,10,4,8,12,28,30,20,16,18
C．12,2,10,20,6,18,4,16,30,8,28 D．30,10,20,12,2,4,16,6,8,28,18
（2）A．10,6,18,8,4,2,12,20,16,30,28 B．6,2,10,4,8,12,28,30,20,16,18
C．2,4,6,8,10,12,16,18,20,28,30 D．6,10,8,28,20,18,2,4,12,30,16
（3）A．10,6,18,8,4,2,12,20,16,30,28 B．1,12,10,20,6,18,4,16,30,8,28
C．2,4,6,8,10,12,16,18,20,28,30 D．30,10,20,12,2,4,16,6,8,28,18
（4）A．2,12,16,8,28,30,4,6,10,18,20 B．2,12,16,30,8,28,4,10,6,20,18
C．12,2,16,8,28,30,4,6,10,28,18 D．12,2,10,20,6,18,4,16,30,8,28
（5）A．30,28,20,12,18,16,4,10,2,6,8 B．20,30,28,12,18,4,16,10,2,8,6
C．2,6,4,10,8,28,16,30,20,12,18 D．2,4,10,6,12,28,16,20,8,30,18
n 参* （1）C （2）B （3）D （4）B （5）C
4．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 （1） 。
从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 （2） 。设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用 （3） 排序法。
（1）A．希尔排序 B．起泡排序 C．插入排序 D．选择排序
（2）A．希尔排序 B．起泡排序 C．插入排序 D．选择排序
（3）A．起泡排序 B．快速排序 C．堆排序 D．基数排序
n 参* （1）D （2）C （3）C
5．用某种排序方法对线性表（25,84,21,47,15,27,68,35,20）进行排序时,元素序列的变化情况如下：
①25,84,21,47,15,27,68,35,20 ②20,15,21,25,47,27,68,35,84
③15,20,21,25,35,27,47,68,84 ④15,20,21,25,27,35,47,68,84
则所采用的排序方法是 （1） 。下列（2）中不稳定的排序是 （2） 。
外排序是指 （3） 。
（1）A．选择排序 B．希尔排序 C．归并排序 D．快速排序
（2）A．直接插入排序 B．冒泡排序 C．Shell排序 D．归并排序
（3）A．用机器指令直接对硬盘中需排序数据排序
B． 把需排序数据，用其它大容量机器排序
C． 把外存中需排序数据一次性调入内存，排好序后再存储外存
D．对外存中大于内存允许空间的待排序的数据，通过多次内外间的交换实现排序。
n 参* (1) D (2) C （3）D
6．在内部排序中，通常要对被排序数据进行多次扫描。各种排序方法有不同的排序实施过程和时间复杂性。对给定的整数数列（541,132,984,746,518,181,946,314,205,827）进行从小到大的排序时,采用冒泡排序和简单选择排序时,若先选出大元素,则第一次扫描结果分别是 （1） 采用快速排序（以中间元素518为基准）的第一次扫描结果是 （2） 。
设被排序的序列有n个元素，冒泡排序和简单选择排序的时间复杂度是 （3） ；快速排序的时间复杂度是 （4） 。
（1）
A．(181,132,314,205,541,518,946,827,746,984）和（541,132,827,746,518,181,946,314,205,984）
B．（132,541,746,518,181,946,314,205,827,984）和（541,132,827,746,518,181,946,314,205,984）
C．（205,132,314,181,518,746,946,984,541,827）和（132,541,746,518,181,946,314,205,827,984）
D．(541,132,984,746,827,181,946,314,205,518）和（132,541,746,518,181,946,314,205,827,984）
（2）A．（181,132,314,205,541,518,946,827,746,984）
B．（541,132,827,746,518,181,946,314,205,984）
C．（205,132,314,181,518,746,946,984,541,827）
D．(541,132,984,746,827,181,946,314,205,518）
（3）A．O(nlog2n) B．O(n) C．log2n D．O(n2)
（4）A．O(nlog2n) B．O(n2log2n) C．O(log2n) D．O(n2)
n 参* （1）B （2）C （3）D （4）A
7．结定结点的关键字序列（F、B、J、G、E、A、I、D、C、H），对它按字母的字典顺序进行排列，采用不同方法，其最终结果相同。但中间结果是不同的。
Shell排序的第一趟扫描（步长为5）结果应为 （1） 。
冒泡排序（大数下沉）的第一趟冒泡的效果是 （2） 。
快速排序的第一次扫描结果是 （3）
二路归并排序的第一趟结局是 （4） 。
若以层次序列来建立对应的完全二叉树后，采用筛选法建堆，其第一趟建的堆是 （5） 。
（1）A．（B、F、G、J、A、D、I、E、H、C）
B．（B、F、G、J、A、E、D、I、C、H）
C．（A、B、D、C、E、F、I、J、G、H）
D．（C、B、D、A、E、F、I、G、J、H）
（2）A．（A、B、D、C、F、E、I、J、H、G）
B．（A、B、D、C、E、F、I、H、G、J）
C．（B、F、G、E、A、I、D、C、H、J）
D．（B、F、G、J、A、E、D、I、C、H）
（3）A．（C、B、D、A、F、E、I、J、G、H）
B．（C、B、D、A、E、F、I、G、J、H）
C．（B、A、D、E、F、G、I、J、H、C）
D．（B、C、D、A、E、F、I、J、G、H）
（4）A．（B、F、G、J、A、E、D、I、C、H）
B．（B、A、D、E、F、G、I、J、H、C）
C．（A、B、D、C、E、F、I、J、G、H）
D．（A、B、D、C、F、E、J、I、H、G）
（5）
n 参* （1）C （2）C （3）B （4）A （5）B
8．二叉树 （1） 。在完全二叉树中，若一个结点没有 （2） ，则它必定是叶结点。每棵树都能唯一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子树是N在原树里对应结点的 （3） ，而N的右子树是它在原树里对应结点的 （4） 。二叉排序树的平均检索长度为 （5） 。
（1）A．是特殊的树 B．不是树的特殊形式
C．是两棵树的总称 D．是只有二个根结点的树形结构
（2）A．左子树 B．右子树 C．左子树或没有右子树 D．兄弟
（3）～(4)A．最左子树 B．最右子树 C．最邻近的右兄弟 D．最邻近的左兄弟
（5）A．O(n2) B．O(n) C．O(log2n) D．O(nlog2n)
n 参* （1）B （2）A （3）A （4）C （5）C
9．哈希存储的基本思想是根据 （1） 来决定 （2） ，冲突（碰撞）指的是 （3） ， __(4)___越大，发生冲突的可能性也越大。处理冲突的两种主要方法是 （5） 。
（1）～（2）A．存储地址 B．元素的序号 C．元素个数 D．关键码值
（3） A．两个元素具有相同序号 B．两个元素的关键码值不同，而非码属性相同
C．不同关键码值对应到相同的存储地址 D．数据元素过多
（4） A．非码属性 B．平均检索长度 C．负载因子 D．哈希表空间
（5） A．线性探查法和双散列函数法 B．建溢出区法和不建溢出区法
C．除余法和折叠法 D．拉链法和开放地址法
n 参* （1）D （2）A （3）C （4）C （5）D
10． 设二维数组F的行下标为1至5，列下标为0至8，F的每个数据元素均占4个字节。在按行存储的情况下，已知数据元素F[2，2]的第一个字节的地址是1044，则F[3，4]和F[4，3]的第一个字节的地址分别为 （1） 和 （2） ，而数组的第一个数据元素的第一个字节和数组最后一个元素的最后一个字节的地址分别为 （3） 和 （4） 。
对一般的二维数组G而言，当 （5） 时，其按行存储的G[I，J]的地址与按列存储的G[J，I]的地址相同。
（1）A．1088 B． 1084 C．1092 D．1120
（2）A．1092 B． 1088 C．1120 D．1124
（3）A．1004 B． 1044 C．1000 D．984
（4）A．1183 B． 1179 C．1164 D．1187
（5）A．G的列数与行数相同
B．G的列的上界与G的行的上界相同
C．G的列的上界与G的行的下界相同
D．G的列的上下界与G的行的上下界相同
n 参* （1）A （2）C （3）C （4）B （5）D
11．某顺序存储的表格，其中有90,000个元素，已按关键字递增有序排列，现假定对各个元素进行查找的概率是相同的，并且各个元素的关键字皆不相同。
用顺序查找法查找时，平均比较次数约为 (1) ，最大比较次数为 (2) 。
现把90,000个元素按排列顺序划分成若干组，使每组有g个元素（最后一组可能不足g个）。查找时，先从第一组开始，通过比较各组的最后一个元素的关键字，找到欲查找的元素所在的组，然后再用顺序查找法找到欲查找的元素。在这种查找法中，使总的平均比较次数最小的g是 (3) ，此时的平均比较次数是 (4) 。当g的值大于等于90,000时，此方法的查找速度接近于 (5) 。
(1)～(2) A. 25,000 B. 30,000 C. 45,000 D. 90,000
(3)～(4) A. 100 B. 200 C. 300 D. 400
(5) A. 快速分类法 B. 斐波那契查找法 C. 二分法 D. 顺序查找法
n 参* （1）C （2）D （3）C （4）C （5）D
12．已知无向图的邻接表如图2-35所示：
此邻接表对应的无向图为 (1) 。此图从F开始的深度优先遍历为 （2） 。从F开始的广度优先遍历为 （3） 。从F开始的深度优先生成树为 （4） 。从F开始的广度优先生成树为 （5） 。
（1）
（2）A. F G I L J M K H B. F G I L J K H M
C. F G I L J K M H D. F G H M I L J K
（3）A. F G I L J K M H B. F G H M I L J K
C. F G H I L J K M D. F G H M K I L J
（4）
（5）
n 参* （1）C （2）B （3）B （4）A （5）B
13．图2-36是带权的有向图G的邻接表。以结点V1出发深度遍历图G所得的结点序列为 （1） ；广度遍历图G所得的结点序列为 （2） ；G的一种拓扑序列是 （3） ；从结点V1到V8结点的最短路径是 （4） ；从结点V1到V8结点的关键路径是 （5） 。
（1）A. V1，V2，V3，V4，V5，V6，V7，V8 B. V1，V2，V3，V8，V4，V5，V6，V7
C. V1，V2，V3，V8，V4，V5，V7，V6 D. V1，V2，V3，V8，V5，V7，V4，V6
（2）A. V1，V2，V3，V4，V5，V6，V7，V8 B. V1，V2，V4，V6，V5，V3，V7，V8
C. V1，V2，V4，V6，V3，V5，V7，V8 D. V1，V2，V4，V6，V7，V3，V5，V8
（3）A. V1，V2，V3，V4，V5，V6，V7，V8 B. V1，V2，V4，V6，V5，V3，V7，V8
C. V1，V2，V4，V6，V3，V5，V7，V8 D. V1，V2，V4，V6，V7，V3，V5，V8
(4)～(5)A.( V1，V2，V4，V5，V3，V8) B. (V1，V6，V5，V3，V8)
C.( V1，V6，V7，V8) D. ( V1，V2，V5，V7，V8)
n 参* （1）D （2）C （3）B （4）D （5）B
热心网友
时间：2022-06-18 12:29
