《数据结构与算法》期末练习题 - 2010-2011-1 - 带答案 下载本文

56. 下列内部排序算法中:

A.快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序 (1) 其比较次数与序列初态无关的算法是( ) (2)不稳定的排序算法是( )

(3)在初始序列已基本有序(除去n个元素中的某k个元素后即呈有序,k<

(4)排序的平均时间复杂度为O(n?logn)的算法是( )为O(n?n)的算法是( ) 1 DC 2 ADF 3 B 4 ACF BDE

57. 下列排序算法中(C )排序在一趟结束后不一定能选出一个元素放在其最终位置上。

A. 选择 B. 冒泡 C. 归并 D. 堆 58. 栈和队列都是( A ) A)限制存取位置的线性结构 C)顺序存储的线性结构

B)链式存储的非线性结构 D)限制存取位置的非线性结构

59. 对关键码序列28,16,32,12,60,2,5,72快速排序,从小到大一次划分结果为( B )。

A. (2,5,12,16)26(60,32,72) B. (5,16,2,12)28(60,32,72) C. (2,16,12,5)28(60,32,72) D. (5,16,2,12)28(32,60,72) 60. 一棵含有n个节点的k叉树,可能达到的最小深度为多少?( C ) A) n-k B) n-k+1 C) |logkn|+1 D) |logkn| 其中|k|表示下取整 61. 下列序列中( B )不是堆。

A) 12 36 53 68 48 60 75 B) 12 48 53 68 36 60 75 C) 12 48 36 60 75 68 53 D) 12 36 60 53 48 68 75 62. 在下列内排序方法中,( C )的平均时间复杂性是O(nlogn)。

A) 直接插入排序 B) 简单选择排序 C) 快速排序 D) 希尔排序

63. 设顺序栈s非空,则语句段( C )可实现栈s的出栈操作,其中s.top为栈顶指针,s.elem为栈空间,出栈的元素存放在x中。

A) s.top:=s.top+1; B) x:=s.elem[s.top]; x:=s.elem[s.top]; s.top:=s.top+1; C) s.top:=s.top-1; D) x:=s.elem[s.top]; x:=s.elem[s.top]; s.top:=s.top-1;

64. 有一组数据(15,9,7,8,20,-1,7,4),用堆排序的筛选方法建立的初始堆为 ( C )

A.-1,4,8,9,20,7,15,7 B.-1,7,15,7,4,8,20,9 C.-1,4,7,8,20,15,7,9 D.A,B,C均不对。

65. 下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序( D )。 A)二叉排序树

B)哈夫曼树

C)AVL树

D)堆

66. 下面给出的四种排序法中( D )排序法是不稳定性排序法。

A) 插入 B) 冒泡 C) 二路归并 D) 快速排序 67. 算法的时间复杂度取决于( A )

A.问题的规模 B. 待处理数据的初态 C. A和B D. 计算机cpu

