数据结构期末刷题去哪里

1. 有什么适合大一计算机专业学生免费的刷题网站

既然大一的同学选择计算机专业，当然少不了刷题啦！但是有很多刷题网站是免费的，同学们想知道吗？下面由我来讲讲吧。

1.力扣

这个网站收录了很多知名互联网公司出的算法题目，相信大一同学很熟悉了，很多同学都在这里刷题，增强对计算机基础知识掌握。它支持多种编程语言，如：Java、Ptthon、Ruby等。最常做的是算法题，目前有一千多道的题目。有专门的图文和视频讲解，方便同学们茶楼补缺。也可以在个人界面查看进展，看自己的学习情况。如果出来工作笔试中，面试官会从这里抽题。刷题过程中全部会了，那么工作没有什么大问题。

以上我列举了三个计算机免费刷题的网站，同学们看到我写的推荐后，来收藏夹吃灰~希望同学们有时间使用这三个网站学习计算机相关知识，提高计算机专业能力，祝你们学有所成！

2. 如何学好数据结构，去哪里刷题

https://leetcode.com/
很多企业的笔试和面试的数据结构&算法题是从这里面找的。

3. 萌新想问一下大佬关于数据结构刷题的书有什么好的可以推荐吗像高数同济大学出版社那种经典的有吗

c语言的刷题用清华大学出版社严蔚敏版（我们教材就是这个，讲的不错）配套的题集书就可以了，应该有单卖的《数据结构题集（C语言版）》

4. 如何学习数据结构

• 学好数据结构首先学好C语言指针，数据机构内在串联全靠指针作用，指针主要难在本身是带地址的变量，再加上指针的指针串联导致很多人误解，先要学会理解，要对计算机的内存结构有个大概了解，对一些常见的进制之间的转化以及字节对齐等有行程基本的认知。

• 理解概念，建立抽象模型，比如简单的队列，先进先出模式，在设计数据模型的时候，就需要有一个对头和队尾的概念，数据需要从队尾插入队头出来，基本上三个属性就出来了，一个对头指针，一个队尾指针，一个结构体数值，常见的方法有删除清空队列，有插入队列操作，出队操作，创建初始队列操作等等，这样子抽象数据模型，形成自己的思维理解，然后再进行代码设计。

• 需要变通实践，代码调试变通，数据结构的组合无穷变着写代码。算法的奥妙就是在于变换，放在数据结构也是这个样子，掌握基本的数据机构算法，在学好数据结构的前提下可以学习下一本经典的算法书《算法导论》这个是算法的经典书籍。

• 学习数据机构不要想着有什么技巧或者方法，把自己调整到最佳的学习状态，方法自然就有了，不要给自己设置什么限制，设置底线只会让自己处在一个围墙之内，学习新东西就是突破自我的一个过程，不要在开始学习的时候给自己过大的压力。

5. 怎么复习数据结构（c++）已学一学期。

要应付期末考试最快捷的方法是找到本校历年试卷然后让班上学得比较好的同学给讲题，大概能搞懂三套题的话基本题型你也了解了，自己的话，花三天时间，即使看不懂也把整本书的知识点整成一个纲要，主要有线性表，这是一种一对一的数据结构，就是一一对应（顺序表、链表）；栈、队列（操作受限的线性表，说白了还是线性表）串和广义表我当初是不考的，这部分要考也考得少；树与二叉树，这是一种一对多的数据结构（会计算叶子节点什么的，了解这种结构的特点，重点有树的遍历，树与森林的转换，哈夫曼树，二叉排序树）；然后是图，这是一种多对多的数据结构（重点有图的存储表示，图的遍历和最短路径啊关键路径和拓扑排序，按这些内容出的题都涉及算法，最好是自己能读懂算法然后按照算法操作，如果不行就学会做题，明白一种题怎么做）；接下来是查找，重点是二分查找，哈希表，特别是哈希，仔细看的话你会发现这章挺有意思的；最后就是排序，重点掌握各种排序方法的实现，比较好的方法是从网上找到一些算法执行的动态演示图，效果相当好。说实话，当年学DS也是大白，最后渐渐明白就是通过狂做练习。对于算法题，这不是速成的，无法提供好的解决方案，见谅。

6. 哪里有数据结构期末考题

（三）简答题
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

7. 谁有数据结构的期末试题，借我参考下马上考试了

A：

06－07第一学期期末考试试卷

试卷代码：03266A 授课课时：112
课程名称：数据结构与算法 适用对象：本科

