数据结构基础教程题及解答

数据结构基础教程习题解答新第1章习题解答一、填空1数据是指所有能够输入到计算机中被计算机加工、处理的 符号 的集合.2可以把计算机处理的数据,笼统地分成 数值 型和 非数值 型两大类.3数据的逻辑结构就是指数据间的 邻接关系 .4数据是由一个个 数据元素 集合而成的.5数据项是数据元素中 不可再分割 的最小标识单位,通常不具备完整、确定的实际意义,只是反映数据元素某一方面的属性.6数据是以 数据元素 为单位存放在内存的,分配给它的内存区域称为 存储结点 .7每个数据元素都具有 完整 、 确定 的实际意义,是数据加工处理的对象.8如果两个数据结点之间有着逻辑上的某种关系,那么就称这两个结点是 邻接 的.9在一个存储结点里,除了要有数据本身的内容外,还要有体现 数据间邻接关系 的内容.10从整体上看,数据在存储器内有两种存放的方式：一是集中存放 在一个连续的 内存存储区中；一是利用存储器中的零星区域, 分散地存放在 内存的各个地方.11在有些书里,数据的存储结构也称为数据的 物理结构 .12基本操作是指算法中那种所需时间与操作数的具体取值 无关 的操作.二、选择1在常见的数据处理中, B 是最基本的处理.A删除B查找C读取D插入2下面给出的名称中, A 不是数据元素的同义词.A字段B结点C顶点D记录3 D 是图状关系的特例.A只有线性关系B只有树型关系C线性关系和树型关系都不D线性关系和树型关系都4链式存储结构中,每个数据的存储结点里 D指向邻接存储结点的指针,用以反映数据间的逻辑关系.A只能有1个B只能有2个C只能有3个D可以有多个5本书将采用 C 来描述算法.A自然语言B流程图即框图C类C语言DC语言6有下面的算法段：for i=0; i k+;其时间复杂度为 B .AOBOCODO三、问答1中国百家姓中的赵、钱、孙、李、周、吴、郑、王等姓氏数据之间,是一种什么样的邻接关系,为什么？答：是一种线性关系,因为这些姓氏之间符合关系的有头有尾,顺序排列的特点.2什么是数据结点？什么是存储结点？它们间有什么关系？答：数据结点即是数据集合中的一个数据元素,存储结点是存放数据结点的内存单位.在存储结点里,不仅要存放数据结点的内容,还要显式或隐式地存放数据结点间的逻辑关系.3为什么说链式存储既提高了存储的利用率,又降低了存储的利用率？答：由于链式存储是通过指针来体现数据元素之间的逻辑关系的,因此,存储结点可以不占用存储器的连续存储区.从这个意义上说,链式存储能够充分利用存储器中小的存储区,因此提高了存储器的利用率.另一方面,链式存储中的存储结点不仅要存放数据元素,还要占用适当的存储区来存放指针,这是一种额外的存储开销.从这个意义上说,链式存储降低了存储器的利用率.4列举几个数据之间具有树型结构的实际例子.答：学校各级管理之间,是一种分支层次结构；一本书的书目,是一种分支层次结构.5判断如下除法过程是否是一个算法,为什么：1开始；2给变量m赋初值5,给变量n赋初值0；3m=m/n；4输出m；5结束.答：因为0不能为除数,本题第3步不具有有效性,所以它不是一个算法.但如果n的初值不为0,则是一个正确的算法.四、应用1用类C语言中的do-while语句,描述输出整数1、2、3、9、10的过程.答：算法编写如下.void num i=1; do printf ; i = i +1; while i;2用类C语言中的if-else语句,编写算法,描述当输入的数据大于等于0时,输出信息：输入的是正数；当输入的数据小于0时,输出信息：输入的是负数.答：算法编写如下.void judge scanf ; if =0 printf ; else printf ;3分析算法段中标有记号#1和#2的基本操作的执行次数：for i=0; i for j=0; j #1 y=1; for k=0; k #2 y=y+1;答：标有记号#1的基本操作的执行次数是：n2；标有记号#2的基本操作的执行次数是：n3.4给出下面3个算法段的时间复杂度：1x+；2for j=1; j x+;3for j=1; j printf ; for k=j; k x+;答：1的时间复杂度为O；2的时间复杂度O；3中printf ;执行次数的数量级为O,x+;执行次数是：n+2+1 = n/2其数量级为O,因此整个算法段的时间复杂度应该是O.第2章习题解答一、填空1当一组数据的逻辑结构呈线性关系时,在数据结构里就称其为 线性表 .2线性表中数据元素的个数n称为线性表的 长度 .3以顺序存储结构实现的线性表,被称为 顺序表 .4以链式存储结构实现的线性表,被称为 链表 .5不带表头结点的链表,是指该链表的表头指针直接指向该链表的 起始结点 .6在一个双链表中,已经由指针ptr指向需要删除的存储结点,则删除该结点所要执行的两条操作是ptr-Prior-Next = ptr-Next; ptr-Next-Prior = ptr-Prior; .7设tail是指向非空、带表头结点的循环单链表的表尾指针.那么,该链表起始结点的存储位置应该表示成 tail-Next-Next .8在一个不带表头结点的非空单链表中,若要在指针qtr所指结点的后面插入一个值为x的结点,则需要执行下列操作：ptr = malloc ;ptr-Data = x ;ptr-Next = qtr-Next ;qtr-Next = ptr ;9顺序表Sq = n1中,每个数据元素需要占用w个存储单元.若m为元素a1的起始地址,那么元素an的存储地址是m+*w.10当线性表的数据元素个数基本稳定、很少进行插入和删除操作,但却要求以最快的速度存取表中的元素时,我们应该对该表采用 顺序 存储结构.二、选择1下面,对非空线性表特点的论述, C 是正确的.A所有结点有且只有一个直接前驱B所有结点有且只有一个直接后继C每个结点至多只有一个直接前驱,至多只有一个直接后继D结点间是按照1对多的邻接关系来维系其逻辑关系的2一般单链表Lk_h为空的判定条件是 A .ALk_h = NULLBLk_h-Next = NULLCLk_h-Next = Lk_hDLk_h != NULL3带表头结点的单链表Lk_h为空的判定条件是 B .ALk_h = NULLBLk_h-Next = NULLCLk_h-Next = Lk_hDLk_h != NULL4往一个顺序表的任一结点前插入一个新数据结点时,平均而言,需要移动 B个结点.AnBn/2Cn+1D/25在一个单链表中,已知qtr所指结点是ptr所指结点的直接前驱.现要在qtr所指结点和ptr所指结点之间插入一个rtr所指的结点,要执行的操作应该是 C .Artr-Next = ptr-Next;ptr-Next = rtr;Bptr-Next = rtr-Next;Cqtr-Next = rtr;rtr-Next = ptr;Dptr-Next = rtr;rtr-Next = qtr-Next;6在一个单链表中,若现在要删除ptr指针所指结点的直接后继结点,则需要执行的操作是 A .Aptr-Next = ptr-Next-Next ;Bptr = ptr-Next; ptr-Next = ptr-Next-Next ;Cptr = ptr-Next-Next ;Dptr-Next ptr ; 7在长度为n的顺序表中,往其第i个元素1in之前插入一个新的元素时,需要往后移动 B 个元素.An-iBn-i+1Cn-i-1Di8在长度为n的顺序表中,删除第i个元素1in时,需要往前移动 A 个元素.An-iBn-i+1Cn-i-1Di9设tail是指向一个非空带表头结点的循环单链表的尾指针.那么,删除链表起始结点的操作应该是 D .Aptr = tail ;Btail = tail-Next ; tail = tail-Next ; free ; free ;Ctail = tail-Next-Next ;Dptr = tail-Next-Next ; Free ; tail-Next-Next = ptr-Next ;Free ; free ;10在单链表中,如果指针ptr所指结点不是链表的尾结点,那么在ptr之后插入由指针qtr所指结点的操作应该是 B .Aqtr-Next = ptr ;Bqtr-Next = ptr-Next ; ptr-Next = qtr ; ptr-Next = qtr ;Cqtr-Next = ptr-Next ;Dptr-Next = qtr ; ptr = qtr ; qtr-Next = ptr ;三、问答1试问,如下的线性表：L = 是有序线性表还是无序线性表？答：L是一个有序线性表.2线性表L第i个存储结点ai的起始地址LOCai可以通过下面的公式计算得到：LOCai= LOCai-1+k其中k表示存储结点的长度.这个公式对吗？为什么？答：这个公式是对的,因为第i个存储结点ai的起始地址LOCai,实际上就是等于第i-1个存储结点ai-1的起始地址LOCai-1加上一个存储结点的长度k得到.3试说明创建顺序表算法Create_Sq 中,Sq_max和Sq_num的不同之处.答：Sq_max代表的是顺序表的最大长度,也就是它最多可以容纳下多少个数据元素,顺序表创建后,Sq_max是一个保持不变的常量；Sq_num代表的是顺序表内当前拥有的数据元素个数,在顺序表创建后,随着对数据元素进行的插入、删除操作,Sq_num将会不断地发生变化.4如何判断一个顺序表是否为空？答：只需判定Sq_num的当前值是多少,如果Sq_num为0,则表示顺序表Sq为空,否则表示该顺序表里有数据元素存在.5在算法2-3里,操作Sq_num=Sq_num -1的作用是什么？没有它行吗？答：该操作是非常重要的,因为顺序表里当前拥有的元素个数是通过Sq_num来记录的,删除了一个元素,Sq_num必须减1,这样才能正确反映出删除后表中元素的个数.所以,没有这个操作是不行的.6在算法2-9里,如果现在是把一个结点插入到单链表尾结点的后面.按照算法的描述,能够保证插入后最后一个结点的Next域为吗？答：能够.因为原来ptr-Next里是,做了第1步操作：qtr-Next = ptr-Next ;后,就是把插入结点的Next域置为.7在一个单链表中,为了删除指针ptr所指的结点,有人编写了下面的操作序列.读懂并加以理解.试问,编写者能够达到目的吗？其思想是什么？x = ptr-Data ;qtr = ptr-Next ;ptr-Data = ptr-Next-Data ;ptr-Next = ptr-Next-Next ;free ;答：能够达到删除指针ptr所指结点的目的.编写者的思想是不去直接删除ptr所指的结点,而是在把ptr直接后继的Data域内容写入ptr所指结点的Data域之后,把它的直接后继删除.对于单链表来说,得到一个结点的直接后继容易,得到它的直接前驱难,所以这样的设计是有其可取之处的.8在一个单链表中,为了在指针ptr所指结点之前插入一个由指针qtr所指的结点,有人编写了下面的操作序列,其中temp是一个临时工作单元.读懂并加以理解.试问,编写者能够达到目的吗？其思想是什么？qtr-Next = ptr-Next ;ptr-Next = qtr ;temp = ptr-Data ;p-Data = qtr-Data ;qtr-Data = temp ;答：能够达到在指针ptr所指结点之前插入一个由指针qtr所指结点的目的.编写者的思想是考虑到在单链表中得到一个结点的前驱信息较为困难,因此在这里先把qtr所指结点插入到ptr所指结点的后面,暂时成为它的直接后继.然后通过临时工作单元temp,将ptr与qtr所指结点的Data域内容进行交换,从而达到插入的目的.9打算形成一个有表头结点的循环双链表,初始时除了每个结点的Next域已经好外,它们的Prior域还都是空的.有人编写了下面的算法,试图完成Prior域的：Com_Cd ptr = Cd_h-Next ; qtr = Cd_h ; while ptr -Prior = qtr ; qtr = ptr ; ptr = ptr-Next ;Cd_h-Prior = qtr ;读懂并理解它,解释为什么能够完成各结点的Prior域的？答：算法中用两个指针ptr和qtr配合,从头到尾扫描这个循环双链表,以达到让每个结点的Prior域指向其直接前驱的目的.四、应用1设计一个计算表头指针为Lk_h的单链表长度即结点个数的算法.答：算法设计如下：Length_Lk n = 0 ; ptr = Lk_h ;/* ptr指向起始结点 */ while ptr = ptr-Next ; n=n+1 ;/* n为结点计数单元 */return ;2用总是在表的头部插入整数结点的方法建立一个单链表,当输入为0时,建表过程结束.答：算法设计如下：Clink Lk_h = NULL; scanf ; while ptr = malloc ;ptr-Data = x;ptr-Next = Lk_h;Lk_h = ptr;scanf ;return Lk_h;3一个不带表头结点的循环双链表Ck的表头指针为Ck_h,要在指针ptr指向处前插入一个rtr所指结点.模仿图2-21,对一般插入位置标示出下面4个操作步骤：rtr-Next = ptr ;rtr-Prior = ptr-Prior ;ptr-Prior-Next = rtr ;ptr-Prior = rtr ;答：4个操作步骤的具体功能体现如下图所示.4试设计一个算法copy ,将一个带表头结点的、以Ck_h1为表头指针的单链表Ck1的内容,复制到一个不带表头结点的、以Ck_h2为表头指针的单链表Ck2中.答：算法具体如下.Copy ptr = Ck_h1-Next ; qtr = Ck_h2 ; while rtr = malloc ;rtr-Data = ptr-Data ;qtr-Next = rtr ;qtr = rtr ;ptr = ptr-Next ;qtr-Next = NULL ;5已知一个带表头结点的递增单链表.试编写一个算法,功能是从表中去除值大于min、且值小于max的数据元素.假定表中存在这样的元素答：所需算法编写如下.Del_Sq ptr = Lk_h-Next ;/* ptr指向链表的起始结点 */ while & Data /* 跳过所有值Next ;while & Data /* 若结点值Next ;qtr-Next = ptr ;/* qtr指出第1个大于max的结点位置,完成 */6已知一个带表头结点的无序单链表.试编写一个算法,功能是从表中去除所有值大于min、且值小于max的数据元素.答：所需算法编写如下,其中指针ptr总是指向当前被检查的结点,qtr总是指向被检查结点的直接前驱.Del_Lk ptr = Lk_h-Next ;/* ptr指向单链表的起始结点 */ while /* 扫视直到链尾结点 */ if Data | Data = max/* 不满足删除条件 */ qtr = ptr ;/* 往后移动qtr和ptr */ ptr = ptr-Next ;else/* 删除ptr所指结点,往后移动ptr */ qtr-Next = ptr-Next ; free ; ptr = qtr-Next ;7一个单链表Lk的表头指针为Lk_h,不同结点的Data域值有可能相同.编写一个算法,功能是计算出Data域值为x的结点的个数.答：算法应该遍历链表的每一个结点,遇到一个结点的Data域值为x时,计数器n就加1.最后返回计数器n.Count_Lk n = 0 ; ptr = Lk_h ; while if Data = x n = n+1 ; ptr = ptr-Nextreturn ;第3章习题解答一、填空1限定插入和删除操作只能在一端进行的线性表,被称为是 栈 .2如果在顺序栈满时仍打算进行进栈操作,就称为发生了 上溢 出错.3如果在顺序栈空时仍打算进行出栈操作,就称为发生了 下溢 出错.4在具有n个数据结点的循环队列中,队满时共有n-1 个数据元素.5如果操作顺序是先让字母A、B、C进栈,做两次出栈；再让字母D、E、F进栈,做一次出栈；最后让字母G进栈,做三次出栈.最终这个堆栈从栈顶到栈底的余留元素应该是 DA .6中缀表达式-c/对应的后缀表达式是 ab+cde+/- .7函数的递归调用有两种形式：如果一个函数是直接调用自己,就称其为 直接 递归调用；如果一个函数是通过另一个函数来调用自己,就称其为 间接 递归调用.8设某栈的元素输入顺序是1、2、3、4、5,想得到4、3、5、2、1的输出顺序.那么push、pop的操作序列应该是 push、push、push、push、pop、pop、push、pop、pop、pop .9设链栈的栈顶指针为Ls_top,那么它非空的条件应该是 Ls_top != NULL .10队列中,允许进行删除的一端称为 队首 .二、选择1一个栈的元素进栈序列是a、b、c、d、e,那么下面的 C 不能做为一个出栈序列.Ae、d、c、b、aBd、e、c、b、aCd、c、e、a、bDa、b、c、d、e2判定一个顺序队列Qs最多有n个元素为空的条件是 C .AQs_rear-Qs_front = n*sizeBQs_rear-Qs_front+1 = n*sizeCQs_front = Qs_rearDQs_front = Qs_rear+size3判定一个顺序队列Qs最多有n个元素真满的条件是 A .AQs_rear-Qs_front = n*sizeBQs_rear-Qs_front+1 = n*sizeCQs_front = Qs_rearDQs_front = Qs_rear+size4在一个链式队列Lq中,Lq_front和Lq_rear分别为队首、队尾指针.现在由指针ptr所指结点要进队,则插入操作应该是 B .ALq_front-Next = ptr; Lq_front = ptr;BLq_rear-Next = ptr; Lq_rear = ptr;Cptr-Next = Lq_rear; Lq_rear = ptr;Dptr-Next = Lq_front; Lq_front = ptr;5链栈与顺序栈相比,一个较为明显的优点是 D .A通常不会出现栈空的情形B插入操作更加便利C删除操作更加便利D通常不会出现栈满的情形6向链栈插入一个结点时,操作顺序应该是 C .A先修改栈顶指针,再插入结点B无须修改栈顶指针C先插入结点,再修改栈顶指针D谁先谁后没有关系7从链栈中删除一个结点时,操作顺序应该是 A .A先保存被删结点的值,再修改栈顶指针B先修改栈顶指针,再保存被删结点的值C无须修改栈顶指针的值D谁先谁后没有关系8一个循环队列的最大容量为m+1,front为队首指针,rear为队尾指针.那么进队操作时求队位号应该使用公式 D .ACq_front = %mBCq_front = %CCq_rear = %mDCq_rear = %9在一个循环顺序队列里,队首指针Cq_front总是指向 B .A队首元素B队首元素的前一个队位C任意位置D队首元素的后一个队位10若一个栈的进栈序列是1、2、3、4,那么要求出栈序列为3、2、1、4时,进、出栈操作的顺序应该是 A .注：所给顺序中,I表示进栈操作,O表示出栈操作AIIIOOOIOBIOIOIOIOCIIOOIOIODIOIIIOOO三、问答1若元素进栈的序列是1、2、3、n,有一个出栈序列的第1个元素是n.那么,这个出栈序列的第i个元素是什么？答：由于栈具有先进后出的特性,因此只有将1、2、3、n依次都进栈后,出栈序列的第1个元素才能是n.所以,在这个出栈序列里,第个i元素应该是n-i+1.2设元素进栈的次序是a,b,c,d,e.试问,在下面所列的6种元素序列里,哪些可以是这个栈的出栈序列？Ac,e,a,b,dBc,b,a,d,eCd,c,a,b,eDa,c,b,e,dEa,b,c,d,eFe,a,b,c,d答：对A进行分析.由于是c第1个出栈,因此b必须先于a出栈.但所给序列里,a却先于b出栈,故A不能是该栈的出栈序列.对C进行分析.由于是d第1个出栈,因此a、b、c三者出栈的顺序必须是c、b、a.但所给序列里,a却先于b出栈,故C不能是该栈的出栈序列.对F进行分析.由于是e第1个出栈,因此a、b、c、d四者出栈的顺序必须是d、c、b、a.但所给序列里,它们的出栈顺序全乱了,故F不能是该栈的出栈序列.因此,所列的6种元素序列里,只有B、D、E可以是这个栈的出栈序列.3有一个顺序栈Ss,其栈顶指针为Ss_top,栈底指针为Ss_bottom.阅读下面给出的算法,其中的两条prinf函数的输出结果各是什么？算法中的Push_Ss表示将ch里的元素进栈,Pop_Ss表示将栈顶元素出栈,存入ch中print for ch = A; ch Push_Ss ;printf ;while Pop_Ss; printf ;答：第1条printf的输出是前13个英文大写字母ABCDEFGHIJKLM,第2条printf输出的是前面输出的倒置,即MLKJIHGFEDCBA.4设有6个元素a1、a2、a3、a4、a5、a6,它们以此顺序依次进栈.假定要求它们的出栈顺序是a4、a3、a2、a6、a5、a1,那么应该如何安排push和pop操作序列？ 答：所需的push和pop操作序列如下：push,push,push,push,pop,pop,pop,push,push,pop,pop,pop5有中缀表达式a / b / c / .有人将其转化为相应的后缀表达式是abcde/.这一转化结果对吗？ 答：转化结果是对的.6试述栈与队列各自具有什么样的逻辑特点？它们之间又有什么共同点？答：对于栈来说,由于只能在栈顶处进行插入和删除操作,这就使得数据元素到达栈即往栈里插入元素的顺序与数据元素离开栈即从栈里删除元素的顺序恰好相反.所以,堆栈的逻辑特点是后进先出LIFO,或先进后出FILO.而对队列来说,插入在一端进行,删除在另一端进行,这就使得数据元素到达队列即往队列里插入元素的顺序与数据元素离开队列即从队列里删除元素的顺序是完全一致的.所以,队列的逻辑特点是先进先出FIFO或后进后出LILO.它们之间的共同之处是插入和删除只能在表的端点处进行要知道,对于线性表,可以在表的任何位置处插入和删除.7有一个顺序队列,最大容量为5.初始时有Qs_front = Qs_rear = 0.画出做下列操作时队列与其首、尾指针的变化情况.若不能进队时就停止,并简述原因.1d、e、b进队2d、e出队 3i、j进队4b出队5n、o、p进队答：队列与其首、尾指针的变化情况如下图所示.在做5时,由于队满假溢出,故操作停止.8有一个递归函数Write,定义如下：Write if Write ; for j=1; j printf ; printf ;试问,Write的输出结果是什么？答：输出结果为：12 23 3 34 4 4 45 5 5 5 5四、应用1编写一个判顺序栈空的算法.要求是如果栈空,返回1,否则返回0.答：算法设计如下：Empty_Ss if /* 栈空 */ return ; else/* 栈不空 */ return ;2编写一个算法,它能够输出顺序队列Qs上所有元素的值.答：算法编写如下：Print_Qs if /* 队列空！*/ printf ; else/* 队列非空！*/ qtr = Qs_front ; while qtr printf ; qtr+ ;3编写一个算法,它能够取得链式队列首元素的值.答：取得链式队列首元素的值,只有在队列非空的前途下才有意义.算法编写如下.Getf_Lq if /* 队列空！*/ printf ; else/* 队列非空！*/ ptr = Lq_front-Next ; x = ptr-Data ; return ;4有五个人顺序坐在一起.问第5个人多少岁,回答说比第4个人大2岁；问第4个人多少岁,回答说比第3个人大2岁；问第3个人多少岁,回答说比第2个人大2岁；问第2个人多少岁,回答说比第1个人大2岁；问第1个人多少岁,回答说是10岁.试给出该递归的公式、结束条件,并编写出相应的递归算法.答：递归公式为：age=age+22=n=5递归的结束条件是：age=10相应算法为：Age if return ; else x=age+2 ; return ;5将中缀表达式转化为后缀表达式的方法类似于中缀表达式求值.具体地,要开辟一个运算符栈op和一个数组st.在自左至右扫描算术表达式时,遇到操作数就直接顺序存入st；遇到运算符时就与op栈顶元素比较,高则进栈,不高则让栈顶元素出栈,存入st,然后该运算符再次去与新的op栈顶元素比较.最后,在数组st里形成所需要的后缀表达式.试用这种方法,用图示将中缀表达式5+8*3-2转化成为相应的后缀表达式.答：相应的后缀表达式是583*+2-,其图示如下.6语言编译时,总是先将中缀表达式转化成为后缀表达式,然后再计算后缀表达式的值,因为后缀表达式已经去除了括号,没有了运算符的优先级.计算后缀表达式的方法是只开辟一个对象栈ob,当从左往右扫描后缀表达式时,每遇到操作数就让其进入ob栈,每遇到运算符就从ob栈里弹出两个操作数进行当前的计算,并将计算结果进ob栈.该过程直至整个表达式结束.ob栈的栈顶值就是最终结果.试用图示计算后缀表达式583*+2-的值.答：计算结果为27,其图示如下.第4章习题解答一、填空1字符串是一种特殊的线性表,特殊在于它的数据元素只能是 字符 ,特殊在于串可以作为一个 整体 参与所需要的处理.2空格串是由 空格 组成的串,空串是 不含任何字符 的串,因此空格串和空串不是一个概念.3字符串中任意多个 连续 字符所组成的子序列,被称作是这个串的子串,这个字符串本身则称为主串.4我们说两个字符串相等,在计算机内部实际上是通过对相应位置上字符 ASCII 码的比较而得到的结论.5设有串s=I am a teacher.该串的长度是 14 .6设有三个串：s1=Good,s2=,s3=bye!.则s1、s2、s3连接后的结果串应该是Good bye! .7所谓数组,是指nn1个具有 相同 类型的数据的有序集合.8矩阵与通常所说的 二维 数组有关.9所谓 特殊矩阵 ,是指那些元素在矩阵中的分布具有一定规律性的矩阵；而矩阵中的零元素个数远远多于非零元素的个数,但非零元素的分布却没有规律,这样的矩阵被称为 稀疏矩阵 .10在一个n阶方阵A中,若所有元素都有性质：aij = aji ,就称其为 对称 矩阵.二、选择1设有两个串s1和s2.求s2在s1中首次出现的位置的操作称为 B .A连接B模式匹配C求子串D求串长2有串：,那么它的长度是 B .A0B1C2D33设有串s1=ABCDEFG和s2=PQRST.已知：算法con返回串x和y的连接串；subs返回串s的第i个字符开始往后j个字符组成的子串；len返回串s的长度.那么,consubss1, 2, len, subss1, len, 2的操作结果是串 D .ABCDEFBBCDEFGCBCPQRSTDBCDEFEF4设有一个8阶的对称矩阵A,采用以行优先的方式压缩存储.a11为第1个元素,其存储地址为1,每个元素占一个地址空间.试问元素a85的地址是 A .A33B30C13D235一个m*m的对称矩阵,如果以行优先的方式压缩存入内存.那么所需存储区的容量应该是 C .Am*/2Bm*m/2Cm*/2D*/26二维数组M的每个元素含4个字符每个字符占用一个存储单元,行下标i从1变到5,列下标j从1变到6.那么按行顺序存储时元素M46的起始地址与M按列顺序存储时元素 B 的起始地址相同.AM35BM45CM46DM557二维数组M中的每个元素占用3个存储单元,行下标i从1变到8,列下标j从1变到10.现从首地址为SA的存储区开始存放A.那么该数组以行优先存放时,元素A85的起始地址应该是 C .ASA+141BSA+180CSA+222DSA+2258设有一个5阶上三角矩阵A,将其元素按列优先顺序存放在一维数组B中.已知每个元素占用2个存储单元,B1的地址是100.那么A34的地址是 A .A116B118C120D122分析：把一个上三角矩阵按列优先顺序存放在一个一维数组B中,元素的顺序是：a11a12a22a13A3,4的地址=100+a34前面的元素个数*2=100+前3列的个数+本列a34前面的个数*2=100+1+2+3+2*2=116 三、问答1为什么可以把二维数组视为是一种线性结构？答：实际上,二维数组是一种较为复杂的数据结构,数据元素之间的关系并不是线性的.不过,如果我们把它看作是其每个元素为一维数组的一个一维数组,那么就可以把二维数组视为是线性表的一种推广因为一维数组即是线性表,因此可以说它的数据元素间的逻辑关系呈现出的是一种线性结构.2图4-34a所示为一个特殊矩阵A55,这种形式的矩阵被称作是带状矩阵,因为它的非零元素都分布在以主对角线为中心的一个带状区域里,其他位置上的元素全部为0.可以以行优先的方式,将其压缩存储到一个一维数组里,如图4-34b所示.试找出元素下标i、j与存储序号k间的对应关系.图4-34 带状矩阵答：压缩存储元素下标i、j与存储序号k间的对应关系是：k = 2*i + j 23一个稀疏矩阵如图4-35所示.试问,它对应的三元组表是什么？图4-35 稀疏矩阵示例答：它所对应的三元组表如下.四、应用1请将算法4-1改为用while循环来实现.答：改写的算法4-1可以是如下所示.Concat_St char St3maxsize;/* 创建一个新的顺序串为空 */ St3_len=0; if maxsize+1/* 新串放不下两个串 */ printf; return; else i=1； while i St3i=St1i; i+;j=1;while j St3j+St1_len=St2j; j+;St3_Len=St1_len+St2_len;St3St3_len+1= 0;return;2算法4-2也可以这样来描述,直接核对相应位置上的字符是否相同,然后再分别情况做出判断：一是有不相同的字符出现,一是有一个字符串比另一个字符串长,最后则是两个串完全相等.按照这样的设计,改写算法4-2.答：按照这样的设计,算法4-2的描述如下.Equal_St i=1; while /* 两串进行比较 */ if /* 相等,继续比较 */ i+; else/* 不等,强制退出 */ black; if /* 比较是由于相应位置上的字符不同而结束 */ return ; else if /* 比较是由于长度不同而结束 */ return ; else return ; 3算法：Trans_Sti=1； While if Sti=ch2；i+； 是通过while循环来实现将顺序串St中所有的字符ch1改为字符ch2的.请改写成用for循环来实现相同的功能.答：用for 循环改写的算法如下.Trans_St for i=1; i if Sti = ch2;4编写一个算法,将顺序串St中所有的大写字母全部换成小写字母.答：算法编写如下.Catosm_St for i=1; i if A&Sti Sti=Sti+32;5已知顺序串St,编写一个算法,将其中第i个字符开始连续的j个字符删除.提示：先要判断所给参数是否合理,然后通过将第i+j开始往后的字符全部移动j个位置,完成删除的功能答：算法编写如下.Moveij if i+j for k=i+j; k/* 将i+j开始往后的所有字符前移j个位置 */ Stk-j=Stk; St_len=St_len-j;/* 修改St的长度 */ StSt_len= 0;/* 安放新的串结束符 */elseprintf ; 6在算法4-12的最后,为了释放被删结点使用的存储空间,先做了操作：ptr-Next = NULL;把由指针ptr指向的最后一个要释放空间的结点的Next域设置为NULL,然后通过while循环完成释放.其实,由于知道要释放空间的结点共有m个,因此可以取消这一操作,改用for循环通过m来控制释放空间的结点个数.请试着按照这一思路改写那一小段算法.答：改写一小段算法如下.for j=1; j ptr=rtr; rtr=rtr-Next; free;7编写一个算法,功能是复制一个链串.答：复制一个完整的链串,是一件比较容易的事情.其算法起名为Copy_Lt,参数为Lt1.具体编写如下.Copy_Ltptr=Lt1_h;rtr=malloc;rtr-Data=ptr-Data;Lt2_h=rtr;ptr=ptr-Next;while qtr=malloc; qtr-Data=ptr-Data; rtr-Next=qtr; ptr=ptr-Next;rtr-Next=NULL;return;算法是通过while循环,不断修改指针ptr,以便指向链串Lt1的各个结点；指针rtr总是指向当前已形成的新链串Lt2的最后一个结点；用指针qtr指向刚申请到的新存储结点,并把它链入到rtr所指结点的后面.8已知两个mn的矩阵A和B.编写一个算法,求C=A+B.即C也是一个mn的矩阵,其元素满足条件：cij = aij + bij1im,1jn答：算法名为Add_Mt,参数为A,B,C.Add_Mt for i=1; i for j=1; j Cij = Aij + Bij;第5章习题解答此处树的高度不计算根节点一、填空1结点数为7的二叉树的高度最矮是 2 ,最高是 6 .2给定二叉树的结点数,要使树高为最大,那么该树应该是 单枝 形状.3给定二叉树的结点数,要使树高为最矮,那么该树应该是 完全二叉树 形状.4如果一棵满二叉树的深度为6,那么它共有 127 个结点,有 64 个叶结点.5有15个结点的二叉树,最少有 1 个叶结点,最多有 8 个叶结点.6由n个带权值的叶结点生成的哈夫曼树,最终共有 2n-1个结点.7将一棵完全二叉树按层次进行编号.那么,对编号为i的结点,如果有左孩子,则左孩子的编号应该是 2i；如果有右孩子,则右孩子的编号应该是 2i+1 .8若二叉树共有n个结点,采用二叉链表存储结构.那么在所有存储结点里,一共会有 2n 个指针域,其中有n+1 个指针域是空的. 9深度为5的二叉树,至多有 31 个结点.10在二叉树中,有一个结点具有左、右两个孩子.那么在中序遍历序列里,它的右孩子一定排在它的 右 边.二、选择1在所给的4棵二叉树中, C 不是完全二叉树.2把一棵深度为3的左单支二叉树改造成完全二叉树时,要增添 D 个空结点.A10B8C6D4 3设有一棵5个结点的二叉树,其先序遍历序列为：A-B-C-D-E,中序遍历序列为：B-A-D-C-E,那么它的后序遍历序列为 B .AA-B-D-E-CBB-D-E-C-ACD-E-C-A-BDA-B-C-D-E 4将一棵有50个结点的完全二叉树按层编号,那么编号为25的结点是 B .A无左、右孩子B有左孩子,无右孩子C有右孩子,无左孩子D有左、有孩子 5深度为6的二叉树,最多可以有 A 个结点.A63B64C127D128 6在一棵非空二叉树的中序遍历序列里,根结点的右边 D 结点.A只有左子树上的部分B只有左子树上的所有C只有右子树上的部分D只有右子树上的所有 7在任何一棵二叉树的各种遍历序列中,叶结点的相对次序是 A .A不发生变化B发生变化C不能确定D以上都不对 8权值为1、2、6、8的四个结点,所构造的哈夫曼树的带权路径长度是 D .A18B28C19D29 9一棵二叉树度2的结点数为7,度1的结点数为6.那么它的叶结点数是 C .A6B7C8D9 10在一棵二叉树中,第5层上的结点数最多是 C 个.A8B15C16D32 三、问答1试问满二叉树与完全二叉树之间有何关系？答：由满二叉树与完全二叉树的定义可知,满二叉树一定是一棵完全二叉树,但完全二叉树却不一定是一棵满二叉树.如果一棵二叉树不是完全二叉树,那么它绝对不可能是一棵满二叉树.这就是满二叉树与完全二叉树之间的关系.2请画出由3个结点构成的所有二叉树,它们的高度分别是多少？答：大小为3的不同的二叉树共有5种,如下图所示.其中,4棵树的高度为2,1棵树的高度为1.3一棵高度为3的满二叉树有多少个叶结点？有多少个度为2的结点？总共有多少个结点？答：有23=8个叶结点,有度为2的结点23-1=7个,总共有23+1-1=24-1=15个结点.4有人说,任何一棵非空满二叉树,它的叶结点数等于其分支结点数加1.这样的一个结论正确吗？请说明理由.提示：利用性质5-3答：在我们介绍的二叉树性质中,只有性质5-3是涉与叶结点数与度为2的分支结点数的关系的.对于满二叉树来说,所有的分支结点都是度为2的结点.因此,正好可以直接利用性质5-3得出所需要的结论.所以,此人说的结论是完全正确的.5有人说,有一棵结点数为n1的二叉树,只包含