数据结构数据结构习题课件.ppt

《数据结构数据结构习题课件.ppt》由会员分享，可在线阅读，更多相关《数据结构数据结构习题课件.ppt（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、1.数据结构是一门研究非数值计算的程序设计问题中计算机的数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象操作对象以及它们之间的以及它们之间的和运算等的学科。和运算等的学科。2.数据结构被形式地定义为（数据结构被形式地定义为（D,R），其中），其中D是是数据元素数据元素的有限集合，的有限集合，R是是D有限集合。有限集合。3.数据结构包括数据的数据结构包括数据的逻辑结构逻辑结构、数据的、数据的存储结构存储结构运算运算这三个方面的内容。这三个方面的内容。4.数据结构按逻辑结构可分为两大类，它们分别是数据结构按逻辑结构可分为两大类，它们分别是线性结构线性结构和和非线性结构非线性结构。5.线

2、性结构中元素之间存在线性结构中元素之间存在一对一一对一关系，树形结构中元素之间存在关系，树形结构中元素之间存在一对多一对多系，图形结构中元素之间存在系，图形结构中元素之间存在多对多多对多6在线性结构中，第一个结点在线性结构中，第一个结点没有没有前驱结点，其余每个结点有且只有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点个前驱结点；最后一个结点没有没有后续结后续结点，其余每个结点有且只有点，其余每个结点有且只有1个后续结点。个后续结点。7.在树形结构中，树根结点没有在树形结构中，树根结点没有前驱前驱结点，其余每个结点有且只有结点，其余每个结点有且只有1个前驱结点；叶子结点没有个前驱结点

3、；叶子结点没有结点，其余每结点，其余每个结点的后续结点数可以个结点的后续结点数可以。8.在图形结构中，每个结点的前驱结点数和后续结点数可以在图形结构中，每个结点的前驱结点数和后续结点数可以。9数据的存储结构可用数据的存储结构可用2种基本的存储方法表示，它们分别是种基本的存储方法表示，它们分别是顺序存储结构和连式存储结构顺序存储结构和连式存储结构。10.数据的运算最常用的有数据的运算最常用的有5种，它们分别是种，它们分别是检索、排序、插入、删除、修改检索、排序、插入、删除、修改。11.一个算法的效率可分为一个算法的效率可分为效率和效率和效率。效率。（B B）1.1.非线性结构是数据元素之间存在一

4、种：非线性结构是数据元素之间存在一种：B B）多对多关系）多对多关系 （C C）2.2.数据结构中，与所使用的计算机无关的是数据的数据结构中，与所使用的计算机无关的是数据的 结构；结构；C)C)逻辑逻辑 （C C）3.3.算法分析的目的是：算法分析的目的是：C)C)分析算法的效率以求改进分析算法的效率以求改进 （A A）4.4.算法分析的两个主要方面是：算法分析的两个主要方面是：A)A)空间复杂性和时间复杂性空间复杂性和时间复杂性（C C）5.5.计算机算法指的是：计算机算法指的是：C)C)解决问题的有限运算序列解决问题的有限运算序列 （B B）6.6.计算机算法必须具备输入、输出和计算机算法

5、必须具备输入、输出和 等等5 5个特性。个特性。B)B)可行性、确定性和有穷性可行性、确定性和有穷性1.1.在在顺顺序序表表中中插插入入或或删删除除一一个个元元素素，需需要要平平均均移移动动 一一半半 元元素素，具具体体移移动动的的元元素素个个数数与与 表表长长和和该该元元素素在在表表中中的位置的位置 2.2.线性表中结点的集合是线性表中结点的集合是 的，结点间的关系是的，结点间的关系是 一对一一对一 的的3.3.向一个长度为向一个长度为n n的表的第的表的第i i个元素个元素(1in+1)(1in+1)之前插入一个元素时，需向后移动之前插入一个元素时，需向后移动 n-i+1 n-i+1 个元

6、素。个元素。4.4.向一个长度为向一个长度为n n的表中删除第的表中删除第i i个元素个元素(1in)(1in)时，需向前移动时，需向前移动 n-i n-i 个元素。个元素。5.5.在顺序表中访问任意一结点的时间复杂度均为在顺序表中访问任意一结点的时间复杂度均为 O(1)O(1)，因此，顺序表也称为，因此，顺序表也称为 随机存取随机存取 的数据结构。的数据结构。6.6.顺序表中逻辑上相邻的元素的物理位置顺序表中逻辑上相邻的元素的物理位置 必定必定 相邻。单链表中逻辑上相邻的元素的物理位置相邻。单链表中逻辑上相邻的元素的物理位置 不一定不一定 （C C）1 1数据在计算机存储器内表示时，物理地址

