数据结构试题-数据结构（四套试卷加答案）

数据结构原则我讲过的都属于考试内容，我没讲过的肯定不会考（尤其是打星号的部分）。具体范围第一章（全部）第二章（全部）第三章（31，321，322，323，34）第六章（61,62,63,66）第七章（71，72，73，741，743）第九章（911，912，921之二叉排序树,93）第十章（101,102,103,104）数据结构试卷（一）参考答案一、选择题（每题2分，共20分）1A2D3D4C5C6D7D8C9D10A二、填空题（每空1分，共26分）1正确性易读性强壮性高效率2ON39334134X2Y3/52NN1N16E2E7有向无回路8NN1/2NN19（12，40）（）（74）（23,55，63）10增加111OLOG2NONLOG2N12归并三、计算题（每题6分，共24分）1线性表为（78，50，40，60，34，90）2邻接矩阵010010邻接表如图11所示图113用克鲁斯卡尔算法得到的最小生成树为1,23,4,64,1,35,1,48,2,510,4,7204见图12图124444422255522884352834四、读算法（每题7分，共14分）1（1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线性表为（A2,A3,AN,A1）2递归地后序遍历链式存储的二叉树。五、法填空（每空2分，共8分）TRUEBSTLEFTBSTRIGHT六、编写算法（8分）INTCOUNTXLNODEHL,ELEMTYPEXINTI0LNODEPHL/I为计数器WHILEPNULLIFPDATAXIPPNEXT/WHILE,出循环时I中的值即为X结点个数RETURNI/COUNTX数据结构试卷（二）参考答案一、选择题1D2B3C4A5A6C7B8C二、填空题1构造一个好的HASH函数，确定解决冲突的方法2STACKTOP，STACKSSTACKTOPX3有序4ON2，ONLOG2N5N01，2N0N16D/2731，38，54，56，75，80，55，6381，3，4，5，2，1，3，2，4，5三、应用题122，40，45，48，80，78，40，45，48，80，22，782QLLINKPQRLINKPRLINKPRLINKLLINKQPRLINKQ32,ASL91122344225/94树的链式存储结构略，二叉树略5E1，3，1，2，3，5，5，6，6，46略四、算法设计题1设有一组初始记录关键字序列（K1，K2，KN），要求设计一个算法能够在ON的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于KI，右半部分的每个关键字均大于等于KI。VOIDQUICKPASSINTR,INTS,INTTINTIS,JT,XRSWHILEIXJJ1IFINEXTFORQHBQ0QQNEXTIFQDATAPDATABREAKIFQ0TLKLISTMALLOCSIZEOFLKLISTTDATAPDATATNEXTHCHCT数据结构试卷（三）参考答案一、选择题1B2B3A4A5A6B7D8C9B10D第3小题分析首先用指针变量Q指向结点A的后继结点B，然后将结点B的值复制到结点A中，最后删除结点B。第9小题分析9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数，而堆排序只需要在初始堆的基础上再进行10次筛选即可，每次筛选的时间复杂度为OLOG2N。二、填空题1顺序存储结构、链式存储结构29，501354出度，入度506ED7中序879O110I/2，2I1115，16，71，23，72，94，73121，4，3，213J1，HASHTABLEJKEYK14RETURNT，TTRCHILD第8小题分析二分查找的过程可以用一棵二叉树来描述，该二叉树称为二叉判定树。在有序表上进行二分查找时的查找长度不超过二叉判定树的高度1LOG2N。三、计算题1AEBFGCDHKJNUL2、H3636MOD71H2211MOD72冲突H1515MOD71冲突H22221MOD73H1511MOD72H4040MOD75H6363MOD70H2222MOD71冲突（1）01234566336152240（2）ASL653、8,9,4,3,6,1,10,12,18,181,6,4,3,8,9,10,12,18,181,3,4,6,8,9,10,12,18,181,3,4,6,8,9,10,12,18,181,3,4,6,8,9,10,12,18,18四、算法设计题1设计在单链表中删除值相同的多余结点的算法。TYPEDEFINTDATATYPETYPEDEFSTRUCTNODEDATATYPEDATASTRUCTNODENEXTLKLISTVOIDDELREDUNDANTLKLISTFORPHEADP0PPNEXTFORQPNEXT,SQQ0IFQDATAPDATASNEXTQNEXTFREEQQSNEXTELSESQ,QQNEXT2设计一个求结点X在二叉树中的双亲结点算法。TYPEDEFSTRUCTNODEDATATYPEDATASTRUCTNODELCHILD,RCHILDBITREEBITREEQ20INTR0,F0,FLAG0VOIDPREORDERBITREEBT,CHARXIFBT0RETURNELSERR120QRBTPREORDERBTLCHILD,XPREORDERBTRCHILD,XVOIDPARENTBITREEBT,CHARXINTIPREORDERBT,XFORIF1ILCHILDDATAX|QIRCHILDDATABREAKIFFLAG0PRINTF“NOTFOUNDXN“ELSEIFIDATAELSEPRINTF“NOTPARENT“数据结构试卷（四）参考答案一、选择题1C2D3D4B5C6A7B8A9C10A二、填空题1ON2，ONLOG2N2PLLINKRLINKPRLINKPRLINKLLINKPRLINK3342K15N/2650，517M1，RFMM8N1I，NI919，18，16，20，30，221016，18，19，20，32，2211AIJ112等于13BDCA14HASHTABLEI0，HASHTABLEKS三、计算题11100EABCDLS21ABCDEFBDEFCA；2ABCDEFGHIJKBDEFCAIJKHG林转换为相应的二叉树；AGBCDEFHIJK3H4H50,H3H6H92,H83,H2H7601234567894569827四、算法设计题1设单链表中有仅三类字符的数据元素大写字母、数字和其它字符，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。TYPEDEFCHARDATATYPETYPEDEFSTRUCTNODEDATATYPEDATASTRUCTNODENEXTLKLISTVOIDSPLITLKLISTHEAD,LKLISTHA0,HB0,HC0FORPHEADP0PHEADHEADPNEXTPNEXT0IFPDATAAHAPELSEIFPDATA0HBPELSEPNEXTHCHCP2设计在链式存储结构上交换二叉树中所有结点左右子树的算法。TYPEDEFSTRUCTNODEINTDATASTRUCTNODELCHILD,RCHILDBITREEVOIDSWAPBITREEBITREEBTBITREEPIFBT0RETURNSWAPBITREEBTLCHILDSWAPBITREEBTRCHILDPBTLCHILDBTLCHILDBTRCHILDBTRCHILDP3在链式存储结构上建立一棵二叉排序树。DEFINEN10TYPEDEFSTRUCTNODEINTKEYSTRUCTNODELCHILD,RCHILDBITREEVOIDBSTINSERTBITREEBTKEYKEYBTLCHILDBTRCHILD0ELSEIFBTKEYKEYBSTINSERTBTLCHILD,KEYELSEBSTINSERTBTRCHILD,KEYVOIDCREATEBSTTREEBITREEFORI1INEXTQL；LLNEXT；PL；S1WHILEPNEXTPPNEXT；S2PNEXTQ；QNEXTNULL；RETURNL；请回答下列问题（1）说明语句S1的功能；（2）说明语句组S2的功能；（3）设链表表示的线性表为（A1,A2,AN）,写出算法执行后的返回值所表示的线性表。2VOIDABCBTNODEBTIFBTABCBTLEFTABCBTRIGHTCOUTDATADATAITEMBSTDATA/查找成功RETURN_ELSEIFITEMDATARETURNFIND_,ITEMELSERETURNFIND_,ITEM/IF六、编写算法（共8分）统计出单链表HL中结点的值等于给定值X的结点数。INTCOUNTXLNODEHL,ELEMTYPEX数据结构试卷（二）一、选择题24分1下面关于线性表的叙述错误的是（）。A线性表采用顺序存储必须占用一片连续的存储空间B线性表采用链式存储不必占用一片连续的存储空间C线性表采用链式存储便于插入和删除操作的实现D线性表采用顺序存储便于插入和删除操作的实现2设哈夫曼树中的叶子结点总数为M，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。A2M1B2MC2M1D4M3设顺序循环队列Q0M1的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（）。ARFBFRCRFMMDFRMM4设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。ABADCBBCDACCDABDCBDA5设某完全无向图中有N个顶点，则该完全无向图中有（）条边。ANN1/2BNN1CN2DN216设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。A9B10C11D127设某有向图中有N个顶点，则该有向图对应的邻接表中有（）个表头结点。AN1BNCN1D2N18设一组初始记录关键字序列5，2，6，3，8，以第一个记录关键字5为基准进行一趟快速排序的结果为（）。A2，3，5，8，6B3，2，5，8，6C3，2，5，6，8D2，3，6，5，8二、填空题24分1为了能有效地应用HASH查找技术，必须解决的两个问题是_和_。2下面程序段的功能实现数据X进栈，要求在下划线处填上正确的语句。TYPEDEFSTRUCTINTS100INTTOPSQSTACKVOIDPUSHSQSTACKELSE_3中序遍历二叉排序树所得到的序列是_序列（填有序或无序）。4快速排序的最坏时间复杂度为_，平均时间复杂度为_。5设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数为_；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_个空指针域。6设某无向图中顶点数和边数分别为N和E，所有顶点的度数之和为D，则E_。7设一组初始记录关键字序列为55，63，44，38，75，80，31，56，则利用筛选法建立的初始堆为_。8已知一有向图的邻接表存储结构如下从顶点1出发，DFS遍历的输出序列是，BFS遍历的输出序列是三、应用题36分1设一组初始记录关键字序列为45，80，48，40，22，78，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。2设指针变量P指向双向链表中结点A，指针变量Q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为LLINK和RLINK）。3设一组有序的记录关键字序列为13，18，24，35，47，50，62，83，90，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。4设一棵树T中边的集合为A，B，A，C，A，D，B，E，C，F，C，G，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。5设有无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合。6设有一组初始记录关键字为45，80，48，40，22，78，要求构造一棵二叉排序树并给出构造过程。四、算法设计题16分1设有一组初始记录关键字序列（K1，K2，KN），要求设计一个算法能够在ON的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于KI，右半部分的每个关键字均大于等于KI。2设有两个集合A和集合B，要求设计生成集合CAB的算法，其中集合A、B和C用链式存储结构表示。数据结构试卷（三）一、选择题每题1分，共20分1设某数据结构的二元组形式表示为AD，R，D01，02，03，04，05，06，07，08，09，RR，R，则数据结构A是（）。A线性结构B树型结构C物理结构D图型结构2下面程序的时间复杂为（）FOR（I1，S0；INEXT；PDATAQDATA；PNEXTQNEXT；FREEQ；BQPNEXT；QDATAPDATA；PNEXTQNEXT；FREEQ；CQPNEXT；PNEXTQNEXT；FREEQ；DQPNEXT；PDATAQDATA；FREEQ；4设有N个待排序的记录关键字，则在堆排序中需要（）个辅助记录单元。A1BNCNLOG2NDN25设一组初始关键字记录关键字为20，15，14，18，21，36，40，10，则以20为基准记录的一趟快速排序结束后的结果为。A10，15，14，18，20，36，40，21B10，15，14，18，20，40，36，21C10，15，14，20，18，40，36，2LD15，10，14，18，20，36，40，216设二叉排序树中有N个结点，则在二叉排序树的平均平均查找长度为（）。AO1BOLOG2NCDON27设无向图G中有N个顶点E条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）。AN，EBE，NC2N，EDN，2E8设某强连通图中有N个顶点，则该强连通图中至少有（）条边。ANN1BN1CNDNN19设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。A快速排序B堆排序C归并排序D插入排序10下列四种排序中（）的空间复杂度最大。A插入排序B冒泡排序C堆排序D归并排序二、填空殖每空1分共20分1数据的物理结构主要包括_和_两种情况。2设一棵完全二叉树中有500个结点，则该二叉树的深度为_；若用二叉链表作为该完全二叉树的存储结构，则共有_个空指针域。3设输入序列为1、2、3，则经过栈的作用后可以得到_种不同的输出序列。4设有向图G用邻接矩阵ANN作为存储结构，则该邻接矩阵中第I行上所有元素之和等于顶点I的_，第I列上所有元素之和等于顶点I的_。5设哈夫曼树中共有N个结点，则该哈夫曼树中有_个度数为1的结点。6设有向图G中有N个顶点E条有向边，所有的顶点入度数之和为D，则E和D的关系为_。7_遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。8设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较_次就可以断定数据元素X是否在查找表中。9不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为_。10设有N个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第I个结点的双亲结点编号为_，右孩子结点的编号为_。11设一组初始记录关键字为72，73，71，23，94，16，5，则以记录关键字72为基准的一趟快速排序结果为_。12设有向图G中有向边的集合E，则该图的一种拓扑序列为_。13下列算法实现在顺序散列表中查找值为X的关键字，请在下划线处填上正确的语句。STRUCTRECORDINTKEYINTOTHERSINTHASHSQSEARCHSTRUCTRECORDHASHTABLE,INTKINTI,JJIKPWHILEHASHTABLEJKEYKIFIJRETURN1IF_RETURNJELSERETURN114下列算法实现在二叉排序树上查找关键值K，请在下划线处填上正确的语句。TYPEDEFSTRUCTNODEINTKEYSTRUCTNODELCHILDSTRUCTNODERCHILDBITREEBITREEBSTSEARCHBITREET,INTKIFT0RETURN0ELSEWHILET0IFTKEYK_ELSEIFTKEYKTTLCHILDELSE_三、计算题每题10分，共30分1已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。2已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为06，假定选用的散列函数是H（K）KMOD7，若发生冲突采用线性探查法处理，试（1）计算出每一个元素的散列地址并在下图中填写出散列表0123456（2）求出在查找每一个元素概率相等情况下的平均查找长度。3已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。四、算法设计题每题15分，共30分1设计在单链表中删除值相同的多余结点的算法。2设计一个求结点X在二叉树中的双亲结点算法。数据结构试卷（四）一、选择题每题1分共20分1设一维数组中有N个数组元素，则读取第I个数组元素的平均时间复杂度为（）。AONBONLOG2NCO1DON22设一棵二叉树的深度为K，则该二叉树中最多有（）个结点。A2K1B2KC2K1D2K13设某无向图中有N个顶点E条边，则该无向图中所有顶点的入度之和为（）。ANBEC2ND2E4在二叉排序树中插入一个结点的时间复杂度为（）。AO1BONCOLOG2NDON25设某有向图的邻接表中有N个表头结点和M个表结点，则该图中有（）条有向边。ANBN1CMDM16设一组初始记录关键字序列为345，253，674，924，627，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。A3B4C5D87设用链表作为栈的存储结构则退栈操作（）。A必须判别栈是否为满B必须判别栈是否为空C判别栈元素的类型D对栈不作任何判别8下列四种排序中（）的空间复杂度最大。A快速排序B冒泡排序C希尔排序D堆9设某二叉树中度数为0的结点数为N0，度数为1的结点数为NL，度数为2的结点数为N2，则下列等式成立的是（）。AN0N11BN0NLN2CN0N21DN02N1L10设有序顺序表中有N个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。ALOG2N1BLOG2N1CLOG2NDLOG2N1二、填空题每空1分共20分1设有N个无序的记录关键字，则直接插入排序的时间复杂度为_，快速排序的平均时间复杂度为_。2设指针变量P指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为_（设结点中的两个指针域分别为LLINK和RLINK）。3根据初始关键字序列19，22，01，38，10建立的二叉排序树的高度为_。4深度为K的完全二叉树中最少有_个结点。5设初始记录关键字序列为K1，K2，KN，则用筛选法思想建堆必须从第_个元素开始进行筛选。6设哈夫曼树中共有99个结点，则该树中有_个叶子结点；若采用二叉链表作为存储结构，则该树中有_个空指针域。7设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储_个队列元素；当前实际存储_个队列元素（设头指针F指向当前队