HYPERLINK"http://202.43.154.166/entity/function/homeworkpaper/homeworkpaper_info.jsp?paperId=4613"\t"_blank"201209学期算法与数据结构作业4单项选择题第1题Haffman树是一棵：（）。A、满二叉树B、多叉树C、带权路径长最小的树D、最小代价生成树答案：C第2题字符串|abcd|与字符串|abcde|比较后的关系是：（）。A、”abcd”＞”abcde”B、”abcd”＜”abcde”C、”abcd”＜=”abcde”D、”abcd”＞=”abcde”答案：B第3题下列程序中，哪一段是正确求解n！？（）A、intfactor(intn)｛returnn*(n-1)!｝B、intfactor(intn)｛returnn*factor(n-1)｝C、intfactor(intn)｛if(n＜=1)return1returnn*factor(n-1)｝D、intfactor(intn)｛if(n==0)return1elsereturnn*(n-1)!｝答案：C第4题设n为正整数。试确定下列程序段中带标号@的语句的频度。I=1;j=0;While(i+j＜=n)@If(i＞j)J=j+1;ElseI=i+1;：（）。A、n*nB、nC、2nD、(1+2+3+...+n)答案：B第5题假设有上三角矩阵a[n][n]，对角线及对角线以上的元素非零，对角线以下的元素为C。如果采用压缩存贮，将三角矩阵的元素存贮于一维数据B中，则a[i][j]与B[k]的下标对应关系是什么：（）。A、(i-j)*(j+1)=kB、(i-1)*(j+1)=kC、(j-1)*(i+1)=kD、i*(j+1)=k答案：B判断题第6题分块查找时引入了静态查找就是顺序查找、折半查找和分块查找。答案：错误第7题二叉树只有前序、中序和后序三种遍历运算。答案：错误第8题二叉树是一种特殊的图。答案：正确第9题度为二的树是二叉树。答案：错误第10题动态查找的概念是指查找中指定关键字不断发生变化的查找。答案：错误填空题第11题算法的五个重要特性分别是：有穷性，___，可行性，有输入，有输出。答案：确定性第12题假定二叉树的数据域为data,左右子树的指针域分别是lChild和rChild，指向根结点的指针为t,完善以下二叉树前序遍历的算法。Preorder(t){___Printf(t->data);Preorder(t->lChild);Preorder(t->rChild);}答案：Preorder(t){if(t==NULL)return;Printf(t->data);Preorder(t->lChild);Preorder(t->rChild);}第13题分块查找的组织过程中，将数据存贮于称之为分场查找表的文件中，分块查找表中对数据的要求是，不同块之间的数据是有序的，同一块中的数据不要求___；与此同时，将块中的关键字存贮于___。答案：有序，索引表第14题昌泡排序算法在最好情况下，比较次数是___。答案：n-1问答题第15题简要描述线性结构的概念。答案：结构中的数据元素之间存在一个对一个的关系，或者结构中的数据元素呈现线性排列的结构。第16题简要描述数据元素的概念。答案：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。第17题简述分块查找的数据结构与算法基本思想？答案：将数据文件分为若干块，各块之间要按一定的顺序排列，即前一块中所有元素的关键字都小于（或大于）后一块中所有元素的关键字，而每一块中的元素是无序的。从各块中抽取最大关键字，与块号共同构成索引表，查找过程如下：以折半查找算法在索引表中查找块号，然后以顺序查找的算法在块内查找数据元素。第18题假设有如下的结构定义：structnode{chardata;structnode*link;}*p,*pre;而且pre指向链表中非空元素，写一段程序生成构造p结点，并将其链入到pre之后。答案：ch=getchar();//取一个数据元素//p=(structnode*)malloc(sizeof(structnode));//申请一个新结点//p->data=ch;p->link=pre->link;pre->link=p;第19题给出求最小代价生成树的Kruskal方法。答案：设给定的图G＝（V,E）构造最小代价生成树的Kruskal方法如下：步骤1置边集合A为空步骤2从图中选择权重最小的一条边e，并从原图中删除