第6章查找树of北京联合大学数据结构

北航数据结构试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构通常使用什么数据结构来实现？A. 链表B. 栈C. 数组D. 树答案：C2. 下列关于二叉树的描述中，错误的是：A. 二叉树的第i层最多有2^(i-1)个节点B. 任意非空二叉树的叶子节点数等于度为2的节点数加1C. 任意非空二叉树的叶子节点数等于度为2的节点数减1D. 任意非空二叉树的叶子节点数等于度为2的节点数答案：C3. 在图的遍历算法中，深度优先搜索（DFS）使用的数据结构是：A. 队列B. 栈C. 链表D. 数组答案：B4. 哈希表的冲突解决方法不包括以下哪种？A. 开放定址法B. 链地址法C. 再散列法D. 排序法答案：D5. 快速排序算法的时间复杂度最坏情况下为：A. O(nlogn)B. O(n^2)C. O(n)D. O(1)答案：B6. 以下排序算法中，时间复杂度为O(nlogn)的是：A. 冒泡排序B. 快速排序C. 选择排序D. 插入排序答案：B7. 以下关于堆的描述中，正确的是：A. 堆是一种特殊的二叉树B. 堆是一种完全二叉树C. 堆是一种平衡二叉树D. 堆是一种链表答案：A8. 在一个长度为n的有序数组中查找一个元素，使用二分查找算法的时间复杂度是：A. O(n)B. O(nlogn)C. O(logn)D. O(1)答案：C9. 以下算法中，不属于动态数据结构的是：A. 链表B. 栈C. 数组D. 哈希表答案：C10. 以下关于图的描述中，错误的是：A. 图是由顶点和边组成的B. 图的顶点可以有0个或多个C. 图的边可以有向或无向D. 图的顶点数一定大于边数答案：D二、多项选择题（每题3分，共15分）1. 下列哪些是线性表的存储结构？A. 顺序存储B. 链式存储C. 索引存储D. 散列存储答案：A, B2. 在图的表示方法中，以下哪些是正确的？A. 邻接矩阵B. 邻接表C. 边表D. 顶点表答案：A, B, C3. 下列哪些排序算法是稳定的？A. 冒泡排序B. 快速排序C. 插入排序D. 选择排序答案：A, C4. 在数据结构中，以下哪些是递归算法的特点？A. 问题可以分解为更小的子问题B. 每个子问题都是原问题的实例C. 存在递归终止条件D. 递归算法的时间复杂度一定比迭代算法高答案：A, B, C5. 在使用链表实现栈时，以下哪些操作是合法的？A. pushB. popC. peekD. clear答案：A, B, C三、简答题（每题5分，共30分）1. 请简述什么是递归，并给出一个递归算法的例子。

基于C语言的数据结构教学技巧范莉丽;彭涛【摘要】Necessity and significance of studying data structure is described in this paper,and the common problem in the process of data structure teaching is pointed out;an attempt of research and exploration on the teaching mode of data structure based on C language teaching mode is made,and some practical teaching skills are proposed to enhance the student＇s subjective initiative and improve the teaching effect.%阐述学好数据结构的必要性和重要性;指出在数据结构教学过程普遍存在的问题;探索基于C 语言的数据结构教学模式,提出一些实用的教学技巧,旨在提高学生主观能动性,提高教学效果。

【期刊名称】《计算机教育》【年(卷),期】2011(000)018【总页数】4页(P61-64)【关键词】数据结构;教学模式;主观能动性;教学效果【作者】范莉丽;彭涛【作者单位】北京联合大学信息学院,北京100101;北京联合大学信息学院,北京100101【正文语种】中文【中图分类】G642数据结构在计算机学科中有着重要的地位，起着承上启下的作用。

通过对数据结构的学习可以锻炼学生的逻辑思维能力，提出问题、分析问题和解决问题的能力，为学好后继课程打下坚实的基础[1]。

因为数据结构知识点繁多，理论抽象难以理解，使得数据结构在一开始就被披上了冷冰冰的晦涩难懂，拒学生以千里之外的面纱，神秘却使人失去一探究竟的兴趣和勇气。