一、单项选择题(从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共24分。)
1.数据结构被形式地定义为(K,R)，其中K是数据元素的有限集，R是K上的___有限集。
A.操作 B.映像 C.存储 D.关系
2.线性表若采用链式存储结构时，要求内存中可用存储单元的地址____。
A.必须连续的 B.部分地址必须连续的 C.一定是不续的 D.连续不连续都可以
3.一个栈的入栈序列是a、b、c、d、e，则栈的不可能输出序列是____。
A.edcba B.decba C.dceab D.abcde
4.一个队列的入队序列是1、2、3、4，则队列输出序列是____。
A.4、3、2、1 B.1、2、3、4 C.1、4、3、2 D.3、2、4、1
5.栈和队列的共同点是____。
A.都是先进后出 B.都是先进先出
C.只允许在端点处插入、删除元素 D.没有共同点
6.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行____。
A. s->next = p->next; p->next=s; B. p->next = s->next; s->next = p;
C. q->next = s; s->next = p; D. p->next = s; s->next = q;
7.设串s1=‘ABCDEFG’，s2=‘PQRST’，函数con (x, y) 返回x与y串的连接串，函数subs (s, i, j) 返回串s的从序号i的字符开始的j个字符组成的子串，函数len (s) 返回串s的长度，则con (subs (s1, 2, len (s2)), subs (s1, len (s2), 2)) 的结果串是____。
A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF
8.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____。
A. 2h B. 2h-1 C. 2h +1 D. h +1
9.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历结点访问顺序是dgbaechf，则其后序遍历结点访问顺序是____。
A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca
10.具有6个顶点的无向图至少应有____条边才能确保是一个连通图。
A. 5 B. 6 C. 7 D. 8
11.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为–。
A. n B. n/2 C. (n+1)/2 D. (n-1)/2
12.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列(注：初始时为空)的一端的方法，称为____。
A. 希尔排序 B. 归并排序 C. 插入排序 D. 选择排序
二、填空题(请在每小题的横线上填入正确内容，每空1分，共7分。)
1.在树形结构中，树根结点没有 结点，其余每个结点有且只有 个前驱结点。
2.对n个元素的序列进行起泡排序时，最少的比较次数是 。
3.空串是 ，其长度等于0。
4.一棵有n个结点的满二叉树共有 个叶子结点。
5.在散列函数H(key)=key % p中，p应取 。
6.已知模式串t=‘abcaabbabc’， 其用KMP法求得的每个字符对应的next函数值为 。
三、简答题(本大题共3小题，每小题5分，共15分)
1.在对线性表的处理中一般使用两种存储结构，顺序存储结构和链式存储结构。试叙述在什么情况下使用顺序表比链表好？
2.简述什么是稳定的排序，什么是不稳定的排序。
3.下列中缀表达式对应的后缀形式是什么？
(1) (A + B) * D + E / (F + A * D) + C
(2) A && B|| ! (E > F) {注：按C的优先级)
四、判断题(本大题共10小题，命题正确的在题后括号内写 “T”，错误的在题后括号内写“F”，每小题1分，共10分)
1.数据元素不是数据的最小单位( )。
2.已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。( )
3.AOE网是一种带权的无环连通图。( )
4.对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的( )。
5.一棵树中的叶子数一定等于与其对应的二叉树的叶子数。( )
6.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。( )
7.折半插入排序是稳定的。( )
8.在散列法中，使用双散列函数可保证绝对不产生冲突。( )
9.消除递归不一定需要使用栈( )
10.堆排序是交换排序的一种。( )
五、分析应用题（本题共26分，1、4小题各6分，2、3小题各7分）
1．阅读后分析下面程序段的功能是什么? （6分）
SeqStack S1, S2, tmp;
DataType x; //设栈tmp和S2已做过初始化
while ( ! StackEmpty (S1))
{ x=Pop(S1) ;
Push(tmp,x);
}
while ( ! StackEmpty (tmp) )
{ x=Pop(tmp);
Push( S2, x);
}
2.某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11试设计赫夫曼编码。（7分）
3.设散列表为HT[13], 散列函数为 H (key) = key %13。用线性探测再散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。（7分）
4.设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试写出使用希尔排序(增量为5,2,1)方法每趟排序后的结果。（6分）
六、算法设计题（本题共18分，第1小题10分，第2小题8分）
1.编写一个算法frequency，统计在一个输入字符串中所含各个不同字符出现的频度。用适当的测试数据来验证这个算法。(10分)
2.在一棵以二叉链表表示的二叉树上，试写出用按层次顺序遍历二叉树的方法，并统计树中具有度为1的结点数目的算法。要求给出二叉链表的类型定义。(8分)

