数据结构题库讲解

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

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

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

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

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

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

7、少说出两条好处） 2在单链表、双链表中，如果仅知道指针p 指向某结点，不知道头指针，能否将结点*p 从相应的链表中删去？ 3如果频繁地对一个线性表进行插入和删除操作，那么该线性表应该采用何种存储结构？为什么？四、程序设计题1有一个带头结点的单链表（不同结点的数据域值可能相同），其头指针为 head，编写一个函数计算数据域值为 x 的结点个数。2设计一个算法，删除一个递增的单链表（允许出现值域重复的结点）中多余的元素 值相同的结点 。3. 设计一个删除单链表 L中值为 m的结点的直接前驱结点操作的算法。 4设计一个算法，将一个不带头结点的单链表L（至少有一个结点）逆置，即最后一个结点变成第一个结

8、点，原来倒数第二个结点变成第二个结点，如此等等。5在一个带头结点的单链表中，头指针为head，它的数据域的类型为整型，而且按由小到大的顺序排列，编写一个算法 insertx list （），在该链表中插人值为 x 的元素，并 使该链表仍然有序。习题三、选择题l 一个栈的序列是： a， b，c，d，e，则栈的不可能输出的序列是（） 。A a，b，c，d，e B d，e，c， b，a C d，c，e， a，b D e，d，c，b，a 2判定一个栈 S（最多元素为 MaxSize ）为栈满的条件是： （ ）A S top!= -1B S top=-1CS top=MaxSize-1DS top!=M

9、axSize-13若一进栈序列为 1，2，3，n，其出栈序列为 P1,P2,P3,Pn，如果 Pn=n, 则 Pi （1 inext=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 的值分别是（） ：A 3 和 5B 5 和 3C2和 6D6和 26判断一个循环队列A Q-front=Q-rear BC Q-front!=Q-rear 7向一个带头结点、栈顶

