王道-数据结构

1 设数组data[m］作为循环队列的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为____ 

 答案：D

解析：队列的头指针指向队首元素的实际位置，因此出队操作后，头指针需向上移动一个元素的位置。循环队列的容量为m，所以头指针front加1以后，需对m取余，使之自动实现循环，即当front取到最大下标（m－1处）以后，自动循环回来取0值。所以答案是D。

1 若已知一个栈的入栈序列是1，2，3，…，30，其输出序列是p1，p2，p3，…，pn，若p1=30，则p10为_______

答案：D

解析：已知数据的入栈序列是1，2，3，…，30，出栈序列的第1个元素是30，因此可以确定，所有元素是按入栈序列顺序全部入栈之后才开始出栈的。也就是说，出栈序列与入栈序列刚好相反，可求得出栈序列的第10个元素为21。

1 从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行______

答案：D

解析：首先用指针变量x保存被删除结点，然后调整栈顶指针（top=top－>next）。选项A中，x=top－>data操作目的是将栈顶结点的元素值赋给x，故无法满足题目要求。选项B中，首先进行栈顶指针top调整，则x保存的不是当前删除的结点，而是栈调整后的栈顶元素。因此答案应选择D。

1 一棵三叉树中，已知度为3的结点数等于度为2的结点数，且树中叶结点的数目为13，则度为2的结点数目为______

答案：A

解析：n0+n1+n2+n3=n，n－1=n1+2n2+3n3，n0，n1，n2，n3分别为度是0，1，2，3的结点数，n为树的结点总数。在本题中，n0=13，n2=n3。解方程得正确答案为A。

1 下面关于二叉树的结论正确的是_____

答案：A

解析：二叉树中结点个数可以为0，称为空树，所以B错。满二叉树中，任何一个结点的度，或者为0，或者为2。完全二叉树中，任何一个结点的度，或者为0，或者为1，或者为2，所以C错。二叉树的度可以是0，1，2，所以D错。

1 下列说法错误的是_____

答案：A

解析：对于连通图而言，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点；对于非连通图而言，从某个顶点出发，进行一次深度优先或广度优先搜索，只能访问连通分量内的每个顶点，若要访问图的所有顶点，还需从余下的连通分量中选择一顶点出发进行遍历。

1 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是______

答案：D

解析：给出有向图G=（V，E），对于V中顶点的线性序列（Vi1，Vi2....，Vin），如果满足如下条件：若在G中顶点Vi到Vj有一条路径，则在序列中顶点Vi必在顶点Vj之前，则该序列称为G的一个拓扑序列。根据定义可知，顶点Vi顶点Vj之前，并不能说明顶点Vi和顶点Vj之间邻接关系，但不可能存在一条从Vj到Vi的路径，因为存在从Vj到Vi的路径则说明顶点Vj必须在顶点Vi之前，这与题目产生矛盾。因此答案应选择D。

1 下列说法错误的是_____