答案：

06－07第一学期
期末考试参考答案与评分标准

试卷代码：03266A 授课课时：112
课程名称：数据结构与算法 适用对象：本科

一、单项选择题(每小题2分，共24分。)
1. D 2. D 3. C 4. B 5. C 6. C
7. D 8. B 9. D 10. A 11. C 12. D
二、填空题(每空1分，共7分。)
1.父(或前驱)， 1
2. n-1
3. 不包含任何字符的串
4. (n+1)/2
5. 素数
6. 0111223123
三、简答题(每小题5分，共15分)
1.答：① 顺序存储时，相邻数据元素的存放地址也相邻(逻辑与物理统一)；要求内存中可用存储单元的地址必须是连续的。
优点：存储密度大，存储空间利用率高。缺点：插入或删除元素时不方便。
②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小(<1)，存储空间利用率低。
顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。
若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；
若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。
2.答：在排序序列中，任何两个相等的关键字Ki=Kj,如果在排序前的序列中Ki领先于Kj，若在排序后的序列中Ki仍领先于Kj，则称所用的排序方法是稳定的；反之，若可能使排序后的序列中Kj领先于Ki，则称所用的排序方法是不稳定的。
3.答：各中缀表达式的后缀形式如下：
(1)AB+D*EFAD*+/+C+
(2)AB&&EF>!||
四、判断题(本大题共10小题，命题正确的在题后括号内写 “T”，错误的在题后括号内写“F”，每小题1分，共10分)
1.T 2.F 3.T 4.F 5.F
6.F 7.T 8.F 9.T 10.F
五、分析应用题（1、4小题各6分，2、3小题各7分）
1．（6分）
答：程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。
2．（7分）
答：为方便起见，设各种字符的权值w={5,29,7,8,14,23,3,11}。因为n=8，所以要构造的赫夫曼树共有m=2n-1=2*8-1=15个结点。生成的赫夫曼树为下图所示：

赫夫曼编码为：概率为0.23的字符编码为：00
概率为0.11的字符编码为：010
概率为0.05的字符编码为：0110
概率为0.03的字符编码为：0111
概率为0.29的字符编码为：10
概率为0.14的字符编码为：110
概率为0.07的字符编码为：1110
概率为0.08的字符编码为：1111
3.（7分）
答：使用散列函数H(key)=key mod 13 有：
H（12）=12， H（23）=10，H（45）=6，H（57）=5，H（20）=7，H（03）=3，H（78）=0，H（31）=5，H（15）=2，H（36）=10
利用线性探查法造表：
0 1 2 3 4 5 6 7 8 9 10 11 12
78 15 03 57 45 20 31 23 36 12
1 1 1 1 1 1 4 1 2 1
搜索成功的平均搜索长度为：
ASL=1/10（1+1+1+1+1+1+4+1+2+1）=14/10
4.（6分）
答： 希尔排序(增量为5,2,1)

六、算法设计题（第1小题10分，第2小题8分）
1. (10分)
include <iostream.h>
include”string.h”
int charnumber=128;
void frequency(string&s,int C[ ]){
for(int i=0;i< charnumber;i++) C[i]=0;
for( i=0;i< s.length();i++) C[atoi(s[i])]++;
for( i=0;i< charnumber;i++)
if(C[i]>0) cout<<”(”<<i<<”):\t”<<C[i]<<”\t”;
}
2. (8分)
类型定义（略）
int Level(BiTree bt) //层次遍历二叉树，并统计度为1的结点的个数
{
int num=0; //num统计度为1的结点的个数
if(bt){
QueueInit(Q); QueueIn(Q,bt)；//Q是以二叉树结点指针为元素的队列
while(!QueueEmpty(Q))
{ p=QueueOut(Q); printf(p->data); //出队,访问结点
if(p->lchild && !p->rchild ||!p->lchild && p->rchild)
num++;//度为1的结点
if(p->lchild) QueueIn(Q,p->lchild); //非空左子女入队
if(p->rchild) QueueIn(Q,p->rchild); //非空右子女入队
}
}
return(num); //返回度为1的结点的个数
}

B：

06－07第一学期期末考试试卷

试卷代码：03266B 授课课时：112
课程名称：数据结构与算法 适用对象：本科