第九章查找：习题习题一、选择题1．散列表查找中k个关键字具有同一散列值，若用线性探测法将这k个关键字对应的记录存入散列表中，至少要进行( )次探测。

A. k B。

k+l C. k(k+l）／2 D. l+k （k+l)/22．下述命题( )是不成立的。

A。

m阶B-树中的每一个结点的子树个数都小于或等于mB。

m阶B-树中的每一个结点的子树个数都大于或等于『m/2-1C。

m阶B-树中的每一个结点的子树高度都相等D。

m阶B—树具有k个子树的非叶子结点含有(k-l）个关键字3．如果要求一个基本线性表既能较快地查找，又能适应动态变化的要求，可以采用( ）查找方法.A。

分块 B. 顺序 C. 二分 D.散列4．设有100个元素，用折半查找法进行查找时，最大比较次数是( ),最小比较次数是( ）.A。

7，1 B.6，l C.5，1 D. 8，15．散列表长m=15，散列表函数H(key）=key％13。

表中已有4个结点：addr（18)=5；addr(32）=6; addr(59)=7；addr(73)=8;其余地址为空，如果用二次探测再散列处理冲突，关键字为109的结点的地址是( )。

A. 8 B。

3 C. 5 D。

46．用分块查找时，若线性表中共有729个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分( )个结点最佳。

A。

15 B. 27 C。

25 D。

307．散列函数有一个共同性质，即函数值应当以( )取其值域的每个值。

A.同等概率B。

最大概率C。

最小概率D。

平均概率8．设散列地址空间为O.。

m—1，k为关键字，假定散列函数为h(k)=k％p，为了减少冲突，一般应取p为( )。

A.小于m的最大奇数B. 小于m的最大素数C.小于m的最大偶数D.小于m的最大合数9．当向一棵m阶的B-树做插入操作时，若使一个结点中的关键字个数等于( )，则必须分裂成两个结点。

A。

m B。

m-l C.m+l D。

第六章习题1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。

3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，则该树中有多少个叶子结点并证明之。

4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。

5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？6．给出满足下列条件的所有二叉树：①前序和后序相同②中序和后序相同③前序和后序相同7． n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child 域有多少个？8．画出与下列已知序列对应的树Ｔ：树的先根次序访问序列为GFKDAIEBCHJ；树的后根次序访问序列为DIAEKFCJHBG。

9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10请为这8个字母设计哈夫曼编码。

10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点指针,是否可不用递归且不用栈来完成?请简述原因.11. 画出和下列树对应的二叉树：12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。

13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。

14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。

在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。

15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。

16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。

17．对以孩子-兄弟链表表示的树编写计算树的深度的算法。

18．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。

第1 章绪论课后习题讲解1. 填空⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

【解答】数据元素⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。

【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。

【解答】集合，线性结构，树结构，图结构⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。

【解答】自然语言，程序设计语言，流程图，伪代码，伪代码⑺在一般情况下，一个算法的时间复杂度是（）的函数。

【解答】问题规模⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。

【解答】Ο(1)，Ο(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

2. 选择题⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

A 线性结构B 非线性结构C 存储位置D 指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

则表示该遗产继承关系的最合适的数据结构应该是（）。

第一章绪论1、数据结构就是计算机中存储、组织数据的方式。

精心选择的数据结构可以带来最优效率的算法。

2、程序设计= 算法+数据结构3、解决问题方法的效率:●跟数据的组织方式有关●跟空间的利用效率有关●跟算法的巧妙程度有关4、数据:所有能输入到计算机中,且被计算机处理的符号的集合,就是计算机操作对象的总称;就是计算机处理的信息的某种特定的符号表示形式。

5、数据元素:数据中的一个“个体”,数据结构中讨论的基本单位。

相当于“记录”,在计算机程序中通常作为一个整体考虑与处理。

6、数据项: 相当于记录的“域”, 就是数据的不可分割的最小单位,如学号。

数据元素就是数据项的集合。

7、数据对象:性质相同的数据元素的集合、例如: 所有运动员的记录集合8、数据结构:就是相互间存在某种关系的数据元素集合。

9、数据结构就是带结构的数据元素的集合。

10、不同的关系构成不同的结构。

11、次序关系:{<ai,ai+1>|i=1,2,3,4,5,6}12、对每种数据结构,主要讨论如下两方面的问题:1) 数据的逻辑结构,数据结构的基本操作;2) 数据的存储结构,数据结构基本操作的实现;13、数据的逻辑结构:数据之间的结构关系,就是具体关系的抽象。

数据结构的基本操作:指对数据结构的加工处理。

14、数据的存储结构(物理结构):数据结构在计算机内存中的表示。

数据结构基本操作的实现:基本操作在计算机上的实现(方法)。

15、数据结构的有关概念16、数据元素的4类的基本结构:○1集合;○2线性结构:结构中数据元素之间存在一对一的关系;○3树形结构:结构中数据元素之间存在一对多的关系;○4图状结构或网状结构:结构中数据元素之间存在多对多的关系。

17、C语言的优点:C语言可以直接操作内存。

18、每个节点都由两部分组成:数据域与指针域。

19、链接存储结构特点:●比顺序存储结构的存储密度小(每个节点都由数据域与指针域组成)。

●逻辑上相邻的节点物理上不必相邻。

第6章 树和二叉树（参考答案）6.1(1)根结点a6.2三个结点的树的形态： 三个结点的二叉树的形态：（1） （1） （2） （4） （5）6．3 设树的结点数是n ，则n=n0+n1+n2+……+nm+ (1)设树的分支数为B ，有n=B+1n=1n1+2n2+……+mnm+1 (2)由（1）和（2）有：n0=n2+2n3+……+(m-1)nm+16.4(1) k i-1 (i 为层数)(2) (n-2)/k+1(3) (n-1)*k+i+1(4) (n-1)%k !=0; 其右兄弟的编号 n+16.5（1）顺序存储结构注：#为空结点6.6(1) 前序 ABDGCEFH(2) 中序 DGBAECHF(3) 后序 GDBEHFCA6.7(1) 空二叉树或任何结点均无左子树的非空二叉树(2) 空二叉树或任何结点均无右子树的非空二叉树(3) 空二叉树或只有根结点的二叉树6.8int height(bitree bt)// bt是以二叉链表为存储结构的二叉树，本算法求二叉树bt的高度{ int bl,br; // 局部变量，分别表示二叉树左、右子树的高度if (bt==null) return(0);else { bl=height(bt->lchild);br=height(bt->rchild);return(bl>br? bl+1: br+1); // 左右子树高度的大者加1（根） }}// 算法结束6.9void preorder(cbt[],int n,int i);// cbt是以完全二叉树形式存储的n个结点的二叉树，i是数// 组下标，初始调用时为1。

本算法以非递归形式前序遍历该二叉树{ int i=1,s[],top=0; // s是栈，栈中元素是二叉树结点在cbt中的序号 // top是栈顶指针，栈空时top=0if (n<=0) { printf(“输入错误”);exit（0）；}while (i<=n ||top>0){ while(i<=n){visit(cbt[i]); // 访问根结点if (2*i+1<=n) s[++top]=2*i+1; //若右子树非空，其编号进栈i=2*i;// 先序访问左子树}if (top>0) i=s[top--]; // 退栈，先序访问右子树} // END OF while (i<=n ||top>0)}// 算法结束//以下是非完全二叉树顺序存储时的递归遍历算法，“虚结点”用‘*’表示void preorder(bt[],int n,int i);// bt是以完全二叉树形式存储的一维数组，n是数组元素个数。

数据结构_中国人民解放军陆军工程大学中国大学mooc课后章节答案期末考试题库2023年1.若检索树中序序列是从小到大的序列，下列说法正确的是。

答案:检索树中，每个结点的关键字都比其左子树中所有结点关键字大或相等，比其右子树中所有结点关键字小2.如图所示检索树，其成功平均查找长度为____。

答案:2.93.由输入序列46，70，25，15，28，10，36，78，55所构造的检索树，在此树上插入结点30和32后，它的先序序列是___________。

答案:46，25，15，10，28，36，30，32，70，55，784.具有5层结点的AVL树至少有个结点。

答案:125.将结点13，24，37，90，53插入开始为空的平衡树，其先序遍历序列为。

答案:24，13，53，37，906.根据哈夫曼编码，字母ABCDE的不等长编码不可能是_____。

答案:100，11，10，1，07.排序的时间复杂度不受数据初始状态影响而恒为O(nlogn)的是（）。

答案:8.一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（）。

答案:希尔排序9.利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（）。

答案:O(n^2)10.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序排序的第一趟冒泡排序结束后的结果是（）。

答案:H，C，Q，P，A，M，S，R，D，F，X，Y11.下面给出的四种排序法中，（）排序是不稳定排序法。

答案:12.一组记录的关键字为{25，50，15，35，80，85，20，40，36，70}，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果为（）。

答案:15,25,35,50,20,40,80,85,36,7013.对初始状态为递增序列的表按递增顺序排序，最省时间的是（）算法。

答案:直接插入排序14.对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-1，4，8，20，9，7}则该次采用的增量是 ( ) 。

第七章树PROBLEM 2(1/1 分)一个深度为h的满k叉树，最多有多少个结点？（独根树深度为0）There is a full k-ary tree, whose depth is h. How many nodes can it have at most? (The depth of a tree, which only has a root node, is 0.)k^(h-1) k^h (k^(h+1)-1)/(k-1) (k^(h+1)-1)/(k-1) - 正确(k^h-1)/(k-1)Explanation层数---节点数number of levels---number of nodes0---11---k2---k^23---k^3....h---k^h所以答案是：so, the answer is：1+k+k^2+k^3+...+k^h = (k^(h+1)-1)/(k-1)PROBLEM 3(1/1 分)2-3树是一种特殊的树，它满足两个条件：（1）每个内部结点有两个或三个子结点；（2）所有的叶结点到根的路径长度相同；如果一棵2-3树有9个叶结点，那么它可能有_________个非叶结点。

(多项)2-3 tree is a special kind of tree, it satisfy:（1）Every internal node has 2 or 3 child nodes. (2)All the leaf nodes have the same length of the path to the root node.If a 2-3 tree has 9 leaf nodes, then it may have __________ non-leaf nodes.（There are more than one correct answers）4, 7, - 正确4 5 6 7Explanation倒数第二层若是3个结点，深度为2，加上根结点，一共4个非叶子结点。

第1章绪论 (2)1、填空题 (2)2、应用题 (2)第2章线性表 (3)1、填空题 (3)2、选择题 (3)3、判断题 (4)4、程序设计题 (4)第3章栈和队列 (6)1、填空题 (6)2、选择题 (6)3、判断题 (7)第4章串 (7)1、选择题 (7)2、判断题 (7)第5章数组和广义表 (7)1、填空题 (7)2、选择题 (7)3、判断题 (8)第6章树和二叉树 (8)1、填空题 (8)2、选择题 (9)3、判断题 (9)4、应用题 (9)5、读程序写结果 (16)第7章图 (17)1、填空题 (17)2、选择题 (17)3、判断题 (18)4、应用题 (18)5、程序设计题 (22)第8章动态存储管理 (23)1、填空题 (23)2、选择题 (23)3、判断题 (23)4、应用题 (23)5、程序设计题 (23)第9章查找 (23)1、选择题 (23)2、判断题 (24)3、应用题 (24)4、程序设计题 (26)第10章内部排序 (27)1、填空题 (27)2、选择题 (27)3、判断题 (27)4、应用题 (28)第11章外部排序 (28)第12章文件 (28)第1章绪论1、填空题1.常见的数据结构有_线性__结构，__树形___结构，__图形__结构等三种。

2.常见的存储结构有__顺序存储_______结构，__链式存储____结构等两种。

3.数据的基本单位是_数据元素___，它在计算机中是作为一个整体来处理的。

4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，__线性结构____和__非线性结构___。

2、应用题1、给出以下算法的时间复杂度.void fun(int n){int i=1,k=100;while(i<n){k=k+1;i=i+2;}}时间复杂度为____O（n）_____。

2、给出以下算法的时间复杂度.void fun2(int n){int i=1,k=100;while(i<n){i=i*10;k=k+1;}}时间复杂度为____O（log n）___________。

数据结构与算法(下)解忧书店JieYouBookshop第二章课后作业1、(1分)已知一组元素的排序码为(46，74，16，53，14，26，40，38，86，65，27，34)，利用直接选择排序方法写出第三次选择和交换后的排列结果。

注意：数字中间用一个空格隔开，不要写逗号和括号。

答案一共有12个数字。

答案：14 16 26 53 46 74 40 38 86 65 27 342、(1分)对于序列{E，A，S，Y，Q，U，E，S，T，I，O，N}，以{6，3，1}为增量采用Shell排序。

头两趟{6，3}增量排序后，关键字的累积比较次数为()。

A、16B、17C、18D、15答案：B3、(1分)一组记录的关键字为45，80，55，40，42，85，则利用堆排序的方法建立的初始最大堆为________。

（数字之间用一个空格隔开，答案中不含逗号和括号）答案：85 80 55 40 42 45 4、(1分)在图书馆里计算机类书籍区一共有12列书架，书架上的书本来都是按照编目号排列好的，其中有些书被读者放错了地方，但通常不会超过一个书架。

来将这些书重新放回正确位置，应该使用何种排序方法() A、插入排序C、快速排序D、直接选择排序E、堆排序答案：A5、(1分)15个记录的冒泡排序算法所需最大交换次数为______，最小交换次数为______。

注意：答案中，两个数字之间用一个空格隔开，其余不含任何符号。

答案：105 0第三章课后作业1、(1分)已知一组元素的排序码为(46，74，16，53，14，26，40，38，86，65，27，34)，利用直接选择排序方法写出第三次选择和交换后的排列结果。

注意：数字中间用一个空格隔开，不要写逗号和括号。

答案一共有12个数字。

答案：14 16 26 53 46 74 40 38 86 65 27 342、(1分)对于序列{E，A，S，Y，Q，U，E，S，T，I，O，N}，以{6，3，1}为增量采用Shell排序。

《数据结构》复习资料一、单项选择题1.一种逻辑结构在存储时(C)。

A.只要存储数据元素间的关系B.只能采用一种存储结构c.可采用不同的存储结构 D.只要存储数据元素的值2.对链表，以下叙述中正确的是(A)A.不能随机访问任一结点B.结点占用的存储空间是连续的c.插入删除元素的操作一定要移动结点D.可以通过下标对链表进行直接访问3.线性表在存储后，如果相关操作是:要求已知第i个结点的位置访问该结点的前驱结点，则采用(A)存储方式是不可行的。

A.单链表B.双链表 c.单循环链表 D.顺序表4.械和队列的共同特点是(C)。

A.都是先进后出B.元素都可以随机进出c.只容许在端点处插入和删除元素 D.都是先进先出5.元素2，4，6，8按顺序依次进拢，按该校的可能输出序列依次人队列，该队列的可能输出序列是(D)(进找出校可以交替进行)。

A.8,6,2,4B.8,4,2,6C.6,2,4,8D.8,6,4,26.在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，则从该对列中删除一个结点并把结点的值保存在变量x中的运算为(C)。

A.x=r•data;r=r•next;B.r=r•next;x=r•dataC.x=f•data;f=f•next;D.f=f•next;x=f•data7.设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始)，则数组中第38号元素对应于矩阵中的元素是(C)。

(矩阵中的第1个元素是al，l)A.alO,8B.a7,6C.a9,2D.句，58.在C语言中，分别存储"S"和‘s'，各需要占用(D)字节。

A.一个和两个B.两个c.一个 D.两个和一个9.一棵有n个结点，采用链式存储的二叉树中，共有()个指针域被有效使用(C)。

A.n+1B.nC.n-1D.n-210.在一棵二叉树中，若编号为i的结点存在双亲结点，则双亲结点的顺序编号为(B)。