哈工大2004春《数据结构》考试题

1、哈工大 2004年 春季学期班号数据结构B试题学号姓名考试时间 120分钟满分 80分题号一一一-二三三四五六七实验报告成绩总分分数填空题（共10分）注 意 行 为 规 范1. 数组、栈和队列都是线性表的存储结构，可以在数组中的位置插入和删除元素；栈的主要特点是，即只能在插入和删除元素；队列的主要特点是，即只能在插入元素和删除元素。2. 设有一个元素互异的、个数为n的输入序列a1a2a3.an jan，元素经过一个栈到遵 守 考 场 纪 律达输出队列，并且元素一旦离开输入队列就不能再回到输入队列，则经过这个 栈后可以得到种不同的输出序列。3. 向一个长度为n的数组的第i个元素（1Eq+1）之前

2、插入一个元素时，需要向后移动个元素。若在长度为 n的数组中删除第i个元素（1Eq）时，需要向前移动个元素。4. 两个串相等的充分必要条件是 空串是，其长度等于，空格串管导核字 主领审签是，其长度等于。5. 已知二维数组 Amn采用行序为主方式存储，每个元素占k个存储单元，并且的一个元素的存储地址是 LOC（A00）,贝U Aij的地址6. 设单链表的结构由两个域组成，一个为 data域，另一个为指针 next域，则带有个头结点的单链表 head为空的条件是；在一个单链表中p所指向结点之后插入一个s所指结点时，应执行的两步操作依次是： 和的操作。7.用一维数组存放的一棵完全二叉树为:ABCDEF

3、GHIJKL。那么用中序遍历的方法访问该完全二叉树的顺序为简答题（共15分）1、假设二叉树的存储结构采用左右孩子链表示方法,试设计递归算法，分别求出一棵给定的二叉树BT中的所有单孩子结点个数和树的高度。（只要求写出递归模型，不用给出程序代码）有N个结点的二叉树，已知叶子结点个数为 N0,写出求度为1的结点的个数Ni的计算公式；如果此树是深度为 K的完全二叉树，写出 N为最小的公式。3、请叙述图中的两种基本遍历算法：深度优先遍历算法（DFS）和广度优先遍历算法（BFS）4、的基本思想。请请叙述Hash表的定义，在构造 Hash函数的过程中应该注意什么，常用的Hash函数有哪些。请给出处理 Has

4、h冲突的方法。第1页（共2页）试题：数据结构（2004春）B班号:姓名:三、已知某字符串S共有6种字符，不妨设为 a, b, c, d, e, f，各种字符分别出现 7次，9次,12次，22次，23次，27次，对该字符串用 0, 1进行前缀编码，请回答 下列问题：（10分）（1） 该字符串的编码至少有多少位？试求出这六种字符的Huffman编码。（2） 计算你所构造的 Huffman树的带权路径长度，并画出 Huffman树。（以上两个问题，请按左子树根结点的权小于或等于右子树根结点的权的次序构造设计编码时，左子树的编码为 0,右子树的编码位1 ）。四、有一带权无向图的顶点集合为 V1,V2,

5、V3,V4, V5,V6,V7,V8 。已知其邻接矩阵的三元组压缩存储示意图如右图所示（数组的脚标从1开始计数）：试回答下列问题： 请画出该无向图，并标明每个顶点的编号和每条边上的权，同时画出该图的邻接表存储示意图。Fs11222333444555666778 图六82O12 125 21 126 3854 S5 26 4385 107 31 23 24 102 33 4774 86 725三元组表 利用Prim算法或者Kruskal算法给出该图的所有可能的最小生成树。 根据你所设计的邻接表结构，分别写出从顶点V1出发，对该图进行深度优先遍历和广度优先遍历的顶点序列。（15分）五、假设二叉树中

6、所有非叶子结点都有左、右子树，则对此类二叉树：试问：有n个叶子结点的这类二叉树，共有多少个结点?n 试证明v 2，Li J） =1，其中n为叶子结点的个数， .表示第I个叶子结点所在的层次i -数（设根结点所在的层次数为1）o（ 10分）六、设哈希表为Hash13,表长为m=13 ,现在采用一种新的散列法双散列法来解决Hash冲突。散列（Hash）函数和再散列（ReHash）函数分别为：Ho（key）二key%13（注：是求余数运算（=Mod ）Hj =（H 匸 REV（key 1）%111）%13 i = 1 , 2,，m 1;其中函数 REV （ x）表示颠倒 10进制数x的各位，如 RE

7、V（37） = 73 , REV（9） = 9 , REV（10） = 1等。若插入的关键字依次为序列 2, 18, 31 , 20, 19, 18, 53, 27中的关键字（假设初始hash表为空），试按照上面给出的函数按照插入顺序计算给定的关键字的hash地址（若发生地址冲突，还要求给出解决冲突的相关计算过程），并画出上述关键字序列的数组方式存储示意图。（10 分）七、已知序列3, 11, 7, 13, 5, 23, 15, 17, 9: （10 分） 请给出采用快速排序法 （Quicksort）对该序列作升序排序时的第一趟和第二趟的结果（每次都是取待排序列中的第一个数据项作为枢轴（即基准

8、数据）； 如果对上述序列进行堆排序，请画出创建的初始堆结构（以二叉树方式给出，堆结构为最小堆）并给出堆排序的输出序列（最后的输出结果）。第2页（共2页）Whe n you are old and grey and full of sleep,And no ddi ng by the fire, take dow n this book,And slowly read, and dream of the soft lookYour eyes had on ce, and of their shadows deep;How many loved your mome nts of glad grac

9、e,And loved your beauty with love false or true,But one man loved the pilgrim soul in you.And loved the sorrows of your cha nging face;And bending dow n beside the glow ing bars,Murmur, a little sadly, how love fledAnd paced upon the mountains overheadAnd hid his face amid a crowd of stars.The furth

10、est dista nee in the worldIs not betwee n life and deathBut whe n I sta nd in front of youYet you don't know thatI love you.The furthest dista nee in the worldIs not whe n I sta nd in front of youYet you can't see my loveBut whe n un doubtedly knowing the love from bothYet cannot be together.The furthest dista nee in the worldIs not being apart while being in loveBut whe n I pla inly cannot resist the year ningYet prete nding you have n ever bee n in my heart.