考研数据结构及程序设计在线题库每日一练（一十一）

本文提供考研数据结构及程序设计在线题库每日一练，以下为具体内容

1、在一个双链表中，在p结点之后插入结点q的操作是（ ）。

A、q→prior=p;p→next=q;p→next→prior=q;q→next=p→next;

B、q→next=p→next;p→next→prior=q;p→next=q;q→prior=p;

C、p→next=q;q→prior=p;q→next=p→next;p→next→prior=q;

D、q→prior=p:p→next=q;q→next=p→next;p→next→prior=q;

2、如下图1，从顶点1出发，按照广度优先规则遍历，可能得到的序列为（ ）。

A、1352467

B、142375

C、1234576

D、1354672

3、中缀表达式A*（B+C）/（D-E+F）的后缀表达式是（ ）。

A、A*B+C/D-E+F

B、AB*C+D/E-F+

C、ABC+*DE-+/

D、ABCDEF*+/-+

4、一棵m阶非空B-树，除根结点外，所有非终端结点最少有（ ）棵子树。

A、⌈m/2⌉

B、m-1

C、m

D、m+1

5、设A是n×n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1…n(n+1)/2]中，对上述任一元素aij（1≤i，j≤n，且i≤j）在B中的位置为（ ）。

A、i(i-1)/2+j

B、j(j-1)/2+i

C、j(j-1)/2+i-1

D、i(i-1)/2+j-1

1、试题答案：B

试题解析：

【考点】本题考查双链表的删除。
【解析】在一个双链表中，在p结点之后插入结点q的操作示意图如下所示，其中① q->next=p->next; ② p->next->prior=q; ③ p->next=q; ④ q->prior=p;。故本题选B。

2、试题答案：C

试题解析：

【考点】本题考查图的广度优先遍历。
【解析】从1出发访问与1相邻的所有顶点，即2453（顺序可以有所不同）。因此，B和D可以排除，不满足遍历要求。A：若访问完13524，此时与顶点3和顶点5相邻的顶点均已访问完，与顶点2相邻的顶点还剩顶点7未访问，所以接下来访问顶点7，而不是顶点6。因此，A排除。C：若访问完12345，此时与顶点2相邻的顶点还剩顶点7未访问，所以接着访问顶点7。与顶点3相邻的顶点均已访问，继续看检查顶点4，与其相邻的顶点还剩顶点6未访问，所以接着访问顶点6。最终整个图按照广度优先遍历得到的序列为1234576。故本题选C。

3、试题答案：C

试题解析：

【考点】本题考查中缀表达式转后缀表达式。
【解析】
（1）首先从左至右标出中缀表达式中各个元素符号运算的先后顺序，如下所示：

（2）依次按照运算符的先后顺序将运算符移动到两个操作数的后面，即可得到中缀表达式A*（B+C）/（D-E+F）对应的后缀表达式为BC+*DE-+/。故本题选C。

4、试题答案：A

试题解析：

【考点】本题考查B-树的特点。
【解析】B-树是一种平衡的多路查找树，它在文件系统中很有用。
m阶B-树的特性：
（1）树中每个结点至多有m颗子树；
（2）若根结点不是叶子结点，则至少有两颗子树；
（3）除根结点之外的所有非终端结点至少有⌈m/2⌉颗子树；
（4）所有的非终端结点中包含下列信息数据（n，A0，K1，A1，K2，A2，…，Kn，An）。
根据m阶B-树的特性可知，除根结点外，所有非终端结点最少有⌈m/2⌉棵子树。故本题选A。

5、试题答案：B

试题解析：

【考点】本题考查对称矩阵的压缩存储。
【解析】因为i从1开始，所以非零元素aij是第i行第j个元素。下三角矩阵A（n×n）按列优先顺序压缩时，aij是第（1+2+…+j-1）+i=j（j-1）/2+i个元素。又因为数组B的下标是从1开始的，所以aij存储在对应的数组下标为j(j-1)/2+i的位置。故本题选B。