一、单项选择题(从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共24分。)
1.数据结构被形式地定义为 (K, R)，其中K是____的有限集，R是K上的关系有限集。
A.算法 B.数据元素 C.数据操作 D.逻辑结构
2.在数据结构中，从逻辑上可以把数据结构分成____。
A.动态结构和静态结构 B.紧凑结构和非紧凑结构
C.线性结构和非线性结构 D.内部结构和外部结构
3.以下的叙述中，正确的是____。
A.线性表的存储结构优于链式存储结构
B.二维数组是其数据元素为线性表的线性表
C.栈的操作方式是先进先出
D.队列的操作方式是先进后出
4.若一个栈的入栈序列是1、2、3、… 、n，其输出序列为p1、p2、p3、… 、pn，若p1=n，则pi为____。
A. i B. n = i C. n - i +1 D.不确定
5.判断一个循环队列QU (最多元素为m) 为空的条件是____。
A. QU->front == QU->rear B. QU->front != QU->rear
C. QU->front == (QU->rear+1)%m D. QU->front != (QU->rear+1)%m
6.在某单链表中，已知p所指结点不是最后结点，在p之后插入s所指结点，则执行____。
A. s->next = p; p->next=s; B. s->next = p->next; p->next = s;
C. s->next = p->next; p = s; D. p->next = s; s->next = p;
7.串是一种特殊的线性表，其特殊性体现在____。
A.可以顺序存储 B.数据元素是一个字符
C.可以链接存储 D.数据元素可以是多个字符
8.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，前序遍历序列是____。
A. acbed B. decab C. deabc D. cedba
9.对于一个满二叉树，m个树叶，n个结点，深度为h，则____。
A. n = h + m B. h + m = 2n C. m = h-1 D. n = 2h -1
10.一个有n个顶点的无向图最多有____条边。
A. n B. n(n-1) C. n(n-1)/2 D. 2n
11.顺序查找法适合于存储结构为____的线性表。
A. 散列存储 B. 顺序存储或链接存储
C. 压缩存储 D. 索引存储
12.在待排序的元素序列基本有序的前提下，效率最高的排序方法是____。
A. 插入排序 B.选择排序 C.快速排序 D. 归并排序
二、填空题(请在每小题的横线上填入正确内容，每空1分，共7分。)
1.在线性结构中，第一个结点 前驱结点，其余每个结点有且只有1个前驱结点。
2.在无权图G的邻接矩阵中，若A[i][j]等于1，则等于A[j][i] = 。
3.根据二叉树的定义，具有三个结点的二叉树有 种不同的形态。
4.空格串是指 ，其长度等于 。
5.在散列存储中，装填因子α的值越大，则存储元素时发生冲突的可能性就 。
6.已知模式串t= ‘abacabaaad’， 其用KMP法求得的每个字符对应的next函数值为 。
三、简答题(本大题共3小题，每小题5分，共15分)
1.比较静态查找与动态查找的主要区别，它们的基本运算有哪些不同？
2.逻辑结构分哪几种，存储结构有哪几种？
3.在具有n(n>1)个结点的各棵不同形态树中，其中深度最小的那棵树的深度是多少？它共有多少叶子和非叶子结点？
四、判断题(本大题共10小题，命题正确的在题后括号内写 “T”，错误的在题后括号内写“F”，每小题1分，共10分)
1.每种数据结构都应具备三种基本运算：插入、删除、搜索( )。
2.满二叉树不一定是完全二叉树。( )
3.带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。( )
4.任一棵二叉搜索树的平均搜索时间都小于用顺序搜索法搜索同样结点的顺序表的平均搜索时间。( )
5.线性链表中所有结点的类型必须相同。( )
6.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关( )。
7.在散列法中解决冲突时，其装载因子的取值一定在(0，1)之间。( )
8.任何一个关键活动延迟，那么整个工程将会延迟。( )
9.平衡二叉树的左右子树深度之差的绝对值不超过1。( )
10.n个结点的有向图，若它有n(n－1)条边，则它一定是强连通的。( )
五、分析应用题（本题共26分，1、4小题各6分，2、3小题各7分）
1.下述算法的功能是什么? （6分）
LinkList Demo(LinkList L)
{ // L 是无头结点单链表
ListNode *Q,*P;
if(L&&L->next){
Q=L;
L=L->next;
P=L;
while (P->next) P=P->next;
P->next=Q; Q->next=NULL;
}
return L;
}
2.将给定的图简化为最小的生成树，要求从顶点1出发。（7分）

