数据结构作业题及参考答案

数据结构作业题及参考答案-标准化文件发布号：（9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII东北农业大学网络教育学院数据结构作业题（一）一、选择题（每题2分，共20分）在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。A、O（n）B、O（n/2）C、O（1）D、O（n2）带头结点的单链表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、20B、18C、25D、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、出优于进•假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为（）。A、（rear-front-1）％nB、（rear-front）％nC、（front-rear+1）％nD、（rear-front+n）％n•高度为5的完全二叉树中含有的结点数至少为（）。．答：先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右子树”，后序遍历顺序是：“左子树一右子树一根"，根据以上原则，本题解答如下：（1）若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树（2）若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树．（3）若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树．（4）若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树4．答：（1）T树的最大深度Kmax=6（除根外，每层均是两个结点）T树的最小深度Kmin=4（具有6个叶子的完全二叉树是其中的一种形态）（2）非叶子结点数是5°（n2=n0-1）（3）哈夫曼树见下图，其带权路径长度wpl=51Wpl=4*3+3*3+2*（4+5+6）=51n(n>0)个结点的d度树共有nd个链域，除根结点外，每个结点均有一个指针所指,故该树的空链域有nd-(n-1)=n(d-1)+1个。习题二参考答案一、选择题(每题2分，共20分)12345678910BDACDDBBCA二、填空题(每空2分，共40分)1．n-1.(15,02,21,24,26,57,43,66,81,48,73).0(n).HL->next=NULLHL->next=HL.O(nlog2n)；O(n2)26.6：31：19.2；1；1；6._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次比较2．该排序方法为快速排序。3.①快速排序②冒泡排序③直接插入排序4．答：(1)T树的最大深度Kmax=6(除根外，每层均是两个结点)T树的最小深度Kmin=4(具有6个叶子的完全二叉树是其中的一种形态)5．答：n(n>0)个结点的d度树共有nd个链域，除根结点外，每个结点均有一个指针所指,故该树的空链域有nd-(n-1)=n(d-1)+1个。6．答：(1)176(2)76和108(3)28和116。习题三参考答案一、单选题(每题2分，共10分1、A2、B3、D4、D5、D二、填空题（每空1分，共25分）1、1:11:NM:N（或者1对11对NM对N）、p->nexta[p].next、引用、后进先出先进先出、162TOC\o"1-5"\h\z、3121、6、查找成功左子树右子树、n2、nn-111、二叉搜索树理想平衡树（次序无先后）12、O（n）O（nlog2n）O（n）13、596三、运算题（每题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、最小生成树的权：55、312、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．有穷性；确定性；可行性。4．424．426•非零元很少（tvvm*n）且分布没有规律5．91748788

7．深度8．7．深度8．99．1210．64三、计算题(每题6分，共30分)1．输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素(4356)得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。2．先序：a,b,c,d,e,f中序：c,b,a,e,d,f后序：c,b,e,f,d,a按层：a,b,d,c,e,f3．(0,3)2,(0,2)5,(0,1)8,(1,5)6,(3,6)10,(6,4)4,(5,7)204．拓扑序列：1,3,6,0,2,5,4,7,85．[40342538]46[805679]四、算法填空(10分)1．BST->left=BST->right=NULLInsert(BST->left,item)Insert(BST->right,item)五、编程(10分)2•从集合(l..n)中选出k(本题中k=2)个元素，为了避免重复和漏选，可分别求出包括1和不包括1的所有组合。即包括1时，求出集合(2..n)中取出k-1个元素的所有组合；不包括1时，求出集合(2..n)中取出k个元素的所有组合。，将这两种情况合到一起，就是题目的解

intA[],n;//设集合已存于数组A中。voidcomb(intP[],inti,intk)//从集合(l..n)中选取k(k<=n)个元素的所有组合{if(k==0)printf(P);elseif(k<=n){P[i]=A[i];comb(P,i+1,k-1);comb(P,i+1,k);}}//算法结束习题五参考答案一、单选题（每题2分，共20分）1．B2．D3．A4．B6．D7．C8．A9．D、填空题（每空1分，共25分）1．集合结构线性结构树形结构2．O(n)O(1)3．行号列号元素值（次序无先后）4．35．top==06．5507．168．最小值最大值9．n-110．O(n2)O（n十e)O(e)11．顺序有序5．B10．A图形结构

12．稠密稀疏13．O（1og2n）O（n1.1.(40，38.35，30，25，20)2.（0，3）2，（4，6）4，（0，2)5，(1，3.（50，42，46，38，40，56，79，84)4.[3638404046567980][256675三、运算题（每题5分，共20分）5）6，（0，1）8，（3，6）10，（5，7）2084]四、阅读算法，回答问题（每题5分，共10分）1．(50，30，5，8，12，15)2．121553018五、算法填空，在画有横线的地方填写合适的内容（10分（A[i]stn<