68. 有关静态链表的叙述:(1) 静态链表既有顺序存储的优点,又有动态链表的优点。所以,它存取表中第i个元素的时间与i无关。(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了,以后不能增加。(3) 静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。以上错误的是( B )

A.(1),(2) B.(1) C.(1),(2),(3) D.(2)

69.一个栈的输入序列为123?n,若输出序列的第一个元素是n,输出第i(1<=i<=n)个元素是( B )。

A. 不确定 B. n-i+1 C. i D. n-i 70.下面关于串的的叙述中,哪一个是不正确的?( B )

A.串是字符的有限序列 B.空串是由空格构成的串

C.模式匹配是串的一种重要运算 D.串既可以采用顺序存储,也可以采用链式存储

71. 关于二叉树的叙述:①只有一个结点的二叉树的度为0; ②二叉树的度为2; ③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。正确的是( D )

A.①②③ B.②③④ C.②④ D.①④

72.用DFS遍历一个无环有向图,并在DFS算法退栈返回时打印相应的顶点,则输出的顶点序列是( A )。

A.逆拓扑有序 B.拓扑有序 C.无序的

73. 对n个关键字的序列进行快速排序,平均情况下的空间复杂度为( B ) A.O(1) B.O(logn) C.O(n) D.O(n logn) 二 填空题

1、在单链表L中,指针p所指结点有后继结点的条件是: p->next!=null

2、n(n大于1)个结点的各棵树中,其深度最小的那棵树的深度是_(1)__。它共有_(2)__个叶子结点和_(3)__个非叶子结点,其中深度最大的那棵树的深度是_(4)__,它共有_(5)__个叶子结点和_(6)__个非叶子结点。 (1)2 (2) n-1 (3) 1 (4) n (5) 1 (6) n-1 3、深度为9的完全二叉树最多有 个结点 256

4、二叉树由_(1)__,__(2)_,_(3)__三个基本单元组成。 .(1)根结点(2)左子树(3)右子树

5、先根遍历树林正好等同于按__ _遍历对应的二叉树. 先序

6、设只含根结点的二叉树的高度为0,则高度为k的二叉树的最大结点数为______,最小结点数为______。 (1) 2-1 (2) k+1

7、在有序表A[1..12]中,采用二分查找算法查等于A[12]的元素,所比较的元素下标依次为 6,9,11,12

8、设y指向二叉线索树的一叶子,x指向一待插入结点,现x作为y的左孩子插入,树中标志域为ltag和rtag,并规定标志为1是线索,则下面的一段算法将x插入并修改相应的线索,试补充完整:(lchild,rchild分别代表左,右孩子)

x^.ltag:= (1)___; x^.lchild:= (2)___; y^.ltag:= (3)___; y^.lchild:= (4)___; x^.rtag:= (5)___; x^.rchild:= (6)___;

IF (x^.lchild<>NIL) AND (x^lchild^.rtag=1) THEN x^.lchild^.rchild:= (7)___; (1)1 (2)y^.lchild (3)0 (4)x (5)1 (6) y (7)x(本题按中序线索化) 9、有N个顶点的有向图,至少需要量_______条弧才能保证是连通的。 N-1

10、在顺序表(8,11,15,19,25,26,30,33,42,48,50)中,用二分(折半)法查找关键码值11,需做的关

键码比较次数为 4

11、①二叉树用来表示表达式,因为需要保存各子树的值,修改二叉树的结点结构为(Lchild,Data,Val,Rchild)。其中Lchild,Rchild的意义同前,Val用来存放以该结点为根的子树的值,值的类型依具体情况而定。为了简便起见,算法假定所考虑的表达式只有+,-,*,/ 四种二目运算,且已表示成相应的二叉树。算法所计算的表达式值放在根结点的Val域中。 PROC Postorder-eval(t:ptrType) BEGIN IF (t!=NULL)

K+1

BEGIN (1)_______; (2)_______;

CASE t^.data:

‘+’: t^.Val:=t^. Lchild^. Val + t^. Rchild ^. Val; BREAK;

‘-’: t^.Val:=t^. Lchild^. Val - t^. Rchild ^. Val; BREAK; ‘*’: t^.Val:=t^. Lchild^. Val * t^. Rchild ^. Val; BREAK; ‘/’: t^.Val:=t^. Lchild^. Val / t^. Rchild ^. Val; BREAK; otherwise: (3)___; BREAK; ENDCASE END END;

②PROC Delete(x:datatype,A:tree) BEGIN tempA:= (4)___;

WHILE (tempA^.Item!=x) AND (tempA!=NULL) DO

IF (x

ELSE BEGIN r:=tempA;tempA:=tempA^.Rchild;END;//tempA为要删结点,r为tempA的父亲 IF (6)___ return(x);

IF (tempA^.Lchild!=NULL) AND (tempA^.rchild!=NULL) BEGIN t:=tempA; q:=tempA^.Rchild;

WHILE (q^.Lchild!=NULL) DO BEGIN t:=q; q:=q^.Lchild; END;

t^.Lchild:= (7)___; //删去q

q^.Lchild :=tempA^.Lchild; q^.Rchild:=tempA^.Rchild;

IF (tempA^.item< r^.item) r^.Lchild := (8)_ ELSE r^.Rchild:=q //用q代替 tempA

END;

ELSE IF(tempA^.Lchild!=NULL) IF(tempA^.item

ELSE IF(tempA^.Rchild!=NULL) IF(tempA^.item

ELSE r^.Lchild:=tempA^.Rchild

ELSE //tempA为树叶

IF(10)_ r^.Lchild:=NULL ELSE r^.Rchild:=NULL END;

本题①是表达式求值,②是在二叉排序树中删除值为x的结点。首先查找x,若没有x,则结束。否则分成四种情况讨论:x结点有左右子树;只有左子树;只有右子树和本身是叶子。

(1)Postoder_eval(t^.Lchild) (2) Postorder_eval(t^.Rchild) (3)ERROR(无此运算符)(4)A (5)tempA^.Lchild (6)tempA=NULL (7)q^.Rchild (8)q (9)tempA^.Rchild (10)tempA^.Item

12、利用树的孩子兄弟表示法存储,可以将一棵树转换为______。 二叉树

13、n个结点的完全有向图含有边的数目__(7) n*(n-l)

14、当问题的规模n趋向无穷大时,算法执行时间T(n)的数量级被称为算法的________。 时间复杂度

15、假设S和X分别表示进栈和出栈操作,由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX,则由“a*b+c/d”得到“ab*cd/+”的操作序列为___________。 SXSSXXSSXSSXXX 16、在一棵度为3的树中,度为2的结点个数是1,度为0的结点个数是6,则度为3的结点个数是________。 2

17、设t是给定的一棵二叉树,下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子

的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量,且在调用count(t)之前都置为0. typedef struct node

{int data; struct node *lchild,*rchild;}node; int N2,NL,NR,N0; void count(node *t)

{if (t->lchild!=NULL) if (1)___ N2++; else NL++;

else if (2)___ NR++; else (3)__ ;

if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____; } /*call form :if(t!=NULL) count(t);*/

(1)t->rchild!=null (2)t->rchild!=null (3)N0++ (4)count(t->lchild) (5)count(t->rchild)

18、利用筛选法将关键字序列(37,66,48,29,31,75)建成的大根堆为(____ ____)。 75, 66, 48, 29, 31, 37

19、对长度为20的有序表进行二分查找的判定树的高度为________。 5

20、阅读下列程序说明和程序,填充程序中的______

【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示(编者略)。

本程序采用非递归的方法,设立一个堆栈stack存放还没有转换过的结点,它的栈顶指针为tp。交换左、右子树的算法为:

(1)把根结点放入堆栈。

(2)当堆栈不空时,取出栈顶元素,交换它的左、右子树,并把它的左、右子树分别入栈。 (3)重复(2)直到堆栈为空时为止。 typedef struct node *tree;

struct node{int data; tree lchild,rchild;} exchange(tree t)

{tree r,p; tree stack [500]; int tp=0; (1)_______ while (tp>=0)

{(2)_______ if((3)_______)

{r=p->lchild; p->lchild=p->rchild; p->rchild=r stack[(4)_______]=p->lchild; stack[++tp]=p->rchild; } }}

(1)stack[tp]=t (2) p=stack[tp--] (3)p (4)++tp

21、排序(sorting)有哪几种方法_______________,_____________,____________,_____________,____________。

直接插入排序,冒泡排序,快速排序,希尔排序,归并排序,基数排序,堆排序等 22、下面程序段的时间复杂度为______________。(用O估计) FOR i:=1 TO n DO FOR j:=i TO n DO s=s+j; O(n*n)

23、非线性结构包括______________和_________________。 树,图

24、判断带头结点的双向循环链表L是否对称相等的算法如下所示,请在划线处填上正确的语句