数据结构复习题_计算机-数据结构与算法.pdf

《数据结构复习题_计算机-数据结构与算法.pdf》由会员分享，可在线阅读，更多相关《数据结构复习题_计算机-数据结构与算法.pdf（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.v .一判断题以下各题，正确的请在前面的括号内打；错误的打 第 1 章 1数据的逻辑构造与数据元素本身的内容和形式无关。2 一个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体。3数据元素是数据的最小单位。4数据项是数据的根本单位。5数据的逻辑构造和数据的存储构造是一样的。6数据的逻辑构造是各数据元素之间的逻辑关系，是用户按使用需要而建立的。7数据的物理构造是指数据在计算机内实际的存储形式。8从逻辑关系上讲，数据构造主要分为线性构造和非线性构造两类。9数据的存储构造是数据的逻辑构造的存储映像。10算法是对解题方法和步骤的描述。第 2 章 1链表的物理存储构造具有同链表一样的

2、顺序。2链表的每个结点都恰好包含一个指针域。3 线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有一样的特性，因此属于同一数据对象。4链表的删除算法很简单，因为当删除链中某个结点后，计算时机自动地将后续的各个单元向前移动。5顺序表构造适宜于进展顺序存取，而链表适宜于进展随机存取。6数组元素的存储位置是下标的线性函数。7在单链表中，元素的存储位置用指针联系，所以可以从头结点开场查找任何一个元素。8顺序存储线性表的插入和删除操作不需要付出很大的代价，因为平均每次移动仅一半的元素。9顺序存储方式的优点是存储密度大，插入、删除效率高。10在单链表中，要取得某个元素，只要知道该元素的指针即可，

3、因此单链表是随机存取的存储构造。第 3 章 1大多数排序算法都有比拟关键字大小和改变指向记录的指针或移动记录本身两种根本操作。2快速排序在任何情况下都比其它排序方法速度快。3快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。4如果某种排序算法不稳定，那么该排序方法就没有实际应用价值。5对 n 个记录的进展快速排序，所需要的平均时间是 Onlog2n。6冒泡排序是不稳定的排序。7冒泡排序的时间复杂度是 On2。.v .8堆排序所需的时间与待排序的记录个数无关。9对快速排序来说，初始序列为正序或反序都是最坏情况。10对于 n 个记录的集合进展归并排序，所需的平均时间为 O(nlog2n)

4、。第 4 章 1栈是运算受限制的线性表。2在栈空的情况下，不能作出栈操作，否那么产生下溢出。3栈一定是顺序存储的线性构造。4空栈就是所有元素都为 0 的栈。5一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。6一个栈的输入序列为：A，B，C，D，通过入出栈操作可以输出序列：A，B，C，D。7在 C 或 C+语言中设顺序栈的长度为 MAXLEN，那么 top=MAXLEN 时表示队满。8链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。9在栈中插入或删除一个元素应遵守的“后进先出的原那么。10进位制的换算算法是栈的应用。11队列是限制在两端进展操作的线性表。12判断顺序队

5、列为空的标准是头指针和尾指针均指向同一个结点。13在链队列做出队操作时，会改变 front 指针的值。14在循环队列中，假设尾指针 rear大于头指针 front，其元素个数为 rear-front。15队列是一种“先进先出的线性表。16在循环链队列中无上溢出现象。17栈和队列都是顺序存储的线性构造。18栈和队列都是属于线性构造。19顺序队和循环队的队满和队空的判断条件是一样的。20在队列中插入或删除一个元素应遵守的先进先出的原那么。第 5 章 1串的长度是指串中不同字符的个数。2串是 n 个字母的有限序列。3空串不等于空格串。4如果两个串含有一样的字符，那么说明它们相等。5如果一个串中所有的

6、字母均在另一个串中出现，那么说明前者是后者的子串。6串的堆分配存储是一种动态存储构造。7“DT是“DATA的子串。8空串与空格串是一样的。9串中任意个字符组成的子序列称为该串的子串。10子串的定位运算称为模式匹配。11n 维的多维数组可以视为 n-1维数组元素组成的线性构造。个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的

