数据结构 课后习题答案汇 （张惠涛）第1-9章

一、填空题1.数据结构被形式地定义为（D,R），其中D是数据元素的有限集合，R是D上的关系的有限集合。（解析：D代表数据元素的集合，R代表元素间的关系集合。）2.数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。（解析：数据结构涵盖逻辑结构（数据间的关系）、存储结构（物理存储方式）和运算（相关操作）。）3.数据结构按逻辑结构可分为四大类，它们分别是集合、线性结构、树形结构、图状结构。（解析：逻辑结构的分类基于元素间的关系类型。）4.线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。（解析：线性结构如数组、链表；树形结构如二叉树；图形结构如网络图。）5.在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。（解析：线性结构严格遵循顺序，首尾结点无前驱或后继。）6.在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后继结点，其余每个结点的后续结点数可以任意多个。（解析：树根无父结点（前驱），叶子无子结点（后继），非叶子结点可有多个子结点（后继）。）7.在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。（解析：图结构元素间关系自由，前驱和后继数量无限制。）8.数据的存储结构可用四种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储、哈希存储。（解析：存储方法包括顺序（连续内存）、链式（指针链接）、索引（索引表）、散列（哈希函数）。）9.一个算法的效率可分为时间效率和空间效率。（解析：算法效率主要从时间复杂度和空间复杂度衡量。）10.数据结构是研讨数据的逻辑结构和存储结构，以及它们之间的相互关系，并对与这种结构定义相应的操作，设计出相应的算法。（解析：数据结构研究数据的逻辑关系、物理存储及操作算法。）11.下面程序段中带下划线的语句的执行次数的数量级是O(nlogn)。plaintexti=1;while(i<n){for(j=1;j<=n;j++)//语法修正：逗号改为分号x=x+1;//带下划线的语句i=i*2;}（解析：外层while循环执行次数为O(logn)（因i每次乘以2），内层for循环执行次数为O(n)，故总次数为O(nlogn)，数量级为O(nlogn)。）二、选择题C)数据元素之间的关系解析：存储数据时，除了元素值本身，还需存储元素间的逻辑关系（如指针、索引），这是数据结构的核心。C)逻辑解析：逻辑结构描述数据元素间的抽象关系（如线性、树形），与计算机无关；存储结构和物理结构依赖于具体实现。C)分析算法的效率以求改进解析：算法分析的核心是评估时间/空间效率，优化算法性能。B)可行性、确定性和有穷性解析：算法五大特性：输入、输出、可行性（能执行）、确定性（步骤明确）、有穷性（执行终止）。B.(1),(2),(4)解析：(1)错误：原地工作指O(1)额外空间，并非完全不需要空间。(2)错误：O(n)与O(2n)等价（常数系数可忽略），时间复杂度相同。(3)正确：时间复杂度通常指最坏情况的上界。(4)错误：语言级别与执行效率无直接关联（如C语言高级但高效）。C)线性结构、非线性结构解析：逻辑结构分为线性结构（顺序关系，如链表）和非线性结构（树、图等）。A)一定连续解析：连续存储（如数组）要求物理地址严格连续，这是其实现的基础特性。三、判断题数据元素是数据的最小单位。答案：×解析：数据的最小单位是数据项，数据元素是由数据项组成的（例如：一条记录是数据元素，其中的字段是数据项）。记录是数据处理的最小单位。答案：×解析：数据处理的最小单位是数据项，记录由多个数据项组成（例如：一条学生记录包含学号、姓名等数据项）。数据的逻辑结构是指数据的各数据项之间的逻辑关系。答案：×解析：逻辑结构描述数据元素之间的逻辑关系，而非数据项之间的关系（例如：线性结构中元素的先后关系）。算法的优劣与算法描述语言无关，但与所用计算机有关。答案：×解析：算法优劣取决于时间/空间复杂度，与描述语言和计算机无关（复杂度分析是数学抽象）。健壮的算法不会因非法的输入数据而出现莫名其妙的状态。答案：√解析：健壮性指算法对非法输入有容错处理（如返回错误提示），避免崩溃或不可控状态。算法用高级语言描述后就是程序。答案：×解析：算法是解决问题的步骤，程序是算法的具体实现；算法描述不等同于可执行程序（需编译/解释）。程序一定是算法。答案：×解析：程序不一定是算法，例如死循环程序不满足算法的有穷性（算法必须有限步骤内结束）。数据的物理结构是指数据在计算机内的实际存储形式。答案：√解析：物理结构（存储结构）是数据在内存中的具体存储方式（如顺序存储、链式存储）。顺序存储的优点是存储密度大且插入/删除效率高。答案：×解析：顺序存储密度大（连续空间），但插入/删除需移动大量元素，效率低（时间复杂度O(n)）。数据的逻辑结构依赖于计算机的存储结构。答案：×解析：逻辑结构是抽象的数据关系，独立于存储结构（例如：链表和数组逻辑相同，存储结构不同）。四、分析下列算法的时间复杂度算法1：x=90;y=100;while(y>0)if(x>100){x=x-10;y--;}elsex++;时间复杂度：O(1)无论输入规模如何，循环次数固定为常数（约1100次）。原因：y从100递减到0，每次递减需固定次数的x操作（约11次/递减），总操作数恒定。算法2：i=1;while(i<=n)i=i*s;//假设s是大于1的常数时间复杂度：O(logn)循环每次将i乘以常数s，i的值呈指数增长：1→s→s²→...→sᵏ。循环结束条件：sᵏ>n→k≈logₛ(n)。对数阶复杂度，与底数s无关（换底公式）。算法3：for(i=0;i<n;i++)for(j=0;j<m;j++)a[i][j]=0;时间复杂度：O(n×m)外层循环执行n次，内层循环执行m次。总操作数为n×m，与两个输入规模线性相关。算法4：x=n;y=0;while(x>=(y+1)*(y+1))y++;时间复杂度：O(√n)循环条件：x≥(y+1)²（初始x=n）。y从0递增，直到(y+1)²>n→最大y值≈√n。循环次数为√n级别。一、选择题1.A线性表是n个数据元素的有限序列，可以为空（即n=0）。2.C在顺序表中删除第i个元素（索引从0开始），需将第i+1至第n-1个元素前移，移动元素数为n-i-1。3.D链式存储中，节点地址不要求连续，通过指针链接，地址可连续或不连续。4.C查找成功的平均比较次数为(n+1)/2（等概率下，平均需遍历一半节点）。5.D正确操作顺序：s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;6.A删除p（指向结点m）的后继结点：修改p的next指针，使其指向后继的后继，即p->next=p->next->next。7.B在顺序表中向第i个元素前插入（索引从1开始），需将第i至第n个元素后移，移动元素数为n-i+1。8.Bq是p的前驱，在q和p间插入s：将q的next指向s，s的next指向p，即q->next=s;s->next=p。9.C线性表中，首结点无直接前趋，尾结点无直接后继，故C错误。D正确（如空表或单元素表）。10.A顺序存储支持随机存取（通过地址计算直接访问任意元素）。11.D结点存储地址=基地址+(索引-1)×结点大小，需基地址和结点大小。12.B等概率插入时，平均需移动n/2个结点（插入位置有n+1种可能，平均移动次数为n/2）。13.C顺序表按序号查找时间复杂度为O(1)（随机存取），链表为O(n)；插入、删除和按值查找链表更优。14.B有序单链表插入需先查找位置（平均O(n)），插入操作O(1)，总时间复杂度O(n)。15.C进栈次序A,B,C,D,E：A可（A进A出，B进B出，...）。B可（A进B进B出，C进C出，D进D出，E进E出，A出）。D可（A,B,C,D,E全进，E出，D出，C出，B出，A出）。E先出需所有元素已入栈，栈顶为E，出栈后栈顶为D，不能直接出A（需先出D,C,B），故C不可能。16.C栈顶指针top指向栈顶元素，出栈时top减1（向地址低端移动）。17.B链栈插入：新结点s的next指向原栈顶hs，然后hs更新为s，即s->next=hs;hs=s。18.D循环队列队满条件：(rear+1)%n==front（牺牲一个单元区分队空队满）。19.C循环队列队空条件：rear==front（无元素时指针相等）。20.A链队列删除队首结点：将front指向front的next，即front=front->next。二、填空题1.线性表是一种典型的_________结构。答案：线性解析：线性表是数据元素呈线性排列的数据结构。2.在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移____个元素。答案：n-i+1*解析：插入位置为i（从1开始计数），需将第i个元素及之后的元素后移，共n-i+1个元素。*3.顺序表中逻辑上相邻的元素的物理位置________。答案：相邻解析：顺序存储中，逻辑相邻的元素在物理内存中连续存放。4.要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需_______一个位置，移动过程是从_______向_______依次移动每一个元素。答案：前移；前；后解析：删除后需将后续元素前移填补空位，从被删除元素的下一个位置（前）向表尾（后）逐个移动。5.在线性表的顺序存储中，元素之间的逻辑关系是通过_______决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_______决定的。答案：存储位置；指针解析：顺序存储通过物理相邻体现逻辑关系；链式存储通过指针链接体现逻辑关系。6.在双向链表中，每个结点含有两个指针域，一个指向_______结点，另一个指向_______结点。答案：前驱（或直接前驱）；后继（或直接后继）解析：双向链表的结点包含指向前驱和后继的指针。7.当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_______存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_______存储结构为宜。答案：顺序；链式*解析：顺序存储支持高效随机存取（O(1)），链式存储支持高效插入/删除（O(1)）。*8.顺序表中逻辑上相邻的元素，物理位置____相邻，单链表中逻辑上相邻的元素，物理位置____相邻。答案：一定；不一定解析：顺序存储强制物理相邻；链式存储通过指针链接，物理位置可任意。9.线性表、栈和队列都是_______结构，可以在线性表的______位置插入和删除元素；对于栈只能在_______位置插入和删除元素；对于队列只能在_______位置插入元素和在_______位置删除元素。答案：线性；任何；栈顶；队尾；队头解析：三者均为线性结构；线性表允许任意位置操作；栈遵循LIFO（栈顶操作）；队列遵循FIFO（队尾插入，队头删除）。10.根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_________和_______；而根据指针的联接方式，链表又可分为________和_________。答案：单链表；双链表；循环链表；非循环链表解析：单链表结点含1个指针（后继），双链表含2个指针（前驱和后继）；循环链表的尾结点指向头结点，非循环链表无此特性。11.在单链表中设置头结点的作用是________。答案：简化边界处理（或统一空表/非空表操作）解析：头结点不存储数据，使首元结点的操作与其他结点一致，避免空表特殊处理。12.对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为_______。答案：O(1)；O(n)解析：已知结点p时插入为O(1)；需先遍历查找值为x的结点，平均O(n)。13.对于一个栈作进栈运算时，应先判别栈是否为_______，作退栈运算时，应先判别栈是否为_______，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为_______。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的_______分别设在这片内存空间的两端，这样只有当_______时才产生上溢。答案：满；空；m；栈底；两个栈顶相邻解析：进栈前检查栈满（避免上溢），出栈前检查栈空（避免下溢）；栈满时元素数为最大容量m；共享栈时两栈底在两端，栈顶相向生长，栈顶相遇时上溢。14.设有一空栈，现有输入序列1，2，3，4，5，经过push,push,pop,push,pop,push,push后，输出序列是_________。答案：2,3解析：操作步骤：push→栈：[1]push→栈：[1,2]pop→输出2，栈：[1]push→栈：[1,3]pop→输出3，栈：[1]push→栈：[1,4]push→栈：[1,4,5]输出序列为2,3。15.无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为__________。答案：O(1)*解析：栈的入栈/出栈（O(1)），队列的入队/出队（O(1)），无论顺序（循环队列）或链式存储。*三、简答题1.头指针、头结点、表头结点的区别头指针：指向链表第一个结点的指针（无论是否存在头结点）。若链表为空，头指针为NULL。头结点：附加在链表首元素之前的结点（不存储数据），其指针域指向首元素结点。用于统一空表和非空表的操作。表头结点：链表中第一个存储实际数据的结点（又称首元结点）。总结：头指针指向头结点（若有）或表头结点；头结点是数据域为空的辅助结点；表头结点是实际数据的第一个结点。2.线性表两种存储结构的优缺点顺序存储（顺序表）：优点：随机存取（O(1)时间访问任意元素）；存储密度高（无额外指针开销）。缺点：插入/删除需移动大量元素（O(n)时间）；预分配固定空间，可能浪费或溢出。链式存储（链表）：优点：插入/删除灵活（O(1)时间）；动态分配空间，无需预定义长度。缺点：只能顺序存取（访问元素需O(n)时间）；存储密度低（指针占用额外空间）。3.多表动态变化场景下的存储结构选择选择链式存储结构。理由：表长度动态变化时，链表可高效插入/删除（O(1)时间）。表总数自动改变时，链表动态分配内存，避免顺序表连续空间的限制。4.稳定表快速存取场景下的存储结构选择选择顺序存储结构。理由：顺序表支持随机存取（O(1)时间访问元素）。表总数稳定且少插入/删除，顺序表的缺点影响小。5.单循环链表设置尾指针的优势优于设置头指针。理由：尾指针tail可直接访问尾结点（tail）和头结点（tail->next）。合并链表时：两链表合并仅需修改尾指针（O(1)时间），而头指针需遍历到尾结点（O(n)时间）。6.四个元素的所有出栈序列可能的出栈序列（共14种）：A,B,C,DA,B,D,CA,C,B,DA,C,D,BA,D,C,BB,A,C,DB,A,D,CB,C,A,DB,C,D,AB,D,C,AC,B,A,DC,B,D,AC,D,B,AD,C,B,A注：序列需满足栈的LIFO特性（如D,A,B,C不可能）。7.队列的上溢现象及解决方法上溢现象：队列满时仍进行入队操作导致空间溢出。解决方法：循环队列：利用模运算重用数组空间（需牺牲一个单元区分队空/队满）。链式队列：动态分配结点，无固定大小限制（除非内存耗尽）。动态扩容：顺序队列满时分配更大空间并迁移数据（时间复杂度高）。8.算法功能分析LinkList*Demo(LinkList*L){LinkList*q,*p;if(L&&L->next){//至少有两个结点q=L;//q指向首结点L=L->next;//L指向第二个结点（新头）p=L;//p从新头开始遍历while(p->next)//找到尾结点p=p->next;p->next=q;//原首结点链到尾结点后q->next=NULL;//原首结点成为新尾结点}returnL;//返回新头指针}功能：将无头结点的单链表首结点移至表尾，返回新的表头指针。示例：链表1→2→3→4变为2→3→4→1，返回指向2的指针。四、算法设计题1.无头结点单链表中删除第i个结点voidDeleteNode(LinkList*L,inti){if(i<1)return;//位置无效LinkList*p=L,*q;//删除第1个结点if(i==1){if(L==NULL)return;//空表q=L;L=L->next;//修改头指针free(q);return;}//寻找第i-1个结点intj=1;while(p&&j<i-1){p=p->next;j++;}//检查位置有效性if(p==NULL||p->next==NULL)return;//删除第i个结点q=p->next;p->next=q->next;free(q);}2.单链表求表长intListLength(LinkList*L){intlen=0;LinkList*p=L;while(p!=NULL){len++;p=p->next;}returnlen;}3.带表头链表逆置voidReverseList(LinkList*L){LinkList*p,*q;p=L->next;//p指向首元结点L->next=NULL;//头结点next域置空while(p!=NULL){q=p->next;//保存下一个结点p->next=L->next;//头插法插入pL->next=p;p=q;}}4.链表按值排序（使用prior域）voidSortList(LinkList*head){LinkList*p,*min_pre,*min_node,*sorted=NULL;while(head->next!=NULL){//寻找最小值结点min_pre=head;p=head->next;while(p->next!=NULL){if(p->next->data<min_pre->next->data)min_pre=p;p=p->next;}//移除最小值结点min_node=min_pre->next;min_pre->next=min_node->next;//将结点插入有序链min_node->prior=sorted;sorted=min_node;}//重建链表head->next=sorted;p=head->next;LinkList*prev=NULL;while(p!=NULL){p->next=prev;//反转next指针prev=p;p=p->prior;}}5.有序表删除范围元素voidDeleteRange(LinkList*L,intmin,intmax){LinkList*p=L->next,*pre=L,*q;while(p!=NULL){if(p->data>min&&p->data<max){//删除满足条件的结点q=p;pre->next=p->next;p=p->next;free(q);}else{pre=p;p=p->next;}}}6.无序表删除范围元素voidDeleteRange(LinkList*L,intmin,intmax){LinkList*p=L->next,*pre=L,*q;while(p!=NULL){if(p->data>min&&p->data<max){//删除满足条件的结点q=p;pre->next=p->next;p=p->next;free(q);}else{pre=p;p=p->next;}}}7.循环队列操作（单循环链表，只设队尾指针）//(1)插入元素voidEnQueue(LinkList*rear,ElemTypex){LinkList*s=(LinkList*)malloc(sizeof(LinkList));s->data=x;if(*rear==NULL){//空队列s->next=s;//自环*rear=s;}else{s->next=(*rear)->next;//新结点指向队头(*rear)->next=s;//原队尾指向新结点*rear=s;//更新队尾指针}}//(2)删除元素voidDeQueue(LinkList*rear,ElemType*x){if(*rear==NULL)return;//空队列LinkList*p=(*rear)->next;//p指向队头*x=p->data;if(p==*rear){//只有一个结点free(p);*rear=NULL;}else{(*rear)->next=p->next;//队尾指向新的队头free(p);}}8.递减有序表插入元素voidInsertDesc(SqList*L,ElemTypex){if(L->length>=L->listsize){//扩容处理（此处省略具体实现）}inti=L->length-1;//从后向前查找插入位置while(i>=0&&L->data[i]<x){L->data[i+1]=L->data[i];//元素后移i--;}L->data[i+1]=x;//插入元素L->length++;//表长增加}一、选择题1.答案：C.dceab解析：栈的特点是后进先出（LIFO）。选项A、B、D的输出序列可以通过合理的入栈和出栈操作实现，而选项C中的“dceab”无法实现，因为在“d”出栈后，“c”和“e”必须连续出栈，无法在“e”之前出栈“a”和“b”。2.答案：C.n-i+1解析：如果第一个出栈的元素是n，则栈中的元素是按n,n-1,...,1的顺序入栈的。因此，第i个出栈的元素是n-i+1。3.答案：A.顺序存储结构和链式存储结构解析：栈通常采用顺序存储结构（数组）或链式存储结构（链表）实现。4.答案：C.栈解析：Push和Pop是栈的典型操作，分别用于入栈和出栈。5.答案：C.s->next=HS;HS=s;解析：在链栈中，新结点s插入到栈顶，因此s的next指向当前栈顶HS，然后将HS更新为s。6.答案：B.1,2,3,4解析：队列的特点是先进先出（FIFO），因此出队顺序与入队顺序一致。7.答案：C.只允许在端点处插入和删除元素解析：栈和队列的共同点是插入和删除操作都限制在端点进行，但栈是同一端（栈顶），队列是两端（队尾插入，队头删除）。8.答案：C.栈顶解析：栈的插入和删除操作只能在栈顶进行。9.答案：C.插入和删除解析：栈顶可以进行插入（Push）和删除（Pop）操作。10.答案：D.D解析：元素按A、B、C、D顺序入栈，Pop操作会取出栈顶元素D。11.答案：B.后进先出解析：栈的特点是后进先出（LIFO）。12.答案：B.可变的解析：栈中元素的个数是动态变化的，取决于入栈和出栈操作。13.答案：B.B解析：元素按A、B、C、D顺序入栈，两次Pop操作后，栈顶元素是B。14.答案：A.必须一致解析：栈内元素的类型必须一致，这是由栈的同构性决定的。15.答案：A.已固定解析：顺序栈的空间大小在定义时已固定。16.答案：B.加了限制的解析：栈是一种操作受限的线性表，只能在栈顶进行插入和删除。17.答案：D.插入、删除元素的位置解析：栈与一般线性表的区别在于插入和删除操作的位置受限。18.答案：D.栈解析：栈适合用于检查括号匹配问题，因为可以方便地检查最近的左括号和右括号是否配对。19.答案：C.栈解析：递归调用时，参数和返回地址通过栈来管理。20.答案：A.(rear-front+m)%m解析：循环队列中，元素个数的计算公式为(rear-front+m)%m，可以正确处理队列环绕的情况。---二、名词解释1.栈栈是一种线性数据结构，遵循后进先出（LIFO）的原则。插入和删除操作只能在栈顶进行，主要操作包括Push（入栈）和Pop（出栈）。2.队列队列是一种线性数据结构，遵循先进先出（FIFO）的原则。插入操作在队尾进行，删除操作在队头进行，主要操作包括Enqueue（入队）和Dequeue（出队）。3.循环队列循环队列是队列的一种实现方式，通过将队列的首尾相连形成一个环形结构，以解决顺序队列中“假溢出”的问题。循环队列通过模运算实现指针的循环移动。一、单项选择题1.答案：C.模式匹配是串的一种重要运算解析：-A错误：串是字符的有限序列，不是无限序列。-B错误：空串是长度为0的串，不包含任何字符（包括空格）。-C正确：模式匹配是串的核心运算之一，用于查找子串在主串中的位置。-D错误：串可以采用顺序存储（如数组）或链式存储（如块链结构）。2.答案：B.数据元素是一个字符解析：串的特殊性在于其数据元素是单个字符，而普通线性表的数据元素可以是任意类型。3.答案：B.串中所含字符的个数解析：串的长度是指串中字符的总数，包括空格和其他符号。4.答案：C.模式匹配解析：模式匹配是用于查找子串在主串中首次出现位置的算法，如KMP算法或BF算法。5.答案：B.11解析：串s="data"的长度为4，子串个数为\(\frac{n(n+1)}{2}+1=\frac{4\times5}{2}+1=11\)（包括空串和所有连续字符组合）。---二、填空题1.答案：空串；字符解析：-空串是长度为0的串，不含任何字符。-串的长度是指串中字符的总数。2.答案：由空格组成的串；空格的数量解析：-空格串是由一个或多个空格组成的串（如""）。-其长度是空格的数量，与空串（长度为0）不同。3.答案：长度；相同；子；主解析：-两个串相等的条件是长度相同且对应字符完全相同。-子串是串中任意连续字符组成的序列，原串称为主串。4.答案：3解析：-BF算法（暴力匹配）从主串"structure"的第一个字符开始匹配子串"truc"。-首次匹配成功的位置是第3个字符开始（"struc"中的"truc"），因此返回3（假设下标从0开始则为2，但通常题目描述为从1开始）。5.答案：2解析：-模式串P="abaabc"的next数组计算如下：-next[0]=-1（通常定义为-1或0，视实现而定）-next[1]=0-next[2]=0（"ab"无公共前后缀）-next[3]=1（"aba"的最长公共前后缀为"a"，长度1）-next[4]=1（"abaa"的最长公共前后缀为"a"）-next[5]=2（"abaab"的最长公共前后缀为"ab"，长度2）-因此next[5]=2。一、选择题1.正确答案：C.a[3-1][3]解析：数组

a

定义为

inta[3][4]，表示有3行（行下标范围0到2）和4列（列下标范围0到3）。数组下标从0开始，最大值为n-1。2.正确答案：B.1032解析：根据元素

a[i][j]

的地址计算公式为：基地址+(i*列数+j)*元素大小。在a[2][4]之前，总计12+4=16个元素。偏移量16*2=32，地址1000+32=1032。因此，地址为1032。3.正确答案：D.n(n+1)/2解析：根据对称矩阵压缩存储的特点，数组B中总元素数=1+2+...+n=n(n+1)/2。4.正确答案：B.随机存储解析：稀疏矩阵压缩存储（如三元组）通常只存储非零元素及其位置（如(行,列,值)），元素存储非连续，失去随机存储特性。二、应用题参考答案：压缩存储原理：利用连续相同元素重复出现的特性，用(元素值,重复次数)的二元组序列代替原数组。存储结构：创建一个新的结构数组B[]，每个元素包含：value：原始数组中的元素值。count：该值连续重复的次数。示例：原数组A=[5,5,5,8,8,3,3,3,3]压缩后B=[(5,3),(8,2),(3,4)]。空间节省：原数组空间：O(n)。压缩后空间：O(k)（k为连续重复段的段数）。当重复段远少于n时（如全相同元素时k=1），空间大幅优化。参考答案：x；分析：Head操作取第一个元素x（原子元素）。（2）((x,y),z)分析：Tail操作移除广义表第一个元素(a,b)，剩余元素组成的子表为((x,y),z)。参考答案：算法步骤：初始化累加器sum=0。遍历三元组表中的每个元素：若当前三元组的行号row等于列号col：将value加入sum。返回sum。代码实现（C/C++）：typedefstruct{//三元组结构introw,col;floatvalue;//假设元素为浮点型}Triple;typedefstruct{//三元组表Tripledata[MAXSIZE];intlen;//非零元素个数}TSMatrix;floatdiagonalSum(TSMatrixM){floatsum=0.0;for(inti=0;i<M.len;i++){Triplet=M.data[i];if(t.row==t.col){//判断是否在对角线上sum+=t.value;}}returnsum;}时间复杂度：O(len)，其中len为非零元素个数，远小于n²。一、选择题1.正确答案：B解析：树中结点总数N=度数之和+1。给定度为4的结点20个、度为3的结点10个、度为2的结点1个、度为1的结点10个，度数之和为4×20+3×10+2×1+1×10=80+30+2+10=122。因此，总结点数N=122+1=123。叶子结点个数为123-20-10-1-10=82个。2.正确答案：C解析：叶子结点个数n0=n2+1=8，结点总数N=n0+n1+n2=8+5+7=20。3.正确答案：C解析：该完全二叉树，n0=8，n2=n0-1=7，则n=n0+n1+n2=15+n1。完全二叉树中n1=0或n1=1，则n1=1时结点个数最多，此时n=16。最大高度h==5。4.正确答案：C解析：完全二叉树的叶子结点只能在最下两层，对于本题，结点最多的情况是第6层为倒数第二层，即1～6层构成一个满二叉树，其结点总数为26-1=63。其中第6层有25=32个结点，含8个叶子结点，则另外有32-8=24个非叶子结点，它们中每个结点有两个孩子结点（均为第7层的叶子结点），计48个叶子结点。这样最多的结点个数=63+48=111。5.正确答案：A解析：森林转二叉树时，第一棵树的根作为二叉树的根，其左子树是第一棵树去除根后的子树（结点数为a−1)，右子树是其余树转换的二叉树（结点数为b+c+d)。故二叉树根结点的左子树结点数为a−1。6.正确答案：C森林转二叉树后，无右孩子的结点对应原森林中是其父结点最后一个孩子的结点或最后一棵树的根。森林中有n个非叶子结点，每个非叶子结点恰好有一个最后一个孩子，共n个结点；加上最后一棵树的根（无右孩子），总计n+1个无右孩子的结点。7.正确答案：D解析：高度为3的满二叉树有7个结点：根A，左孩子B，右孩子C；B有左孩子D、右孩子E；C有左孩子F、右孩子G。还原为森林：A为第一棵树根，其左子树转换为子树（B为根，D、E为子），右子树转换为子树（C为根，F、G为子）。包含A的树有结点A、B、D、E，共4个。二、填空题第一个空：11第二个空：6解析：三次树度数之和为3×2+2×1+1×2=6+2+2=10，总结点数=10+1=11，叶子结点数=11−2−1−2=6。第一个空：14解析：根据树的性质，度数之和+1=结点总数，可得树的结点总数N为3×2+2×3+2×4+1=21。叶子结点个数=21-3-2-2=14。3.第一个空：A第二个空：B、E、G、D第三个空：4第四个空：E、F第五个空：A解析：括号表示A(B,C(E,F(G)),D)对应树结构：根：AA的孩子：B、C、DC的孩子：E、FF的孩子：G叶子：B、E、G、D（无孩子）C的孩子：E、FC的双亲：A应用题参考答案：树形表示形式为：对应的先序序列为：abcedfhgij解析：由后序序列echfjigdba（根为a），中序序列ecbhfdjiga（左子树中序ecbhfdjig，右子树空）。递归构建：-左子树后序echfjigdb（根b），中序ecbhfdjig（左子树中序ec，右子树中序hfdjig）。-左子树：中序ec，后序ec（根c，左e）。-右子树：中序hfdjig，后序hfjigd（根d），左子树中序hf（根f，左h），右子树中序jig（根g，左i，i左j）。参考答案：typedefstructnode{chardata;structnode*lchild，*rchild;}BTNode;intNodeNum(BTNode*b){if(b==NULL)return0;elsereturnNodeNum(b->lchild)+NodeNum(b->rchild)+1;}参考答案：typedefstructnode{chardata;structnode*lchild，*rchild;}BTNode;intcount=0; voidLnodenum(BTNode*b，inth，intk){if(b==NULL) return0;else {if(h==k)count++; elseif(h<k) {Lnodenum1(b->lchild，h+1，k);Lnodenum1(b->rchild，h+1，k);}}}参考答案：voidfindMinNode(BTNode*b,char*min_val){if(b==NULL)return;if(b->data<*min_val)*min_val=T->data;findMinNode(b->lchild,min_val);findMinNode(b->rchild,min_val);}charfindMin(BTNode*b){if(b==NULL)return'\0';charmin_val=b->data;findMinNode(b,&min_val);returnmin_val;}参考答案：构造的哈夫曼树为：带权路径长度为：WPL=8+12+12+14+16+18=80哈夫曼编码（左0右1）：a：1010b：1011c：100d：00e：01f：11第7章习题答案一、单项选择题在一个图中，所有顶点的度数之和等于图的边数的____倍。

答案：C.2

解析：在无向图中，每条边贡献两个度数（每个端点一个），因此度数之和是边数的两倍。在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的__倍。

答案：B.1

解析：在有向图中，每条边对应一个入度和一个出度，因此入度之和等于出度之和，且都等于边数。有8个结点的无向图最多有__条边。

答案：B.28

解析：无向完全图的边数为

n(n−1)/2​，代入

n=8得

8×7/2=28。有8个结点的无向连通图最少有___条边。

答案：C.7

解析：无向连通图的最少边数为生成树的边数，即

n−1=8−1=7。有8个结点的有向完全图有__条边。

答案：C.56

解析：有向完全图的边数为

n(n−1)，代入

n=8

得

8×7=56。用邻接表表示图进行广度优先遍历时，通常是采用___来实现算法的。

答案：B.队列

解析：广度优先遍历（BFS）使用队列管理待访问顶点，确保按层次遍历。用邻接表表示图进行深度优先遍历时，通常是采用____来实现算法的。

答案：A.栈

解析：深度优先遍历（DFS）通常使用栈（或递归调用栈）实现，以探索路径深度。深度优先遍历类似于二叉树的

答案：A.先序遍历

解析：DFS的访问顺序（根-子节点）与二叉树的先序遍历（根-左-右）相似。广度优先遍历类似于二叉树的

答案：D.层次遍历

解析：BFS按层次访问顶点，与二叉树的层次遍历一致。任何一个无向连通图的最小生成树

答案：B.一棵或多棵

解析：最小生成树可能不唯一（例如，图中存在相同权重的边时可能有多个），但一定存在。二、填空题图有

邻接矩阵、邻接表

等存储结构，遍历图有

深度优先遍历、广度优先遍历

等方法。有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的

出度。如果n个顶点的图是一个环，则它有

n

棵生成树。(以任意一顶点为起点，得到n-1条边)n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为

O(n2)。n个顶点e条边的图，若采用邻接表存储，则空间复杂度为

O(n+e)。设有一稀疏图G，则G采用

邻接表

存储较省空间。设有一稠密图G，则G采用

邻接矩阵

存储较省空间。图的逆邻接表存储结构只适用于

有向

图。已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是

将邻接矩阵的第i行全部置为0。图的深度优先遍历序列

不唯一。第8章习题答案一、单项选择题如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用()查找法。

答案：C.分块查找

解析：分块查找结合了顺序查找和折半查找的优点，块内可无序（适应动态插入/删除），块间有序（支持较快查找）。对22个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。

答案：C.5

*解析：n=22时，折半查找树的最大高度为5（因

24<22≤25），查找失败时至少需比较5次（最坏情况）。*在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作（）型调整以使其平衡。

答案：D.RR

解析：A的右孩子平衡因子为1（右重），且插入发生在右子树的右子树，故需RR旋转。已知一个有序表(13,18,24,35,47,50,62,83,90,115,134)，当二分查找值为90的元素时，查找成功的比较次数为()。

答案：B.2

*解析：第一次mid=5（值50<90），第二次mid=8（值90），共2次比较。*下面关于哈希查找的说法，不正确的是（）。

答案：A.采用链地址法处理冲突时，查找一个元素的时间是相同的

解析：查找时间取决于链表长度，不同关键字的哈希冲突链长度可能不同，查找时间不一定相同。设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15,38,61,84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（）。

答案：D.9

*解析：H(49)=5（冲突），探测序列：*(5+12)%14=6（冲突，有61）(5−12)%14=4（冲突，有15）(5+22)%14=9（空闲，成功放置）。采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字()。

答案：A.不一定都是同义词

解析：线性探测可能引发“堆积”，探测路径上可能包含非同义词（不同哈希地址的关键字）。由n个数据元素组成的两个表：一个递增有序，一个无序。采用顺序查找算法，对有序表从头开始查找，发现当前元素已不小于待查元素时，停止查找，确定查找不成功，已知查找任一元素的概率是相同的，则在两种表中成功查找()。

答案：B.平均时间两者相同

解析：成功查找时，有序表提前停止仅减少失败比较次数，成功查找的平均比较次数均为

（n+1）/2。对长度为3的顺序表进行查找，若查找第一个元素的概率为1/2，查找第二个元素的概率为1/3,查找第三个元素的概率为1/6,则查找任一元素的平均查找长度为()。

答案：A.5/3

解析：ASL=

(1/2×1)+(1/3×2)+(1/6×3)=1/2+2/3+1/2=5/3​.具有