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 1833、设有广义表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)） E(a,L( ) )
36、递归表、再入表、纯表、线性表之间的关系为（ C ）
A 再入表>递归表>纯表>线性表 B 递归表>线性表>再入表>纯表 C 递归表>再入表>纯表>线性表
D递归表>再入表>线性表>纯表
B E(a,E)
C E (a,b)
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 ）的线性表。 A 散列存储 C 压缩存储
B 顺序存储或链接存储 D 索引存储
44、采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（ C ） A O（n2）
B O（n log2n） C O（log2n）
D O（n）
45、对于一个具有n个顶点和e条边的无向图，进行拓扑排序时，总的时间为( A ) A n
B n+1
C n-1
D n+e
46、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（C ）。
A 求关键路径的方法 B 求最短路径的Dijkstra方法 C 深度优先遍历算法
D 广度优先遍历算法
47、在10阶B-树中根结点所包含的关键码个数最多为（C ），最少为( A ) A 1
B 2
C 9
D 10
48、对包含n 个元素的散列表进行搜索，平均搜索长度为（ C ） A O（log2n） B O（n）
C 不直接依赖于n D 上述都不对
二、 填空题（）
1、 数据的逻辑结构被分为集合结构、线性结构、树形结构、图形结构 四种 2、 数据的存储结构被分为顺序结构、链接结构、索引结构、散列结构 四种 3、一种抽象数据类型包括（数据 ）和（操作 ）两个部分。
4、设有两个串p和q，求p在q中首次出现的位置的运算称为（模式匹配） 5、 栈、队列逻辑上都是（线性存储）结构。
6、 线性结构反映结点间的逻辑关系是（一对一）的，图中的数据元素之间的关
系是（多对多）的，树形结构中数据元素间的关系是（一对多）的。 7、栈中存取数据的原则（ 后进先出），队列中存取数据的原则（ 先进先出 ）
8、串是由（ 零个或多个）字符组成的序列。（ 长度为零的串 ）称为空串，（ 由一个或多个空格组成的串）称为空格串。
9、设目标串T=”abccdcdccbaa”,模式P=”cdcc”则第（6）次匹配成功。 10、一维数组的逻辑结构是（线性结构），存储结构是（顺序存储表示）。对于二维数组，有（行优先顺序）和（列优先顺序）两种不同的存储方式，对于一个二维数组A[m][n],若采用按行优先存放的方式，则任一数组元素A[i][j]相对于A[0][0]的地址为（ n*i+j）。
11、向一个顺序栈插入一个元素时，首先使（ 栈顶指针 ）后移一个位置，然后把待插入元素（ 写 ）到这个位置上。从一个顺序栈删除元素时，需要前移一位（栈顶指针）。
12、在一个循环队列Q中，判断队空的条件为（Q.front= =Q.rear）, 判断队满的条件为（ (Q.rear+1)%MaxSize= =q.front ）
13、对于一棵具有n个结点的树，该树中所有结点的度数之和为（ n-1 ）。 14、一棵高度为5的满二叉树中的结点数为（ 63 ）个，一棵高度为3满四叉树中的结点数为（ 85 ）个。
15、若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一维数组中，即编号为0的结点存储到a[0]中，其余类推，则a[i]元素的左子女结点为（ 2*i+1），右子女结点为（ 2*i+2 ），双亲结点（i>=1 ）为（「(i-1)/2 ┐ ）.
16、在一个最大堆中，堆顶结点的值是所有结点中的（最大值），在一个最小堆中，堆顶结点的值是所有结点中的（最小值）。
17、已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为LOC(a1)，那么，LOC(ai)= LOC(a1)+(i-1)*k 。 18、在霍夫曼编码中，若编码长度只允许小于等于4,则除掉已对两个字符编码为0和10外，还可以最多对（ 4 ）个字符编码。
19、设高度为h的空二叉树的高度为-1，只有一个结点的二叉树的高度为0，若
设二叉树只有度为2上度为0的结点，则该二叉树中所含结点至少有（ 2h+1 ）个。
20、由一棵二叉树的前序序列和（中序序列）可唯一确定这棵二叉树。 21、以折半搜索方法搜索一个线性表时，此线性表必须是（顺序）存储的（有序）表。
22、已知完全二叉树的第8层有8个结点，则其叶子结点数是（68）。若完全二叉树的第7有10个叶子结点，则整个二叉树的结点数最多是（235） 23、对于折半搜索所对应的判定树，它既是一棵（二叉搜索树），又是一棵（理想平衡树）。
24、假定对长度n=50的有序表进行折半搜索，则对应的判定树高度为（ ５ ），判定树中前５层的结点数为（３１），最后一层的结点数为（１９）。
25、在一个无向图中，所有顶点的度数之和等于所有边数的（２）倍。在一个具有n个顶点的无向完全图中，包含有（ n(n-1)/2 ）条边，在一个具有n个顶点的有向完全图中，包含有（ n(n-1) ）条边。
26、对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为（n）和（n-1）。
27、设线性表中元素的类型是实型，其首地址为1024，则线性表中第6个元素的存储位置是( 1044)。
28、在插入和选择排序中，若初始数据基本正序，则选择（插入排序），若初始数据基本反序，则最好选择（选择排序）。
29、算法是对特定问题的求解步驟的一种描述，它是（指令）的有限序列，每一条（指令）表示一个或多个操作。