考研试题求解（四）（散分500，答就给分！）
考研试题求解。我考非名校，这些题目都比较简单，基础，但自己做的答案总是不太放心，希望大家帮着检查一下对错，没回答的就是不会，也希望能够帮我解答。大家有时间的话多看几题，暂时没空的少答几题也可以，我都表示感谢！不管回答多少，人人给分，聊表谢意！
选择题。
（ D ）1.在决定选取何种存储结构时，一般不考虑____________。
A.各结点的值如何 B.结点数目的多少
C.对数据有哪些运算 D.所用编程语言实现这种结构是否方便
（ C ）2.对长度为n的无序线性表进行顺序查找，则查找成功，不成功时平均数据比较次数ACN分别为_____________
A.n/2, n B.(n+1)/2, n-1 C.(n+1)/2, n D.(n-1)/2, n-1
( A ) 3.数组A[1..5，1..6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5][5]的地址为_____________
A.1120 .B.1125 C.1140 D. 其他
( B ) 4.下面程序段时间复杂度为:
for (int i=1; i <=m; i++)
for (int j=1; j <=m; j++ )
S+=i
A.O(n的平方) B.O(m的平方) C.O(n+m) D.O(n*m)
( B )5.现有一带表头结点的单链表，若要在结点 p的后面插入结点q，则需要执行------------
A.q-> link=p ;p-> link=q; B.p-> link=q ;q-> link=p-> link;
C.q-> link=p-> link;p-> link=q; D.p-> link=q-> link;q-> link=p;
( A )6.设有两个长度为n的单向链表，结点类型相同。若以H1为表头指针的链表是非循环的，以H2为表头指针的链表是循环的，则________。
A. 对于两个链表来说，删除第一个结点的操作，其时间复杂度都是O（1）。
B. 对于两个链表来说，删除最后一个结点的操作，其时间复杂度都是O（n）。
C.循环链表要比非循环链表占用更多的存储空间。
D. H1和H2是不同类型的变量。
( B )7.设n个元素的进栈序列是1，2，3，…，n，出栈是p1,p2,…,Pn,若p1=3,则p2的值___________.
A.可能是2 B.一定是2 C.可能是1 D.一定是1
( )8.设栈和队列的初始状态为空，元素123456依次进栈，出栈后立即进入队列，元素的出队顺序是254631，则栈的容量至少为：
A.3 B.4 C.5 D.6
( D )9.空的广义表，是指广义表____________。
A.尚未赋值 B.深度为0
C.不含任何原子 D.不含任何元素
( D )10.广义表A=（a，b，（c，d），（e，（f，g））），则Head(Tail(Head(Tail(Tail(A)))))的值为：
A.（g） B.（d） C.c D.d
（ B ）11.如果二叉树结点的前序序列和中序序列分别是abcdefgh和bcafegdh,则后序序列为________.
A.一定是cbfgehda B.可能是cbghfhda C.不存在 D.其他
（ C ）12.用整数1，2，3，4，5作为五个树叶的权值，可构造一棵带权路径长度值为_______的Huffman树。：
A.15 B.33 C.34 D.其他
（ C ）13.在高度为h的完全二叉树中，_______.
A度为0的结点都在第h层上 。
B.第i（0≤i〈h-1）层上的结点都是度为2的结点。
C. 第i（0≤i〈h-1）层上有2的（i-1）次方的结点。
D.不存在度为1的结点。
（ B ）15.无权值有向图用邻接矩阵表示后，顶点i的入度等于____________中1的个数。
A．第i行 B.主对角线 C. 第i列 D.辅对角线
（ B ）16.在下面几组关键字中，哪个是最小堆
A.{05，13，55，94，17，46，42} B. {05，42，13，55，94，17, 46}
C. {05，42，17，94，55，13，46} D. {94，42，55，01，17, 13,46}
（ C ）17.在一个空AVL树内，依次插入关键字：49，94，91，47，92，45，89，42，87，当删除关键码时，如果该关键码同时具有左右子女，则以其中序后继替代，则删除关键码91时的旋转类型是__________
A．左单旋 B. 左右单旋 C. 右单旋 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.直接选择排序
（ D ）19.有18个元素的有序表作二分查找，则查找 A.[3]所比较序列的下标为_____________
A.1，2，3 B.9，5，3 C.9，5，2，3 D.9，4，2，3
（ D ）20.在一棵m阶B-树中，若在某叶子结点插入中一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是___________。
A.m-1 B.m C.︱ m/2 ︳ D. ︱m/2 ︳-1
[解决办法]
7.设n个元素的进栈序列是1，2，3，…，n，出栈是p1,p2,…,Pn,若p1=3,则p2的值___________.
A.可能是2 B.一定是2 C.可能是1 D.一定是1
应该选A，p2可能是除了1和3的任意一个数。
[解决办法]
5.现有一带表头结点的单链表，若要在结点 p的后面插入结点q，则需要执行------------
A.q-> link=p ;p-> link=q; B.p-> link=q ;q-> link=p-> link;
C.q-> link=p-> link;p-> link=q; D.p-> link=q-> link;q-> link=p;
应选C
[解决办法]
我觉得有问题的:3, 4, 15,18 ,
8.A
[解决办法]
我仅对eidewood() 的答案给出补充，
请楼主参考。
3.选C
数组A是5行6列，数组下标从[1][1]开始，首元素A[1][1]对应地址为1000；
而A[5][5]相对A[1][1]的偏移是4*6+5-1=28,所以地址为1000+28*5=1140H。
楼主的错误在于，当成5列了。
4.选D，题干中肯定笔误，i循环上限应该为n，否则选项的n无意义。
15.选C
18.选C 每次快排，以序列最后一个元素为枢纽；冒泡一定不对，每次排序，都是从后往前，所有靠后的小于前面一个元素，都要交换操作。记住：冒泡不止是针对1个元素。
呵呵，准备接分了。
[解决办法]
补充一下
8.选B
[解决办法]
12 B
[解决办法]
11题
如果已知中序，并且知道前序或后序的任一个，则肯定能确定另外一个。
我画了一下，选A，树是这样的：
a -- d -- h
| |
b-c e -- g
|
f
