学海网

北京邮电大学数据结构考研测验试题及答案（共5份）
一. 填空题
1. 设只包含要根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为 ，最小结点数为 。
2. 某二叉树结点的中序遍历序列为A，B，C，D，E，F，G，后序遍历序列为B，D，C，A，F，G，E，则该二叉树结点的前序遍历序列为 ，该二叉树对应的树林包括 棵树。
3. 设有关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是 ；若采用以第一个元素为分界元素的快速排序法，则一趟扫描的结果是 。
4.在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个________,且存在一条从根到该结点的_______。
5. 对于顺序存储的栈，因为栈的空间是有限的，在进行_______运算时，可能发生栈的上溢，在进行________运算时，可能发生栈的下溢。
......
一、单项选择题
1、栈结构通常采用的两种存储结构是 。
A、线性存储结构和链表存储结构；B、散列方式和索引方式；
C、链表存储结构和数组； D、线性存储结构和非线性存储结构。
2、判定一个栈ST（最多元素为m0）为栈满的条件是 。
A、ST→top!=0； B、ST→top==0；
C、ST→top!=m0-1； D、ST→top==m0-1
3、判定一个队列Qu（最多元素为m0）为空的条件是 。
A、Qu→rear-Qu→front==m0； B、Qu→rear-Qu→front-1==m0；
C、Qu→front==Qu→rear； D、Qu→front==Qu→rear+1。
......