数据结构习题讲解

1、数据结构习题习题一、选择题1、算法分析的两个主要方面是：（ ）A 正确性和简明性 B 时间复杂度和空间复杂度C数据复杂性和程序复杂性D 可读性和文档性2、在数据结构中，从逻辑上可以把数据结构分成（）。A动态结构和静态结构C线性结构和非线性结构3、计算机算法具备输入、输出和A有穷性、确定性和稳定性C有穷性、确定性和可行性4、算法分析的目的是（） 。A找出算法的合理性C分析算法的有效性以求改进B 紧凑结构和非紧凑结构D 逻辑结构和存储结构）等 5 个特性： B可行性、可移植性和可扩充性 D易读性、稳定性和安全性B 研究算法的输人与输出关系D分析算法的易懂性二、填空题1、数据结构是一门研究非数值计算

2、的程序设计问题中计算机的以及它们之间的和运算等的学科。2、线性结构中元素之间存在的关系，树形结构中元素之间存在 的关系，图形结构中元素之间存在 的关系。3、是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为 。4、数据的 指数据元素及其关系在计算机存储器内的表示。 是逻辑结构在计算机里的实现，也称之为映像。5、所谓算法（ Algorithm ）是对特定问题求解方法和步骤的一种描述，它是指令的一组 ，其中每个指令表示一个或多个操作。三、问答题1、用大 O 形式写出下面算法的时间复杂度： i0； s=0； while（s n） i+;s+=i;

3、 2、写出以下算法的时间复杂度：for （ i 0; im; i） for（j0 ; jt; j） cij=0 ； for（i=0；i m； i） for （j=o; jt; j+ ） for（ k=0；kn；k） cij ai k*bkj;习题二一、选择题 1在一个长度为 n 的顺序表中删除第 i 个元素 （ 0 in ）时，需要向前移动 （ ）个元素。A n-iB n-i+1C n-i+1D i+12从一个具有 n 个元素的线性表中查找其值等于x 的结点时，在查找成功的情况下，需平均比较 （ ） 个元素结点。An/2BnC（n-1）/2D（n +1）/23若某表最常用的操作是在最后一个结点

4、之后插入一个结点或删除最后一个结点，则 下列存储方式最节省运算时间的是（ ）：A 带头结点的双循环链表B 双链表C给出表头指针的单循环链表D单链表4如果最常用的操作是取第 i 个结点及其前驱结点，那么下列存储方式最节省时间的 是（ ）：A单链表B单循环链表C顺序表D双链表（）B双链表D单链表B一个有限序列，不可以为空D一个无限序列，不可以为空i个元素（0一 1n1）之前捕人一个新元素时，C ni 1D i190，每个元素的长度是 2，则第 6D 1065若某线性表最常用的操作是在最后一个结点之后插入一个结点或者删除最后一个结 点，则下列存储方式最节省运算时间的是： A 仅有尾指针的单循环链表

5、C仅有头结点的单循环链表 6线性表是 （ ）。A一个有限序列，可以为空 C一个无限序列，可以为空7在一个长度为 n 的顺序表中， 向第 需要向后移动 （ ）个元素。An-iB n-i 18一个顺序存储线性表的第一个元素的存储地址是 个元素的存储地址是（） 。A98B100C 1029. 在以下叙述中，正确的是： （）A线性表的线性存储结构优于链式存储结构 B栈的操作方式是先进先出C队列的操作方式是先进后出 D二维数组是其数据元素为线性表的线性表、填空题1线性表是具有 n 个 的有限序列。2在单链表中，要删除某一个指定的结点，必须找到该结点的结点。3向一个长度为 n 的顺序表中的第 i 个数据元

6、素（ 1 in）之前插入一个元素时，需 要向后移动 个数据元素。4在双向链表中，每个结点都具有两个指针域，一个指向，另一个指向。 5线性表中有且仅有一个开始结点，表中有且仅有一个终端结点，除开始结点外，其 他每个元素有巨仅有一个 ，除终端结点外，其他每个元素有且仅有一个 。6线性表的链式存储结构的每一个结点（Node）需要包括两个部分：一部分用来存放元素的数据信息，称为结点的 ；另一部分用来存放元素的指向直接后继元素的指针（ 即直接后继元素的地址信息 ），称为 或 。7写出带头结点的双向循环链表L 为空表的条件 。三、问答题1对链表设置头结点的作用是什么？（至少说出两条好处） 2在单链表、双链

