数据结构与算法总复习题市公开课一等奖省赛课微课金奖课件

数据结构第一章第1页一、填空题1.数据结构是一门研究非数值计算程序设计问题中计算机操作对象以及它们之间关系和运算等学科。第2页2.数据结构被形式地定义为（D,R），其中D是数据元素有限集合，R是D上关系有限集合。3.数据结构包含数据逻辑结构、数据存放结构、和数据运算这三个方面内容。第3页4.数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。5.线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。第4页6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最终一个结点没有后续结点，其余每个结点有且只有1个后续结点。第5页7.在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点后续结点数能够任意多个。第6页8.在图形结构中，每个结点前驱结点数和后续结点数能够任意多个。9．数据存放结构可用四种基本存放方法表示，它们分别是次序、链式、索引和散列。第7页10.数据运算最惯用有5种，它们分别是插入、删除、修改、查找、排序。11.一个算法效率可分为时间效率和空间效率。第8页二、单项选择题（B）1.非线性结构是数据元素之间存在一个：A）一对多关系B）多对多关系C）多对一关系D）一对一关系（C）2.数据结构中，与所使用计算机无关是数据

结构；A)存放B)物理C)逻辑D)物理和存放第9页（C）3.算法分析目标是：A)找出数据结构合理性B)研究算法中输入和输出关系C)分析算法效率以求改进D)分析算法易懂性和文档性第10页（A）4.算法分析两个主要方面是：A)空间复杂性和时间复杂性B)正确性和简明性C)可读性和文档性D)数据复杂性和程序复杂性第11页（C）5.计算机算法指是：A)计算方法B)排序方法C)处理问题有限运算序列D)调度方法第12页（B）6.计算机算法必须具备输入、输出和

等5个特征。A)可行性、可移植性和可扩充性B)可行性、确定性和有穷性C)确定性、有穷性和稳定性D)易读性、稳定性和安全性第13页三、简答题1.数据结构和数据类型两个概念之间有区分吗？答：简单地说，数据结构定义了一组按一些关系结合在一起数组元素。数据类型不但定义了一组带结构数据元素，而且还在其上定义了一组操作。第14页2.简述线性结构与非线性结构不一样点。答：线性结构反应结点间逻辑关系是一对一，非线性结构反应结点间逻辑关系是多对多。第15页3.算法定义和特征。算法是处理特定问题有限指令序列。特征：有限性、确定性、可行性、有0个或多个输入数据、有1个或多个输出结果。第16页

4.数据结构逻辑结构有哪四类？集合结构、线性结构、树形结构、图形结构线性结构前驱与后继之间为一对一关系，非线性结构前驱与后继之间通常为一对多或多对多关系。第17页第二章线性表习题1次序表中逻辑上相邻元素物理位置

相邻。单链表中逻辑上相邻元素物理位置

相邻。第18页一定不一定第19页2在单链表中，除了首元结点外，任一结点存放位置由其直接前驱结点链域值指示。第20页3.线性表中结点间关系是一对一。第21页判断题（）1.链表每个结点中都恰好包含一个指针。答：错误。链表中结点可含多个指针域，分别存放多个指针。比如，双向链表中结点能够含有两个指针域，分别存放指向其直接前趋和直接后继结点指针。第22页（）2.链表删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续各个单元向前移动。错，链表结点不会移动，只是指针内容改变。第23页（）3.线性表每个结点只能是一个简单类型，而链表每个结点能够是一个复杂类型。错，混同了逻辑结构与物理结构，链表也是线性表！且即使是次序表，也能存放统计型数据。第24页（）4.次序表结构适宜于进行次序存取，而链表适宜于进行随机存取。错，恰好说反了。次序表才适合随机存取，链表恰恰适于“顺藤摸瓜”第25页（）5.次序存放方式优点是存放密度大，且插入、删除运算效率高。错，前二分之一正确，但后二分之一说法错误，那是链式存放优点。次序存放方式插入、删除运算效率较低，在表长为n次序表中，插入和删除一个数据元素，平均需移动表长二分之一个数数据元素。第26页（）8.线性表在次序存放时，逻辑上相邻元素未必在存放物理位置次序上相邻。错误。线性表有两种存放方式，在次序存放时，逻辑上相邻元素在存放物理位置次序上也相邻。第27页单项选择题（）1．数据在计算机存放器内表示时，物理地址与逻辑地址相同而且是连续，称之为：（A）存放结构（B）逻辑结构（C）次序存放结构（D）链式存放结构第28页C第29页（）2.一个向量第一个元素存放地址是100，每个元素长度为2，则第5个元素地址是

