《数据结构 严蔚敏C》期末高频考题整理（含详解）_数据结构c语言版期末考试题

1、数据的物理结构是数据在计算机中实际的存储形式。

对

2、算法分析的目的是分析算法的易懂性和文档性。

错，算法分析的目的是分析算法的效率以求改进

3、顺序存储的线性表的插入和删除操作不需要付出很大的代价,因为平均每次操作只有近一半的元素需要移动。

错

4、不论线性表采用顺序存储结构还是链式存储结构,删除值为X的结点的时间复杂度均为O(N)。

对

5、链式存储的线性表可以随机存取。

错 顺序存储的特点(优点)才是随机存储，因为顺序表是用数组来存储的，每一个数据都有相应的数组下标，我们通过数组下标就能找到任意位置的数据。而链式存储就不同了，不管你找谁都要从头结点开始的。

6、线性表只能用顺序存储结构实现。

错 链式存储结构也可以实现。

7、以链表的头部作为栈顶是最方便的。

对 对栈来讲，进栈出栈都在栈顶进行，而对单链表来讲，始终在单链表的头部插入或删除一个结点最为方便，这是其一，其二，采用头插法，生成的链表，其里的数据元素刚好栈的特征相符。先进后出。所以链表的头部作为栈顶是最方便的

8、链栈采用动态分配,不会出现闲置或栈满溢出现象。

对

9、在括号匹配问题中,若读入的字符是左括号,则将其压入栈。

对    感兴趣的朋友可以去做下洛谷的括号匹配问题：洛谷P1739、UVA673  Parentheses Balance

10、若以链表作为栈的存储结构,则出栈需要判断栈是否空。

对  

11、对于不同的特殊矩阵应该采用不同的存储方式。

对 特殊矩阵中元素有规律，采用数组存储。而像稀疏矩阵中元素没有规律，所以一般采用三元组或者伪地址表示法～

12、在一般情况下,采用压缩存储之后,对称矩阵是所有特殊矩阵中存储空间节约最多的。

错 压缩情况下，稀疏矩阵占用内存最少。

13、哈夫曼树是带权路径长度最短的树，所以已知叶子的权值求出的哈夫曼树一定是唯一的。

错，因为没有限定左右子树，并且如果有权值重复时，可能树的高度都不唯一，唯一的只是带权路径长度之和最小

14、将一棵树转换成二叉树后,根结点没有左子树。

错  没有右子树

15、完全二叉树的存储结构通常采用顺序存储结构。

对    

16、连通图上各边权值均不相同，则该图的最小生成树是唯一的。

对

17、有e条边的无向图，在邻接表中有e个结点。

错   ，对于任意一条边 在用邻接表表示时都需要表示两次，每次都涉及到两个结点，所以有2e个结点

18、任何无向图都存在生成树。

错  只有图为无向连通图时才能生成树。多个连通分量无法构成树。

19、有n个数存放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。

错

20、用顺序表和单链表表示的有序表均可使用折半查找方法来提高查找速度。

错

21、折半查找和二叉排序树的时间性能相同

错  不一定相同。

1. 二叉排序树不一定是平衡树，它是只要求了左右子树与根结点存在大小关系，但是对左右子树之间没有层次差异的约束，因此通过二叉排序树进行查找不一定能够满足logn的，例如一棵只有多层左子树的而叉排序树。

2. 只有是一棵平衡的二叉排序树时，其查找时间性能才和折半查找类似。     

22、（ 10，5，16，2，4 ）是堆。

错  堆的定义：{k1,k2,k3,···kn},当满足(1)ki >= k2i且ki>=k2i+1

