《数据结构复习题_计算机-数据结构与算法》由会员分享，可在线阅读，更多相关《数据结构复习题_计算机-数据结构与算法（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对快速排序来说，初始序列为正序或反序都是
4、最坏情况。 10对于 n 个记录的集合进展归并排序，所需的平均时间为 O (nlog2n)。 第 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在栈中插入或删除一个元素
5、应遵守的“后进先出的原那么。 10进位制的换算算法是栈的应用。 11队列是限制在两端进展操作的线性表。 12判断顺序队列为空的标准是头指针和尾指针均指向同一个结点。 13在链队列做出队操作时，会改变 front 指针的值。 14在循环队列中，假设尾指针 rear大于头指针 front，其元素个数为 rear- front。 15队列是一种“先进先出的线性表。 16在循环链队列中无上溢出现象。 17栈和队列都是顺序存储的线性构造。 18栈和队列都是属于线性构造。 19顺序队和循环队的队满和队空的判断条件是一样的。 20在队列中插入或删除一个元素应遵守的先进先出的原那么。 第 5 章 1串的长度是
6、指串中不同字符的个数。 2串是 n 个字母的有限序列。 3空串不等于空格串。 4如果两个串含有一样的字符，那么说明它们相等。 5如果一个串中所有的字母均在另一个串中出现，那么说明前者是后者的子串。 6串的堆分配存储是一种动态存储构造。 7 “DT是“DATA的子串。 8空串与空格串是一样的。 9串中任意个字符组成的子序列称为该串的子串。 10子串的定位运算称为模式匹配。 11n 维的多维数组可以视为 n-1维数组元素组成的线性构造。 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑
7、构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 12稀疏矩阵中非零元素的个数远小于矩阵元素的总数。 13假设采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了
8、对该矩阵的转置运算。 14在稀疏矩阵的三元组表表示法中，每个三元组表示矩阵中数据元素的行号、列号和值。 15上三角矩阵主对角线以上不包括主对角线中的元素 ，均为常数 C。 16对称矩阵、三角矩阵、稀疏矩阵都可以进展压缩存储。 17任何矩阵都可以进展压缩存储。 18在稀疏矩阵的三元组表表示法中，每个三元组表示矩阵中非零元素的行号、列号和值。 19数组元素可以由假设干个数据项组成。 (20稀疏矩阵压缩存储就是为矩阵中非零元素分配一个存储空间。 第 6 章 1树构造中每个结点最多只有一个直接前驱。 2完全二叉树一定是满二查树。 3由树转换成二叉树，其根结点的右子树一定为空。 4在前序遍历二叉树的序列
9、中，任何结点的子树的所有结点都是直接跟在该结点之后。 5用一维数组来存储二叉树时，总是以前序遍历存储结点。 6二叉树的前序遍历和后序遍历并不能唯一确定这棵二叉树，因为不知道根结点是哪一个。 7二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。 8由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。 9不使用递归，也可以实现二叉树的前序、中序和后序遍历。 10在完全二叉树中，假设一个结点没有左孩子，那么它必然是叶子结点。 第 7 章 1图可以没有边，但不能没有顶点。 2在无向图中， V1，V2与V2，V1是两条不同的边。 3邻接表只能用于有向图的存储。 4用邻接矩阵法存储一个图
10、时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。 5一个图的邻接矩阵表示是唯一的。 6有向图不能进展广度优先遍历。 7一个图的最小生成树是该图所有生成树中权最小的生成树。 8存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角或下三角局部就可以了。 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存
11、储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 9有向图的邻接矩阵一定是对称的。 10一个图的深度优先遍历的序列是唯一的。 第 8 章 1二分查找法要求待查表的关键字值必须有序。 2哈希法是一种将关键字转换为存储地址的存储方法。 3在二叉排序树中，根结点的值都小于孩子结点的值。 4对有序表而言采用二分查找总比采用顺序查找法
12、速度快。 5二叉排序树是一种特殊的线性表。 6散列存储法的根本思想是由关键字的值决定数据的存储地址。 7哈希法的查找效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。 8一般说来用哈希函数得到的地址，冲突不可能防止，只能尽可能减少。 9选择好的哈希函数就可以防止冲突的发生。 10在二叉排序树上删除一个结点时，不必移动其它结点，只要将该结点的父结点的相应的指针域置空即可。 二填空题 第 1 章 1数据构造是一门研究非数值计算程序设计中计算机的操作对象以及它们之间的关系和运算的学科。 2数据的存储构造形式包括：顺序存储、链式存储、散列存储、索引存储。 3数据构造按逻辑构造可分为两大类，它们
13、分别是：线性构造和非线性构造。 4一个算法的空间复杂度是指该算法所消耗的存储空间，它是该算法求解问题规模 n 的函数。 5数据构造有逻辑构造和存储构造两种构造。 6数据的存储构造形式包括：顺序存储、链式存储、散列存储、索引存储。 7一个算法的效率可分为时间效率和空间效率。 8数据元素是数据的根本单位。 9数据构造主要研究数据的逻辑构造、存储构造和算法。 11数据的逻辑构造是独立于计算机的。 12数据构造被定义为(D，R)，其中 D 是数据的有限集合，R是 D 上的关系的有限集合。 13树形构造构造中的元素之间存在一对多的关系。 14假设一个算法中的语句频度之和为 Tn=125n+3nlog2n
14、，那么算法的时间复杂度为 Onlog2n 。 15数据构造主要研究数据的逻辑构造、存储构造和算法。 第 2 章 1顺序表中逻辑上相邻的元素在物理位置上必须相连。 2在单链表中要在结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个
15、指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 的时间复杂度为 O (n) 。 3线性表是 n 个结点的有限集合。 4链表相对于顺序表的优点有插入、删除方便；缺点是存储密度小。 5链表相对于顺序表的优点有插入、删除方便；缺点是存储密度小。 6顺序表相对于链表的优点是：节省存储和随机存取。 7 对于一个具有n 个结点的单链表， 在 p 所指结点后插入一个新结点的时间复杂度是 O
16、 1 。 8在链表中逻辑上相邻的元素的物理位置不必相连。 9线性表中第一个结点没有直接前趋，称为开场结点。 10在顺序表中访问任意一个结点的时间复杂度均为 O (1) 。 11在 n 个结点的单链表中要删除结点*P，其时间复杂度为 O (1) 。 12在单链表中需知道头指针才能遍历整个链表。 13在一个单链表中，在指针 p 所指向的结点之后插入指针 s 所指向的结点时，应执行s-next=p-next和 p-next=s 操作。 14 在一个长度为 n 的顺序表中， 如果要在第 i 个元素前插入一个元素， 要后移 n- i +1 个元素。 15在双向链表中，每个结点都有两个指针域，它们一个指向
17、其前趋结点，另一个指向其后继结点。 第 3 章 1 根据被处理的数据在计算机中使用不同的存储设备，排序可分为：内排序和外排序。 2 评价排序算法优劣的主要标准是时间复杂性和算法所需的附加空间。 3插入排序、堆排序、归并排序中，排序是不稳定的有：堆排序。 4在对一组记录54，38，96，23，15，72，60，45，83进展直接插入排序时，当把第 7个记录 60插入到有序表时，为寻找插入位置需比拟 3 次。 5对 n 个关键字进展冒泡排序，其可能的最小比拟次数为： n-1 次。 6内排序是指整个排序过程，全部在计算机的内存中进展。 7大多数排序算法都有两个根本的操作：比拟和移动。 8在插入排序和
18、选择排序中，假设初始数据根本正序，那么选用插入排序较好。 9在排序前，关键字值相等的不同记录，排序后相对位置变化的排序方法，称为不稳定的排序方法。 10假设原始数据接近无序，那么选用快速排序最好。 11对于 n 个记录的集合进展归并排序，所需要的平均时间为： Olog2n 。 12在插入排序、归并排序、快速排序中，排序是不稳定的有：快速排序。 13对一组记录54，35，96，21，12，72，60，44，80进展直接选择排序时，第四次选择和交换后，未排序记录是 54，72，60，96，80 。 14对于 n 个记录的集合进展，假设对其进展快速排序，在最坏的情况下所需要的时间是 O(n2) 。
19、个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性
20、表的插. . . v . 15在最坏情况下，在第 i趟直接插入排序中，要进展 i-1 次关键字的比拟。 第 4 章 1在栈中存取数据遵从的原那么是：后进先出。 2在有n个元素的栈中，进栈操作的时间复杂度为 O1。 3后进先出的线性表称为栈。 4在顺序栈中，当top=MAXLEN-1 时，表示栈满。 5. 栈是输入、输出受限制的线性表。 6在有n个元素的栈中，出栈操作的时间复杂度为 O1。 7在栈构造中，允许插入、删除的一端称为栈顶。 8顺序栈S存在数组S-data0.MAXLEN-1中，出栈操作时要执行的语句有：S-top - 。 9在顺序栈中，当栈顶指针top=-1时，表示栈空。 10向一个
21、栈顶指针为top 的链栈插入一个新结点*p时，应执行p-next=top ；和top=p ；操作。 11同一栈的各元素的类型一样。 12栈只能在栈顶插入和删除元素。 13顺序栈 S，在对 S 进展出栈操作之前首先要判断栈是否空。 14假设进栈的次序是 A、B、C、D、E，执行三次出栈操作以后，栈顶元素为 B 。 15从一个栈删除元素时，首先取出栈顶元素，然后再移动栈顶指针。 16在队列中存取数据应遵从的原那么是先进先出。 17设长度为n的链队列用单循环链表表示，假设只设头指针，那么入队操作的时间复杂度为 On。 18在队列中，允许插入的一端称为队尾。 19设长度为n的链队列用单循环链表表示，假
22、设只设头指针，那么出队操作的时间复杂度为 01。 20设循环队列的头指针front 指向队头元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN ，那么队空的标志为 front=rear 。 21队列在进展出队操作时，首先要判断队列是否为空。 22设循环队列的头指针front 指向队头元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN ，那么队满标志为 front=(rear+1)% MAXLEN 。 23在一个链队列中，假设队头指针为front ，队尾指针为rear，那么判断该队列只有一个结点的条件为： front=rear & fron
23、t NULL 。 24队列构造的元素个数是可变的。 25设长度为n的链队列用单循环链表表示，假设只设尾指针，那么出队操作的时个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展
24、随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 间复杂度为 01。 26设长度为n的链队列用单循环链表表示，假设只设尾指针，那么入队操作的时间复杂度为 01。 27链队列为空时，LQ-front-next= NULL 。 28设循环队列的头指针front 指向队头元素，尾指针rear指向队尾元素后的一个空闲 元 素 ， 队 列 的 最 大 空 间 为 MAXLEN ， 当 rearfront 时 ， 队 列 长 度 是 MAXLEN-front 。 29向一个循环队列中插入元素时，首先要移动队
25、尾指针，然后再向指针所指位置写入新的元素。 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(s)=_ 20 。 7由零个或多个字符组成的
26、有限序列称为字符串或串。 8字符串按存储方式可以分为：顺序存储、存储和堆分配存储。 9设S=“A:/mydocument/text1.doc ，那么 strlen(S)= 23 。 10在空串和空格串中，长度不为 0 的是空格串。 11串顺序存储紧凑格式的优点是：空间利用率高 ,对串的字符处理效率低。 12两个串相等是指两个串相长度等，且对应位置的字符都一样。 13串顺序存储紧凑格式的缺点是对串的字符处理效率低。 14模式匹配成功的起始位置称为：有效位移。 15所有模式匹配不成功的起始位置称为：无效位移。 16.多维数组的顺序存储方式有行优先顺序存储和列优先顺序存储两种。 17.同一数组中各元
27、素的长度相等。 18.在多维数组中，数据元素的存放地址可以直接通过地址计算公式算出，所以多维数组是一种随机存取构造。 19. 在n维数组中的每一个元素最多可以有 n 个直接前驱。 20.输出二维数组Amn中所有元素值的时间复杂度为 O(m*n) 。 数组元素a0.20.3的实际地址上2000，元素长度是4，那么Loc1,2= 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方
28、法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 2024 。 21.数组的三元组存储是对稀疏矩阵的压缩存储 22.稀疏矩阵的三元组有 3 列。 23.稀疏矩阵的三元组中第1列存储的是数组中非零元素所在的行数。 24.n阶对称矩阵，如果只存储下三角元素，只需要 nn-1 /2 个存储单元。 25
29、.稀疏矩阵A如以下图所示，其非零元素存于三元组表中，三元组4，1，5按行优先顺序存储在三元组表的第 6 项。 26.稀疏疏矩阵的压缩存储方法通常有三元组表和十字链表两种。 27 n阶下三角矩阵，因为对角线的上方是同一个常数，需要 nn-1 /2+1 个存储单元。 28稀疏矩阵中有 n 个非零元素，那么三元组有 n 行。 29.稀疏矩阵的三元组中第 2 列存储的是数组中非零元素所在的列数。 30.稀疏矩阵的三元组中，第3列存储的是稀疏数组中的非零元素。 第 6 章 1在树中，一个结点所拥有的子树数称为该结点的度。 2一棵含有 n 个结点的完全二叉树，它的高度是 | log2n |+1 。 下取整
30、 3度为零的结点为叶子结点或叶结点 。 4一棵深度为 h 的完全二叉树上的结点总数最少为 2 h-1个。 5树内各结点度的最大值称为树的度。 6一棵深度为 h 的完全二叉树上的结点总数最多为 2 h-1 个。 7树中结点的最大层次称为树的深度或高度 。 8三个结点可以组成 2 种不同形态的树。 9由树转换成二叉树时，其根结点没有右子树。 10有 20个结点的完全二叉树，编号为 10的结点的左儿子结点的编号是 20 。 11在树中，一个结点的直接子结点的个数称为该结点的度。 12由二叉树的后序和中序遍历序列，可以唯一确定一棵二叉树。 13给定如以下图所示的二叉树，其前序遍历序列为： ABEFHC
31、G 。 A B F G HC E 8 0 0 0 0 0 0 11 0 0 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= 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线
32、性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 14给定如以下图所示的二叉树，其层次遍历序列为： ABCEFGH 。 15 将一棵完全二叉树按层次编号， 对于任意一个编号为 i 的结点， 该结点右孩子的编号为： 2*i+1 。 第 7 章 1图有： _邻接矩阵_ 和邻接表等存储构造。 2 n 个顶点e条边的图假设采用邻接矩阵存储， 深度优先遍历算法的时间复杂度为： O n2 。 3图的遍历有：深度优先搜和 _广度优先搜
33、 _等方法。 4n 个顶点 e 条边的图假设采用邻接矩阵存储，那么空间复杂度为： _ On2_。 5图有：邻接矩阵和邻接表等存储构造。 6假设图 G 中每条边都 _无方向，那么 G 为无向图。 7在具有 n 个顶点的图的生成树中，含有 n-1 条边。 8有向图的边也称为 _弧_ 。 9图的邻接矩阵表示法是表示 _顶点_之间相邻关系的矩阵。 10有向图 G 用邻接矩阵存储，其第 i 行的所有元素之和等于顶点 i 的 _出度_。 11图的深度优先遍历序列 _不是_唯一的。 12设有一稀疏图 G，那么 G 采用 _邻接表_存储比拟节省空间。 13从图中某一顶点出发，访遍图中其余顶点，且使每一顶点仅被
34、访问一次，称这一过程为 图的遍历或遍历 。 14遍历图的两种根本方法是：深度优先遍历和广度优先遍历。 15有向图的邻接表表示适于求顶点的出度。 第 8 章 1顺序查找法，表中元素可以任意存放。 2散列表查找法的平均查找长度与元素个数 n 无关。 A B F G HC E 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序
35、链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 3快速排序是对冒泡排序的一种改良。 4在哈希函数 H(key)=key % P 中，P 一般应取质数。 5二分查找的存储构造仅适用于顺序存储构造，而且关键字有序的。 6在分块查找方法中，首先查找索引，然后再查找相应的块。 7二分查找法，表中元素必须按关键字有序存放。 8在分块查找方法中，表中元素每块内
36、的元素可以任意存放，块与块之间必须有序存放。 9顺序查找、二分查找、分块查找都属于静态查找。 10顺序查找法，其平均查找长度为： (n+1)/2 。 11理想情况下，在散列表中查找一个元素的时间复杂度为： O1 。 12散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法。 13二叉排序树是一种动态查找表。 14处理冲突的两类主要方法是开放定址法和拉链法或链地址法 。 15设有 100个元素，用二分查找时，最少的比拟次数是 1 次。 三选择题 第 1 章 1数据构造通常是研究数据的 A 及它们之间的相互联系。 A. 存储构造和逻辑构造 B. 存储和抽象 C. 联系和抽象 D.
37、联系与逻辑 2执行以下语句的时间复杂度为： B 。 s=0; for (i=1;i=n; i+) s=s+i; A. O1 B. On C. On2 D. On3 3数据构造中，在逻辑上可以把数据构造分成： C 。 A. 动态构造和静态构造 B. 紧凑构造和非紧凑构造 C. 线性构造和非线性构造 D. 内部构造和外部构造 4某程序的时间复杂度为3n+log2n+n2+15其数量级表示为 B A. On B. On2 C. Olog2n D. Onlog2n 5非线性构造的数据元素之间存在 B 。 A. 一对多关系 B. 多对多关系 C. 多对一关系 D. 一对一关系 6以下时间复杂度中最坏的是
38、 D A. O1 B. O n C. Olog2n D. On2 7以下任何两个结点之间都没有逻辑关系的是 D A. 图型构造 B. 线性构造 C. 树型构造 D. 集合 8存储的存储构造所占存储空间 A 。 A分两局部，一局部存放结点的值，另一局部存放表示结点间关系的指针 B只有一局部，存放结点值 C只有一局部，存储表示结点间关系的指针 D分两局部，一局部存放结点值，另一局部存放结点所占单元素 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按
39、使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 9一个存储结点存放一个 B A. 数据项 B. 数据元素 C. 数据构造 D. 数据类型 10以下时间复杂度中最好的是 A A. O1 B. O n C. Olog2n D.
40、 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数据元素是数据的根本单位，其内 B 数据项。 A. 只能包括一个 B. 可以包括多个 C. 不包括 D. 可以包括也可以不包括 14. 数据构造中，与所使用的计算机无关的是数据的 C 构造； A.存储 B. 物理 C.逻辑 D. 物理和存储 15数据的逻辑构造是 A 关系的整体
41、A. 数据元素之间逻辑 B. 数据项之间逻辑 C. 数据类型之间 D. 存储构造之间 第 2 章 1 用单链表方式存储的线性表， 存储每个结点需要两个域， 一个数据域， 另一个是 B 。 A当前结点所在地址域 B指针域 C空指针域 D空闲域 2在具有 n 个结点的单链表中，实现 A 的操作，其算法的时间复杂度都是 On 。 A遍历链表和求链表的第 i 个结点 B在地址为 P 的结点之后插入一个结点 C删除开场结点 D删除地址为 P 的结点的后继结点 3设 a，b，c 为三个结点，p，10，20，代表地址，那么如下存储构造称为 B 。 A 循环链表 B单链表 C双向循环链表 D双向链表 4一个顺
42、序存储的线性表，设每个结点需占 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)和求第 i个结点的直接前驱(2=i=n) a 10 c b 20 P 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的
43、逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . B在第 i 个结点之后插入一个新结点(1=i=n) C删除第 i 个结点(1=inext= = P CP-next= = NULL
44、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 C100 D120 12两个指针 P 和 Q，分别指向单链表的两个元素，P 所指元素是 Q 所指元素前驱的条件是 。 AP-next= =Q-next BP-next
45、= = 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 章 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造
46、是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 1每次从无序表中取出一个元素，把它插入到有序表中的适当位置，这种排序方法叫 C 。 A选择 B交换 C插入 D归并 2
47、快速排序方法在 C 情况下最不利于发挥其长处。 A要排序的数据量太大 B要排序的数据中含有多个一样值 C. 要排序的数据已根本有序 D. 要排序的数据个数为奇数 3排序方法中，从无序序列中选择关键字最小的记录，将其与无序区初始为空的第一个记录交换的排序方法，称为: ( D )。 A希尔排序 B归并排序 C插入排序 D. 选择排序 4在待排序的元素序列根本有序的前提下，效率最高的排序方法是： A 。 A直接插入 B冒泡排序 C希尔排序 D选择排序 5每次把待排序方的区间划分为左、右两个区间，其中左区间中元素的值不大于基准元素的值，右区间中元素的值不小于基准元素的值，此种排序方法叫做 C 。 A冒
48、泡排序 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选择 11直接插入排序的方法要求被排序的数据 B 存储。 A必须链表 B必须顺序 C顺
49、序或链表 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，56，79，84 D40，38，46，56，79，84 15用某种排序方
50、法对关键字序列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 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的
51、但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . 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的四辆列车，顺序进入一个栈式构造的站台，以下不可能的出站顺序为 ( D ) A1234 B1243 C132
52、4 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链表B数组 C循环链表 D
53、变量 9在C或C+ 语言中，一个顺序栈一旦被声明，其占用空间的大小 A 。 A已固定 B不固定 C可以改变 D动态变化 10当栈中的元素为n个，做进栈运算时发生上溢，那么说明该栈的最大容量为 C 。 An-1 Bn+1 Cn Dn/2 11栈与一般线性表的区别在于 ( B )。 A数据元素的类型不同 B运算是否受限制 C数据元素的个数不同 D逻辑构造不同 12设有一个顺序栈S，元素A,B,C,D,E,F,依次进栈，如果六个元素出栈的顺序是B，个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数
54、据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . D，C，F，E，A，那么栈的容量至少应是 ( A )。 A3 B4 C5 D 6 13在栈顶一端可进展 D 操作。 A插入 B删
55、除 C进栈 D插入和删除 14从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行以下 ( D )命令。 Ax=top;top=top-next; Btop=top-next;x=top-data; Cx=top-data; Dx=top-data;top=top-next; 15在一个栈顶指针为HS的链栈中，将一个S指针所指的结点入栈，应执行以下 ( B )命令。 AHS-next=S; BS-next=HS-next;HS-next=S; CS-next=HS-next;HS=S; DS-next=HS;HS=HS-next; 16在队列中存取数据应遵循的原那么是(
56、A )。 A先进先出 B后进先出 C先进后出 D随意进出 17设长度为n的链队列用单循环链表表示，假设只设头指针，那么人队操作的时间复杂度为( C )。 AO(1) BO(log2n) CO(n) DO(n2) 18一个循环队列一旦说明，其占用空间的大小 A 。 A已固定 B可以变动 C不能固定 D动态变化 19当利用大小为n的数组顺序存储一个队列时，该队列的最后一个元素的下标为 B 。 An-2 Bn-1 Cn Dn+1 20设长度为n的链队列用单循环链表表示，假设只设尾指针，那么出队操作的时间复杂度为( A )。 AO(1) BO (log2n) CO(n) DO(n2) 21队列是限定在
57、 D 进展操作的线性表。 A中间 B队头 C队尾 D端点 22假设进队的序列为：A，B，C，D，那么出队的序列是 C 。 AB，C，D，A BA，C，B，D CA，B，C，D DC，B，D，A 23从一个顺序循环队列删除一个元素时，首先需要做的操作是 B 。 A队头指针减1 B取出队头指针所指的元素 C队头指针加1 D取出队尾指针所指的元素 24. 在一个顺序存储的循环队列中，队头指针指向队头元素的 A 位置。 A前一个 B后一个 C后面 D当前 25四个元素按：A，B，C，D顺序连续进队Q，执行一次OutQueue(Q) 操作后，队头元素是 B 。 A A B B C C D D 个数据构造
58、是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插.
59、. . v . 26队列中的元素个数是( B )。 A不变的B可变的C任意的D0 27设链栈中结点的构造：data为数据域，next为指针域，且top是栈顶指针。假设想在链栈的栈顶插入一个由指针s所指的结点，那么应执行以下 A 操作。 As-next=top-next；top-next=s Btop-next=s Cs-next=top；top=top-next Ds-next=top；top=s 28假设用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再参加两个元素后，front和rear的值分别为( B )。 A5和1 B4和2 C2
60、和4 D1和5 29以下属于队列的操作有( D )。 A在队首插入元素 B删除值最小的元素 C按元素的大小排序 D判断是否还有元素 30.带头结点的链队列LQ示意图如下，LQ为空时 A LQ-front H A B C D LQ-rear ALQ-front= LQ-rear BLQ-rear=NULL CLQ-front!= LQ-rear DLQ-front=null 第5章 1串是一种特殊的线性表，其特殊性表达在 B 。 A.可以顺序存储 B数据元素是一个字符 C.可以存储 D数据元素可以是多个字符 2设目标串T=AABBCCDDEEFF ，P=CCD ，那么该模式匹配的有效位移为 (
61、C )。 A2 B3 C4 D. 5 3设有两个串p和q，求q在p中首次出现的位置的运算称作( B )。 A.连接 B模式匹配 C.求子串 D求串长 4. S1=sdudent，S2=SDUDENT ，执行串比拟函数EqualStr(S1,S2) 后的结果为( C )。 A0 B小于0 C大于0 D不确定 5串的模式匹配是指 D 。 A判断两个串是否相等 B对两个串比拟大小 C找某字符在主串中第一次出现的位置 D找某子串在主串中第一次出现的第一个字符位置 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储
62、构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 6朴素模式匹配算法在最坏情况下的时间复杂度是( D )。 AOm BOn C0m+n D0m*n 7以下论断正确的
63、选项是( A )。 A是空串， 空格串 BBEIJING 是BEI JING 的子串 CsomethingSomethig DBIT=BITE 8. S1=Today is，S2=30 July 2005，执行串连接函数ConcatStr(S1,S2)后的结果为( A )。 AToday is 30 July 2005 B30 July 2005 CToday is D30 July 2005 Today is 9某串的长度小于一个常数，那么采用 B 存储方式最节省空间。 A链式 B顺序 C堆构造 D无法确定 10. S=Today is 30 July 2005 ，LenStr(S)=( D
64、 )。 A18 B19 C20 D21 11设有两个串S1和S2，那么EqualStr(S1,S2)运算称作( D )。 A. 串连接 B模式匹配 C. 求子串 D串比拟 12. S1=good ， S2=morning ， 执 行 串 连 接 函 数 ConcatStr(S1,S2) 后 的 结 果 为( A )。 Agoodmorning Bgood morning CGOODMORNING DGOOD MORNING 13在实际应用中，要输入多个字符串，且长度无法预定，那么应该采用 C 存储方式比拟适宜。 A链式 B顺序C堆构造 D无法确定 14. 设串S1=I AM，S2=A SDUD
65、ENT, 那么ConcatStr(S1,S2)=( B )。 AI AM BI AM A SDUDENT CIAMASDUDENTD. A SDUDENT 15. 以下论述正确的选项是 C 。 A空串与空格串是一样的Btel是Teleptone的子串 C空串是零个字符的串 D. 空串的长度等于1 16. 在一个m维数组中， D 恰好有m个直接前驱和m个直接界后继。 A.开场结点 B总终端结点 C.边界结点 D内部结点 17. 多维数组的体积与 A 无关。 A数组的基地址 B维数 C各维的上下界 D结点的大小 18. 对下述矩阵进展压缩存储后，失去随机存取功能是 D 。 A对称矩阵 B三角矩阵
66、C三对角矩阵 D稀疏矩阵 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查
67、找任何一个元素顺序存储线性表的插. . . v . 19. 在按行优先顺序存储的三元组表中，下述陈述错误的选项是 D 。 A 同一行的非零元，是按列号递增次序存储的 B 同一列的非零元，是按行号递增次序存储的 C 三元组表中三元组行号递增的 D 三元组表中三元组列号递增的 20. 以下 C 是稀疏矩阵的压缩存储方法。 A一维数组 B二维数组 C三元组表 D广义表 21. 对稀疏矩阵进展压缩存储是为了 B 。 A降低运算时间 B节约存储空间 C便于矩阵运算 D便于输入和输出 22. 假设数组A0.m0.n按列优先顺序存储，那么aij的地址为 A 。 ALOC(a00)+j*m+i BLOC(a0
68、0)+j*n+i CLOC(a00)+(j-1)*n+i-1 DLOC(a00)+(j-1)*m+i-1 23. 以下矩阵是一个 B A对称矩阵 B三角矩阵 C稀疏矩阵 D带状矩阵 24.在稀疏矩阵的三元组表示法中，每个三元组表示 D 。 A 矩阵中非零元素的值 B 矩阵中数据元素的行号和列号 C 矩阵中数据元素的行号、列号和值 D 矩阵中非零数据元素的行号、列号和值 25. 二维数组A610， 每个数组元素占4个存储单元， 假设按行优先顺序存放数组元素a35的存储地址是1000，那么a00的存储地址是 B 。 A872 B860 C868D864 26. 二维数组A810中，a12的地址为1
69、000，那么a00的地址为 C 。 A972 B979 C980D982 27. 数组与一般线性表的区别主要在 C 。 A不能进展插入操作 B不能进展删除操作 C逻辑构造方面 D存储方面 28. 数组是一个 B 线性表构造。 A非 B推广了的 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个
70、指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . C加了限制的 D不加限制的 29. 数组A0:1,0:1,0:1 共有 D 元素。 A4 B5 C6 D8 30. 二维数组a44，数组的元素起始地址Loc00=1000，元素长度为2，那么Loc00为 D 。 A1000 B1008 C1010D1020 第 6 章 1树最适合用来表示 D 。 A有序数据元素 B无序数据元素
71、C元素之间无联系的数据 D元素之间有分支层次的关系 2对于一棵满二叉树，m 个树叶，n 个结点，深度为 h，那么 D 。 An=h+m Bh+m=2n Cm：h-1 Dn=2h-1 3结点前序为 ABC 的不同二叉树有 C 形态。 A3 B4 C5 D6 4以下 4 棵树中， B 不是完全二叉树。 A B C D 5根据二叉树的定义，具有 3 个结点的二叉树有 C 种树型。 A3 B4 C5 D6 6如右图所示的二叉树，先序遍历的序列是 B A A、B、C、D、E、F、G 、H、I B A、B、D、H、I、E、C、F、G C H、D、I、B、E、A、F、C、G D H、I、D、E、B、F、G、
72、C、A 7以下存储形式中，哪一个不是树的存储形式 D 。 A B E G FC D A B E F C D A B E C D A B C D A BD E C F G H I 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单
73、元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . A数组存储法 B双亲表示法 C孩子链表表示法 D孩子兄弟表示法 8具有 35个结点的完全二叉树的深度为 B A5B6 C7D8 9对于二叉树来说，第 K 层至多有 C 个结点。 A 2KB2K-1 C2K-1 D2K-1-1 10线索二叉树是一种 A 。 A物理 B逻辑 C逻辑和存储 D线性 11一棵 n 个结点的二叉树，其空指针域的个数为 B 。 An Bn+1 Cn-1 D不确定 12如右
74、图所示的二叉树，中序遍历的序列是 C A A、B、C、D、E、F、G 、H、I B A、B、D、H、I、E、C、F、G C H、D、I、B、E、A、F、C、G D H、I、D、E、B、F、G、C、A 13二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索，这种说法 B 。 A正确 B错误 C不确定 D都有可能 14深度为 K 的二叉树至多有 B 个结点。 A 2KB2K-1 C2K-1 D2K-1-1 15A，B 为一棵二叉树上的两个结点，在中序遍历时，A 在 B 前的条件是 C 。 AA 在 B 右方 BA 是 B 祖先 CA 在 B 左方 DA 是 B 子孙 第 7 章 1在一个
75、图中，所有顶点的度数之和等于图的边数的( C )倍。 A1/2 B. 1 C. 2 D. 4 2生成树的构造方法只有 B 。 A深度优先 B深度优先和广度优先 C无前驱的顶点优先 D无后继的顶点优先 3在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的( B )倍。 A1/2 B. 1 C. 2 D. 4 4下面的各种图中， C 的邻接矩阵一定是对称的。 AAOE 图 BAOV 图 C无向图 D有向图 5无向图顶点 v 的度是关联于该顶点 B 的数目。 A顶点 B边 C序号 D下标 A BD E C F G H I 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数
76、据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 6有 n 个顶点的有向图的邻接矩阵是用 B
77、数组存储。 A一维 Bn 行 n 列 C任意行 n 列 Dn 行任意列 7有 n 个条边的无向图的邻接矩阵表存储法中，链表中结点的个数是 C 个。 An/2 Bn C2n Dn*n 8在图的表示法中，表示形式唯一的是 A 。 A邻接矩阵表示法 B邻接表表示法 C逆邻接表表示法 D邻接表和逆邻接表表示法 9最小生成树的构造可使用 A 算法。 Aprim 算法 B卡尔算法 C哈夫曼算法 D迪杰斯特拉算法 10在以下图中，度为 3 的结点是 B 。 AV1 B. V2 C. V3 D. V4 11具有 4 个顶点的无向完全图有 A 条边。 A6 B12 C 16 D20 12 按广度优先进展遍历，那
78、么可能得到的一种顶点序列为 B 。 A a，b，e，c，d，f B a，b，e，c，f，d C. a，e，b，c，f，d D. a，e，d，f，c，b 13连通分量是 C 的极 XX 通子图。 A树 B图 C无向图 D有向图 14强连通分量是 D 的极大强连通子图。 A树 B图 C无向图 D有向图 15任何一个连通图的生成树 ( C )。 A可能不存在 B. 只有一棵 C. 有一棵或多棵 D. 一定有多棵 第 8 章 1顺序查找法适合于存储构造为 B 的线性表。 A散列存储 B顺序存储或存储 C压缩存储 D索引存储 1 2 3 5 4 a b c f d e 个数据构造是由一个逻辑构造和这个逻
79、辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 2采用二
80、分查找方法查找长度为 n 的线性表时，每个元素的平均查找长度为 D 。 AO(n2) BO(nlog2n) C. O(n) DO(log2n) 3对线性表进展二分查找时，要求线性表必须 D 。 A以顺序方式存储 B以方式存储，且结点按关键字有序排序 C以方式存储 D以顺序方式存储，且结点按关键字有序排序 4采用顺序查找方法查找长度为 n 的线性表时，每个元素的平均查找长度为 C 。 An Bn2 C(n+1)2 D(n-1) 2 5如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用 A 查找方法。 A分块 B顺序 C二分 D散列 6设哈希表长 m=14，哈希函数 H(key)=
81、key11。表中已有 4 个结点： addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7 其余地址为空。如用二次探测再散列处理冲突，关键字为 49的结点的地址是 D 。 A8 B3 C5 D9 7有一个长度为 12的有序表，按二分查找法对该表进展查找，在表内各元素等概率情况下查找成功所需的平均比拟次数为 B 。 A3512 B3712 C3912 D4312 8平衡二叉树的各结点左右子树深度之差不能为 D 。 A-1 B0 C1 D2 9以下 C 不是利用查找表中数据元素的关系进展查找的方法。 A平衡二叉树 B有序表的查找 C. 散列查找 D二叉排序树的查找
82、10100个元素采用二分查找时，最大的比拟次数是 C 。 A25 B50 C7 D10 11冲突指的是 C 。 A两个元素具有一样序号 B. 两个元素的键值不同 C不同键值对应一样的存储地址 D两个元素的键值一样 12线性表必须是 B ，才能进展二分查找方法查找。 A顺序存储的线性表 B顺序存储的有序表 C. 链表存储的线性表 D链表存储的有序表 13不可能生成以下图所示二叉排序树的关键字序列是 A 。 A 4 5 3 1 2 B 4 2 5 3 1 C 4 5 2 3 1 4 21 3 5 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数
83、据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . D 4 2 3 1 5 14动态查找包括 B 查找。 A顺序表 B. 二叉排
84、序树 C有序表 D索引顺序表 15在查找过程中，不做增加、删除、修改工作，这种查找称为 A 。 A静态查找 B. 内创造 C动态查找 D外查找 四应用题 1根据二元组关系画出逻辑图形，并指出它们属于何种数据构造。 A=D，R ，其中： D=1 ，2，3，4，5，6， R= 1,2,1,6,2,3,2,4, 3,4,3,5,3,6,4,5,5,6 解： 属于图构造 2.根据二元组关系画出逻辑图形，并指出它们属于何种数据构造。 B=D，R ，其中： D=40 ，30，20，60，50，80，70，10， R=, , 解： 属于树构造 3 . 求以下表达式：3+4/(25-(6+15)*8的后缀表达
85、式要求写出过程 解： 3 4 25 6 15 + - / 8 * + 4 . 求以下表达式：A*(B+C)*D-E的后缀表达式要求写出过程 20 30 10 50 80 40 70 60 1 2 6 3 4 5 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各
86、样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 解： A B C + * D * E 5 设有一个栈，元素进栈的次序为：A，B，C，D，E，用I表示进栈操作，O表示出栈操作，写出以下出栈的操作序列。 1C，B，A，D，E 2A，C，B，E，D 解：1IIIOOOIOIO 2IOIIOOIIOO 6. 序列1，2，3 顺序入栈，试写出所有可能的出栈序列。 解：1，2，3 1，3，2 2，1，3 2，3，1 3
87、，2，1 7 按二叉树前序遍历的结果为：ABC，试画出所有不同的二叉树。 解： 8. 二叉树按中序遍历的结果为：ABC，试画出所有不同形态的二叉树。 解： 9. 把以下一般树转换为二叉树 C B A A AC B B A B C A C C B 1 2 4 6 8 5 3 7 1 2 4 6 8 5 3 7 A B C A AC B C B A B B A C C 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造
88、是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 解： 10 把以下森林转换为二叉树 解： 11. 将以下二叉树转换为森林。 解： 12. 将以下二叉树转换为森林。 A B C H DF G E I K A B C H DF G E I J D A B E
89、 G C F F A G H I C D B K E J A B G DE C H I F个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的
90、线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 解： 13. 某二叉树的结点数据采用顺序存储，其构造如下： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 E A F D H C G I B 1画出该二叉树2 分 2写出结点值为 D 的父结点及左、右子树3 分 解： 1 2 D 的父结点为 A D 的左子树为 C D 的右子树为空 14 给定如下图二叉树 T，请画出与其对应的中序线索二叉树。 【2000计算机研究生考题】 A D H F G E C B I D A B I
91、HE C F G J K 3028253340600854个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置
92、用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 解： 1中序遍历序列：55 40 25 60 28 08 33 54 2中序线索二叉树： 15 一棵二叉树结点的中序遍历序列为：DEBAFCHG ，后序遍历序列：EDBFHGCA ，试恢复该二叉树，并写出它的先序遍历的序列。 解：恢复的二叉树 先序遍历序列为：A B D E C F G H 16. 画出表达式：-A+B-C+D 的标识符树，并求它们的后缀表达式。 解： B E G FC H A D + + BC A D 0 NULL NULL 02825334060085455个数据构造是由一个逻辑构造和这个逻
93、辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 后缀表达
94、式：0 A B + C D + 17. 画出表达式： A+B/C-D *E*F+G 的标识符树，并求它们的后缀表达式。 解： 后缀表达式：A B C / + D E F G + * * 后缀表达式：A B C D / * + E * F G * + 18 假设用于通信的电文仅由 A、B、C、D、E、F、G 8 个字母组成，字母在电文中出现的频率分别为 7，19，2，6，32，3，21，10。试为这 8 个字母设计哈夫曼编码。 解：以权值：2、3、6、7、10、19、21、32构造哈夫曼树： A B C + DF G E / + * * 6 5 19 11 28 17 4021 32 60100
95、0 2 37 100 0 0 0 0 1 1 1 1 1 1 0 1 字母编号 对应编码 出现频率 A 1010 7 B 00 19 C 10000 2 D 1001 6 E 11 32 D 10001 3 E 01 21 F 1011 10 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个
96、指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 19. 某图 G 的邻接矩阵如图， 1画出相应的图； 3 分 2要使此图为完全图需要增加几条边。 2 分 解： 1 2完全无向图应具有的边数为：n*n-1 1/2=4*4-1 /2=6 ，所以还要增加 2 条边如右图 。 20. 根据如下有向图，画出邻接矩阵和邻接表。 解 1邻接矩阵 1 2 3 4 5 010000000110
97、000010001011054321 4 23 1 1 3 4 2 0101101001011010 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储
98、位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 2邻接表 1 2 3 5 2 4 3 5 4 1 5 4 21. 一个无向图有 6 个结点，9 条边，这 9 条边依次为0，1，0，2，0，4，0，5，1，2，2，3，2，4，3，4，4，5。试画出该无向图，并从顶点 0出发，分别写出按深度优先搜索和广度优先搜索进展遍历的结点序列。 解： 从顶点 0 出发的深度优先搜索遍历的结点序列：0 1 2 3 4 5 不唯一 。 从顶点 0 出发的广度优先搜索遍历的结点序列：0 1 2 4 5 3 不唯一 。 22. 一个无向图
99、的顶点集为：a，b，c，d，e，其邻接矩阵如下： （1） 画出该图的图形； （2） 写出从顶点 a 出发按深度优先搜索进展遍历的结点序列。 解： 1 2深度优先搜索： a b d c e 或 a b d e c 2 3 10 4 5 a c b e d 0110110110110000100110010个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的
100、物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 23. 图 G 的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。 解： 最小生成树： 8 11 10 3 4 8 13 7 3 4 7 24. 如下图的有向图，请给出该图的: （1） 每个顶点的入/ 出度； （2） 邻接表。 解： 1 2 25 对于给定结点的关键
101、字集合 K=5 ，7，3，1，9，6，4，8，2，10， 1试构造一棵二叉排序树； 2求等概率情况下的平均查找长度 ASL。 解：1构造二叉排序树：2ASL=(1*1+2*2+3*4+4*3)/10=2.9 7 4 3 1 5 9 6 2 5 4 3 1 2 5 4 3 1 0701307040110403101303080111080顶点 1 2 3 4 5 6 入度 3 2 1 1 2 2 出度 0 2 2 3 1 3 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数
102、据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 26 对于给定结点的关键字集合 K=1 ，12，5，8，3，10，7，13，9， 1试构造一棵二叉排序树； 2在二叉树排序 BT 中删除“12后的
103、树构造： 或 27 给定结点的关键字序列为：19，14，23，1，68，20，84，27，55，11，10，79。 设散列表的长度为 13，散列函数为：HK=K % 13。 试画出线性探测再散列解决冲突时所构造的散列表，并求出其平均查找长度。 解：1线性探测再散列解决冲突时所构造的散列表： 0 1 2 3 4 5 6 7 8 9 10 11 12 14 1 68 27 55 19 20 84 79 23 11 10 2平均查找长度 ASL=1*6+2*1+3*3+4*1+9*1/12=30/3=3 8 53 7 13 9 1 10 13 8 53 7 10 1 9 13 8 53 7 12 9
104、 1 10 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素
105、顺序存储线性表的插. . . v . 28 给定结点的关键字序列为：19，14，23，1，68，20，84，27，55，11，10，79。 设散列表的长度为 13，散列函数为：HK=K % 13。 试画出链地址法解决冲突时所构造的哈希表，并求出其平均查找长度。 解： 1链地址法解决冲突时所构造的哈希表。 0 1 14 1 27 79 2 3 68 55 4 5 6 19 84 7 20 8 9 10 23 10 11 11 12 2平均查找长度 ASL=1*6+2*4+3*1+4*1/12 = 21/12 =7/4 (或 1.75) 29 数据序列17，18，60，40，7，32，73，65，
106、85 请写出采用冒泡排序法对该序列作升序排序时每一趟的结果。 解： 17 18 60 40 7 32 73 65 85 第一趟排序结果： 17 18 40 7 32 60 65 73 85 第二趟排序结果： 17 18 7 32 40 60 65 73 第三趟排序结果： 17 7 18 32 40 60 65 第四趟排序结果： 7 17 18 32 40 60 第五趟排序结果： 7 17 18 32 40 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关
107、系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 第五趟排序过程中已无记录交换，排序完毕。 30 数据序列10，8，18，15，7，16，写出采用直接插入算法排序时，每一趟排序的结果。 解： 10 8 18 15
108、7 16 第一趟完毕时结果： 8 10 18 15 7 16 第二趟完毕时结果： 8 10 18 15 7 16 第三趟完毕时结果： 8 10 15 18 7 16 第四趟完毕时结果： 7 8 10 15 18 16 第五趟完毕时结果： 7 8 10 15 16 18 31 数据序列10，1，15，18，7，15，试画出采用快速排序法，第一趟排序的结果。 解 10 1 15 18 7 15 low high 交换 7 1 15 18 10 15 low high 交换 第一趟排序结果： 7 1 10 18 15 15 low high 32 数据序列10，18，4，3，6，12，9，15，写出
109、二路归并排序的每一趟排序结果。 10 18 4 3 6 12 9 15 10 18 3 4 6 12 9 15 第一趟排序结果 3 4 10 18 6 9 12 15 第二趟排序结果 3 4 6 9 10 12 15 18 第三趟排序结果 33 数据序列40，63，11，84，35，93，58，39，15，写出采用简单项选择择排序的每一趟排序结果。 解：40 63 11 84 35 93 58 39 15 11 63 40 84 35 93 58 39 15 11 15 40 84 35 93 58 39 63 11 15 35 84 40 93 58 39 63 11 15 35 39 40
110、 93 58 84 63 11 15 35 39 40 93 58 84 63 11 15 35 39 40 58 93 84 63 11 15 35 39 40 58 63 84 93 11 15 35 39 40 58 63 84 93 11 15 35 39 40 58 63 84 93 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储
111、构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 五程序填空题填上适当的表达式、运算符或语句，每空 1 分，共 5 分 1线性表中的元素是无序的，并以带表头结点的单链表作存储。试写一算法，删除表中所有大于 min，小于 max 的元素。 Void delete (lklist head; datatype min, max)
112、q=head-next; while (p!=NULL) if (p-datadata=max ) q=p; p= p-next ; else q-next= p-next ; delete (p) ; p= q-next ; 2在带头结点的 head 单链表的结点 a 之后插入新元素 x，试完成以下填空。 struct node elemtype data; node *next; ; void lkinsert (node *head, elemtype x) node *s, *p; s= new node ; s-data=_ _x _; p=head-next; while (p!=
113、NULL) & ( p-data!=a ) _p=p-next_; if (p=NULL) coutnext=p-next_; _ p-next=s _; 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适
114、宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 3在顺序存储的线性表第 i 个位置插入新结点 x， typedef struct datatype dataMAXLEN; / 将 data 和 last封装在一个构造体 int last; SeqList; int InsList(SeqList *L,int i,datatype x) / 插入结点函数 int j; if (L-last= =MAXLEN-1) cout 顺序表已满！; return(-1);
115、 if( iL-last+2 ) / 检查插入位置的正确性 coutlast; j=i-1 ; j-) / 结点移动 L-dataj+1=L-dataj ; L-Latai-1= x ; / 新结点插入 L-last + ; 或 L-last= L-last +1 return(1); 4试完成显示队列中所有元素的程序填空。 typedef struct queuenode / 定义队列的存储构造 int data; struct queuenode *next; queuenode; typedef struct / 定义队头、队尾指针 queuenode *front,*rear; lin
116、kqueue; void ShowQueue (linkqueue *q) / 显示队列函数 queuenode *p=q-front ; if (p= = NULL ) cout 队列为空! ; else cout 队列为： ; while ( p!=NULL ) coutdata ; p= p-next ; 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述
117、第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 5下面程序是把两个串 r1 和 r2 首尾的程序，即：r1=r1+r2，试完成程序填空。 typedef Struct char vecMAXLEN; / 定义合并后串的最大长度 int len; / len 为串的长度 St ; void ConcatStr
118、(Str *r1,Str *r2) / 字符串连接函数 int i; coutvec vec; if(r1-len+r2-len MAXLEN ) cout 两个串太长，溢出！; else for(i=0;ilen ;i+) / 把 r2 连接到 r1 r1-vec r1-len+i =r2-veci; r1-vecr1-len+i= 0 ; / 添上字符串完毕标记 r1-len= r1-len+r2-len ; / 修改新串长度 6. 在按行优先顺序存储的三元组表中， 求某列非零元素之和的算法如下， 填空以完成算法。(补构造体声明) if f2(TablSum *a,col) / 求第 co
119、l 列非零元素之和 int k,sun=0; if ( a-t=0 ) printf(“a=0); if ( n=a-n ) printf(“列错！); for ( col=0 ; kt ; k+ ) if (a-tadak.j=n) sum= a-datak.v ; return sum; 7二叉树先序优先遍历 typedef struct BT datatype data; / 定义结点 BT *lchild; BT *rchild; BT; void Preorder(BT *T) / 先序遍历 if( T ) (或 T!=NULL ) coutdata ; Preorder( T-lc
120、hild ); 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个
121、元素顺序存储线性表的插. . . v . Preorder( T-rchild ); 8二叉树中序优先遍历 typedef struct BT datatype data; / 定义结点 BT *lchild; BT *rchild; BT; void Inorder(BT *T) / 中序遍历 if ( T ) 或 T！=NULL Inorder( T- lchild ); coutdata ; Inorder( T- rchild ); 9二叉树后序优先遍历 typedef struct BT datatype data; / 定义结点 BT *lchild; BT *rchild; BT
122、; void Postorder(BT *T) / 后序遍历 if ( T ) 或 T!=NULL Postorder( T-lchild ); Postorder( T-rchild ); coutdata ; 10二叉树按层次遍历 typedef struct BT datatype data; / 定义结点 BT *lchild; BT *rchild; BT; void Levelorder(BT *T) / 层次遍历 int i,j; BT *q100,*p; p=T; if ( p!=NULL ) i=1;qi=p;j=2; while (i!=j) p=qi; coutdata
123、; 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储
124、线性表的插. . . v . if ( p-lchild!=NULL ) qj= p-lchild ;j+; if (p-rchild!=NULL) qj= p-rchild ;j+; i+; 11以二叉链表为存储构造，试完成求二叉树深度的程序填空 typedef struct BT datatype data; / 定义结点 BT *lchild; BT *rchild; BT; int TreeDepth(BT *T) / 求树深度 int ldep,rdep; if( T=NULL ) return 0; else ldep= TreeDepth(T-lchild) ; rdep= Tr
125、eeDepth(T-rchild) ; if(ldeprdep) return ldep+1 ; else return rdep+1 ; 12以二叉链表为存储构造，试完成求二叉树中叶结点数的程序填空。 typedef struct BT datatype data; / 定义结点 BT *lchild; BT *rchild; BT; void Leafnum(BT *T) / 求叶结点数 if( T ) 或 T！=NULL if(T-lchild=NULL & T-rchild=NULL) count+ ; / count 初值为 0 Leafnum( T-lchild ); Leafnu
126、m( T-rchild ); 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开
127、场查找任何一个元素顺序存储线性表的插. . . v . 13设表的长度为 L，试填空完成直接插入排序程序。 void insertsort(int R ) / 按递增序对 R1 R n 进展直接插入排序 int i, j; for ( i=2; i = L ; i+ ) R 0 =R i ; / 设定 R0为监视哨 j= i-1 ； while (R 0 R j ) Rj+1=Rj ; j- - ; R j+1 = R0 ; / 插入第 i个记录 14直接选择排序 void selectsort ( ) / 按递增序对 R1 Rn 进展直接选择排序 int i, j, k ; for (i=1
128、; i= n ; i+) k=i ; for (j= i+1 ; j=n; j+) / 选择选择关键字最小的记录 if ( R j lchild); Exchange(T-rlchild); 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地
129、将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . if ( T-lchild | T-rchild ) p= T-lchild ; T-lchild= T-rchild ; T-lchild= p ; 六按题目要求，写出运行以下程序的结果 1 An为 int 类型的数组，An=1，45，16，28，3，80，36，18，77，66，写出运行以下算法后的输出结果。 void findmax ( An ) int max, i; m
130、ax=A 0 ; i= 1 ; while ( i max ) max= Ai ; i + ; coutmax ; 答： 80 2 写出运行以下程序段的输出结果栈的元素类型为 char 。 void main() Stack S; Char x,y; InitStack(S); x= c ; y= k ; Push(S,x); Push(S, a ); Push(S,y); Pop(S,x); Push(S, t ); Push(S,x); Pop(S,x); Push(S, s ); while(!StackEmpty(S) Pop(S,y);couty; ; coutx; 答：stack
131、3 写出运行以下程序段的输出结果队列中的元素类型为 char 。 void main() Queue Q; InitQueue (Q); 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而
132、链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . Char x= e ; y= c ; InQueue (Q, h ); InQueue (Q, r ); InQueue (Q, y); OutQueue (Q,x); InQueue (Q,x); OutQueue (Q,x); InQueue (Q, a ); while(!QueueEmpty(Q) OutQueue (Q,y);couty; ; coutlchild ); Nodenum( T-rchild ); 解：总结点
133、数或“结点总数，或“结点数 6二叉树的构造如下图，试写出执行以下算法后的输出结果： 。 用大写的英文字母表示， 字母之间不要任何间隔符号， 最后一个字母后面也不要间隔符号 typedef struct BT 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的
134、但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . datatype data; BT *lchild; BT *rchild; BT; void Preorder(BT *T) if (T!=NULL) coutdata; Preorder(T-lchild); Preorder(T-rchild); 解：ABCEDFG 先序遍历 7二叉树的构造如下图，试写出执行以下算法后的输出结果： 。 用大写的英文字母表示，
135、 字母之间不要任何间隔符号， 最后一个字母后面也不要间隔符号 typedef struct BT datatype data; BT *lchild; BT *rchild; BT; void Inorder(BT *T) if (T!=NULL) Inorder(T-lchild); coutdata; Inorder(T-rchild); 解： CEBAFDG 中序遍历 8二叉树的构造如下图，试写出执行以下算法后的输出结果： 。 用大写的英文字母表示， 字母之间不要任何间隔符号， 最后一个字母后面也不要间隔符号 typedef struct BT datatype data; BT *lc
136、hild; BT *rchild; BT; void Postorder(BT *T) if (T!=NULL Postorder(T-lchild); Postorder(T-rchild); coutdata; 解： ECBFGDA 后序遍历 C F BA D G E C F BA D G E C F BA D G E 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法
137、和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 9二叉树的构造如下图，试写出执行以下算法后的输出结果： 。 用大写的英文字母表示， 字母之间不要任何间隔符号， 最后一个字母后面也不要间隔符号 typedef struct BT datatype data; / 定义结点 BT *lchild;
138、BT *rchild; BT; void Levelorder(BT *T) int i,j; BT *q100,*p; p=T; if (p!=NULL) i=1;qi=p;j=2; while (i!=j) p=qi; coutdata ; if (p-lchild!=NULL) qj=p-lchild; j+; if (p-rchild!=NULL) qj=p-rchild; j+; i+; 解：ABDCFGE 层次遍历 10二叉树的构造如下图，试写出执行以下算法后的输出结果： 。 typedef struct BT datatype data; / 定义结点 BT *lchild; B
139、T *rchild; BT; int BTD(BT *T) int ldep,rdep; if(T=NULL) return 0; else ldep= BTD (T-lchild) ; rdep= BTD (T-rchild) ; if(ldeprdep) return ldep+1; else return rdep+1; C F BA D G E C F BA D G E 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类
140、数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 解：4 求二叉树深度 11二叉树的构造如下图，试写出执行以下算法后的输出结果： 。 typedef struct BT datatype data; / 定义结点 BT *lchild; BT
141、 *rchild; BT; void Leafnum(BT *T) if(T!=NULL if(T-lchild=NULL & T-rchild=NULL) count+; / count为全局变量，且初值为 0 Leafnum(T-lchild); Leafnum(T-rchild); 解：3 求叶结点数 12读以下算法，并答复以下问题： 1采用算法进展排序. 2算法中 R0的作用是什么. void insertsort(int R ) int i, j; for ( i=2; i=n; i+ ) R 0 =R i ; j=i-1; while (R 0 high) return 0; /
142、查找不到时返回 0 mid= (low+high)/2; if (ST.elemmid.key= =key) return mid; else if (ST.elemmid.keykey) return BS(ST, key, low, mid-1); else return BS(ST, key, mid+1, high); 解：3 二分查找 14如以下图所示的二叉树，其存储构造为二叉链表。其中 lchild，rchild分别为指向左右孩子的指针，data 为数据域，试答复以下问题： 1对以下二叉树，执行算法 Preorder()，试指出其输出结果是： ； 用大写的英文字母表示，字母之间不要
143、任何间隔符号，最后一个字母后面也不要间隔符号 2设二叉树共有 n 个结点，试分析算法 Preorder()的时间复杂度是： 。 解： （1） A B C E D F G （2） On或 O(n) 15如以下图所示的二叉树，其存储构造为二叉链表。其中lchild ，rchild分别为指向左右孩子的指针，data为数据域， 试答复以下问题： 1对以下二叉树，执行算法 traversal()，试指出其输出结果； 用大写的英文字母表示， 字母之间不要任何间隔符号， 最后一个字母后面也不要间隔符号 2对 n 个结点的二叉树，试写出算法 traversal()的时间复杂度。 二叉树的二叉链表描述如下： t
144、ypedef struct BT datatype data; BT *lchild; BT *rchild; BT; C算法如下： void traversal(BT *T) if (T!=NULL) coutdata; traversal(T-lchild); coutdata ; traversal(T-rchild); 二叉树的二叉链表描述如下： typedef struct BT datatype data; BT *lchild; BT *rchild; BT; C算法如下： void Preorder(BT *T) if (T=NULL) return; coutdata; Pr
145、eorder(T-lchild); Preorder(T-rchild); C F BA D G E C F BA D G 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展
146、随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 答： 1ABCCEEBADFFDGG 先根再左再根再右 2时间复杂度为 O(n) * 每个结点都被打印两次，其规律是：但凡有左子树的结点，必间隔左子树的全部结点后再重复出现；如 A，B，D 等结点。反之马上就会重复出现。如 C，E，F，G 等结点。 七程序设计题 1一个带头指针的单链表，写出在值为 X 的结点之后插入 m 个结点的算法。 void insertm ( lklist head; int m ) p=head-next; while
147、( p!=NULL ) & ( p-data!=x ) p=p-next; q=p-next; for ( i=0; im; i + ) s=new ( node ); cindata=a; p-next=s; p=s; p-next=q; 2. 在线性链表的第 i 个位置，插入值为 x 的结点，试写出该算法。 typedef struct linknode char data; struct linknode *next; node; node *head; int n=0; / 线性表长度 void InsList(int i,char x) / 插入结点函数 node *s,*p; in
148、t j; s=new node; 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结
149、点开场查找任何一个元素顺序存储线性表的插. . . v . n+; s-data=x; if(i=0) s-next=head;head=s; else p=head;j=1; while (p!=NULL & jnext; if(p!=NULL) s-next=p-next; p-next=s; else coutnext!=head1) p=p-next; q=head2; while (q-next!=head2) q=q-next; p-next=head2; q-next=head1; return (head1); 4链栈的存储构造和栈顶指针定义如下： *define MAXLEN
150、 100 typedef struct stacknode / 定义栈的存储构造 int data; struct stacknode *next; stacknode; typedef struct stacknode *top; / 定义栈顶的指针 linkstack; 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的
151、顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 试写出把十进数转换为二进制数的程序。 解： void Conversion(int n) / 栈的应用：二十进制转换 linkstack s; int x; s.top=NULL; / 置栈空 do x=n%2; / 取余数 n=n/2; / 取新的商 stacknode *p=new stack
152、node ; / 申请新结点 p-next=s.top ; / 修改栈顶指针 s.top=p; s.top-data=x ; / 余数入栈 while (n); cout 转换后的二进制数值为：; while (s.top) / 出栈处理 coutdata ; stacknode *p=s.top; s.top= s.top-next ; delete p ; / 出栈一个余数，收回一个结 5. 设计一个算法，要求判别一个算术表达式存在字符数组 a 中的圆括号配对是否正确. 允许使用 InitStack (s)，产生一个堆栈 S 来帮助判断 解： int correct (char a ) s
153、tack s ; InitStack (s); / 调用初始化栈函数 for (i=0; i strlen(a);i+) if (ai= =() Push (s,(); else if (ai= =) if StackEmpty (s) return 0; / 假设栈空返回 0；否那么出栈 else Pop (s); if (StackEmpty (s) ) cout “ 配对正确！; /假设栈空，说明配对正确 else coutlchild); InQueue(Q,p-rchild); / 不管孩子是否为空，都入队列 return 1; 分析：该问题可以通过层次遍历的方法来解决，不管当前结点
154、是否有左右孩子都入队列。这样当树为完全二叉树时，遍历时得到的是一个连续的不包含空指针的序列。反之，那么序列中会含有空指针。 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展
155、随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . 8 试写一个判别给定二叉树是否为二叉排序树的算法， 设此二叉树以二叉链表作存储构造。且树中结点的关键字均不同。 解： bool BisortTree(BiTree T, BiTree &PRE) / PRE 为指向当前访问结点的前驱的指针。 int last=0, flag=1; / last 是全局变量，用来记录前驱结点值，只要每个结点都比前趋大就行。 int IsBSTree (Bitree T) / 判断二叉树 T 是否二叉排序树，是那么返
156、回 1，否那么返回 0 if (T-lchild & flag) IsBSTree(T-lchild); if (T-datadata; if (T-rchild & flag) IsBSTree (T-rchild); return flag; 9从键盘输入假设干个整数，以回车为间隔，以-1为完毕符号，建立一个顺序存储的线性表，然后按提示输入一个待查找的数进展查找。假设找到，那么显示找到的数据在线性表中的位置；否那么显示“找不到。 void SeqSearch() int an,i,x,y; cout 建立整数的顺序表(以回车为间隔，以-1完毕)：; for (i=1;iai; if (ai
157、=-1) y=i; break; coutx; i=y-1; while (i=0 & ai!=x) i-; if (i=0) cout 没有找到; else cout 已找到，在第i 个位置上; 10. 对有序表 R0至 Rn-1 进展二分查找，查找成功时返回记录在表中的位置；查找失败时显示： “没有找到！，试编写此程序。 void BinSearch() int RMAXLEN,i,low,high,mid,n,x; char ch; 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据
158、的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . cout x ; low=0; high= n-1 ; while (lowx) high=mid-1; else if (Rmi
159、dhigh ) cout 没有找到！; if (Rmidx) mid+ ; cout 可将此数插入到 mid+1 的位置上。; else cout 要找的数据 x 在第 mid+1=i+1;j-) / 由底向上 if (rj.keyrj-1.key) b=1; t=rj; rj=rj-1; rj-1=t; for (j=i+1;jrj+1.key) b=1; 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据
160、的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . t=rj; rj=rj+1; rj+1=t; i+; 12以单链表为存储构造，写一个直接选择排序算法。 解：void selectsort (pointer h) pointer p,q,r,s,t; t=NUL
161、L; while(h) p=h; q=NULL; s=h; r=NULL; while (p) if (p-keykey) s=p; p=q; if (s= =h) h=h-link; else h=s; s-link=t; t=s; h=t; 13以单链表作为存储构造实现直接插入排序算法。 解：void InsertList (List head) Lnode *p, * pprev,q,*qprev, *current; if (!head) return; pprev=head; p=head-next; while(p) q=head; qprev=NULL; while (q-key
162、key) / 查找插入位置 qprev=q; q=q-next; if(q= =p) / p 最大，无须插入 pprev=p; p=p-next; else current=p; p=p-next; pprev-next=p; current-next=q; 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结
163、点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插. . . v . if (q= =head) / 插在表头 head=current; else / 插在中间某个位置上 qprev-next=current; 14. 个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体数据元素是数据的最小单位数据项是数据的根本单位数据的逻辑构造和数据的存储构造是一样的数据的逻辑构造是各数据元素之间的逻辑关系是用户按使和非线性构造两类数据的存储构造是数据的逻辑构造的存储映像算法是对解题方法和步骤的描述第章链表的物理存储构造具有同链表一样的顺序链表的每个结点都恰好包含一个指针域线性表中的元素可以是各种各样的但同一线性表动地将后续的各个单元向前移动顺序表构造适宜于进展顺序存取而链表适宜于进展随机存取数组元素的存储位置是下标的线性函数在单链表中元素的存储位置用指针联系所以可以从头结点开场查找任何一个元素顺序存储线性表的插
