数据结构期末复习.doc

《数据结构期末复习.doc》由会员分享，可在线阅读，更多相关《数据结构期末复习.doc（140页珍藏版）》请在三一文库上搜索。

1、练习一1第16题要将现实生活中的数据转化为计算机所能表示的形式，其转化过程依次为()。A.逻辑结构、存储结构、机外表示B.存储结构、逻辑结构、机外表示C.机外表示、逻辑结构、存储结构D.机外表示、存储结构、逻辑结构答案:C2第17题关于矩阵的三元组表表示，以下叙述正确的是()。A.转置运算时只需把每个三元组的行、列下标互换即可。B.存储时只需要各非零元素的三元组信息，不需要其它信息。C.适合于对称矩阵的压缩存储。D.访问元素时不能随机存取。答案:D3第24题对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8，查找后面5个元素的概率相同，均为3/40，则查找任一元素的平均查找

2、长度为()。A.5.5B.5C.39/8D.19/4答案:C4第25题若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用()存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表答案:D5第27题将数组称为随机存储结构是因为()。A.数组元素是随机的B.随时可以对数组元素进行访问C.对数组的任一元素的存取时间是相等的D.数组的存储结构是不定的答案:C6第28题在下列排序方法中，空间复杂性为O(log2n)的方法为()。A.直接选择排序B.归并排序C.堆排序D.快速排序答案:D7第30题对n个顶点和e条边的有向图，以邻接矩阵

3、存储，则求图中某顶点入度的时间复杂度为()。A)O(n)B)O(e)C)O(n+e)D)O(n2)A.AB.BC.CD.D答案:A8第31题图的广度遍历必须借助()作为辅助空间。A.栈B.队列C.查找表D.数组答案:B9第39题基数排序中的“基数”可以是()。A.10B.8C.16D.以上都可以答案:D10第40题n个记录直接插入排序时所需的记录最少比较次数是()。A.n-1B.nC.n(n-1)/2D.n(n+1)/2答案:A11第41题下图所示二叉树对应的森林中有()棵树。A.1B.2C.3D.不确定答案:C12第42题对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为()。A.求

4、顶点的邻接点B.求顶点的度C.深度优先遍历D.广度优先遍历答案:B13第52题二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序()。A.可能改变B.一定会改变C.一定不改变D.可能变也可能不变答案:C14第53题下列叙述错误的是()。A.多维数组是向量的推广。B.多维数组是非线性结构。C.如果将二维数组看成由若干个行向量组成的一维数组，则为线性结构。D.对矩阵进行压缩存储的目的是为了数据加密。答案:D15第54题以下关于算法叙述不正确的是()。A.时间和空间性能往往是一对矛盾B.常常可牺牲空间性能换取时间性能C.常常可牺牲时间性能换取空间性能D.时间和空间性能并不会矛盾答案:D16第55

5、题由同一关键字集合构造的各棵二叉排序树()。A.形态和平均查找长度都不一定相同B.形态不一定相同，但平均查找长度相同C.形态和平均查找长度都相同D.形态相同，但平均查找长度不一定相同答案:A17第56题算法的时间复杂度取决于()。A.问题的规模B.数据的初始状态C.A和BD.以上都不是答案:C18第57题对二叉排序树进行()，可以得到各结点键值的递增序列。A.先根遍历B.中根遍历C.层次遍历D.后根遍历答案:B19第58题串是()。A.一些符号构成的序列B.有限个字母构成的序列C.一个以上的字符构成的序列D.有限个字符构成的序列答案:D20第59题以下广义表关系正确的是()。A.线性表再入表纯

6、表递归表B.线性表纯表递归表再入表C.纯表线性表再入表递归表D.线性表纯表再入表递归表答案:D21第63题以下叙述错误的是()。A.数据的三个层次是数据、数据元素、数据项B.数据类型是指相同性质的计算机数据的集合C.每种逻辑结构都有一个运算的集合D.储存结构中不仅要储存数据的内容，还要把数据间的关系表示出来。答案:B22第64题若只在线性表的首、尾两端进行插入操作，宜采用的存储结构为()。A.顺序表B.用头指针表示的单循环链表C.用尾指针表示的单循环链表D.单链表答案:C23第65题栈操作的原则是()。A.先进先出B.后进先出C.栈底删除D.以上都不是答案:B24第66题若下图表示某广义表，则