7、表中，如果仅知道指针p 指向某结点，不知道头指针，能否将结点*p 从相应的链表中删去？ 3如果频繁地对一个线性表进行插入和删除操作，那么该线性表应该采用何种存储结 构？为什么？四、程序设计题 1有一个带头结点的单链表（不同结点的数据域值可能相同），其头指针为 head，编写一个函数计算数据域值为 x 的结点个数。2设计一个算法，删除单链表 L 中值为 x 的结点的直接前驱结点。 3设计一个算法，将一个不带头结点的单链表L（至少有一个结点）逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。4在一个带头结点的单链表中，头指针为head，它的数据域的类型为整型，而且按由

8、小到大的顺序排列，编写一个算法insertx list（），在该链表中插人值为 x 的元素，并使该链表仍然有序。习题三一、选择题l一个栈的序列是： a，b， c，d，e，则栈的不可能输出的序列是（） 。Aa，b，c，d，e Bd，e，c， b，a Cd，c，e，a，b De，d，c，b，a2判定一个栈 S（最多元素为 MaxSize ）为栈满的条件是： （ ）A S top!= - 1B S top= - 1C S top=MaxSize -1D S top!=MaxSize -13若一进栈序列为 1，2，3，n，其出栈序列为 P1,P2,P3, Pn，如果 Pn=n,则Pi （1 inext

9、=s ； r=s； B r-next=s ； f=s；C s-next=r ； r=s； D s-next=f ； f=s；5若用一个大小为 8 的一维数组来实现循环队列，且当前 front 和 rear 的值分别为 4 和 1，当从队列中删除一个元素，再加入两个元素后，front 和 rear 的值分别是（） ：A3和5B5和3C2 和 6D 6和 26判断一个循环队列MaxSize ）为空的条件是： （）Q（最多元素为AQ-front=Q-rearB Q-front=( Q-rear +1) %MaxSizeCQ-front!=Q-rearDQ-front!= (Q-rear +1) %M

10、axSize7向一个带头结点、栈顶指针为 top 的链栈中插人一个 *S 结点的时候，应当执行语句）。A top-next=S ；B S-next=top ； top=S；C S-next=top-next ； top-next=S ； D S-next=top ； top=S-next ； 8在一个链队列中，假定 front 和 rear 分别为头指针和尾指针，则插入一个结点 *S 的 操作是（ ）。B S-next=rear ； rear=S D S-next=front ； front SB链式存储的非线性结构 D限制存取点的非线性结构 ）不可能是一个出栈序列。A front front

11、-nextC rear-next=S ； rear=S 9栈与队列都是（）。A链式存储的线性结构C限制存取点的线性结构10若进栈序列为 l， 2，3，4，则（A 3，2，4，1 Bl，2，3，4C 4，2，3，1D4，3，2，l11在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区， 主机将要输出的数据依次写人该缓冲区， 而打印机则从该缓冲区中取走数据打印。 该缓冲区 应该是一个（ ）结构。A 堆栈B队列C数组D线性表、填空题1栈和队列的共同点是2通常元素进栈的操作是3栈（ stack）是限定在 一端进行插人或删除操作的线性表。在栈中，允许插人和删除操作的一端称为 ，而另一

12、端称为 。不含元素的栈称为 4队列（ Queue）也是一种 ，但它与栈不同，队列中所有的插人均限定在表的一端进行，而所有的删除则限定在表的另一端进行。允许插人的一端称为 ，允许删除的一端称为 。5队列中允许进行删除的一端称为 ；允许进行插入的一端称为。三、问答题1设有一个数列的输入顺序为 abcdef，若采用栈结构，并以 J 和 C 分别表示进栈和出栈操 作，试问下列输出序列是否是合法序列？如是，请用进栈和出栈操作表示其合法序列。（1）能否得到输出顺序为 cbefda 的序列？（2）能否得到输出顺序为 aedfbc154623 的序列？2设输入元素为 4、5、 6、B、A，入栈次序为 456B

