考研试题求解（二）（散分500，答就给分！）
考研试题求解。我考非名校，这些题目都比较简单，基础，但自己做的答案总是不太放心，希望大家帮着检查一下对错，没回答的就是不会，也希望能够帮我解答。大家有时间的话多看几题，暂时没空的少答几题也可以，我都表示感谢！不管回答多少人人给分，聊表谢意！


（ D ）1.下列时间复杂度中最好的是____________。
A.O（2的n次方） B.O（n）
C.O（n的3次方） D.O（n*2（n））

（ 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

( C ) 3.设C语言二维数组A[m][n],假设A[0][0]的存放位置在644，A[2][2]的存放位置在676，每个元素占一个空间，问A[3][3]的存放位置为_____________
A.698 .B.695 C.692 D. 其他

( A ) 4.设n为正整数，下列程序段中加下划线语句的执行次数为________
for (int i=1; i <=n; i++)
for (int j=i-1; j <=i+1; j++ )
c[i][j]=0;
A.n B.3n C.n的平方 D.其他

( B )5.两指针p和q分别指向单链表的两个结点，p所指结点是q所指结点的前驱的条件是________
A.q-> link==p ; B.p-> link=q ;
C.p==q; D.p-> link==q-> link;

( B )6.把一个指针s所指的新结点，作为非空双链表中q所指结点（中间结点）的直接后继插入，则正确的是________。
A.q-> rlink=s;s-> llink=q; q-> rlink-> llink=s;s-> rlink=q-> rlink;
B. s-> llink=q; q-> rlink=s; q-> rlink-> llink=s; s-> rlink=q-> rlink;
C. s-> llink=q; s-> rlink=q-> rlink; q-> rlink-> llink=s; q-> rlink=s;
D.以上都不对

( C )7.经过下列栈运算后，IsEmpty( )的值是___________.
Stack s(10); Push(s,a); Push(s,b); Pop(s); Pop(s)
A.1 B.0 C.a D.b

( )8.设栈和队列的初始状态为空，元素123456依次进栈，出栈后立即进入队列，元素的出队顺序是254631，则栈的容量至少为：
A.3 B.4 C.5 D.6

( D )9.对于广义表（（a,b）,(( )),(a,(b))）,其_______
A.长度为4 B.深度为4
C.有2个元素 D3个元素

( )10.已知广义表A=（（a,b,c）,(d,e,f)）,则Head(Tail(Head(Tail(A))))的值为_________
A.（d ） B.（e） C.c D.e

（ A ）11.如果二叉树结点的前序序列和中序序列分别是abdgcefh和dgbaechf ,则后序序列为________.
A.gdbehfca B.gdbecfha C.bdgcefha D.其他

（ A）12.如果结点A有4个兄弟，并且B是A的双亲，则B的度为______.
A.5 B.4 C.1 D.其他

（ A ）13.在一棵非空二叉树的中序遍历中，根结点的右边_______.
A.只有右子树上的所有结点
B.只有右子树上的部分结点
C.只有左子树上的所有结点
D.只有左子树上的部分结点
（ C ）14.已知图的邻接矩阵如图，从顶点V0开始进行深度优先遍历，可得到的顶点访问序列是__________
A.0 2 4 3 1 5 6 B.0 1 3 6 5 4 2 C. 0 1 3 4 2 5 6 D. 0 3 6 1 5 4 2

0 1 1 1 1 0 1
1 0 0 1 0 0 1
1 0 0 0 1 0 0
1 1 0 0 1 1 0

1 0 1 1 0 1 0
0 0 0 1 1 0 1
1 1 0 0 0 1 0

（ C ）15.对n个顶点的带权连通图，它的最小生成树是指图中任意一个____________。
A.由n-1条权值最小的边构成的子图
B.由n-1条权值之和最小的边构成的子图
C.由n-1条权值之和最小的边构成的连通子图
D.由n个顶点构成的边的权值之和最小的连通子图

（ 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.其他情况

( D )18.假设排序过程中线性表的变化情况如下：
21 25 49 25* 16 08 （初始状态）
08 25 49 25* 16 21
08 16 49 25* 25 21
08 16 21 25* 25 49
08 16 21 25* 25 49
08 16 21 25* 25 49
所采用的排序方法是__________
A.直接插入排序 B.冒泡排序 C.快速排序 D.直接选择排序

