下载文档原格式
数据结构复习题汇总黄⽼师：题型结构如下：单项选择题，15⼩题，30分；填空题，5⼩题，10分；综合应⽤题，50分（树、图、查找）算法设计与分析，2选1,10分（线性结构）试卷中⼀些算法只给英⽂名称；考查范围(⿊体字为建议的重点考查内容；红字为备注；蓝字为拟纳⼊的考研⼤纲内容)⼀、绪论（⼀）算法、数据结构基本概念（⼆）算法分析中O（f（n））符号的含义（三）时间复杂度简单分析表⽰⼆、线性表（⼀）线性表的定义和基本操作（⼆）线性表的实现1.顺序存储2.链式存储3.线性表的应⽤三、栈、队列（⼀）栈和队列的基本概念（⼆）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应⽤四、树与⼆叉树（⼀）树的概念（⼆）⼆叉树1.⼆叉树的定义及其主要特征2.⼆叉树的顺序存储结构和链式存储结构3.⼆叉树的遍历及应⽤（三）树、森林1. 森林与⼆叉树的转换2. 树的存储结构；3.树和森林的遍历4.线索⼆叉树的基本概念和构造（四）⼆叉树的应⽤1.哈夫曼（Huffman）树和哈夫曼编码2.⼆叉排序树五、图（⼀）图的基本概念（⼆）图的存储及基本操作1.邻接矩阵法2.邻接表法（三）图的遍历1.深度优先搜索2.⼴度优先搜索（四）图的基本应⽤1.最⼩（代价）⽣成树2.最短路径3.拓扑排序4.关键路径六、查找（⼀）查找的基本概念（⼆）顺序查找法（三）折半查找法（四）⼆叉查找树及其基本操作（只考察基本概念）（五）平衡⼆叉树（只考察基本概念）（六）散列（Hash）表（七）查找算法的分析及应⽤七、排序（⼀）排序的基本概念（⼆）直接插⼊排序（三）⽓泡排序（bubble sort）（四）简单选择排序（五）希尔排序（shell sort）（六）快速排序（七）堆排序（⼋）⼆路归并排序（merge sort）（九）各种排序算法的⽐较（⼗）排序算法的应⽤选择题1、顺序队列的出队操作，正确修改队⾸指针的是（ B ）（A）sq.front = (sq.front+1)%maxsize; （B）sq.front = sq.front+1;（C）sq.rear = (sq. rear +1)%maxsize; （D）sq.rear = sq. rear +1;2、⾮空的循环单链表head的尾结点（由指针p指）满⾜（ C ）（A）p->next = NULL （B）p = NULL （C）p->next = head （D）p = head3、在单键表中，删除p所指结点的直接后继，其中指针修改为（ A ）（A）p->next = p->next ->next; （B）p = p->next; p->next = p->next->next;（C）p->next = p->next; （D）p = p->next ->next;4、通常要求同⼀逻辑结构中的所有数据元素具有相同的特性，这意味着（ B ）（A）数据元素具有同⼀特点（B）不仅数据元素所包含的数据项的个数要相同，⽽且对应数据项的类型也要⼀致（C）每个数据元素都⼀样（D）数据元素所包含的数据项的个数要相等5、关于线性表，下列说法正确的是（ D ）（A）每个元素都有⼀个直接前驱和直接后继（B）线性表中⾄少要有⼀个元素（C）表中诸元素的排列顺序必须是由⼩到⼤或由⼤到⼩的（D）除第⼀元素和最后⼀个元素外，其余每个元素都有⼀个且仅有⼀个直接前驱和直接后继6、带头结点的单链表，其表头指针为head，则该单链表为空的判断条件是（ B ）（A）head == NULL （B）head->next == NULL（C）head->next == head （D）head !== NULL7、含n个顶点的连通图中的任意⼀条简单路径，其长度不可能超过（C ）（A）1 （B）n/2 （C）n-1 （D）n8、设有⼀个顺序栈S，元素S1, S2, S3, S4, S5, S6依次进栈，如果6个元素出栈的顺序是S2, S3, S4, S6, S5, S1，则栈的容量⾄少应该是（ B ）（A）2 （B）3 （C）5 （D）69、设深度为k的⼆叉树上只有度为0和度为2的结点，则这类⼆叉树上所含结点的总数最少为（ C ）个（A）k+1 （B）2k （C）2k -1 （D）2k +110、从具有n个结点的单链表中查找指定结点时，若查找每个结点的概率相等，在查找成功的情况下，平均需要⽐较（ D ）个结点。
数据结构试题一、单选题（每题 2 分，共20分）1.1. 对一个算法的评价，不包括如下（ B ）方面的内容。
A．健壮性和可读性B．并行性 C．正确性 D．时空复杂度2.2. 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( A )。
A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3.3. 对线性表，在下列哪种情况下应当采用链表表示？( B )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4.4. 一个栈的输入序列为 1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35.5. AOV网是一种（ D ）。
A．有向图 B．无向图 C．无向无环图D．有向无环图6.6. 采用开放定址法处理散列表的冲突时，其平均查找长度（ B ）。
A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同 D．高于二分查找7.7. 若需要利用形参直接访问实参时，应将形参变量说明为（ D ）参数。
A．值 B．函数 C．指针 D．引用8.8. 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（ A ）。
A．行号B．列号 C．元素值 D．非零元素个数9.9. 快速排序在最坏情况下的时间复杂度为（ D ）。
A．O(log2n) B．O(nlog2n) C．O(n) D．O(n2)10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。
A. O(n)B. O(1)C. O(log2n) D. O(n2)二、运算题（每题 6 分，共24分）1. 1. 数据结构是指数据及其相互之间的_对应关系(联系)。
当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。
快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；1. 插入排序—直接插入排序(Straight Insertion Sort)基本思想:将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。
即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。
要点：设立哨兵，作为临时存储和判断数组边界之用。
直接插入排序示例：如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。
所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
算法的实现：效率：时间复杂度：O（n^2）.其他的插入排序有二分插入排序，2-路插入排序。
2. 插入排序—希尔排序（Shell`s Sort）希尔排序是1959 年由D.L.Shell 提出来的，相对直接排序有较大的改进。
希尔排序又叫缩小增量排序基本思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
操作方法：1.选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；2.按增量序列个数k，对序列进行k 趟排序；3.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。
仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
希尔排序的示例：算法实现：我们简单处理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1} n为要排序数的个数即：先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。
一、选择题1．下面关于线性表的叙述中，错误的是哪一个？（ B ）A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
3．线性表是具有n个（ C ）的有限序列（n>0）。
A．表元素B．字符C．数据元素D．数据项E．信息项2．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。
A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表3．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。
A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表4. 静态链表中指针表示的是（ C ）.A．内存地址B．数组下标C．下一元素地址D．左、右孩子地址5. 链表不具有的特点是（ B ）A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比1. 对于栈操作数据的原则是（B ）。
A. 先进先出B. 后进先出C. 后进后出D. 不分顺序2. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ A ）A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 41 5 63. 设栈的输入序列是1，2，3，4,则（D ）不可能是其出栈序列。
A. 1，2，4，3，B. 2，1，3，4，C. 1，4，3，2，D. 4，3，1，2，E. 3，2，1，4，1. 已知数组A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，求A[6，8]的地址。
13402. 已知二维数组A[1..10，0..9]中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，求A[5，9]的地址。
这几天笔试了好几次了，连续碰到一个关于常见排序算法稳定性判别的问题，往往还是多选，对于我以及和我一样拿不准的同学可不是一个能轻易下结论的题目，当然如果你笔试之前已经记住了数据结构书上哪些是稳定的，哪些不是稳定的，做起来应该可以轻松搞定。
本文是针对老是记不住这个或者想真正明白到底为什么是稳定或者不稳定的人准备的。
首先，排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。
在简单形式化一下，如果Ai = Aj, Ai原来在位置前，排序后Ai还是要在Aj位置前。
其次，说一下稳定性的好处。
排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。
基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。
另外，如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能会少一些(个人感觉，没有证实)。
回到主题，现在分析一下常见的排序算法的稳定性，每个都给出简单的理由。
(1)冒泡排序冒泡排序就是把小的元素往前调或者把大的元素往后调。
比较是相邻的两个元素比较，交换也发生在这两个元素之间。
所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
(2)选择排序选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。
那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。
比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。
关于堆排序、归并排序、快速排序的⽐较时间复杂度：堆排序归并排序快速排序最坏时间 O(nlogn) O(nlogn) O(n^2)最好时间 O(nlogn) O(nlogn) O(nlogn)平均时间 O(nlogn) O(nlogn) O(nlogn)辅助空间 O(1) O(n) O(logn)～O(n)从时间复杂度看堆排序最好有⼈说代码实现后，数据量⾜够⼤的时候，快速排序的时间确实是⽐堆排序短解释是，对于数组，快速排序每下⼀次寻址都是紧挨当前地址的，⽽堆排序的下⼀次寻址和当前地址的距离⽐较长。
⽹友解答：1#4种⾮平⽅级的排序：希尔排序，堆排序，归并排序，快速排序我测试的平均排序时间：数据是随机整数，时间单位是秒数据规模快速排序归并排序希尔排序堆排序1000万 0.75 1.22 1.77 3.575000万 3.78 6.29 9.48 26.541亿 7.65 13.06 18.79 61.31堆排序是最差的。
这是算法硬伤，没办法的。
因为每次取⼀个最⼤值和堆底部的数据（记为X）交换，重新筛选堆，把堆顶的X调整到位，有很⼤可能是依旧调整到堆的底部（堆的底部X显然是⽐较⼩的数，才会在底部），然后再次和堆顶最⼤值交换，再调整下来。
从上⾯看出，堆排序做了许多⽆⽤功。
⾄于快速排序为啥⽐归并排序快，我说不清楚。
2#算法复杂度⼀样只是说明随着数据量的增加，算法时间代价增长的趋势相同，并不是执⾏的时间就⼀样，这⾥⾯有很多常量参数的差别，即使是同样的算法，不同的⼈写的代码，不同的应⽤场景下执⾏时间也可能差别很⼤。
快排的最坏时间虽然复杂度⾼，但是在统计意义上，这种数据出现的概率极⼩，⽽堆排序过程⾥的交换跟快排过程⾥的交换虽然都是常量时间，但是常量时间差很多。
3#请问你的快快速排序是怎么写的，我写的快速排序，当测试数组⼤于5000的时候就栈溢出了。
其他的⼏个排序都对着，不过他们呢没有⽤栈。
这是快速排序的代码，win7 32位，vs2010.1int FindPos(double *p,int low,int high)2 {3double val = p[low];4while (low<high)5 {6while(low<high&&p[high]>=val)7 high--;8 p[low]=p[high];9while(low<high&&p[low]<val)10 low++;11 p[high]=p[low];12 }13 p[low]=val;14return low;15 }16void QuickSort(double *a,int low,int high)17 {18if (!a||high<low)19return;2021if (low<high)22 {23int pos=FindPos(a,low,high);24 QuickSort(a,low,pos-1);25 QuickSort(a,pos+1,high);26 }27 }……7#谁说的快排好啊？我⼀般都⽤堆的，我认为堆好。
2021《算法数据结构》复习试题库及答案试题1算法设计题(每小题6分.共12分)1.请写出在循环队列上进行插入操作的算法。
要求若插入成功则返目true，否则返回else.循环队列定义如下：struet CyclicQueue {ElemTy[ae elem[M]; //M为已定义过的整型常量，表示队列数组空间长度int rear,front; //rear指向队尾元素后一个位置，front指向队头元索int tag;};注意：当front=rear且tag=0时，队列空，当front=rear 且tag=1时，队列满，即队列中已有M个元素.bool EnCQueue(CyclicQueue& Q, ElemType x){ {/*编写该函数体。
/}//在下面编写函数体2.已知二又树中的结点类型Bin·rreeNode定义为：slruct BinTreeNode {char data;BinTreeNode * left, * right;};其中data为结点值域，left和righ~分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中结点总数的递归算法，该总数值由函数返回.假定BT初始指向这棵二又树的.根结点.int BTreeCount(BinTreeNode* BT);答案算法设计题(2小题，每小题6‘分，共12分)1.分步给分if (Q. rear=Q, front && Q tag== 1) return false;Q. elem[Q, rear] = x;Q. rtar= (Q. rear+ 1) %M;if(Q. rear== Q. front) Q. tag= 1;return true;2.分步给分int BTreeCount(BinTreeNode * BT)(if(BT== NULL)return O;elsereturn BTreeCount ( BT->left) +BTreeCount(BT-> fight) + l;试题21.设字符串类String具有下列操作：int Length()const; //计算字符串的长度chargetData(k); //提取字符串第k个字符的值若字符串Tar的值为“ababcabcacbab“，的值为‘abcac”时，(1)给出下面算法执行后返回的结果，(2)给出下面。
数据结构填空题集锦一1. 数据结构是指数据及其相互之间的联系。
当结点之间存在M对N（M：N）的联系时，称这种结构为图或者是图的结构2. 队列的插入操作是在队列的尾进行，删除操作是在队列的首进行。
3. 当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是top==0 （要超出才为满）。
4. 对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为O(1) ，在表尾插入元素的时间复杂度为O(n) 。
5. 设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j从0到3 ，则二维数组W的数据元素共占用128 个字节。
W中第6 行的元素和第4 列的元素共占用44 个字节。
若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为108 。
6.广义表A= (a,(a,b),((a,b),c)),则它的深度为3 ，它的长度为3 。
7. 二叉树是指度为2的有序树。
一棵结点数为N的二叉树，其所有结点的度的总和是n-1 。
8. 对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个有序序列有序列表。
对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的_后缀表达式后缀表达式（或列波兰式）。
9. 对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为___2n___个，其中____n-1___个用于指向孩子，___n+1____个指针是空闲的。
10.若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A 中，即编号为0的结点存储到A[0]中。
其余类推，则A[ i ]元素的左孩子元素为_2加一___,右孩子元素为_2加二___，双亲元素为__（i-1）/2__。
11.在线性表的散列存储中，处理冲突的常用方法有开放地址法和__ _链接法______两种。
12. 当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用快速_排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用____并归排序。