13、A ，元素经过栈后到达输出序列，当所 有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名？3假设 Q0 10 是一个线性队列，初始状态为 front=rear=0 ，画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。（1）d，e，b，g，h 入队（2）d，e 出队（3）i，j，k，l，m 入队（4）b 出队（5）n，o，p 入队4设有 4个元素 A、B、C 和D 进栈，给出它们所有可能的出栈秩序。四、程序设计题1假设表达式中有三种括号：圆括号“ （）”、方括号“ ”和花括号“ ”用 C语言编 写程序判断读人的表达式中不同括号是否正确配对，假定读人的表

14、达式以”#”结束。习题四、选择项4设有两个串求串 S2在 S1，那么求串 S2在 S1求串 n在串 m 中首次出现的位置的运 算称为：( )A求子串 B求串长C模式匹配 D 串连接4设有串 S=Computer ，则其子串的数目是()。A36B 37C8D94下列是 C 语言中“ ASDF567HJKL ”子串的是： ( ) AASDFBDF56 C“F567HJ” D“DFHJ ”5空串与空格串()。A相同B不相同C可能相同 D 无法确定二、境空题1串是由零个或多个字符组成的 。通常记作： s“ c1，c2，cn”(n=0) ，其中， S称为；串中的 Ci(1=i1）个 的有序组合，数组中的

15、数据是按顺序存储在一块 的存储单元中。2数组中的每一个数据通常称为 ，用下标区分， 其中下标的个数由数组的决定。3广义表是 n（n=0）个元素的序列。记作： A（a1，a2，an），其中， A 是广义 表的，n是它的 ，当 n=0 的时候称为 。4广义表的深度一般定义为广义表元素 ，或者说是广义表 。利用递归的定义，广义表的深度就是所有子表中 。三、问答题 1现有一个稀疏矩阵如下图所示，写出其对应的三元组表示，并求出其转置矩阵的三元组表示。0 2 0 00 0 3 01 0 0 40 0 0 02写一个创建稀疏矩阵相应三元组的算法。四、程序设计题1假设三元组元素值为整型，写一个查找三元组元素值

16、为n 的算法。习题六、选择题 1设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含节点数至少 有：（ ）A 2h B2h+1Ch+1D 2h-12现有一二叉树，若其先序遍历序列为ABCDE ，中序遍历序列为 CBDAE ，那么其后序遍历序列为：（ ）A BDAEC BEDCBA CDABEC DCDBEA3在线索化二叉树中，A t-left=NULLCt-ltag=1t 所指结点没有左子树的充要条件是：B t-left=0D t-left=NULL 且 t-ltag=1 4设深度为 h 的二叉树上只有叶子结点和同时具有左右子树的结点，则此类二叉树中所包含的结点数目至

17、少为（ ）。A 2hB2h5二叉村第 k 层上最多有（）个结点。C2h1A2k6二叉树的深度为A2kB2k-1k，则二叉树最多有（B2k-1kC2k-1 ）个结点。C2k-1D2h-lD2kkD 2 -17设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是A abdecB debacCdebcaD abedc8设某一二叉树中序遍历为badce，后序遍历为bdeca，则该三叉树先序遍历的顺序是）。）。A adbecB decabC debacD abodeA29B 31C17D209 N 个结点的线索二叉树中，线索的数目是（）。AN-1BN1C 2ND2N110将

18、一棵树 T 转换为一棵二叉树 T2 ，则 T 的先序遍历是 T2 的（）。A先序B中序C后序D无法确定11将一棵树 T 转换为一棵二叉树 T2 ，则 T 的后序遍历是 T2 的（）。A先序B中序C后序D无法碉定12设一棵二叉树度2 的结点数是 7 ，度为 1 的结点数是 6，则叶子结点数是（）A6B7C8D913一棵非空的二叉树，先序遍历与后序遍历正好相反，则该二叉树满足（）。A 无左孩子B无右孩子C只有一个叶子结点D任意二叉树14线索二叉树是一种（）。A逻辑结构B线性结构C逻辑和线性结构D 物理结构15权值为 l， 2， 6，8的四个结点构成的哈夫曼树的带权路径长度是（）。、填空题1树 （T

