资源描述
数据结构 应用题 天涯古巷 出品 第三章 题型一：表达式求值 按照四则运算加 （ +） 、减 （ -） 、乘 （ *） 、除 （ /） 和幂运算 ()优先关系的惯例 ，画出对下列算术 表达式求值时操作数栈和运算符栈的变化过程： A-B C/D+EF 解： BC=G G/D=H A-H=I EF=J I+J=K 步骤 OPTR栈 OPND栈 输入字符 主要操作 1 # A-B*C/D+EF# PUSH(OPND,A) 2 # A -B*C/D+EF# PUSH(OPTR,-) 3 #- A B*C/D+EF# PUSH(OPND,B) 4 #- A B *C/D+EF# PUSH(OPTR,*) 5 #-* A B C/D+EF# PUSH(OPND,C) 6 #-* A B C /D+EF# Operate(B,*,C) 7 #- A G /D+EF# PUSH(OPTR,/) 8 #-/ A G D+EF# PUSH(OPND,D) 9 #-/ A G D +EF# Operate(G,/,D) 10 #- A H +EF# Operate(A,-,H) 11 # I +EF# PUSH(OPTR,+) 12 #+ I EF# PUSH(OPND,E) 13 #+ I E F# PUSH(OPTR,) 14 #+ I E F# PUSH(OPND,F) 15 #+ I E F # Operate(E,F) 16 #+ I J # Operate(I,+,J) 17 # K # RETURN 题型二：汉诺塔时间复杂度的分析及证明 汉诺塔问题的递归算法的时间复杂度是什么？请给出答案并且给予证明。 解： 时间复杂度 T(n)=O(2 n )，证明如下 已知： f(1)=1， f(n)=2f(n-1)+1 所以 ： f(n)+1=2(f(n-1)+1) f(n)= 2 n -1 （ 2 n -1为至少执行移动操作的次数） T(n)=O(2 n ) 故： 得证 第四 章 题型一：数组地址的计算 设有二维数组 A(68)，每个元素占 6字节存储，顺序存放， A的起地址为 1000，计算： （ 1）数组 A的体积（即存储量）； （ 2）数组的最后一个元素 A57的起始地址； （ 3）按行优先存放时，元素 A14的起始地址； （ 4）按列优先存放时，元素 A47的起始地址。 第五 章 题型一：由二叉树的中序遍历和前（后）序遍历，画出该二叉树 1、 给定二叉树的两种遍历序列，分别是： 前序遍历序列： A B D F C E G H； 中序遍历序列： B F D A G E H C 试画出二叉树 B，并简述由任意二叉树 B的前序遍历序列和中序遍历序列求二叉树 B的思想方法。 答案： 2、 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的 结点序列。 A ED CB HGF 题型二：哈夫曼树的构造（画树、计算 WPL、初态和终态表），设计哈夫曼编码 1、 假设用于通信的电文仅由 8个字母组成，字母在电文中出现的频率分别为 ： 0.07， 0.19， 0.02， 0.06， 0.32， 0.03， 0.21， 0.10。 试为这 8个字母设计赫夫曼编码。 试设计另一种由二进制表示的等长编码方案。 对于上述实例，比较两种方案的优缺点。 答案：方案 1；哈夫曼编码 先将概率放大 100倍，以方便构造哈夫曼树。 w=7,19,2,6,32,3,21,10，按哈夫曼规则：【 （ 2,3）， 6, (7,10)】 , 19, 21, 32 （ 100） （ 40） （ 60） 19 21 32 （ 28） （ 17） （ 11） 7 10 6 （ 5） 2 3 方案比较： 方案 1 WPL=2*(0.19+0.32+0.21)+4*(0.07+0.06+0.10)+5*(0.02+0.03)=1.44+0.92+0.25=2.61 方案 2 WPL 3*(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 结论：哈夫曼编码优于等长二进制编码 字母编号 对应编码 出现频率 1 000 0.07 2 001 0.19 3 010 0.02 4 011 0.06 5 100 0.32 6 101 0.03 7 110 0.21 8 111 0.10 字母编号 对应编码 出现频率 1 1100 0.07 2 00 0.19 3 11110 0.02 4 1110 0.06 5 10 0.32 6 11111 0.03 7 01 0.21 8 1101 0.10 2、 已知下列字符 A、 B、 C、 D、 E、 F、 G的权值分别为 3、 12、 7、 4、 2、 8， 11，试填写出其对应 哈夫曼树 HT的存储结构的初态和终态。 答案： 初态 : 终态 : weight parent lchild rchild 1 3 8 0 0 2 12 12 0 0 3 7 10 0 0 4 4 9 0 0 5 2 8 0 0 6 8 10 0 0 7 11 11 0 0 8 5 9 5 1 9 9 11 4 8 10 15 12 3 6 11 20 13 9 7 12 27 13 2 10 13 47 0 11 12 weight parent lchild rchild 1 3 0 0 0 2 12 0 0 0 3 7 0 0 0 4 4 0 0 0 5 2 0 0 0 6 8 0 0 0 7 11 0 0 0 8 0 0 0 9 0 0 0 10 0 0 0 11 0 0 0 12 0 0 0 13 0 0 0 题型三：利用二叉树的性质对某些问题进行证明 对于那些所有非叶子结点均含有左右子数的二叉树： (1) 试问：有 n个叶子结点的树中共有多少个结点？ (2) 试证明： ( ) 12 1 1 = = n i l i ，其中 n为叶子结点的个数， i l表示第 i个叶子结点所在的层次 （设根节点所在层次为 1）。 解： （ 1）总结点数为 1 21 n+ ，其中 1 为非叶子结点数，则叶子结点数为 1 1 += nn ，所以总 结点数为 2n 。 （ 2）用归纳法证明。 i=1，说明二叉树只有一个叶子结点，则整棵树只有一个根结点， 1 1 =l , 12 )1( 1 = l ，结论成立。 设有 n个叶子结点时也成立，即 12.2.22 )1( )1( )1()1( 21 =+ + n p l l ll ，现假设 增加一个叶子结点，这意味着在某叶子结点 p上新生两个叶子结点，而结点 p则成为非叶子结点， 可见，总结点数增 2，叶子结点数增 1。此时，所有叶子结点是原结点除去 p，然后加上两个深度 为 1+ p l 的新叶子结点，由此， )11()11( )1( )1()1( )1()1( 222.22.22 11 21 + + + + pp n pp ll l ll ll 12.2.22 )1( )1( )1()1( 21 =+= + n p l l ll 则当 i=n+1时，也成立，由此即得到证明。 第六 章 题型一：给定图的逻辑结 构，画出邻接矩阵和邻接表（或反过来考） 1、 已知图所示的有向图，请给出： 每个顶点的入度和出度； 邻接矩阵； 邻接表； 逆邻接表。 答案： 2、 已知如图 6.33所示的无向网，请给出： 邻接矩阵； 邻接表； 最小生成树 答案： 645 625 236 379 456755 5553 9554 34 a b 4 c 3 b a 4 c 5 d 5 e 9 c a 3 b 5 d 5 h 5 d b 5 c 5 e 7 f 6 g 5 h 4 e b 9 d 7 f 3 f d 6 e 3 g 2 g d 5 f 2 h 6 题型二：根据图的逻辑结构或存储结构，写出深度、广度优先搜索遍历结果 （根据逻辑结构写是唯一的，根据存储结构写不唯一） 已知图的邻接矩阵如图所示。试分别画出自顶点 1出发进行遍历所得的深度优先生成树和广度优先 生成树。 答案： 题型三：根据图的逻辑结构填写最短路径求解过程表，画出最小生成树（计算权值和），写出拓扑 排序结果 有向网如图所示，试用迪杰斯特拉算法求出从顶点 a到其他各顶点间的最短路径，完成 下 表 答案： D 终点 i=1 i=2 i=3 i=4 i=5 i=6 b 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) c 2 (a,c) d 12 (a,d) 12 (a,d) 11 (a,c,f,d) 11 (a,c,f,d) e 10 (a,c,e) 10 (a,c,e) f 6 (a,c,f) g 16 (a,c,f,g) 16 (a,c,f,g) 14 (a,c,f,d,g) S 终点集 a,c a,c,f a,c,f,e a,c,f,e,d a,c,f,e,d,g a,c,f,e,d,g,b 第七 章 题型一：折半查找过程，画判定树，计算 ASL 假定对有序表：（ 3， 4， 5， 7， 24， 30， 42， 54， 63， 72， 87， 95）进行折半查找，试回答下列 问题： 画出描述折半查找过程的判定树； 若查找元素 54，需依次与哪些元素比较？ 若查找元素 90，需依次与哪些元素比较？ 假定每个元素的查找概率相等，求查找成功时的平均查找长度。 答案： 先画出判定树如下（注： mid=(1+12)/2=6）： 30 5 63 3 7 42 87 4 24 54 72 95 查找元素 54，需依次与 30, 63, 42, 54 元素比较； 查找元素 90，需依次与 30, 63,87, 95元素比较； 求 ASL之前，需要统计每个元素的查找次数。判定树的前 3层共查找 1 2 2 4 3=17 次； 但最后一层未满，不能用 8 4，只能用 5 4=20次， 所以 ASL 1/12（ 17 20） 37/12 3.08 题型二：二叉排序树的创建，查找，计算 ASL 已知如下所示长度为 12的表：（ Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec） 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序 树，并求其在等概率的情况下查找成功的平均查找长度。 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查 找成功的平均查找长度。 答案： 题型三：已知哈希表长度和哈希函数，利用线性探测法和链地址法解决冲突，构造哈希表，计算 ASL 1、（ 线 性 探 测 ） 设哈希表的地址范围为 0 17，哈希函数为： H（ key） =key%16。用线性探测法处 理冲突，输入关键字序列：（ 10， 24， 32， 17， 31， 30， 46， 47， 40， 63， 49）， 构 造 哈 希 表 ， 试 回答下列问题： 画出哈希表的示意图； 若查找关键字 63，需要依次与哪些关键字进行比较？ 若查找关键字 60，需要 依次与哪些关键字比较 ？ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 答案： 画表如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 32 17 63 49 24 40 10 30 31 46 47 查找 63,首先要与 H(63)=63%16=15号单元内容比较，即 63与 31比较 ,不匹配 ; 然后顺移，与 46,47,32,17,63相比，一共比较了 6次！ 查找 60,首先要与 H(60)=60%16=12号单元内容比较，但因为 12号单元为空（应当有空标 记），所以应当只比较这一次即可。 对于黑色数据元素，各比较 1次；共 6次； 对红色元素则各不相同，要统计移位的位数。“ 63”需要 6次，“ 49”需要 3次，“ 40”需要 2 次，“ 46”需要 3次，“ 47”需要 3次， 所以 ASL=1/11（ 6 2 3 3+6） 23/11 2、 （链地址法） 设哈希函数 H（ K） =3 K mod 11，哈希地址空间为 0 10，对关键字序列（ 32， 13， 49， 24， 38， 21， 4， 12）， 按 下 述 两 种 解 决 冲 突 的 方 法 构 造 哈 希 表 ， 并 分 别 求 出 等 概 率 下 查 找成功时和查找失败时的平均查找长度 ASLsucc和 ASLunsucc。 线性探测法； 链地址法。 答案： 散列地址 0 1 2 3 4 5 6 7 8 9 10 关键字 4 12 49 38 13 24 32 21 比较次数 1 1 1 2 1 2 1 2 ASLsucc =（ 1+1+1+2+1+2+1+2） /8=11/8 ASLunsucc=（ 1+2+1+8+7+6+5+4+3+2+1） /11=40/11 ASLsucc =（ 1*5+2*3） /8=11/8 ASLunsucc=（ 1+2+1+2+3+1+3+1+3+1+1） /11=19/11 第八 章 题型一：已知整数序列，写出直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简 单选择排序、归并排序的排序过程（考两到三种），并会分析时空复杂度、稳定性及适用情况 1、 设待排序的关键字序列为 12， 2， 16， 30， 28， 10， 16*， 20， 6， 18，试分别写出使用以下 排序方法，每趟排序结束后关键字序列的状态。 直接插入排序 折半插入排序 希尔排序（增量选取 5， 3， 1） 冒泡排序 快速排序 简单选择排序 二路归并排序 答案： 直接插入排序 2 12 16 30 28 10 16* 20 6 18 2 12 16 30 28 10 16* 20 6 18 2 12 16 30 28 10 16* 20 6 18 2 12 16 28 30 10 16* 20 6 18 2 10 12 16 28 30 16* 20 6 18 2 10 12 16 16* 28 30 20 6 18 2 10 12 16 16* 20 28 30 6 18 2 6 10 12 16 16* 20 28 30 18 2 6 10 12 16 16* 18 20 28 30 折半插入排序 排序过程同 希尔排序（增量选取 5， 3， 1） 10 2 16 6 18 12 16* 20 30 28 （增量选取 5） 6 2 12 10 18 16 16* 20 30 28 （增量选取 3） 2 6 10 12 16 16* 18 20 28 30 （增量选取 1） 冒泡排序 2 12 16 28 10 16* 20 6 18 30 2 12 16 10 16* 20 6 18 28 30 2 12 10 16 16* 6 18 20 28 30 2 10 12 16 6 16* 18 20 28 30 2 10 12 6 16 16* 18 20 28 30 2 10 6 12 16 16* 18 20 28 30 2 6 10 12 16 16* 18 20 28 30 2 6 10 12 16 16* 18 20 28 30 快速排序 12 6 2 10 12 28 30 16* 20 16 18 6 2 6 10 12 28 30 16* 20 16 18 28 2 6 10 12 18 16 16* 20 28 30 18 2 6 10 12 16* 16 18 20 28 30 16* 2 6 10 12 16* 16 18 20 28 30 左子序列递归深度为 1，右子序列递归深度为 3 简单选择排序 2 12 16 30 28 10 16* 20 6 18 2 6 16 30 28 10 16* 20 12 18 2 6 10 30 28 16 16* 20 12 18 2 6 10 12 28 16 16* 20 30 18 2 6 10 12 16 28 16* 20 30 18 2 6 10 12 16 16* 28 20 30 18 2 6 10 12 16 16* 18 20 30 28 2 6 10 12 16 16* 18 20 28 30 2 6 10 12 16 16* 18 20 28 30 二路归并排序 2 12 16 30 10 28 16 * 20 6 18 2 12 16 30 10 16* 20 28 6 18 2 10 12 16 16* 20 28 30 6 18 2 6 10 12 16 16* 18 20 28 30
展开阅读全文