（ A）19.关键路径是结点网络中_____________
A.从源点到汇点的最长路径 B.从源点到汇点的最短路径
C.最长的回路 D. 最短的回路

（ B）20.在一棵m阶B-树中，若在某叶子结点插入中一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是___________。

A.m-1 B.m C. m/2 D. m/2 -1




[解决办法]
( A ) 4.设n为正整数，下列程序段中加下划线语句的执行次数为________
for (int i=1; i <=n; i++)
for (int j=i-1; j <=i+1; j++ )
c[i][j]=0;
A.n B.3n C.n的平方 D.其他

如果划线的是c[i][j]=0；这道题应该是B，执行了j=i-1;j=i;j=i+1；

[解决办法]
( B )6.把一个指针s所指的新结点，作为非空双链表中q所指结点（中间结点）的直接后继插入，则正确的是________。
A.q-> rlink=s;s-> llink=q; q-> rlink-> llink=s;s-> rlink=q-> rlink;
B. s-> llink=q; q-> rlink=s; q-> rlink-> llink=s; s-> rlink=q-> rlink;
C. s-> llink=q; s-> rlink=q-> rlink; q-> rlink-> llink=s; q-> rlink=s;
D.以上都不对

这道题答案应该是C。
[解决办法]
( )8.设栈和队列的初始状态为空，元素123456依次进栈，出栈后立即进入队列，元素的出队顺序是254631，则栈的容量至少为：
A.3 B.4 C.5 D.6

这道题应该是B
最大的时候，栈里面的数据是1,3,4,5
[解决办法]
8.C
[解决办法]
( D )18.假设排序过程中线性表的变化情况如下：
21 25 49 25* 16 08 （初始状态）
08 25 49 25* 16 21
08 16 49 25* 25 21
08 16 21 25* 25 49
08 16 21 25* 25 49
08 16 21 25* 25 49
所采用的排序方法是____C(只有快排不稳定)___
A.直接插入排序 B.冒泡排序 C.快速排序 D.直接选择排序

[解决办法]
8. B
[解决办法]
( )8.设栈和队列的初始状态为空，元素123456依次进栈，出栈后立即进入队列，元素的出队顺序是254631，则栈的容量至少为：
A.3 B.4 C.5 D.6

队列的第一个元素是2，说明此时栈的进出情况是：1进栈，2进栈，2出栈（进队列），所以此时栈的容量至少是2。
队列的第二个元素是5，说明此时栈的进出情况是：1在栈，3进栈，4进栈，5进栈，5出栈（进队列），所以此时栈的容量至少是4。
队列的第三个元素是4，说明此时栈的进出情况是：1在栈，3在栈，4出栈（进队列），所以此时栈的容量仍然是4。
其他依次类推。答案是4。

之所以写这么多废话，是因为以前有过类似经历，高手给出了答案，可自己就是不知道为什么是这个答案，郁闷。希望高手在回答的时候给出原因或解题思路。
[解决办法]
lz 看开点吧 还是自己研究吧 要不问问同学
在这里你要是能找到答案 我今年不考研了
ps：我也考计算机研
[解决办法]
( A ) 4.设n为正整数，下列程序段中加下划线语句的执行次数为________
for (int i=1; i <=n; i++)
for (int j=i-1; j <=i+1; j++ )
c[i][j]=0;
A.n B.3n C.n的平方 D.其他
这题如果划线的是C[i][j]那这个答案就应该选B。
[解决办法]
( )10.已知广义表A=（（a,b,c）,(d,e,f)）,则Head(Tail(Head(Tail(A))))的值为_________

A.（d ） B.（e） C.c D.e

A1= tail(A) = ((d,e,f))
A2= head(A1)= (d,e,f)
A3= tail(A2)= (e,f)
A3= head(A3)=e

选B

( )8.设栈和队列的初始状态为空，元素123456依次进栈，出栈后立即进入队列，元素的出队顺序是254631，则栈的容量至少为：
A.3 B.4 C.5 D.6
你只要将栈具体时间包含的数据列出不就......
栈中有 出栈
12 2
13
134
1345 5
134 4
136 6
13 3
1 1
答案B