2022年数据结构期末总复习题 .pdf

《2022年数据结构期末总复习题 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构期末总复习题 .pdf（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、学而不思则惘，思而不学则殆套题 1 一、选择题（每题2 分，共 15 题，总计 30 分）1 以下叙述中正确的是_。A 数组是数据的最小单位B 数据对象就是一组数据元素的集合C 顺序存储方式只能用于存储线形结构D 树对应到的二叉树其根结点的右子树总是空的2 一个数组的第一个元素的存储地址是100，每个元素长度为2，则第 5 个元素的存储地址是_。A 110 B 108 C 100 D 120 3 一个栈的入栈顺序是a,b,c,d,e，则其出栈顺序不可能是_。A a,b,c,d,e B e,d,c,b,a C d,c,e,a,b D d,e,c,b,a 4 栈的特点是 _。A 先进先出B 先进后

2、出C 随即存取D 链式实现5 一个队列的入队顺序是1，2，3，4，5，那么出队顺序是_。A 5，4，3，2，1 B 1，2，3，5，4 C 1，2，3，4，5 D 1，3，2，4，5 6 向一个长度为10 的数组的第5 个元素之前插入一个元素时，需向后移动_个元素。A 3 B 5 C 6 D 7 7 若一棵二叉树有101 个结点，且无度为1 的结点，则叶结点的个数为_。A 48B 49C 50D 51 8 高度为 6 的完全二叉树中第4 层结点的个数为 _。A 2B 4C 8D 16 9 具有 n 个顶点的无向完全图，其边数为_。A nB n(n-1)C n(n-1)/2D n210 具有 n

3、 个顶点的有向完全图，其边数为_。A nB n(n-1)C n(n-1)/2D n211 在有 7 个顶点的无向图中至少有_条边才能确保该图连通。A 1B 6C 7D 21 12 对于一个有n 个顶点的无向图，若采用邻接矩阵表示法，则该矩阵的大小是_。A n-1B nC (n-1)2D n213 在序列 1，10，12，15，23，40，66，77，85 中利用直接查找，查找15 所需的比较次数为_。A 2 B 3 C 4 D 6 14 采用顺序查找方法查找长度为n 的线性表时，每个元素的平均查找长度为_。AO( n)B O(nlogn)C O(n2)D O(logn) 15 在待排序元素基本

4、有序的前提下，效率最高的排序方法是_。A 插入排序B 选择排序C 快速排序D 归并排序二、填空题（每空 2 分，共 20 空，总计40 分）1 判定下列程序段的时间复杂度为_，其中语句Aij 频度为 _ for(i=0;in;i+) for(j=0;j=n;j+) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 19 页学而不思则惘，思而不学则殆 Aij=0; Bji=1; 2 对线性表进行二分查找时，要求线性表必须_且_。3 对于一个头指针为head 的带头结点的单链表，判定该链表为空的条件是_，对于一个不带头指针的单链表，判定该链表

5、为空的条件是_。4 在循环单链表中，头指针用head 表示，队尾结点用p 指向，那么pnext 等于 _。5 在选择数据结构的存储结构时，为了方便地定位和读取某特定元素，数据结构宜采用_形式，为了方便地进行数据元素的插入删除操作，数据结构宜采用_形式。6 深度为 5 的二叉树，最多有_个结点，最少有 _个结点。7 若深度为 5 的二叉树中仅有度为0 的结点和度为2 的结点，那么这棵二叉树最多有_个结点，最少有 _个结点。8 在线索二叉树中，若以 ltag 表示某结点的左标志域，以 lch 表示某结点的左孩子域，则结点 t 没有左子树的条件是。9 在含有个 8 结点的二叉链表中有_个空链域。10

6、 有_个结点的二叉树将会呈现5 种不同的表现形式。11 在无向图的邻接矩阵中，若Aij=1,Aji= _。12 如下图所示的有向图， 顶点 D 的入度为，出度为， 顶点 D 的度为。D F E C B A 三、操作题（共4 题，总计 20 分）1 已知一棵二叉树如下图所示：写出该二叉树的先根遍历序列(2 分) 写出该二叉树的中根遍历序列(2 分) 判断正误：这棵二叉树的先根、中根、后根遍历序列中，叶子结点的相对次序保持不变，其实，任意一棵二叉树，其叶子结点在先根、中根、后根遍历序列中的相对次序都保持不变。（2 分）2 下面的程序段是一个在单链表表示的有序序列a,b,d,e中插入新值c 并保持有