7、它是一种()。A.线性表B.纯表C.再入表D.递归表答案:D25第67题导致队列下溢的操作是()。A.队满时执行出队B.队满时执行入队C.队空时执行出队D.队空时执行入队答案:C27第69题关键字比较次数与数据的初始状态无关的排序算法是()。A.直接选择排序B.冒泡排序C.直接插入排序D.希尔排序答案:A28第70题对n个元素进行冒泡排序，最好情况下的只需进行()对相邻元素之间的比较。A.nB.n-1C.n+1D.n/2答案:B29第71题对n个顶点的有向图，若所有顶点的出度之和为s，则所有顶点的入度之和为()。A.sB.s-1C.s+1D.n答案:A30第72题与邻接表表示相比，邻接矩阵表示

8、更适合()。A.无向图B.有向图C.稠密图D.稀疏图答案:C31第89题多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为()。A.数组的元素处在行和列两个关系中B.数组的元素必须从左到右顺序排列C.数组的元素之间存在次序关系D.数组是多维结构，内存是一维结构答案:A32第90题高度为n、结点数也为n的二叉树，共有()棵。A）nB）2n-1C）n-1D）2n-1A.AB.BC.CD.D答案:D33第91题单链表中增加头结点的目的是为了()。A.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储答案:C34第92题对n个结点的二叉树，按()

9、遍历顺序对结点编号（号码为1n）时，任一结点的编号等于其左子树中结点的最大编号加1，又等于其右子树中结点的最小编号减1。A.前根B.中根C.后根D.层次答案:B35第93题算法分析是指()。A.分析算法的正确性B.分析算法的可读性C.分析算法的健壮性D.分析算法的时空性能答案:D36第94题栈和队列的共同特点是()。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点答案:C37第95题下列关于串的叙述中，正确的是()。A.一个串的字符个数即该串的长度B.一个串的长度至少是1C.空串是由空格字符组成的串D.两个串若长度相同，则它们相等答案:A38第96题希尔排序的增量

10、序列必须是()。A.递增的B.随机的C.递减的D.任意的答案:C39第97题在不完全排序的情况下，就可以找出前几个最大值的方法是()。A.快速排序B.直接插入排序C.堆排序D.归并排序答案:C40第98题若要在O(1)的时间内将两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向()。A.各自的头结点B.各自的尾结点C.各自的第一个元素结点D.一个表的头结点，另一个表的尾结点答案:B41第99题在n个顶点和e条边的无向图的邻接表中，边结点的个数为()。A.nB.n*eC.eD.2*e答案:D42第100题若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调

11、用()次深度优先搜索遍历的算法。A.1B.kC.k-1D.k+1答案:B43第22题连通图的BFS生成树一般比DFS生成树的高度小。答案:正确44第23题利用栈可将递归程序转化成非递归程序。答案:正确45第29题每一种逻辑结构只能对应一种存储结构。答案:错误46第32题用线性探测法解决突出时，同义词在散列表中是相邻的。47第33题链表中逻辑上相邻的元素在物理位置上不一定相邻。答案:正确48第34题稀疏矩阵就是矩阵的元素很少。答案:错误49第35题堆排序是一种巧妙的树型选择排序。答案:正确50第36题图G的生成树T是G的子图。答案:正确51第37题二叉树中不可能有两个结点在先根、中根和后根序列中

12、的相对次序都不变。答案:错误52第43题若二叉树中没有度为1的结点，则为满二叉树。答案:错误53第44题空串并不是由空白字符组成的串。答案:正确54第45题在顺序表中按值查找运算的复杂性为O(1)。答案:错误55第46题如果根结点的左子树和右子树高度差不超过1，则该二叉树是平衡二叉树。答案:错误56第47题排序的目的是为了方便以后的查找。答案:正确57第48题基数排序不需进行关键字间的比较，故执行时间比基于比较的排序方法要快。答案:错误58第49题如果网络中有多条边的权相同，则其最小生成树就不会是唯一的。答案:错误59第50题在栈的应用中，栈顶指针总是指向真正的栈顶。答案:错误60第73题线索

13、二叉链表就是用结点的空指针域来存放某种遍历的前趋和后继线索，所以线索二叉链表中就没有空指针了。答案:错误61第74题数据的逻辑结构和运算集组成问题的数学模型，与计算机无关。答案:正确62第75题单链表中的头结点就是单链表的第一个结点。答案:错误63第76题一维数组是一种顺序表。答案:正确64第77题直接插入排序是稳定的，而Shell排序就是调用若干趟直接插入排序，故也是稳定的。答案:错误65第78题二叉排序树上，以根到任一结点的路径为界，则：路径左边结点路径结点路径右边结点。答案:错误66第79题不是所有的有向图都可以进行拓扑排序，而能拓扑排序时，结果不一定唯一。答案:正确67第80题稀疏矩阵