（A）110（B）108（C）100（D）120第30页B第31页（）5.链接存放存放结构所占存放空间：A分两部分，一部分存放结点值，另一部分存放表示结点间关系指针B只有一部分，存放结点值C只有一部分，存放表示结点间关系指针D分两部分，一部分存放结点值，另一部分存放结点所占单元数

第32页A第33页（）6.链表是一个采取

存放结构存放线性表；（A）次序（B）链式（C）星式（D）网状第34页B第35页（）7.线性表若采取链式存放结构时，要求内存中可用存放单元地址:（A）必须是连续（B）部分地址必须是连续（C）一定是不连续（D）连续或不连续都能够第36页D第37页（）8．线性表在

情况下适合用于使用链式结构实现。（Ａ）需经常修改线性表中结点值（Ｂ）需不停对线性表进行删除插入（Ｃ）线性表中含有大量结点（Ｄ）线性表中结点结构复杂第38页B第39页（）10．设a1、a2、a3为3个结点，整数P0，3，4代表地址，则以下链式存放结构称为（Ａ）循环链表（Ｂ）单链表（Ｃ）双向循环链表（Ｄ）双向链表第40页B第41页简答题1.【严题集2.3②】试比较次序存放结构和链式存放结构优缺点。在什么情况下用次序表比链表好？第42页答：①次序存放时，相邻数据元素存放地址也相邻（逻辑与物理统一）；要求内存中可用存放单元地址必须是连续。优点：存放空间利用率高。缺点：插入或删除元素时不方便。第43页②链式存放时，相邻数据元素可随意存放，但所占存放空间分两部分，一部分存放结点值，另一部分存放表示结点间关系指针优点：插入或删除元素时很方便，使用灵活。缺点：存放空间利用率低。第44页次序表适宜于做查找这么静态操作；链表宜于做插入、删除这么动态操作。若线性表长度改变不大，且其主要操作是查找，则采取次序表；若线性表长度改变较大，且其主要操作是插入、删除操作，则采取链表。第45页第三章第46页1.向量(线性表)、栈和队列都是

结构，能够在向量

位置插入和删除元素；对于栈只能在

插入和删除元素；对于队列只能在

插入和

删除元素。第47页1、向量、栈和队列都是线性结构，能够在向量任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。第48页2.栈是一个特殊线性表，允许插入和删除运算一端称为

。不允许插入和删除运算一端称为

。第49页2.栈是一个特殊线性表，允许插入和删除运算一端称为

栈顶

。不允许插入和删除运算一端称为

栈底

。第50页3.

是被限定为只能在表一端进行插入运算，在表另一端进行删除运算线性表。第51页3.

队列

是被限定为只能在表一端进行插入运算，在表另一端进行删除运算线性表。第52页二、判断正误（判断以下概念正确性，并作出简明说明。）（）1.线性表每个结点只能是一个简单类型，而链表每个结点能够是一个复杂类型。

第53页二、判断正误（判断以下概念正确性，并作出简明说明。）（×）1.线性表每个结点只能是一个简单类型，而链表每个结点能够是一个复杂类型。错，线性表是逻辑结构概念，能够次序存放或链式存放，与元素数据类型无关。第54页（）2.在表结构中最惯用是线性表，栈和队列不太惯用。

第55页（×）2.在表结构中最惯用是线性表，栈和队列不太惯用。错，不一定吧？调用子程序或函数惯用，CPU中也用队列。第56页（）3.栈是一个对全部插入、删除操作限于在表一端进行线性表，是一个后进先出型结构。第57页（√）3.栈是一个对全部插入、删除操作限于在表一端进行线性表，是一个后进先出型结构。第58页（）6.栈和队列是一个非线性数据结构。

第59页（×）6.栈和队列是一个非线性数据结构。错，他们都是线性逻辑结构，栈和队列其实是特殊线性表，对运算定义略有不一样而已。第60页（）7.栈和队列存放方式既可是次序方式，也可是链接方式。

第61页（√）7.栈和队列存放方式既可是次序方式，也可是链接方式。第62页（）8.队是一个插入与删除操作分别在表两端进行线性表，是一个先进后出型结构。第63页（×）8.队是一个插入与删除操作分别在表两端进行线性表，是一个先进后出型结构。 错，后半句不对。第64页（）9.一个栈输入序列是12345，则栈输出序列不可能是12345。

