数据结构c语言程序题 严蔚敏《数据结构(c语言版)习题集》（包括基础部分）.doc...

严蔚敏《数据结构(c语言版)习题集》(包括基础部分).doc

线性表第1章绪论11简述下列术语数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。解数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。12试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。解抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。13设有数据结构D,R，其中，，4,32,1DDRR4,3,2,1DD试按图论中图的画法惯例画出其逻辑结构图。解14试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)。解ADTCOMPLEX{数据对象D{R,I|R,I为实数}数据关系R{}基本操作INITCOMPLEXI1WHILEIJJELSEI}7XNY0//N是不小于1的常数WHILEXY1Y1{Y}8X91Y100WHILEY0{IFX100{X10Y}ELSEX}解1N12N13N14NN1N2121N5112123123NNI12NINININI1112123246N7向下取整8110019假设N为2的乘幂，并且N2，试求下列算法的时间复杂度及变量COUNT的值(以N的函数形式表示)。INTTIMEINTN{COUNT0X2WHILEX438时，22LOG50114判断下列各对函数和，当时，哪个函数增长更快F1，31LN2F74N2，552G3，412FL4，23N52N解1GN快2GN快3FN快4FN快115试用数学归纳法证明16/1212NIN0N2/10XXNNI,1X321NNI421NI1116试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值解INCLUDEVOIDMAIN{INTA,B,CSCANF“DDD“,IFAB{//冒泡排序INTTEMPAABBTEMP}IFBC{INTTEMPBBCCTEMPIFAB{INTTEMPAABBTEMP}}117已知K阶斐波那契序列的定义为，，，，；0F1F02KF1KF，NNN2,试编写求K阶斐波那契序列的第M项值的函数算法，K和M均以值调用的形式在函数参数表中出现。解K0为阶数，N为数列的第N项INTFIBONACCIINTK,INTN{IFKARRSIZE或对某个，使时，NK1INTMAX2K应按出错处理。注意选择你认为较好的出错处理方法。解INCLUDEINCLUDEDEFINEMAXINT65535DEFINEARRSIZE100INTFUNINTIINTMAIN{INTI,KINTAARRSIZECOUTKIFKARRSIZE1EXIT0FORI0IMAXINTEXIT0ELSEAI2IAI1}}FORI0IMAXINTEXIT0ELSECOUTINCLUDEDEFINEN10DOUBLEPOLYNOMAILINTA,INTI,DOUBLEX,INTNINTMAIN{DOUBLEXINTN,IINTANCOUTXCOUTNIFNN1EXIT0COUTAICOUT0RETURNANIPOLYNOMAILA,I1,X,NXELSERETURNAN}本算法的时间复杂度为ON。第2章线性表第一章21描述以下三个概念的区别头指针，头结点，首元结点(第一个元素结点)。解头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。22填空题。解1在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。2顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。3在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。4在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。23在什么情况下用顺序表比链表好解当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。24对以下单链表分别执行下列各程序段，并画出结果示意图。解25画出执行下列各行语句后各指针及链表的示意图。LLINKLISTMALLOCSIZEOFLNODEPLFORI1INEXTLINKLISTMALLOCSIZEOFLNODEPPNEXTPDATAI21}PNEXTNULLFORI4I1IINS_LINKLISTL,I1,I2FORI1INEXTS2PNEXTPNEXTNEXT3PNEXTSNEXT4SNEXTPNEXT5SNEXTL6SNEXTNULL7QP8WHILEPNEXTQPPNEXT9WHILEPNEXTNULLPPNEXT10PQ11PL12LS13LP解A41B711841C512D91627已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。A删除P结点的直接后继结点的语句序列是____________________。B删除P结点的直接前驱结点的语句序列是____________________。C删除P结点的语句序列是____________________。D删除首元结点的语句序列是____________________。E删除尾元结点的语句序列是____________________。1PPNEXT2PNEXTP3PNEXTPNEXTNEXT4PPNEXTNEXT5WHILEPNULLPPNEXT6WHILEQNEXTNULL{PQQQNEXT}7WHILEPNEXTQPPNEXT8WHILEPNEXTNEXTQPPNEXT9WHILEPNEXTNEXTNULLPPNEXT10QP11QPNEXT12PL13LLNEXT14FREEQ解A11314B10128314C10127314D1211314E91131428已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。A在P结点后插入S结点的语句序列是______