<4D F736F F D20BBAAC4CFC0EDB9A4B4F3D1A72020CAFDBEDDBDE1B9B9B8B4CFB0B1CABCC7D5FBC0ED2E646F63>

Size: px

Start display at page:

Download "<4D F736F F D20BBAAC4CFC0EDB9A4B4F3D1A72020CAFDBEDDBDE1B9B9B8B4CFB0B1CABCC7D5FBC0ED2E646F63>"

倍焦
5 years ago
Views:

1 数据结构复习笔记整理第二部分复习提纲 ( 不分题型, 弄清原理, 不要死记硬背 ). 简单复杂性的判断 : ()i=n; while(i>=) i=i/2; 其中 i=n,n/2,n/2 2,,n/2 k, 需 n/2 k >=, 即 2 k <=n, 所以复杂性为 O(log2n) (2)i=; while(i<=n) i=i+2; 其中 i=,3,5,,(2k-), 需 2k-<=n, 则频度 k<=(n+)/2, 复杂性为 O(n) (3)i=; while(i<=n) i=i*3; 其中 i=,3,3 2,,3 k, 需 3 k <=n, 则频度 k<=log3n, 复杂性为 O(log3n) (4)i=; while(i*i<=n) i++; 其中 i=,2,3,,k, 需 k 2 <=n, 则频度 k<=n /2, 复杂性为 O(n /2 ) 2. 四种基本存储方式的特点? 什么时候逻辑关系可以由存储地址表示? 什么时候由指针表示? 什么时候存储地址与结点内容有关系? 答 : 顺序存储方法 : 它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里, 结点间的逻辑关系由存储单元的邻接关系来体现由此得到的存储表示称为顺序存储结构链接存储方法 : 它不要求逻辑上相邻的结点在物理位置上亦相邻, 结点间的逻辑关系是由附加的指针字段表示的由此得到的存储表示称为链式存储结构索引存储方法 : 除建立存储结点信息外, 还建立附加的索引表来标识结点的地址散列存储方法 : 就是根据结点的关键字直接计算出该结点的存储地址 3. 逻辑结构存储结构运算算法算法复杂性等, 哪些与计算机有关? 无关? 答 : 逻辑结构 : 存储结构 : 指数据的逻辑结构在计算机存储器中的实现, 存储结构是依赖于计算机的运算 : 在数据逻辑结构上定义的操作例如有一张学生成绩表, 记录了一个班的学生各门课的成绩按学生的姓名为一行记成的表这个表就是一个数据结构每个记录 ( 有姓名, 学号, 成绩等字段 ) 就是一个结点, 对于整个表来说, 只有一个开始结点 ( 它的前面无记录 ) 和一个终端结点 ( 它的后面无记录 ), 其他的结点则各有一个也只有一个直接前趋和直接后继 ( 它的前面和后面均有且只有一个记录 ) 这几个关系就确定了这个表的逻辑结构那么我们怎样把这个表中的数据存储到计算机里呢? 用高级语言如何表示各结点之间的关系呢? 是用一片连续的内存单元来存放这些记录 ( 如用数组表示 ) 还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题, 我们都是从高级语言的层次来讨论这个问题的

