《数据结构作业..doc》由会员分享，可在线阅读，更多相关《数据结构作业..doc（2页珍藏版）》请在三一文库上搜索。
1、1. 铁路进行列车调度时 , 常把站台设计成栈式结构的站台， 如 右图所示。 试问：(1) 设有编号为 1,2,3,4,5,6 的六辆列车 , 顺序开入栈式结构的站台 , 则可能的出栈序列有多少种 ?(2) 若进站的六辆列车顺序如上所述 , 那么是否能够得到 435612, 325641, 154623 和 135426 的出站序列 , 如果不能 , 说明为什么不能 ; 如果能, 说明如何得到 (即写出 "进栈"或 "出栈 "的序列 )。2. 假设将循环队列定义为： 以域变量 rear 和 length 分别指示循环队列中队尾元素的位置和内含元素的个数。
2、 试给出此循环队列的队满条件， 并写出相应的入队列和出队列的算法(在出队列的算法中要返回队头元素) 。3. 设有一个二维数组 amn ，求元素 ai j 的寻址公式。假定数组采用以行序为主序 表示方法，每个元素占 k 个存储单元，且 a00 的地址为 。4. 设数组采用以列序为主序的存储方式，做习题1。5. (a) 写出下图所示矩阵的三元组表；(b) 写出进行快速转置是数组 S 和 T中的值5000000000000800200070090000000006056假设在树中， 结点 x 是结点 y 的双亲时，用 (x,y) 来表示树中的分支。 已知一棵树的分支 集合为：(i,m),(i,n),
3、(b,e),(e,i),(b,d),(a,b),(g,i),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c) ，请用树形表示法画出此树，并回答下列问题：( 1)哪个是根结点？( 2)哪些是叶结点？(3)哪个是 g的双亲？( 4)哪些是 g的祖先？( 5)哪些是 g的孩子？( 6)哪些是 e 的子 孙？( 7)哪些是 e的兄弟？哪些是 f 的兄弟？( 8)结点 b和 n的层次各是多少？( 9)树 的深度是多少？( 10)以结点 c 为根的子树的深度是多少？( 11)树的度是多少？ 7 试采用顺序存储方法和链式存储方法分别画出题3 图所示二叉树的存储结构。8. 对二叉树中结点
4、进行按层次顺序(每一层自左至右)的访问操作称为二叉树的层次遍历， 遍历所得到的结点序列称为二叉树的层次序列。现已知一棵二叉树的层次序列为 ABCDEFGHI，J 中序序列为 DBGEHJACI，F 请画出该二叉树。9 试画出题 3 图所示二叉树的前序、中序和后序线索树。10. 已知二叉树的先序遍历序列为 ABDCEGFH，I中序遍历序列为 DBAGECHF，I试画出该二叉树， 并给出后序遍历结果。8 个字母在电文中出现的概率分别11. 假设用于通信的电子由以下字符集中的字母构成，这 为：ABCDEFG H2357111317 191 ）为这 8 个字母设计哈夫曼编码。2）若用三位二进制数（ 0 7）为这个 8个字母设计等长编码，并比较哈夫曼编码的平均码长和等长编码码长，计算压缩效率。