数据结构题海遨游的第14天

1：两个顺序栈共享数组S【0…n-1】，其中第一个栈的栈顶指针top1的初始值为-1，第二个栈的栈顶指针top2的初始值为n，则判断该共享栈满的条件是（B） A：top2+2=top1 B：top1+1=top2 C：top1+2=top2 D：top2+1=top1 解析： 2：如果约定树中结点的度数不超过2,则它实际上就是一棵二叉树(B) A：正确 B：错误 解析：二叉树中的左右子树 有区分，次序不能颠倒。 3：一棵哈夫曼树共有215个结点,对其进行哈夫曼编码,共能得到(B)个不同的码字 A：107 B：108 C：214 D：215 解析：叶子结点对应的即是不同的编码，所以叶子结点=其他结点+1，即108（叶子结点）+ 107（其他结点）=215 4：栈和队列的共同特点是（A） A：只允许在端点处插入和删除元素 B：都是先进后出 C：都是先进先出 D：没有共同点 解析：队列只能在一端进行插入，另一端进行删除，栈的操作都在栈顶 5：如果两个串含有相同的字符，则说它们相等。（B） A：正确 B：错误 解析：A串：abcd；B串：cabd，两个串有相同的字符但是并不相等。 6：必须把一般树转换成二叉树后才能进行存储(B) A：正确 B：错误 解析：树的表示法：广义表表示法，父指针表示法，子女链表表示法，子女兄弟链表表示法；不一定要转换成二叉树进行存储。 7：若一棵二叉树汇总，度为2的结点为9，则该二叉树的叶子结点数为（A） A：10 B：11 C：12 D：不确定 解析：二叉树中度为0的结点是度为2的结点数+1,，则叶子结点数10. 8：有一个用数组C[1…m]表示的环形队列，m为数组的长度。假设f为队头元素在数组中的位置，r为队尾元素的后一位置（按顺时针方向）。若队列非空，则计算队列中元素个数的公式应为（A） A：（m+r-f）mod m B：r-f C：(m-r+f) mod m D：(m-r-f) mod m E：(r-f) mod m F：需要判断边界 解析： 9：设S为一个长度为n的字符串,其中的字符各不相同,则S中的互异的非平凡子串(非空且不同于S本身)的个数为(D) A：2n-1 B：n² C：(n²/2)+(n/2) D：(n²/2)+(n/2)-1 E：(n²/2)-(n/2)-1 F：其他情况 解析： 10：对于有n个结点的二叉树,其高度为 （A） A：不确定 B：log2n C：log2n+1 D：n 解析：完全二叉树可以根据结点计算出高度（具有n个结点的完全二叉树的深度为log2n(向下取整)+1），但是任意二叉树不能确定