2 最后, 我们有了这个表 ( 数据结构 ), 肯定要用它, 那么就是要对这张表中的记录进行查询, 修改, 删除等操作, 对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了所谓算法 (Algorithm) 是对问题求解步骤的一种描述, 是指令的有限序列, 其中每一条指令表示一个或多个操作所谓算法复杂度 : T (n) = O(f(n)) 称 T (n) 为算法的渐近时间复杂度 (Asymptotic Time Complexity), 简称时间复杂度 O 是数量级的符号下面我们探讨一下如何估算算法的时间复杂度算法 = 控制结构 + 原操作 ( 固有数据类型的操作 ) 算法的执行时间 = 原操作 (i) 的执行次数原操作 (i) 的执行时间算法的执行时间与原操作执行次数之和成正比. 顺序表单链表的存储插入删除运算特点? 是否可以随机存取? 顺序存取? 答 : 顺序表 : 顺序存储 : 就是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的运算 : 对于顺序表的插入和删除运算, 其平均时间复杂度均为 O(n), 顺序表是一种随机存储结构单链表 : 链式存储结构 : 链表是用一组任意的存储单元来存放线性表的结点, 这组存储单元可以分布在内存中任何位置上因此, 链表中结点的逻辑次序和物理次序不一定相同所以为了能正确表示结点间的逻辑关系, 在存储每个结点值的同时, 还存储了其后继结点的地址信息 ( 即指针或链 ) 这两部分信息组成链表中的结点结构一个单链表由头指针的名字来命名, 不是随机存储运算 : 其操作运算主要有建立单链表 ( 头插法尾插法和在链表开始结点前附加一个头结点的算法 ) 查找 ( 按序号和按值 ) 插入运算删除运算等以上各运算的平均时间复杂度均为 O(n). 其主要时间是耗费在查找操作上 2. 单链表中插入结点的基本步骤? 答 : 如果插入在链表开头 : New NewNode; NewNode->Next=Pointer; HEAD->Next=NewNode; 如果插入在链表中间 : NewNode->Next=Pointer->Next; Pointer->Next=NewNode; 如果插入在链表末端 : NewNode->Next=Pointer->Next; Pointer->Next=NewNode; 3. 有头结点无头结点的循环非循环单链表为空的条件分别是什么? 有头结点非循环 :HEAD->Next = = NULL 有头结点循环 : HEAD->Next = =NULL 无头结点非循环 : HEAD = =NULL 无头结点循环 : HEAD = = NULL 4. 用尾指针表示循环单链表有什么好处? 答 : 尾指针是指向终端结点的指针, 用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便, 设一带头结点的单循环链表, 其尾指针为 rear, 则开始结点和终端结点的位置分别是 rear->next->next 和 rear, 查找时间都是 O() 若用头指针来表示该链表, 则查找终端结点的时间为 O(n) 5. 例 : 删除顺序表中所有的正数, 要求移动次数小解 : 搜索顺序表, 对每一个正数, 先不删除, 而是累计当前正数个数 s, 于是, 对每个非正数, 将它一次性前移 s 位算法复杂性为 O(n) void dels(sqlist *L) {

3 int s,i; s=; // 正数计数器 for(i=;i<l->n;i++) if(l->data[i]> s++; // 累计当前正数 else if(s>) L->data[i-s]=l->data[i]; // 向前移动 s 位 L->n=L->n-s; // 调整表长 6. 例 : 将顺序表中所有负数移动到表的前端, 要求移动次数小解 : 双向扫描 : 从前向后找一个正数, 再从后向前找一个负数, 然后交换两者位置复杂性为 O(n) void moves(sqlist *L) { int i,j; datatype x; i=;j=l->n; // 删除 A[] 到 A[n] 的所有零元素, 设数组下标从开始 while(i<j) { while(l->data[i]< && i<j) i++; // 从前向后找正数 while(l->data[j]>= && i<j) j ; // 从后向前找负数 if(i<j) { x=l->data[i];l->data[i]=l->data[j];l->data[j]=x; // 交换 i++;j ;. 链队列链栈是否都有必要设置头结点? 答 : 一个链队列需要两个分别指示队头和队尾的指针才能为一确定 ; 链接栈需要链表的头指针 2. 循环队列 A[m] 中, 已知头指针尾指针与元素个数中的任意两个, 求另一个? 队满条件? len=(rear-front+m)%m; rear=(front+len)%m; front=(rear-len+m)%m; 队满 :front=(rear+)%m 3. 串长空串空白串串连接子串定位 ( 模式匹配 ) 等是何意? 串中字符的数目 n 称为串的长度个字符的串成为空串, 它的长度为串的串连是将一个串紧接着存放在另一个串的后面而成的一个新串串的连接满足结合率, 不满足交换率串的模式匹配问题 : 子串的定位操作通常称为串的模式匹配通常思想是从主串 S 的第 pos 个字符起和模式的第一个字符比较, 若相等则继续逐个比较后继字符, 否则从主串的下一个字符起再重新和模式的字符比较依此类推, 直至模式 T 中的每个字符依次和主串 S 中的一个连续的字符序列相等, 则称匹配成功, 函数值为和模式 T 中第一个字符相等的字符在主串 S 中的序号, 否则称模式不匹配, 函数值为. 稀疏矩阵特殊矩阵的含义? 为什么要对矩阵进行压缩存储? 稀疏矩阵 : 对于 m*n 的矩阵 A 中若有 N 个非元, 若 N<<m*n, 则可称 A 为稀疏矩阵特殊矩阵 (): 对称矩阵由于对称性, 只需存储上三角或下三角部分, 如按行优先顺序存储对称矩阵 A, 则等价于压缩在一个一维数组 B 中 LOC[aij]=LOC[B[k]]=LOC(a)+(k-)*L 特殊矩阵 (2): 上 ( 下 ) 三角矩阵以下三角为例, 既当 i<j 时,aij= 其压缩思路同对称矩阵 LOC[aij]=LOC(a)+(k-)*L 矩阵压缩的原因 : 在数值分析中经常出现一些阶数很高的矩阵, 同时在矩阵中有许多值相同的元素或者是元素有时为了节省存储空间, 可以对这类矩阵进行压缩储存 2. 三元组含义? 一般矩阵按三元组存储能否节省空间? 三元组表表示法 : 每一个非元素对于一个三元组 (row,col,val),row 为非元素的行下标,col 为非元素的列下标,val 为非元素的值显然, 有 N 个非元素的, 只需要 3N 个存储单元

4 3. 广义表可分成几种? 它们的图形表示特点如何? 4. 例 : 从广义表 A=(x,(a,b,c),y) 中取出原子 b 在广义表中取某个元素, 需要将该元素所在的子表逐步分离出来, 直到所求的元素成为某个子表的表头, 再用取表头运算取出注意, 最终取出某个元素时, 不能用取表尾, 因为它得到的是该元素组成的子表, 而不是元素本身本例的运算过程为取表尾 tail(a): 得到 B=((a,b,c),y) 2 取表头 head(b): 得到 C=(a,b,c) 3 取表尾 tail(c): 得到 D=(b,c) 4 取表头 head(d): 得到 b 总的过程为 :head(tail(head(tail(a)))). 树所有结点的度数之和与结点数有何关系? 与边数有何关系? 解 : 边数 = 度数和 = 结点数 - 因为度数就是孩子数, 而根不是孩子, 故度数和比结点总数少 2. 只有 3 个结点的二叉排序树有几种形态? 解 : 有 5 种, 见下图所示 3. 二叉树是否是树的特殊情形? 是否是有序树的特殊情形? 解 : 都不是 4. 树和二叉树的度有何特点? 二叉树的度肯定为 2 吗? 解 : 二叉树每个结点最多两个孩子, 即结点的度最大为 2, 但也可能所有结点的度都不为 2, 如只有个结点, 或单枝树等, 所以二叉树的度并不一定是 2 5. 某完全二叉树有 6 个结点, 则叶子数有多少? 度结点有多少?

5 解 : 由层次编号规律, 结点 i 的左孩子编号为 2i, 若结点 i 为叶子, 则它没有左孩子, 即 2i>n, 即 i>n/2 =3 的结点为叶子, 叶子号为 3,32,,6, 共 3 个由于 n=n2+, 现在 n=3, 所以 n2=299 另外, 结点总数 n=n+n+n2, 所以 n= = 6. 二叉树每层只有一个结点, 则高度为 k 的二叉树有多少种? 解 : 每种这样的二叉树只能有一个叶子, 在最底层, 而叶子可能有 2 k- 种情况, 故有 2 k- 种 7. 完全二叉树有 6 个叶子, 则结点总数就是吗? 解 : 已知叶子数的完全二叉树一般有两棵, 结点数差, 见下图 : A A B C B C D E F G D E F G H I J K H I J K L 一般, 结点数 n=n+n+n2, 而 n=n2+( 二叉树性质 ), 所以 n=2n-+n 完全二叉树树中度为的结点最多只有个, 即 n= 或, 所以 n=2n 或 n=2n- 8. 二叉树各结点在先中后序序列中的相对位置是否不变? 解 : 若是叶子结点, 则在先中后序序列中的相对位置不变, 其它结点未必 9. 给定二叉树先中后序序列中的任意两个, 是否就可还原出二叉树? 解 : 若给定的是先序和后序, 则由于不能确定根, 也就不能还原出二叉树 ( 不唯一 ). 如何由先序 + 中序后序 + 中序还原出二叉树? 解 : 由遍历方法以下几点是显然的 : 对前序序列, 序列的第一个点就是整个二叉树的根 ; 2 对后序序列, 序列的最后一个点就是整个二叉树的根 ; 3 对中序序列, 以根为界, 序列的前一部分结点在根的左子树中, 后一部分结点在根的右子树中 ; 并且, 由前一部分构成的子序列是左子树的中序序列, 由后一部分构成的子序列是右子树的中序序列若给定了前序和中序序列, 反复利用上面的和 3, 就可获得结点完整的逻辑信息, 即由前序序列找到根, 由中序序列得到左右子树 ; 再在对每个子树由前序序列找到子树的根, 由中序序列得到子树的左右子树, 等等类推, 每次都可得到一个点 ( 子树的根 ), 从而逐渐获得树的全部信息, 也就可以还原和构造出该二叉树这个过程参见下图前序遍历序列 : 根根左子树根右子树 ps pe 中序遍历序列 : 左子树根右子树 is i 例 : 已知二叉树的中序和后序序列分别为 :BCDAFEHJIG DCBFJIHGEA, 画出该二叉树解 : 由后序序列可知, 整个二叉树的根为 A, 再从中序序列找到结点 A, 其左边为 BCD, 对应 A 的左子树, 右边为 FEHJIG, 对应根的右子树对每个子树进行同样分析即可画出此二叉树比如对左子树 BCD, 从原后序序列可找到它对应的后根序列为 DCB, 于是左子树的根为 B, 然后再由中序序列 BCD 可知 B 的左子树为空,CD 在 B 的右子树, 等等继续下去, 直到每个结点都画出来. 完全二叉树的深度为 log 2 n 或 log 2 (n ), 是否是说深度有两种可能? 解 : 只一种, 它们的具体值相等 2. 树的常用存储方法有哪些? 如何将树转换为二叉树? 树的遍历与对应二叉树的遍历有何关系? 3. 怎样知道线索二叉树某结点是否有左右孩子, 是否为叶子? 解 : 看结点的线索标志位, 比如左线索标志位 ltag= 则无左孩子, 左右线索标志位都为则为叶子 4. 如何画中序先序后序线索二叉链表? 线索二叉链表是否就没有空指针了? 解 : 以中序线索二叉链表为例, 下列二叉树的中序线索二叉链表如图所示详细过程见课本 ie

6 A A B C B C NULL D E NULL D E F F 5. 线索二叉树上求结点的前趋和后继时, 是否可不再需要遍历了? 答 : 是, 因为为了方便得到结点在任意序列中的前驱和后继的信息, 特地在结点的结构中增加了两个标志域, 分别标明节点的前驱和后继信息其中指向结点前驱和后继的指针, 叫做线索 6. 什么是前缀码? 指的是, 任何一个字符的编码都不是同一个字符集中另一个字符的编码的前缀哈夫曼编码是一种最优前缀编码 7. 哈夫曼树如何构造?WPL 如何求? 其结点总数可以为吗? 其中有度结点吗? 解 : 哈夫曼树的结点总数为 2n-, 必为奇数, 不可能为偶数其中 n 为叶子数构造过程是每次两个结点合并, 故不会出现度的结点 8. 例 : 求二叉树中度为的结点数解 : 设二叉树结点类型为 bitree, 函数名为 sum, 函数返回结点数 int sum(bitree t) { int L,R; if(t==null) return ; // 当前树为空, 递归出口 L= sum(t->lchild); // 求左子树中相应结点数 R= sum(t->rchild) // 求右子树中相应结点数 if((t->lchild==null && t->rchild!=null) (t->lchild!=null && t->rchild==null)) // 当前结点度为也 return L+R+; // 度结点数 = 左子树中度结点数 + 右子树中度结点数 + else return L+R; 9. 例 : 求二叉树中度为 2 的结点数解 : 设二叉树结点类型为 bitree, 函数名为 sum2, 函数返回结点数 int sum2(bitree t) { int L,R; if(t==null) return ; // 当前树为空, 递归出口 L= sum(t->lchild); // 求左子树中相应结点数 R= sum(t->rchild) // 求右子树中相应结点数 if(t->lchild!=null && t->rchild!=null) // 当前结点度为也 2 return L+R+; // 度 2 结点数 = 左子树中度 2 结点数 + 右子树中度 2 结点数 + else return L+R;. 图的 DFS 和 BFS 遍历分别用到什么数据结构? 解 : 栈队列 2. 一个图有 n 个顶点, 则每个顶点的度最大是多少? 解 : 对无向图, 最大为 n-; 对有向图, 最大可为 2(n-), 因为每个顶点到其余 n- 顶点都可有一条入边和出边 3. 连通图如果没有回路, 则最多多少条边? 多少条边后肯定有回路? 解 : 无回路时, 最多 n- 条边, 即生成树

7 4. 连通分量含义? 连通图有多少连通分量? 答 : 在无向图 G 中, 若从顶点 vi 到顶点 vj 有路径, 则称 vi 和 vj 是连通的若图中的任意两个顶点都连通, 则称 G 为连通图, 否则称为非连通图无向图 G 的极大连通子图称为 G 的连通分量显然, 任何连通图的连通分量只有一个, 即本身 5. n 个顶点的强连通图至少多少条边? 最多多少边? 答 : 强连通的图最多有 n(n-), 最少有 n 条边 6. 度出度入度的概念和关系? 无向图中顶点 v 的度 (degree) 定义为以该结点为一端点的边的数目, 简单地说, 就是该顶点的边的数目, 即为 D(v) 在有向图中顶点 v 的度有入度和出度之分, 入度 (indegree) 是该顶点的入边数目, 记为 ID(v); 出度 (outdegree) 是该顶点的出边的数目, 记为 OD(v); 顶点 v 的度等于它的入度和出度之和, 即 D(v)=ID(v)+OD(v) 7. 邻接矩阵邻接表逆邻接表的特点, 如怎样求边数出度入度等? 邻接矩阵 : 是表示顶点之间相邻关系的矩阵在采用邻接矩阵表示图, 对于无向图, 边数即为矩阵中非 ( 或非 max) 的个数除以 2, 对于有向图, 边数即为矩阵中非 ( 或非 max) 的个数 ; 对于无向图, 顶点 vi 的度就是对应第 i 行或第 i 列上非 ( 或非 max) 元素的个数, 对于有向图, 顶点 vi 的出度就是对应第 i 行上非 ( 或非 max) 元素的个数, 顶点 vi 的入度就是对应第 i 列上非 ( 或非 max) 元素的个数邻接表 : 是对图中的顶点建立一个邻接关系的单链表, 并把它们的表头指针用向量存储的一种图的表示方法在图的邻接表中便于查找一个顶点的度 ( 出度 ), 这只要首先从表头向量中取出对应的表头指针, 然后从表头指针出发进行查找计算即可但对于有向图的邻接表中查找一个顶点的入度, 那就不方便了, 它需要扫描所有的顶点邻接表中所有顶点邻接表中的边结点, 因此专门建立一个逆邻接表, 该表中的每个顶点的单链表示储存该顶点的所有入边的信息 8. 生成树和最小生成树的概念, 是否唯一? 生成树 : 一个连通无向图的生成树是图的一个连通分量, 它含有图的所有 n 个顶点以及连接这些顶点的 n- 条边不唯一最小生成树 : 具有权最小的生成树称为图的最小生成树不唯一 9. 什么时候不能拓扑排序? 解 : 存在有向回路时不能. 为什么要对数据进行排序? 排序算法可分为哪几类? 2. 哪些排序思想或方法可用来找序列中前几个最大或最小? 提示 : 堆排序选择排序快速排序 ( 基准位置为第几就是第几大 ) 3. 哪些排序方法的效率与序列的初始状态基本无关? 有关? 4. 哪些是稳定的? 不稳定的? 5. 各种排序算法的复杂度如何? 排序法平均时间复杂度最坏时间复杂度稳定度空间复杂度 ( 辅助存储 ) 效率与序列的初始状态冒泡排序法 O(n 2 ) O(n 2 ) 稳定 O() 基本有关快速排序 O(nlog2n) O(n 2 ) 不稳定 O(log2n) 选择排序 O(n 2 ) O(n 2 ) 稳定 O() 基本有关堆排序 O(n log2n) O(n log2n) 不稳定 O() 插入排序 O(n 2 ) O(n 2 ) 稳定 O() 基本有关谢尔排序 O(n.3 ) O 不稳定 O() 二叉排序树 O(n log2n) O(n 2 ) 不一定 O(n) 归并排序 O(n log2n) O(n log2n) 稳定 O(n) 基数排序 O(d(n+rd)) O(d(n+rd)) 稳定 O(n+rd)

8 6. 各种排序方法步骤如何? 要会写每趟的结果难点 : 快速排序堆排序希尔排序 7. 排序效率如何评价? 关键字比较次数越少, 排序就越快吗? 解 : 除了关键字比较, 还有关键字移动问题如果移动次数多结点内容又多, 则排序时间也会较长特别地, 基数排序不需比较, 但执行时间并不一定比需要比较的排序快.2 个结点的有序表二分查找, 最多比较次数如何? 解 : 判定树的高度, log 2 n 2. 二叉排序树的形态与什么有关? 解 : 取决于关键字输入顺序 3. 在 n 个结点的二叉排序树上查找, 最多比较多少次? 最少比较多少次? 解 : 不超过树的高度, 最大为 n( 此时为单枝树 ) 4. 二叉排序树中删除一个结点后马上再插入, 二叉树是否不变? 解 : 若删除的是叶子, 则不变其它会变 5. 什么叫 AVL 树? 特点? 答 : 平衡二叉树又称 AVL 树, 它或是一棵空树, 或是具有下列性质的二叉树 : 他的左子树和右子树都是平衡二叉树, 且左子树和右子树的深度之差的绝对值不超过 7.B- 树 B+ 树概念? 如何识别? 如何判断树的阶数? 谁既可随机查找, 又可顺序查找? 答 :B 树和 B+ 树都是平衡的多路查找树, 主要用于文件系统中一棵 m 阶的 B- 树, 或为空树, 或满足下列特性的 m 叉树 : () 树中每个结点至多有 m 棵子树 ; (2) 若根结点不是叶子结点, 则至少有两棵子树 ; (3) 除根之外的所有非终端结点至少有 [m/2] 棵子树 ; (4) 所有的非终端结点中包含下列数据信息 (n,a,k,a,k2,a2, Kn, An) 其中 :Ki(i=,2,,n) 为关键字, 且 Ki<Ki+(i=,2,,n-);Ai(i=,,2,,n) 为指向子树根结点的指针, 且指针 Ai- 所指子树中的所有结点的关键字小于 Ki(i=,2,.,n),An 所指的子树中的所有结点的关键字均大于 Kn,n( m / 2 -<=n<=m-) 为关键字的个数 ( 或 n+ 为子树的个数 ) (5) 所有的子叶结点都出现在同一层次上, 并且不带信息 ( 可以看作是外部结点或查找结点失败的结点, 实际上这些结点不存在, 指向这些结点的指针为空 ) B+ 树是应文件系统所需而出的一种 B- 树的变型树一棵 m 阶的 B+ 树和 m 阶的 B- 树的差异在于 : () 有 n 棵子树的结点中含有 n 个关键字 (2) 所有的子叶结点中包含了全部关键字的信息和指向含这些关键字记录的指针, 且叶子结点本身依关键字从小到大顺序链接 (3) 所有的非终结点可以看成是索引部分, 结点中仅含子树 ( 根结点 ) 中的最大 ( 或最小 ) 关键字 (4) 通常在 B+ 树上有两个头指针, 一个指向根节点, 另一个指向关键字最小的叶枝结点因此, 可以对 B+ 树进行两种查找运算 : 一种是从最小关键字起顺序查找, 另一种是从根节点开始, 进行随机查找 ; 而 B- 树只有一个指向根结点的指针, 无法实现顺序查找 (5) 在 B+ 树上进行随机查找插入和删除的过程基本上与 B- 树类似只是在查找时, 若非终结点的关键字等于给定值, 并不终止, 而是继续向下直到叶子结点因此, 在 B+ 树中, 不管查找成功与否, 每次查找都是走了一条从根到叶子结点的路径 9. 什么叫冲突? 答 : 一个待插入元素的散列地址单元已被占用, 使得该元素无法直接存入到此单元中, 我们把这种现象叫做冲突. 线性探测法解决冲突时, 同义词分布是否是连续的? 答 : 是. 散列表的查找效率主要取决哪些因素? 是否取决于关键字的个数?

9 答 : 取决于三个因素 : 哈希函数处理冲突的方法和哈希表的填装因子否. 在个结点中查找, 肯定比在个结点中查找的平均时间慢吗? 提示 : 如果采用散列方法组织数据, 查找效率不直接取决于数据个数 n 2. 例 : 已知关键字输入序列 {,7,6,9,2, 画出相应的二叉排序树, 并求在等概率下查找成功和不成功时的平均查找长度解 : 对应的二叉排序树见右图 ( 插入过程见课本 ) 查找成功时平均查找长度为 3 ASL=( )/5=/5=2.2 5 查找不成功时有图中虚线所示的几种情况 ( 即 <6,6~9,9~,~7,7~2,>2), 所以平均查找长度为 ASLun=( )/6=6/6=2.67 注意这里指关键字比较, 不包含空树的空指针比较 3. 例 : 在 6 个结点的有序表中进行二分查找, 在等概率下查找成功和不成功时的平均查找长度如何? 解 : 先画出 6 个结点二分查找的判定树, 右图显然, 如果要查找的点正好在第 i 层, 则经过 i 次关键字的比较, 对本题, 每层的结点数分别为 2 3 个, 所以查找成功时平均查找长度为 ASL=( )/6=4/6=2.33 查找不成功时有图中虚线所示的 7 种情况 ( 即 6 7 Key<A[],A[]~A[2],A[2]~A[3],A[3]~A[4],A[4]~A[5], A[5]~A[6],>A[6]), 所以平均查找长度为 9 2 ASLun=(2 +3 6)/7=2/7=2.86 注意这里指关键字比较, 不包含空树的空指针比较 4. 例 : 对关键字序列 {,78,,,3,2,4,2 构造散列表, 取散列地址为 HT[..], 散列函数为 H(K) =K%, 试用线性探查法冲突, 画出相应的闭散列表, 并分别求查找成功和不成功时的平均查找长度解 : 首先求出散列地址, 见下图 (a), 据此得到闭散列表见下图 (b) 查找成功的平均比较次数为 : ASL=( l)/8=2.375 查找不成功的平均查找长度为 : ASLunsucc=( )/ 例 : 对关键字序列 {,78,,,3,2,4,2 构造散列表, 取散列地址为 HT[..], 散列函数为 H(K) =K%, 试用拉链法解决冲突, 画出相应的开散列表, 并分别求查找成功和不成功时的平均查找长度解 : 散列地址同上题, 开散列表分别见下图 (c) 查找成功的平均比较次数为 : ASL=( 6+2 2)/8=l.25 查找不成功的平均查找长度为 : ASLunsucc=( )/.727 关键字 K 散列地址 K% (a) HT key next 不成功比较次数散列表成功比较次数不成功比较次数 (b) 成功比较次数 2 (c)

2018 年天津城建大学攻读硕士学位研究生入学考试试题 (A) 卷考试科目代码 :825 考试科目名称工程信息技术招生专业 : 建筑与土木工程

2018 年天津城建大学攻读硕士学位研究生入学考试试题 (A) 卷考试科目代码 :825 考试科目名称工程信息技术招生专业 : 建筑与土木工程一单项选择题 ( 本题共 20 小题, 每题 2 分, 共 40 分 ) 1. 计算机所处理的数据一般具有某种内在联系, 这是指 ( ) A. 数据和数据之间存在某种联系 B. 数据项和数据项之间存在某种联系 C. 元素内部具有某种结构 D. 元素和元素之间存在某种联系 2. 在计算机中表示数据时, 数据的物理地址和逻辑地址相同并且连续, 称其为 ( ) A. 链式存储结构 B. 顺序存储结构 C.