14、压缩存储后会丧失随机存取特性。答案:正确68第101题当问题具有先进先出特点时，就需要用到栈。答案:错误69第102题算法的时间复杂性越高，则计算机速度提高后，得到的收益就越大。答案:错误70第103题顺序表不需存放指针，链表要存放指针，故链表的存储空间要求总是比顺序表大。答案:错误71第104题n个结点的有向图，若它有n(n1)条边，则它一定是强连通的。答案:正确72第105题二路归并排序的核心操作是把两个有序序列合并为一个有序序列。答案:正确73第1题树的三种常用存储结构是：孩子链表表示法、_和_。答案:双亲链表、孩子兄弟链表74第2题线索二叉树中，线索的含义是_。答案:某种遍历的前趋或后

15、继信息75第3题运算定义在逻辑结构上，算法定义在_结构上；运算指出“做什么”，算法指出_。答案:储存；怎么做76第4题下面程序段的时间复杂性为_。y=1;while(yn)y=y*3;答案:O(log3n)77第5题下面程序段的时间复杂性为_。for(i=0;in;i+)for(j=0;jnext!=NULL&p-next-next=NULL83第11题内排序是指_。答案:数据全部在内存中进行排序84第12题对n个结点的线索二叉树，线索有_个。答案:n+185第13题稀疏矩阵的三元组表示中，三元组是指非零元素的_、_和_三项。答案:行号、列号、值86第14题四种基本逻辑结构是：_、_、树、图；

16、可把它们分成两类：_和_。答案:集合、线性；线性、非线性87第15题程序设计的实质是：数据的表示和_，或者说，程序=数据结构_。答案:数据的处理；算法88第18题设链栈结点结构为(data,next)，top为栈顶指针，当执行入栈操作时需执行下列语句：p=newnode;p-data=x;p-nexttop;_;答案:top=p89第19题深度为k的二叉树，结点数至多为_，结点数至少为_。答案:2k-1、k90第20题某完全二叉树的第5层只有6个结点，则其叶子结点数是_。答案:1191第26题四种基本存储结构是：顺序、_、索引、_；其中最基本的是：_和_。答案:链式、散列；顺序、链式92第60

17、题散列表中同义词是指_。答案:键值不同但散列地址相同93第61题设元素a1，a2，a3，a4，a5和a6依次入栈，出栈顺序为a3，a5，a4，a6，a2，a1，则栈的容量至少为_。答案:494第62题串The含有的子串个数为_。答案:795第81题“就地排序”是指排序算法辅助空间的复杂度为_。答案:O(1)96第82题对n个顶点和e条边的图，采用邻接矩阵和邻接表表示时，空间复杂性分别为_和_。答案:O(n2)、O(n+e)97第83题若有向图有2个有向回路，则其拓扑序列有_个。答案:098第84题某树所有结点的度数之和为100，则树中边数为_。答案:10099第85题深度为k的二叉树，叶子数至

18、多为_，叶子数至少为_。答案: 2k-1、1100第86题某哈夫曼树有109个结点，则其叶子数是_，度为2的结点数是_。答案:55、54101第87题某二叉树有50个结点，根的右子树有45个结点，则对应的森林中第一棵树的结点数为_。答案:55102第88题以行优先存储的一维数组A1.10，每个元素占4字节，A5的地址是1020，则数组的首地址是_。答案:1004103第21题设计递归算法，判断二叉树t是否满足小根堆的特点。二叉链表的类型定义如下：typedefintdatatype;/结点的数据类型，假设为inttypedefstructNODE*pointer;/结点指针类型structNO

19、DEdatatypedata;pointerlchild,rchild;typedefpointerbitree;/根指针类型答案:intdetect(bitreet)if(t=NULL)return1;/空树看成真if(t-lchild!=NULL&t-lchild-datat-data),(t-rchild!=NULL&t-rchild-datat-data)return0;/左孩子根，或右孩子根，为假elsereturndetect(t-rchild)&detect(t-rchild);题目分数：2.5104第38题设计递归算法，求二叉排序树t的高度。二叉链表的类型定义如下：typede

20、fintdatatype;/结点的数据类型，假设为inttypedefstructNODE*pointer;/结点指针类型structNODEdatatypedata;pointerlchild,rchild;typedefpointerbitree;/根指针类型答案:inthigh(bitreet)intL,R;if(t=NULL)return0;L=high(t-lchild);R=high(t-rchild);returnLR?L+1:R+1;105第51题设计算法将顺序表L中所有的数字字符都移动到表的后端，要求元素的移动次数尽量少。顺序表类型定义如下：typedefchardataty

21、pe;/结点的数据类型，假设为charconstintmaxsize=100;/最大表长，假设为100typedefstructdatatypedatamaxsize;/线性表的存储向量，第一个结点是data0intn;/线性表的当前长度sqlist;/顺序表类型答案:voidmoves(sqlist*L)inti,j;datatypex;i=1;j=L-n;while(idataidatai9)&idatai=0&L-datai=9)&ij)j-;if(idatai;L-datai=L-dataj;L-dataj=x;i+;j-;练习二2第2题下列编码中属前缀码的是()。A.1,01,000

22、001B.1,01,011,010C.0,10,110,11D.0,1,00,11答案:A3第3题线性表采用链式存储时，其地址()。A.必须连续B.部分地址必须连续C.一定不连续D.连续与否均可答案:D4第4题设计一个判断表达式中左右括号是否配对出现的算法，采用()数据结构最好。A.顺序表B.链表C.队列D.栈答案:D5第5题执行下列程序段后，串X的值为()。S=”abc”;T=”xyz”;X=strcat(S,T);A.”abcxyz”B.”xyzabc”C.”abc”D.”xyz”答案:A7第7题某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用()存储方式最

23、节省运算时间。A.单链表B.双链表C.单循环链表D.带头结点的双循环链表答案:D9第9题设有向图n个顶点和e条边，进行拓扑排序时，总的计算时间为()。A)O(nlog2n)B)O(en)C)O(elog2n)D)O(n+e)A.AB.BC.CD.D答案:D10第22题在n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素个数为()。A.nB.n*eC.eD.2*e答案:D11第23题为便于判别有向图中是否存在回路，可借助于()。A.广度优先搜索算法B.最小生成树算法C.最短路径算法D.拓扑排序算法答案:D12第29题栈和队列都是()。A.限制存取位置的线性结构B.顺序存储的线性结构C.链式存

