2021年数据结构课后习题及答案.docx

精品word 可编辑资料 - - - - - - - - - - - - -填空题（10 * 1 = 10）一.概念题2.2 .当对一个线性表常常进行的为插入和删除操作时，采纳链式储备结构为宜；2.3 .当对一个线性表常常进行的为存取操作，而很少进行插入和删除操作时，最好采纳次序储备结构；2.6.带头结点的单链表L 中只有一个元素结点的条件为L->Next->Next=Null；3.6.循环队列的引入，目的为为了克服假溢出；4.2.长度为 0 的字符串称为空串；4.5.组成串的数据元素只能为字符；4.8.设 T 和 P 为两个给定的串，在T 中查找等于P 的子串的过程称为模式匹配，又称 P 为模式；7.2.为了实现图的广度优先搜寻，除一个标志数组标志已拜访的图的结点外，仍需要队列存放被拜访的结点实现遍历；5.7.广义表的深度为广义表中括号的重数7.8 .有向图 G 可拓扑排序的判别条件为有无回路；7.9 .如要求一个稠密图的最小生成树，最好用Prim 算法求解；8.8. 直接定址法法构造的哈希函数确定不会发生冲突；9.2.排序算法所花费的时间，通常用在数据的比较和交换两大操作；1.1 .通常从正确性可读性健壮性时空效率等几个方面评判算法的（包括程序）的质量；1.2 .对于给定的n 元素，可以构造出的规律结构有集合关系线性关系树形关系图状关系四种；1.3 .储备结构主要有次序储备链式储备索引储备散列储备四种；1.4 .抽象数据类型的定义仅取决于它的一组规律特性，而与储备结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用；1.5 .一个算法具有五大特性：有穷性确定性可行性，有零个或多个输入有一个或多个输入；2.8 .在双向链表结构中，如要求在p 指针所指的结点之前插入指针为s 所指的结点，就需执行以下语句： s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;；2.9 .在单链表中设置头结点的作用为不管单链表为否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情形下统一；3.1 .队列为限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原就；3.2 .栈为限定尽在表位进行插入或删除操作的线性表；3.5.在链式队列中，判定只有一个结点的条件为(Q->rear=Q->front)&&(Q->rear.=NULL)；3.7 .已知链队列的头尾指针分别为f 和 r，就将 x 入队的操作序列为node*p=(node *)malloc(node);p->next=x; p->next=NULL;if(r)r->next=p;r=p;elser=p;f=p; ；3.8 .循环队列的满与空的条件为(rear+1)%MAXSIZE=fornt和(front=-1&&rear+1=MAXSIZE)；4.3.串为一种特殊的线性表，其特殊性表现在数据元素都为由字符组成；4.7.字符串储备密度为串值所占储备位和实际安排位的比值，在字符串的链式储备结构中其结点大小为可变的；5.3 .所谓稀疏矩阵指的为矩阵中非零元素远远小于元素总数，就称该矩阵为矩阵中非零元素远远小于元素总数，就称该矩阵为稀疏矩阵；5.4 .一维数组的规律结构为线性结构，储备结构为次序储备结构；对二维或多维数组，分别按行优先和列优先两种不同的储备方式；7.4.在有向图的邻接矩阵表示中，运算第i 个顶点入度的方法为求邻接矩阵中第i 列非 0 元素的个数；7.10.AOV 网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示大事，边表示活动；9.1.按排序过程中依据不同原就对内部排序方法进行分类，主要有挑选排序交换排序插入排序归并排序等4 类；9.3 .在堆排序.快速排序和归并排序中如只从排序结果的稳固性考虑，就应挑选归并排序方法；如只从平均情形下排序最快考虑，就应挑选快速排序方法；如只从最坏情形下排序最快且要节约类存考虑，就应挑选堆排序方法；9.4 .直接插入排序用监视哨的作用为存当前要的插入记录，可又省去查找插入位置时对为否出界的判定；9.6.设表中元素的初始状态为按键值递增的，就直接插入排序最省时间，快速排序最费时间；4.9.以下程序判定字符串s 为否对称，对称就返回1，否就返回0；如.(“abba”)返回 1， .（”abab”）返回 0. Int f (char*s)Int i=0、j=0;while(sj) j+;/* 求串长 */第 1 页，共 8 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -for(j-;i<j && si=sj;i+、j+); return( i>=j );二.结论题2.7.在具有 n 个结点有序单链表中插入一个新结点并仍旧有序的时间复杂度为O(n) ；2.10.对于一个具有n 个结点的单链表，在已知的结点*p 后插入一个新结点的时间复杂度为O(1) ，在给定值为x 的结点后插入一个新结点的时间复杂度为O(n) ；4.1.设正文产长度为n ，模式串长度为m，就简洁模式匹配算法的时间复杂度为O(m*n)；9.5.对 n 个记录进行快速排序时，递归调用而为用的栈所能达到的最大深度为O(n) ，平均深度为O(log 2 n) ；7.1.克鲁斯卡尔算法的时间复杂度为O(eloge) ，它对稀疏图较为合适；6.3.在一棵二叉树中，度为0 的结点的个数为N0，度为 2 的结点个数为N2，就有 N0= N 2 +1 ；6.8 深度为 k 的完全二叉树至少有2 k-1 个结点，至多有2 k-1个结点；7.3.具有 n 个结点 e 条边的有向图和无向图用邻接表表示，就邻接表的边结点个数分别为e 和 2e 条；7.5.如 n 个顶点的连通图为一个环，就它有n 棵生成树；7.6.n 个顶点的连通图用连接矩阵表示时，该矩阵至少有2(n-1) 个非零元素；7.7.有 n 个顶点的有向图，至少需要n 条弧才能保证为连通的；9.7.归并排序除了在递归为现实所用的log 2n 个栈空间外，仍用n 个帮助空间；2.1.对于采纳次序储备结构的线性表，当随机插入一个数据元素时，平均移动表中n/2 元素；删除一个数据元素时，平均移动表中 (n-1)/2 元素；2.4 .在一个长度为n 的次序储备结构的线性表中，向第i 个元素（ 1 i n+1)之前插入一个新元素时，需向后边移动 n-i+1 个元素；2.5 .从长度为n 的采纳次序储备结构的线性表中删除第i 个元素（ 1 i n） 、需向前移动n-1 个元素；3.4.当两个栈共享一储备区时，储备区用一维数组stack（ 1， n）表示，两栈顶指针为top【1】与 top【2】，就当栈1空时； top【1】为 0，栈 2 空时 top 【2】为 n+1 ，栈满的条件为top1+1=top2；8.1.次序查找n 个元素的次序表，如查找胜利，就比较关键字的次数最多为n 次；当使用监视哨时，如查找失败，就比较关键字的次数为n+1 ；6.5.设一颗完全二叉树叶子结点数为k，最终一层结点数为偶数时，就该二叉树的高度为log 22k1+1，最终一层结点数为奇数时，就该二叉树的高度为log 22k+1；9.8.对 n 个记录建立一个堆的方法为：第一将要排序的全部记录分到一棵二叉树的各个结点中，然后从i= n / 2 的结点ki，逐步把以kn/2、kn/ 2-1kn/ 2-2、为根的子树排成堆，直到以k1 根的树排成堆，就完成了初次建堆的过程；三.运算题4.4.StrIndex( “MY STUDENT”、”STU”)=4 ；5.5.求以下广义表的运算结果：Get TailGetHeada、b、c、d= （ b）；6.7.已知二叉树先序为，中序为，就后序肯定为DGEBFCA ；5.8.广义表 a、a、b、d、e、i、j、k 的长度为5，深度为 3 ；6.9.具有 10 个叶子的哈夫曼树，其最大高度为9 ，最小高度为5 ；6.1.已知二叉树有50 个叶子结点，就该二叉树的总结点数至少为99； 6.10.设 F 为一个森林，B 为由 F 转换得到的二叉树，F 中有 n 个非终端节点，就B 中右指针域为空的结点有n+1 个；3.10. 表达式 23+（ 12*13-2 ） /4+34*5/7 ） +108/9 的后缀表达式为23 12 3*2-4/34 5*7/+108 9/+；3.3. 用 s 表示入栈操作；X 表示出栈操作，如元素入栈的次序为1、2、3、4、 为了得到1、3、4、2 出栈次序，相应的s 和 x 的操作串为SXSSXSXX ；5.6.广义表 A=a、b、c、d、e、 取出 A 中的原子e 的操作为： GetT ail(GetTail(GetT ail(GetHead(A)；9.10. 一组记录的键值为12、38、35、25、74、50、63、90 ，按二路归并排序方法对该序列进行一趟归并后的结果为12、38、25、35、50、74、63、90；3.9. 一个栈的输出序列为，1， 2， 3， 4，5，就不同的输出序列有42 种4.6.设串 S 的长度为4，就 S 的子串个数最多为10 ；6.6.有 5 种不同形状的二叉树可以按中序遍历得到相同的abc 序列；9.9.如用冒泡排序对关键字序列50、45、35、19、9、3进行从小到大的排序，所需进行的关键字比较总次数为15 ；5.1.二维数组A68 采纳行序为主方式储备，每个元素占4 个储存单元，已知A 的起始储存地址基地址 为 1000 ，就A23 的地址为1076 ；第 2 页，共 8 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -6.4.叶子权值（ 5、6、17、8、19）所构造的哈夫曼树带权路径长度为121 ；8.2.在次序表（ 8、11、15、19、25、26、30、33、42、48、50 ）中，用折半法查找关键字20，需要的关键字比较次数为4；8.3.对于具有144 个记录的文件，如采纳分块查找法，且每块长度为8，就平均查找长度为8.25 或 14 ；5.2.设数组 A910 ，数组中任一元素均占内存48 个二进制位，从首地址2000 开头连续存放在主内存里，主内存字长为 16 位，那么：1 存放该数组至少需要的单元数为270 ；2 存放数组的第8 列的全部元素至少需要的单位数为27；3 数组按列储备时，元素A58 的起始地址为2231 ；挑选题 （ 15 * 1= 15）一.表达类1.1 .依据数据元素之间关系的不同性，以下说明错误选项（）；A 集合中任何两个结点之间都有规律关系但组织形式松散B 线性结构中结点形成1 对 1 的关系C 树形结构具有分支.层次特性，其形状有点像自然界中的树D 图状结构中的各个结点按规律关系相互缠绕，任何两个结点都可以邻接1.2 .关于规律结构，以下说法错误选项（）；A 规律结构为独立于运算机的B 运算的定义与规律结构无关C 同一规律结构可以采纳不同的储备结构D 一些表面上很不相同的数据可以有相同的规律结构E 规律结构为数据组织的某种“本质性”的东西1.3 .下面关于算法的说法正确选项（）；A 算法的时间效率取决于算法所花费的CPU 时间B 在算法设计中不能用牺牲空间代价来换取好的时间效率C 算法必需具有有穷性.确定性等5 个特性D 通常用时空效率来衡量算法的优劣1.4 .下面关于算法说法错误选项（）；A 运算机程序肯定为算法B 算法只能用运算机高级语言来描述C 算法的可行性为指指令不能有二义性D 以上几个都为错误的1.6.以下说法正确选项（）；A 数据元素为数据的最小单位B 数据项为数据的基本单位C 原子类型不行再分解D 数据项只能为原子类型2.1.线性表为（）A.一个有限序列，可以为空B.一个有限序列，不能为空C.一个无限序列，可以为空D.一个无限序列，不能为空2.3 .线性表采纳链式储备时，其各元素储备地址（）；A.必需为连续的B.部分地址必需为连续的C.肯定为不连续的D.连续与否均可以2.4 .用链表表示线性表的优点为（）；A.便于随机存取B.花费的储备空间较次序储备少C.便于插入和删除D.数据元素的物理次序与规律次序相同2.5.（）插入.删除速度快，但不能随机存取；A.链接表B.次序表C.次序有序表D.上述三项无法比较2.6 .如期望从链表中快速确定一个结点的前驱，就链表最好采纳（）方式；A.单链表B.循环单链表C.双向链表D.任意2.7 .下面关于线性表的表达错误选项（）；A.线性表采纳次序储备，必需占用一片地址连续的单元B.线性表采纳次序储备，便于进行插入和删除操作C.线性表采纳链式储备，不必占用一片地址连续的单元D.线性表采纳链式储备，便于进行插入和删除操作2.9.如某线性表中最常用的操作的操作为在最终一个元素之后插入一个元素和删除第一个元素，就采纳（）储备方法最节约运算时间；A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表3.1.栈和队列的共同点为（）；A.都为先进先出B.都为先进后出C.只答应在端点处插入和删除元素D.没有共同点3.4.递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构；A.队列B.多维数组C.栈D.线性表3.6 .用链式储备的队列，在进行删除运算时（）；A.仅修改头指针B.仅修改尾指针C.头.尾指针都要修改D.头.尾指针可能都要修改第 3 页，共 8 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -3.7 .栈应用在（）；A.递归调用B.子程序调用C.表达式求值D.A、B、C4.1 .如下陈述中正确的事（）A.串为一种特殊的线性表B.串的长度必需大于零C.串中元素只能为字母D.空串就为空白串4.2 .设有两个串p 和 q，其中 q 为 p 的子串，求q 在 p 中首次显现的位置的算法称为（）A.求子串B.联接C.匹配D.求串长4.4.串为（）A.不少于一个字母的序列B.任意个字母的序列C.串中所含不同字符的个数D.串中所含非空格字符的个数4.5.串的长度为指（）A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数5.4.对矩阵压缩储存为为了（）A便利压缩B.节约空间C.便利储备D.提高运算速度6.1.假如 T2 为由树 T 转换而来的二叉树，那么对T 中结点的后根遍历就为对T2 中结点的（）遍历；A先序B 中序C 后序D 层次序6.4.二叉树在线索后，仍不能有效求解的问题为（）；A 先序线索二叉树中求先序后继B 中序线索二叉树求中序后继C 中序线索二叉树中求中序前驱D 后序线索二叉树中求后序后继6.8 某二叉树的先序遍历序列和后序遍历序列正好相反，就此二叉树肯定为（）；A 空或只有一个结点B 完全二叉树C 单枝树D 高度等于结点数6.9 .在二叉树结点的先序序列，中序序列和后序序列中，全部叶子结点的先后次序（）；A 都不相同B 完全相同C 先序和中序相同而后序不同D 中序和后序相同而与先序不同7.5.图的广度优先搜寻类似于树的（）遍历；A.先序B.中序C.后序D.层次7.8 .下面（）方法可以判定出一个有向图为否有环（回路）；A.深度优先遍历B.拓扑排序C.求最短路径D.求关键路径7.9 .在有向图G 的拓扑序列中，如顶点Vi 在顶点 Vj 之前，就以下情形不行能显现的为（）；A.G 中有弧 <Vi、Vj>B.G 中有一条从Vi 到 Vj 的路径C. G中没有弧 <Vi、Vj>D.G 中有一条从Vj 到 Vi 的路径7.10 .以下关于AOE 网的表达中，不正确选项（）； A.关键活动不按期完成就会影响整个工程的完成时间 B.任何一个关键活动提前完成，那么整个工程将会提前完成 C.全部的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动提前完成，整个工程将会提前完成8.3.当采纳分块查找时，数据的组织方式为（）A.数据分块如干块，每块内数据有序 B.数据分成如干块，每块内数据不必有序，但块间必需有序，每块内最大（或最小）的数据组成索引块 C.数据分成如干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D.数据分成如干块，没块（除最终一块外）中数据个数需相同8.5.下面关于折半查找的表达正确选项（）；A.表必需有序，表可以次序方式储备，也可以链表方式储备 B.表必需有序且表中数据必需为整型，实型或字符型 C.表必需有序，而且只能从小到大排序D.表必需有序，且表只能一次序方式储备8.11 .下面关于哈希查找的说法正确选项（）A.哈希函数构造的越复杂越好，由于这样随机性好.冲突小B.除留余数法为全部哈希函数中最好的C.不存在特殊好与坏的哈希函数，要视情形而定 D.如需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简洁地将该元素删去即可8.12 .将 10 个元素散列到100000 个单元的哈希表中，就（）产生冲突；A.肯定会B.肯定不会C.仍可能会9.1.以下排序算法中，其中（）为稳固的；A.堆排序和冒泡排序B.快速排序和堆排序C.简洁挑选排序和归并排序D.归并排序和冒泡排序第 4 页，共 8 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -9.3 .以下时间复杂度不为O（ nlog2n ）的排序方法为（）；A.堆排序B.直接插入排序C.二路归并排序D.快速排序9.4 .如需在 O（ nlog2n ）的时间内完成对数组的排序，且要求排序为稳固的，就可以挑选的排序方法为（）；A.快速排序B.堆排序C.直接插入排序D.归并排序9.7 .在待排序的元素序列基本有序的前提下，效率最高的排序方法为（）；A直接插入排序B.快速排序C.简洁挑选排序D.归并排序9.8 .就排序算法所用的帮助空间而言，堆排序.快速排序.归并排序的关系为（）；A.堆排序 <快速排序 <归并排序B.堆排序 <归并排序 <快速排序C.堆排序 >归并排序 >快速排序D.堆排序 >快速排序 >归并排序9.9 .一个序列有10 000 个元素，如只想得到其中前10 个最小的元素，最好采纳（）方法；A.二路归并排序B.直接挑选排序C .Shell 排序D .堆排序9.10 .设有字符序列Q、H、C、Y、P、A、M、S、R、D、F、X， 新序列 D、H、C、F、P、A、M、Q、R、S、Y、X为以下（）算法一趟排序的结果；A.冒泡排序B.初始步长为4 的 Shell 排序C.二路归并排序D. 快速排序二.数字类1.5.程序段for(i=n-1;i>=0;i-) for(j=1;j<=n;j+)if Aj>Aj+1Aj 与 Aj+1 互换;其中 n 为正整数，就最终一行的语句频度在最坏情形下为（）；A.O(n)B.O(n2)C.O(n3)D.O(nlog2n)2.2.从一个具有n 个结点的单链表中查找值为x 结点，在查找胜利情形下，需要平均比较（）个结点；A.nB.n/2C.（ n-1） /2D.（n+1 ）/22.8 .带头结点的单链表head 为空的判定条件为（）；A. head=NULLB.head >next=NULLC.head >next=headD.head.=NULL2.10.在循环双链表的p 所指结点之后插入s 所指结点的操作为（）； A.p >next=s;s >prior=p;p >next >prior=s;s >next=p >next; B.p >next=s;p >next>prior=s;s >prior=p;s >next=p >next; C.s >prior=p;s >next=p >next;p >next=s;p >next >prior=s; D.s >prior=p;s >next=p >next;p >next >prior=s;p >next=s;3.2 .如一个栈的输入序列为1，2， 3， n ，输出序列的第一个元素为n、就第 i 个输出元素为（）；A.n-i-1B.n-iC.n-i+1D.不确定3.3 .设 a、b、c、d、e、f 以给定的次序进栈，如在进栈操作时，答应出栈操作，就下面得不到的序列为（）；A. f、e、d、c、b、aB.b、c、a、f、e、dC.d、c、e、f、b、aD.c、a、b、d、e、f3.5 .如一个栈以向量V1.n 储备，初始栈顶指针top 为 n+1，就下面x 入栈的正确操作为（）；A. top=top+1;Vtop=xB. Vtop=x;top=top+1C.top=top-1;Vtop=xD.Vtop=x;top=top-13.8 .中级表达式A-(B+C/D)×E 的后缀形式为（）；A.AB-C+D/E ×B.ABC+D/E ×C.ABCD/E× +-D.ABCD/+E × -3.9 .假设以数组A【 m】存放循环队列的元素，其头尾指针分别为front 和 rear，就当前队列中的元素个数为（）A.(rear-front+m)%mB.rear-front+1C.（ front-rear+m ） %mD.（ rear-front ） %m3.10 .循环队列储备在数组A【0.m】中，就入队时队尾的操作为（）A.rear=rear+1B.rear=（ rear+1） %（ m-1） C.rear= （ rear+1） %mD.rear= （ rear+1） %（ m+1）3.11 .如元素a，b， c， d， e，f 依次进栈，答应进栈，退栈操作交替进行，单不答应连续三次进行进退栈工作，就不行能得到的出栈序列为（）A.dcebfaB.cbdaefC. dbcaefD.afedcb 3.12.某队列答应在其两端进行入队操作，但仅答应再一端进行出队操作，就不行能得到的次序为（）A.bacdeB.dbaceC. dbcaeD.ecbad3.13.假如栈s 和队列 q 的初始状态均为空，元素a， b， c， d，e， f， g 依次进入栈s，假如每个元素出栈立刻进入队列 q，且 7 个元素出队的次序为b， d ，c， f ，e， a， g，就栈 s 的容量至少为（）A.1B.2C. 3D.4第 5 页，共 8 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -4.3.串“ ababaaababaa”的 next 数组为（）A.012345678999B.012121111212C.011234223456D.0123012322344.6.如 s=”1234ab567abcdab0 ”、t=”ab”、r=”(”空串 )，串替换StrRep(s、t、r)的结果为（）A.”1234ab567abcdab0 ”B.”1234ab567abcd ”C.”1234567cd0 ”D.”1234 567 cd 0 ”4.7.S 为一个长度为n 的字符串， 其中字符各不相同， 就 S 中的互逆的非平凡子串 （非空且不同于S 本身）的个数（）A.2n-1B.n2C.(n2/2)+(n/ 2)D.(n2/2)+(n/ 2)-14.8.如串 S=”English”、其中串的个数为（） A.9B.16C.36D.285.1 .数组 A56 的每个元素占5 个字节，将其按列优先次序储备在起始地址为1000 的内存单元中，就元素A45 的地址为（ 1145）5.2 .如对 n 阶对称矩阵A 以行序为主序方式将其下三角的元素（包括主对角线上全部元素）依次存放于一维数组 B1.(n（ n+1） )/2 中， aoo 存放于数组B1 中，就在B 中确认定 aij （i<j）的位置k 的关系为（） A i×（ i+1） /2+jB.j×（ j+1） /2+IC.i×（ j-1）D.j× m+i-15.3 .设二维数组A1.m ， 1.n 按行储备在数组B1.m × n 中，就二维数组元素Aij 在一维数组B 中的下标为（）A.（ i-1）× n+jB.(i-1)× n+j-1C.i× (j-1)D.j× m+i-15.5 .设广义表L=（ a， b， c） ，就 L 的长度和深度分别为（）A 1 和 1B.1 和 3C.1 和 2D.2 和 35.6 .有一个 100× 90 的稀疏矩阵，非0 元素有 10 个，设每个整型数占两个字节，就用三元组表示该矩阵时，所需的字节数为（）A.60B.66C.18000D.335.7 .已知广义表LS=（ a， b， c），（ d， e， f） ，运用 Get Head 和 Get Tail 函数取出LS中原子 e 的运算为（）A.GteHead（ Get Tail（ LS）B. Get Tail（ GteHead（ LS）C. GteHead（Get Tail（ GteHead（ Get Tail（ LS）D. GteHead（ Get Tail（ Get Tail（GteHead（ LS） ）5.8 .已知广义表： A=(a，b)，B=（ A、A）、C=(a，（ b，A），B)、求以下运算的结果：Get Tail（GteHead（ Get Tail（ C） ）=（）A.(a)B.AC.aD.(b)E.bF.(A)6.2 .设树 T 的度为 4 ，其中度为1 .2. 3.4 的结点个数分别为4.2.1.1 就 T 中的叶子数位（）C7D8C14D16A5B66.3 .由 4 个结点可以构造出（）种不同的二叉树；A10B126.5 .如一棵二叉树具有10 个度为 2 的结点， 5 个度为 1 的结点，就度为0 的结点个数为（）A9B11C15D不确定6.6 设高度为h 的二叉树只有度为0 和 2 的结点就此类二叉树中所包含的结点数至少为（）个；A2hB2h-1C2h+1Dh+16.7 设给定权值的叶子总数有n 个，其哈夫曼树的结点总数为（）；A 不确定B 2nC 2n+1D 2n-16.10.依据使用频率，为5 个字符设计的哈夫曼编码不行能为（）；A 111、110、10、01、00B 000、001、010、011、1C 100、11、10、1、0D 001、000、01、11、107.1 .无向图 G=（V、E）V=a、b、c、d、e、E=(a、b)(a、e)、（ a、c)、(b、e)、(c、f)、(f、d)、(e、d)、 其中对该图进行深度优先遍历，得到的顶点序列正确选项（）Aa、b、e、c、d、fBa、c、f、e、b、dCa、e、b、c、f、dDa、e、d、f、c、b7.2 .一个 n 个顶点的连通无向图，其边的个数至少为（）C.n+1Prim 算法的时间复杂度为（）D.nlog2nC.O(n2)D.O(n3)A.n-1B.n7.3 .在图采纳邻接表储备时，求最小生成树的A.O(n)B.O(n+e)7.4.G 为一个非连通的无向组，共有28 条边，就该图至少有（）个顶点；A. 6B.7C.8D.97.6.一个有 n 个顶点的无向图，最少有（）个连通重量，最多有（）个连通重量；A.0B.1C.n-1D.n7.7.在一个无向图中，全部顶点的度数之和等于全部边数（ 有顶点的出度之和的（）倍；）倍，在一个有向图中，全部顶点的入度之和等于所A.12B.2C.1D.4第 6 页，共 8 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -8.1 .如查找每个记录的概率均等，就在具有n 个记录的次序文件中采纳次序查找法查找一个记录，其平均查找长度ASL为（）A.（n-1） /2B.n/2C.(n+1)/2D.n8.2 .具有 12 个关键字的有序表，折半查找的平均查找长度为（）A. 3.1B. 4C.2.5D. 58.10.假定有 k 个关键字互为同义词，如用线性探测法把这k 个关键字存入散列表中，至少要进行（）次探测；A.k-1 次B. k 次C.k+1 次D.k(k+1)/2 次9.2.如对 N 个元素进行快速排序，假如初始数据已经有序，就时间复杂度为（）；A.O（1）B.O（n ）C.O（ n2）D.O（ log2n）9.5 .一组记录的关键字问46、79、56、38、40、84 ，就利用快速排序方法，以第一个记录为轴值得到的一次划分结果为（）；A.38、40、46、56、79、84、B.40、38、46、79、56、84C.40、38、46、56、79、84D.40， 38， 46、84、56、799.6 .一组记录的关键字为45、80 ，55， 40、42、85 ，就利用堆排序方法建立的初始堆为（）；A.80、45、50、40、42、85B.85、80、55、40、42、45C.85、80、55、45、42、40D.85、55、80、42、45、40判定题（15 * 1 = 15）一.正确（ 35 个）1.5.数据的物理结构为指数据在运算机内的实际储备形式；2.2 .次序储备的线性表可以按序号随机存取；2.3 .线性表采纳链式表储备时，储备空间可以为不连续的；2.7 .循环链表可以在尾部设置头指针；2.8 .为了便利插入和删除，可以使用双向链表存放数据；3.2 .栈为实现过程和函数调用所必需的结构.3.3 .两个栈共享一片连续内存空间时、为提高内存利用率、削减溢出的机会、应把两个栈的栈底分别设在这片内存空间的两端 .3.5.栈与队列为一种特殊的线性表3.7 .循环队列通常会铺张一个储备空间.3.8 .循环队列也存在空间溢出问题.3.9 .栈和队列的储备方式、既可以为次序方式、又可以为链式方式.3.10 .任何一个递归过程都可以转换成非递归过程.4.1.KMP 算法的特点为在模式匹配时指示主串的指针不会变小；4.3.nest 函数值序列的产生仅与模式串有关；4.6.串名的储备应先高就为按串名拜访串值的一种方法；4.8.在插入和删除操作中，链式串肯定比次序串便利；4.10.在串的次序储备中，通常将0 作为串的终止标记；5.2 .二维以上的数组其实为一种特殊的广义表；5.3 .稀疏矩阵压缩储备后，必会失去随机存取功能；5.5 .线性表可以看成为广义表的特例，假如广义表中的每个元素都为原子，就广义表便成为线性表；5.6 .一个广义表可以为其他广义表所共享；5.9 .广义表为由零或多个原子或子表所组成的有限序列，所以广义表可能为空表；5.10 .任何一个非空广义表，其表头可能为单个元素或广义表，其表尾必定为广义表；6.1.哈夫曼树的结点个数不行能为偶数；6.4 .哈夫曼编码为前缀编码；6.5 .非空的二叉树肯定满意：某结点如有左孩子，就其中序前驱肯定没有右孩子；6.7.由先序和后序遍历序列不能唯独确定一棵二叉树；6.9.一棵树的叶结点，在先序遍历和后序遍历下，皆以相同的相对位置显现；7.4.哈夫曼编码为前缀编码；7.6.必需把一般树转成二叉树后才能进行储备；7.10.在哈夫曼树中，权值相同的叶结点都在同一层上；8.10.装填因子为哈希表的一个重要参数，他反应哈希表的装满成度；9.2.在大根堆中，最大元素在根的位置；第 7 页，共 8 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -9.8 .只有在初始数据表为逆序时，直接插入排序所执行的比较次数最多；9.9 .简洁挑选排序算法的时间