3.设散列表为HT[13], 散列函数为 H (key) = key %13。用双散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。再散列函数为 RH (key) = (7*key) % 10 + 1, 寻找下一个地址的公式为 Hi = (Hi-1 + RH (key)) % 13, H1 = H (key)。画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。（7分）
4.设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18},写出使用快速排序法每趟排序后的结果。（6分）
六、算法设计题（本题共18分，第1小题10分，第2小题8分）
1.试设计一个实现下述要求的查找运算函数Locate。设有一个带表头结点的双向链表L， 每个结点有4个数据成员：指向前驱结点的指针llink、指向后继结点的指针rlink，存放字符数据的成员data和访问频度freq。所有结点的freq 初始时都为0。每当在链表上进行一次Locate(L, x) 操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。(10分)
2.设一棵二叉树以二叉链表为存贮结构，设计一个算法将二叉树中所有结点的左，右子树相互交换。要求给出二叉链表的类型定义。(8分)

答案：

06－07第一学期
期末考试参考答案与评分标准

试卷代码：03266B 授课课时：112
课程名称：数据结构与算法 适用对象：本科

一、单项选择题(每小题2分，共24分。)
1. B 2. C 3. B 4. C 5. A 6. B
7. B 8. D 9. D 10.C 11. B 12. A
二、填空题(每空1分，共7分。)
1. 无
2. 1
3. 5
4. 串中字符全为空格 ， 空格的个数
5. 大
6. 0112123422 。
三、简答题(本大题共5小题，每小题5分，共15分)
1．答：两种查找方法最大的区别在于：
静态查找方法不修改查找表；动态查找在查找不成功时，将结点插入查找表中，即有可能修改查找表；
静态查找的基本运算有建表、查找和读表元；动态查找除上述基本操作外还有初始化、插入和删除操作；
2.答：根据数据元素之间关系的不同特性，通常有下列四类基本结构：(1)集合；(2)线性结构；(3)树形结构；(4)图状结构或网状结构。有两种不同的存储结构：顺序存储结构和链式存储结构。
3.答：深度最小的那棵树的深度为2。对于这n个结点，除了一个根结点之外，其余得n-1个结点均为叶子结点，故其深度为2。该树叶子结点数为n-1，非叶子结点数为1。

四、判断题(每小题1分，共10分)
1. (T) 2. (F) 3. (T) 4. (F) 5. (T)
6. (T) 7. (F) 8. (T) 9. (T ) 10.(T)

五、分析应用题（本题共26分，1、4小题各6分，2、3小题各7分）
1.（6分）
答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。
2.（7分）
答:

3.（7分）
答：使用散列函数H(key)=key mod 13 有：
H（12）=12， H（23）=10，H（45）=6，H（57）=5，H（20）=7，H（03）=3，H（78）=0，H（31）=5，H（15）=2，H（36）=10
利用双散列法造表：Hi =（Hi-1+RH(key)）%13, Hi =H(key)

0 1 2 3 4 5 6 7 8 9 10 11 12
78 15 03 57 45 20 31 36 23 12
1 1 1 1 1 1 3 5 1 1
搜索成功的平均搜索长度为：ASL =1/10（1+1+1+1+1+1+3+5+1+1）=16/10
4.（6分）
答：
六、算法设计题（第1小题10分，第2小题8分）
1.(10分)
答：
(1) 定义链表结构
struct DoubleListNode {
char data ;
int freq;
DoubleListNode * llink, *rlink ;
};
初始时，所有结点的freq域的值都为0。
(2) 定义函数
DoubleListNode * locate ( DoubleListNode *f ; char &x ) {
DoubleListNode * p, *q;
p = f→rlink; /*跳过表头结点*/
while ( p != NULL && p→data != x ) p = p→rlink; /*搜索*/
if ( p ) {
p→freq ++; q = p→llink;
p→rlink→llink = q; q→rlink = p→rlink; /*从链中摘下p*/
while ( q != f &&q→freq < p→freq ) q =q→llink;
p→llink = q;
p→rlink = q→rlink; q→rlink→llink = p;
q→rlink = p; /*在q后面插入p*/
}
return p;
}
2． (8分)
答：类型定义（略）
void exchange(BiTree bt)//将二叉树bt所有结点的左右子树交换
{
if(bt)
{ BiTree s；
s=bt->lchild; bt->lchild=bt->rchild; bt->rchild=s; //左右子女交换
exchange(bt->lchild); //交换左子树上所有结点的左右子树
exchange(bt->rchild); //交换右子树上所有结点的左右子树
}
}

8. 如何学好数据结构，去哪里刷题

推荐 1.算法与数据结构考研试题精析(不一定需要考研才能做) 2.数据结构高分笔记 以上也是我自己考试使用的参考资料

9. 如何学好数据结构，去哪里刷题

大数据学习。柠檬学院大数据，注册就可以学习了，还有大数据的基础课程，java，linux，mysql。