7、与逻辑地址相同并且是连续的，称之为：（数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（C C）顺序存储结构）顺序存储结构 （A A）3.3.在在n n个结点的顺序表中，算法的时间复杂度是个结点的顺序表中，算法的时间复杂度是O O（1 1）的操作是：）的操作是：(A(A）访问第访问第i i个结点（个结点（1in1in）和求第）和求第i i个结点的直接前驱（个结点的直接前驱（2in2in）（B B）4.4.向一个有向一个有127127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 个元素（个元素（B

8、 B）63.5 63.5（）1.链表的每个结点中都恰好包含一个指针。链表的每个结点中都恰好包含一个指针。答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。别存放指向其直接前趋和直接后继结点的指针。（）2.链表的物理存储结构具有同链表一样的顺序。链表的物理存储结构具有同链表一样的顺序。错，链表的存储结构特点是无序，而链表的示意图有序。错，链表的存储结构特点是无序，而链表的示意图有序。（）3.链表的删除算法很

9、简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。错，错，链表的结点不会移动，只是指针内容改变。链表的结点不会移动，只是指针内容改变。（）4.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。（）5.顺序表结构适宜于进行顺序存取，而

10、链表适宜于进行随机存取。顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。错，正好说反了。顺序表才适合随机存取，链表恰恰适于错，正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜顺藤摸瓜”（）6.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。顺序存储方式的优点是存储密度大，且插入、删除运算效率高。错，前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，在表长为错，前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，在表长为n的的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。顺序表中，

11、插入和删除一个数据元素，平均需移动表长一半个数的数据元素。（）7.线性表在物理存储空间中也一定是连续的。线性表在物理存储空间中也一定是连续的。错，线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。错，线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。（）8.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。错误。线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。错误。线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。（）9

12、.顺序存储方式只能用于存储线性结构。顺序存储方式只能用于存储线性结构。错误。顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，错误。顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。但其最佳存储方式是顺序存储方式。（）10.线性表的逻辑顺序与存储顺序总是一致的。线性表的逻辑顺序与存储顺序总是一致的。错，理由同错，理由同7。链式存储就无需一致。链式存储就无需一致。5.5.链接存储的存储结构所占存储空间：链接存储的存储结构所占存储空间：分两部分，一部分存放结点值，另一部分存放表示

13、结点间关系的指针分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针6.6.链表是一种采用链表是一种采用 存储结构存储的线性表；（存储结构存储的线性表；（B B）链式链式 7.7.线性表若采用链式存储结构时，要求内存中可用存储单元的地址线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（D D）连续或不连续都可以连续或不连续都可以8 8 线性表在线性表在 情况下适用于使用链式结构实现。（）需不断对进行删除插入情况下适用于使用链式结构实现。（）需不断对进行删除插入 1.1.线性表、栈和队列都是线性表、栈和队列都是 线性线性 结结构，可以在线性表的构，可以在线性表的 任意任意 位置

14、插入和删除元素；对于栈只能在位置插入和删除元素；对于栈只能在 栈顶栈顶 插入和插入和删除元素；对于队列只能在删除元素；对于队列只能在 队尾队尾 插入和插入和 队头队头 删除元素。删除元素。2.2.栈是一种特殊的线性表，允许插入和删除运算的一端称为栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶栈顶 。不允许插入和删除运算的一端称为。不允许插入和删除运算的一端称为 栈底栈底 。1.1.3.3.队列队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。2.2.4.4.在一个循环队列中，队首指针指

15、向队首元素的在一个循环队列中，队首指针指向队首元素的 当前当前 位置。位置。3.3.5.5.在具有在具有n n个单元的循环队列中，队满时共有个单元的循环队列中，队满时共有 n-1n-1 个元素。个元素。6.6.向栈中压入元素的操作是先向栈中压入元素的操作是先 插入元素插入元素 ，后，后 移动指针移动指针 。1.1.7.7.从循环队列中删除一个元素时，其操作是从循环队列中删除一个元素时，其操作是 先先 读取元素读取元素 ，后，后 移动指针移动指针 。（FF）1.1.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一

16、个复杂类型。（FF）2.2.在表结构中最常用的是线性表，栈和队列不太常用。在表结构中最常用的是线性表，栈和队列不太常用。（TT）3.3.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（TT）4.4.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（FF）5.5.栈和链表是两种不同的数据结构。栈和链表是两种不同的数据结构。（FF）6.6.栈和队列是一种非线性数据结构。栈和队列是一种非线性数据结构。

17、（TT）7.7.栈和队列的存储方式既可是顺序方式，也可是链接方式。栈和队列的存储方式既可是顺序方式，也可是链接方式。（TT）8.8.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。这片内存空间的两端。（FF）9.9.队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。1.1.（FF）10.10.一个栈的输入序列是一个栈的输入序列是1234512345，则栈的输出

18、序列不可能是，则栈的输出序列不可能是1234512345。1.1.栈中元素的进出原则是栈中元素的进出原则是后进先出后进先出 1.1.2.2.若已知一个栈的入栈序列是若已知一个栈的入栈序列是1 1，2 2，3 3，n n，其输出序列为，其输出序列为p1p1，p2p2，p3p3，pnpn，若，若p1=np1=n，则，则pipi为为n-n-i+1 i+1 2.2.3.3.判定一个栈判定一个栈STST（最多元素为（最多元素为m0m0）为空的条件是）为空的条件是 ST-top=0ST-top=0 3.3.4.4.判定一个队列判定一个队列QUQU（最多元素为（最多元素为m0m0）为满队列的条件是）为满队列

19、的条件是QU-rear QU-rear QU-front=m0QU-front=m0 （D D ）5 5数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素的位置，假定队数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素的公式为（）（列中元素的个数小于，计算队列中元素的公式为（）（n nr rf f）%n%n1.假设有二维数组假设有二维数组A68，每个元素用相邻的，每个元素用相邻的6个字节存储，存储器按字节编址。已知个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）的起始存储位置（基地址）为为1000，则数组，

20、则数组A的体积（存储量）为的体积（存储量）为288；末尾元素；末尾元素A57的第一个字节地址为的第一个字节地址为1282；若按行存储时，元素；若按行存储时，元素A14的的第一个字节地址为第一个字节地址为1072；若按列存储时，元素；若按列存储时，元素A47的第一个字节地址为的第一个字节地址为1276。2.设数组设数组a160,170的基地址为的基地址为2048，每个元素占，每个元素占2个存储单元，若以列序为主序顺序存储，则元素个存储单元，若以列序为主序顺序存储，则元素a32,58的存储地址为的存储地址为8950。3.三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表

21、示该元素的三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的行下标行下标、列下标列下标和和元素值元素值。（A）4.假设有假设有60行行70列的二维数组列的二维数组a160,170以列序为主序顺序存储，其基地址为以列序为主序顺序存储，其基地址为10000，每个元素占，每个元素占2个个存储单元，那么第存储单元，那么第32行第行第58列的元素列的元素a32,58的存储地址为的存储地址为。（无第。（无第0行第行第0列元素）列元素）16902（T T ）1.1.若二叉树用二叉链表作存贮结构，则在若二叉树用二叉链表作存贮结构，则在n n个结点的二叉树链表中只有个结点的

22、二叉树链表中只有n n1 1个非空指针域。个非空指针域。（F F ）2.2.二叉树中每个结点的两棵子树的高度差等于二叉树中每个结点的两棵子树的高度差等于1 1。（T T ）3.3.二叉树中每个结点的两棵子树是有序的。二叉树中每个结点的两棵子树是有序的。（F F ）4.4.二叉树中每个结点有两棵非空子树或有两棵空子树。二叉树中每个结点有两棵非空子树或有两棵空子树。（F F ）5.5.对于一棵非空二叉树，它的根结点作为第一层，则它的第对于一棵非空二叉树，它的根结点作为第一层，则它的第i i层上最多能有层上最多能有2 2i i1 1个结点。个结点。（C C）1 1 不含任何结点的空树不含任何结点的空

23、树 。（）是一棵树也是一棵二叉树）是一棵树也是一棵二叉树;（C C）2 2二叉树是非线性数据结构，所以二叉树是非线性数据结构，所以 。（）顺序存储结构和链式存储结构都能存储（）顺序存储结构和链式存储结构都能存储;（C C）3.3.具有具有n(n0)n(n0)个结点的完全二叉树的深度为个结点的完全二叉树的深度为 。()log log2 2(n)(n)+1+1 （A A）4 4一棵树转换为二叉树后，这棵二叉树的形态是一棵树转换为二叉树后，这棵二叉树的形态是 。（）唯一的（）唯一的5.二叉树二叉树A。在完全的二叉树中，若一个结点没有。在完全的二叉树中，若一个结点没有B，则它必定是叶结点。每棵树都能惟

24、一地转换成与它对应的，则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点二叉树。由树转换成的二叉树里，一个结点N的左子女是的左子女是N在原树里对应结点的在原树里对应结点的C，而，而N的右子女是它在原树里对的右子女是它在原树里对应结点的应结点的D。供选择的答案。供选择的答案A：是特殊的树是特殊的树不是树的特殊形式不是树的特殊形式是两棵树的总称是两棵树的总称有是只有二个根结点的树形结构有是只有二个根结点的树形结构B:左子结点左子结点右子结点右子结点左子结点或者没有右子结点左子结点或者没有右子结点兄弟兄弟CD：最左子结点最左子结点最右子结点最右子结点最邻近的右兄

25、弟最邻近的右兄弟最邻近的左兄弟最邻近的左兄弟最左的兄弟最左的兄弟最右的兄弟最右的兄弟答案：答案：A=B=C=D6.二叉树的基本组成部分是：根（二叉树的基本组成部分是：根（N）、左子树（）、左子树（L）和右子树（）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按三种：前序法（即按NLR次序），后序法（即按次序），后序法（即按LRN次序）和中序法（也称对称序法，即按次序）和中序法（也称对称序法，即按LNR次序）。次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEF

26、CGDH，中序序列是，中序序列是FEBGCHD，则它的后序序，则它的后序序列必是列必是FEGHDCB。（C C ）1 1 对对2222个记录的有序表作折半查找，当查找失败时，至少需要比较个记录的有序表作折半查找，当查找失败时，至少需要比较 次关键字。次关键字。C C5 5 （C C）3.3.折半搜索与二叉搜索树的时间性能折半搜索与二叉搜索树的时间性能 C.C.有时不相同有时不相同4.4.在二叉排序树中，每个结点的关键码值在二叉排序树中，每个结点的关键码值A A，B B一棵二叉排序，即可得到排序序列。同一个结点集一棵二叉排序，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均

27、检索长度最短的二叉排序树称作最佳二叉排序，最佳二叉排序树合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序，最佳二叉排序树在结构上的特点是在结构上的特点是C C。供选择的答案供选择的答案A A：比左子树所有结点的关键码值大，比右子树所有结点的关键码值小比左子树所有结点的关键码值大，比右子树所有结点的关键码值小比左子树所有结点的关键码值比左子树所有结点的关键码值小，比右子树所有结点的关键码值大小，比右子树所有结点的关键码值大比左右子树的所有结点的关键码值都大比左右子树的所有结点的关键码值都大与左子树所有结点的关与左子树所有结点的关键码值和右子树所有结点的关键码值无必

28、然的大小关系键码值和右子树所有结点的关键码值无必然的大小关系B:B:前序遍历前序遍历中序（对称）遍历中序（对称）遍历后序遍历后序遍历层次遍历层次遍历C C：除最下二层可以不满外，其余都是充满的除最下二层可以不满外，其余都是充满的除最下一层可以不满外，其余都是充满除最下一层可以不满外，其余都是充满的的每个结点的左右子树的高度之差的绝对值不大于每个结点的左右子树的高度之差的绝对值不大于11最下层的叶子必须在最左边最下层的叶子必须在最左边答案：答案：A ABBCC 5.5.散列法存储的基本思想是根据散列法存储的基本思想是根据 A A 来决定来决定 B B ，碰撞（冲突）指的是，碰撞（冲突）指的是 C

29、 C ，处理碰撞的两类主要方法是，处理碰撞的两类主要方法是 D D 。供选择的答案。供选择的答案A A，B B：存储地址存储地址元素的符号元素的符号元素个数元素个数关键码值关键码值非码属性非码属性平均检索长度平均检索长度负载因子负载因子 散列表空间散列表空间 C:C:两个元素具有相同序号两个元素具有相同序号 两个元素的关键码值不同，而非码属性相同两个元素的关键码值不同，而非码属性相同 不同关键码值对应到相同不同关键码值对应到相同的存储地址的存储地址 负载因子过大负载因子过大 数据元素过多数据元素过多D D：线性探查法和双散列函数法线性探查法和双散列函数法 建溢出区法和不建溢出区法建溢出区法和不建溢出区法 除余法和折叠法除余法和折叠法 拉链法和开地址法拉链法和开地址法答案：答案：A ABBCCDD