数据结构及应用c语言描述答案

回顾第一章知识要点基本概论数据、数据元素、数据项、数据对象数据结构D,S逻辑结构线性结构、树形结构、图形结构、集合结构存储结构顺序存储、链式存储、索引存储、散列存储运算初始化、查找、插入、删除、遍历等抽象数据类型（D,S,P）回顾第二章知识要点算法定义及特性算法效率分析时间复杂度用语句频度总和的数量级描述空间复杂度用占有存储空间的数量级描述回顾第三章知识要点C语言重点内容参数传递、结构类型、指针递归直接递归、间接递归存储分配方式静态分配（全局静态变量区）、动态分配（堆区）、自动分配（栈区）总结重点了解数据、数据元素、数据对象、数据结构、数据结构的逻辑结构、数据的存储结构及抽象数据类型概念，熟悉C语言中指针、结构体，学会分析时间复杂度。13章习题1113见教材14试述数据的逻辑结构与存储结构之间的区别与联系。答数据结构包括数据逻辑结构和数据物理结构两个层次，两者是密切相关、相辅相成的。数据的逻辑结构是对数据元素之间存在的逻辑关系的一种抽象描述；数据的物理结构则为其逻辑结构在计算机中的存储表示或实现。一种逻辑结构可映射成不同的存储结构，不同的存储实现方法其算法不同，实现的效率也不同。16什么是抽象数据类型它有什么作用答抽象数据类型（ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。抽象数据类型是用户定义的数据类型，使得其使用和实现分类，提高软件的复用率。21试述算法和程序的区别。答算法是指解决问题的一种方法或一个过程，即由若干条指令组成的有穷序列。程序是算法用某种程序设计语言的具体实现。算法中指令的执行必须是有穷性的，而程序可以不满足此要求。24判断下述计算过程是否是一个算法STEP1开始STEP2NJII1ELSEJJ1TNON2INTRECINTNIFNTYPEDEFSTRUCTINTNOCHARNAME8CHARSEX2INTAGECHARCLS14INTMATHINTENGLISHINTCHINESESTUDENTVOIDMAINSTUDENTST15INTI,J11,J21,J31,AVG10,AVG20,AVG30,MAX10,MAX20,MAX30FORI0ISTINOSTINAMESTISEXSTIAGESTICLSSTIMATHSTIENGLISHSTICHINESEFORI0IMAX1MAX1STIMATHJ1IIFSTIENGLISHMAX2MAX2STIMATHJ2IIFSTICHINESEMAX3MAX3STIMATHJ3IAVG1AVG1/15AVG2AVG2/15AVG3AVG3/15COUTNEXTLINKLISTMALLOCSIZEOFLNODEPPNEXTPDATAI21PNEXTNULLFORI4I1IINS_LINKLISTL,I1,I2FORI1INEXTNULL1、不带头结点的单链表P为空的判断条件是C、PNEXTPD、PNULL（）A、PNEXTNULLB、PNULLC、PNEXTHEADD、PHEAD2、非空循环单链表HEAD的尾结点（由P指向）满足（）A、N个结点B、N/2个结点C、N1/2个结点D、N1/2个结点3、在N个结点的单链表中查找等于X的结点，需平均比较（）A、PNEXTPNEXTNEXTB、PPNEXTPNEXTPNEXTNEXTC、PNEXTPNEXTD、PPNEXTNEXT4、一个单链表中若删除P所指的后继结点，则执行（）A、SNEXTPNEXTPNEXTSB、PNEXTSNEXTSNEXTPC、QNEXTSSNEXTPD、PNEXTSSNEXTQ5、某单链表中Q是P的前趋，若Q和P之间插入结点S则（）ACDACA、必须是连续的B、部分地址必须是连续的6、线性表采用链式存储，要求所用的存储地址C、一定不是连续的D、连续与否都可以（）A、数据项B、数据对象C、数据元素D、表元素7、线性表是具有N个（）的有限序列（）A、O1B、ONC、ONND、OLOG2N8、在一有N个结点的有序单链表中插入一结点的时间复杂度（）A、数据项B、数据对象C、数据元素D、数据信息9、数据的最小单位是（）A、PPRIORPNEXTPB、PPRIORPPNEXTNULLC、PPRIORPNEXTNULLD、PPRIORNULLPNEXTP10、双向循环链表P判断为空的条件是（）DCBAA二、填空题（请用正确答案填充下列空白）1、顺序表中插入或删除一个元素，需要平均移动元素，具体移动元素的个数与有关；2、单链表中设置头结点的作用是；3、在非空双向循环链表中的结点Q前插入结点P的过程如下，补充完整PPRIORQPRIOR_PNEXTQ_4、在单链表中首元结点外任一结点的存储位置是由指示的；5、链式存储结构既可以通过来实现也可以通过来实现；6、在双向链表中，每个结点都有两个指针域，其中一个指向另一个指向；6、程序段I1WHILEIPRIORNEXTP_QPRIORP前一结点指针指针数组下标前驱后继OLOG2N三、算法解析（请用正确答案填充下列程序段中的空白）1、输入一系列整数，以“0”为输入结束标志，将这些整数域建立一个单链表。试写出具体算法。VOIDCREATNODEHEAD,P,SINTX,CYCLEHEADNODEMALLOCSIZEOFNODEPHEADWHILECYCLESCANF“D”,IFX0SNODEMALLOCSIZEOFNODE_ELSECYCLE0_；_FREEP线性结构操作受限的线性表栈、队列线性结构线性表数据元素受限的线性表串线性表回顾第四章线性表知识要点1、线性表类型的定义（A1,A2,AN）2、线性表的存储形式顺序存储和链式存储方式，以及各自的优缺点顺序存储连续存储单元存储，分静态和动态2种链式存储单链表、静态链表、双链表、循环链表3、线性表的应用一元多项式相加第四章习题42请给出下述要求的判断条件（1）以HEAD为头指针、不带头结点的单链表为空的条件是什么不为空的条件是什么为空HEADNULL不为空HEADNULL2以HEAD为头指针、带头结点的单链表为空的条件是什么不为空的条件是什么为空HEADNEXTNULL不为空HEADNEXTNULL3以HEAD为头指针、不带头结点的单链环为空的条件是什么不为空的条件是什么为空HEADNULL不为空HEADNULL4以HEAD为头指针、带头结点的单链环为空的条件是什么不为空的条件是什么为空HEADNEXTHEAD不为空HEADNEXTHEAD42请给出下述要求的判断条件（5）以HEAD为头指针、不带头结点的单链表仅含有两个结点的条件是什么HEADNEXTNEXTNULL；6以HEAD为头指针、带头结点的单链表仅含有两个结点的条件是什么HEADNEXTNEXTNEXTNULL；7以HEAD为头指针、不带头结点的单链环仅含有两个结点的条件是什么HEADNEXTNEXTHEAD；8以HEAD为头指针、带头结点的单链环仅含有两个结点的条件是什么HEADNEXTNEXTNEXTHEAD；43在长度为N的顺序表上进行插入运算，有几个可插入的位置在第I（假设合法）个位置上插入一个数据元素，需要向什么方向平移多少个数据元素在长度为N的顺序表上进行删除运算，有几个可删除的数据元素删除第I（假设合法）个位置上的数据元素，需要向什么方向平移多少个数据元素长度为N,有N1个插入位置第I个位置上插入，需向右移动NI1个数据元素长度为N，有N个删除位置第I个位置上删除，需向左移动NI个数据元素44根据图示回答下面的问题（1）如何访问P结点的数据域PDATA（2）如何访问P结点的直接前驱结点的数据域PPRIORDATA（3）如何访问P结点的直接后继结点的数据域PNEXTDATA45对于以HEAD为头指针的不带头结点的双链环而言，如何判断P指针所指结点是否为尾元结点如何判断P指针所指结点是否为首元结点对于以HEAD为头指针的带头结点的双链环而言情况又如何不带头结点判断尾元PNEXTHEAD判断首元PHEAD带头结点判断尾元PNEXTHEAD判断首元PHEADNEXT46若线性表中的数据元素以值递增有序排列（数据元素的类型为整数类型），且用带头结点的单链表存储。试写出一个高效算法删除表中所有值大于MIN且小于MAX的数据元素（表中有这样的数据元素时），并说明该算法的时间复杂度。（说明MIN和MAX是给定的两个参变量，可以设定为任意的整数值。）VOIDDELETELINKLISTHEADLINKLISTP,QPHEADWHILEPNEXTNULLIFPNEXTDATANEXTDATAMINQPNEXTPNEXTQNEXTFREEQPPNEXT47若有一个以HEAD为头指针的带头结点的单链表，结点数据域值属于整数类型。现将其数据域值除以3，得余数0,1,2。试按这3种不同的情况，把原有的链表分解成3个不同的单链表，且只增设两个头结点空间，不允许另辟空间。写出一个算法实现上述要求，并且要求头结点的数据域记录该链表中的数据结点数目。VOIDDECOMPOSITIONLINKLISTAH,LINKLISTLINKLISTPA,PB,PC,QPAAHBHLNODEMALLOCSIZEOFLNODECHLNODEMALLOCSIZEOFLNODEBHNEXTNULLCHNEXTNULLPBBHPCCHWHILEPANEXTNULLIFPANEXTDATA30K0ELSEIFPANEXTDATA31K1ELSEK2SWITCHKCASE0PAPANEXTBREAKCASE1QPANEXTPANEXTQNEXTQNEXTPBNEXTPBNEXTQPBQBREAKCASE2QPANEXTPANEXTQNEXTQNEXTPCNEXTPCNEXTQPCQBREAK49设有一个不带头结点的单链表，其结点的值均为整数，并按绝对值从小到大链接。试将该单链表改造为结点按绝对值从大到小进行链接。不允许另辟空间，写出一个算法实现上述要求。APRNULLQHEADWHILEQNULLRQNEXTQNEXTPPQQRHEADP410线性表有两种存储结构，即顺序表和单链表。试问（1）若有N个线性表同时并存，且在处理过程中各表长度会动态发生变化，线性表的总数也会自动地改变，在此情况下应选用哪种存储结构为什么应采用链式存储结构，因为采用链式存储时插入删除操作不许移动数据元素（2）若线性表的总数基本稳定，且很少进行插入和删除操作，但要以最快的速度存取表中元素，那么应采用哪种存储结构为什么应采用顺序存储结构，因为采用顺序存储时可以随机存取，提高存取表中元素的速度。栈回顾第五章栈知识要点1、栈类型的定义（A1,A2,AN），只在栈顶进行插删操作，先进后出。2、栈的存储形式顺序存储链式存储3、栈的应用表达式求值52设计一个算法，判断某输入字符串是否具有中心对称关系，例如ABABBABA，BAXZXAB皆具有中心对称性（具有中心对称性的字符串称为回文）。思路采用顺序栈解决。VOIDJUDGESQSTACKSINITSTACKCHARE1INTI0COUT0时式中，N为正整数。写出它的递归算法。INTFINTNIFN0RETURN1RETURNNFINTN/258写出下列程序的输出结果。（说明该程序中用到的栈S是数据元素为CHAR类型的栈。）VOIDMAINSTACKSCHARX,YINITSTACKSXCYYPUSHS,XPUSHS,NPUSHS,YPOPS,XPUSHS,APUSHS,XPOPS,XPUSHS,NWHILESTACKEMPTYSPOPS,YPRINTF“C”,YPRINTF“C”,X结果NANCY59已知一个栈S的输入序列为ABCD，下面两个序列是否能通过栈的PUSH和POP操作输出如果能，请写出操作序列；如果不能，请说明原因。（X表示入栈，S表示出栈）（1）DBCA；（2）CBDA。（1）不能（2）XXXSSXSS510写一个算法将给定十进制数转换为二进制数。VOIDCONVERSIONINITSTACKS/初始化一个空栈CINN/输入要转换的十进制整数NWHILEN/当N不为0时执行PUSHS,N2NN/2/余数进栈WHILESTACKEMPTYS/当栈不为空时进行POPS,ECOUTEWHILEEANDEPUSHS,ECINEIFERETURN0WHILEECINEIFSTACKEMPTYSRETURN0POPS,CIFECRETURN0IFSTACKEMPTYSRETURN0RETURN1/ISREVERSE队列回顾第六章队列知识要点1、队列类型的定义（A1,A2,AN），只在队首进行删除操作，在队尾进行插入操作，先进先出。2、队列的存储形式链式存储顺序存储循环队列61循环队列的优点是什么如何判别它的空和满由于队列的顺序存储结构中从队尾入队、从队首出队，可能会造成存储空间实际未满，但又数据元素无法入队的情况，即虚溢出现象，而循环队列将整个队列看成一个环，则可以解决虚溢出问题。对于循环队列Q，其存储空间大小为MAXQSIZE，则队空条件QFRONTQREAR队满条件QREAR1MAXQSIZEQFRONT62设长度为N的链队列用循环单链表表示，若只设头指针，则入列操作、出列操作实现的时间开销是多少若只设尾指针呢若只设头指针入列、出列操作实现时间开销分别为ON和O1若只设尾指针入列、出列操作实现时间开销分别为O1和O164用两个栈实现一个队列，并分析你的算法的时间复杂度。思路利用栈S1和S2模拟一个队列，其中S1栈用于插入元素，S2栈用于删除元素时辅助空间，每次删除元素时将S1栈的所有元素出栈并进栈到S2栈中。算法实现为STATUSENQUEUESTACKELSEPUSHS1,XRETURN1时间复杂度TNO1STATUSDEQUEUESTACKWHILESTACKEMPTYS1POPS1,YPUSHS2,YPOPS2,XWHILESTACKEMPTYS2POPS2,YPUSHS1,Y时间复杂度TNON66简述下列算法的功能（假设栈和队列的元素类型均为INT类型）。VOIDALGQUEUEQSTACKSINTEINITSTACKSWHILEQUEUEEMPTYQDEQUEUEQ,EPUSHS,EWHILESTACKEMPTYSPOPQ,EENQUEUES,E实现功能将队列Q逆置。串回顾第七章串知识要点1、串类型的定义“A1,A2,AN”2、串的存储形式顺序存储堆存储链式存储块链结构72已知S1”IMAGIRL”，S2”GIRL”，S3”ISVERYNICE”，试求下列各运算的结果STRINDEXS1,S2STRLENGTHS1CONCATS,S2,S3；答STRINDEXS1,S27STRLENGTHS111CONCATS,S2,S3”GIRLISVERYNICE”77将串的各字符均相同且长度大于1的子串称为该串的一个等值子串。试写算法实现输入字符串S，以为结束符；如果串S中不存在等值子串，则输出“无等值子串”，否则输出串S的一个长度最大的等值子串。如，若S“ABC345B6A7C”，则输出“无等值子串”；若S“ABCAAABBAC”，则输出“AAA”。VOIDEQSUBSTRINGCHARSINTI,J,K,HEAD,MAX,COUNTPRINTF“请输入字符串”FORK0K/输入串SCANF“C”,IFSKBREAKFORI0,J1,HEAD0,MAX1SIIJ,J/找等值子串COUNT1WHILESISJJCOUNTIFCOUNTMAXHEADIMAXCOUNTIFMAX1PRINTF“最大等值子串”FORKHEADKS2则输出一个正数；若S1S2，则输出0；若S1TOP0B、STTOP0C、STTOPM0D、STTOPM012、判定栈ST最多元素为M0为空的条件是（）A、QREARQFRONTM0B、QREARQFRONT1M0C、QFRONTQREARD、QFRONTQREAR13、判定链队列Q最多元素为M0为空的条件是（）A、QFRONTQREARB、QFRONTQREARC、QFRONTQREAR1M0D、QFRONTQREAR1M04、判定循环队列Q最多元素为M0为空的条件是（）A、QREARQFRONTNEXTB、QREARNEXTQREARNEXTNEXTC、QFRONTNEXTQFRONTNEXTNEXTD、QFRONTQREARNEXT5、在链队列Q中删除一结点需要执行的命令是（）BCCAC一、选择题（下列各小题均有一个答案是正确的接上）A、QFRONTNEXTSFSB、QREARNEXTSQREARS6、链队列Q中，若插入结点S需顺序执行的指令是C、SNEXTQREARQREARSD、SNEXTQFRONTQFRONTS（）A、链头B、链中C、链尾D、不确定7、用单链表表示的链式队列的队头在链表中位置（）A、ABCD/EB、ABCD/EC、ABCD/ED、ABCD/E8、中缀表达式ABC/DE的后缀表达式是（）A、QFRONTQREARB、QFRONTQREARC、QFRONTQREAR1M0D、QFRONTQREAR1M09、判定循环队列Q最多元素为M0为满的条件是（）A、3527B、3527C、3527D、352710、3527的前缀表达式是（）ABDCA二、填空题（请用正确答案填充下列空白）1、向栈中压入元素的操作是先_后_存入元素移动栈顶指针2、循环队列中删除一个元素时则应该先_后_；移动头指针取元素3、在具有N个存储单元的循环队列中，队满时共有_个元素；N14、在链队列Q中判定只有一个结点的条件是_；QFRONTNEXTQREAR5、栈S和队列Q的初始状态为空，元素A,B,C,D,E,F依次通过栈S，一个元素出栈后即进入队列Q，若这6个元素出队列的顺序是B,D,C,F,E,A则栈S的容量至少应该是_；36、非空队列中，头指针始终指向_，而尾指针则始终指向队列_元素的_一个位置；队列头元素尾下7、栈和队列的共同特点是_；只允许在端点处进行插入和删除元素8、对不带头结点的链式队列，其队头指针指向队头结点，对尾指针指向队尾结点，则进行出队操作时队头指针_修改，对尾指针_修改，填写要或不要或可能要；可能要可能要三、阅读下列程序段，请说明这些程序段所描述的算法的功能。1STATUSALGOLSTACKS2STATUSALGOL2STACKS,INTEINTI,N0,A255STACKTINTDWHILESTACKEMPTYSINITSTACKTNWHILESTACKEMPTYSPOPS,ANPOPS,DFORI1I2从栈T中出来后变为3YAY2/的操作步骤。XSXXXSSSXXSXXSXXSSSS1INTCOUNTLINKLISTHSLINKLISTPPHSWHILEPNPPNEXTRETURNN1、在栈顶指针为HS的链栈中，写出计算该链栈中结点个数的算法；五、根据题意要求回答问题。2、为什么具有N个存储空间的循环队列满时整个队列只有N1个元素2一般环状队列的头和尾其中之一要进行特殊处理，否则队空或满时只凭QREARQFRONT是无法判断的，一般处理方法是将QREAR指向下一个要插入的位置，这样虽然牺牲了一个单元的存储空间，但很容易区分队列的空与满。串补充习题一、选择题（下列各小题均有一个答案是正确的）1、串是一种特殊的线性表，其特殊性表现在A、可以顺序存储B、数据元素是一个字符C、可以链接存储D、数据元素可要是多个字符2、