10、指针为 （ ）。A top-next=S ；C S-next=top-next 8在一个链队列中，假定 的操作是（ ）。A front front-nextC rear-next=S ； rear=S9栈与队列都是（）。A 链式存储的线性结构 C 限制存取点的线性结构 10若进栈序列为 l ，2， 3，4，则（Q(最多元素为 MaxSize )为空的条件 Q-front= ( Q-rear +1 ) D Q-front!= ( Q-rear +1 top 的链栈中插人一个B； top-next=S ；front 和 rearBDBD是： （ ）%MaxSize） %MaxSize*S 结点的时

11、候，应当执行语句A 3，2，4，1 B l，2，3， S-next=top ； top=S ；D S-next=top ；top=S-next ； 分别为头指针和尾指针，则插入一个结点 *S S-next=rear ； rear=S S-next=front ； front S链式存储的非线性结构限制存取点的非线性结构）不可能是一个出栈序列。4，2， 3，1 D 4，3，2，l该缓冲区4 C11在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区， 主机将要输出的数据依次写人该缓冲区， 而打印机则从该缓冲区中取走数据打印。 应该是一个（ ）结构。A 堆栈 B 队列 C 数组

12、D 线性表 二、填空题1 栈和队列的共同点是2通常元素进栈的操作是3栈（ stack ）是限定在 一端进行插人或删除操作的线性表。在栈中，允许插人和删除操作的一端称为 ，而另一端称为 。不含元素的栈称为 4队列（ Queue）也是一种 ，但它与栈不同，队列中所有的插人均限定在表的一端进行，而所有的删除则限定在表的另一端进行。允许插人的一端称为 ，允许删除的一端称为 。5队列中允许进行删除的一端称为 ；允许进行插入的一端称为 。三、问答题1设有一个数列的输入顺序为 abcdef ，若采用栈结构，并以 I 和 O分别表示进栈和出栈操 作，试问下列输出序列是否是合法序列？如是，请用进栈和出栈操作表示

13、其合法序列。（ 1）能否得到输出顺序为 cbefda 的序列？（ 2）能否得到输出顺序为 aedfbc154623 的序列？2设输入元素为 4、5、6、B、A，入栈次序为 456BA，元素经过栈后到达输出序列，当所有 元素均到达输出序列后，有哪些序列可以作为高级语言的变量名？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

14、进栈，给出它们所有可能的出栈秩序。四、程序设计题 1假设表达式中有三种括号：圆括号“ （）”、方括号“ ”和花括号“ ”用 C语言 编写程序判断读人的表达式中不同括号是否正确配对，假定读人的表达式以”#”结束。习题四、选择项4设有两个串求串S2在 S1，那么求串 S2在 S1求串 n 在串 m中首次出现的位置的运算称为：( )A求子串B求串长C模式匹配 D 串连接4设有串 S=Computer ，则其子串的数目是(A36B 37 C 84下列是 C 语言中“ ASDF567HJK”L 子串的是：(D“ DFHJ”)。9A ASDF B DF56 C“F567HJ” 5空串与空格串(A 相同 B

15、)。不相同 C可能相同无法确定二、境空题1串是由零个或多个字符组成的 。通常记作： s“ c1，c2，cn”(n=0) ，其中， S称为 ；串中的 Ci(1=i1）个 的有序组合，数组中的数据是按顺序存储在一块 的存储单元中。2数组中的每一个数据通常称为 ，用下标区分， 其中下标的个数由数组的决定。3广义表是 n（ n=0）个元素的序列。记作： A（a1，a2，an），其中， A是广义 表的 ， n 是它的 ，当 n=0 的时候称为 。4广义表的深度一般定义为广义表元素 ，或者说是广义表 。利用递归的定义，广义表的深度就是所有子表中 。三、问答题1现有一个稀疏矩阵如下图所示，写出其对应的三元组

16、表示，并求出其转置矩阵的三元组表示。02000030100400002写一个创建稀疏矩阵相应三元组的算法。四、程序设计题1假设三元组元素值为整型，写一个查找三元组元素值为n 的算法。习题六一、选择题1设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含节点数至少 有：（ ）A2h B2h+1 C h+1 D 2h-12现有一二叉树，若其先序遍历序列为ABCDE，中序遍历序列为 CBDAE，那么其后序遍历序列为：（ ）ABDAEC B EDCBA C DABEC D CDBEA3在线索化二叉树中， t 所指结点没有左子树的充要条件是： （ ）A t-left=NULLB

17、 t-left=0C t-ltag=1D t-left=NULL 且 t-ltag=14设深度为 h 的二叉树上只有叶子结点和同时具有左右子树的结点，则此类二叉树中所包含的结点数目至少为（）。A 2hB2hC 2h1D2h-l5二叉村第 k 层上最多有（）个结点。A 2kB2k-1Ck 2k-1D2k-16二叉树的深度为 k ，则二叉树最多有（）个结点。A 2kB2k-1Ck-1 2k-1D2k -17（设某一二叉树先序遍历为）。abdec，中序遍历为dbeac ，则该二叉树后序遍历的顺序是（）。A abdec B debacC debcaD abedc8设某一二叉树中序遍历为badce，后序

18、遍历为bdeca ，则该三叉树先序遍历的顺序是（）。A adbecBdecabC debacD abode9N个结点的线索二叉树中，线索的数目是（）。A N-1 BN1C 2N D 2N110将一棵树 T 转换为一棵二叉树 T2，则 T的先序遍历是 T2 的（）。A先序B中序C后序 D无法确定11将一棵树 T 转换为一棵二叉树 T2，则 T的后序遍历是 T2 的（）。A先序B中序C后序 D无法碉定12设一棵二叉树度 2 的结点数是 7，度为 1 的结点数是 6，则叶子结点数是（）A 6B7C 8 D913一棵非空的二叉树，先序遍历与后序遍历正好相反，则该二叉树满足（）。A 无左孩子B无右孩子C

19、只有一个叶子结点D 任意二叉树14线索二叉树是一种（）。A 逻辑结构B线性结构C 逻辑和线性结构 D 物理结构15 权值为 l ， 2，6，8的四个结点构成的哈夫曼树的带权路径长度是（）。A 29 B 31 C 17D20二、填空题1 树 （Tree） 是 n（n 0） 个结点的 集。2 深度为 5 的二叉树至多有 个结点。3树中任意结点允许有零个或多个孩子结点， 除根结点以外 , 其余结点 双 亲结点。4在一棵二叉树中，度为零的结点个数为n0 ，度为 2 的结点个数为 n2, 那么n0= 。5 结点的度是指结点所拥有的 。6 一个结点的子树中的任一结点都称为该结点的 。7 从根到该结点所经分

20、支上的所有结点称为该结点的 。8 具有 的结点互称为兄弟结点，简称为兄弟。9从根结点开始定义，根为 层，根的孩子为 层，依次往下类推，若某结点在第 k 层，则其子树的根就在 层。10 如果树中各结点的各子树无排列顺序， 即可以互换位置， 则称为该树为 。11 二又树( Binary Tree )是结点的有限集合，这个集合或者是空，或者是由一个根 结点和 的称为 和 的二叉树构成。12 二叉树第 i 层上最多有 个结点。13 深度为 k 的二又树最多有 个结点 (k l) 。14 在任意二叉树中，叶子结点的数目( 即度为 0 的结点数 ) 等于度为 2 的结点数15 一棵深度为 k 且具有 2k

21、-1 个结点的二叉树称为 。这类二叉树的特点是，二叉树中每一层结点的个数都是 的个数。16 是那种在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者所缺少的结点都在右边。17 具有 n 个结点的完全二叉树的深度是 。18 先序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作： 访问二叉树 ；先序遍历二叉树 ；先序遍历二叉树 。19 中序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作： 中序遍历二叉树 ；访问二又树 ；中序遍历二又树 。20 后序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作： 后序遍历二叉树 ；

22、后序遍历二叉树 ；访问二叉树 。21 线索二叉树( Threaded Binary Tree )是充分利用二义链表的 n+1 个空的指针域 作为线索来标志每一个结点的 和 信息。 当某个结点有左孩子的时候， 使其 指向其左孩子，无左孩子的时候，使其左指针域指向该结点的 ；当某个结点有有孩子的时候， 使其右指针域指向该结点的 ，无右孩子的时候， 使其有指针域指向该结点的 。22 线索二叉树的线索链表中，指向结点前驱和后继的指针称为 ；加上线索的二叉树称为 ；对二叉树以某种次序进行遍历使其成为线索二叉树的过程称为 。23 哈夫曼树( Huffman Tree )又称 。它是 n 个带权叶子结点构成

23、的所有二叉树中，带权路径长度 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为结点集合， R 为边的集合。请根据以上内容回答以下问题：- 10 -(1) 画出这棵树。(2) 该树的根结点是哪一个？(3) 哪些是叶子结点？(4) F 结点的双亲是谁？(5) F 结点的祖先是哪些？(6) F 结点的孩子是哪些？(7) F 结点的兄弟是哪些？(8) F 结点的堂兄弟是哪些？(9) F

24、 结点的度是多少？(10) F 结点的层次是多少？(11) D 结点的子孙有哪些？(12) 以结点 D为根的子树度是多少？(13) 以结点 D为根的子树层是多少？(14) 该树的层是多少？(15) 该树的度是多少？2画出图 6-1 中树的二叉树表示形式。( a)( b)(c)图 6-l3已知某二叉树的先序遍历的结果是：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 ，构建哈夫曼树

25、 (请 按左子树根结点的权小于等于右子树根结点的权的次序构造) ，计算出带权路径长度 WPL， 并设计每个字母的哈夫曼编码5假设一棵二叉树的后序序列为 DCEGBFHKJI，A 中序序列为 DCBGEAHFIJ，K请完成下列 操作：(1)画出该二叉树； (2) 写出该二叉树的先序遍历序列； ( 3)画出该二叉树的中序遍 历线索二叉树。6假设一棵二叉树的先序序列为 ABDGCEHLIKMF，J中序序列为 GDBALHEKIMCF，J请完成 下列操作。(1) 画出该二叉树；(2) 写出该二叉树的后序遍历序列；(3) 画出该二叉树的中序遍历线索二叉树。7假设通讯电文中只用到 A，B，C，D，E，F

26、六个字母，它们在电文中出现的相对频率 分别为： 7，2，15，9，4，19，要求画出哈夫曼树(请按左子树根结点的权小于等于右子树 根结点的权的次序构造) ，并计算出带权路径长度 WPL，试设计每个字母的哈夫曼编码。8有七个带权结点 , 其权值分别为 2,6,7,1,5,9,13, 试以它们为叶子结点构造一棵哈夫- 11 - 曼树（请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造） , 并计 算出带权路径长度 WPL。9假设一棵哈夫曼树共有 n0 个叶子结点，试证明树中共有 2no-l 个结点。10假设通信用的报文由 9 个字母 A、B、C、D、E、F、G、H和 I 构成，它们

27、出现的频 率分别是： 10、20、5、15、8、2、3、7和 30。请用这 9个字母出现得频率作为权值求：（l ）设计一棵哈夫曼树。（ 2）计算其带权路径长度 WPL值。（3）写出每个字符的哈夫曼编码。四、程序设计题1. 自己设计一棵二叉树，编写一个完整的程序，输出该二叉树的先序、中序和后序序 列。（程序中应包括二叉树的生成函数，先序、中序、后序遍历函数） 。2已知一棵二叉树的先序遍历序列和中序遍历序列，请写出根据二又树先序遍历序列 和中序遍历序列构造一棵二叉树的算法。- 12 -习题七、选择题1 在一个无向图 G 中，所有顶点的度数之和等于所有边数之和的( )倍。A l/2B 12对某个无向

28、图的邻接矩阵来说： A第 i 行上的非零元素的个数和第C 2D4()i 列上的非零元素的个数一定相等B矩阵中的非零元素的个数等于图中的边数C第 i 行上、第 i 列上非零元素的总数等于顶点 Vi 的度数 D矩阵中非全零行的行数等于图中的顶点数 3采用邻接表存储的图的深度优先遍历算法类似于二叉树的：( )A先序遍历 B 中序遍历 C 后序遍历 D 按层遍历4在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要条边： ( )An-1BnC n+1Dn/25在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的()倍。Al/2B 1 C 2D 46一个具有n 个顶点的无向图包含()条边。An

29、B n 1C n-1 Dn/27一个具有n 个顶点的无向完全图包含()条边。An(n-l)B n(n+l) C n(n-l)/2Dn(n-l)/28.一个具有n 个顶点的有向完全图包含()条边。An(n-1)B n(n+l) C n(n-l)/2Dn(n+l)/29无向图的邻接矩阵是一个( )。A对称矩阵 B 零矩阵 C 上三角矩阵D对角矩阵二、填空题1在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种 的关系。2在有 n 个顶点的有向图中，至多有条边。3具有 10 个顶点的无向图，边的总数最多为。4在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要 条边。5 具有

30、n (n-1)/2 条边的无向图称为 ，简称为 ，其中 n 表示无向图中顶点的个数， n(n-1)/2 是具有 n 个顶点无向图所拥有边的 。6 具有 n 个顶点的有向图，如果它同时具有 n(n-1) 条弧，则称该图为 ，其中 n(n-1) 是具有 n 个顶点有向图所拥有弧的 。7 如果图中的边或弧带有权，则称这种图为 。8顶点 v 的度定义为 的数目，记为 D(v) 。9 在有向图中，顶点 v 的度又分为 和，是以顶点v 为头的弧的数目，或者说是以该顶点为终点的边的数目，记为 ID(v) ； 是以顶点 v 为尾的弧的数目，或者说是以顶点为起点的边的数目，记为OD(v) ；顶点 v 的度是它的

31、 和之和，即 D(v)=ID(v) OD(v)。10 是指一条路径上所经过的边或弧的数目。11 若一条路径上除开始结点和结束结点外 ( 开始结点和结束结点也可以为不同顶点)- 13 -其余顶点均不相同，则称该路径为 。12 若一条路径上的开始结点和结束结点为同一个顶点，则称该路径为 。同时除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称 或 。13 一个 称为有向无环图，简称为 DAG图。三、问答题或0 出发分别进1 已知一个无向图的邻接矩阵如图所示， 请画出该无向图， 并写出从顶点 行深度优先和广度优先搜索遍历得到的顶点序列。一个无向图 G- 14 -2依据以下无向图，使用普里姆

32、算法，写出构造该图的最小生成树的过程。习题九一、选择题1. 顺序查找方法适合于存储结构为(A. 散列存储B.C.散列存储或索引存储)的线性表索引存储D. 顺序存储或链接存储2采用折半查找法查找长度为n 的线性表时，每个元素的平均查找长度为：A O(n2) B O(n log2n)C O(n)D O(log2n)3对线性表进行折半查找时要求线性表必须：(A以顺序方式存储 B 以顺序方式存储，且结点按关键字有序排序C以链式方式存储 D以链式方式存储，且结点按关键字有序排序4可以在哈希查找过程中处理冲突的方法是：()A关键字比较法 B 线性探查法 C数字分析法D除留余数法 5. 己知一个有序表为 (

33、11,22,33,44,55,66,77, 88,99), 则折半查找元素 55 需要比较 ( ) 次。A.1 B.2 C.3 D.46. 顺序查找法与二分查找法对存储结构的要求是 ( ) 。A. 顺序查找与二分查找均只是适用于顺序表B. 顺序查找与二分查找均既适用于顺序表 , 也适用于链表C. 顺序查找只是适用于顺序表D. 二分查找适用于顺序表二、填空题1. 折半查找 ( Binary Search) 又称为 ， 是一种效率较高的一种查找算法 。2. 分块查找 (Blocking Search) 又称为 ，是一种以 的形式来来进 行的查找方法。分块查找是 的一种改进，它是一种介于 和折半查找

34、之 间的查找方法。3. 如果对查找表只进行查询某个 特定的数据元素是否在查找表中 , 以及查找某 特 定的 数据元素的各种属性两种类型的基本操作, 而不进行插入和删除数据元素的查找表称为。4. 如果在查找表中进行查找的过程中，同时插入查找表中不存在的数据元素，或者查 找表中删除已存在的某个数据元素，则称此类查找表为 。5. 用折半法查找一个线性表时，该线性表必须具有的特点是 。6. 在 一 个 查 找 表 中 ， 能 够 惟 一 的 标 识 一 个 数 据 元 素 ( 或 记 录 ) 的 关 键 字 称 为。7. 二叉排序树 (Binary Sort Tree) ，又称为 ，它或者是一棵空树，

35、或者是 具有下列性质的一棵二叉树：(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，请画出初始二叉排序树和删除结点后的二叉排序树。2关键字序列 A=(36,27,68,33,97,40,81,24,23,90,32,14) 共 12 个数据，哈希表长为- 15 - 13，采用的哈

36、希函数为： 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

37、% 13 ，采用线性探 查法解决冲突，试用关键字序列 15,21,57,7,6,18,40,27 建立散列表，并求出在该散列表 上进行查找的平均查找长度。四、程序设计题1设计一个算法，实现在二叉排序树中查找指定关键字的结点的非递归操作。2编写算法， 用折半查找算法在一个有序的顺序表中插入x 结点， 并保持结点的有序性。3. 写出二叉排序树的插入结点的递归算法，并利用插入算法写出建立一个有 n 个结点 的二叉排序树算法。- 16 -习题十、选择题1 在所有的排序方法中，关键字比较的次数与记录初始排列秩序无关的是（）A 冒泡排序C直接选择排序B 希尔排序D 直接插人排序2 一组记录的排序码（立的初

38、始堆为： （ ）A79,46,56,38,40,80C84,79,56,46,40,3846,79,56,38,40,84 ），则利用堆排序（建立大根堆）的方法建B84,79,56,38,40,46D84,56,79,40,46,383设有 5000 个无序的元素，希望用最快的速度挑选出其中前10 个最大的元素，最好选用：（ ）A基数排序 B 快速排序 C堆排序D冒泡排序4从未排序序列中依次取出元素与已经排好序的序列中的元素作比较，将其放入已排 序序列的正确位置上，此方法称为（） 。A 插人排序 B 选择排序C交换排序D 归并排序5 依次将每两个相邻的有序表合并成一个有序表的排序方法称为（）A插人排序B交换排序C选择排序D归并排序6 当两个元素出现逆序的时候就交换位置，这种排序方法称为（）A插人排序B交换排序C选择排序D归并排序7 在正常情况下，直接插人排序的时间复杂度为（） 。AO（log 2n）B O（n）2CO（n log 2n）