第65页（×）9.一个栈输入序列是12345，则栈输出序列不可能是12345。错，有可能。第66页三、单项选择题（）1.栈中元素进出标准是Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出

第67页三、单项选择题（B）1.栈中元素进出标准是Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出第68页6.【初程P71】从供选择答案中，选出应填入下面叙述

内最确切解答，把对应编号写在答卷对应栏内。设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈或队初始状态都是空。第69页现要进行栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到元素是A，第二次出栈得到元素是B是；类似地，考虑对这四个数据元素进行队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到元素是C，第二次出队得到元素是D。经操作后，最终在栈中或队中元素还有E个。供选择答案：A～D：①a1②a2③a3④a4E：①1②2③3④0第70页答：ABCDE＝2,4,1,2,2第71页第五章1.假设有二维数组A6×8，每个元素用相邻6个字节存放，存放器按字节编址。已知A起始存放位置（基地址）为1000，则数组A体积（存放量）为

；末尾元素A57第一个字节地址为

；若按行存放时，元素A14第一个字节地址为

；若按列存放时，元素A47第一个字节地址为

。第72页1.假设有二维数组A6×8，每个元素用相邻6个字节存放，存放器按字节编址。已知A起始存放位置（基地址）为1000，则数组A体积（存放量）为288B；末尾元素A57第一个字节地址为1282；若按行存放时，元素A14第一个字节地址为(8+4)×6+1000=1072；若按列存放时，元素A47第一个字节地址为(6×7＋4)×6＋1000）＝1276。(注：数组是从0行0列还是从1行1列计算起呢？由末单元为A57可知，是从0行0列开始！)第73页2.三元素组表中每个结点对应于稀疏矩阵一个非零元素，它包含有三个数据项，分别表示该元素

、

和

。第74页2.三元素组表中每个结点对应于稀疏矩阵一个非零元素，它包含有三个数据项，分别表示该元素行下标、列下标和元素值。第75页5.用三元组表表示以下稀疏矩阵：第76页解：三元素组表中每个结点对应于稀疏矩阵一个非零元素，它包含有三个数据项，分别表示该元素行下标、列下标和元素值。588521325843667570266405-2149325543第77页6以下各三元组表分别表示一个稀疏矩阵，试写出它们稀疏矩阵。455001139218246327第78页6答：为4×5矩阵，非零元素有5个10000000900800600700第79页第六章一、下面是相关二叉树叙述，请判断正误（）1.若二叉树用二叉链表作存贮结构，则在n个结点二叉树链表中只有n—1个非空指针域。第80页（√）1.若二叉树用二叉链表作存贮结构，则在n个结点二叉树链表中只有n—1个非空指针域。第81页（）2.二叉树中每个结点两棵子树高度差等于1。（）3.二叉树中每个结点两棵子树是有序。第82页（×）2.二叉树中每个结点两棵子树高度差等于1。（√）3.二叉树中每个结点两棵子树是有序。第83页（）4.二叉树中每个结点关键字值大于其左非空子树（若存在话）全部结点关键字值，且小于其右非空子树（若存在话）全部结点关键字值。第84页（×）4.二叉树中每个结点关键字值大于其左非空子树（若存在话）全部结点关键字值，且小于其右非空子树（若存在话）全部结点关键字值。（没有这个要求）第85页（）5.对于一棵非空二叉树，它根结点作为第一层，则它第i层上最多能有个结点。第86页（×）5.对于一棵非空二叉树，它根结点作为第一层，则它第i层上最多能有2i—1个结点。（应）第87页（）6.用二叉链表法（link-rlink）存放包含n个结点二叉树，结点2n个指针区域中有n+1个为空指针。第88页（√）6.用二叉链表法（link-rlink）存放包含n个结点二叉树，结点2n个指针区域中有n+1个为空指针。（正确。用二叉链表存放包含n个结点二叉树，结点共有2n个链域。因为二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点链域存放指向非空儿女结点指针，还有n+1个空指针。）即有后继链接指针仅n-1个。第89页二、填空1．由３个结点所组成二叉树有

种形态。2.一棵深度为6满二叉树有

个分支结点和

个叶子。

第90页1．由３个结点所组成二叉树有5种形态。2.【计算机研】一棵深度为6满二叉树有n1+n2=0+n2=n0-1=31个分支结点和26-1=32个叶子。注：满二叉树没有度为1结点，所以分支结点数就是二度结点数。第91页二叉树基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树遍历次序有六种。最惯用是三种：前序法（即按NLR次序），后序法（即按

