下载文档原格式
北航数据结构试题及答案一、单项选择题（每题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、链接存储结构特点:●比顺序存储结构的存储密度小(每个节点都由数据域与指针域组成)。
●逻辑上相邻的节点物理上不必相邻。