19、ree）是 n（n 0）个结点的 集。2深度为 5 的二叉树至多有 个结点。3树中任意结点允许有零个或多个孩子结点，除根结点以外 ,其余结点双 亲结点。4在一棵二叉树中，度为零的结点个数为n0 ，度为 2 的结点个数为 n2,那么n0= 。5结点的度是指结点所拥有的 。6一个结点的子树中的任一结点都称为该结点的 。7从根到该结点所经分支上的所有结点称为该结点的 。8具有 的结点互称为兄弟结点，简称为兄弟。9从根结点开始定义，根为 层，根的孩子为 层，依次往下类推，若某结点在第 k 层，则其子树的根就在 层。10如果树中各结点的各子树无排列顺序， 即可以互换位置， 则称为该树为 11二又树( B

20、inary Tree )是结点的有限集合，这个集合或者是空，或者是由一个根结 点和 的称为 和 的二叉树构成。12二叉树第 i 层上最多有 个结点。13深度为 k 的二又树最多有 个结点 (k l)。14在任意二叉树中，叶子结点的数目 ( 即度为 0 的结点数 )等于度为 2 的结点数15一棵深度为 k 且具有 2k-1 个结点的二叉树称为 。这类二叉树的特点是，二叉树中每一层结点的个数都是 的个数。16是那种在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者所缺少的结点都在右边。17具有 n 个结点的完全二叉树的深度是 。18先序遍历二叉树的操作定义为：若二叉树为空

21、，则为空操作；否则进行如下操作： 访问二叉树 ；先序遍历二叉树 ；先序遍历二叉树 。19中序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作： 中序遍历二叉树 ；访问二又树 ；中序遍历二又树 。20后序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作： 后序遍历二叉树 ；后序遍历二叉树 ；访问二叉树 。21线索二叉树( Threaded Binary Tree)是充分利用二义链表的n+1 个空的指针域作为线索来标志每一个结点的 和 信息。 当某个结点有左孩子的时候， 使其指向其左孩子， 无左孩子的时候， 使其左指针域指向该结点的 ；当 某个结点有有孩子的时候

22、， 使其右指针域指向该结点的 ，无右孩子的时候， 使其有指针域指向该结点的 。22线索二叉树的线索链表中，指向结点前驱和后继的指针称为 ；加上线索的二叉树称为 ；对二叉树以某种次序进行遍历使其成为线索二叉树的过程称为 。23哈夫曼树( Huffman Tree )又称 。它是 n 个带权叶子结点构成的所有二叉树中，带权路径长度 WPL 。三、问答题1一棵树表达成如下形式：DA ，B，C，D，E，F，G， H，I，J，K，L，M ，N，OR=A，B，A，C，A，D，B，E，B，F， C，G，D，H，D，I， D ， J， K ， F， K，L， F， M ， I，N， I，O 其中 D 为结点集

23、合， R 为边的集合。请根据以上内容回答以下问题：10(1) 画出这棵树。(2) 该树的根结点是哪一个？(3) 哪些是叶子结点？(4) F 结点的双亲是谁？(5) F 结点的祖先是哪些？(6) F 结点的孩子是哪些？(7) F 结点的兄弟是哪些？(8) F 结点的堂兄弟是哪些？(9) F 结点的度是多少？(10) F 结点的层次是多少？(11) D 结点的子孙有哪些？(12) 以结点 D 为根的子树度是多少？(13) 以结点 D 为根的子树层是多少？(14) 该树的层是多少？(15) 该树的度是多少？2画出图 6-1 中树的二叉树表示形式。( a)(b)( c)图 6-l3已知某二叉树的先序遍

24、历的结果是： A，B，D，QC，E，H，L，I，K，M，F和 J， 它的中序遍历的结果是： QD，B，A，L，H，E，K，LM，C，F和 J，请画出这棵二叉树， 并且写出该二叉树后序通历的结果。4设 A、B、C、D、E、F 六个字母出现的概率分别为 7,19,2,6,32,3 ，构建哈夫曼树 (请 按左子树根结点的权小于等于右子树根结点的权的次序构造) ，计算出带权路径长度 WPL， 并设计每个字母的哈夫曼编码5假设一棵二叉树的后序序列为 DCEGBFHKJI，A 中序序列为 DCBGEAHFIJ，K请完成下列 操作：(1)画出该二叉树； (2) 写出该二叉树的先序遍历序列； ( 3)画出该二