次序）和中序法（也称对称序法，即按LNR次序）。这三种方法相互之间相关联。

若已知一棵二叉树前序序列是BEFCGDH，中序序列是FEBGCHD，则它后序序列必是

。

第92页3.二叉树基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树遍历次序有六种。最惯用是三种：前序法（即按NLR次序），后序法（即按LRN次序）和中序法（也称对称序法，即按LNR次序）。这三种方法相互之间相关联。若已知一棵二叉树前序序列是BEFCGDH，中序序列是FEBGCHD，则它后序序列必是FEGHDCB。解：法1：先由已知条件画图，再后序遍历得到结果；法2：不画图也能快速得出后序序列，只要找到根位置特征。由前序先确定root，由中序先确定左子树。比如，前序遍历BEFCGDH中，根结点在最前面，是B；则后序遍历中B一定在最终面。法3：递归计算。如B在前序序列中第一，中序中在中间（可知左右子树上有哪些元素），则在后序中必为最终。如法对B左右子树一样处理，则问题得解。第93页第94页4.用5个权值{3,2,4,5,1}结构哈夫曼（Huffman）树带权路径长度是

。第95页4.【计算机研】用5个权值{3,2,4,5,1}结构哈夫曼（Huffman）树带权路径长度是33。解：先结构哈夫曼树，得到各叶子路径长度之后便可求出WPL＝（4＋5＋3）×2＋（1＋2）×3=33第96页三、选择题()1.3个结点可组成

个不一样形态二叉树。A.2B.3C.4D.5第97页(D)1.3个结点可组成

个不一样形态二叉树。A.2B.3C.4D.5第98页（）2．二叉树是非线性数据结构，所以

。（Ａ）它不能用次序存放结构存放;（Ｂ）它不能用链式存放结构存放;（Ｃ）次序存放结构和链式存放结构都能存放;（Ｄ）次序存放结构和链式存放结构都不能使用

第99页（C）2．二叉树是非线性数据结构，所以

。（Ａ）它不能用次序存放结构存放;（Ｂ）它不能用链式存放结构存放;（Ｃ）次序存放结构和链式存放结构都能存放;（Ｄ）次序存放结构和链式存放结构都不能使用

第100页（）3．把一棵树转换为二叉树后，这棵二叉树形态是

。（Ａ）唯一（Ｂ）有各种（Ｃ）有各种，但根结点都没有左孩子（Ｄ）有各种，但根结点都没有右孩子第101页（A）3．把一棵树转换为二叉树后，这棵二叉树形态是

。（Ａ）唯一（Ｂ）有各种（Ｃ）有各种，但根结点都没有左孩子（Ｄ）有各种，但根结点都没有右孩子第102页()4.将一棵有50个结点完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点编号为1，则编号为30结点右孩子编号为

。A.30B.60C.61D.62第103页(C)4.将一棵有50个结点完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点编号为1，则编号为30结点右孩子编号为

。A.30B.60C.61D.62第104页()5.设森林F中有三棵树，第一、第二和第三棵树结点个数分别为M1、M2和M3。与森林F对应二叉树根结点右子树上结点个数是

。A.M1B.M1+M2C.M3D.M2+M3第105页(D)5.设森林F中有三棵树，第一、第二和第三棵树结点个数分别为M1、M2和M3。与森林F对应二叉树根结点右子树上结点个数是

。A.M1B.M1+M2C.M3D.M2+M3第106页6.二叉树A。在完全二叉树中，若一个结点没有B，则它必定是叶结点。每棵树都能惟一地转换成与它对应二叉树。由树转换成二叉树里，一个结点N左儿女是N在原树里对应结点C，而N右儿女是它在原树里对应结点D。供选择答案A：①是特殊树②不是树特殊形式③是两棵树总称④有是只有二个根结点树形结构B:①左子结点②右子结点③左子结点或者没有右子结点④弟兄C～D：①最左子结点②最右子结点③最邻近右弟兄④最邻近左弟兄⑤最左弟兄⑥最右弟兄答案：A=

B=

C=

D＝

第107页6.二叉树A。在完全二叉树中，若一个结点没有B，则它必定是叶结点。每棵树都能惟一地转换成与它对应二叉树。由树转换成二叉树里，一个结点N左儿女是N在原树里对应结点C，而N右儿女是它在原树里对应结点D。供选择答案A：①是特殊树②不是树特殊形式③是两棵树总称④有是只有二个根结点树形结构B:①左子结点②右子结点③左子结点或者没有右子结点④弟兄C～D：①最左子结点②最右子结点③最邻近右弟兄④最邻近左弟兄⑤最左弟兄⑥最右弟兄答案：A=

