下载文档原格式
华东理工大学网络学院（专科）《数据结构》------ch7图、ch9排序班级学号姓名成绩一、填空题（每空1分，共10分）1.具有n个顶点的有向图最多有n（n-1）条边。
2.在无向图G的邻接矩阵中，求第i个结点的度的方法是求邻接矩阵第i行非零元素之和。
3.堆排序通常采用顺序存储结构。
4. 与快速排序和堆排序相比，归并排序的最大特点是，它是一种稳定的排序方法。
5.具有8个顶点的有向完全图有56 条弧。
6. 在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于 1 。
7.在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，则使用直接插入排序方法最好。
8. 已知有向图的邻接矩阵，要计算i号顶点的入度，计算方法是：将i列元素累加。
9. n个顶点的强连通图至少有n 条边，至多有n(n-1) 条边。
二、判断正误（对的用”T”表示，错误的用”F”表示。
每小题1分，共10分）1. ( T )若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存在。
2. ( F )快速排序的速度在所有的排序方法中为最快，而且所需附加空间也最少。
3.（ F ）采用邻接表存储的图的深度优先遍历算法类似二叉树的按层次遍历算法。
4.（T ）在待排序的元素序列基本有序的前提下，效率最高的是插入排序。
5.（T ）图的广度优先遍历类似于树的层次遍历。
6.（T ）拓扑排序时，总是在有向图中选择入度为0的顶点输出。
7.（ F ）若要求一个稠密图G的最小生成树，最好用Kruscal算法来求解。
8.（T ）拓扑排序输出的顶点数小于有向图的顶点数，则该图一定存在回路。
9.（T ）设有一稠密图G，则G采用邻接矩阵存储较省空间。
10.（F）n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为O(n+e)。
三、单项选择题（每小题2分，共20分）1.已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是 C 。
数据结构－树练习题一、选择题1、二叉树的深度为k，则二叉树最多有（ C ）个结点。
A. 2kB. 2k-1C. 2k-1D. 2k-12、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是（ B ）。
A. R[2i-1]B. R[2i+1]C. R[2i]D. R[2/i]3、设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是（ B ）。
A. a在b的右方B. a在b的左方C. a是b的祖先D. a是b的子孙4、设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树先序遍历序列为（）。
A. adbceB. decabC. debacD. abcde5、在一棵具有5层的满二叉树中结点总数为（ A ）。
A. 31B. 32C. 33D. 166、由二叉树的前序和后序遍历序列（ B ）惟一确定这棵二叉树。
A. 能B. 不能7、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（C ）。
A. 3B. 2C. 4D. 58、若以{4,5,6,7,8}作为权值构造哈夫曼树，则该树的带权路径长度为（C ）。
A. 67B. 68C. 69D. 709、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（A ）。
A. 98B. 99C. 50D. 4810、表达式a*(b+c)-d的后缀表达式是（ B ）。
A. abcd+-B. abc+*d-C. abc*+d-D. -+*abcd11、对某二叉树进行先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果是（ B ）。
A. DBFEACB. DFEBCAC. BDFECAD. BDEFAC12、树最适合用来表示（ C ）。
练习题及答案第一部分：选择题一、单项选择题1．DBS是采用了数据库技术的计算机系统。
DBS是一个集合体，包含数据库、计算机硬件、软件和A.系统分析员B.程序员C.数据库管理员D.操作员2．模型是对现实世界的抽象，在数据库技术中，用模型的概念描述数据库的结构与语义，对现实世界进行抽象。
表示实体类型及实体间联系的模型称为A.数据模型B.实体模型C.逻辑模型D.物理模型3．关系模型概念中，不含有多余属性的超键称为A.候选键B.对键C.内键D.主键4．设R、S为两个关系，R的元数为4，S的元数为5，则与RS等价的操作是A．σ3<6(R×S) B.σ3<2(R×S） C.σ3>6(R×S) D.σ7<2(R×S)5．分布式数据库存储概念中，数据分配是指数据在计算机网络各场地上的分配策略，一般有四种，分别是集中式、分割式、全复制式和A. 任意方式B.混合式C.间隔方式D.主题方式6．数据库系统中，类是指具有相同的消息，使用相同的方法，具有相同的变量名和A. 变量值B. 特征C. 定义D. 类型7．随着计算机应用领域的扩大，第一代、第二代DBS不能适应处理大量的A.格式化数据B.网络数据C.非格式数据D.海量数据9．数据库并发控制概念中，使用X封锁的规则称为A.PS协议B.PX协议C.PSC协议D.两段封锁协议10.在数据库操作过程中事务处理是一个操作序列，必须具有以下性质：原子性、一致性、隔离性和A.共享性B.继承性C.持久性D.封装性11．面向对像模型概念中，类可以有嵌套结构。
系统中所有的类组成一个有根的A.有向无环图B.有向有环图C.无向有环图D.无向无环图12．在教学管理系统中，有教师关系T（T＃，NAME），学生关系S（S＃，NAME），学生成绩关系S(S＃，NU)。
其中T＃表示教师工号，S＃表示学生学号，则T和N存在联系为A. 1：1B. 1：NC. M：ND. 无联系13．一个数据库一般不是由独立的对象组成的，对象的聚集形式的数学意义是A. 笛卡尔积B. 选择C. 投影D. 联接14．对象标识是指针一级的概念是一个强有力的数据操纵原语言，是集合、元组和递归等复合对象操纵的基础，标识是A.任意的B. 可以改变的C.不唯一的D.不能改变的15．数据库系统中除了可用层次模型和关系模型表示实体类型及实体间联系的数据模型以外，还有A. E-R 模型B. 信息模型C.网络模型D.物理模型第二部分：非选择题二、填空题16. 数据库系统中，存放___________ 的数据库，称为数据字典（DD）。
习题一一、选择题1、数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（B）和运算的学科。
A．结构B．关系C．运算D．算法2、在数据结构中，从逻辑上可以把数据结构分成（C）。
A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．逻辑结构和存储结构3、线性表的逻辑顺序和存储顺序总是一致的，这种说法（B）。
A．正确B．不正确C．无法确定D．以上答案都不对4、算法分析的目的是（C）。
A．找出算法的合理性B．研究算法的输人与输出关系C．分析算法的有效性以求改进D．分析算法的易懂性二、填空题1、数据是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，数据是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。
例如，数学中所用到的整数和实数，文本编辑所用到的字符串等。
2、数据元素是数据的基本单位，有些情况下也称为元素、结点、顶点、记录等。
3、数据项是数据不可分割的最小单元，是具有独立含义的最小标识单位。
例如构成一个数据元素的字段、域、属性等都可称之为_数据项。
4、简而言之，数据结构是数据之间的相互关系，即数据的组织形式。
5、数据的逻辑结构是指数据之间的逻辑关系。
逻辑结构是从逻辑关系上描述数据，它与具体存储无关，是独立于计算机的。
因此逻辑结构可以看作是从具体问题抽象出来的数学模型。
6、数据的存储结构指数据元素及其关系在计算机存储器内的表示。
存储结构是逻辑结构在计算机里的实现，也称之为映像。
7、数据的运算是指对数据施加的操作。
它定义在数据的逻辑结构之上，每种逻辑结构都有一个数据的运算。
常用的有：查找、排序、插人、删除、更新等操作。
8、数据逻辑结构可以分为四种基本的类型，集合结构中的元素除了仅仅只是同属于一个集合_，不存在什么关系。
9、数据逻辑结构的四种基本类型中，线性结构_中的元素是一种一对一的关系，这种结构的特征是：若结构是非空集，则有且只有一个开始结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。
习 题 六 树 和 二 叉 树6.1 单项选择题1. 如图8.7所示的4棵二叉树，_C ___不是完全二叉树。
2. 如图8.8所示的4棵二叉树，__B_是平衡二叉树。
3. 在线索化二叉树中，t 所指结点没有左子树的充要条件是B __。
A. t —＞left=NULLB. t —＞ltag=1C. t —＞ltag=1且t —＞left=NULLD. 以上都不对4. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法_B __。
（A）（B）（C）（D）图8.7 4棵二叉树（A）（B）（C）图8.8 4棵二叉树A. 正确B. 错误5. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法__A__。
A. 正确B. 错误6. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法___B_。
A. 正确B. 错误7. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为__B__。
A. 2hB. 2h-1C. 2h+1D. h+1 a8. 如图8.9所示二叉树的中序遍历序列___B_。
A. abcdgefB. dfebagcC. dbaefcgD. defbagc图8.9 一棵二叉树9. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是D____。
A. acbedB. decabC. deabcD. cedba10．设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 B 。
A．a在b的右方B．a在b的左方C．a是b的祖先D．a是b的子孙11. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为个。
BA．15 B．16 C．17 D．4712.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是D___ _。
江南大学网络教育第一阶段练习题考试科目:《数据结构》第章至第章（总分100分）__________学习中心（教学点）批次：层次：专业：学号：身份证号：姓名：得分：一单选题 (共10题，总分值20分，下列选项中有且仅有一个选项符合题目要求，请在答题卡上正确填涂。
)1. 设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则删除一个结点的操作是（C ）。
（2 分）A. rear=front->nextB. rear=rear->nextC. front=front->nextD. front=rear->next2. 下列说法中错误的是（B ）。
（2 分）A. 数据对象是数据的子集B. 数据元素间关系在计算机中的映象即为数据的存储结构C. 非顺序映象的特点是借助指示元素存储地址的指针来表示数据元素间逻辑关系D. 抽象数据类型指一个数学模型及定义在该模型上的一组操作3. 下列不属算法特性的是（D ）。
（2 分）A. 有穷性B. 确定性C. 零或多个输入D. 健壮性4. 判定一个栈顶指针为S且不带头结点的链栈为空栈的条件是（ D）。
（2 分）A. SB. S->nextC. S->next==NULLD. !S5. 在长为n的顺序表中删除一个数据元素，平均需移动（ D）个数据元素。
（2 分）A. nB. n-1C. n/2D. (n-1)/26. 设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则判定该队中只有一个结点的条件是（C ）。
（2 分）A. front->nextB. rear->nextC. front==rearD. front!=rear第1页/共5页。
江南大学网络教育第三阶段练习题考试科目:《数据结构》第章至第章（总分100分）__________学习中心（教学点）批次：层次：专业：学号：身份证号：姓名：得分：一单选题 (共10题，总分值20分，下列选项中有且仅有一个选项符合题目要求，请在答题卡上正确填涂。
)1. m阶Ｂ树中的一个分支结点最多含（D）个关键字。
（ D）（2 分）A. m-1B. mC. [m/2]D. [m/2]+12. 将两个各有n个元素的有序表归并成一个有序表，最少进行（ C）次比较。
（2 分）A. nB. 2n-1C. 2nD. n-13. 下述文件中适合于磁带存储的是（ C ）。
（2 分）A. 顺序文件B. 索引文件C. 散列文件D. 多关键字文件4. 外部排序是指（ B ）。
（2 分）A. 在外存上进行的排序方法B. 不需要使用内存的排序方法C. 数据量很大，需要人工干预的排序方法D. 排序前后数据在外存，排序时数据调入内存的排序方法5. 设哈希表地址范围为0~19，哈希函数H(key)=key%17，使用二次探测再散列法处理冲突。
若表中已存放有关键字值为6、22、38、55的记录，则再放入关键字值为72的记录时，其存放地址应为（ C）。
（2 分）A. 2B. 3C. 7D. 86. ISAM文件和VSAM文件属于（A ）。
（2 分）A. 索引非顺序文件B. 索引顺序文件C. 顺序文件D. 散列文件第1页/共5页。
共6页 第1页 软件技术基础（二） 数据结构（二） 一、选择题 1. 只允许在一端进行插入删除的线性表称为_________. A.栈顶 B.队列 C.堆栈 D.队尾 2. 向顺序栈中压入元素时，______ A.先移动栈顶指针，后存入元素 B. 先存入元素，后移动栈顶指针 C.谁先谁后无关紧要 D.同时进行 3. 对链式存储的线性表_________。 A.可采用顺序查找，但不可采用二分查找 B.可采用二分查找，但不可采用顺序查找 C.顺序查找和二分查找均可采用 D.顺序查找和二分查找均不可采用 4. 线性表L在下列________情况下，适合使用链接结构实现。 A.L中含有大量结点 B.需经常对L表进行删除与插入 C.需经常修改L的结点值 D.L表结点结构复杂 5. 设f和r分别是一个链表的队头和队尾，那么从该队列中删除一个结点的运算是______。 A.r=f->next B.r=r->next C.f=f->next D.f=r->next 6. 设f和r分别是一个链表的队头和队尾，那么从该队列中插入一个结点的运算是______。 A.r=f->next B.r=r->next C.f=f->next D.f=r->next 7. 在有n单元的顺序存储的堆栈中,假定以地址低端(即下标为1的单元)作为栈底,以top作为栈顶指针,
则当做入栈处理时,top的变化为：_____. A.top不变 B. top=top+1 C. top=n D.top=top-1 8. 若进栈序列为1，2，3，4，假定进栈和出栈可以穿插进行，则不可能出栈的序列是_____. A. 1,4,3,2 B. 2,3,4,1 C. 3,1,4,2 D. 3,4,2,1 9. 设栈初始为空，输入序列为：a，b，c，d。经过入栈、入栈、出栈、入栈、出栈、入栈操作之后，栈中的元素(从栈底到栈顶)依次为__________。 A．a，d B.a,c C．b，c D．d,a 10. 对于任何一棵二叉树，若叶子结点个数为n0，度为2的结点个数为n2，则n0=________. A.n2-1 B.n2 C.n2+1 D.2*n2 11. 一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为__________ A.219 B.221 C.229 D.231 12. 深度为6的二叉树上共有___________个叶子结点。 A. 31 B.32 C.63 D.64 13. 将有三棵树的森林转换成一棵二叉树，则第二棵树的根结点是该二叉树根结点的_______的根结点。 A.左子树 B. 左子女的右子树 C.右子树 D.右子女的右子树 14. 将有三棵树的森林转换成一棵二叉树，则第三树的根结点是该二叉树根结点的____的根结点。 A．左子树 B.左子树的右子树 C.右子树 D.右子树的右子树 共6页 第2页
15. 假定一棵二叉树的结点数为18，则它的最小深度为__________. A.18 B.9 C.5 D.3 16. 在具有size单元的顺序存储的循环队列中，假定front和rear分别指示队列中第一个元素和最后一个元素的下一个位置，则判断队空的条件是：_______. A.front+1== rear B.front==0 C. front== rear D.front==rear+1 17. 在由m个单元组成的循环队列中，队首指针F指示队列中首元素的前一个位置，队尾指针R指示队列中最后一个元素，则判断队满的条件是___________。 A.F=(R+1)%m B.F=R C.(F+1)%m=R D.R%m+1=F 18. 链栈与顺序栈相比，有一个比较明显的优点是________ A．插入操作更加方便 B．通常不会出现栈满的情况 C．不会出现栈空的情况 D．删除操作更加方便 19. 如果n1和n2是二叉树T中两个不同结点，n2是n1的后代，那么按________遍历二叉树T时，结点n2一定比结点n1先被访问。 A.先序 B.中序 C.后序 D.逆中序 20. 一棵二叉树具有9个叶子结点。且非叶子结点都是度为2的结点，则这棵二叉树共有_________结点。 A.17 B.18 C.19 D.20 21. 具有三个结点的二叉树的基本形态有________种。
A.5 B.4 C.3 D.2 22. 以下_______不是队列的基本操作。 A．从队尾插入一个新元素 B.从队列中删除第i个元素 C．判断一个队列是否为空 D。读取队头元素的值。 23. 在树结构中，如果结点A有3个兄弟，而且B是A的双亲，则B的度是________。 A．3 B．1 C．4 D5． 24. 线性表是________ A．一个有限序列，可以为空 B．一个有限序列，不能为空 C．一个无限序列，可以为空 D．一个无限序列，不能为空 25. 线性表采用链式存储时，其地址________ A．必须是连续的 B。部分地址必须是连续的 C．一定是不连续的 D．连续与否均可以 26. 一维数组和线性表的区别是________。 A．前者长度固定 ，后者长度可变 B。后者长度固定 ，前者长度可变 C．两者长度均固定 D．两者长度均可变 27. 数据结构中，与所使用的计算机无关的是数据的________结构. A.存储 B.物理 C.物理和存储 D.逻辑
28. 链表不具有的特点是________。 共6页 第3页
A．随机访问 B．不必事先估计存储空间 C．插入删除时不需移动元素 D．所需空间与线性表成正比 29. 二叉树有多种形式，若深度为K，且有2K-1个结点的二叉树称为__________。 A.完全二叉树 B.满二叉树 C.顺序二叉树 D.排序树 30. 已知某二叉树的前序序列是ABDC，中序序列是DBAC，问它的后序序列是_____。 A. ADBC B. DBCA C. CABD D.DCBA 31. 上溢现象通常出现在________. A.顺序栈的入栈操作过程中 B.顺序栈的出栈操作过程中 C.链栈的入栈操作过程中 D.链栈的出栈操作过程中 32. 引起循环队列队头位置发生变化的操作是____________. A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 33. 除第一层外，满二叉树中每一层结点个数是上一层结点个数的_________. A.1/2 倍 B. 1 倍 C. 2 倍 D．3 倍 34. 在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系___________. A.不一定相同 B.都相同 C.都不相同 D.互为逆序 35. 一棵二叉树中共有10个叶子结点与20个度为1的结点，则该二叉树中的总结点数为__________ A.30 B.31 C.39 D.40 36. 栈结构通常采用的两种存储结构是_____________ A．顺序存储结构和链表存储结构 B．链表存储结构和数组 C．线性存储结构和非线性存储结构 D．散列方式和索引方式 37. 链式存储的存储结构所占存储空间________。 A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B．只有一部分，存放结点值 C．只有一部分，存储表示结点间关系的指针 D．分两部分，一部分存放结点值，另一部分存放结点所占单元数 38. 只允许在二端进行插入删除的线性表称为_________. A.栈顶 B.队列 C.堆栈 D.队尾 39. 堆栈结构的特点是________。 A．同时进出 B．先进先出 C．后进后出 D．后进先出 40. 网状数据模型___________. A.允许有一个以上的结点无双亲 B．有且只有一个结点无双亲 C．除了一个根结点，其他结点只有一个双亲 D．每一个结点的子女不能多于一个 41. 学校中学生作为一个实体与他的学习课程（另一个实体）之间的联系是__________. A．一对一 B．多对多 C．一对多 D．多对一 42. 链表中进行___________操作的效率比顺序表中高。
A.二分查找和删除 B.插入和删除 C.二分查找和插入 D.快速查找 43. 当栈中的元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为______. A.n-1 B.n C.n+1 D.n/2 共6页 第4页
44. 栈和队列____________. A. 的共同点都是先进后出 B. 的共同点都是先进先出 C. 的共同点是只允许在端点处插入和删除元素 D. 没有共同点
二.填空题 45. 有一棵顺序二叉树，有编号为22结点的双亲，其左孩子在____编号位置上。 46. 在深度为7的满二叉树中，度为2的结点个数为__________。 47. 按“先进后出”原则组织数据的数据结构是_____________。 48. 需要对线性表进行插入和删除运算，则最好采用_________存储结构。 49. 若一个栈的输入序列是1，2，3„.，n，输出序列的第一个元素是n，则第I个输出元素是________。 50. 允许在一端进行插入,而在一端进行删除的线性表称为_________. 51. 对于任一棵二叉树,若叶子结点个数为n0,度为2 的结点数为n2,则n2=________. 52. 一个具有22个叶子结点的二叉树，其度数为2的结点数是_______。 53. 在二叉树上的第3层上至多有__________个结点. 54. 采用二叉链表存储二叉树时，具有10个结点的二叉树，则有_______个指针域为空。 55. 一棵二叉树其终端结点为10，则度为2的结点数有_______个。 56. 深度为K的满二叉树有__________个结点.（K>=1） 57. 顺序表是一种随机存取的存储结构，而单链表是一种________的存储结构. 58. 需要对线性表经常进行插入和删除运算，则最好采用_________存储结构。 59. 为了最快的存取某元素，宜用顺序结构；为了方便地插入一个元素，宜用_____________. 60. 设有n个节点的完全二叉树，顺序存放在数组A[1..n]中，对任一个节点A[i]，若 A[i]有左子女，则左子女是数组A的________ . 61. 设有n个节点的完全二叉树，顺序存放在数组A[1..n]中，对任一个节点A[i]，若 A[i]有父母，则父母是数组A的________ . 62. 链式存储结构的特点是借助 _______ 来表示数据元素之间的逻辑关系。 63. 树形结构中节点a有4个兄弟，b是a的双亲，则b的度为________ 64. 二元组（D，R）来表示数据结构，那么D指数据元素，R指_____________。 65. 二叉排序树进行中序遍历时，得到的结点序列是一个_______________. 66. 在树中，一个结点的直接子结点的个数称为该结点的_______. 67. 数据库的层次模型有且仅有一个结点无双亲，而网状模型一定会有 ___________ 结点无双亲，这是与层次模型的重要区别。
