ERP和数据结构,项目管理复习.doc

2. 已知二叉树T的数组表示法为下图所示，请用二叉链表表示法表示此树。 0 1 2 3 4 5 6 7 8 9 10 7 6 5 8 9 3 3. 初始关键字序列如下：{49，38， 65，97，76，13，27，49，55 04}，请写出它们的希尔排序的全过程(其中d=5,3,1） 4．假设通信电文使用的字符集为{a,b,c,d,e,f}，各字符在电文中出现的频度分别为：0.34，0.05，0.12，0.23，0.08，0.18，试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子节点的权值小于右孩子节点的权值，左分支表示字符“0”，右分支表示字符“1”)，然后分别写出每个字符对应的编码。 5．设哈希（Hash）表的地址范围为0～13，哈希函数为：H（K）＝K MOD 13。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列： （23，24，32，4，31，30，46，47）造出Hash表，试回答下列问题： 画出哈希表的示意图； 若查找关键字30，需要依次与哪些关键字进行比较？ 若查找关键字14，需要依次与哪些关键字比较？ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 2. 请用序列（45，24，53，12，37，93）建立一棵二叉排序树，画出该树，并求在等概率情况下，查找成功的平均查找长度。 3.A,B,C,D,E的权值为{3, 2, 4, 5, 1}，用此权值构造哈夫曼（Huffman）树，并求此哈夫曼（Huffman）树和各个字符的哈夫曼编码（左分支为0，右分支为1） 4. 给定的关键字序列21，22，27，78，40，05，47，69，12，99，要按升序排序，请写出采用冒泡排序法前3趟的结果，和用堆排序法选择出最大和次大关键字的结果（图） 5. 选取哈希函数H(key)＝key Mod 11，用线性探测再散列开放定址法解决冲突。试在0～10的散列地址空间内对关键字序列(19、11、31、23、17、27、41、13、91、61(构造哈希表，并计算在等概率下成功查找的平均查找长度。 1.什么是顺序表？什么是链表？比较二者的优缺点。 2．将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果） 3. 假定用于通讯的电文仅有8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这8个字母设计哈夫曼编码树，并写出8个字符的哈夫曼编码 4. 已知某文件的记录关键字集为{50，10，75，40，45，85，80}，写出快速排序方法进行排序的前2趟排序结果。 5. 设有一组关键字{9,1,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的线性探测再散列方法解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。 1. 顺序队的“假溢出”是怎样产生的？什么是循环队列？如何知道循环队列是空还是满？ 2．已知树T的数组表示法为下图所示，请用二叉链表表示法表示此树。 0 1 2 3 4 5 6 7 8 9 10 A B C D E F G 3. 假定用于通讯的电文仅有8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这8个字母设计哈夫曼编码（左0，右1，左边比右边小）。 4. 已知某文件的记录关键字集为{50，10，30，40，45，85，80}，要从小到大进行排序，请分别写出直接插入排序的前2趟结果和直接选择排序的前3趟结果。 5. 设哈希（Hash）表的地址范围为0～17，哈希函数为：H （K）=K MOD 16，K为关键字，用线性探测再散列法处理冲突，输入关键字序列：{10，24，32，17，31，30，46，47，40，63，49}造出哈希表，试回答下列问题： （1） 画出哈希表示意图； （2） 若查找关键字63，需要依次与哪些关键字比较? （3） 若查找关键字60，需要依次与哪些关键字比较? （4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 1．对于序列：12，16，23，34，45，57，78，91，95，100，112进行二分法查找： （1）画出二分查找判定树 （2）求出等概率情况下，该二分查找的ASL？ （3）查找元素95需要经过几次比较？和哪些元素比较？ （4）查找元素20需要经过几次比较确定找不到？和哪些元素比较？ 2．设一棵二叉树的先序序列为：A B D F C E G H 中序遍历序列为： B F D A G E H C （1）画出这棵二叉树。 （2）将这