数据结构习题 5概览
第8章查找
8.1选择题
1．顺序查找法适合于存储结构为（）的线性表。
A）散列存储B）顺序存储或链接存储C）压缩存储D）索引存储
2．下面哪些操作不属于静态查找表（）
A）查询某个特定元素是否在表中B）检索某个特定元素的属性
C）插入一个数据元素D）建立一个查找表
3．下面描述不正确的是（）
A）顺序查找对表中元素存放位置无任何要求，当n较大时，效率低。
B）静态查找表中关键字有序时，可用二分查找。
C）分块查找也是一种静态查找表。
D）经常进行插入和删除操作时可以采用二分查找。
4．散列查找时，解决冲突的方法有（）
A）除留余数法B）数字分析法C）直接定址法D）链地址法
5．若表中的记录顺序存放在一个一维数组中，在等概率情况下顺序查找的平均查找长度为（）
A）O（1）B）O(log2n) C）O(n) D）O(n2)
6．对长度为4的顺序表进行查找，若第一个元素的概率为1/8，第二个元素的概率为1/4，第三个元素的概率为3/8，第四个元素的概率为1/4，则查找任一个元素的平均查找长度为（）
A）11/8 B）7/4 C）9/4 D）11/4
7．静态查找表与动态查找表二者的根本差别在于（）
A）它们的逻辑结构不一样B）施加在其上的操作不同
C）所包含的数据元素的类型不一样D）存储实现不一样
8．若查找表中的记录按关键字的大小顺序存放在一个一维数组中，在等概率情况下二分法查找的平均检索长度是（）
A）O(n) B）O(log2n) C）O(nlog2n) D）O((log2n)2)
9．对有14个数据元素的有序表R[14]（假设下标从1开始）进行二分查找，搜索到R[4]的关键码等于给定值，此时元素比较顺序依次为（）。
A）R[1]，R[2]，R[3]，R[4] B）R[1]，R[13]，R[2]，R[3]
C）R[7]，R[3]，R[5]，R[4] D）R[7]，R[4]，R[2]，R[3]
10．设有一个长度为100的已排好序的表，用二分查找进行查找，若查找不成功，至少比较（）次。A）9B）8 C）7 D）6
11．请指出在顺序表{2,5,7,10,14,15,18,23,35,41,52}中，用二分法查找关键码12需做（）次关键码比较。
A）2 B）3 C）4 D）5
12．从具有n 个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为( ) 。
A )O (n) B）O（1）C）O (log 2 n) D）O (n 2 )
13．分块查找时确定块的查找可以用顺序查找，也可以用（），而在块中只能是（）A）静态查找，顺序查找B）二分查找，顺序查找
C）二分查找，二分查找D）散列查找，顺序查找
14．采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（）个结点最佳。
A）10 B）25 C）6 D）625
15．采用分块查找法（块长为s，以二分查找确定块）查找长度为n的线性表时，每个元素的平均查找长度为（）
A）s+n B）log2n＋s/2 C）log2 (n/s+1)+s/2 D）(n+s)/2
16．对一棵二叉排序树根结点而言，左子树中所有结点与右子树中所有结点的关键字大小关系是（）A）小于B）大于C）等于D）不小于
17．若二叉排序树中关键字互不相同，则下面命题中不正确的是（）
A）最小元和最大元一定是叶子 B）最大元必无右孩子
C）最小元必无左孩子D）新结点总是作为叶结点插入二叉排序树
18．设二叉排序树中关键字由1至1000的整数构成，现要查找关键字为363的结点，下述关键字序列（）不可能是在二叉排序树上查找到的序列?
A）2,252,401,398,330, 344,397,363
B）924, 220, 911, 244, 898, 258, 362, 363
C）2, 399, 387, 219, 266, 382, 381, 278, 363
D）925, 202, 911, 240, 912, 245, 363
19．在初始为空的散列表中依次插入关键字序列(MON,TUE,WED,THU,FRI,SAT,SUN),散列函数为H(k)=i MOD 7，其中，i为关键字k的第一个字母在英文字母表中的序号，地址值域为[0:6] ，采用线性再散列法处理冲突。插入后的散列表应该如（）所示。
A）0 1 2 3 4 5 6
THU TUE WED FRI SUN SAT MON
B）0 1 2 3 4 5 6
TUE THU WED FRI SUN SAT MON
C）0 1 2 3 4 5 6
TUE THU WED FRI SAT SUN MON
D）0 1 2 3 4 5 6
TUE THU WED SUN SAT FRI MON
20．若根据查找表建立长度为m 的散列表，采用线性探测法处理冲突，假定对一个元素第一次计算的散列地址为 d ，则下一次的散列地址为( ) 。
A）d B）(d+1)%m C）(d+1)/m D）d+1
21．若根据查找表建立长度为m 的散列表，采用二次探测法处理冲突，假定对一个元素第一次计算的散列地址为 d ，则第四次计算的散列地址为( ) 。
A )(d+1)%m B）(d-1)%m C）(d+4)%m D）(d-4)%m
22．下面有关散列查找的说法中正确的是（）
A）直接定址法所得地址集合和关键字集合的大小不一定相同。
B）除留余数法构造的哈希函数H(key)=key MOD p，其中P必须选择素数。
C）构造哈希函数时不需要考虑记录的查找频率。
D）数字分析法适用于对哈希表中出现的关键字事先知道的情况。
23．下面有关散列冲突解决的说法中不正确的是（）
A）处理冲突即当某关键字得到的哈希地址已经存在时，为其寻找另一个空地址。
B）使用链地址法在链表中插入元素的位置随意，即可以是表头表尾，也可以在中间。
C）二次探测能够保证只要哈希表未填满，总能找到一个不冲突的地址。
D）线性探测能够保证只要哈希表未填满，总能找到一个不冲突的地址。
24．设哈希表长m=14，哈希函数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
8.2填空题
1．在散列函数H(key)=key%p中，p应取_____________。
2．采用分块查找法（块长为s，以顺序查找确定块）查找长度为n的线性表时的平均查找长度为_____________。
3．己知一个有序表为(12,18,20,25,29,32,40,62,83,90,95,98)，当二分查找值为29和90的元素时，分别需要_____________次和_____________次比较才能查找成功；若采用顺序查找时，分别需要_____________次和_____________次比较才能查找成功。
4．从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明_____________ ，若元素的值小于根结点的值，则继续向_____________查找，若元素的值大于根结点的值，则继续向_____________ 查找。
5．二分查找的存储结构仅限于_____________，且是_____________。
6．假设在有序线性表A[1..20]上进行二分查找，则比较一次查找成功的结点数为_____________个，比
较二次查找成功的结点数为_____________ ，比较三次查找成功的结点数为_____________ ，比较四次查找成功的结点数为_____________ ，比较五次查找成功的结点数为_____________，平均查找长度为_____________ 。
7．在对有20个元素的递增有序表作二分查找时，查找长度为5的元素的下标从小到大依次为_____________。（设下标从1开始）
8．对于线性表（70,34,55,23,65,41,20,100）进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为1的元素有_____________个，散列地址为7的元素有_____________ 个。
9．索引顺序表上的查找分两个阶段：_____________、_____________。
10．分块查找中，要得到最好的平均查找长度，应对256个元素的线性查找表分成_____________块，每块的最佳长度是_____________。若每块的长度为8，则等概率下平均查找长度为_____________。
11．_____________是一棵二叉树，如果不为空，则它必须满足下面的条件：
A）若左子树不空，则左子树上所有结点的值均小于根的值。
B）若右子树不空，则右子树上所有结点的值均大于根的值。
C）其左右子树均为二叉排序树。
13．假定有k个关键字互为同义词，若用线性探测法把这些同义词存入散列表中，至少要进行_____________次探测。
8.3应用题
1．设有序表为(a, b, c, d, e, f, g, h, i, j, k, p, q)，请分别画出对给定值a, g和n进行折半查找的过程。2．已知一棵二叉排序树如下：
（1）假如删除关键字28，画出新二叉树。
（2）若查找56，需和哪些关键字比较。
3．已知散列表的地址区间为0～11，散列函数为H(k)=k % 11，采用线性探测法处理冲突，将关键字序列20,30,70,15,8,12,18,63,19依次存储到散列表中，试构造出该散列表，并求出在等概率情况下的平均查找长度。
4．设散列函数为H(k)=k % 11，采用拉链法处理冲突，将上例中关键字序列依次存储到散列表中，并求出在等概率情况下的平均查找长度。
5．假定一个待散列存储的线性表为(32,75,29,63,48,94,25,46,18,70)，散列地址空间为HT[13]，若采用除留余数法构造散列函数和线性探测法处理冲突，试求出每一元素的初始散列地址和最终散列地址，画出最后得到的散列表，求出平均查找长度。
第9章排序
9.1选择题
1．从末排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为（）排序法。
A）插入B）选择C）希尔D）二路归并
2．下面各种排序方法中，最好情况下时间复杂度为O(n)的是（）
A）快速排序B）直接插入排序C）堆排序D）归并排序
3．用某种排序方法对线性表（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
则所采用的排序方法是（）
Ａ）选择排序Ｂ）希尔排序Ｃ）归并排序Ｄ）快速排序
4．下面给出的四种排序法中，（）排序是不稳定排序法。
A）插入B）冒泡C）二路归并D）堆
5．快速排序方法在（）情况下最不利于发挥其长处。
Ａ）要排序的数据量太大
Ｂ）要排序的数据中含有多个相同值
Ｃ）要排序的数据已基本有序
Ｄ）要排序的数据个数为奇数
6．一组记录的关键码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）
Ａ）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
7．对记录的关键码{50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为：50,26,38,80,70,90 ,8,30,40,20
50,8,30,40,20,90,26,38,80,70
26,8,30,40,20,80,50,38,90,70
8,20,26,30,38,40,50,70,80,90
其使用的排序方法是（）
A）快速排序B）基数排序C）希尔排序D）归并排序
8．在文件“局部有序”或文件长度较小的情况下，最佳内部排序方法是（）
A）直接插入排序B）冒泡排序C）简单选择排序D）归并排序
9．在下列算法中，（）算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。
A）堆排序B）冒泡排序C）插入排序D）快速排序
10．设有5000个无序的元素，希望用最快速度挑选出其中前10个最大的元素，在以下的排序方法中，采用（）方法最好
A）快速排序B）堆排序C）基数排序
11．对给出的一组关键字{14，5，19，20，11，19}。若按关键字非递减排序，第一趟排序结果为{14，5，19，20，11，19}，问采用的排序算法是（）
A）简单选择排序B）快速排序C）希尔排序D）二路归并排序
12．以下序列不是堆的是（）
A）100,85,98,77,80,60,82,40,20,10,66
B）100,98,85,82,80,77,66,60,40,20,10
C）10,20,40,60,66,77,80,82,85,98,100
D）100,85,40,77,80,60,66,98,82,10,20
13．下面排序方法中，关键字比较次数与记录的初始排列无关的是（）
A）希尔排序B）冒泡排序C）直接插入排序D）直接选择排序
14．一组记录的关键字为{45，80，55，40，42，85}，则利用堆排序的方法建立的初始堆为（）A）80,45,50,40,42,85
B）85,80,55,40,42, 45
C）85,80,55,45,42,40
D）85,55,80,42,45,40
15．一组记录的关键字为{25，50，15，35，80，85，20，40，36，70}，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果为（）
A）15,25,35,50,20,40,80,85,36,70
B）15,25,35,50,80,20,85,40,70,36
C）15,25,50,35,80,85,20,36,40,70
D）15,25,35,50,80,20,36,40,70,85
16．n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为（）
A）O(1) B）O(log2n) C）O(n2) D）O(n)
17．n个元素进行快速排序的过程中，第一次划分最多需要移动（）次元素(包括开始将基准元素移到临时变量的那一次)。
A）n／2 B）n-1 C）n D）n+l
18．下述几种排序方法中，要求内存量最大的是（）
A）插入排序B）选择排序C）快速排序D）归并排序
19．下面排序方法中，时间复杂度不是O(n2)的是（）
A）直接插入排序B）二路归并排序C）冒泡排序D）直接选择排序
20．对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是序列（）
A）70,75,82,90, 23,16,10,68
B）70,75,68,23,10,16,90,82
C）82,75,70,16,10,90,68,23
D）23,10,16,70,82,75,68,90
9.2填空题
1．当数据量特别大需借助外部存储器对数据进行排序，则这种排序称为_____________。
2．在堆排序、快速排序和归并排序中，若从节省存储空间考虑，则应首先选取_____________方法，其次选取_____________方法；若只从排序结果的稳定性考虑，则应先择_____________方法；若只从平均情况下排序的速度来考虑，则选择_____________方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取_____________方法。
3．对n个元素的序列进行冒泡排序，最少的比较次数是_____________，此时元素的排列情况为_____________，在_____________情况下比较次数最多，其比较次数为_____（4）_ ____。
4．希尔排序是把记录按下标的一定增量分组，对每组记录进行直接插入排序，随着增量_____________，所分成的组包含的记录越来越多，当增量的值为_____________时，整个数组合为一组。
5．直接插入排序需借助的存储单元个数（空间复杂度）为_____________，最好情况下直接插入排序的算法时间复杂度为_____________，最坏情况下该算法的时间复杂度为_____________。
6．对n个数据进行简单选择排序，所需进行的关键字间的比较次数为_____________，时间复杂度为_____________。
7．对于关键字序列(12，13，11，18，60，15，7，20，25，100)，用筛选法建堆，必须从键值为_____________的关键字开始。
8．对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第7个记录60插入到已排序的有序表时，为寻找其插入位置需比较_____________次。
9．若对顺序存储在A[l]～A[9]的记录(76，38，62，53，80，74，83，65，85)进行堆排序，已知除第一个元素76外，以其余元素为根的结点都已是堆，则对第一个元素进行筛运算时，它将最终被筛到A数组下标为_____________的位置上。
10．在时间复杂度为O(log2n)的排序方法中，_____________排序方法是稳定的；在时间复杂度为O(n)的排序方法中，_____________排序方法是不稳定的。
11．设表中元素的初态是按键值递增的，若分别用堆排序、快速排序、冒泡排序和归并排序方法对其仍按递增顺序进行排序，则_____________最省时间，_____________最费时间。
12．从一个无序序列建立一个堆的方法是：首先将要排序的n个键值分放到一棵______________的各个结点中，然后从i=_____________的结点K i开始，逐步把以K i-1、K i-2、…、K1为根的子树排成堆，直到以K l为根的树排成堆，就完成了建堆的过程。
13．在归并排序中，若待排序记录的个数为20，则共需要进行_____________趟归并，在第三趟归并中，是把长度为_____________的有序表归并为长度为_____________的有序表。
9.3应用题
1．设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次排序码比较。
（1）直接插入排序（2）希尔排序（增量为5,2,1）
（3）起泡排序（4）快速排序
（5）基数排序（6）堆排序（7）直接选择排序
2．对一个具有7个记录的文件进行快速排序，请问：
（1）在最好情况下需进行多少次比较？并给出一个最好情况初始排列的实例。
（2）在最坏情况下需进行多少次比较？为什么？并给出此时的实例。
3．如果某个文件经内排序得到80个初始归并段，试问：
（1）若使用多路归并执行3趟完成排序，那么应取的归并路数至少应为多少？
（2）如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过15个，则按多路归并至少需要几趟可以完成排序？如果限定这个趟数，可取的最低路数是多少？
(完整版)数据结构实验报告全集
数据结构实验报告全集 实验一线性表基本操作和简单程序 1 ．实验目的 （1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法； （2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求 （1 ）认真阅读和掌握和本实验相关的教材内容。 （2 ）认真阅读和掌握本章相关内容的程序。 （3 ）上机运行程序。 （4 ）保存和打印出程序的运行结果，并结合程序进行分析。 （5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include
nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"<
数据结构复习题目和答案
《数据结构-C语言版》 第一章绪论 单项选择题 1．在数据结构中，数据的基本单位是_____ ____。 A. 数据项 B. 数据类型 C. 数据元素 D. 数据变量 2．数据结构中数据元素之间的逻辑关系被称为__ ____。 A. 数据的存储结构 B. 数据的基本操作 C. 程序的算法 D. 数据的逻辑结构3．在数据结构中，与所使用计算机无关的是数据的____ ___。 A. 存储结构 B. 逻辑和物理结构 C. 逻辑结构 D. 物理结构4．在链式存储结构中，数据之间的关系是通过____ ____体现的。 A. 数据在内存的相对位置 B. 指示数据元素的指针 C. 数据的存储地址 D. 指针 5．计算算法的时间复杂度是属于一种____ ___。 A. 事前统计的方法 B. 事前分析估算的方法 C. 事后统计的方法 D. 事后分析估算的方法 6．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是____ __。 A. n2 B. nlogn C. n D. logn 7．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为____ ___。 A. O(1) B. O(n) C. O(200n) D. O(nlog2n)
CDCBBDD 第二章线性表 单项选择题 1．链表不具有的特点是____ ____。 A. 可随机访问任一元素 B. 插入和删除时不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与线性表的长度正比 2．设顺序表的每个元素占8个存储单元。第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为。 A. 139 B. 140 C. 147 D. 148 3．在线性链表存储结构下，插入操作算法。 A. 需要判断是否表满 B. 需要判断是否表空 C. 不需要判断表满 D. 需要判断是否表空和表满 4．在一个单链表中，若删除p所指结点的后继结点，则执行。 A. p->next = p->next->next; B. p->next = p->next; C. p = p->next->next; D. p = p->next; p->next = p->next->next; 5．将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为。A. O(n) B. O(1) C. O(m) D. O(m+n) 6．需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是。 A. 单链表 B. 静态链表 C. 线性链表 D. 顺序存储方式ACCABB 填空题 1．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的_____结点。2．在单链表中，指针p所指结点为最后一个结点的条件是。 3．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。4．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动元素的个数是。 5．在长度为n的顺序表中插入一个元素的时间复杂度为。 1前驱 2 p->next==NULL
经典数据结构面试题(含答案)
栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是 __________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________
数据结构第五章习题课课案
1、特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存取的功能?为什么? 答：后者在采用压缩存储后将会失去随机存储的功能。因为在这种矩阵中，非 零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所 在的行、列号作为一个结点存放在一起，这样的结点组成的线性表中叫三元组 表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。 2、二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下 标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的 起始地址与M按列存储时元素（）的起始地址相同。 A、M[2][4] B、M[3][4] C、M[3][5] D、M[4][4] 为第 3、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a 11 的地址为（）。 一元素，其存储地址为1，每个元素占一个地址空间，则a 85 A. 13 B. 33 C. 18 D. 40 4、若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线 （i 数据结构模拟卷(含答案)经典习题 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( ) 1、下图所示的4棵二叉树中，不是完全二叉树的是（） 2、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法（）。 A 、正确 B 、错误 C 、不一定 3、已知某二叉树的后序遍历序列是dabec ，中序遍历序列是debac ，它的前序遍历序列是（）。 A 、acbed B 、decab C 、deabc D 、cedba 4、如果T2是由有序树T 转换而来的二叉树，那么T 中结点的后序就是T2中结点的（）。 A 、前序 B 、中序 C 、后序 D 、层次序 5、深度为5的二叉树至多有（）个结点。 A 、16 B 、32 C 、31 D 、10 6、在一个非空二叉树的中序遍历序列中，根结点的右边（）。 A 、只有右子树上的所有结点 B 、只有右子树上的部分结点 C 、只有左子树上的部分结点 D 、只有左子树上的所有结点 7、树最适合用来表示（）。 A 、有序数据元素 B 、无序数据元素 C 、元素之间具有分支层次关系的数据 D 、元素之间无联系的数据。 8、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。 A 、不发生改变 B 、发生改变 C 、不能确定 D 、以上都不对 9、实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用（）存储结构。 A 、二叉链表 B 、广义表存储结构 C 、三叉链表 D 、顺序存储结构 10、对一个满二叉树，m 个树叶，n 个结点，深度为h ，则（）。 A 、n=m+h B 、h+m=2n C 、m=h-1 D 、n=2h -1 11、设n ，m 为二叉树上的两个结点，在中序遍历时，n 在m 前的条件是（）。 A 、n 在m 右方 B 、n 是m 祖先 C 、n 在m 左方 D 、n 是m 子孙 12．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/- ， A B C D 知识点： 01．绪论 02．顺序表 03．链表 04．栈 05．链队列 06．循环队列 07．串 08．数组的顺序表示 09．稀疏矩阵 10．广义表 11．二叉树的基本概念 12．二叉树遍历、二叉树性质 13．树、树与二叉树的转换 14．赫夫曼树 15．图的定义、图的存储 16．图的遍历 17．图的生成树 18．静态查找（顺序表的查找、有序表的查找） 19．动态查找（二叉排序树、平衡树、B树） 20．哈希查找 21．插入排序（直接插入、折半插入、2路插入、希尔排序）22．选择排序（简单选择、树形选择、堆排序） 23．快速排序、归并排序 101A1（1）．数据的逻辑结构是（A）。 A．数据的组织形式B．数据的存储形式C．数据的表示形式D．数据的实现形式 101A1（2）．组成数据的基本单位是（C）。 A．数据项B．数据类型C．数据元素D．数据变量 101B1（3）．与顺序存储结构相比，链式存储结构的存储密度（B）。 A．大B．小C．相同D．以上都不对 101B2（4）．对于存储同样一组数据元素而言，（D）。 A．顺序存储结构比链接结构多占空间B．在顺序结构中查找元素的速度比在链接结构中查找要快C．与链接结构相比，顺序结构便于安排数据元素D．顺序结构占用整块空间而链接结构不要求整块空间101B2（5）．下面程序的时间复杂度为（B）。 x=0； for（i=1；i 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 1 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位 10. 下列图示的顺序存储结构表示的二叉树是( ) 2 《数据结构》实验报告 实验序号：4 实验项目名称：栈的操作 附源程序清单： 1. #include { return false; } else { st->top++; //移动栈顶位置 st->data[st->top]=x; //元素进栈 } return true; } bool Pop(SqStack *st,ElemType &e) //出栈 { if(st->top==-1) { return false; } else { e=st->data[st->top]; //元素出栈 st->top--; //移动栈顶位置} return true; } //函数名：Pushs //功能：数组入栈 //参数：st栈名,a->数组名，i->数组个数 bool Pushs(SqStack *st,ElemType *a,int i) { int n=0; for(;n 排序算法（19） 1.以单链表为存储结构，写一个直接选择排序算法。 2.设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关 键字之前。请分析算法的时间复杂度。 3.写一个双向冒泡排序的算法，即在排序过程中交替改变扫描方向。 4. 4.下面是一个自上往下扫描的冒泡排序的伪代码算法，它采用lastExchange 来记录每趟扫描中进 行交换的最后一个元素的位置，并以它作为下一趟排序循环终止的控制值。请仿照它写一个自下往上扫描的冒泡排序算法。 void BubbleSort(int A[],int n) //不妨设A[0..n-1]是整型向量 int lastExchange,j,i=n-1; while (i>0) lastExchange=0; for(j=0;j if([j+1] 交换A[j]和A[j+1]; lastExchange=j; } i=lastExchange;//将i置为最后交换的位置 }//endwhile }//BubbleSort 5.改写快速排序算法，要求采用三者取中的方式选择划分的基准记录；若当前被排序的区间长度小于等于3时，无须划分而是直接采用直接插入方式对其排序。 6.对给定的j(1 ≤ j ≤ n ),要求在无序的记录区R[1..n]中找到按关键字自小到大排在第j个位置上的记录(即在无序集合中找到第j个最小元)，试利用快速排序的划分思想编写算法实现上述的查找操作。 7.以单链表为存储结构，写一个直接选择排序算法。 8.写一个heapInsert(R,key)算法，将关键字插入到堆R中去，并保证插入R后仍是堆。提示：应为堆R增加一个长度属性描述(即改写本章定义的SeqList类型描述，使其含有长度域)；将key先插入R 中已有元素的尾部(即原堆的长度加1的位置，插入后堆的长度加1)，然后从下往上调整，使插入的关键字满足性质。请分析算法的时间。 9.写一个建堆算法：从空堆开始，依次读入元素调用上题中堆其中。 10.写一个堆删除算法：HeapDelete(R,i),将R[i]从堆中删去，并分析算法时间，提示：先将R[i]和堆中最后一个元素交换，并将堆长度减1，然后从位置i开始向下调整，使其满足堆性质。 数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #include #define OVERFLOW 0 #define MAXSIZE 100 typedef int ElemType; typedef struct list {ElemType elem[MAXSIZE]; int length; }Sqlist; void Creatlist(Sqlist &L) {int i; printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。 scanf("%d",&L.length); for(i=0;i 课程实验报告课程名称：数据结构 专业班级：信安1302 学号： 姓名： 指导教师： 报告日期：2015. 5. 12 计算机科学与技术学院 目录 1 课程实验概述............ 错误!未定义书签。 2 实验一基于顺序结构的线性表实现 2.1 问题描述 ...................................................... 错误!未定义书签。 2.2 系统设计 ...................................................... 错误!未定义书签。 2.3 系统实现 ...................................................... 错误!未定义书签。 2.4 效率分析 ...................................................... 错误!未定义书签。 3 实验二基于链式结构的线性表实现 3.1 问题描述 ...................................................... 错误!未定义书签。 3.2 系统设计 ...................................................... 错误!未定义书签。 3.3 系统实现 ...................................................... 错误!未定义书签。 3.4 效率分析 ...................................................... 错误!未定义书签。 4 实验三基于二叉链表的二叉树实现 4.1 问题描述 ...................................................... 错误!未定义书签。 4.2 系统设计 ...................................................... 错误!未定义书签。 4.3 系统实现 ...................................................... 错误!未定义书签。 4.4 效率分析 ...................................................... 错误!未定义书签。 5 实验总结与评价 ........... 错误!未定义书签。 1 课程实验概述 这门课是为了让学生了解和熟练应用C语言进行编程和对数据结构进一步深入了解的延续。 第一章绪论 一、选择题 1.D 2.C 3.C 4.B 5.D 6.C 7.D 8.C 9.A 10.D 11.D 12.B 二、填空题 1. 逻辑结构存储结构运算 2. 集合结构线性结构树形结构图状结构 3. 有穷性. 确定性. 可行性. 输入. 输出 4. 顺序存储. 链式存储 5. 数据元素 6. 线性结构非线性结构 三、简答题 1. 尽管算法的含义与程序非常相似，但两者还是有区别的。首先，一个程序不一定满 有穷性，因为它不是一个算法。其次，程序中的指令必须是计算机可以执行的，而 算法中的指令却无此限制。如果一个算法采用机器可执行的语言来书写，那么它就 是一个程序。 2. 数据结构是指数据对象以及该数据对象集合中的数据元素之间的相互关系（数据元 素的组织形式）。例如：队列的逻辑结构是线性表（先进后出）；队列在计算机中 既可以采用顺序存储也可以采用链式存储；队列可进行删除数据元素. 插入数据元 素. 判断是否为空队列，以及队列置空等操作。 3. 数据元素之间的逻辑关系，也称为数据的逻辑结构。数据元素以及它们之间的相互 关系在计算机存储器内的表示（又称映像）称为数据的存储结构，也称数据的物理 结构。 4. 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表 示一个或者多个操作。此外，一个算法还具有下列5个特性： （1）有穷性：一个算法必须在执行有穷步之后结束，即算法必须在有限时间内完 成。 （2）确定性：算法中每一步必须有明确的含义，不会产生二义性。并且，在任何 条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。 （3）可行性：一个算法是能执行的，即算法中的每一步都可以通过已经实现的基 本运算执行有限次得以实现。 （4）输入：一个算法有零个或者多个输入，它们是算法开始时对算法给出的初始 量。 （5）输出：一个算法有一个或者多个输出，它们是与输入有特定关系的量 5. 举例说明四种基本结构的区别: 集合: 数据元素之间无任何关系,如集合A={x,5,t,&}; 线性结构: 数据元素之间存在一个对一个的关系,如线性表L=（2,3，4,5,7,10）； 树形结构: 数据元素之间存在一个对多个的关系,如文件系统目录管理； 图状结构: 数据元素之间存在多个对多个的关系,如教学计划课程安排顺序图。 四. 算法设计题 《数据结构》课程设计题目 (程序实现采用C语言) 题目1：猴子选王（学时：3） 一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。 //链表 #include { pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 } void KickFromRing(RingNodePtr pHead, int n) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == n) { // 踢出环 printf("\n%d", pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; 第一章习题答案 2、××√ 3、（1）包含改变量定义的最小范围 （2）数据抽象、信息隐蔽 （3）数据对象、对象间的关系、一组处理数据的操作 （4）指针类型 （5）集合结构、线性结构、树形结构、图状结构 （6）顺序存储、非顺序存储 （7）一对一、一对多、多对多 （8）一系列的操作 （9）有限性、输入、可行性 4、（1）A（2）C（3）C 5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n） 第二章习题答案 1、（1）一半，插入、删除的位置 （2）顺序和链式，显示，隐式 （3）一定，不一定 （4）头指针，头结点的指针域，其前驱的指针域 2、（1）A（2）A：E、A B：H、L、I、E、A C：F、M D：L、J、A、G或J、A、G （3）D（4）D（5）C（6）A、C 3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。 头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什么都不存。 首元素结点：线性表中的第一个结点成为首元素结点。 4、算法如下： int Linser(SeqList *L,int X) { int i=0,k; if(L->last>=MAXSIZE-1) { printf(“表已满无法插入”)； return(0); } while(i<=L->last&&L->elem[i] L->last++; return(1); } 5、算法如下： #define OK 1 #define ERROR 0 Int LDel(Seqlist *L,int i,int k) { int j; if(i<1||(i+k)>(L->last+2)) { printf(“输入的i，k值不合法”); return ERROR; } if((i+k)==(L->last+2)) { L->last=i-2; ruturn OK; } else {for(j=i+k-1;j<=L->last;j++) elem[j-k]=elem[j]; L->last=L->last-k; return OK; } } 6、算法如下： #define OK 1 #define ERROR 0 Int Delet(LInkList L,int mink,int maxk) { Node *p,*q; p=L; while(p->next!=NULL) p=p->next; if(mink 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << "Please enter two vertexs number of edge: "; cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } } template 1.数据的四种存储结构是( ) A.顺序存储结构、链接存储结构、索引存储结构和散列存储结构 B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构 C.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构 D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构 2.若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少， 下列选项中，应选择的存储结构是( ) A.无头结点的单向链表 B.带头结点的单向链表 C.带头结点的双循环链表 D.带头结点的单循环链表 3.若带头结点的单链表的头指针为head，则判断链表是否为空的条件是( ) A.head=NULL B.head->next=NULL C.head!=NULL D.head->next!=head 7.若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是( ) A.树中没有度为2的结点 B.树中只有一个根结点 C.树中非叶结点均只有左子树 D.树中非叶结点均只有右子树 8.若根结点的层数为1，则具有n个结点的二叉树的最大高度是( ) A.n B. C. +1 D.n/2 9.在图G中求最小生成树可以采用的算法是( ) A.迪杰斯特拉（Dijkstra）算法 B.克鲁斯卡尔（Kruskal）算法 C.深度优先遍历(DFS)算法 D.广度优先遍历(BFS)算法 10.下图G=(V,E)是一个带权连通图，G的最小生成树的权为( ) A.15 B.16 C.17 D.18 11.在下图中，从顶点1出发进行深度优先遍历可得到的序列是( ) A.1 2 3 4 5 6 7 B.1 4 2 6 3 7 5 C.1 4 2 5 3 6 7 D.1 2 4 6 5 3 7 12.如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是( ) A.不稳定的 B.稳定的 C.基于交换的 D.基于选择的 13.设有一组关键字(19, 14, 23, 1，6，20, 4，27, 5，11, 10, 9)，用散列函数H(key)=key%13构造散列表，用拉链法解 决冲突，散列地址为1的链中记录个数为( ) A.1 B.2 C.3 D.4 14.已知二叉树结点关键字类型为字符，下列二叉树中符合二叉排序树性质的是( ) 数据结构经典例题 1.设计一个算法将L拆分成两个带头节点的单链表L1和L2。 void split(LinkList *&L,LinkList *&L1,LinkList *&L2) { LinkList *p=L->next,*q,*r1; //p指向第1个数据节点 L1=L; //L1利用原来L的头节点 r1=L1; //r1始终指向L1的尾节点 L2=(LinkList *)malloc(sizeof(LinkList));//创建L2的头节点 L2->next=NULL; //置L2的指针域为NULL while (p!=NULL) { r1->next=p; //采用尾插法将*p(data值为ai)插入L1中 r1=p; p=p->next; //p移向下一个节点(data值为bi) q=p->next; //由于头插法修改p的next域,故用q保存*p的后继节点 p->next=L2->next; //采用头插法将*p插入L2中 L2->next=p; p=q; //p重新指向ai+1的节点 } r1->next=NULL; //尾节点next置空 } 2.查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。 typedef struct LNode {int data; struct LNode *link; } *LinkList; int Searchk(LinkList list,int k) { LinkList p,q; int count=0; p=q=list->link; while (p!=NULL) { if (count数据结构模拟卷(含答案)经典习题培训讲学
数据结构第六章习题课
数据结构习题库汇总
数据结构模拟卷(含答案)经典习题
《数据结构》实验报告
数据结构习题
经典数据结构上机题_答案解析
数据结构课程实验报告(15)
数据结构1-4章习题答案
数据结构经典题目c语言代码
(完整版)数据结构---C语言描述-(耿国华)-课后习题答案
数据结构实验报告--图实验
数据结构习题2011级
数据结构经典例题