B=

C=

D＝

答案：ABCDE＝2，1，1，3第108页四、简答题1一棵度为2树与一棵二叉树有何区分？第109页四、简答题1一棵度为2树与一棵二叉树有何区分？答：度为2树从形式上看与二叉树很相同，但它子树是无序，而二叉树是有序。即，在普通树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。第110页2给定二叉树两种遍历序列，分别是：前序遍历序列：D，A，C，E，B，H，F，G，I；中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树B

第111页第112页4.试写出如图所表示二叉树分别按先序、中序、后序遍历时得到结点序列。第113页4.试写出如图所表示二叉树分别按先序、中序、后序遍历时得到结点序列。

答：DLR：ABDFJGKCEHILM LDR:BFJDGKACHELIM LRD：JFKGDBHLMIECA第114页

6.【严题集6.21②】画出和以下二叉树对应森林。第115页6答：注意根右边子树必定是森林，而孩子结点右子树均为弟兄。第116页第七章第117页一、单项选择题（）1.在一个图中，全部顶点度数之和等于图边数

倍。A．1/2B.1C.2D.4（）2.在一个有向图中，全部顶点入度之和等于全部顶点出度之和

倍。A．1/2B.1C.2D.4

第118页（C）1.在一个图中，全部顶点度数之和等于图边数

倍。A．1/2B.1C.2D.4（B）2.在一个有向图中，全部顶点入度之和等于全部顶点出度之和

倍。A．1/2B.1C.2D.4

第119页（）3.有8个结点无向图最多有条边。

A．14B.28C.56D.112

第120页（B）3.有8个结点无向图最多有

条边。

A．14B.28C.56D.112

第121页（）4.有8个结点有向完全图有

条边。

A．14B.28C.56D.112

第122页（C）4.有8个结点有向完全图有

条边。

A．14B.28C.56D.112

第123页二、填空题1.图有

、

等存放结构，遍历图有

、

等方法。第124页1.图有邻接矩阵、邻接表等存放结构，遍历图有深度优先遍历、广度优先遍历等方法。第125页三、简答题1.【严题集7.1①】已知如图所表示有向图，请给出该图:(1)每个顶点入/出度；(2)邻接矩阵；(3)邻接表；(4)逆邻接表。

第126页第127页第128页第129页第130页第131页4.已知一个图顶点为A、B、C、D，其邻接矩阵上三角元素（包含主对角线元素）全为0，其它元素均为1(以下表所表示)。请问：（1）该图是有向图还是无向图?（2）请画出该图形。第132页

该图是一个有向图图形以下:第133页5已知某网邻接（出度）表，请画出该网络。节点结构表示以下:第134页第135页第八章第136页一、填空题1.在数据存放无规律而言线性表中进行检索最正确方法是

。第137页一、填空题1.在数据存放无规律而言线性表中进行检索最正确方法是次序查找（线性查找）。第138页3.假设在有序线性表a[20]上进行折半查找，则比较一次查找成功结点数为1；比较两次查找成功结点数为

；比较四次查找成功结点数为

。第139页3.假设在有序线性表a[20]上进行折半查找，则比较一次查找成功结点数为1；比较两次查找成功结点数为2；比较四次查找成功结点数为8。第140页5.在各种查找方法中，平均查找长度与结点个数n无关查找方法是

。6.哈希法存放基本思想是由

决定数据存放地址。第141页5.在各种查找方法中，平均查找长度与结点个数n无关查找方法是哈希查找。6.哈希法存放基本思想是由关键字值决定数据存放地址。第142页（）2．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中

比较大小，查找结果是失败。A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50第143页（A）2．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中

比较大小，查找结果是失败。A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50第144页（）4.链表适合用于

查找A．次序B．二分法C．次序，也能二分法D．随机第145页（A）4.链表适合用于

查找A．次序B．二分法C．次序，也能二分法D．随机第146页6．要进行线性查找，则线性表A；要进行二分查找，则线性表B；要进行散列查找，则线性表C。供选择答案：A~C：①必须以次序方式存放②必须以链表方式存放③必须以散列方式存放④既能够以次序方式，也能够以链表方式存放⑤必须以次序方式存放且数据元素已按值递增或递减次序排好⑥必须以链表方式存放且数据元素已按值递增或递减次序排好答案：A=

