数据结构试题集(包含答案 - 完整版)

k的值是( B )。

A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j

13、广义表A=((a),a)的表头是( B )。

A. a B. (a) C. b D. ((a)) 14、稀疏矩阵一般的压缩存储方法有两种,即( C )。

A. 二维数组和三维数组 B. 三元组和散列 C. 三元组和十字链表 D. 散列和十字链表

15、假设以三元组表表示稀疏矩阵,则与如图所示三元组表对应的4×5的稀疏矩阵是(注:矩阵的行列下标均从1开始)( B )。

?0?8?0?7A. ?00???50??0?8?0?0C. ?70???50?060??000?

000??400??060??003?

000??400???0?8?0?7B. ??50??00?060??003?

400??000??060??000?

403??000??

?0?8?0?7 D. ??50??00?16、以下有关广义表的表述中,正确的是( A )。

A. 由0个或多个原子或子表构成的有限序列 B. 至少有一个元素是子表

C. 不能递归定义 D. 不能为空表 17、对广义表L=((a,b),((c,d),(e,f)))执行head(tail(head(tail(L))))操作的结果是(D )。

A. 的 B. e C. (e) D. (e,f) 二、判断题

(× )1、广义表中原子个数即为广义表的长度。

( ×)2、一个稀疏矩阵采用三元组表示,若把三元组中有关行下标与列下标的值互换,并把mu和nu的值进行互换,则完成了矩阵转置。

(√ )3、稀疏矩阵压缩存储后,必会失去随机存取功能。 (× )4、广义表的长度是指广义表中括号嵌套的层数。

(√ )5、广义表是一种多层次的数据结构,其元素可以是单原子也可以是子表。 三、填空题

1、已知二维数组A[m][n]采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOC(A[0][0]),则A[i][j]的地址是___ Loc(A[0][0])+(i*N+j)*k ____。

2、广义表运算式HEAD(TAIL((a,b,c),(x,y,z)))的结果是: (x,y,z) 。 3、二维数组,可以按照 列序为主和行序为主 两种不同的存储方式。

4、稀疏矩阵的压缩存储方式有: 三元组 和 十字链表 。 四、综合题

1、现有一个稀疏矩阵,请给出它的三元组表。

?0?1??0??0i112334300?0??

210??0?20?j231233v31121-210答案:

第六章 树

一、选择题

1、二叉树的深度为k,则二叉树最多有( C )个结点。

A. 2k B. 2k-1 C. 2k-1 D. 2k-1

2、用顺序存储的方法,将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中,若结点R[i]有右孩子,则其右孩子是( B )。

A. R[2i-1] B. R[2i+1] C. R[2i] D. R[2/i] 3、设a,b为一棵二叉树上的两个结点,在中序遍历时,a在b前面的条件是( B )。

A. a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙

4、设一棵二叉树的中序遍历序列:badce,后序遍历序列:bdeca,则二叉树先序遍历序列为( D )。

A. adbce B. decab C. debac D. abcde 5、在一棵具有5层的满二叉树中结点总数为( A )。 A. 31 B. 32 C. 33 D. 16

6、由二叉树的前序和后序遍历序列( B )惟一确定这棵二叉树。

A. 能 B. 不能

7、某二叉树的中序序列为ABCDEFG,后序序列为BDCAFGE,则其左子树中结点数目为( C )。

A. 3 B. 2 C. 4 D. 5

8、若以{4,5,6,7,8}作为权值构造哈夫曼树,则该树的带权路径长度为( C )。

A. 67 B. 68 C. 69 D. 70

9、将一棵有100个结点的完全二叉树从根这一层开始,每一层上从左到右依次对结点进行编号,根结点的编号为1,则编号为49的结点的左孩子编号为( A )。

A. 98 B. 99 C. 50 D. 48 10、表达式a*(b+c)-d的后缀表达式是( B )。

A. abcd+- B. abc+*d- C. abc*+d- D. -+*abcd