24、储的线性结构D.限制存取位置的非线性结构答案:A13第30题在C语言中，串的存储方式是()。A.顺序存储B.散列存储C.索引存储D.链式存储答案:A15第32题用链表表示线性表的优点是()。A.便于随机存取B.花费的存储空间较顺序存储少C.便于插入和删除D.数据元素的物理顺序与逻辑顺序相同答案:C16第33题对有向图，下面()种说法是正确的。A.每个顶点的入度等于出度B.每个顶点的度等于其入度与出度之和C.每个顶点的入度为0D.每个顶点的出度为0答案:B17第34题图的深度遍历必须借助()作为辅助空间。A.栈B.队列C.查找表D.数组答案:A18第46题已知森林F=T1，T2，T3，各棵树Ti

25、i=1，2，3)中所含结点的个数分别为7，3，5，则与F对应的二叉树的右子树中的结点个数为()。A.10B.12C.8D.15答案:C20第56题下列排序方法中，不稳定的是()。A.冒泡排序B.归并排序C.希尔排序D.直接插入排序答案:C21第57题以下叙述错误的是()。A.树的先根遍历需要借助栈来实现。B.树的层次遍历需要借助队列来实现。C.树的后根遍历与对应二叉树的后根遍历相同。D.树的先根序列与对应二叉树的先根序列相同。答案:C22第58题在顺序表中，数据元素之间的逻辑关系用()。A.数据元素的相邻地址表示B.数据元素在表中的序号表示C.指向后继元素的指针表示D.数据元素的值表示答案:

26、A24第60题为查找某一特定单词在文本中出现的位置，可应用的串运算是()。A.插入B.删除C.串联接D.子串定位答案:D25第61题在待排关键字序列基本有序的前提下，效率最高的排序方法是()。A.直接插入排序B.快速排序C.直接选择排序D.归并排序答案:A26第62题循环链表的主要优点是()。A.不在需要头指针了B.已知某个结点的位置后，能够容易找到他的直接前趋C.在进行插入、删除运算时，能更好的保证链表不断开D.从表中的任意结点出发都能扫描到整个链表答案:D27第63题从理论上讲，将数据以()结构存放，查找一个数据的时间不依赖于数据的个数n。A.二叉查找树B.链表C.散列表D.顺序表答案:C

