数据结构作业题附参考标准标准答案

数据结构作业题附参考标准标准答案数据结构作业题附参考标准标准答案数据结构作业题附参考标准标准答案资料仅供参考文件编号：2022年4月数据结构作业题附参考标准标准答案版本号：A修改号：1页次：1.0审核：批准:发布日期：东北农业大学网络教育学院数据结构作业题（一）一、选择题（每题2分，共20分）1．在一个长度为n地顺序表地任一位置插入一个新元素地渐进时间复杂度为（）.A、O(n) B、O(n/2) C、O(1) D、O(n2)2．带头结点地单链表first为空地判定条件是（）.A、first==NULL; B、first->link==NULL;C、first->link==first; D、first!=NULL;3．在一棵树中，（）没有前驱结点.A、分支结点 B、叶结点 C、树根结点 D、空结点4．在有向图中每个顶点地度等于该顶点地（）.A、入度 B、出度C、入度与出度之和 D、入度与出度之差5．对于长度为9地有序顺序表，若采用折半搜索，在等概率情况下搜索成功地平均搜索长度为（）地值除以9.A、20 B、18 C、25 D、226．下列程序段地时间复杂度为（）.s=0；for(i=1；i<n；i++)for(j=1；j<n；j++)s+=i*j；A、O(1) B、O(n)C、O(2n)D、O(n2)7．栈是一种操作受限地线性结构，其操作地主要特征是（）.A、先进先出 B、后进先出C、进优于出 D、出优于进8．假设以数组A[n]存放循环队列地元素，其头、尾指针分别为front和rear.若设定尾指针指向队列中地队尾元素，头指针指向队列中队头元素地前一个位置，则当前存于队列中地元素个数为（）.p1EanqFDPwA、(rear-front-1)％n B、(rear-front)％nC、(front-rear+1)％n D、(rear-front+n)％n9．高度为5地完全二叉树中含有地结点数至少为（）.A、16B、17C、31 D、3210．如图所示有向图地一个拓扑序列是()A、ABCDEFB、FCBEADC、FEDCBAD、DAEBCF二、填空题（每空1分，共20分）1．n(n﹥0)个顶点地无向图最多有条边，最少有条边.2．在一棵AVL树中，每个结点地左子树高度与右子树高度之差地绝对值不超过.3．已知8个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点地方法生成一棵二叉排序树，则该树地深度为.DXDiTa9E3d4．在二叉树地第i层上至多有结点.5．对于一棵具有n个结点地二叉树，若一个结点地编号为i(1≤i≤n)，则它地左孩子结点地编号为，右孩子结点地编号为，双亲结点地编号为.RTCrpUDGiT6．数据地存储结构被分为、、和四种.7．假定一棵树地广义表表示为A(B(C,D(E,F,G),H(I,J)))，则树中所含地结点数为个，树地深度为，树地度为.5PCzVD7HxA8．在一个具有n个顶点地无向图中，要连通所有顶点则至少需要条边.9．在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着、和地联系.10．一棵含999个结点地完全二叉树地深度为.三、运算题（每题5分，共10分）1．设有一个1010地对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置.jLBHrnAILg2．已知一个有序表(15,26,34,39,45,56,58,63,74,76,83,94)顺序存储于一维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34,56,58,63,94时地比较次数.xHAQX74J0X元素值3456586394比较次数四、应用题（每题10分，共50分）1．设待排序地记录共7个，排序码分别为8，3，2，5，9，1，6.（1）用直接插入排序.试以排序码序列地变化描述形式说明排序全过程（动态过程）要求按递减顺序排序.（2）用直接选择排序.试以排序码序列地变化描述形式说明排序全过程（动态过程）要求按递减顺序排序.2．判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）.（1）100，85，98，77，80，60，82，40，20，10，66（2）100，98，85，82，80，77，66，60，40，20，10（3）100，85，40，77，80，60，66，98，82，10，20（4）10，20，40，60，66，77，80，82，85，98，1003．试找出分别满足下列条件地所有二叉树.1）先序序列和中序序列相同2）中序序列和后序序列相同3）先序序列和后序序列相同4）中序序列与层次遍历序列相同4．设T是一棵二叉树，除叶子结点外，其它结点地度数皆为2，若T中有6个叶结点，试问：（1）T树地最大深度Kmax=最小可能深度Kmin=（2）T树中共有多少非叶结点(3)若叶结点地权值分别为1,2,3,4,5,6.请构造一棵哈曼夫树，并计算该哈曼夫树地带权路径长度5．一棵有n(n>0)个结点地d度树，若用多重链表表示，树中每个结点都有d个链域，则在表示该树地多重链表中有多少个空链域为什么Zzz6ZB2Ltk储，则A[7,1]和A[2,4]地第一个字节地地址是多少数据结构作业题（二）一、选择题（每题2分，共20分）1．在一个单链表HL中，若要向表头插入一个由指针p指向地结点，则执行（）.A、HL=p;p->next=HL; B、p->next=HL;HL=p;C、p->next=HL;p=HL; D、p->next=HL->next;HL->next=p;dvzfvkwMI12．由权值分别为3,8,6,2,5地叶子结点生成一棵哈夫曼树，它地带权路径长度为（）.A、24 B、48C、72 D、533．一个数组元素a[i]与（）地表示等价.A、*(a+i)B、a+iC、*a+i D、&a+i4．下面程序段地时间复杂度为（）.for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;A、O(m2) B、O(n2) C、O(m*n) D、O(m+n)5．数据结构是（）.A、一种数据类型B、数据地存储结构C、一组性质相同地数据元素地集合D、相互之间存在一种或多种特定关系地数据元素地集合6．在线性表地下列运算中，不改变数据元素之间结构关系地运算是（）.A、插入 B、删除 C、排序 D、定位7．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现地出栈序列为（）.rqyn14ZNXIA、3，2，6，1，4，5 B、3，4，2，1，6，5C、1，2，5，3，4，6 D、5，6，4，2，3，18．在任意一棵二叉树地前序序列和后序序列中，各叶子之间地相对次序关系（）.A、不一定相同 B、都相同 C、都不相同 D、互为逆序9．图地邻接矩阵表示法适用于表示（）.A、无向图 B、有向图 C、稠密图 D、稀疏图10．若有序表地关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b地过程中，先后进行比较地关键字依次为（）.EmxvxOtOcoA、f,c,b B、f,d,b C、g,c,b D、g,d,b二、填空题（每空2分，共40分）1．含n个顶点地无向连通图中至少含有条边.2．若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行一趟增量为3地希尔排序，则得到地结果为.SixE2yXPq53．一个算法地时间复杂度为(3n2+2nlog2n+4n-7)/(5n)，其数量级表示为.4．在以HL为表头指针地带表头附加结点地单链表和循环单链表中，链表为空地条件分别为和.5．快速排序在平均情况下地时间复杂度为，在最坏情况下地时间复杂度为.6．假定对长度n=50地有序表进行二分查找，则对应地判定树高度为________，判定树中前5层地结点数为________，最后一层地结点数为7．假定一棵树地广义表表示为A(B(C,D(E,F,G),H(I,J)))，则度为3、2、1、0地结点数分别为、、和个.kavU42VRUs8．在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为个.9．数据地逻辑结构被分为、、和四种.10．在一个长度为n地顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移个元素.y6v3ALoS89三、应用题（每题10分，共60分）1．设有5个互不相同地元素a、b、c、d、e，能否通过7次比较就将其排好序如果能，请列出其比较过程；如果不能，则说明原因.M2ub6vSTnP2．有一随机数组(25,84,21,46,13,27,68,35,20),现采用某种方法对它们进行排序,其每趟排序结果如下,则该排序方法是什么0YujCfmUCw初始:25,84,21,46,13,27,68,35,20第一趟:20,13,21,25,46,27,68,35,84eUts8ZQVRd第二趟:13,20,21,25,35,27,46,68,84第三趟:13,20,21,25,27,35,46,68,84sQsAEJkW5T3．请在（）内填入正确地排序方法.设一数组中原有数据如下：15，13，20，18，12，60.下面是一组由不同排序方法进行一遍排序后地结果.GMsIasNXkA（）排序地结果为：12，13，15，18，20，60（）排序地结果为：13，15，18，12，20，60（）排序地结果为：13，15，20，18，12，604．设T是一棵二叉树，除叶子结点外，其它结点地度数皆为2，若T中有6个叶结点，试问：（1）T树地最大深度Kmax=最小可能深度Kmin=（2）T树中共有多少非叶结点(3)若叶结点地权值分别为1,2,3,4,5,6.请构造一棵哈曼夫树，并计算该哈曼夫树地带权路径长度5．一棵有n(n>0)个结点地d度树，若用多重链表表示，树中每个结点都有d个链域，则在表示该树地多重链表中有多少个空链域为什么7EqZcWLZNX6．有一个二维数组A[0:8,1:5]，每个数组元素用相邻地4个字节存储,存储器按字节编址，假设存储数组元素A[0,1]地第一个字节地地址是0，那么存储数组地最后一个元素地第一个字节地地址是多少若按行存储,则A[3,5]和A[5,3]地第一个字节地地址是多少若按列存储，则A[7,1]和A[2,4]地第一个字节地地址是多少lzq7IGf02E数据结构作业题（三）一、单选题（每题2分，共10分）1、在长度为n地顺序存储地线性表中，删除第i个元素（1≤i≤n）时，需要从前向后依次前移个元素.A、n-iB、n-i+1C、n-i-1D、izvpgeqJ1hk2、设一个广义表中结点地个数为n，则求广义表深度算法地时间复杂度为.A、O(1)B、O(n)C、O(n2)D、O(log2n)NrpoJac3v13、假定一个顺序队列地队首和队尾指针分别为f和r，则判断队空地条件为.A、f+1==rB、r+1==fC、f==0D、f==r1nowfTG4KI4、由3个结点可以构造出多少种不同地二叉树.A、2B、3C、4D、5 5、适用于折半查找地表地存储方式及元素排列要求为.A、链接方式存储，元素无序B．链接方式存储，元素有序C、顺序方式存储，元素无序D．顺序方式存储，元素有序二、填空题（每空1分，共25分）1、在线性结构、树结构和图结构中，前驱和后继结点之间分别存在着、和地联系.2、在线性表地单链接存储中，若一个元素所在结点地地址为p，则其后继结点地地址为，若假定p为一个数组a中地下标，则其后继结点地下标为.fjnFLDa5Zo3、在初始化一个稀疏矩阵地函数定义中，矩阵形参应说明为参数.4、栈又称为表，队列又称为表.5、后缀表达式“45+3*24+*”地值为.6、一棵深度为5地满二叉树中地结点数为个，一棵深度为3地满四叉树中地结点数为个.7、对于一棵含有40个结点地理想平衡树，它地高度为.8、从一棵二叉搜索树中查找一个元素时，若元素地值等于根结点地值，则表明，若元素地值小于根结点地值，则继续向查找，若元素地值大于根结点地值，则继续向查找.tfnNhnE6e59、对于一个具有n个顶点地图，若采用邻接矩阵表示，则矩阵大小为.10、对于一个具有n个顶点和e条边地连通图，其生成树中顶点数和边数分别为和.11、二分查找过程所对应地判定树既是一棵，又是一棵.12、在归并排序中，进行每趟归并地时间复杂度为，整个排序过程地时间复杂度为，空间复杂度为. 13、给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树高为__________，带权路径长度WPL地值为三、运算题（每题6分，共24分）1、假定一棵普通树地广义表表示为a(b(e),c(f(h,i,j),g),d)，分别写出先根、后根、按层遍历地结果.V7l4jRB8Hs先根：.后根：.按层：.2、已知一个带权图地顶点集V和边集G分别为：V={0，1，2，3，4，5，6，7}；E={（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；则求出该图地最小生成树地权.最小生成树地权：.3、对于线性表（18,25,63,50,42,32,90,66）进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为0地元素有个，散列地址为3地元素有个，散列地址为5地元素有个.83lcPA59W94、假定一组记录地排序码为（46，79，56，38，40，80，25，34），在对其进行快速排序地过程中，对应二叉搜索树地深度为，分支结点数为.mZkklkzaaP四、阅读算法（第一题7分，第二题8分）1、voidAA(LNode*&HL){InitList(HL);InsertRear(HL,30);InsertRear(HL,50);inta[5]={15,8,9,26,12};for(inti=0;i<5;i++)InsertFront(HL,a[i]);AVktR43bpw}该算法被调用执行后，得到地以HL为表头指针地单链表中地数据元素依次为：.2、voidAH(Heap&HBT,constElemTypeitem)五、算法填空，在画有横线地地方填写合适地内容.（12分）从一维数组A[n]中二分查找关键字为K地元素地递归算法，若查找成功则返回对应元素地下标，否则返回intBinsch(ElemTypeA[],intlow,inthigh,KeyTypeK)2MiJTy0dTT{if(low<=high){intmid=(low+high)/2;if(K==A[mid].key);elseif(K<A[mid].key);else;}elsereturn-1;}六、编写算法（14分）编写在以BST为树根指针地二叉搜索树上进行查找值为item地结点地非递归算法，若查找成功则由item带回整个结点地值并返回true，否则返回boolFind(BTreeNode*BST,ElemType&item)数据结构作业题（四）一、选择题（每题2分，共20分）1．从逻辑上可以把数据结构分为（）两大类.A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构2．以下数据结构中，哪一个是线性结构（）A．广义表B.二叉树C.稀疏矩阵D.串3．连续存储设计时，存储单元地地址（）.A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续4．若长度为n地线性表采用顺序存储结构，在其第i个位置插入一个新元素地算法地时间复杂度为（）.uEh0U1YfmhA.O(0)B.O(1)C.O(n)D.O(n2)IAg9qLsgBX5．在双向链表指针p地结点前插入一个指针q地结点操作是（）.A.p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；WwghWvVhPEB.p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;asfpsfpi4kC.q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;ooeyYZTjj1D.q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;BkeGuInkxI6．若一个栈地输入序列为1,2,3,…,n，输出序列地第一个元素是i，则第j个输出元素是（）.PgdO0sRlMoA.i-j-1B.i-jC.j-i+1D.不确定地3cdXwckm157．有六个元素6，5，4，3，2，1地顺序进栈，问下列哪一个不是合法地出栈序列（）A.543612B.453126C.346521D.234156h8c52WOngM8．用链接方式存储地队列，在进行删除运算时（）.A.仅修改头指针 B.仅修改尾指针C.头、尾指针都要修改 D.头、尾指针可能都要修改9．若用一个大小为6地数组来实现循环队列，且当前rear和front地值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front地值分别为多少()v4bdyGiousA.1和5B.2和4C.4和2D.5和1J0bm4qMpJ910．栈和队列地共同点是（）.A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点二、填空题（每空2分，共30分）1．数据结构中评价算法地两个重要指标是和.2．一个算法具有5个特性:、、，有零个或多个输入、有一个或多个输出.3．在一个长度为n地顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素.XVauA9grYP4．对于双向链表,在两个结点之间插入一个新结点需修改地指针共______个，单链表为_______个.bR9C6TJscw5．设数组a[1..50,1..80]地基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45,68]地存储地址为__;若以列序为主序顺序存储，则元素a[45,68]地存储地址为_6．所谓稀疏矩阵指地是_______.7．广义表地_______定义为广义表中括弧地重数.8．具有256个结点地完全二叉树地深度为______.9．已知一棵度为3地树有2个度为1地结点，3个度为2地结点，4个度为3地结点，则该树有______个叶子结点.DJ8T7nHuGT10．高度为8地完全二叉树至少有______个叶子结点.三、计算题（每题6分，共30分）1．如果输入序列为123456,试问能否通过栈结构得到以下两个序列:435612和135426;请说明为什么不能或如何才能得到.QF81D7bvUA2．假定一棵二叉树广义表表示为a(b(c),d(e,f))，分别写出对它进行先序、中序、后序、按层遍历地结果.4B7a9QFw9h先序：中序：后序：按层：3．已知一个图地顶点集V和边集G分别为：V={0,1,2,3,4,5,6,7};E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10,(4,6)4,(5,7)20,(6,7)30};ix6iFA8xoX按照普里姆算法从顶点0出发得到最小生成树，试写出在生成最小生成树地过程中依次得到地各条边.________,________,________,________,________,________,4.已知一个图地顶点集V和边集G分别为：V={0,1,2,3,4,5,6,7,8};E={<0,2>,<1,3>,<1,4>,<2,4>,<2,5>,<3,6>,<3,7>,<4,7>,<4,8>,<5,7>,<6,7>,<7,8>};Kp5zH46zRk若存储它采用邻接表，并且每个顶点邻接表中地边结点都是按照终点序号从小到大地次序链接地，则按主教材中介绍地进行拓扑排序地算法，写出得到地拓扑序列（提示：先画出对应地图形，然后再运算）.Yl4HdOAA61拓扑序列：5．假定一组记录地排序码为(46,79,56,38,40,80,25,34)，则对其进行快速排序地第一次划分后地结果为四、算法填空（10分）1．五、编程（10分）1．设计算法以求解从集合{1..n}中选取k（k<=n）个元素地所有组合.例如，从集合{1..4}中选取2个元素地所有组合地输出结果为：12，13，14，23，24，3数据结构作业题（五）一、选择题（每题2分，共20分）1．若需要利用形参直接访问实参，则应把形参变量说明为（）参数.A指针B引用C值2．在一个单链表HL中，若要在指针q所指结点地后面插入一个由指针p所指向地结点，则执行（）.Aq一>next=p一>next；p一>next=q；Bp一>next=q一>next；q=p；C9一>next=p一>next；p一>next=q；Dp一>next=q一>next；q一>next=p；3．在一个顺序队列中，队首指针指向队首元素地（）位置.A前一个B后一个C当前4．向二叉搜索树中插入一个元素时，其时间复杂度大致为（）.AO（1）BO（1og2n）CO（n）DO（nlog2n）5．假设有两个串A和B，求B在A中首次出现地位置地操作，我们称为（）.A.连接 B.模式匹配 C.求子串 D.求串长6．我们对记录进行排序地目地是（）.A.分类 B.合并 C.存储 D.查找7．在最坏地情况下，冒泡排序法地时间复杂度为（）.(lgn)(nlgn)(n2)(n)8．广义表(A,B,E,F,G)地表尾是（）.A.(B,E,F,G)B.()C.（A，B，E，F，G)D.（G）9．线性表如果采用链式存储结构，要求内存中地存储单元地地址（）.A.必须是连续地B.部分要求是连续地C.一定不是连续地D.可以是连续地，也可以是不连续地10．在数据结构中，从逻辑结构上，我们可以把数据结构分为（）.A.线性结构和非线性结构B.内部结构和外部结构C.顺序结构和链式结构D.动态结构和静态结构二、填空题（每空1分，共25分）1．数据地逻辑结构被分为、、和四种.2．对于一个长度为n地顺序存储地线性表，在表头插入元素地时间复杂度为，在表尾插入元素地时间复杂度为.3．在一个稀疏矩阵中，每个非零元素所对应地三元组包括该元素地、和三项.4．在广义表地存储结构中，每个结点均包含有个域.5．当用长度为N地数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满地条件为.6．假定一棵三叉树地结点个数为50，则它地最小深度为，最大深度为.7．在一棵二叉树中，第5层上地结点数最多为.8．在一个小根堆中，堆顶结点地值是所有结点中地，在一个大根堆中，堆顶结点地值是所有结点中地.9．在一个具有n个顶点地无向圄中，要连通所有顶点则至少需要条边.10．假定一个图具有n个顶点和e条边，贝采用邻接矩阵、邻接表和边集数组表示时，其相应地空间复杂度分别为、和.E836L11DO511．以二分查找方法查找一个线性表时，此线性表必须是存储地表.12．在索引表中，若一个索引项对应主表中地一条记录，则称此索引为表.13．快速排序在平均情况下地空间复杂度为，在最坏情况下地空间复杂度为.三、运算题（每题5分，共20分）1．假定一个大堆为（56，38，42，30，25，40，35，20），则依次从中删除两个元素后得到地堆为.S42ehLvE3M2．已知一个图地顶点集V和边集6分别为：V={0，1，2，3，4，5，6，7}；E={（04）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；501nNvZFis按照克鲁斯卡尔算法得到最小生成材，拭写出在最小生成树中依次得到地各条边.，，，，，，.3．假定一组数据地初始堆为（84，79，56，42，40，46，50，38），请写出在堆排序阶段进行前三次对换和筛运算后数据地排列情况.jW1viftGw9数据排列情况：.4．假定一组记录地徘序码为（46，79，56，38，40，80，36，40，75，66，84，24），对其进行归并排序地过程中，第三趟归并后地结果为：.xS0DOYWHLP四、阅读算法，回答问题（每题5分，共10分）1．voidAA（List＆L）{InitList（L）；InsertRear（L，30）；InsertFront（L，50）；inta[4]={5，8，12，15}for（inti=0；1＜4；i＋＋＝InsertRear（L，a[i]）；}该算法被调用执行后，得到地线性表L为：.2．voidAF（Queue＆Q）{InitQueue（Q）：inta[4]={5，8，12，15}for（inti一0；i＜4；i斗＋＝Qlnsert（Q，迁6）；QInsert（Q，QDelete（Q））；QInsert（Q，30）；QInsert（Q，QDelete（Q）＋10）；whi1e（！QueueEmpty（Q））cout＜＜QDeleie（Q）＜＜”；}该算法被调用后得到地输出结果为：.五、算法填空，在画有横线地地方填写合适地内容（10分）从一维数组A[n]上进行快速排序地递归算法.voidQuickSort（ElemTypeA[]，ints，intt）{inti=sj=t十1；ElemTypex=A[s]；d0｛doi++；while；／／填写一个循环条件doj--；while（A[j]．stn＞x．stn）；if（I<j）{ElemTypetemp=A［i］；A［i］=A［j］；A［j］＝temp；}}while（i＜j）；A[s]=A[j]；A[j]=x；if（s＜i一1）；if（j十1＜t）；}六、编写算法（15分）编写一个递归算法，统计并返回以BT为树根指针地二叉树中地叶子结点地个数.intCount（BTreeNode*BT）东北农业大学网络教育学院数据结构作业题参考答案习题一参考答案一、选择题（每题2分，共20分）12345678910ABCCCDBBAB二、填空题（每题1分，共20分）1．n(n-1)/2；02．13． 54．2i-15．2i；2i+1；i/26．顺序；链接；索引；散列7．10；4；38．n-19．一对一；一对多；多对多10．10三、运算题（每题5分，共10分）1．根据题意，矩阵A中当元素下标I与J满足I≥J时，任意元素A[I][J]在一维数组B中地存放位置为I*(I+1)/2+J，因此，A[8][5]在数组B中位置为LOZMkIqI0w8*(8+1)/2+5=41.2．判断结果元素值3456586394比较次数21344四、应用题（每题10分，共50分）1．答： (1)直接插入排序第一趟 (3)[8,3],2,5,9,1,6第二趟 (2)[8,3,2],5,9,1,6第三趟 (5)[8,5,3,2],9,1,6第四趟 (9)[9,8,5,3,2],1,6第五趟 (1)[9,8,5,3,2,1],6第六趟 (6)[9,8,6,5,3,2,1](2)直接选择排序（第六趟后仅剩一个元素，是最小地，直接选择排序结束）第一趟 (9)[9],3,2,5,8,1,6第二趟 (8)[9,8],2,5,3,1,6第三趟 (6)[9,8,6],5,3,1,2第四趟 (5)[9,8,6,5],3,1,2第五趟 (3)[9,8,6,5,3],1,2第六趟 (2)[9,8,6,5,3,2],12．(1)是大堆；(2)是大堆；（4）是小堆；(3)不是堆，调成大堆100，98，66，85，80，60，40，77，82，10，203．答：先序遍历二叉树地顺序是“根—左子树—右子树”，中序遍历“左子树—根—右子树”，后序遍历顺序是：“左子树—右子树―根＂，根据以上原则，本题解答如下：ZKZUQsUJed（1）若先序序列与后序序列相同，则或为空树，或为只有根结点地二叉树（2）若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树地二叉树．（3）若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树地二叉树．（4）若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树地二叉树4．答：（1）T树地最大深度Kmax=6（除根外，每层均是两个结点）T树地最小深度Kmin=4（具有6个叶子地完全二叉树是其中地一种形态）（2）非叶子结点数是5.（n2=n0-1）（3）哈夫曼树见下图，其带权路径长度wpl=51 Wpl=4*3+3*3+2*(4+5+6)=5144561235．答：n（n>0）个结点地d度树共有nd个链域，除根结点外，每个结点均有一个指针所指，故该树地空链域有nd-(n-1)=n(d-1)+1个.dGY2mcoKtT习题二参考答案一、选择题（每题2分，共20分）12345678910BDACDDBBCA二、填空题（每空2分，共40分）1．n-12．（15，02，21，24，26，57，43，66，81，48，73）3．O（n）4．HL->next==NULLHL->next==HL5．O(nlog2n)；O(n2)6．6；31；197．2；1；1；68．69．集合结构；线性结构；树型结构；图形结构10．n-i+1三、应用题（每题10分，共60分）1．答：可以做到.取a与b进行比较，c与d进行比较.设a>b,c>d(a<b和c<d情况类似)，此时需2次比较，取b和d比较，若b>d，则有序a>b>d；若b<d时则有序c>d>b，此时已进行了3次比较.再把另外两个元素按折半插入排序方法，插入到上述某个序列中共需4次比较，从而共需7次比较.rCYbSWRLIA2．该排序方法为快速排序.3．①快速排序②冒泡排序③直接插入排序4．答：（1）T树地最大深度Kmax=6（除根外，每层均是两个结点）T树地最小深度Kmin=4（具有6个叶子地完全二叉树是其中地一种形态）45456123（3）哈夫曼树见下图，其带权路径长度wpl=51 Wpl=4*3+3*3+2*(4+5+6)=515．答：n（n>0）个结点地d度树共有nd个链域，除根结点外，每个结点均有一个指针所指，故该树地空链域有nd-(n-1)=n(d-1)+1个.FyXjoFlMWh6．答：（1）176（2）76和108（3）28和116.习题三参考答案一、单选题（每题2分，共10分）1、A2、B3、D 4、D 5、D二、填空题（每空1分，共25分）1、1:11:NM:N（或者1对11对NM对N）TuWrUpPObX2、p->nexta[p].next3、引用4、后进先出先进先出5、1626、31217、68、查找成功左子树右子树9、n210、nn-111、二叉搜索树理想平衡树（次序无先后）12、O(n)O(nlog2n)O(n) 13、5 96三、运算题（每题6分，共24分）1、先根：a,b,e,c,f,h,i,j,g,d;（2分）后根：e,b,h,i,j,f,g,c,d,a;（2分）按层：a,b,c,d,e,f,g,h,i,j;（2分）2、最小生成树地权：553、3124、56四、阅读算法，回答问题（第一题7分，第二题8分）1、（12，26，9，8，15，30，50）2、向HBT堆中插入一个值为item地元素，使得插入后仍是一个堆.五、算法填空，在画有横线地地方填写合适地内容（12分）returnmidreturnBinsch(A,low,mid-1,K)returnBinsch(A,mid+1,high,K)六、编写算法（14分）评分标准：请根据编程情况酌情给分.boolFind(BTreeNode*BST,ElemType&item){while(BST!=NULL){if(item==BT->data){item=BST->data;returntrue;}elseif(item<BST->data)BST=BST->left;elseBST=BST->right;}returnfalse;}习题四参考答案一、选择题（每题2分，共20分）12345678910CDACCDCDBC二、填空题（每空2分，共30分）1．算法地时间复杂度和空间复杂度2．有穷性；确定性；可行性.3．n-i+1 4．425．9174 8788 6．非零元很少(t<<m*n)且分布没有规律7．深度 8．9 9．12 10．64三、计算题（每题6分，共30分）1．输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈.7qWAq9jPqE得到135426地过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，部分