7、序的算法，已知插入位置的前驱用 p 指向，请将程序段补充完整。(6 分) A B C D E F p 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 19 页学而不思则惘，思而不学则殆 Status ListInsert_L(LinkList &L, char c) s=(LinkList)malloc(sizeof(LNode); ; snext=; pnext=; return OK; /ListInsert_L 3 下图为一个无向图G，请给出该图从A出发的两个可能的广度优先遍历序列(2 分) (2 分) 画出该图的邻接矩阵表示（4

8、 分）四、算法设计题（共1 题，总计 10 分）设有两个栈 S1,S2 都采用顺序栈方式，并且共享一个存储区O.maxsize-1,为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2 有关入栈和出栈的操作算法。套题 2 一、选择题（每题2 分，共 10 题，总计 20 分）1 一个数组的第一个元素的存储地址是1000，每个元素长度为4，则第 4 个元素的存储地址是_。A 1004 B 1008 C 1012 D 1016 2 一个栈的入栈顺序是a,b,c,d,e，则其出栈顺序不可能是_。A a,b,c,d,e B e,d,c,b,a C d,c,e,a,b

9、D d,e,c,b,a 3 从一个具有n 个结点的单链表中查找值等于x 的结点，在查找成功的前提下，其平均比较次数为_。A n B n/2 C (n-1)/2 D (n+1)/2 4 在序列 1，10，12，15，23，40，66，77，85 中利用直接查找，查找15 所需的比较次数为_。A 2 B 3 C 4 D 6 5 下列排序算法中不稳定的是_。A B C D E F a b d e head 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 19 页学而不思则惘，思而不学则殆A 堆排序B 折半插入排序C 直接插入排序D 链式基数排

10、序6 向一个长度为100 的数组的第 45 个元素之前插入一个元素时，需向后移动_个元素。A 45 B 46 C 55 D 56 7 若一棵二叉树有101 个结点，且无度为1 的结点，则叶结点的个数为_。A 48B 49C 50D 51 8 具有 n 个顶点的无向完全图，其边数为_。A nB n(n-1)C n(n-1)/2D n29 下列关于图的描述，错误的是_。A 无向图中所有顶点的度数之和为边数之和的2 倍B 有向图中所有顶点的度数之和为边数之和的2 倍C 有向图中所有顶点的入度之和等于出度之和D 具有 n 个顶点， n-1 条边的无向图是连通图10 有关二叉树下列说法正确的是_。A 二

11、叉树是度为2 的树B 一棵二叉树的度可以小于2 C 二叉树中至少有一个结点的度为2 D 二叉树中所有结点的度都为2 二、填空题（每空 2 分，共 12 题，总计40 分）1 判定下列程序段的时间复杂度为_，其语句频度为_ for(i=0;in;i+) for(j=0;jnext=_; p-next=s; t=p-data; p-data=_; s-data=_; 3 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是 _，需要内存容量最多的排序是_。4 对线性表进行二分查找时，要求线性表必须_。5 对于一个头指针为head 的带头结点的单链表，判定

12、该链表为空的条件是_，对于一个不带头指针的单链表，判定该链表为空的条件是_。6 数据的存储结构是指，设有一批数据元素，为了方便地定位和读取某特定元素，数据结构宜采用_形式，为了方便地进行数据元素的插入删除操作，数据结构宜采用_形式。7 已知一棵二叉树，其先序序列为ABCDE ，中序序列为CDBEA ，则其后序序列为_ 。8 高度为 6 的二叉树，其结点个数最多为_个，最少为 _个。9 在线索二叉树中，若以 ltag 表示某结点的左标志域，以 lch 表示某结点的左孩子域，则结点 t 没有左子树精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，

13、共 19 页学而不思则惘，思而不学则殆的条件是。10 在含有个 20 结点的二叉链表中有_个空链域。11 有_个结点的二叉树将会呈现5 种不同的表现形式。12 如下图所示的AOE 网，其关键路径为。D F E C B A 3 5 2 1 2 3 2 3 三、算法题（每题8 分，共 2 题，总计 16 分）1、关键字序列a,b,c ，d 的链式存储如下，编写算法，通过更改指针实现关键字序列a，d，c,b 的链式存储。2、设计算法，现有一字符串“12468” （即该变量为字符数组，每个单元存放一个char 型的值，分别为1，2，4，6，8） ，若该字符串表示的是数值型的八进制数值，即（12468）

14、8，设计算法将它转换为十进制数并输出。四、操作题（每题6 分，共 4 题，总计 24 分）1、已知一棵树如下图所示，要求：给出树的先根遍历序列和后根遍历序列（3 分）将该树转化为二叉树（3 分）2、设有一组关键字为8,7,13,10,9,23,15，哈希函数为H(key)=key MOD 7，按开放定址的线性探测再散列解决冲突，即增量序列为1，2，3，构造表地址空间为0-9 的哈希表。a b c d head A B C D E F G H I J K 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 19 页学而不思则惘，思而不学则殆请

15、画出该哈希表（3 分）0 1 2 3 4 5 6 7 8 9 计算对关键字23 进行查找时的查找长度并写出计算过程（3 分）3、下图为一个无向图G 请给出该图的邻接表表示(3 分) 依据你所作的邻接表，从A出发，给出该图的深度优先遍历序列（3 分）4、下图所示为一棵3 阶 B-树 请给出删除元素25 之后的 3 阶 B-树(3 分) 在的基础上，给出插入15 之后的 3 阶 B-树（ 3 分）A B C D E F 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 19 页学而不思则惘，思而不学则殆套题 3 一、选择题（共10 题，每题

16、2 分，共 20分） ：1、从逻辑上可以把数据结构分为（）两大类。A）动态结构、静态结构B）顺序结构、链式结构C）线性结构、非线性结构D）初等结构、构造型结构2、下面关于线性表的叙述中，错误的是哪一个？（）A）线性表采用顺序存储，必须占用一片连续的存储单元。B）线性表采用顺序存储，便于进行插入和删除操作。C）线性表采用链接存储，不必占用一片连续的存储单元。D）线性表采用链接存储，便于插入和删除操作。3、设无向图的顶点个数为n，则该图最多有（）条边。A) n-1 B) n(n-1)/2 C) n(n+1)/2 D) 0 4、对线性表进行二分查找时，要求线性表必须（）A) 以顺序方式存储 B) 以

