哈工大2005春《数据结构》考试题-b.doc

班号 学号 姓名 哈工大 2005 年 春 季学期 《数据结构－B》试 题 考试时间 120 分钟 满分 100 分 题号 一 二 三 总分 分数 填空题（共30分，每空1分） 数组、栈和队列都是常见的线性表类型，数组的特点是可以在 位置插入和删除元素；栈的主要特点是 ，即只能在 插入和删除元素；队列的主要特点是 ，即只能在 插入元素和 删除元素。 向一个长度为n的单向链表的第i个元素（1≤i≤n+1）之前插入一个元素时，需要向后移动 个元素。若在长度为n的数组中删除第i个元素（1≤i≤n）时，需要向前移动 个元素。 顺序表中逻辑上相邻的元素的物理位置 相邻。单链表中逻辑上相邻的元素的物理位置 相邻。在带头结点的单向链表中，除了头结点外，其他任一结点的存储位置由 　　　　　　　　　　　　　　　　　　　 指示。 两个串相等的充分必要条件是 　　　　　　　　　　 。空串是 　　　　　　　　 ，空格串是 　　　　　　　　　 ，其长度等于 　　　　　　　　　 。 设一棵完全二叉树具有1000个结点，则此完全二叉树有 　　 个叶子结点，有 　 个度为2的结点，有 个结点只有非空左子树，有 　 个结点只有非空右子树。设一棵深度为6的满二叉树有 　　 个内部结点和 　 个叶子。 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 　　　 ；末尾元素A57的第一个字节地址为 　　　　 ；若按行存储时，元素A14的第一个字节地址为 　　 ；若按列存储时，元素A47的第一个字节地址为 　　 。 设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为 　　。 给出下列广义表操作的结果：（1） GetHead【((a,b),(c,d))】=== 　　 ; （2） GetHead【GetTail【((a,b),(c,d))】】=== 　　 ; （3） GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== 　　 ; （4） GetTail【GetHead【GetTail【((a,b),(c,d))】】】===　　　　; 判断题，如果错误，请在括号中标记“×”，否则标记“√”（共10分，每题一分） （ 　 ）1. 链表的每个结点中都恰好包含一个指针。链表的物理存储结构具有同链表一样的顺序。 （ 　 ）2. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 （ 　 ）3. 顺序存储方式只能用于存储线性结构。线性表的逻辑顺序与存储顺序是一致的。 （ 　 ）4. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n+1个非空指针域。 （ 　 ）5. 二叉树中每个结点有两棵非空子树或有两棵空子树。二叉树中所有结点个数是2k-1-1，其中k是树的深度。 （ 　 ）6. 二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （ 　 ）7. 对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。具有12个结点的完全二叉树有5个度为2的结点。 （ 　 ）8. 用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个为空指针。 （ 　 ）9. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈顶分别设在这片内存空间的两端。 （ 　 ）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 综合题（共60分） 设某一通信系统由0～9十种字符组成，其出现的概率为: (={0.15, 0.11, 0.08, 0.03, 0.12, 0.06, 0.19, 0.04, 0.13, 0.09}, 现用Huffman方法进行编码，请画出对应的Huffman树，并计算平均码长WPL（带权路径长度），给出每个字符的编码。（请按左子树根结点的权小于或等于右子树根结点的权的次序构造设计编码，左子树的编码为0，右子树的编码位1）。（10分） 已知一棵二叉树的前序遍历序列和后序遍历序列，可以唯一地确定这棵二叉树吗？请给出严格证明，