考研试题求解（五）（散分500，答就给分！）
考研试题求解。我考非名校，这些题目都比较简单，基础，但自己做的答案总是不太放心，希望大家帮着检查一下对错，没回答的就是不会，也希望能够帮我解答。大家有时间的话多看几题，暂时没空的少答几题也可以，我都表示感谢！不管回答多少，人人给分，聊表谢意！
一.判断题.
（ 对 ）1.线性结构中的结点按前驱，后继关系可以排成一个线性序列。
（ 错 ）2.在动态单向链表中，每个结点总是占用一片连续的内存空间。
（ 对 ）3.算法的有穷性是指一个算法无论在什么情况下都应在执行有穷步后结束 。
（ 对 ）4.后缀表达式ABC+*的中缀形式为A*（B+C）。
（ 错 ）5.对顺序栈进行插入，删除操作，不涉及元素的前后移动问题。
（ 对 ）6.广义表的长度是广义表中元素的个数。
（ 对 ）7.在任何一棵完全二叉树中，叶结点的个数或者和分支结点一样多，或者只比分支结点多一个。
（ 错 ）8.直接选择排序是一种稳定的排序方法。
（ 对 ）9.n个顶点的生成树中有n-1条边。
（ 对 ）10.B-和B+树都是用来实现动态索引。
二.选择题.
（ A ）1.顺序表在各表项插入概率相等的情形下，插入一个元素平均数据移动次数AMN为：
A.n/2 B.(n-1)/2 Cn D.其他
（ A ）2.判断带表头结点的非循环单链表f为空的条件是_______
A.f= =null B.f-> link= =null C.f!=null Df-> link=f
( C ) 3.若有声明int a[4][8]；若按行优先次序存储, 则任一数组元素a[i][j]的地址为:
A.a+i*j .B.a+i*4+j C.a+i*8+j D. 其他
( D ) 4.下面程序段时间复杂度为:
for (int i=1;i <=n;i++)
for (int j=1;j <=m;j++ )
S +=i+j;
A.O(n的平方) B.O(m的平方) C.O(n+m) D.O(n*m)
( A )5.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p和q之间插入s结点，则执行：
A.s-> link=p-> link; p-> link=s; B.p-> link=s-> link;s-> link=p;
C.q-> link=s; s-> link=p; D.p-> link=s; s-> link=q;
( C )6.让元素1234依次进栈，要求出栈序列为3241，则对栈的运算为：
A. Push(1); Push(2); Push(3); Push(4); Pop( ); Pop( ) ;Pop( ) ;Pop( );
B. Push(1); Push(2); Push(3); Pop( ); Pop( ) ;Pop( ) ; Push(4);Pop( );
C. Push(1); Push(2); Push(3); Pop( ); Pop( ) ; Push(4);Pop( ) ;Pop( );
D. Push(1); Pop( ); Push(2); Pop( ); Push(3); Pop( ) Push(4); Pop( );
( C )7.在顺序循环队列中，存放队列元素的数组大小为8（0～7），若front和rear的值分别为6和3，则队列中元素个数为：
A.3 B.4 C.5 D.其他
( )8.设栈和队列的初始状态为空，元素123456依次进栈，出栈后立即进入队列，元素的出队顺序是243651，则栈的容量至少为：
A.6 B.5 C.4 D.3
( D )9.对于广义表（（a）,( ), (b,(c))）,
A.长度为4 B.深度为4
C.有2个元素 D.有3个元素
( C )10.广义表A=（1，2，（3，4），（5，（6，7））），则Head(Tail(Head(Tail(Tail(A)))))的值为：
A.（7） B.（4） C.3 D.4
（ A ）11.一棵满二叉树上有63个结点，则叶结点的个数为：
A.32 B.30 C.15 D.其他
（ B ）12.字符a,b,c,d的权值分别为2，3，4，11，则字符a的Huffman编码可能为：
A.11 B.010 C.0 D.其他
（ C ）13.若某棵二叉树的中序遍历与后序遍历相同，则该二叉树：
A.空树或所有结点只有右子树的二叉树。
B.空树或所有结点只有左子树的二叉树。
C.空树或只有根结点的二叉树。
D.不存在。
（ D ）14.设无向图的顶点个数为n，则该图最多有_________条边。
A.n(n+1) B.n(n-1) C.n(n+1)/2 D.n(n-1)/2
（ D ）15.在有向图拓扑序列中，若顶点Vx在Vy之前，则不可能为：
A．图中有一条从Vy到Vx的路径 B.图中有边 <Vx,Vy>
C. 图中有一条从Vx到Vy的路径 D.图中没有边 <Vx,Vy>
（ C ）16.依次插入序列（49，70，42，89，77，23，36，46，67，33）后建立的二叉搜索树中，查找元素36要进行________元素间的比较。
A.4次 B.5次 C.6次 D.其他
（ C ）17.若根结点在第0层，则具有4层的AVL树至少有________个结点。
A．12 B.14 C.16 D.其他
( B )18.假设排序过程中线形表的变化情况如下：
21 25 49 25* 16 08 （初始状态）
08 21 25 49 25* 16
08 16 21 25 49 25*
08 16 21 25 25* 49
08 16 21 25 25* 49
所采用的排序方法是_________
A.直接插入排序 B.冒泡排序 C.快速排序 D.直接选择排序
（ A ）19.设有100个元素，用折半搜索时，最大比较次数为：
A.6次 B.7次 C.8次 D.其他
（ B ）20.在散列查找中，平均查找长度主要与________有关。
A散列表长度 B.装填因子 C.散列元素个数 D.处理冲突方法
[解决办法]
上面看错了，8应该选D
[解决办法]
5.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p和q之间插入s结点，则执行：
A.s-> link=p-> link; p-> link=s; B.p-> link=s-> link;s-> link=p;
C.q-> link=s; s-> link=p; D.p-> link=s; s-> link=q;
应选C，q在p前面，所以插入手应该是q-> s-> p。
[解决办法]
（ C ）17.若根结点在第0层，则具有4层的AVL树至少有__A__个结点。
A．12 B.14 C.16 D.其他
递推公式：An=An-1 + An-2
[解决办法]
8. D
[解决办法]
13.A
16.A
建立后的查找树为:
49
/ \
42 70
/ \ / \
23 46 67 89
\ /
36 77
/
33
19.B 公式: [log2(n)] + 1
[解决办法]
8。选D
2是不是要选B？题目说了带表头结点
[解决办法]
我怎么这么熟悉呢
是不是考武汉理工
[解决办法]
根据Huffman编码规则,生成的Huffman树应该为:
○
/ \
○ ○
/ \ d
○ ○
c / \
○ ○
a b
看看是不是着样?