17、顺序方式存储且元素有序C) 以链式方式存储 D) 以链式方式存储且元素有序12 1621 231082425 2820精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 19 页学而不思则惘，思而不学则殆5、下面给出的四种排序法中( )排序法是不稳定性排序法。A) 插入 B) 冒泡 C) 二路归并D) 堆6、以下说法正确的是_。A) 数据元素是数据的最小单位B) 数据项是数据的最小单位C) 数据结构是带有结构的各数据项的集合D) 数据结构是带有结构的数据元素的集合7、下列说法不正确的是（）A）图的遍历是从给定的源点出发每一个顶点仅被访问一次

18、B）遍历的基本算法有两种：深度遍历和广度遍历C）图的深度遍历不适用于有向图D）图的深度遍历是一个递归过程8、若一棵二叉树具有10 个度为 2 的结点， 5 个度为 1 的结点，则度为0 的结点个数是（）A) 9B) 11C) 15D) 不确定9、栈和队列的共同点是（）A) 都是先进先出B) 都是先进后出C) 只允许在端点处插入和删除元素D) 没有共同点10、有关二叉树下列说法正确的是（）A） 二叉树的度为2 B） 一棵二叉树的度可以小于2 C） 二叉树中至少有一个结点的度为2 D) 二叉树中任何一个结点的度都为2 二、填空题（共15 空，每空 2 分，共30 分）1、当一个 AOV网用邻接表表

19、示时，可按下列方法进行拓扑排序。1） 查邻接表中入度为_ _的顶点，并进栈；2） 若栈不空，则输出栈顶元素Vj，并退栈；查Vj 的直接后继 Vk，对 Vk 进行入度处理，处理方法是_ _ _；3） 若栈空时，输出顶点数小于图的顶点数，说明有_ _ _，否则拓扑排序完成。2、给定一组数据6，2，7，10，3，12以它构造一棵哈夫曼树，则树深度为_，带权路径长度WPL的值为 _ _ _。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 19 页学而不思则惘，思而不学则殆3、在单链表p 结点之后插入s 结点的操作是： _ _ 。4、设有一批数据

20、元素，为了最快地存取某元素，数据结构宜采用_结构，为了方便地插入一个数据元素，数据结构宜采用_结构。5、在一个无向图中，所有顶点的度数之和等于所有边数倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的倍。6、对于一个头指针为head 的带头结点的单链表，判定该表为空表的条件是_ _。7、二叉树的第i 层上最多含有结点数为。8、具有 N 个结点的二叉树，采用二叉链表存储，共有_个空链域。9、一个有 n(n0)个结点的图，最少有个连通分量，最多有个连通分量。三、算法题（共3 题，每题 5 分，共 15 分）1、 写一算法，求带有头结点的单链表的表长。2、请用非递归算法写出折半查找的算法。

