当前位置：文档库 › 数据机构第六章查找习题

数据机构第六章查找习题

06 查找

【单选题】

1. 若在静态查找表中用顺序查找法查找数据元素，该表应该（C ）。

A 、采用顺序存储结构，且表中数据元素按待查关键字值有序排列

B 、采用链式存储结构，且表中数据元素按待查关键字值有序排列

C 、采用链式或顺序存储结构均可，表中数据元素亦可任意排列

D 、采用链式或顺序存储结构均可，但表中数据元素须按待查关键字值有序排列

2. 若在静态查找表中用折半查找法查找数据元素，该表应该（C ）。

A 、元素按待查关键字值有序排列

B 、采用顺序存储结构

C 、元素按待查关键字值有序排列，且采用顺序存储结构

D 、元素按待查关键字值有序排列，且采用链式存储结构

3. 设静态查找表中含100个数据元素，用折半查找法进行查找，在查找成功的情况下所需最多关键字比较次数为（D ）。

A 、50次

B 、25次

C 、10次

D 、7次

4. 设顺序表中含n 个数据元素且已按待查关键字值有序，若用折半查找法按关键字值进行查找，则最多需进行的关键字值间的比较次数为（B ）。

A 、n 2

B 、??1log 2+n

C 、n+1

D 、n

5. 具有12个关键字的有序表，折半查找的平均查找长度（A ）。

A 、3.1

B 、4

C 、2.5

D 、5

6. 折半查找的时间复杂性为（D ）。

A 、O （n 2）

B 、O （n ）

C 、O （nlogn ）

D 、O （logn ）

7. 当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度（C ）。

A 、必定快

B 、不一定

C 、在大部分情况下要快

D 、取决于表递增还是递减

8. 设按关键字序列（24,38,16,98,27,33,12,56）建立平衡的二叉查找树，则在其中查找关键字值为33的数据元素需进行（B ）次关键字值间的比较。

A 、3

B 、4

C 、5

D 、6

9. 对二叉查找树进行（B ）遍历，可得按待查关键字值有序的结点序列。

A 、前序

B 、中序

C 、后序

D 、层序

10. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A ，并已知A 的左孩子的平衡因子为0右孩子的平衡因子为1,则应作（C ）型调整以使其平衡。

A 、LL

B 、LR

C 、RL

D 、RR

11. m阶B树每个内部结点最多含（A）个关键字。

A、m-1

B、m

C、m+1

D、m/2-1

12. 下面关于m阶B树说法正确的是（B）。

①每个结点至少有两棵非空子树；

②树中每个结点至多有m-1个关键字；

③所有叶子在同一层上；

④当插入一个数据项引起B树结点分裂后，树长高一层。

A、①②③

B、②③

C、②③④

D、③

13. m阶B-树是一棵（B）。

A、m叉排序树

B、m叉平衡排序树

C、m-1叉平衡排序树

D、m+1叉平衡排序树

14. 一棵3阶B-树中含有2047个关键字，包括叶结点层，该树的最大深度为（B）。

A、11

B、12

C、13

D、14

15. 设有k个数据元素的关键字互为同义词，若用线性探测法把这k个数据元素存入哈希表，至少要进行（D）次探测。

A、k-1

B、k

C、k+1

D、k(k-1)/2

16. 设哈希表地址范围为0~19，哈希函数H(key)=key%17，使用二次探测再散列法处理冲突。若表中已存放有关键字值为6、22、38、55的记录，则再放入关键字值为72的记录时，其存放地址应为（E）。

A、2

B、3

C、4

D、7

E、8

F、以上都不对

17. 设哈希函数H(key)=key%17，使用线性探查法处理冲突，若表中已放入关键字值为21、3、40的记录，则再放入关键字值为20的记录时，该记录的存放地址应为（C）。

A、3

B、4

C、5

D、6

18. 下面关于哈希查找的说法正确的是（C）。

A、哈希函数构造的越复杂越好，因为这样随机性好，冲突小

B、除留余数法是所有哈希函数中最好的

C、不存在特别好与坏的哈希函数，要视情况而定

D、若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可

【填空题】

1. 设按关键字序列（19,26,68,78,37,12,58,46）建立平衡的二叉查找树，则等概率下查找成功时的平均查找长度为（11/4）。

2. m（m≥3）阶B树中每个内部结点最少有（??2/m）棵子树，最多有（m）棵子树；根结点最少有（2）棵子树，最多有（m）棵子树。

3. 哈希表的装填因子=（表中填入记录数/表长）。

【计算题】

1. 画出对长度为10的有序表进行折半查找的判定树，并求等概率下查找成功时的平均查找长度。解：

判定树：平均查找长度＝(1+2*2+4*3+3*4)/10=2.9

2. 设给定关键字序列（30, 12, 07, 22, 18, 20）

(1)构造二叉查找树，并求等概率下查找成功时的平均查找长度；

