最新数据结构练习3答案优秀文档
- 格式：pdf
- 大小：193.33 KB
- 文档页数：11
下载文档原格式
合集下载
最新数据结构习题课3讲解学习
0 50 1 10 3 -30 1 20 3 -60 35
a[0] 0 0 50 a[1] 1 0 10 a[2] 1 2 20 a[3] 3 0 -30 a[4] 3 2 -60 a[5] 3 3 5
03 10 22 31
num
00 13 23 35
pos
0
TP3[处理三元组表]
3
FOR i ← 0 TO t-1 DO
20
A[4] 3
2
-60
A[5] 3 3
5
B[4] 2
3
-60
B[5] 3 3
5
算法的关键是求出A中元素在B中的位置
Bnubmer = 0
FOR i=0 TO Cols(A) DO
FOR j=0 TO t DO
IF col(A[j])=i Then
(row(B[Bnumber])=i
col(B[Bnumber])=row(A[j])
算法: TRANSPOSE(A. B)
TP1[初始化] /*声明A的转置矩阵B，使得B的行数等于 A的列数，B的列数等于A的行数，B中非 0元素的个数等于A中非0元素的个数*/ n←Rows(B)←Cols(A). Cols (B)←Rows(A). t←Count(B)← Count(A).
TP2
row(B[k]) ←col(A[i]).
val(B[k]) ← val(A[i]).
pos[p]← pos[p]+1 ).
a[0] 0 0 50 a[1] 1 0 10 a[2] 1 2 20 a[3] 3 0 -30 a[4] 3 2 -60 a[5] 3 3 5
0 0 50 0 1 10
2 1 20
数据结构习题三（答案）
哈夫曼编码： a:11 b:101 c:010 d:1001 e:011 f:00 g:1000 2) 等长编码至少需要3 bit 哈夫曼编码WPL=0.31*2+0.16*3+0.10*3+0.08*4+0.11*3+0.20*2+0.04*4=2.61 压缩率=1-2.61/3=13% 4.程序设计题 1)创建一任意二叉树，统计某子树下值为奇数和偶数结点的个数。 #define INT #include"c1.h" #ifdef CHAR typedef char TElemType; TElemType Nil=' '; /* 字符型以空格符为空*/ #endif #ifdef INT typedef int TElemType; TElemType Nil=0; /* 整型以0为空*/ #endif #include"c6-2.h" #include"bo6-2.c" void GetLeafCounts(BiTree T,int *n,int *m) {
文档之家的所有文档均为用户上传分享文档之家仅负责分类整理如有任何问题可通过上方投诉通道反馈
数据结构习题三（答案）
数据结构习题(三) 学号________ 姓名_______ 课堂号(_________) 1.选择题 1)若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B ）A．9 B．11 C．15 D．不确定 2)设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林 F对应的二叉树根结点的右子树上的结点个数是（ D ） A．M1 B．M1+M2 C．M3 D．M2+M3 3)二叉树的第I层上最多含有结点数为（ C ） A．2I B． 2I-1-1 C． 2I-1 D．2I -1 4)在一棵高度为k的满二叉树中，结点总数为（ C ） A．2k-1 B．2k C．2k-1 D．?log2k?+1 5)利用二叉链表存储树，则根结点的右指针是（ C ）。 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 6)已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果 为（ A ）。 A．CBEFDA B． FEDCBA C． CBEDFA D．不定 7)n个结点的线索二叉树上含有的线索数为（ C ） A．2n B．n－l C．n＋l D．n 8)由3 个结点可以构造出多少种不同的二叉树？（ D ） A．2 B．3 C．4 D．5 9)某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E。二叉树对应的森林 包括多少棵树（ B ） A．l B．2 C．3 D．概念上是错误的 10)设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针 域为空的结点有（ C ）个。 A． n-1 B．n C． n+1 D． n+2 11)下面几个符号串编码集合中，不是前缀编码的是（ B ）。 A．{0,10,110,1111} B．{11,10,001,101,0001} C．{00,010,0110,1000} D．{b,c,aa,ac,aba,abb,abc} 2.填空题 12)树在计算机内的表示方式有__双亲表示法_，___孩子表示法___，___孩子兄弟表示法/ 二叉链表表示法_____。 13)在二叉树中，指针p所指结点为叶子结点的条件是_p->lchild==NULL && p->rchild==NULL________________。
北语网院20春《数据结构》作业_3答案
(单选)1：树转换成二叉树后，以下结论正确的是（）。
A：树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B：树的先根遍历序列与其对应的二叉树的中序遍历序列相同
C：树的后根遍历序列与其对应的二叉树的后序遍历序列相同
D：以上都不对
正确答案：A
(单选)2：如果对线性表的操作只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用___。
A：只有表头指针没有表尾指针的循环单链表
B：只有表尾指针没有表头指针的循环单链表
C：非循环双链表
D：循环双链表
正确答案：B
(单选)3：串的长度是指___。
A：串中所含不同字母的个数
B：串中所含字符的个数
C：串中所含不同字符的个数
D：串中所含非空格字符的个数
正确答案：B
(单选)4：设某棵二叉树中有2000个结点，则该二叉树的最小高度为___。
A：9
B：10
C：11
D：12
正确答案：C
(单选)5：将一株有100个节点的完全二叉树从上到下，从左到右依次进行编号，根节点的编号为1，则编号为49的节点的左孩子编号为（）。
B：98
C：89
D：50
E：没有孩子
正确答案：B
(单选)6：在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的___倍。
A：1/2
B：1
C：2
D：4
正确答案：B。
国家开放大学电大《数据结构》网络课形考任务3作业及答案
国家开放大学电大《数据结构》网络课形考任务3作业及答案形考任务3一、单项选择题（每小题2分，共38分）题目1假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）。
选择一项：B. 16题目2二叉树第k层上最多有（）个结点。
选择一项：A. 2k-1题目3将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（）。
选择一项：C. 34题目4如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（）。
选择一项：B. 哈夫曼树题目5在一棵度具有5层的满二叉树中结点总数为（）。
选择一项：C. 31题目6一棵完全二叉树共有6层，且第6层上有6个结点，该树共有（）个结点。
选择一项：B. 37题目7利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子结点中的最长带权路径长度为（）。
选择一项：A. 18在一棵树中，（）没有前驱结点。
选择一项：A. 树根结点题目9设一棵采用链式存储的二叉树，除叶结点外每个结点度数都为2，该树结点中共有20个指针域为空,则该树有（）个叶结点。
选择一项：B. 10题目10在一个图G中，所有顶点的度数之和等于所有边数之和的（）倍。
选择一项：A. 2题目11邻接表是图的一种（）。
选择一项：A. 链式存储结构题目12图的深度优先遍历算法类似于二叉树的（）遍历。
选择一项：A. 先序题目13已知下图所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。
选择一项：D. V1V2V4V8V5V3V6V7题目14已知如下图所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。
选择一项：D. aecbdf题目15图状结构中数据元素的位置之间存在（）的关系。
选择一项：B. 多对多在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（）。
数据结构练习题(含答案)(DOC)
数据结构练习题习题1 绪论单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。
①A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象②A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。
①A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象②A．操作Ｂ．映象Ｃ．存储Ｄ．关系3. 在数据结构中，从逻辑上可以把数据结构分成。
）A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构4. 算法分析的目的是①，算法分析的两个主要方面是②。
① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性② A. 空间复杂性和时间复杂性 B. 正确性和简明性C. 可读性和文档性D. 数据复杂性和程序复杂性5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。
① A. 计算方法 B. 排序方法C. 解决问题的有限运算序列D. 调度方法!② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性填空题（将正确的答案填在相应的空中）1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。
2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。
3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。
4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。
5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。
数据结构练习题第三章栈、队列和数组习题及答案
第三章栈、队列和数组一、名词解释：1.栈、栈顶、栈底、栈顶元素、空栈2.顺序栈3.链栈4.递归5.队列、队尾、队头6.顺序队7.循环队8.队满9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上（下）三角矩阵二、填空题：1.栈修改的原则是_________或称________，因此，栈又称为________线性表。
在栈顶进行插入运算，被称为________或________，在栈顶进行删除运算，被称为________或________。
2.栈的基本运算至少应包括________、________、________、________、________五种。
3.对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“________”。
4.对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。
5.一般地，栈和线性表类似有两种实现方法，即________实现和________实现。
6.top=0表示________，此时作退栈运算，则产生“________”；top=sqstack_maxsize-1表示________，此时作进栈运算，则产生“________”。
7.以下运算实现在顺序栈上的初始化，请在________处用适当的句子予以填充。
int InitStack(SqStackTp *sq){ ________;return(1);}8.以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。
Int Push(SqStackTp *sq,DataType x){ if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);}else{________________:________________=x;return(1);}}9.以下运算实现在顺序栈上的退栈，请在________________用适当句子予以填充。
数据结构练习题及答案
数据结构练习题（一）一、单选题1.栈和队列的共同特点是( )。
A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( )。
A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中( )是非线性结构。
A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在（）位置。
脚注(10)表示用10进制表示。
A．688 B．678 C．692 D．6965.树最适合用来表示( )。
A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( )。
A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )。
A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个。
A．1 B．2 C．3 D．49.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
A.5B.6C.7D.8二、填空题1.通常从四个方面评价算法的质量：_________、_________、_________和_________。
2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。
3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为__________个，树的深度为___________，树的度为_________。
最新版《数据结构》各章习题及答案
最新版《数据结构》各章习题及答案第一章绪论一、选择题1.组成数据的基本单位是（）（A）数据项（B）数据类型（C）数据元素（D）数据变量2.数据结构是研究数据的（）以及它们之间的相互关系。
（A）理想结构，物理结构（B）理想结构，抽象结构（C）物理结构，逻辑结构（D）抽象结构，逻辑结构3.在数据结构中，从逻辑上可以把数据结构分成（）（A）动态结构和静态结构（B）紧凑结构和非紧凑结构（C）线性结构和非线性结构（D）内部结构和外部结构4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。
① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像② （A）结构（B）关系（C）运算（D）算法5.算法分析的目的是（）。
（A）找出数据结构的合理性（B）研究算法中的输入和输出的关系（C）分析算法的效率以求改进（D）分析算法的易懂性和文档性6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5 个特性。
① （A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法② （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性（C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性二、判断题1.数据的机内表示称为数据的存储结构。
（）2.算法就是程序。
（）3.数据元素是数据的最小单位。
（）4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。
（）5.算法的时间复杂度取决于问题的规模和待处理数据的初态。
（）三、填空题1.数据逻辑结构包括________、________、_________ 和__________ 四种类型,其中树形结构和图形结构合称为_____ 。
2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______ 个前驱结点；最后一个结点______后续结点,其余每个结点有且只有 _______ 个后续结点。
3.在树形结构中,树根结点没有_______ 结点,其余每个结点有且只有_______个前驱结点；叶子结点没有 ________ 结点,其余每个结点的后续结点可以_________。
2021年小学信息技术教师数据结构练习题及参考答案(三)
2021年小学信息技术教师专业技能数据结构练习题及参考答案（三）1.每个结点只存储一个数据元素，存储结点存放在连续的存储空间，该存储方式是（ A ）存储方式。
A．顺序 B. 链式 C. 索引 D. 散列2.对于顺序表的优缺点，下面说法错误的是（ C ）。
A．无需为表示节点间的逻辑关系而增加额外的存储空间。
B．可以方便的随机存取表中的任一结点。
C．删除和插入运算较方便。
D.由于顺序表要求占用连续的空间，存储分配只能预先进行（静态分配）。
3.下面( B )的时间复杂性最好，即执行时间最短。
A.O（n）B.O（log2n）C.O（nlog2n）D.O（n2）4.在带头结点的单链表h中，若要向表头插入一个由指针p所指向的结点，则执行（ D ）。
A. h=p, p->next=hB. p->next=h, h=pC. p->next=h, p=hD. p->next=h->next, h->next=p5.与线性表的链接存储相符的特性是( A )。
A．插入和删除操作灵活B．可随机访C．存储空间静态分配D．不需另外开辟空间来保存元素间的关系6.用某种排序方法对序列（25，84，21，47，15，27，68，35，20）进行排序，记录序列的变化情况如下： 25 84 21 47 15 27 68 35 20 20 15 21 25 4727 68 35 84 15 20 21 25 35 27 47 68 84 15 20 21 25 27 35 47 68 84 则采用的排序方法是（ C ）。
A．直接选择排序 B. 冒泡排序 C. 快速排序 D. 二路归并排序7.下列关于线性表的叙述中，不正确的是( C )。
A．线性表是n个结点的有穷序列B．线性表可以为空表C．线性表的每一个结点有且仅有一个前趋和一个后继D．线性表结点间的逻辑关系是1:1的联系8.将长度为m的单链表链接在长度为n的单链表之后的算法的时间复杂度为( B )。
数据结构练习题 第三章 栈、队列和数组 习题及答案
第三章栈、队列和数组一、名词解释：1.栈、栈顶、栈底、栈顶元素、空栈2.顺序栈3.链栈4.递归5.队列、队尾、队头6.顺序队7.循环队8.队满9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上（下）三角矩阵二、填空题：1.栈修改的原则是_________或称________，因此，栈又称为________线性表。
在栈顶进行插入运算，被称为________或________，在栈顶进行删除运算，被称为________或________。
2.栈的基本运算至少应包括________、________、________、________、________五种。
3.对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“________”。
4.对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。
5.一般地，栈和线性表类似有两种实现方法，即________实现和________实现。
6.top=0表示________，此时作退栈运算，则产生“________”；top=sqstack_maxsize-1表示________，此时作进栈运算，则产生“________”。
7.以下运算实现在顺序栈上的初始化，请在________处用适当的句子予以填充。
int InitStack(SqStackTp *sq){ ________;return(1);}8.以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。
Int Push(SqStackTp *sq,DataType x){ if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);}else{________________:________________=x;return(1);}}9.以下运算实现在顺序栈上的退栈，请在________________用适当句子予以填充。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
数据结构练习（三）参考一、选择题1.顺序查找法适合于存储结构为的线性表A）哈希存储 B）顺序存储或链式存储C）压缩存储 D）索引存储2.一个长度为100的已排好序的表，用二分查找法进行查找，若查找不成功，至少比较________次。
A）9 B）8 C）7 D）63.采用顺序查找方法查找长度为n的线性表时，平均比较次数为。
A）n B）n/2 C）（n+1）/2 D）（n-1）/24.对线性表进行折半查找时，要求线性表必须。
A）以顺序方式存储B）以顺序方式存储，且结点按关键字有序排列C）以链表方式存储D）以链表方式存储，且结点按关键字有序排列5.采用二分查找法查找长度为n的线性表时，每个元素的平均查找长度为。
A）O（n2）B）O（nlog2n）C）O（n）D）O（log2n）6.有一个长度为12的有序表R[0…11]，按折半查找法对该表进行查找，在表内各元素等概率查找情况下查找成功所需的平均比较次数为。
A）35/12 B）37/12 C）39/12 D）43/127.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，99}，当采用折半查找法查找关键字为82的元素时，次比较后查找成功。
A）1 B.2 C）4 D）88.当采用分块查找时，数据的组织方式为。
A）数据分成若干块，每块内存数据有序B）数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C）数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D）数据分成若干块，每块（出最后一块外）中的数据个数需相同9.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应有个结点最佳。
A）10 B）25 C）6 D）62510.不能生成右图所示二叉排序树的关键字序列是_____。
A）45312 B）42531 C）45213 D）4231511.按____遍历二叉排序树，可以得到按值递增或递减次序的关键码序列。
A）先序B）中序C）后序D）层序12.在一棵平衡二叉树中，每个结点的平衡因子的取值范围是。
A）-1—1 B）-2—2 C）1—2 D）0—113.具有5层结点的AVL树至少有个结点A）10 B）12 C）15 D）1714.在含有15个结点的平衡二叉树上，查找关键字为28的结点，则依次比较的关键字可能是。
A）30，36 B）38，48，28C）48，18，38，28D）60，30，50，40，38，3615.一棵深度为k的平衡二叉树，其每个非叶子结点的平衡因子均为0，则该树共有个结点。
A）2k-1-1 B）2k-1 C）2k-1 +1D）2k-116.查找效率最高的二叉排序树是。
A．所有结点的左子树都为空的二叉排序树B．所有节点的右子树都为空的二叉排序树C．平衡二叉树D．没有左子树的二叉排序树17.下面关于B-树和B+树的叙述中，不正确的结论是。
A）B-树和B+树都能有效地支持顺序查找B）B-树和B+树都能有效地支持随机查找C）B-树和B+树都是平衡的多分支树D）B-树和B+树都可用于文件索引结构18.设有n个关键字，哈希查找法的平均查找长度是。
A）O（1）B）O（n）C）O（log2n）D）O（n2）19.将10个元素散列到100000个单元的哈希表，则产生冲突。
A）一定会B）一定不会C）仍可能会D）以上都不对20.设哈希表长 m=14，哈希函数H（key）=key Mod 11.表中已有4个结点H （15）=4，H（38）=5，H（61）=6，H（84）=7，其余地址为空，如用二次探测再散列法处理冲突，则关键字为49的结点的地址是。
A）8 B）3 C）5 D）921.假设有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入哈希表中，至少要进行次探查。
A）k-1 B）k C）k+1 D）k（k+1）/222.若采用链地执法构造哈希表，哈希函数为H（key）=key Mod 17，则需（1）个链表，这些链表的首指针构成一个指针数组，该数组的下标范围为（2）。
（1）A）17 B）13 C）16 D）任意（2）A）0—17 B）1—17 C）0—16 D）1—1623.直接插入排序在最好情况下的时间复杂度为。
A）O（n）B）O（nlog2n）C）O（log2n）D）O（n2）24.稳定的排序算法是。
A）直接插入排序B）直接选择排序 C）堆排序D）快速排序25.数据序列{8，9，10，4，5，6，20，1，2}只能是算法的两趟排序后的结果。
A）直接选择排序B）冒泡排序C）直接插入排序D）堆排序26.对数据序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排序变为{9，15，7，8，20，-1，4}，则采用的是算法。
A）直接选择排序B）冒泡排序C）直接插入排序D）堆排序27.以下排序方法中，在初始序列已基本有序的情况下，排序效率最高。
A）归并排序B）直接插入排序C）快速排序D）堆排序28.不稳定的排序方法是。
A）冒泡排序B）直接插入排序C）希尔排序 D）归并排序29.以下排序算法中，不能保证每趟排序至少能将一个元素放到其最终位置上。
A）快速排序B）希尔排序 C）堆排序D）冒泡排序30.在以下排序方法中,关键字比较的次数与记录的初始排列次序无关的是。
A）希尔排序B）冒泡排序C）插入排序D）直接选择排序31.在排序算法中，每次从未排序的记录中选取最小（或最大）关键字的记录，加入到已排序记录的末尾，该排序方法是。
A）希尔排序B）冒泡排序C）插入排序D）直接选择排序32.采用直接选择排列，比较次数与移动次数分别是。
A）O（n），O（log2n）B）O（log2n），O（n2）C）O（n2），O（n）D）O（n log2n），O（n）33.以下序列不是堆的是。
A）{100，85，98，77，80，60，82，40，20，10，66}B）{100，98，85，82，80，77，66，60，40，20，10}C）{10，20，40，60，66，77，80，82，85，98，100}D）{100，85，40，77，80，60，66，98，82，10，20}34.堆排序是（1）类排序，堆排序平均时间复杂度和需要附加的存储空间复杂度分别是（2）。
（1）.A）插入B）交换C）归并D）选择（2）.A）O（n2）和O（1）B）O（nlog2n）和O（1）C）O（nlog2n）和O（n）D）O（n2）和O（n）35.对n个记录的文件进行堆排序，最坏情况下的执行时间是。
A）O（log2n）B）（n）C）O（nlog2n）D）O（n2）36.设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用排序法。
A）冒泡排序B）快速排序 C）堆排序D）基数排序37.在非空m阶B－树上，除根结点以外的所有其他非终端结点。
A）至少有2/m棵子树m棵子树B）至多有2/C）至少有2/m棵子树m棵子树 C）至少有2/38.对于哈希函数H(key)=key%13，被称为同义词的关键字是________。
A）35和41 B）23和39 C）15和44 D）25和51 39.堆的形状是一棵________。
A）二叉排序树B）满二叉树C）完全二叉树D）不是二叉树40.以下法在数据基本有序时效率最好。
A）快速排序B）冒泡排序C）堆排序D）希尔排序41.快速排序在情况下最不利于发挥其长处。
A）要排序的数据量太大B）要排序的数据中含有多个相同值C）要排序的数据个数为奇数D）要排序的数据已基本有序42.下列序列中，__是执行第一趟快速排序后得到的序列(关键字为字符串)A. [da,ax,eb,cd,bb]ff[ha,gc]B. [cd,eb,ax,da]ff[ha,gc,bb]C. [gc,ax,eb,cd,bb]ff[da,ha]D. [ax,bb,cd,da]ff[eb,gc,ha]43.一个记录的关键字为{46，79，56，38，40，84}，采用快速排序以第一个记录为基准得到的第一次划分结果为________。
A）{38,40,46,56,38,79,84} B）{40,38,46,79,56,84}C）{40,38,46,56,79,84} D）{40,38,46,56,79}44.对下列关键字序列用快速排序法进行排序时，速度最快的情形是____。
A）{21，25，5，17，9，23，30} B）{25,23,30,17,21,5,9}C）{21,9,17,30,25,23,5} D）{5,9,17,21,23,25,30}45.下列排序方法中，在一趟结束后不一定能选出一个元素放在其最终位置上。
A）直接选择排序B）冒泡排序C）归并排序D）堆排序46.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。
A）n B）2n-1 C）2n D）n-1二、填空题：1.在n个记录的有序顺序表中进行折半查找,最大的比较次数是log2n +1 。
2.设线性表{a1，，，a2，，…，a500}的元素的值从小到大排列，对一个给定的K的值用二分法查找线性表，在查找不成功的情况下至多需要比较log2n +1 次3.在直接插入排序、希尔排序、直接选择排序、快速排序、堆排序和归并排序中，平均比较次数最少的排序方法是快速排序。
4.一棵深度为h的B-树，任一个叶子结点所处的层数为 h ，当向B-树插入一个新关键字时，为检索插入位置需读取 h-1 个结点。
5.评价哈希表好坏的标准是哈希表的均匀性。
6.在各种查找方法中，其平均查找长度与结点个数n无关的查找方法是哈希表查找。
7.设用希尔排序对数序{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的不长（也称增量序列）依次是4、2、1，则排序需 3 趟，写出第一趟结束后，数序中数据的排列次序是 10,7,-9,0,47,23,1,8,98,36 。
三、判断题1.顺序查找法适用于存储结构为顺序或链式存储的线性表2.顺序查找方法只能在顺序存储结构上进行3.折半查找可以在有序的双向链表上进行4.分块查找的效率与线性表被分成多少块有关5.在二叉排序树中，每个结点的关键字都比左孩子关键字大，比右孩子关键字小6.每个结点的关键字都比左孩子关键字大，比右孩子关键字小，这样的二叉树都是二叉排序树7.在二叉排序树中，新插入的关键字总是处于最低层8.在二叉排序树中，新结点总是作为叶子结点来插入的9.二叉排序树的查找效率和二叉排序树的高度有关10.在平衡二叉排序树中，每个结点的平衡因子值都是相等的11.在平衡二叉排序树中，以每个分支结点为根的子树都是平衡的。