25、叉树的中序遍 历线索二叉树。6假设一棵二叉树的先序序列为 ABDGCEHLIKMFJ ，中序序列为 GDBALHEKIMCFJ ， 请完成下列操作。(1) 画出该二叉树；(2) 写出该二叉树的后序遍历序列；(3) 画出该二叉树的中序遍历线索二叉树。7假设通讯电文中只用到 A，B，C，D，E，F 六个字母，它们在电文中出现的相对频率 分别为： 7，2，15，9，4，19，要求画出哈夫曼树(请按左子树根结点的权小于等于右子树 根结点的权的次序构造) ，并计算出带权路径长度 WPL，试设计每个字母的哈夫曼编码。8有七个带权结点 , 其权值分别为 2,6,7,1,5,9,13, 试以它们为叶子结点构造

26、一棵哈夫11 曼树（请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造） , 并计 算出带权路径长度 WP。L9假设一棵哈夫曼树共有 n0个叶子结点，试证明树中共有2no-l 个结点。10假设通信用的报文由 9个字母 A、B、C、D、E、F、G、H和 I构成，它们出现的 频率分别是： 10、 20、 5、 15、 8、 2、3、 7和 30。请用这 9个字母出现得频率作为权值求：（l）设计一棵哈夫曼树。（ 2）计算其带权路径长度 WPL 值。 （3）写出每个字符的哈夫曼编码。四、程序设计题1. 自己设计一棵二叉树，编写一个完整的程序，输出该二叉树的先序、中序和后序序 列。（程序

27、中应包括二叉树的生成函数，先序、中序、后序遍历函数） 。2已知一棵二叉树的先序遍历序列和中序遍历序列，请写出根据二又树先序遍历序列 和中序遍历序列构造一棵二叉树的算法。12习题七、选择题1在一个无向图 G 中，所有顶点的度数之和等于所有边数之和的()倍。A l/2B 1C2D42对某个无向图的邻接矩阵来说： ( )A 第 i 行上的非零元素的个数和第 i 列上的非零元素的个数一定相等B矩阵中的非零元素的个数等于图中的边数C第 i 行上、第 i 列上非零元素的总数等于顶点 Vi 的度数D矩阵中非全零行的行数等于图中的顶点数3采用邻接表存储的图的深度优先遍历算法类似于二叉树的：( )A 先序遍历

28、B中序遍历 C后序遍历 D按层遍历条边： ( )4在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要An-1BnCn+1D n/25在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的()倍。Al/2B1C2D46一个具有n 个顶点的无向图包含()条边。AnBn1Cn-1Dn/27一个具有n 个顶点的无向完全图包含()条边。A n(n-l)B n(n+l)Cn(n-l)/2D n(n-l)/28. 一个具有n 个顶点的有向完全图包含()条边。An(n-1)Bn(n+l)Cn(n-l)/2D n(n+l)/29无向图的邻接矩阵是一个()。A 对称矩阵B 零矩阵C上三角矩阵D 对角矩阵

29、、填空题1在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种的关系。2在有 n 个顶点的有向图中，至多有条边。3具有 10 个顶点的无向图，边的总数最多为。4在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要 条边。5具有 n (n-1)/2 条边的无向图称为 ，简称为 ，其中 n 表示无向图中顶点的个数， n(n-1)/2 是具有 n 个顶点无向图所拥有边的 。6具有 n 个顶点的有向图，如果它同时具有n(n-1)条弧，则称该图为 ，其中 n(n-1)是具有 n 个顶点有向图所拥有弧的 。7 如果图中的边或弧带有权，则称这种图为 。8顶点 v 的度定义为 的数目，记

30、为 D(v) 。9在有向图中，顶点 v 的度又分为 和，是以顶点v 为头的弧的数目，或者说是以该顶点为终点的边的数目，记为ID(v) ； 是以顶点 v 为尾的弧的数目，或者说是以顶点为起点的边的数目，记为OD(v) ；顶点 v 的度是它的和之和，即 D(v)=ID(v) OD(v) 。10是指一条路径上所经过的边或弧的数目。11若一条路径上除开始结点和结束结点外( 开始结点和结束结点也可以为不同顶点) ，13其余顶点均不相同，则称该路径为 。12 若一条路径上的开始结点和结束结点为同一个顶点，则称该路径为。同时除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称 或 。13一个 称为有