(2)构造平衡的二叉查找树，并求等概率下查找成功时的平均查找长度。

解：

(1)

平均查找长度=(1+2+2*3+4+5)/6=3

(2)

平均查找长度=(1+2*2+3*3)/6=7/3

3. 试推导含12个结点的平衡二叉树的最大深度，并画出一棵这样的树。解：5层

4. 设有3阶B树如下：

(1)求等概率下查找成功时的平均查找长度；

(2)画出向其中插入关键字80的过程；

(3)画出删除其中关键字17的过程。

解：

(1)ASL=(1+2+2+3+3+3+3+4+5+4)/10=3

(2)

插入80：

分裂结点：

(3)删除17：

合并结点：

5. 含9个叶子结点的3阶B-树中至少有多少个非叶子结点？含10个叶子结点的3阶B-树中至多有多少个非叶子结点？

解：4个、8个。

6. 设哈希函数H(key)=(3*key)%11，用开放定址法处理冲突，其中d i=i*((7*key)%10+1)，i=1,2,3…。试在0～10的散列地址空间中对关键字序列（22，41，53，46，30，13，01，67）构造哈希表，要求：

(1)画出哈希表存储结构示意图；

(2)求等概率下查找成功时的平均查找长度；

(3)求哈希表的装填因子。

解：

(1)开放定址法中，H i=(H(key)+d i)%m，i=1,2,…,k，k≤m-1，其中H(key)为哈希函数，m为哈希表长，

d i为增量序列。

H(22)=(3*22)%11=0

H(41)=(3*41)%11=2

H(53)=(3*53)%11=5

H(46)=(3*46)%11=5

冲突！d1=1*((7*46)%10+1)=3 H1=(5+3)%11=8

H(30)=(3*30)%11=2

冲突！d1=1*((7*30)%10+1)=1 H1=(2+1)%11=3

H(13)=(3*13)%11=6

H(01)=(3*01)%11=3

冲突！d1=1*((7*01)%10+1)=8 H1=(3+8)%11=0

冲突！d2=2*((7*01)%10+1)=16 H2=(3+16)%11=8

冲突！d3=3*((7*01)%10+1)=24 H3=(3+24)%11=5

冲突！d4=4*((7*01)%10+1)=32 H4=(3+32)%11=2

冲突！d5=5*((7*01)%10+1)=40 H4=(3+40)%11=10

H(67)=(3*67)%11=3

冲突！d1=1*((7*67)%10+1)=10 H1=(3+10)%11=2

冲突！d2=2*((7*67)%10+1)=20 H2=(3+20)%11=1

哈希表存储结构示意图：

(2)平均查找长度=(1+1+1+2+2+1+6+3)/8=17/8

(3)装填因子=8/11

7. 设哈希函数H(key)=key%11，用链地址法处理冲突，试在长度为12的散列地址空间中对关键字序列（1，13，12，34，38，33，27，22）造哈希表，要求：

(1)画出哈希表存储结构示意图；

(2)求等概率下查找成功时的平均查找长度。

解：

(1)

(2)平均查找长度＝(1+2+1+2+3+1+1+2)/8=13/8

【算法题】

下列算法题中可能用到的类如下：

public class StaticSearchTable {

private int stable[ ];

public StaticSearchTable(int length){

stable = new int[length];

}

}//StaticSearchTable静态查找表类

public class BiSTreeNode {

public int data;

public BiSTreeNode lchild;

public BiSTreeNode rchild;

public BiSTreeNode(int d){

data=d;

lchild=null;

rchild=null;

}

}//BiSTreeNode二叉查找树结点类

public class BiSTree {

private BiSTreeNode root;

public BiSTree(){

root=null;

}

}//二叉查找树类

1. 在StaticSearchTable类中添加方法，实现如下查找操作：若表长<=10，则进行顺序查找，否则进行折半查找（假设查找表中元素已按待查关键字值升序有序）。

2. 在BiSTree类中添加实现如下功能的方法：

(1)判别二叉查找树是否符合定义；

(2)按降序输出二叉查找树中所有关键字值不小于ｘ的数据元素；

(3)将指定二叉查找树与当前二叉查找树合并为一棵。

数据结构第6章习题集