21、3、请写出直接插入排序的算法。四、操作题（共6 题，第 1 题 10 分，其余每题5 分，共 35 分）1、输入一个正整数序列（53，17，12，66，58， 70，87，25，56，60） ，试完成下列各题。（1）按次序构造一棵二叉排序树BS 。(2) 依此二叉排序树，如何得到一个从大到小的有序序列？（3）画出在此二叉排序树中删除结点66 后的树结构。（10 分）2、已知一组关键字为（19，14，23，01，68，20，84，27，55，11，10，79） ，则按哈希函数H(key) = key mod 13 和链地址法处理冲突构造哈希表。（5 分）3、 对于下面的有向图G，请写出所有可能的

22、拓扑序列。（5 分）4、已知一棵二叉树前序为ABDEGCF，中序为 DBGEACF，画出这棵二叉树。 （5 分）B A C D E 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 19 页学而不思则惘，思而不学则殆5、写出对数据（15，9，7，8，20，-1，7，4）进行快速排序中第一趟的序列。（5 分）6、无向图 G=(V，E)，其中： V=a，b，c，d，e，f，E=(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)，写出对该图进行深度优先遍历的一个序列。（5 分）套题 4 一、选择题（共10 题，每

23、题 2 分，共 20分） ：1、以下属于逻辑结构的是（） 。A）顺序表B）哈希表C）有序表D）单链表2、下面关于线性表的叙述中，错误的是哪一个？（） 。A）线性表采用顺序存储，必须占用一片连续的存储单元。B）线性表采用顺序存储，便于进行插入和删除操作。C）线性表采用链接存储，不必占用一片连续的存储单元。D）线性表采用链接存储，便于插入和删除操作。3、设无向图的顶点个数为n，则该图最多有（）条边。A) n-1B) n(n-1)/2 C) n(n+1)/2 D) 0 4、线性表是具有n 个（）的有限序列（ n0） 。A) 表元素B) 字符C) 数据元素D) 数据项5、下面给出的四种排序法中( )排

24、序法是稳定性排序法。A) 希尔B) 快速C) 二路归并D) 堆6、若需在 O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（） 。A) 快速排序B) 堆排序C) 归并排序D) 直接插入排序7、下列说法不正确的是（） 。A）图的遍历是从给定的源点出发每一个顶点仅被访问一次B）遍历的基本算法有两种：深度遍历和广度遍历C）图的深度遍历不适用于有向图D）图的深度遍历是一个递归过程8、若一棵二叉树具有14 个度为 2 的结点， 5 个度为 1 的结点，则度为0 的结点个数是（） 。A) 9B) 11C) 15D) 不确定9、若某线性表最常用的操作是存取任一指定序号的元

25、素和在最后进行插入和删除运算，则利用（）存精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 19 页学而不思则惘，思而不学则殆储方式最节省时间。A) 顺序表B) 双链表C) 带头结点的双循环链表D) 单循环链表10、若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。A）(n-1)/2B) n/2 C) (n+1)/2D) n二、填空题（共15 空，每空 2 分，共30 分）1、数据的物理结构包括的表示和的表示。2、给定一组数据6 ，2，7，10，3，12 以它构造一棵哈

26、夫曼树，则树深度为_，带权路径长度WPL 的值为 _ _ _ 。3、在单链表p 结点之后删除s 结点的操作是： _ _ 。4、设有一批数据元素，为了最快地存取某元素，数据结构宜采用_结构，为了方便地插入一个数据元素，数据结构宜采用_结构。5、在拓扑排序中，拓扑序列的第一个顶点必须是_的顶点。6、对于一个头指针为head 的带头结点的单链表，判定该表为空表的条件是_ _。7、二叉树的第i 层上最多含有结点数为。8、具有 N 个结点的二叉树，采用二叉链表存储，共有_个空链域。9、一个有 n（n0）个结点的图，最少有个连通分量，最多有个连通分量。10、对于具有N个结点的完全二叉树，其深度为。11、

27、在长度为 n 的顺序表的第i 个位置上插入一个元素 （1 i n+1） ， 元素的移动次数为。三、算法题（共3 题，每题 5 分，共 15 分）1、请写一算法，求带有头结点的单向循环链表的表长。2、请用非递归算法写出在二叉树中计算叶子结点个数的算法。3、请写出简单选择排序的算法。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 19 页学而不思则惘，思而不学则殆四、操作题（共6 题，第 1 题 10 分，其余每题5 分，共 35 分）1、已知一组关键字为（19，14，23，01，68，20，84，27，55，11，10，79） ，则按哈