27、28第64题下面关于线性表的叙述错误的是()。A.线性表采用顺序存储，必须占用一片地址连续的单元；B.线性表采用顺序存储，便于进行插入和删除操作；C.线性表采用链式存储，不必占用一片地址连续的单元；D.线性表采用链式存储，便于进行插入和删除操作；答案:B33第83题在AVL树中，任一结点的()。A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左、右子树的结点数均相同D.左、右子树结点数差的绝对值不超过1答案:B34第84题设输入序列为A,B,C,D，借助一个队列得到的输出序列可能是()。A.ABCDB.DCBAC.任意顺序D.以上都不是答案:A35第91题下列排序算法中，当初

28、始数据有序时，花费时间反而最多的是()。A.起泡排序B.希尔排序C.堆排序D.快速排序答案:D36第92题若结点的存储地址可以反映数据间的逻辑关系，则相应的存储结构应为()。A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构答案:A37第93题若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用()存储方式最节省运算时间()。A.单链表B.顺序表C.双链表D.单循环链表答案:B38第94题队列操作的原则是()。A.先进先出B.后进先出C.队尾删除D.队头插入答案:A40第96题n个记录直接选择排序时所需的记录最多交换次数是()。A.n-1B.nC.n(n-1)/

29、2D.n(n+1)/2答案:A41第97题某二叉树的先根遍历序列和后根遍历序列相同，则该二叉树的特征是()。A.高度等于其结点数B.任一结点无左孩子C.任一结点无右孩子D.空或只有一个结点答案:D42第98题如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是()。A.有向完全图B.连通图C.强连通图D.有向无环图答案:D44第11题计算机的内、外存越大，算法的空间复杂性就越低。答案:错误47第14题在拓扑序列中，若两点Vi和Vj相邻，则从Vi到Vj有路径。答案:错误48第15题数组的基本运算有读、写、插入、删除等。答案:错误49第21题在二叉排序树中，即使删除一个结点后马上再插入该结点

30、该二叉排序树的形态也可能不同。答案:正确52第26题图的生成树不唯一，但图的最小生成树是唯一的。答案:错误53第27题设串的长度为n，则其子串个数为n(n+1)/2。答案:错误54第35题消除递归不一定需要使用栈。答案:正确56第37题每个节点一个链域的链表是单链表，每个节点两个链域的链表是双链表。答案:错误58第39题Shell排序的时间性能与增量序列的选取有关，但关系不大。答案:错误59第40题若有向图中含有一个或多个环，则其顶点间不存在拓扑序列。答案:正确60第41题线性表、树、图等都可以用广义表表示。答案:正确62第68题在线索二叉树上，求结点的(遍历)前趋和后继时可利用线索得到，即

31、不必进行遍历了。答案:错误63第69题单链表中取第i个元素的时间与i成正比。答案:正确64第70题无向图中边数等于邻接矩阵中1的个数的一半；也等于邻接表中的边表结点数的一半。答案:正确67第99题由二叉树的先根和后根序列可以唯一确定该二叉树。答案:错误68第100题算法的正确性，一般不进行形式化的证明，而是用测试来验证。答案:正确70第102题广义表不仅是线性表的推广，也是树的推广。答案:正确72第104题缩短关键路径上活动的工期一定能够缩短整个工程的工期。答案:错误73第16题散列表既是一种_方式又是一种_方法。答案:储存、查找储存、查找74第17题某完全二叉树的第5层只有6个结点，则其叶子

32、结点数是_。答案:111175第18题在无头结点的双链表中，指针P所指结点是第一个结点的条件是_。答案:p-prior=NULLp-prior=NULL76第19题可以将排序算法分为：插入排序、_、选择排序、_、分配排序。答案:交换排序、归并排序交换排序、归并排序77第20题设C数组A2010每个元素占2个存储单元，且第1个元素的首地址为2000，则元素A89的存储地址为_。答案:2178217878第42题对n个顶点和e条边的无向图，采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂性分别为_和_。答案:O(n)、O(e/n)O(n)、O(e/n)79第43题将长度为2n和n的有序表归并成