1．由３个结点所构成的二叉树有种形态。 2. 一棵深度为6的满二叉树有个分支结点和个叶子。 3. 设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。 4. 二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R 次序），后序法（即按次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是。 5. 用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是。 6. 一棵度为2的树与一棵二叉树有何区别？ 7. 设如下图所示的二叉树B的存储结构为二叉链表，root为根指针，结点结构为：（lchild,data,rchild）。其中lchild，rchild分别为指向左右孩子的指针，data为字符型，root为根指针，试回答下列问题：对下列二叉树B，执行下列算法traversal(root)，试指出其输出结果；C的结点类型定义如下： struct node {char data; struct node *lchild, rchild; }; C算法如下： void traversal(struct node *root) {if (root) {printf(“%c”, root->data); traversal(root->lchild); printf(“%c”, root->data);

数据结构课后习题与解析第六章

第六章习题 1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。 3．已知一棵度为k的树中有n 1个度为1的结点，n 2 个度为2的结点，……，n k 个度为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．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。 19．设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树是指：在二叉树中不存在子树个数为1的结点。 20．计算二叉树最大宽度的算法。二叉树的最大宽度是指：二叉树所有层中结点个数的最大值。 21．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。 22. 证明：给定一棵二叉树的前序序列与中序序列，可唯一确定这棵二叉树；给定一棵二叉树的后序序列与中序序列，可唯一确定这棵二叉树； 23. 二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。 24. 二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进行交换。实习题 1.[问题描述] 建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。

数据库系统概论试题及标准答案6

试题六 -、单项选择题（本大题共10小题，每小题2分，共20分）在每小题列出的四个备选项中只有一个是符合题目要求的，错选、多选或未选均无分。 1. DB 、DBMS 和DBS 三者之间的关系是（）。 A . D B 包括 DBMS 和 DBS B . DBS 包括 DB 和 DBMS C . DBMS 包括DB 和DBS D .不能相互包括 A .外模式 C .概念模式 3. 在数据库三级模式间引入二级映象的主要作用是（） | A .提高数据与程序的独立性 B .提高数据与程序的安全性 j C .保持数据与程序的一致性 D .提高数据与程序的可移植性 ■ 4.视图是一个“虚表”，视图的构造基于（） A .基本表 B .视图 I C .基本表或视图 D .数据字典 5.关系代数中的n 运算符对应 SELECT 语句中的以下哪个子句？（） | A . SELECT B . FROM - C . WHERE D . GROUP BY ! 6.公司中有多个部门和多名职员，每个职员只能属于一个部门，一个部门可以 I 有多名职员，从职员到部门的联系类型是（） | A .多对多 B . 一对一 C .多对一 D . 一对多 | 7.如何构造出一个合适的数据逻辑结构是（）主要解决的问题。 - A .关系系统查询优化 B .数据字典 C .关系数据库规范化理论 D .关系数据库查询 I I 8.将E-R 模型转换成关系模型，属于数据库的（）。 | A.需求分析 B. 概念设计 j C.逻辑设计 D. 物理设计）线此过超得不题答生 2.对数据库物理存储方式的描述称为（） B .内模式 D .逻辑模式

(完整版)数据库课后习题及答案

第一章数据库系统概述选择题 1实体-联系模型中，属性是指（C） A.客观存在的事物 B.事物的具体描述 C.事物的某一特征 D.某一具体事件 2对于现实世界中事物的特征，在E-R模型中使用（A） A属性描述B关键字描述C二维表格描述D实体描述 3假设一个书店用这样一组属性描述图书（书号，书名，作者，出版社，出版日期），可以作为“键”的属性是（A） A书号B书名C作者D出版社 4一名作家与他所出版过的书籍之间的联系类型是（B） A一对一B一对多C多对多D都不是 5若无法确定哪个属性为某实体的键，则（A） A该实体没有键B必须增加一个属性作为该实体的键C取一个外关键字作为实体的键D该实体的所有属性构成键填空题 1对于现实世界中事物的特征在E-R模型中使用属性进行描述 2确定属性的两条基本原则是不可分和无关联 3在描述实体集的所有属性中，可以唯一的标识每个实体的属性称为键 4实体集之间联系的三种类型分别是1：1 、1：n 、和m：n 5数据的完整性是指数据的正确性、有效性、相容性、和一致性简答题一、简述数据库的设计步骤答:1需求分析：对需要使用数据库系统来进行管理的现实世界中对象的业务流程、业务规则和所涉及的数据进行调查、分析和研究，充分理解现实世界中的实际问题和需求。分析的策略：自下而上——静态需求、自上而下——动态需求 2数据库概念设计：数据库概念设计是在需求分析的基础上，建立概念数据模型，用概念模型描述实际问题所涉及的数据及数据之间的联系。 3数据库逻辑设计：数据库逻辑设计是根据概念数据模型建立逻辑数据模型，逻辑数据模型是一种面向数据库系统的数据模型。 4数据库实现：依据关系模型，在数据库管理系统环境中建立数据库。二、数据库的功能答：1提供数据定义语言，允许使用者建立新的数据库并建立数据的逻辑结构 2提供数据查询语言 3提供数据操纵语言 4支持大量数据存储 5控制并发访问三、数据库的特点答：1数据结构化。2数据高度共享、低冗余度、易扩充3数据独立4数据由数据库管理系统统一管理和控制：（1）数据安全性（2）数据完整性（3）并发控制（4）数据库恢复第二章关系模型和关系数据库选择题 1把E-R模型转换为关系模型时，A实体（“一”方）和B实体（“多”方）之间一对多联系在关系模型中是通过（A）来实现的

数据结构第六章习题课

1、下图所示的4棵二叉树中，不是完全二叉树的是（） 2、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法（）。 A 、正确 B 、错误 C 、不一定 3、已知某二叉树的后序遍历序列是dabec ，中序遍历序列是debac ，它的前序遍历序列是（）。 A 、acbed B 、decab C 、deabc D 、cedba 4、如果T2是由有序树T 转换而来的二叉树，那么T 中结点的后序就是T2中结点的（）。 A 、前序 B 、中序 C 、后序 D 、层次序 5、深度为5的二叉树至多有（）个结点。 A 、16 B 、32 C 、31 D 、10 6、在一个非空二叉树的中序遍历序列中，根结点的右边（）。 A 、只有右子树上的所有结点 B 、只有右子树上的部分结点 C 、只有左子树上的部分结点 D 、只有左子树上的所有结点 7、树最适合用来表示（）。 A 、有序数据元素 B 、无序数据元素 C 、元素之间具有分支层次关系的数据 D 、元素之间无联系的数据。 8、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。 A 、不发生改变 B 、发生改变 C 、不能确定 D 、以上都不对 9、实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用（）存储结构。 A 、二叉链表 B 、广义表存储结构 C 、三叉链表 D 、顺序存储结构 10、对一个满二叉树，m 个树叶，n 个结点，深度为h ，则（）。 A 、n=m+h B 、h+m=2n C 、m=h-1 D 、n=2h -1 11、设n ，m 为二叉树上的两个结点，在中序遍历时，n 在m 前的条件是（）。 A 、n 在m 右方 B 、n 是m 祖先 C 、n 在m 左方 D 、n 是m 子孙 12．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/- ， A B C D

数据库系统原理教程习题答案第6章习题

第6章关系数据库理论 1 ．理解并给出下列术语的定义：函数依赖、部分函数依赖、完全函数依赖、传递依赖、候选码、主码、外码、全码（All 一key ）、1 NF 、ZNF 、3NF 、BcNF 、多值依赖、4NF 。定义1：设R(U)是属性集U上的关系模式。X，Y是属性集U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数确定Y或Y函数依赖于X，记作X→Y。（即只要X上的属性值相等，Y上的值一定相等。）术语和记号： X→Y，但Y不是X的子集，则称X→Y是非平凡的函数依赖。若不特别声明，总是讨论非平凡的函数依赖。X→Y，但Y是X的子集，则称X→Y是平凡的函数依赖。若X→Y，则X叫做决定因素(Determinant)。若X→Y，Y→X，则记作X←→Y。若Y不函数依赖于X，则记作X → Y。定义2：在R(U)中，如果X→Y，并且对于X的任何一个真子集X’，都有X’→ Y，则称Y对X完全函数依赖若X→Y，但Y不完全函数依赖于X，则称Y对X部分函数依赖定义3：若关系模式R的每一个分量是不可再分的数据项，则关系模式R属于第一范式(1NF)。定义4：若关系模式R∈1NF，且每一个非主属性完全函数依赖于码，则关系模式R∈2NF 。（即1NF消除了非主属性对码的部分函数依赖则成为2NF）。定义5:关系模式R 中若不存在这样的码X、属性组Y及非主属性Z(Z不是Y的子集)使得X→Y，Y →X，Y → Z成立，则称R∈3NF。定义6:关系模式R∈1NF 。若X→Y且Y不是X的子集时,X必含有码，则R∈BCNF。定义7:关系模式R∈1NF，如果对于R的每个非平凡多值依赖X→→Y(Y不是X的子集，Z=U-X-Y 不为空)，X都含有码，则称R∈4NF。 2．建立一个关于系、学生、班级、学会等诸信息的关系数据库。学生：学号、姓名、出生年月、系名、班号、宿舍区。班级：班号、专业名、系名、人数、入校年份。系：系名、系号、系办公地点、人数。学会：学会名、成立年份、办公地点、人数。语义如下：一个系有若干专业，每个专业每年只招一个班，每个班有若干学生。一个系的学生住在同一宿舍区。每个学生可参加若干学会，每个学会有若干学生。学生参加某学会有一个入会年份。请给出关系模式，写出每个关系模式的极小函数依赖集，指出是否存在传递函数依赖，对于函数依赖左部是多属性的情况讨论函数依赖是完全函数依赖，还是部分函数依赖。指出各关系模式的候选码、外部码，有没有全码存在? 解：(1)关系模式如下：学生：S(Sno，Sname，Sbirth，Dept，Class，Rno) 班级：C(Class，Pname，Dept，Cnum，Cyear) 系：D(Dept，Dno，Office，Dnum) 学会：M(Mname，Myear，Maddr，Mnum) (2)每个关系模式的最小函数依赖集如下： A、学生S (Sno，Sname，Sbirth，Dept，Class，Rno) 的最小函数依赖集如下:Sno→Sname，Sno→Sbirth，Sno→Class，Class→Dept，DEPT→Rno

数据结构-第六章-图-练习题及答案详细解析(精华版)

⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。【解答】前序，栈，层序，队列 ⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。【解答】回路 ⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题 ⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。

数据结构习题(,,章)

————————————————————————————————作者：————————————————————————————————日期：

第四章串一．选择题 1．若串S='software',其子串的数目是（） A．8 B．37 C．36 D．9 2．设有两个串p和q,求q在p中首次出现的位置的运算称作（） A．连接B．模式匹配C．求串长D．求子串 3．设字符串S1=“ABCDEFG”，S2=“PQRST”，则运算： S=CONCAT（SUBSTR（S1，2，LEN（S2））；SUBSTR（S1，LEN（S2），2））；后的串值为（） A．A BCDEF B．BCDEFG C．BCDPQRST D． BCDEFEF 4．下面的说法中，只有（）是正确的 A．串是一种特殊的线性表B．串的长度必须大于零 C．串中元素只能是字母D．空串就是空白串 5．两个字符串相等的条件是（） A．两串的长度相等 B．两串包含的字符相同 C．两串的长度相等，并且两串包含的字符相同 D．两串的长度相等，并且对应位置上的字符相同二．填空题 1．串“ababcbaababd”的next函数值为，nextval函数值为。2．子串的长度为。第五章数组和广义表一．选择题 1．设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( ) A. BA+141 B. BA+180 C. BA+222 D. BA+225 2．假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（） A. 808 B. 818 C. 1010 D. 1020 3．对稀疏矩阵进行压缩存储目的是（） A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度 4．假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（）

数据结构-习题-第六章-树

数据结构-习题-第六章-树和二叉树

E F D G A B / + + * - C * 第六章树和二叉树一、选择题 1．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( ) A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE 【北京航空航天大学 1999 一、3 （2分)】 2．算术表达式a+b*（c+d/e ）转为后缀表达式后为（）【中山大学 1999 一、5】 A ．ab+cde/* B ．abcde/+*+ C ．abcde/*++ D ．abcde*/++ 3. 设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（）【南京理工大学1999 一、20（2分）】 A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G 4. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T 中的叶子数为（） A ．5 B ．6 C ．7

D．8 【南京理工大学 2000 一、8 （1.5分）】5. 在下述结论中，正确的是（）【南京理工大学 1999 一、4 （1分）】 ①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．② ④ D．①④ 6. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（） A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定【南京理工大学2000 一、17（1.5分）】 7. 树是结点的有限集合，它（ (1）)根结点，记为T。其余结点分成为m（m>0）个(（2）)的集合T1，T2，…，Ｔm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。一个结点的子结点个数称为该结

《数据结构》习题汇编06第六章树和二叉树试题

第六章树和二叉树试题一、单项选择题 1.树中所有结点的度等于所有结点数加（）。 A. 0 B. 1 C. -1 D. 2 2.在一棵树中，（）没有前驱结点。 A. 分支结点 B. 叶结点 C. 根结点 D. 空结点 3.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。 A. 2 B. 1 C. 0 D. -1 4.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）。 A. n B. n-1 C. n+1 D. 2*n 5.在一棵具有n个结点的二叉树的第i层上（假定根结点为第0层，i大于等

于0而小于等于树的高度），最多具有（）个结点。 A. 2i B. 2i+1 C. 2i-1 D. 2n 6.在一棵高度为h（假定根结点的层号为0）的完全二叉树中，所含结点个数不小于（）。 A. 2h-1 B. 2h+1 C. 2h-1 D. 2h 7.在一棵具有35个结点的完全二叉树中，该树的高度为（）。假定空树的高度为-1。 A. 5 B. 6 C. 7 D. 8 8.在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（）。假定树根结点的编号为0。 A. ?(n-1)/2? B. ?n/2? C. ?n/2? D. ?n/2? -1 9.在一棵完全二叉树中，若编号为i的结点存在左孩子，则左子女结点的编号为（）。假定根结点的编号为0

A. 2i B. 2i-1 C. 2i+1 D. 2i+2 10.在一棵完全二叉树中，假定根结点的编号为0，则对于编号为i（i＞0）的结点，其双亲结点的编号为（）。 A. ?(i+1)/2? B. ?(i-1)/2? C. ?i/2? D. ?i/2? -1 11.在一棵树的左子女-右兄弟表示法中，一个结点的右孩子是该结点的（）结点。 A. 兄弟 B. 子女 C. 祖先 D. 子孙 12.在一棵树的静态双亲表示中，每个存储结点包含（）个域。 A. 1 B. 2 C. 3 D. 4 13.已知一棵二叉树的广义表表示为a (b (c), d (e ( , g (h) ), f ) )，则该二叉树的高度为（）。假定根结点的高度为0。 A. 3 B. 4 C. 5 D. 6

第六章树和二叉树习题数据结构

习题六树和二叉树一、单项选择题 1．以下说法错误的是 ( ) A．树形结构的特点是一个结点可以有多个直接前趋 B．线性结构中的一个结点至多只有一个直接后继 C．树形结构可以表达(组织)更复杂的数据 D．树(及一切树形结构)是一种"分支层次"结构 E．任何只含一个结点的集合是一棵树 2．下列说法中正确的是 ( ) A．任何一棵二叉树中至少有一个结点的度为2 B．任何一棵二叉树中每个结点的度都为2 C．任何一棵二叉树中的度肯定等于2 D．任何一棵二叉树中的度可以小于2 3．讨论树、森林和二叉树的关系，目的是为了（） A．借助二叉树上的运算方法去实现对树的一些运算 B．将树、森林按二叉树的存储方式进行存储 C．将树、森林转换成二叉树 D．体现一种技巧，没有什么实际意义 4．树最适合用来表示 ( ) A．有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据 5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定 6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。 A．M1 B．M1+M2 C．M3 D．M2+M3 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（） A． 250 B． 500 C．254 D．505 E．以上答案都不对 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A．不确定 B．2n C．2n+1 D．2n-1 9．二叉树的第I层上最多含有结点数为（） A．2I B． 2I-1-1 C． 2I-1 D．2I -1 10．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+1 11. 利用二叉链表存储树，则根结点的右指针是（）。 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 14．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）A．都不相同 B．完全相同 C．先序和中序相同，而与后序不同 D．中序和后序相同，而与先序不同 15．在完全二叉树中，若一个结点是叶结点，则它没（）。 A．左子结点 B．右子结点 C．左子结点和右子结点 D．左子结点，右子结点和兄弟结点 16．在下列情况中，可称为二叉树的是（）

数据结构第6章树练习

void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法 { InitStack(S); Push(S,T); //根指针进栈 while(!StackEmpty(S)) { while(Gettop(S,p)&&p) { visit(p->data); push(S,p->lchild); } //向左走到尽头 pop(S,p); if(!StackEmpty(S)) { pop(S,p); push(S,p->rchild); //向右一步 } }//while }//PreOrder_Nonrecursive 一、下面是有关二叉树的叙述，请判断正误 1.二叉树中每个结点的两棵子树的高度差等于1。（） 2.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。（） 3.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i —1个结点。（） 4.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。（） 5.具有12个结点的完全二叉树有5个度为2的结点。（）最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5 6．二叉树是度为2的有序树（） 7．完全二叉树一定存在度为1的结点（） 8．深度为K的二叉树中结点总数≤2k-1（） 9．由一棵二叉树的先序序列和后序序列可以惟一确定它（） 10．完全二叉树中，若一个结点没有左孩子，则它必是树叶（）

11．用二叉链表存储n个结点的二叉树时，结点的2n个指针中有n+1个空指针（）12．完全二叉树的存储结构通常采用顺序存储结构（） 13．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近（）14．在中序线索二叉树中，每一非空的线索均指向其祖先结点（）二、填空 1. 一棵具有２５７个结点的完全二叉树，它的深度为。 2. 用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是 3．深度为H 的完全二叉树至少有_____________个结点；至多有_____________个结点4．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是_____________。 5. n（n大于1）个结点的各棵树中，其深度最小的那棵树的深度是_____________。它共有_____________个叶子结点和_____________个非叶子结点，其中深度最大的那棵树的深度是_____________，它共有_____________个叶子结点和_____________个非叶子结点。三、单项选择题 1．有关二叉树下列说法正确的是（） A）二叉树的度为2 B）一棵二叉树的度可以小于2 C）二叉树中至少有一个结点的度为2 D）二叉树中任何一个结点的度都为2 2．二叉树的第I层上最多含有结点数为（） A）2I B）2I-1-1 C）2I-1D）2I-1 3．具有10个叶结点的二叉树中有（）个度为2的结点 A）8 B）9 C）10 D）11 4．在下述结论中，正确的是（） ①只有一个结点的二叉树的度为0； ②二叉树的度为2； ③二叉树的左右子树可任意交换； ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A）①②③B）②③④C）②④D）①④ 5．由3 个结点可以构造出多少种不同的二叉树？（） A）2 B）3 C）4 D）5 6．引入二叉线索树的目的是（）

数据结构第三章习题答案

第三章习题 1.按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答： ⑴如进站的车厢序列为123，则可能得到的出站车厢序列是什么？ ⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。 2.设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个队列重复执行下列4步操作：（1）输出队首元素；（2）把队首元素值插入到队尾；（3）删除队首元素；（4）再次删除队首元素。直到队列成为空队列为止，得到输出序列：（1）A、C、E、C、C （2） A、C、E （3） A、C、E、C、C、C （4） A、C、E、C 3.给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？ 4.按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程： A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ 5.试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1& 序列2’ 模式的字符序列。其中序列1和序列2中都不含字符’&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。 6.假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。 7.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。 8.要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。 9.简述以下算法的功能（其中栈和队列的元素类型均为int）：

数据库系统概论部分答案

第一章 1 ．试述数据、数据库、数据库系统、数据库管理系统的概念。答： ( l ）数据（ Data ) ：描述事物的符号记录称为数据。数据的种类有数字、文字、图形、图像、声音、正文等。 ( 2 ）数据库（ DataBase ，简称 DB ) ：数据库是长期储存在计算机内的、有组织的、可共享的数据集合。 ( 3 ）数据库系统（ DataBas 。 Sytem ，简称 DBS ) ：数据库系统是指在计算机系统中引入数据库后的系统构成， ( 4 ）数据库管理系统（ DataBase Management sytem ，简称 DBMs ) ：数据库管理系统是位于用户与操作系统之间的一层数据管理软件，用于科学地组织和存储数据、高效地获取和维护数据。 5 ．试述数据库系统的特点。答： ( l ）数据结构化数据库系统实现整体数据的结构化，这是数据库的主要特征之一，也是数据库系统与文件系统的本质区别。 ( 2 ）数据的共享性高，冗余度低，易扩充数据库的数据不再面向某个应用而是面向整个系统，因此可以被多个用户、多个应用以多种不同的语言共享使用。( 3 ）数据独立性高数据独立性包括数据的物理独立性和数据的逻辑独立性。数据库管理系统的模式结构和二级映像功能保证了数据库中的数据具有很高的物理独立性和逻辑独立性。 ( 4 ）数据由 DBMS 统一管理和控制数据库的共享是并发的共享，即多个用户可

以同时存取数据库中的数据甚至可以同时存取数据库中同一个数据。 7. 什么是概念模型？试述概念模型的作用。答：概念模型是现实世界到机器世界的一个中间层次，作用：用于信息世界的建模，是现实世界到信息世界的第一层抽象，数据库设计人员进行数据库设计的有力工具，也是数据库设计人员和用户之间进行交流的语言。 8．定义并解释概念模型中以下术语：实体，实体型，实体集，实体之间的联系答：实体：客观存在并可以相互区分的事物叫实体。实体型：具有相同属性的实体具有相同的特征和性质，用实体名及其属性名集合来抽象和刻画同类实体，称为实体型。实体集：同型实体的集合称为实体集。实体之间的联系： 1 : 1 , 1 : n 和 m : n 9 ．试述数据模型的概念、数据模型的作用和数据模型的三个要素。答：数据模型是数据库中用来对现实世界进行抽象的工具，是数据库中用于提供信息表示和操作手段的形式构架。一般地讲，数据模型是严格定义的概念的集合。这些概念精确描述了系统的静态特性、动态特性和完整性约束条件。因此数据模型通常由数据结构、数据操作和完整性约束三部分组成。（ l ）数据结构：是所研究的对象类型的集合，是对系统静态特性的描述。 ( 2 ）数据操作：是指对数据库中各种对象（型）的实例（值）允许进行的操作的集合，包括操作及有关的操作规则，是对系统动态特性的描述。

第六章信息系统与数据库

第六章信息系统与数据库一、选择题 1.以下列出了计算机信息系统抽象结构层次，其中的数据库管理系统和数据库______＿_。Ａ.属于业务逻辑层 B 属于资源管理层Ｃ属于应用表现层 D 不在以上所列层次中 2.以下列出了计算机信息系统抽象结构的4个层次，在系统中为实现相关业务功能(包括流程、规则、策略等)而编制的程序代码属于其中的_＿＿_＿＿__。A基础设施层 B 业务逻辑层 C 资源管理层 D 应用表现层 3. 以下列出了计算机信息系统抽象结构的4个层次，系统中的硬件、系统软件和网络属于其中的______＿_。 A.基础设施层 B．业务逻辑层Ｃ．资源管理层 D.应用表现层 4. 以下列出了计算机信息系统抽象结构层次，在系统中可实现分类查询的表单和展示查询结果的表格窗口＿_＿____＿。Ａ属于业务逻辑层Ｂ属于资源管理层 C属于应用表现层Ｄ不在以上所列层次中 5.以下关于ＳQＬ语言的说法中,错误的是___＿_＿＿_ Ａ.SQＬ的一个基本表就是一个数据库Ｂ．SQL语言支持三级体系结构 C.一个基本表可以跨多个存储文件存放 D.ＳQL的一个二维表可以是基本表,也可以是视图 6. 信息系统采用Ｂ/S模式时,其“查询ＳQＬ请求”和“查询结果”的“应答”发生在___＿＿__＿之间。 A浏览器和Web服务器 B 浏览器和数据库服务器 C Weｂ服务器和数据库服务器 D 任意两层 7. 关系数据库的SQL查询操作由３个基本运算组合而成,其中不包括＿_______ 。 A 连接 B 选择Ｃ投影Ｄ比较

8．信息系统采用的Ｂ/S模式，实质上是中间增加了____＿_＿_ 的C/S模式。 A Web服务器Ｂ浏览器 C数据库服务器 D文件服务器 9.在信息系统的B／S模式中，OＤＢC/JDＢC是＿＿______之间的标准接口。 A Wｅb服务器与数据库服务器 B 浏览器与数据库服务器 C 浏览器与Web服务器Ｄ客户机与Ｗeｂ服务器 10. 计算机信息系统中的B／Ｓ三层模式是指________。 A 应用层、传输层、网络互链层Ｂ应用程序层、支持系统层、数据库层 C浏览器层、Ｗeｂ服务器层、DB服务器层Ｄ客户机层、HTTP网络层、网页层１1.ＯＤＢC是_＿＿_＿___，用户可以直接将SQL语句送给OＤＢＣ。 A一组对数据库访问的标准Ｂ数据库查询语言标准 C数据库应用开发工具标准Ｄ数据库安全标准 12．所谓“数据库访问”，就是用户根据使用要求对存储在数据库中的数据进行操作。它要求___＿____ 。 A．用户与数据库可以不在同一计算机上而通过网络访问数据库;被查询的数据可以存储在多台计算机的多个不同数据库中Ｂ.用户与数据库必须在同一计算机上;被查询的数据存储在计算机的多个不同数据库中 C．用户与数据库可以不在同一计算机上而通过网络访问数据库；但被查询的数据必须存储同一台计算机的多个不同数据库中Ｄ.用户与数据库必须在同一计算机上；被查询的数据存储在同一台计算机的指定数据库中 13．OＤBＣ是_＿______，用户可以直接将ＳＱＬ语句送给ODBＣ。 A.一组对数据库访问的标准Ｂ．数据库查询语言标准 C. 数据库应用开发工具标准 D．数据库安全标准 14. SＱL查询语句:SEＬECT SNＡNE，DEPART,CNAＭＥ，GＲADE FRＯM Ｓ,Ｃ,SC WHERE S.ＳＮＯ=ＳC.SNO ＡND https://www.wendangku.net/doc/648158866.html,Ｏ＝Ｃ.CＮＯAＮＤS.S ＥX=‘男’; 涉及的S，Ｃ和SC三个表。Ｓ和SC表之间和C和SC表之间分别通过公共属性＿_______作连接操作。 A SNO，CＮO B CNＯ,ＳＮO C ＣNO,SEＸ D SＮO，ＳＥX

数据库系统概论第六章测试题及答案范文

第六章习题一、选择题：形框代替形框表示实体的属性。 1．在数据库设计中，用E-R图来描述信息结构但不涉及信息在计算机中的表示，它是数据库设计的____阶段。 A．需求分析B．概念设计C．逻辑设计D．物理设计答案：B 2．E－R图是数据库设计的工具之一，它适用于建立数据库的____。 A．概念模型B．逻辑模型C．结构模型D．物理模型答案：A 3．在关系数据库设计中，设计关系模式是____的任务。 A．需求分析阶段B．概念设计阶段C．逻辑设计阶段D．物理设计阶段答案：C 4．数据库物理设计完成后，进入数据库实施阶段，下列各项中不属于实施阶段的工作是____。 A．建立库结构B．扩充功能C．加载数据D．系统调试答案：B 5．数据库概念设计的E-R方法中，用属性描述实体的特征，属性在E-R图中，用____表示。 A．矩形B．四边形C．菱形D．椭圆形答案：D 6．在数据库的概念设计中，最常用的数据模型是____。 A形象模型B．物理模型C．逻辑模型D．实体联系模型答案：D 7．在数据库设计中，在概念设计阶段可用E－R方法，其设计出的图称为____。 A．实物示意图B．实用概念图C．实体表示图D．实体联系图答案：D 8．从E-R模型关系向关系模型转换时，一个M:N联系转换为关系模式时，该关系模式的关键字是____。 A．M端实体的关键字B．N端实体的关键字 C．M端实体关键字与N端实体关键字组合D．重新选取其他属性答案：C 9．当局部E-R图合并成全局E-R图时可能出现冲突，不属于合并冲突的是____。 A．属性冲突B．语法冲突C．结构冲突D．命名冲突答案：B

数据结构第六章图练习题及答案详细解析

图 1. 填空题 ⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵任何连通图的连通分量只有一个，即是（）。【解答】其自身 ⑶图的存储结构主要有两种，分别是（）和（）。【解答】邻接矩阵，邻接表【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。【解答】求第j列的所有元素之和 ⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。【解答】出度 ⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。【解答】前序，栈，层序，队列 ⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。【解答】回路 ⑽在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。【解答】vi, vj, vk