28、希函数H(key) = key mod 13 和链地址法处理冲突构造哈希表。（10 分）2、请写出在如下具有11 个数据元素的有序表中使用折半查找算法查找21 的过程（关键字即为数据元素的值） 。 （5 分）（05，13，19，21，37，56，64，75，80，88，92）3、对于下面的有向图G，请写出所有可能的拓扑序列。（5 分）4、写出对数据（49，38，65，97，76，13，27，49）进行快速排序中第一趟的序列。（5 分）5、无向图G=(V，E)，其中： V=a，b，c，d，e，f,E=(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)，写出对该图进

29、行广度优先遍历的序列。（5 分）6、已知一棵二叉树前序为ABDEGCF，中序为 DBGEACF，画出这棵二叉树。 （5 分）套题 5 一、选择题（每题2 分，共 10 题，总计 20 分）1以下那一个术语与数据的存储结构无关？（）A栈B. 哈希表C. 线索树D. 双向链表2对于一个头指针为head 的带头结点的单链表，判定该表为空表的条件是（）Ahead=NULL Bheadnext= headCheadnext= NULL Dhead!=NULL 3. 对于栈操作数据的原则是（） 。A. 先进先出B. 后进先出C. 后进后出D. 不分顺序A B C D E 精选学习资料 - - - - -

30、- - - - 名师归纳总结 - - - - - - -第 12 页，共 19 页学而不思则惘，思而不学则殆4若一棵二叉树具有10 个度为 2 的结点， 5 个度为 1 的结点，则度为0 的结点个数是（）A9 B11 C15 D不确定5树的后根遍历序列等同于该树对应的二叉树的( ). A. 先序序列B. 中序序列C. 后序序列D不一定6n 个结点的完全有向图含有边的数目（） 。An*n Bn（n）Cn2 Dn*（nl）7下列哪一种图的邻接矩阵是对称矩阵？（）A有向图B无向图CAOV网DAOE网8. 下面关于哈希 (Hash，杂凑 )查找的说法正确的是( ) A哈希函数构造的越复杂越好，因为这样

31、随机性好，冲突小B除留余数法是所有哈希函数中最好的C不存在特别好与坏的哈希函数，要视情况而定D若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可9下列排序算法中，其中（）是稳定的。A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序10 堆是一种有用的数据结构。试判断下面的关键码序列中哪一个是堆( ) A16，72，31，23，94，53 B94，53，31，72，16，23 C16，53，23，94，31，72 D16，31，23，94，53，72 二、填空题（每空2 分，共 20 空，总计 40 分）1 在下面的程序段

32、中， 语句 x+=1 的频度是 _， 语句 Aij=1 的频度是 _，整个程序的时间复杂度是_。for(i=0;in;i+) x+=1；for(j=0;j K ） ， 则该森林必有_ 棵树。6构造连通网最小生成树的两个典型算法是_和_。7设 G 是一个非连通无向图，共有28 条边，则该图至少有_个顶点。8若 (u, v) 是 E(G) 中的一条边，则称u 与 v 互为 _ 。9一棵具有20 个结点的完全二叉树的树高度（深度）是。10 具有 10 个叶结点的二叉树中有个度为 2 的结点。11有 3 个结点的二叉树将会呈现种不同的表现形式。12N 个顶点的连通图的生成树含有_ _条边。13具有 N

33、 个结点的二叉树，采用二叉链表存储，共有个空链域。14二叉树中某一结点左子树的深度减去右子树的深度称为该结点的。15有一个长度为12 的有序表，按二分查找法对该表进行查找，且查找每个元素的概率相同，则查找成功所需的平均查找长度为。三、算法题（每题8 分，共 2 题，总计 16分）1 关键字序列a,b,c，d 的链式存储如下，编写算法删除d 所在的结点，是删除之后的新序列为a，b，e。其中结点定义为：struct node char data; struct node * next; ; 2、请写出快速排序的算法。（5 分）对 503，87，512，61，908，170，897，275，653，

34、462，以第一个记录为枢轴，写出按升序进行一趟快速排序的结果。 （3 分）a b c d head 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 19 页学而不思则惘，思而不学则殆四、操作题（每题6 分，共 4 题，总计 24分）1、已知某栈结构定义如下，现有一字符序列以a，b，c，d的顺序进栈 ,试完成下面的操作，使最终的输出序列为a，c，b，d struct stack int base; int top; stactsize N;/*N4*/ ; main（） Init (stack); Push (a); ; ; ; Pop

35、; /* 栈顶元素 c 出栈 */ ；Push (d); Pop; /*end of main*/ 2、假设一棵二叉树的先序序列为EBADCFHGIKJ 和中序序列为ABCDEFGHIJK。请画出该二叉树。(4 分) 将此二叉树转化成其对应的森林。（2 分）3、无向图 G=(V,E), 其中： V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d) 请画出该图，并给出该图的邻接矩阵表示(4 分) 依据你所作的邻接矩阵，从A 出发，给出该图的深度优先遍历序列（2 分）得分阅卷人base top 精选学习资料 - - - - - - -