33、一个有序表，至少进行_次键值比较。答案:nn80第44题若有向图有2个有向回路，则其拓扑序列有_个。答案:0081第45题算法满足的五个重要特性是：_、_、_、输入、输出；其中区别于程序的地方是_。答案:有穷性、确定性、可行性；有穷性。有穷性、确定性、可行性；有穷性。82第48题查找表的逻辑结构是_。答案:集合集合83第49题设链栈结点结构为(data,next)，top为栈顶指针，当执行入栈操作时需执行下列语句：p=newnode;p-data=x;p-nexttop;_;答案:top=ptop=p85第51题从n个结点的二叉排序树中查找一个元素，平均时间复杂性大致为_。答案:O(log2n

34、)O(log2n)86第52题深度为k的二叉树，结点数至多为_，结点数至少为_。答案:2k-1、k88第54题在有向无环图中，若存在一条从顶点i到顶点j的弧，则在顶点的拓扑序列中，顶点i与顶点j的先后次序是_。答案:i在j之前i在j之前89第55题对n个结点的线索二叉树，线索有_个。答案:n+1n+190第74题在一个双链表中删除指针p所指结点，可执行以下操作：p-next-prior=_；p-prior-next=_；_；答案:p、p、deletepp、p、deletep91第75题所有基于比较的排序方法，平均时间复杂性最好时为_。答案:O(nlog2n)O(nlog2n)92第76题n个顶

35、点的连通图至少_条边，最多_条边。答案:n-1、n(n-1)/2n-1、n(n-1)/293第77题将对称矩阵A1.n1.n的下三角(含对角线)按行序存入一维数组B1.n(n+1)/2中，设Aij对应位置Bk，则k=_。答案:i(i-1)/2+ji(i-1)/2+j94第79题对长度为100的顺序表，在等概率情况下，查找成功时的平均查找长度为_，在查找不成功时的平均查找长度为_。答案:50/2、100(或101)50/2、100(或101)95第80题设元素a1，a2，a3，a4，a5和a6依次入栈，出栈顺序为a3，a5，a4，a6，a2，a1，则栈的容量至少为_。答案:497第85题在150

36、个结点的有序表中二分法查找，不论成功与否，键值比较次数最多为_。答案:8898第86题对100个结点的树，所有结点的度数之和为_。答案:999999第87题用head()和tail()函数表示在广义表A=(a,(x,y,z),b)中取出原子x的运算是：_。答案:head(head(tail(A)head(head(tail(A)100第88题Prim算法求最小生成树的时间为_，对_图比较有利。答案:O(n2)、稠密O(n2)、稠密101第89题评价排序效率的主要标准是_。答案:关键字比较次数、移动次数关键字比较次数、移动次数102第90题数组A1.81.10中，每个元素占3个单元，从首地址SA

37、开始存放，若该数组按列存放，则元素A85的地址是_答案:SA+117SA+117103第28题设计递归算法，求二叉排序树t的叶子数。二叉链表的类型定义如下：typedefintdatatype;/结点的数据类型，假设为inttypedefstructNODE*pointer;/结点指针类型structNODEdatatypedata;pointerlchild,rchild;typedefpointerbitree;/根指针类型答案:intleaf(bitreet)intL,R;if(t=NULL)return0;if(t-child=NULL&t-rchild=NULL)return1;L=

38、leaf(t-lchild);R=leaf(t-rchild);returnL+R;intleaf(bitreet)intL,R;if(t=NULL)return0;if(t-child=NULL&t-rchild=NULL)return1;L=leaf(t-lchild);R=leaf(t-rchild);returnL+R;题目分数：2.5104第73题设计递归算法，判断二叉树t是否满足小根堆的特点。二叉链表的类型定义如下：typedefintdatatype;/结点的数据类型，假设为inttypedefstructNODE*pointer;/结点指针类型structNODEdatatyp

39、edata;pointerlchild,rchild;typedefpointerbitree;/根指针类型答案:intdetect(bitreet)if(t=NULL)return1;/空树看成真if(t-lchild!=NULL&t-lchild-datat-data),(t-rchild!=NULL&t-rchild-datat-data)return0;/左孩子根，或右孩子根，为假elsereturndetect(t-rchild)&detect(t-rchild);intdetect(bitreet)if(t=NULL)return1;/空树看成真if(t-lchild!=NULL&t-lchild-datat-data)|(t-rchild!=NULL&t-rchild-datat-data)return0;/左孩子根，