7、顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插.v .12稀疏矩阵中非零元素的个数远小于矩阵元素的总数。13假设采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。14在稀疏矩阵的三元组表表示法中，每个三元组表示矩阵中数据元素的行号、列号和值。15上三角矩阵主对角线以上不包括主对角线中的元素，均为常数 C。16对称矩阵

8、、三角矩阵、稀疏矩阵都可以进展压缩存储。17任何矩阵都可以进展压缩存储。18在稀疏矩阵的三元组表表示法中，每个三元组表示矩阵中非零元素的行号、列号和值。19数组元素可以由假设干个数据项组成。(20稀疏矩阵压缩存储就是为矩阵中非零元素分配一个存储空间。第 6 章 1树构造中每个结点最多只有一个直接前驱。2完全二叉树一定是满二查树。3由树转换成二叉树，其根结点的右子树一定为空。4在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点之后。5用一维数组来存储二叉树时，总是以前序遍历存储结点。6二叉树的前序遍历和后序遍历并不能唯一确定这棵二叉树，因为不知道根结点是哪一个。7二叉树的前序遍

9、历中，任意一个结点均处于其子女结点的前面。8由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。9不使用递归，也可以实现二叉树的前序、中序和后序遍历。10在完全二叉树中，假设一个结点没有左孩子，那么它必然是叶子结点。第 7 章 1图可以没有边，但不能没有顶点。2在无向图中，V1，V2与V2，V1是两条不同的边。3邻接表只能用于有向图的存储。4用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。5一个图的邻接矩阵表示是唯一的。6有向图不能进展广度优先遍历。7一个图的最小生成树是该图所有生成树中权最小的生成树。8存储无向图的邻

10、接矩阵是对称的，因此只要存储邻接矩阵的上三角或下三角局部就可以了。个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的

11、存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插.v .9有向图的邻接矩阵一定是对称的。10一个图的深度优先遍历的序列是唯一的。第 8 章 1二分查找法要求待查表的关键字值必须有序。2哈希法是一种将关键字转换为存储地址的存储方法。3在二叉排序树中，根结点的值都小于孩子结点的值。4对有序表而言采用二分查找总比采用顺序查找法速度快。5二叉排序树是一种特殊的线性表。6散列存储法的根本思想是由关键字的值决定数据的存储地址。7哈希法的查找效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。8一般说来用哈希函数得到的地址，冲突不可能防止，只能尽可能减少。9选择好的哈希函数就可

12、以防止冲突的发生。10在二叉排序树上删除一个结点时，不必移动其它结点，只要将该结点的父结点的相应的指针域置空即可。二填空题 第 1 章 1数据构造是一门研究非数值计算程序设计中计算机的操作对象以及它们之间的关系和运算的学科。2数据的存储构造形式包括：顺序存储、链式存储、散列存储、索引存储。3数据构造按逻辑构造可分为两大类，它们分别是：线性构造和非线性构造。4一个算法的空间复杂度是指该算法所消耗的存储空间，它是该算法求解问题规模 n 的函数。5数据构造有逻辑构造和存储构造两种构造。6数据的存储构造形式包括：顺序存储、链式存储、散列存储、索引存储。7一个算法的效率可分为时间效率和空间效率。8数据元

13、素是数据的根本单位。9数据构造主要研究数据的逻辑构造、存储构造和算法。11数据的逻辑构造是独立于计算机的。12数据构造被定义为(D，R)，其中 D 是数据的有限集合，R是 D 上的关系的有限集合。13树形构造构造中的元素之间存在一对多的关系。14假设一个算法中的语句频度之和为 Tn=125n+3nlog2n，那么算法的时间复杂度为 Onlog2n。15数据构造主要研究数据的逻辑构造、存储构造和算法。第 2 章 1顺序表中逻辑上相邻的元素在物理位置上必须相连。2在单链表中要在结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算

14、集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插.v .的时间复杂度为 O(n)。3线性表是 n

15、个结点的有限集合。4链表相对于顺序表的优点有插入、删除方便；缺点是存储密度小。5链表相对于顺序表的优点有插入、删除方便；缺点是存储密度小。6顺序表相对于链表的优点是：节省存储和随机存取。7 对于一个具有n 个结点的单链表，在 p 所指结点后插入一个新结点的时间复杂度是 O 1。8在链表中逻辑上相邻的元素的物理位置不必相连。9线性表中第一个结点没有直接前趋，称为开场结点。10在顺序表中访问任意一个结点的时间复杂度均为 O(1)。11在 n 个结点的单链表中要删除结点*P，其时间复杂度为 O(1)。12在单链表中需知道头指针才能遍历整个链表。13在一个单链表中，在指针 p 所指向的结点之后插入指针

16、 s 所指向的结点时，应执行s-next=p-next和 p-next=s 操作。14 在一个长度为 n 的顺序表中，如果要在第 i 个元素前插入一个元素，要后移 n-i+1 个元素。15在双向链表中，每个结点都有两个指针域，它们一个指向其前趋结点，另一个指向其后继结点。第 3 章 1 根据被处理的数据在计算机中使用不同的存储设备，排序可分为：内排序和外排序。2 评价排序算法优劣的主要标准是时间复杂性和算法所需的附加空间。3插入排序、堆排序、归并排序中，排序是不稳定的有：堆排序。4在对一组记录54，38，96，23，15，72，60，45，83进展直接插入排序时，当把第 7个记录 60插入到有

17、序表时，为寻找插入位置需比拟 3 次。5对 n 个关键字进展冒泡排序，其可能的最小比拟次数为：n-1 次。6内排序是指整个排序过程，全部在计算机的内存中进展。7大多数排序算法都有两个根本的操作：比拟和移动。8在插入排序和选择排序中，假设初始数据根本正序，那么选用插入排序较好。9在排序前，关键字值相等的不同记录，排序后相对位置变化的排序方法，称为不稳定的排序方法。10假设原始数据接近无序，那么选用快速排序最好。11对于 n 个记录的集合进展归并排序，所需要的平均时间为：Olog2n。12在插入排序、归并排序、快速排序中，排序是不稳定的有：快速排序。13对一组记录54，35，96，21，12，72

18、，60，44，80进展直接选择排序时，第四次选择和交换后，未排序记录是 54，72，60，96，80 。14对于 n 个记录的集合进展，假设对其进展快速排序，在最坏的情况下所需要的时间是 O(n2)。个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线

19、性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插.v .15在最坏情况下，在第 i趟直接插入排序中，要进展 i-1 次关键字的比拟。第 4 章 1在栈中存取数据遵从的原那么是：后进先出。2在有n个元素的栈中，进栈操作的时间复杂度为 O1。3后进先出的线性表称为栈。4在顺序栈中，当top=MAXLEN-1 时，表示栈满。5.栈是输入、输出受限制的线性表。6在有n个元素的栈中，出栈操作的时间复杂度为 O1。7在栈构造中，允许插入、删除的一端称

20、为栈顶。8顺序栈S存在数组S-data0.MAXLEN-1中，出栈操作时要执行的语句有：S-top-。9在顺序栈中，当栈顶指针top=-1时，表示栈空。10向一个栈顶指针为top 的链栈插入一个新结点*p时，应执行p-next=top；和top=p；操作。11同一栈的各元素的类型一样。12栈只能在栈顶插入和删除元素。13顺序栈 S，在对 S 进展出栈操作之前首先要判断栈是否空。14假设进栈的次序是 A、B、C、D、E，执行三次出栈操作以后，栈顶元素为 B 。15从一个栈删除元素时，首先取出栈顶元素，然后再移动栈顶指针。16在队列中存取数据应遵从的原那么是先进先出。17设长度为n的链队列用单循环

21、链表表示，假设只设头指针，那么入队操作的时间复杂度为 On。18在队列中，允许插入的一端称为队尾。19设长度为n的链队列用单循环链表表示，假设只设头指针，那么出队操作的时间复杂度为 01。20设循环队列的头指针front 指向队头元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，那么队空的标志为 front=rear 。21队列在进展出队操作时，首先要判断队列是否为空。22设循环队列的头指针front 指向队头元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，那么队满标志为 front=(rear+1)%MAXLEN 。23在一个链队

22、列中，假设队头指针为front，队尾指针为rear，那么判断该队列只有一个结点的条件为：front=rear&front NULL 。24队列构造的元素个数是可变的。25设长度为n的链队列用单循环链表表示，假设只设尾指针，那么出队操作的时个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域

23、线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插.v .间复杂度为 01。26设长度为n的链队列用单循环链表表示，假设只设尾指针，那么入队操作的时间复杂度为 01。27链队列为空时，LQ-front-next=NULL 。28设循环队列的头指针front 指向队头元素，尾指针rear指向队尾元素后的一个空闲 元 素，队 列 的 最 大 空 间 为 MAXLEN，当 rearfront 时，队 列 长

24、度 是 MAXLEN-front 。29向一个循环队列中插入元素时，首先要移动队尾指针，然后再向指针所指位置写入新的元素。30队列 Q 经过 InitQueue(Q)；InQueue(Q，a)；InQueue(Q，b)；GetHead(Q，x)后，x 的值是 a 。第 5 章 1长度为零的字符串称为空串。2在串的运算中，EqualStr(aaa，aabb)的值为 0 。3串的顺序存储构造简称为顺序串。4串的链式存储构造简称为链式串。5求子串函数SubStr(Today is 30 July,2005,13,4)的结果是：July 。6设S=A:/document/mary.doc，那么len(

25、s)=_ 20。7由零个或多个字符组成的有限序列称为字符串或串。8字符串按存储方式可以分为：顺序存储、存储和堆分配存储。9设S=“A:/mydocument/text1.doc，那么 strlen(S)=23 。10在空串和空格串中，长度不为 0 的是空格串。11串顺序存储紧凑格式的优点是：空间利用率高,对串的字符处理效率低。12两个串相等是指两个串相长度等，且对应位置的字符都一样。13串顺序存储紧凑格式的缺点是对串的字符处理效率低。14模式匹配成功的起始位置称为：有效位移。15所有模式匹配不成功的起始位置称为：无效位移。16.多维数组的顺序存储方式有行优先顺序存储和列优先顺序存储两种。17.

26、同一数组中各元素的长度相等。18.在多维数组中，数据元素的存放地址可以直接通过地址计算公式算出，所以多维数组是一种随机存取构造。19.在n维数组中的每一个元素最多可以有 n 个直接前驱。20.输出二维数组Amn中所有元素值的时间复杂度为 O(m*n)。数组元素a0.20.3的实际地址上2000，元素长度是4，那么Loc1,2=个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方

27、法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插.v .2024 。21.数组的三元组存储是对稀疏矩阵的压缩存储 22.稀疏矩阵的三元组有 3 列。23.稀疏矩阵的三元组中第1列存储的是数组中非零元素所在的行数。24.n阶对称矩阵，如果只存储下三角元素，只需要 nn-1/2 个存储单元。25.稀疏矩阵A如以下图所

28、示，其非零元素存于三元组表中，三元组4，1，5按行优先顺序存储在三元组表的第 6 项。26.稀疏疏矩阵的压缩存储方法通常有三元组表和十字链表两种。27 n阶下三角矩阵，因为对角线的上方是同一个常数，需要 nn-1/2+1 个存储单元。28稀疏矩阵中有 n 个非零元素，那么三元组有 n 行。29.稀疏矩阵的三元组中第 2 列存储的是数组中非零元素所在的列数。30.稀疏矩阵的三元组中，第3列存储的是稀疏数组中的非零元素。第 6 章 1在树中，一个结点所拥有的子树数称为该结点的度。2一棵含有 n 个结点的完全二叉树，它的高度是|log2n|+1 。下取整 3度为零的结点为叶子结点或叶结点。4一棵深度

29、为 h 的完全二叉树上的结点总数最少为 2 h-1个。5树内各结点度的最大值称为树的度。6一棵深度为 h 的完全二叉树上的结点总数最多为 2 h-1 个。7树中结点的最大层次称为树的深度或高度。8三个结点可以组成 2 种不同形态的树。9由树转换成二叉树时，其根结点没有右子树。10有 20个结点的完全二叉树，编号为 10的结点的左儿子结点的编号是 20 。11在树中，一个结点的直接子结点的个数称为该结点的度。12由二叉树的后序和中序遍历序列，可以唯一确定一棵二叉树。13给定如以下图所示的二叉树，其前序遍历序列为：ABEFHCG 。A B F G HC E 8 0 0 0 0 0 0 11 0 0

30、 0 0 0 0 0 6 0 0 0 3 0 0 7 0 0 5 0 0 0 0 0 0 0 0 9 0 稀疏矩阵 A A=个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展

31、随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插.v .14给定如以下图所示的二叉树，其层次遍历序列为：ABCEFGH 。15 将一棵完全二叉树按层次编号，对于任意一个编号为 i 的结点，该结点右孩子的编号为：2*i+1 。第 7 章 1图有：_邻接矩阵_ 和邻接表等存储构造。2 n 个顶点e条边的图假设采用邻接矩阵存储，深度优先遍历算法的时间复杂度为：O n2。3图的遍历有：深度优先搜和 _广度优先搜 _等方法。4n 个顶点 e 条边的图假设采用邻接矩阵存储，那么空间复杂度为：_ On2_。5图有：邻接矩阵和邻

32、接表等存储构造。6假设图 G 中每条边都 _无方向，那么 G 为无向图。7在具有 n 个顶点的图的生成树中，含有 n-1 条边。8有向图的边也称为 _弧_。9图的邻接矩阵表示法是表示 _顶点_之间相邻关系的矩阵。10有向图 G 用邻接矩阵存储，其第 i 行的所有元素之和等于顶点 i 的 _出度_。11图的深度优先遍历序列 _不是_唯一的。12设有一稀疏图 G，那么 G 采用 _邻接表_存储比拟节省空间。13从图中某一顶点出发，访遍图中其余顶点，且使每一顶点仅被访问一次，称这一过程为 图的遍历或遍历。14遍历图的两种根本方法是：深度优先遍历和广度优先遍历。15有向图的邻接表表示适于求顶点的出度。

33、第 8 章 1顺序查找法，表中元素可以任意存放。2散列表查找法的平均查找长度与元素个数 n 无关。A B F G HC E 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展

34、随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插.v .3快速排序是对冒泡排序的一种改良。4在哈希函数 H(key)=key%P 中，P 一般应取质数。5二分查找的存储构造仅适用于顺序存储构造，而且关键字有序的。6在分块查找方法中，首先查找索引，然后再查找相应的块。7二分查找法，表中元素必须按关键字有序存放。8在分块查找方法中，表中元素每块内的元素可以任意存放，块与块之间必须有序存放。9顺序查找、二分查找、分块查找都属于静态查找。10顺序查找法，其平均查找长度为：(n+1)/2 。11理想情况下，在散列表中查找一

35、个元素的时间复杂度为：O1。12散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法。13二叉排序树是一种动态查找表。14处理冲突的两类主要方法是开放定址法和拉链法或链地址法。15设有 100个元素，用二分查找时，最少的比拟次数是 1 次。三选择题 第 1 章 1数据构造通常是研究数据的 A 及它们之间的相互联系。A.存储构造和逻辑构造 B.存储和抽象 C.联系和抽象 D.联系与逻辑 2执行以下语句的时间复杂度为：B 。s=0;for (i=1;i=n;i+)s=s+i;A.O1 B.On C.On2 D.On3 3数据构造中，在逻辑上可以把数据构造分成：C 。A.动态构造和静

36、态构造 B.紧凑构造和非紧凑构造 C.线性构造和非线性构造 D.内部构造和外部构造 4某程序的时间复杂度为3n+log2n+n2+15其数量级表示为 B A.On B.On2 C.Olog2n D.Onlog2n 5非线性构造的数据元素之间存在 B 。A.一对多关系 B.多对多关系 C.多对一关系 D.一对一关系 6以下时间复杂度中最坏的是 D A.O1 B.O n C.Olog2n D.On2 7以下任何两个结点之间都没有逻辑关系的是 D A.图型构造 B.线性构造 C.树型构造 D.集合 8存储的存储构造所占存储空间 A 。A分两局部，一局部存放结点的值，另一局部存放表示结点间关系的指针

37、B只有一局部，存放结点值 C只有一局部，存储表示结点间关系的指针 D分两局部，一局部存放结点值，另一局部存放结点所占单元素 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展

38、随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插.v .9一个存储结点存放一个 B A.数据项 B.数据元素 C.数据构造 D.数据类型 10以下时间复杂度中最好的是 A A.O1 B.O n C.Olog2n D.On2 11每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是 B 存储方式 A.顺序 B.链式 C.索引 D.散列 12以下算法的实际复杂度是 D for (i=0;in;i+)for (j=0;in;j+)cij=i+j;A.O1 B.O n C.Olog2n D.On2 13数据元

39、素是数据的根本单位，其内 B 数据项。A.只能包括一个 B.可以包括多个 C.不包括 D.可以包括也可以不包括 14.数据构造中，与所使用的计算机无关的是数据的 C 构造；A.存储 B.物理 C.逻辑 D.物理和存储 15数据的逻辑构造是 A 关系的整体 A.数据元素之间逻辑 B.数据项之间逻辑 C.数据类型之间 D.存储构造之间 第 2 章 1 用单链表方式存储的线性表，存储每个结点需要两个域，一个数据域，另一个是 B 。A当前结点所在地址域 B指针域 C空指针域 D空闲域 2在具有 n 个结点的单链表中，实现 A 的操作，其算法的时间复杂度都是 On。A遍历链表和求链表的第 i 个结点 B

40、在地址为 P 的结点之后插入一个结点 C删除开场结点 D删除地址为 P 的结点的后继结点 3设 a，b，c 为三个结点，p，10，20，代表地址，那么如下存储构造称为 B 。A 循环链表 B单链表 C双向循环链表 D双向链表 4一个顺序存储的线性表，设每个结点需占 m 个存储单元，假设第一个结点的地址 B，那么第 i个结点的地址为 A 。A B+(i-1)*m BB+i*m C B-i*m D B+(i+1)*m 5单链表的存储密度 C 。A大于 1 B等于 1 C小于 1 D不能确定 6在 n 个结点的顺序表中，算法的时间复杂度是 O(1)的操作是 A 。A访问第 i 个结点(1=i-n)和

41、求第 i个结点的直接前驱(2=i=n)a 10 c b 20 P 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的

42、存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插.v .B在第 i 个结点之后插入一个新结点(1=i=n)C删除第 i 个结点(1=inext=P CP-next=NULL DP-next=L 9一维数组和线性表的区别是 A 。A前者长度固定，后者长度可变 B后者长度固定，前者长度可变 C两者长度都固定 D两者长度都可变 10指针 P 所指的元素是双循环链表 L 的尾元素的条件是 D 。AP=L BP-prori=L CP=NULL DP-next=L 11一个向量第一个元素的存储地址是 100，每个元素的长度为 2，那么第 5 个元素的地址是 B A110 B108

43、C100 D120 12两个指针 P 和 Q，分别指向单链表的两个元素，P 所指元素是 Q 所指元素前驱的条件是。AP-next=Q-next BP-next=Q CQ-next=P DP=Q 13向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 B 个元素。A8 B63.5 C63 D7 14用链表存储的线性表，其优点是 C 。A便于随机存取 B花费的存储空间比顺序表少 C便于插入和删除 D数据元素的物理顺序与逻辑顺序一样 15单链表的示意图如下：L A B C D P Q R 指向链表 Q 结点的后继的指针是 D AL BP CQ DR 第 3 章 个数据构造

44、是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插.v

45、 .1每次从无序表中取出一个元素，把它插入到有序表中的适当位置，这种排序方法叫 C 。A选择 B交换 C插入 D归并 2快速排序方法在 C 情况下最不利于发挥其长处。A要排序的数据量太大 B要排序的数据中含有多个一样值 C.要排序的数据已根本有序 D.要排序的数据个数为奇数 3排序方法中，从无序序列中选择关键字最小的记录，将其与无序区初始为空的第一个记录交换的排序方法，称为:(D )。A希尔排序 B归并排序 C插入排序 D.选择排序 4在待排序的元素序列根本有序的前提下，效率最高的排序方法是：A 。A直接插入 B冒泡排序 C希尔排序 D选择排序 5每次把待排序方的区间划分为左、右两个区间，其中

46、左区间中元素的值不大于基准元素的值，右区间中元素的值不小于基准元素的值，此种排序方法叫做 C 。A冒泡排序 B堆排序 C快速排序 D.归并排序 6排序是根据 A 的大小重新安排各元素的顺序。A关键字 B数组 C元素件 D结点 7堆的形状是一棵 D 。A二叉排序树 B满二叉树 C不是二叉树 D.完全二叉树 8 稳定的排序方法是指在排序前后，关键字值相等的不同记录间的前后相对位置 B 。A保持相反 B保持不变 C不定 D无关 9下述几种排序方法中，要求内存量最大的是：D 。A插入排序 B选择排序 C快速排序 D.归并排序 10直接插入排序的方法是 B 的排序方法。A不稳定 B稳定 C外部 D选择

47、11直接插入排序的方法要求被排序的数据 B 存储。A必须链表 B必须顺序 C顺序或链表 D可以任意 12设有 1000 个无序元素，希望用最快的速度挑选出其中前 10 个最大的元素，最好选用 B 排序法。A冒泡排序 B堆排序 C快速排序 D.归并排序 13用快速排序法对 n 个元素进展排序时，最坏情况下的执行时间为 A AOn2 BOlog2n COnlog2n D.O n 14一个数据序列的关键字为：46，79，56，38，40，84，采用快速排序，并以第一个数为基准得到第一次划分的结果为：C A 38，40，46，56，79，84B40，38，46，79，56，84 C40，38，46，5

48、6，79，84 D40，38，46，56，79，84 15用某种排序方法对关键字序列25，84，21，47，15，27，68，35，20进展排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的

49、顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插.v .15，20，21，25，27，35，47，68，84 那么所采用的排序方法是 D 。A选择排序 B希尔排序 C归并排序 D.快速排序 第 4 章 1顺序栈判空的条件是 C Atop=0 Btop=1 Ctop=-1 Dtop=m 2设有编号为1，2，3，4的四辆列车，顺序进入一个栈式构造的站台，以下不可能的出

50、站顺序为(D )A1234 B1243 C1324 D1423 3插入和删除只能在一端进展的线性表，称为(C )。A队列 B循环队列 C栈 D循环栈 4链栈与顺序栈相比，有一个比拟明显的优点是 B。A插入操作根加方便 B通常不会出现栈满的情况。C不会出现栈空的情况 D删除操作根加方便 5在栈中，出栈操作的时间复杂度为(A )。AO(1)BO(log2n)C0(n)DO(n2)6带头结点的链栈LS的示意图如下，栈顶元素是 A LS H A B C D AA BB CC DD 7元素A,B,C,D依次进栈以后，栈顶元素是 D AA BB CC DD 8顺序栈存储空间的实现使用 B 存储栈元素。A链