36、- - 名师归纳总结 - - - - - - -第 15 页，共 19 页学而不思则惘，思而不学则殆4、将关键码DEC, FEB, NOV, OCT, JUL, SEP, AUG, APR, MAR, MAY, JUN, JAN 依次插入到一棵初始为空的AVL树中，画出每插入一个关键码后的AVL树。 （6 分）套题 6 一、选择题（共10 题，每题 2 分，共 20 分）1、对 N 个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) 。A、 （N+1 ）/2 B、N/2 C、N D、（1+N）*N /2 2、若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一

37、个新元素的算法的时间复杂度为（）(1=inext&jnext) |ji-1) return ERROR; （2）; p-next = q-next; e=q-data; free(q); return OK; 2、以下程序的功能是在一有序表ST中折半查找其关键字等于key 的数据元素。若找到，则函数值为该元素中的位置，否则为0,请在画线部分填上代码。 （5 分）int Search_Bin(SSTable ST,KeyType key) /* 在有序表 ST中折半查找其关键字等于key 的数据元素。若找到，则函数值为*/ /* 该元素在表中的位置，否则为0。*/ int low,high,mi

38、d; low=1; /* 置区间初值*/ high=ST.length; while(low=high) (1) ; if EQ(key,ST.elemmid.key) /* 找到待查元素*/ return mid; else if LT(key,ST.elemmid.key) (2) ; /* 继续在前半区间进行查找*/ else low=mid+1; /* 继续在后半区间进行查找*/ return 0; /* 顺序表中不存在待查元素*/ 3、请用递归算法写出二叉树的先序遍历算法。（5 分）4、写一算法，求带有头结点的单链表的表长。（5 分）精选学习资料 - - - - - - - - -

39、名师归纳总结 - - - - - - -第 18 页，共 19 页学而不思则惘，思而不学则殆五、操作题1、设一棵二叉树的前序序列为ABDGECFH ，中序序列为：DGBEAFHC 。（1）试画出该二叉树。（2）写出该二叉树的后序遍历序列。（3）说明由二叉树的中序遍历序列和后序遍历序列是否可唯一地确定出该二叉树？（4）说明由二叉树的前序遍历和后序遍历结果能否唯一确定一棵二叉树？（10 分）2、依次输入表 (30，15，28，20，24，10，12，68，35，50，46，55)中的元素，生成一棵二叉排序树。(1) 试画出生成之后的二叉排序树；(2) 对该二叉排序树作中序遍历，试写出遍历序列；(3

40、) 假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。（10 分）3、 写出对数据（ 49，38，65，97，76，13，27，49）进行快速排序中第一趟的序列。（5 分）4、无向图 G=(V，E)，其中： V=a，b，c，d，e，f，E=(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)，写出对该图进行广度优先遍历的序列。（5 分）5、二叉树结点数值采用顺序存储结构，如下图所示：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 e a f d g c j h i b 1)画出上述顺序存储结构所对应

41、的二叉树表示形式；2)写出前序遍历、中序遍历和后序遍历的结果；3)写出结点 C的双亲结点、其左、右孩子分别是什么；若此树是由森林转换而成的二叉树，请将此二叉树还原成森林。6、关键字序列 a,b,c,d,e,f,g,h在某段文字中出现的频率分别是0.03 ，0.20 ，0.01 ，0.05 ，0.34 ，0.04 ，0.23 ，0.10 。要求：(1) 画出赫夫曼树； （3 分）(2) 依据你所做的赫夫曼树，约定左分支表示字符1 ，右分支表示字符0 ，写出它的赫夫曼编码。 （3分）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 19 页