B=

C=第147页6．要进行线性查找，则线性表A；要进行二分查找，则线性表B；要进行散列查找，则线性表C。供选择答案：A~C：①必须以次序方式存放②必须以链表方式存放③必须以散列方式存放④既能够以次序方式，也能够以链表方式存放⑤必须以次序方式存放且数据元素已按值递增或递减次序排好⑥必须以链表方式存放且数据元素已按值递增或递减次序排好答案：A=④B=⑤C=③第148页7.数据结构反应了数据元素之间结构关系。链表是一个A，它对于数据元素插入和删除B。通常查找线性表数据元素方法有C和D两种方法，其中C是一个只适合于次序存放结构但E方法；而D是一个对次序和链式存放结构均适用方法。A：①次序存放线性表②非次序存放非线性表 ③次序存放非线性表 ④非次序存放线性表B： ①不需要移动结点，不需改变结点指针②不需要移动结点，只需改变结点指针 ③只需移动结点，不需改变结点指针 ④既需移动结点，又需改变结点指针C：①次序查找②循环查找 ③条件查找④二分法查找D：①次序查找②随机查找 ③二分法查找④分块查找E：①效率较低线性查找②效率较低非线性查找 ③效率较高非线性查找④效率较高线性查找答案：A＝

B＝

C＝

D＝

E＝

第149页7.数据结构反应了数据元素之间结构关系。链表是一个A，它对于数据元素插入和删除B。通常查找线性表数据元素方法有C和D两种方法，其中C是一个只适合于次序存放结构但E方法；而D是一个对次序和链式存放结构均适用方法。A：①次序存放线性表②非次序存放非线性表 ③次序存放非线性表 ④非次序存放线性表B： ①不需要移动结点，不需改变结点指针②不需要移动结点，只需改变结点指针 ③只需移动结点，不需改变结点指针 ④既需移动结点，又需改变结点指针C：①次序查找②循环查找 ③条件查找④二分法查找D：①次序查找②随机查找 ③二分法查找④分块查找E：①效率较低线性查找②效率较低非线性查找 ③效率较高非线性查找④效率较高线性查找答案：A＝④B＝②C＝④

D＝①E＝③

第150页三、简答题1.对分（折半）查找适不适合链表结构序列，为何？用二分查找查找速度必定比线性查找速度快，这种说法对吗？第151页1对分（折半）查找适不适合链表结构序列，为何？用二分查找查找速度必定比线性查找速度快，这种说法对吗？答：不适合！即使有序单链表结点是按从小到大（或从大到小）次序排列，但因其存放结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。二分查找速度在普通情况下是快些，但在特殊情况下未必快。比如所查数据位于首位时，则线性查找快；而二分查找则慢得多。第152页4.使用折半查找两个前提条件是什么？（1）采取次序存放结构；（2）按关键字大小有序排列。第153页4.使用折半查找两个前提条件是什么？第154页4.设哈希（Hash）表地址范围为0～17，哈希函数为：H（K）＝KMOD16。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）造出Hash表，试回答以下问题：画出哈希表示意图；若查找关键字63，需要依次与哪些关键字进行比较？若查找关键字60，需要依次与哪些关键字比较？假定每个关键字查找概率相等，求查找成功时平均查找长度。

第155页解：（1）画表以下：第156页（2）查找63,首先要与H(63)=63%16=15号单元内容比较，即63vs31,no;然后顺移，与46,47,32,17,63相比，一共比较了6次！（3）查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应该有空标识），所以应该只比较这一次即可。（4）对于黑色数据元素，各比较1次；共6次；对红色元素则各不相同，要统计移位位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11（6＋2＋3×3）＝17/11=1.5454545454≈1.55第157页4.选取散列函数H（key）=（3*key）%11，用线性探测法处理冲突，对以下关键码序列结构一个散列地址空间为0～10，表长为11散列表，{22，41，53，08，46，30，01，31，66}。第158页解：由题意知，m=11(刚好为素数)则(22*3)%11=6……0(41*3)%11=11……2(53*3)%11=14……5(08*3)%11=2……2(46*3)%11=12……6(30*3)%11=8……2(01*3)%11=0……3(31*3)%11=8……5(66*3)%11=9……0第159页第9章第160页一、填空题1.大多数排序算法都有两个基本操作：

和

。第161页1.大多数排序算法都有两个