或 (2)ki <= k2i且ki <= k2i+1 (1 <= i <= n/2（n/2向下取整）） 

23、排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。

错  排序的稳定性,就是指,在对a关键字排序后会不会改变其他关键字的顺序。
比如排序（2，3，1（第一个），1（第二个），5，6）
不稳定的排序，可能会排出
（1（第二个），1（第一个），2，3，5，6）；//前面两个1无论怎么排都不会影响后面元素的顺序
而稳定的排序则不会，在比较的关键字相同的情况下，稳定的排序会将较早出现的元素排在前面。

24、（101，88，46，70，34，39，45，58，66，10）是堆。

对

设某无向图有n个顶点，则该无向图的邻接表中有（ ）个表头结点。B.n

看动画，彻底理解数据结构中图的知识，图的邻接表和邻接矩阵_哔哩哔哩_bilibili

任一个有向图的拓扑序列（   ）。D.有一个或多个或不存在  

不存在的情况是：当有向图中形成环时。一个图能够进行拓扑排序的一个必要条件就是图中不存在环。

在用邻接表表示图时，拓扑排序算法时间复杂度为( )。C.O（n+e）

对于一个具有n个顶点e条弧的有向图来说，刚开始将入度为0的顶点入栈的时间复杂为O(n)，在之后顶点出栈时，入度减1的操作共执行了e次，所以整个算法的时间复杂度为O(n + e)。

在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有（   ）邻接点。D.入边

邻接表：反映的是顶点出度的情况。
逆邻接表：反映的是顶点的入度情况。

无向完全图的邻接矩阵是（  ）矩阵。D.对称   

一个带权的无向连通图的最小生成树（ ）。D.有一棵或多棵 

 权值相同的情况下可以构成多棵最小生成树

深度优先遍历类似于二叉树的（    ）。C.先序遍历

深度优先遍历，是从根节点开始先根后左后右，所以类似于先序遍历。
广度优先遍历，是一层一层从左到右遍历，所以类似于层序遍历。

设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有________个结点。D.25

将一棵哈夫曼树的度为0,1,2的结点分别表示为 n0, n1, n2。则一共的结点数是 n0 + n1 + n2，

= n0 + 0 + (n0 - 1) = 2n0 - 1。(公式推导看不懂？画画图就懂了) 所以此题就是  2 x 13 - 1 = 25 。

已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？A.16

满二叉树性质补充：k为深度，

1、叶子数：2^(k-1)。二的k-1次方   

2、第k层结点:2^(k-1)。二的k-1次方

3、总结点数必是奇数。

20到40之间的素数，有23，29，31，37。先带23，然后套完全二叉树求深度公式（书上有）算出深度k。本题，k套完全二叉树求深度公式，算出k=5，然后叶子结点数，套第一个公式，算出16。

用一维数组存放的一棵完全二叉树其存储顺序为：ABCDEFGHIJKL。则后序遍历该二叉树的结点访问序列为（    ）。C.HIDJKEBLFGCA

依题意画出完全二叉树，然后求其后序遍历即可、

某二叉树中序序列为ABCDEFG，后序序列为BDCAFGE，则前序序列是________。D.EACBDGF

技巧：(简单易懂)二叉树已知后序序列和中序序列，或已知前序序列和中序序列，画出二叉树（简单易懂）_Curz酥的博客-CSDN博客

下面几个符号串编码集合中，不是前缀编码的是________。B.{11,10,001,101,0001}

任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。

例子：{ 01, 0000, 0001, 001, 1 } 是前缀码。
{ 0, 100, 110, 1110, 1100} 不是前缀码，原因是同时包含了 110 以及 1100，其中 110 是 1100 的前缀。

将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度________。D.6

  具有n个结点的完全二叉树的深度是 log2n + 1。  其中，2为底，且（log2n）向下取整（就是求不大于其的最大整数）。稍微一推导，可知求完全三叉树，这边把公式里的2换成3就行了。《严C语言2版》教材翻到第P119有公式以及公式推导。

顺便提一下深度与高度的区别：深度是从根结点数到它的叶节点，高度是从叶结点数到它的根结点。根结点深度是1。

一棵有124个叶结点的完全二叉树，最多有________个结点。C.248

注意这里说的是叶结点。没那么复杂，只要记住：完全二叉树的叶子结点数等于树总结点除二就行了。如果不能整除那就＋1就是叶子结点数。 这边就是124 x 2 = 248。

在下列存储形式中，哪一个不是树的存储形式？________。B.顺序存储表示法 

树有三种常用的存储方式：双亲表示法、孩子表示法、孩子兄弟表示法。

你可能会想，满二叉树不就用的顺序存储？ 是的，但是这里题目问的是树，树和二叉树还是有区别的，比如树有且只有一个根结点，而二叉树可以为空。

把一棵树转换为二叉树后，这棵二叉树的形态是________。C.唯一的

不会转换？看下面这个视频秒懂：

超详细讲解二叉树，树，森林之间的转换_哔哩哔哩_bilibili

下述几种排序方法中，（   ）是稳定的排序方法。C.归并排序

记住，快排，堆排，希尔是不稳定的，其它都是稳定的，归并最稳定。

下列排序算法中，（   ）不能保证每趟排序至少能将一个元素放到其最终的位置上。B.希尔排序

啥是希尔排序？下面这个视频讲得不错：

[算法]六分钟彻底弄懂希尔排序，简单易懂_哔哩哔哩_bilibili

当采用分块查找时，数据的组织方式为  (    )B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块

要点：块间有序，块内无序。若i < j ，则第j块里所有数据均大于第i块里所有数据。

下面这个视频关于分块查找讲得很清晰，一听就懂：

数据结构与算法基础--第12周06--第7章查找6--7.2线性表的查找5--7.2.3分块查找1--分块查找算法_哔哩哔哩_bilibili

如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（    ）就是不稳定的排序方法。C.希尔排序 

因为希尔排序，相同元素下标发生交换次数最为频繁。稳定排序的意思是相同的元素排序后顺序不变

下述几种排序方法中，要求内存最大的是（   ）。A.归并排序

因为归并排序需要用到辅助数组。你看看归并排序的实现就知道了。
每次partition的时候，你要用到两个辅助数组，一个用来存放左半部分，一个用来存放有半部分，左右分别排序之后，要把这两个辅助数组里的内容，归并回原数组。归并的内存消耗主要用在了辅助数组上。

下列排序算法中，其中（    ）是稳定的。B.归并排序，冒泡排序  

为啥冒泡稳定？因为经过冒泡排序后，元素的前后顺序并没有改变,所以稳定。

算法动画图解：冒泡排序_哔哩哔哩_bilibili

设要将序列（q,h,c,y,p,a,m,s,r,d,f,x）  中的关键码按字母升序重新排序，（  ）是以第一个元素为分界元素的快速一趟扫描的结果。B.f ,h ,c ,d ,p ,a ,m ,q ,r ,s ,y ,x

用的快速排序，如果不会，看完下面这个视频就会做了（一看就懂）：

快速排序算法_哔哩哔哩_bilibilikk  ​​​​​​​ 

想加深印象？Acwing网站里的 应用 Ac Saber，里面有快速排序关卡，题目就是手写快排，把那关过了，说明你对快排有一定理解了。

对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（    ）排序。A.希尔排序

很容易可以看出是希尔排序，这里是从左到右以三个数据为一组来进行希尔排序。

用二分（折半）查找表的元素的速度比用顺序法(    )D.不能确定 

 比如查找的元素刚好在第一个，那顺序法不就比二分快？

散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。元素59存放在散列表中的地址是（    ）。D.11

以下说法正确的是（     ）。D.连通图的生成树，是该连通图的一个极小连通子图。

下面这个百赞回答对于极大连通子图，极小连通子图讲解得很详细：

极大连通子图与极小连通子图（带图讲解）_tong1557在哪里-CSDN博客_极大连通子图

若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为(  )D.9，4，2，3

比较序列下标就是middle。begin的初始值是1，end=18，middle=（18+1）/2=9；第一次之后，begin=1， end=9-1=8，middle=(1+8)/2=4；第二次之后，begin=1，end=4-1=3；middle=(1+3)/2=2;第三次 begin=3,end=3,midlle=3;

无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。A.a,e,d,f,c,b

G=(V,E)，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

不难画出： 

深搜，就是一条路走到死。所以答案是

a,e,d,f,c,b。广搜，就是有路就走，a,c,e,b,f,d。

下面关于二分（折半）查找的叙述正确的是  (    )D.表必须有序，且表只能以顺序方式存储

是的，如果数组不是单调的无法仅通过mid的大小确定目标在左区间还是右区间，简单来说，二分查找在一定区间内查找，要确定区间，所以得排序。

设Hash地址空间为0到m-1，哈希函数为h(k)=k%p，为了减少发生冲突的可能性，一般取p为（    ）。B.小于m的最大素数

在有序表A[80]上进行二分法查找，查找失败时，需对键值进行最多比较次数是(   )。D.7

40,20,10,5,2,1,0，共7次。

若为查找表长度为m的散列表采用二次探测再散列处理冲突，对一个元素第1次计算的哈希地址为d，则第3次计算的哈希地址为（     ）B.(d-1)%m

在查找过程中，若同时还要做插入、删除操作，这种查找称为  (   )  。B.动态查找 

数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用(    )算法最节省时间。D.堆排序  

看到节省时间，就想到快排，但是这里数据特别多？！那就得想到堆排序。因为快排期望时间复杂度为O(nlogn)最坏为O(n^2)，而堆排序是严格O(nlogn)，所以相比之下，本题选D堆排序。

完成在双循环链表结点p之后插入s的操作是( )。B.s→prior=p; s→next=p→next; p→next→prior=s; p→next=s;    

先处理要插入结点的前驱和后继 再处理后继结点的前驱 最后才是前驱结点的后继。

创建一个包括n个结点的有序单链表的时间复杂度是( )。C.O(n^2)    

可以理解成将n个元素依次插入到空链表中，每一个元素插入需要遍历之前已经有序的链表，找到合适的位置，复杂度是O(n)。一共有n个元素，所以就是O(n*n)。

判断带头结点的单循环链表L仅有一个元素结点的条件是(           )D.L->next->next==L&&L->next!=L

可能你会疑惑，为什么要加上这句“&&L->next!=L”？因为这是为了排除只有一个头结点的情况，一个头结点的话，L的next的next也等于L。

用链接方式存储的队列,在进行删除运算时(    )。D.头、尾指针可能都要修改

在队首进行操作，由于是链式存储，删除结点后，需要修改队首的指针，使其指向下一个结点。但当如果队列中只有这一个结点，这时候头、尾指针都指向这个结点，在删除结点后，头、尾指针都需要修改。

设指针变量p指向单链表中结点A,若删除单链表中结点A,则需要修改指针的操作序列为( )。C.q=p->next;p->data=q->data;p->next=q->next;delete q;

 由图，刚开始P指向A。首先，q=p->next，意思是，将q变成（指向）p的next,也就是B。接着，p->data=q->data，意思是，简单来说，就是A结点变成B结点，如图。然后，p->next=q->next，意思是，p原来的next指向B，现在将它的next指向q的next，也就是指向C。最后。delete q。也就是将q指向的结点删除，也就是删除了B。（如果不懂的话，自己动笔跟着画画图就懂了）

数据的不可分割的基本单位是C.元素    

题目说的是基本单位，就是元素。如果说的是不可分割的最小单位，那就是数据项。

某算法的时间复杂度为O(n^2),表明该算法的(      )

A、问题规模是n^2

C、执行时间等于n^2

C.执行时间与n^2成正比

D、问题规模与n^2成正比

时间复杂度的表示无法对问题规模作出预估，而只能对操作次数作出预估，所以A、D错误。
O(n2)表示的是执行次数是多项式计算的，只保留函数最高阶（平方阶），且去掉系数。并不一定绝对等于n2，所以B错误。
O(n2)，当n的值渐增，其算法时间复杂度执行的时间就越长，所以称正比关系。C正确

将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为________。D.50

完全二叉树对于偶数节点其父节点编号为其编号除以2，奇数节点其父节点编号为（其编号-1）/2。这边就是100/2 = 50。

设带有头结点的单向循环链表的头指针变量为head,则其判空条件是( )。B.head->next==head

画图即可知。

对于顺序表,以下说法错误的是(  )。A.顺序表是用一维数组实现的线性表,数组的下标可以看成是元素的绝对地址

顺序表可以使用一维数组来实现。但不仅仅只是一维数组可以实现。顺序表指的是存储单元在内存中是连续存放。

单链表的存储密度( )。D.小于1

存储密度=单链表数据项所占空间/结点所占空间
结点所占空间 由数据项所占空间和存放后继结点地址的链域构成，所以，存储密度小于1。

广义表A=(a),则表尾为(  )。C.空表

这里表头是a，表尾是()。

循环队列存储在数组A[0..m]中,则入队时的操作为(   )。D.rear=(rear+1)mod(m+1)

书上公式。

若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为3和0,当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为多少?(     )D.5和1 

删除1个，队头+1；加入1个，队尾+1。当然如果这边rear值是5了，再加1，rear值变成0，因为是循环队列。

若INDEX(S,T)表示求T在S中的位置的操作,则对于S=“Beijing&Nanjing”,T=“jing”,INDEX(S,T)=(  )。C.4

注意，“B”是第一个字母，不是第0个。

广义表A=(a,b,(c,d),(e,(f,g))),则Head(Tail(Head(Tail(Tail(A)))))的值为(  )。D.d

从里往外看，Tail(A)是(b,(c,d),(e,(f,g)))；继续Tail，得到((c,d),(e,(f,g)))；继续Head，得到

(c,d)；继续Tail，得到（d）；继续Head，得到d。

有一“遗传”关系，设x是y的父亲，则x可以把它的属性遗传给y，表示该遗传关系最适合的数据结构是_______.A.树

串是一种特殊的线性表,其特殊性体现在(  )。B.数据元素是一个字符   

数组A中,每个元素的长度为3个字节,行下标i从1到8,列下标j从1到10,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A[8][5]的起始地址为(  )。C.SA+222

下面算法的时间复杂度是
int p1( int n)
{
t = 1;
while( t <= n)
t *= 2;
return t;
}        A.O(log2n) 注：2是底

不难理解，解析略。

算法分析的目的是()。C.分析算法的有效性以求改进

程序段:
 for( i=n-1;i>1;i--) 
        for(j=1;j<i;j++)   
              if(a[j]>a[j+1])
                    a[j]与a[j+1]对换;  
 其中 n为正整数,则最后一行的语句频度在最坏情况下是________。A.O(n^2)

最坏，就是两个for都循环遍历完才找到目标，所以答案就是O（n^2）。

以下关于栈和队列的叙述中,正确的是 () 。C.栈和队列都不允许在元素序列的中间插入和删除元素

栈，只能从栈顶开始插入或弹栈（删除），后进后出；队列是从队尾插入，队头删除，先来先出。

链式栈结点为:(data,link),top指向栈顶.若想摘除栈顶结点,并将删除结点的值保存到x中,则应执行操作(  )。A.x=top->data;top=top->link;

先把top的值给x，然后再让top指向在它底下的一个值（就是摘除栈顶结点）

求循环链表中当前结点的后继和前驱的时间复杂度分别是(  )。B.O(1)和O(n)

不难理解，解析略。

假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear,则当前队列中的元素个数为(     )。A.(rear-front+m)%m   

背公式！公式本身不难理解，具体公式推导请自行搜索。

若一个栈的输入序列为1,2,3,…,n,输出序列的第一个元素是i,则第j个输出元素是(     )。D.不确定的

栈的输入输出顺序是后进后出。因为这里题目没说是一次性全进栈,也没说是一次性全出栈，所以输出元素不确定。