31、向无环图，简称为 DAG 图。三、问答题或0 出发分别进5依据以下无向图，使用普里姆算法，写出构造该图的最小生成树的过程。G 的最小生成树的过程141已知一个无向图的邻接矩阵如图所示， 请画出该无向图， 并写出从顶点 行深度优先和广度优先搜索遍历得到的顶点序列。习题八一、选择题1.顺序查找方法适合于存储结构为()的线性表A. 散列存储B.索引存储C.散列存储或索引存储D.顺序存储或链接存储2采用折半查找法查找长度为 n 的线性表时，每个元素的平均查找长度为： ( ) A O(n2) BO(n log2n)CO(n) D O(log2n)3对线性表进行折半查找时要求线性表必须：()A以顺序方式存

32、储 B 以顺序方式存储，且结点按关键字有序排序C以链式方式存储 D 以链式方式存储，且结点按关键字有序排序 4可以在哈希查找过程中处理冲突的方法是：()A 关键字比较法 B线性探查法 C数字分析法D 除留余数法5.己知一个有序表为 (11,22,33,44,55,66,77, 88,99), 则折半查找元素 55 需要比较 ()次。A.1B.2C.3 D.46.顺序查找法与二分查找法对存储结构的要求是( ) 。A. 顺序查找与二分查找均只是适用于顺序表B. 顺序查找与二分查找均既适用于顺序表 , 也适用于链表C. 顺序查找只是适用于顺序表D. 二分查找适用于顺序表二、填空题1. 折半查找 (

33、Binary Search) 又称为 ， 是一种效率较高的一种查找算法 。2. 分块查找 (Blocking Search) 又称为 ，是一种以 的形式来来进 行的查找方法。分块查找是 的一种改进，它是一种介于 和折半查找之 间的查找方法。3. 如果对查找表只进行查询某个 特定的 数据元素是否在查找表中 , 以及查找某 特 定的 数据元素的各种属性两种类型的基本操作, 而不进行插入和删除数据元素的查找表称为。4. 如果在查找表中进行查找的过程中，同时插入查找表中不存在的数据元素，或者查 找表中删除已存在的某个数据元素，则称此类查找表为 。5. 用折半法查找一个线性表时，该线性表必须具有的特点是

34、 。6. 在一个查找表中， 能够惟一的标识一个数据元素 (或记录 )的关键字称为。7. 二叉排序树 (Binary Sort Tree)，又称为 ，它或者是一棵空树，或者是具 有下列性质的一棵二叉树：(1) 若左子树不空，则左子树上所有结点的值。(2) 若右子树不空，则右子树上所有结点的值。(3) 左右子树又分别是。8. 对有序表 (25,30,32,38,47,54,62,68,90,95) 用二分查找法查找 32，则所需的比较次数 为。三、问答题1输入一个正整数序列 3,45,91,25,14,76,56,65, 建立一棵二叉排序树，再从该树上删除 结点 76，请画出初始二叉排序树和删除结

35、点后的二叉排序树。2关键字序列 A=(36,27,68,33,97,40,81,24,23,90,32,14) 共 12 个数据，哈希表长为 13 ，15 采用的哈希函数为 ：h (key) = key % 13 。如果采用开放定址的线性探测再散列方法解决冲突， 请构造哈希表并求其平均查找长度。3已知一个顺序存储的有序表为 (17,25,33,37,47,53,59,65,73,77) ，试画出对应的折半查 找判定树，并求其平均查找长度。4设有一组关键字 81,25,91,24,49,56,83,66 ，采用散列函数 h(key)=key % 11 ，采用线 性探查法解决冲突， 试在 010 的散列地址空间中对该组关键字序列构造散列表，并求出在 该散列表上进行查找的平均查找长度。5设散列表 ht0.12 ，既表的大小 m=13。散列函数 h(key)=key % 13 ，采用线性探查法 解决冲突，试用关键字序列 15,21,57,7,6,18,40,27 建立散列表，并求出在该散列表上进行查 找的平均查找长度。四、程序设计题1设计一个在二叉排序树中查找指定关键字的结点的非递归算法。2编写算法， 用折半查找算法在一个有序的顺