(2025年)数据结构(C语言版严蔚敏)课后习题答案(选择题)

(2025年)数据结构(C语言版严蔚敏)课后习题答案(选择题)1.数据结构研究的内容不包括以下哪项？A.数据的逻辑结构B.数据的存储结构C.数据的运算D.数据的算法分析答案：D解析：数据结构的三要素是逻辑结构、存储结构（物理结构）和数据的运算（操作）。算法分析属于算法设计与分析的范畴，并非数据结构直接研究的内容。2.对于顺序表和链表，以下说法正确的是？A.顺序表插入删除操作时间复杂度均为O(n)B.链表的存储空间一定比顺序表更节省C.顺序表可以随机访问，链表只能顺序访问D.链表的头结点是必须的答案：C解析：顺序表插入删除需移动元素，平均时间复杂度为O(n)，但链表插入删除在找到位置后为O(1)，故A错误；链表需额外存储指针域，可能更占空间，B错误；顺序表支持O(1)随机访问，链表仅支持O(n)顺序访问，C正确；头结点是可选设计，非必须，D错误。3.若一个栈的输入序列是1,2,3,4，不可能的输出序列是？A.4,3,2,1B.3,4,2,1C.2,4,1,3D.2,3,4,1答案：C解析：栈遵循后进先出原则。C选项中，2先出（1、2入栈，2出），随后4出（需3、4入栈），此时栈内剩余3、1；下一个输出1时，栈顶为3，无法直接弹出1，故C不可能。4.循环队列存储在数组Q[0..n-1]中，已知队头指针front，队尾指针rear（指向队尾元素的下一个位置），队列长度为？A.(rearfront+n)%nB.rearfrontC.(frontrear+n)%nD.rearfront+n答案：A解析：循环队列中，若rear≥front，长度为rearfront；若rear<front，长度为nfront+rear。综合两种情况，长度计算公式为(rearfront+n)%n。5.设主串S="abcabx"，模式串T="abx"，使用KMP算法时，模式串的next数组为？A.[-1,0,0]B.[-1,0,1]C.[0,1,2]D.[-1,0,2]答案：A解析：KMP算法中，next[0]固定为-1。对于j=1（T[1]='b'），最长相等前后缀长度为0；j=2（T[2]='x'），前缀"ab"与后缀"bx"无公共真前缀，故next[2]=0。因此next数组为[-1,0,0]。6.一个n阶对称矩阵A，采用压缩存储，只存储下三角（含主对角线），则存储元素个数为？A.n(n+1)/2B.n(n-1)/2C.n²D.2n-1答案：A解析：下三角（含主对角线）的元素数为1+2+…+n，即等差数列求和公式n(n+1)/2。7.一棵完全二叉树有100个结点，其叶子结点数为？A.50B.51C.49D.48答案：A解析：完全二叉树中，结点总数n=100。设度为0、1、2的结点数分别为n0、n1、n2，有n0=n2+1且n=n0+n1+n2。若n1=0，则n=2n0-1=100→n0=50.5（舍去）；若n1=1，则n=2n0=100→n0=50，符合条件。8.二叉树的先序序列为ABDCE，中序序列为BDAEC，后序序列为？A.DBECAB.DEBCAC.DBEACD.DCEBA答案：A解析：先序根为A，中序划分左子树BDA、右子树EC。左子树先序BD、中序BD→根B，右子树D；右子树先序CE、中序EC→根C，左子树E。后序遍历顺序为左→右→根，即D→B→E→C→A，最终后序序列为DBECA。9.无向图G有8个顶点，若每个顶点的度至少为2，则边数至少为？A.8B.9C.10D.16答案：A解析：无向图边数m=总度数/2。每个顶点度≥2，总度数≥16，故m≥16/2=8。10.用邻接表存储图，进行DFS遍历的时间复杂度为？A.O(n)B.O(e)C.O(n+e)D.O(n²)答案：C解析：DFS遍历需访问每个顶点（O(n)）和每条边（O(e)），总时间复杂度为O(n+e)。11.对长度为n的有序表进行二分查找，最坏情况下比较次数为？A.log₂nB.⌊log₂n⌋+1C.n/2D.n答案：B解析：二分查找的最坏情况对应二叉判定树的高度，即⌊log₂n⌋+1次比较。12.哈希表中解决冲突的方法不包括？A.开放定址法B.链地址法C.再哈希法D.顺序查找法答案：D解析：顺序查找是查找元素的方法，并非解决哈希冲突的策略。13.以下排序算法中，不稳定的是？A.冒泡排序B.插入排序C.归并排序D.快速排序答案：D解析：快速排序在划分过程中可能交换相同元素的相对顺序（如[2,2,1]排序后可能变为[1,2,2]，原第一个2的位置改变），故不稳定。14.对初始序列{5,3,8,6,7,2,4,1}进行希尔排序（增量序列5,3,1），第一趟（增量5）排序后的序列是？A.2,3,4,1,7,5,8,6B.5,2,8,4,7,3,6,1C.5,3,2,6,7,8,4,1D.1,2,3,4,5,6,7,8答案：B解析：增量5时，分组为(5,2),(3,3),(8,4),(6,1),(7)。各组内部插入排序：5和2交换→2,5；3和3不变；8和4交换→4,8；6和1交换→1,6；7不变。原序列索引0→5（值5和2交换），索引1→6（值3和4不交换），索引2→7（值8和1交换），最终序列为[2,3,1,6,7,5,4,8]（注：原题选项可能调整，正确逻辑为按增量分组后排序）。15.堆排序的时间复杂度为？A.O(n)B.O(nlogn)C.O(n²)D.O(1)答案：B解析：堆排序建堆时间为O(n)，每次调整堆时间为O(logn)，共n次调整，总时间复杂度为O(nlogn)。16.数据的物理结构（存储结构）不包括？A.顺序存储B.链式存储C.索引存储D.逻辑存储答案：D解析：物理结构包括顺序、链式、索引、散列存储，逻辑结构是数据间的抽象关系，与存储无关。17.单链表中，已知p指针指向某结点，若要在p之后插入s结点，操作正确的是？A.p->next=s;s->next=p->next;B.s->next=p->next;p->next=s;C.p->next=s;s->next=p;D.s->next=p;p->next=s;答案：B解析：插入操作需先将s的next指向p的后继（避免断链），再将p的next指向s，正确顺序为B。18.表达式a(b+c)-d的后缀表达式是？A.abc+dB.abc+dC.abc+dD.ab+cd答案：A解析：中缀转后缀时，遇到操作数直接输出，遇到运算符按优先级入栈。计算过程：a输出，入栈；(入栈；b输出，+入栈；c输出，+出栈输出+；)弹出(；出栈输出；-入栈；d输出，-出栈输出-，最终后缀表达式为abc+d-。19.链式队列的队空条件是？A.front==rearB.front==NULLC.rear==NULLD.front->next==NULL答案：A解析：链式队列通常用front（头指针）和rear（尾指针）表示，队空时front和rear均指向头结点（或均为NULL），故判断条件为front==rear。20.设串S="software"，其子串数目是？A.8B.36C.37D.9答案：B解析：长度为n的串的非空子串数目为n(n+1)/2。S长度为8，故子串数目为8×9/2=36。21.二维数组A[10..20][5..15]，按行优先存储，每个元素占4字节，A[10][5]的地址为1000，则A[15][10]的地址是？A.1000+(15-10)11+(10-5)4B.1000+(15-10)114+(10-5)4C.1000+(15-10)10+(10-5)4D.1000+(15-10)104+(10-5)4答案：B解析：行下标范围10-20（共11行），列下标5-15（共11列）。行优先存储时，A[i][j]的地址=基地址+[(i-10)×11+(j-5)]×4。代入i=15、j=10，计算得地址=1000+(5×11+5)×4=1000+60×4=1240，对应选项B。22.一棵二叉树的中序遍历是DBEAFC，后序遍历是DEBFCA，先序遍历是？A.ABDECFB.ABCDEFC.ADBECFD.ABDEFC答案：A解析：后序根为A，中序划分左子树DBEA、右子树FC。左子树后序DEB、中序DBE→根B，后序DE→根E，中序D在左；右子树后序FC、中序FC→根C，左子树F。先序遍历顺序为根→左→右，即A→B→D→E→C→F，最终先序序列为ABDECF。23.有向图的强连通分量是指？A.极大强连通子图B.极小强连通子图C.任意强连通子图D.提供树答案：A解析：强连通分量是图中极大的强连通子图，即无法加入其他顶点仍保持强连通的子图。24.在哈希表中，若哈希函数为H(key)=key%11，采用线性探测法解决冲突，依次插入47,26,60,33,4,14，则关键字14的存储地址是？A.3B.4C.5D.6答案：D解析：H(47)=3→地址3；H(26)=4→地址4；H(60)=5→地址5；H(33)=0→地址0；H(4)=4（冲突