2015(1)年度中国石油大学数据结构试题及答案

typedef int Data Type; typedef struct {

Data Type data[Maxsize]; Int front, rear; } Queue;

若有一个Queue类型的队列Q，试问判断队列满的条件应是下列哪一个语句（ D ）

A Q.front= = Q.rear; B Q.front - Q.rear= = Maxsize; C Q.front + Q.rear= = Maxsize; D Q.front= = (Q.rear+1)% Maxsize; 31、设有一个递归算法如下： int fact (int n ) { if (n<=0) return 1; else return n*fact(n-1); }

下面正确的叙述是（ B ）

A 计算fact(n) 需要执行n次递归 B fact(7)=5040 C 此递归算法最多只能计算到fact(8) D 以上结论都不对

32、设有一个递归算法如下 int x (int n) { if (n<=3) return 1;

else return x(n-2)+x(n-4)+1; }

试问计算 x(x(8))时需要计算（ D ）次x函数。

A 8 次 B 9 次 C 16 次 D 18次

33、设有广义表D(a,b,D),其长度为（ B ），深度为（ A ）

A ∞ B 3 C 2 D 5

34、广义表A(a),则表尾为（ C ）

A a B (( ) ) C 空表 D （a）

35、下列广义表是线性表的有（ C ） A E（a,(b,c)） B E(a,E) C E (a,b) D E(a,L( ) )

36、递归表、再入表、纯表、线性表之间的关系为（ C ）

A 再入表>递归表>纯表>线性表 B 递归表>线性表>再入表>纯表 C 递归表>再入表>纯表>线性表 D递归表>再入表>线性表>纯表

37、某二叉树的前序和后序序列正好相反，则该二叉树一定是（ B ）的二叉树。

A 空或只有一个结点 B 高度等于其结点数

C 任一结点无左孩子 D 任一结点无右孩子

38、对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点为n2.,则( A )

A n0= n2+1 B n2= n0+1 C n0= 2n2+1 D n2=2n0+1

39、 由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（B ）

A 24 B 73 C 48 D 53

40、已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为da1,则第I 个结点的地址为（ A ）。 A da1+(I-1)*m B da1+I*m C da1-I*m D da1+(I+1)*m

41、34 具有35个结点的完全二叉树的深度为( A )

A 5 B 6 C 7 D 8 42、对线性表进行折半搜索时，要求线性表必须（ C ）

A 以链接方式存储且结点按关键码有序排列 B 以数组方式存储 C 以数组方式存储且结点按关键码有序排列 D以链接方式存储 43、顺序搜索算法适合于存储结构为（ B ）的线性表。