11、对某二叉树进行先序遍历的结果为ABDEFC,中序遍历的结果为DBFEAC,则后序遍历的结果是( B )。

A. DBFEAC B. DFEBCA C. BDFECA D. BDEFAC 12、树最适合用来表示( C )。

A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据

13、表达式A*(B+C)/(D-E+F)的后缀表达式是( C )。

A. A*B+C/D-E+F B. AB*C+D/E-F+ C. ABC+*DE-F+/ D. ABCDED*+/-+

14、在线索二叉树中,t所指结点没有左子树的充要条件是(B )。

A. t->left==NULL B. t->ltag==1 C. t->ltag==1&&t->left==NULL D. 以上都不对

15、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序(A )。

A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对

16、假定在一棵二叉树中,度为2的结点数为15,度为1的结点数为30,则叶子结点数为( B )个。

A. 15 B. 16 C. 17 D. 47 17、在下列情况中,可称为二叉树的是( B )。 A. 每个结点至多有两棵子树的树 B. 哈夫曼树

C. 每个结点至多有两棵子树的有序树 D. 每个结点只有一棵子树

18、用顺序存储的方法,将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..n]中,若结点R[i]有左孩子,则其左孩子是(C )。

A. R[2i-1] B. R[2i+1] C. R[2i] D. R[2/i] 19、下面说法中正确的是( D )。

A. 度为2的树是二叉树 B. 度为2的有序树是二叉树

C. 子树有严格左右之分的树是二叉树 D. 子树有严格左右之分,且度不超过2的树是二叉树

20、树的先根序列等同于与该树对应的二叉树的(A )。

A. 先序序列 B. 中序序列 C. 后序序列 D. 层序序列

21、按照二叉树的定义,具有3个结点的二叉树有( C )种。

A. 3 B. 4 C. 5 D. 6 22、由权值为3,6,7,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为( A )。

A. 51 B. 23 C. 53 D. 74 二、判断题

( √)1、存在这样的二叉树,对它采用任何次序的遍历,结果相同。 (× )2、中序遍历一棵二叉排序树的结点,可得到排好序的结点序列。 ( √)3、对于任意非空二叉树,要设计其后序遍历的非递归算法而不使用堆栈结构,最适合的方法是对该二叉树采用三叉链表。

(× )4、在哈夫曼编码中,当两个字符出现的频率相同时,其编码也相同,对于这种情况应做特殊处理。

(√ )5、一个含有n个结点的完全二叉树,它的高度是?log2n?+1。 (√ )6、完全二叉树的某结点若无左孩子,则它必是叶结点。 三、填空题

1、具有n个结点的完全二叉树的深度是 ?log2n?+1 。 2、哈夫曼树是其树的带权路径长度 最小 的二叉树。

3、在一棵二叉树中,度为0的结点的个数是n0,度为2的结点的个数为n2,则有n0= N2+1 。

4、树内各结点度的 最大值 称为树的度。 四、代码填空题

1、函数InOrderTraverse(Bitree bt)实现二叉树的中序遍历,请在空格处将算法补充完整。

void InOrderTraverse(BiTree bt){ if( ){

InOrderTraverse(bt->lchild); printf(“%c”,bt->data);

; } }

2、函数depth实现返回二叉树的高度,请在空格处将算法补充完整。 int depth(Bitree *t){ if(t==NULL) return 0; else{

hl=depth(t->lchild);

hr= depth(t->rchild) ; if( hl>hr ) return hl+1; else

return hr+1; } }

3、写出下面算法的功能。

Bitree *function(Bitree *bt){ Bitree *t,*t1,*t2; if(bt==NULL) t=NULL; else{

t=(Bitree *)malloc(sizeof(Bitree)); t->data=bt->data;

t1=function(bt->left); t2=function(bt->right); t->left=t2; t->right=t1; }

return(t); }

答案:交换二叉树结点左右子树的递归算法

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4