《数据结构课后习题及答案.pdf》由会员分享,可在线阅读,更多相关《数据结构课后习题及答案.pdf(9页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、填空题(io*r=io*)一、概念题2.2.当对一个线性表经常进行的是插入和删除操作时,采用链式存储结构为宜。2.3.当对一个线性表经常进行的是存取操作,而很少进行插入和删除操作时,最好采用顺序存储结构。2.6.带头结点的单链表L中只有一个元素结点的条件是L-Next-Next=NulL3.6.循环队列的引入,目的是为了克服假溢出。4.2.长度为0的字符串称为空串。4.5.组成串的数据元素只能是字符。4.8.设T和P是两个给定的串,在T中寻找等于P的子串的过程称为模式匹配,又称P为模式。7.2.为了实现图的广度优先搜索,除一个标志数组标志已访问的图的结点外,还需要队列存放被访问的结点实现遍历。
2、5.7.广义表的深度是广义表中括号的重数7.8.有向图G可拓扑排序的判别条件是有无回路。7.9.若要求一个稠密图的最小生成树,最好用Prim算法求解。8.8.直接定址法法构造的哈希函数肯定不会发生冲突。9 2排序算法所花费的时间,通常用在数据的比较和交换两大操作。1.1.通常从正确性、可读性、健壮性、时空效率等几个方面评价算法的(包括程序)的质量。1.2.对于给定的n元素,可以构造出的逻辑结构有集合关系、线性关系树形关系、图状关系四种。1.3.存储结构主要有顺序存储、链式存储、索引存储、散列存储四种。1 4抽象数据类型的定义仅取决于它的组逻辑特性,而与存储结构无关,即不论其内部结构如何变化,只
3、要它的数学特性不变,都不影响其外部使用。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
4、.5.在链式队列中,判定只有一个结点的条件是(Q-rear=Q-front)&(Q-rear!=NULL)。3.7.已知链队歹ij的头尾指针分别是f和r,则降x入队的操作序列是node*p=(node*)malloc(node);p-next=x;p-next=NULL;if(r)r-next=p;r=p;else r=p;f=p;3.8.循环队列的满与空的条件是(rear+1)%MAXSIZE=fornt 和(front=-1&rear+1=MAXSIZE)。4.3.串是一种特殊的线性表,其特殊性表现在数据元素都是由字符组成。4.7.字符串存储密度是串值所占存储位和实际分配位的比值,在字符串
5、的链式存储结构中其结点大小是可变的。5 3所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数,则称该矩阵为矩阵中非零元素远远小于元素总数,则称该矩阵为稀疏矩阵。5.4一维数组的逻辑结构是线性结构,存储结构是顺序存储结构;对二维或多维数组,分别按行优先和列优先两种不同的存储方式。7.4.在有向图的邻接矩阵表示中,计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。7.10.AOV网中,结点表示活动,边表示活动之间的优先关系,AOE网中,结点表示事件,边表示活动。9.1.按排序过程中依据不同原则对内部排序方法进行分类,主要有选择排序、交换排序、插入排序归并排序等4类。9.3.在堆排序、快速排
6、序和归并排序中若只从排序结果的稳定性考虑,则应选择归并排序方法;若只从平均情况下排序最快考虑,则应选择快速排序方法;若只从最坏情况下排序最快且要节省类存考虑,则应选择堆排序方法。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+;/*求串长*/for(j-;i=j);)二、结论题2.
7、7.在具有n个结点有序单链表中插入一个新结点并仍然有序的时间复杂度为0(n)。2.10.对于一个具有n个结点的单链表,在已知的结点*p后插入一个新结点的时间复杂度为0(1),在给定值为x的结点后插入一个新结点的时间复杂度为O(n)。4.1.设正文产长度为n,模式串长度为m,则简单模式匹配算法的时间复杂度为O(m*n)。9.5.对n个记录进行快速排序时,递归调用而是用的栈所能达到的最大深度为O(n),平均深度为OQogzn)。7.1.克鲁斯卡尔算法的时间复杂度为O(eloge),它对稀疏图较为合适。6.3.在一棵二叉树中,度为。的结点的个数为No,度为2的结点个数为“,则有NO=N2+1。6.8
8、深度为k的完全二叉树至 少 有 个 结 点,至多有2勺1_个结点。7.3.具有n个结点e条边的有向图和无向图用邻接表表示,则邻接表的边结点个数分别为e和2 e条。7.5.若n个顶点的连通图是一个环,则它有n棵生成树。7.6.n个顶点的连通图用连接矩阵表示时,该矩阵至少有2(n-1)个非零元素。7.7.有n个顶点的有向图,至少需要n条弧才能保证是连通的。9.7.归并排序除了在递归是现实所用的logm个栈空间外,还用n个辅助空间。2.1.对于采用顺序存储结构的线性表,当随机插入一个数据元素时.,平均移动表中n/2元素;删除一个数据元素时,平均移动表中(n-1)/2元素。2.4.在一个长度为n的顺序
9、存储结构的线性表中,向第i个 元 素(lWiWn+1)之前插入一个新元素时,需向后边移动n-i+1个元素。2.5.从长度为n的采用顺序存储结构的线性表中删除第i个 元 素(lW W n),需向前移动n-1个元素。3.4.当两个栈共享一存储区时,存储区用一维数组stack(1,n)表示,两栈顶指针为to p【1】与to p【2】,则当栈1空时。top 1 为0,栈2空时top 2 为n+1,栈满的条件是top1+1=top2。8.1.顺序查找n个元素的顺序表,若查找成功,则比较关键字的次数最多为n次;当使用监视哨时,若查找失败,则比较关键字的次数为n+1。6.5.设一颗完全二叉树叶子结点数为k,
10、最后一层结点数为偶数时,则该二叉树的高度为UgkT)+l,最后一层结点数为奇数时,则该二叉树的高度为L噫(2k)+l。9.8.对n个记录建立一个堆的方法是:首先将要排序的所有记录分到一棵二叉树的各个结点中,然后从i=W2j的结点k i,逐渐把以kn,k n lk n仅-2,为根的子树排成堆,直到以k l根的树排成堆,就完成了初次建堆的过程。三、计算题4.4.Strlndex(MY STUDENT,STU)=4。5.5.求下列广义表的运算结果:GetTailGetHeada,b,c,d=(b)6.7.已知二叉树先序为A B D EG C F,中序为D B G E A C F,则后序一定是DGEB
11、FCA。5.8.广义表包/簿而见明的长度是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)+10的 的后缀表达式是 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.
12、广义表 A=a,b,c,d,e,取出 A 中的原子 e 的操作是:GetTail(GetTail(GetTail(GetHead(A)o9.10.一组记 录 的 键 值 为 12,38,35,25,74,50,63,90,按二路归并排序方法对该序列进行一趟归并后的结果是12,38,25,35,50,74,63,90。3.9.一个栈的输出序列是,1,2,3,4,5,则不同的输出序列有4 2种4.6.设串S的长度为4,则S的子串个数最多为10。6.6.有5种不同形态的二叉树可以按中序遍历得到相同的abc序列。9 9若用冒泡排序对关键字序列50,45,35,19,9,3进行从小到大的排序,所需进行的
13、关键字比较总次数是15。5.1.二维数组A采用行序为主方式存储,每个元素占4个储存单元,已知A的起始储存地址 基地址 是1000,则A的地址是10766.4.叶子权值(5,6,17,8,19)所构造的哈夫曼树带权路径长度为12 1。8.2.在顺序表(8,11,15,19,2 5,2 6,3 0,3 3,4 2,4 8,5 0)中,用折半法查找关键字2 0,需要的关键字比较次数为4。8.3.对于具有14 4 个记录的文件,若采用分块查找法,且每块长度为8,则平均查找长度为8.2 5 或 14。5.2.设数组A 10,数组中任一元素均占内存4 8 个二进制位,从首地址2 000开始连续存放在主内存
14、里,主内存字长 为 16 位,那 么:1 存放该数组至少需要的单元数是2 7 0。2 存放数组的第8列的所有元素至少需要的单位数是2 7。数组按列存储时,元素A 的起始地址是2 2 3 1。选 择 题(15*1/=15,)一、叙述类根据数据元素之间关系的不同性,以下解释错误的是()。A集合中任何两个结点之间都有逻辑关系但组织形式松散 B线性结构中结点形成1 对 1 的关系C 树形结构具有分支、层次特性,其形态有点像自然界中的树D图状结构中的各个结点按逻辑关系互相缠绕,任何两个结点都可以邻接1 2 关于逻辑结构,以下说法错误的是()。A逻辑结构是独立于计算机的 B运算的定义与逻辑结构无关C同一逻
15、辑结构可以采用不同的存储结构 D 一些表面上很不相同的数据可以有相同的逻辑结构E 逻辑结构是数据组织的某种“本质性”的东西1.3.下面关于算法的说法正确的是()。A算法的时间效率取决于算法所花费的C P U 时间C算法必须具有有穷性、确定性等5个特性1.4.下面关于算法说法错误的是()。A计算机程序一定是算法C算法的可行性是指指令不能有二义性B 在算法设计中不能用牺牲空间代价来换取好的时间效率D通常用时空效率来衡量算法的优劣B 算法只能用计算机高级语言来描述D以上几个都是错误的1.6.以下说法正确的是()。A数据元素是数据的最小单位B数据项是数据的基本单位C原子类型不可再分解D数据项只能是原子
16、类型2.1.线性表是()A.一个有限序列,可以为空B.一个有限序列,不能为空2.3.线性表采用链式存储时,其各元素存储地址(A.必须是连续的 B.部分地址必须是连续的2.4.用链表表示线性表的优点是()oA.便于随机存取C.便于插入和删除2.5.()插入、删除速度快,但不能随机存取。A.链接表 B.顺序表C.一个无限序列,可 以 为 空 D.一个无限序列,不能为空C.一定是不连续的 D.连续与否均可以B.花费的存储空间较顺序存储少D.数据元素的物理顺序与逻辑顺序相同C.顺序有序表 D.上述三项无法比较2.6.若希望从链表中快速确定一个结点的前驱,则链表最好采用()方式。A.单链表 B.循环单链
17、表 C.双向链表 D.任意2.7.下面关于线性表的叙述错误的是()。A.线性表采用顺序存储,必须占用一片地址连续的单元 B.线性表采用顺序存储,便于进行插入和删除操作C.线性表采用链式存储,不必占用片地址连续的单元 D.线性表采用链式存储,便于进行插入和删除操作2.9.若某线性表中最常用的操作的操作是在最后一个元素之后插入一个元素和删除第一个元素,则 采 用()存储方法最节省运算时间。A.单链表3.1.栈和队列的共同点是(A.都是先进先出B.仅有头指针的单循环链表C.双链表 D.仅有尾指针的单循环链表)B.都是先进后出 C.只允许在端点处插入和删除元素 D.没有共同点3.4.递归过程或函数调用
18、时,处理参数及返回地址,要用一种称为()的数据结构。A.队列 B.多维数组 C.栈 D.线性表3 6 用链式存储的队列,在进行删除运算时(A.仅修改头指针 B.仅修改尾指针C.头、尾指针都要修改 D.头、尾指针可能都要修改3.7.栈应用在()oA.递归调用 B.子程序调用4.1.如下陈述中正确的事()A.串是一种特殊的线性表 B.串的长度必须大于零C.表达式求值D.A,B,CC.串中元素只能是字母D.空串就是空白串4.2.设有两个串p和q,其中q是p的子串,求q在p中首次出现的位置的算法称为()A.求子串4.4.串 是()A.不少于一个字母的序列4.5.串 的长度是指()A.串中所含不同字母的
19、个数5.4.对矩阵压缩储存是为了(A.方便压缩B.联接B.任意个字母的序列B.串中所含字符的个数)B.节省空间C.匹配C.串中所含不同字符的个数C.串中所含不同字符的个数C.方便存储D.求串长D.串中所含非空格字符的个数D.串中所含非空格字符的个数D.提高运算速度6.1.如果T 2是由树T转换而来的二叉树,那么对T中结点的后根遍历就是对T 2中结点的()遍历。A先序B中序C后序D层次序6.4.二叉树在线索后,仍不能有效求解的问题是()。A先序线索二又树中求先序后继C中序线索二叉树中求中序前驱B中序线索二叉树求中序后继D后序线索二叉树中求后序后继6.8 某二叉树的先序遍历序列和后序遍历序列正好相
20、反,则此二叉树一定是()。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的拓扑序列中,若顶点V i在顶点V j之前,则下列情形不可能出现的是(A.G中有弧 B.G中有一条从V i到V j的路径 C.G中没有弧
21、D.G中有一条从V j到V i的路径7.10.下列关于AOE网的叙述中,不正确的是()。A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成,那么整个工程将会提前完成C.所有的关键活动提前完成,那么整个工程将会提前完成D.某些关键活动提前完成,整个工程将会提前完成8.3.当采用分块查找时,A.数据分块若干块,B.数据分成若干块,C.数据分成若干块,D.数据分成若干块,数据的组织方式为()每块内数据有序每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数据组成索引块每块内数据有序,每块内最大(或最小)的数据组成索引块没 块(除最后一块外)中数据个数需相同8 5下面
22、关于折半查找的叙述正确的是()。A.表必须有序,表可以顺序方式存储,也可以链表方式存储B.表必须有序旦表中数据必须是整型,实型或字符型C.表必须有序,而且只能从小到大排序D.表必须有序,且表只能一顺序方式存储8.11.下面关于哈希查找的说法正确的是()A.哈希函数构造的越复杂越好,因为这样随机性好、冲突小 B.除留余数法是所有哈希函数中最好的C.不存在特别好与坏的哈希函数,要视情况而定D.若需在哈希表中删去一个元素,不管用何种方法解决冲突都只要简单地将该元素删去即可8.12.将1 0个元素散列到100000个单元的哈希表中,则()产生冲突。A.一定会 B.一定不会 C.仍可能会9.1.下列排序
23、算法中,其 中()是稳定的。A.堆排序和冒泡排序 B.快速排序和堆排序C.简单选择排序和归并排序 D.归并排序和冒泡排序9.3.以下时间复杂度不是O(nlog2n)的排序方法是()。A.堆排序 B.直接插入排序 C.二路归并排序 D.快速排序9.4.若需在O(nlog2n)的时间内完成对数组的排序,且要求排序是稳定的,则可以选择的排序方法是()。A.快速排序 B.堆排序 C.直接插入排序 D.归并排序9.7.在待排序的元素序列基本有序的前提下,效率最高的排序方法是()。A.直接插入排序 B.快速排序 C.简单选择排序 D.归并排序9.8.就排序算法所用的辅助空间而言,堆排序、快速排序、归并排序
24、的关系是(A.堆排序 快速排序=0;i-)for(j=l;jAj+lAj与 Aj+1互换;其中n 为正整数,则最后一行的语句频度在最坏情况下是()。A.O(n)B.O(n2)C.O(n3)D.O(nlog2n)2.2.从 一个具有n 个结点的单链表中查找值为x 结点,在查找成功情况下,需要平均比较()个结点。A.n B.n/2 C.(n-1)/2 D.(n+1)2.2.8.带头结点的单链表head为空的判定条件是()。A.head=NULL B.head一next=NULL C.head一next=head D.head!=NULL2.10.在循环双链表的p 所指结点之后插入s 所指结点的操作
25、是()。A.p-next=s;s-prior=p;p-next-prior=s;s-next=p一next;B.pnext=s;p nextprior=s;sprior=p;snext=p next;C.sprior=p;s next=p next;p next=s;pnextprior=s;D.sprior=p;s next=pnext;p nextprior=s;p next=s;3.2.若一个栈的输入序列为1,2,3,,n,输出序列的第一个元素是n,则第i 个输出元素是(A.n-i-1 B.n-i C.n-i+1 D.不确定3.3.设 a,b,c,d,e,f以给定的次序进栈,若在进栈操作
26、时,允许出栈操作,则下面得不到的序列为()。A.f,e,d,c,b,a B.b,c,a,f,e,d C.d,c,e,f,b,a D.c,a,b,d,e,f3 5 若 一 个 栈 以 向 量 存 储,初始栈顶指针top为 n+1,则下面x 入栈的正确操作是()。A.top=top+l;Vtop=x B.Vtop=x;top=top+1 C.top=top-l;Vtop=x D.Vtop=x;top=top-l3.8.中级表达式A-(B+C/D)XE的后缀形式是()。A.AB-C+D/Ex B.ABC+D/Ex C.ABCD/Ex+-D.ABCD/+Ex-3.9、假设以数组A m 存放循环队列的元
27、素,其头尾指针分别为front和 re a r,则当前队列中的元素个数为()A、(rear-front+m)%m B、rear-front+1 C、(front-rear+m)%m D、(rear-front)%m3.10、循环队列存储在数组A 0.m 中,则入队时队尾的操作为()A、rear=rear+l B、rear=(rear+1)%(m-1)C、rear=(rear+1)%m D、rear=(rear+1)%(m+1)3.11、若元素a,b,c,d,e,f 依次进栈,允许进栈,退栈操作交替进行,单不允许连续三次进行进退栈工作,则不可能得到的出栈序列是()A、dcebfa B、cbdae
28、f C、dbcaef D、afedcb3.12、某队列允许在其两端进行入队操作,但仅允许再一端进行出队操作,则不可能得到的顺序是()A、bacde B、dbace C、dbcae D、ecbad3.13、如果栈s 和队列q 的初始状态均为空,元 素 a,b,c,d,e,f,g 依次进入栈s,如果每个元素出栈立即进入队列q,且 7 个元素出队的顺序是b,d,c,f,e,a,g,则栈s 的容量至少是()A、1 B、2 C、3 D、44.3.串“ababaaababaa”的 next 数 组 为()A.012345678999 B,012121111212 C.011234223456 D.0123
29、012322344.6.若 s=l234ab567abedabO,t=ab,r=(空串),串替换 StrRep(s,t,r)的结果是()A.”1234ab567abedabO B.:1234ab567abed C.”1234567cd0 D/1234 567 cd 0”4.7.S为一个长度为n 的字符串,其中字符各不相同,则 S 中的互逆的非平凡子串(非空且不同于S 本身)的个数()A.2n-1 B.n2 C.(n2/2)+(n/2)D.(n2/2)+(n/2)-l4.8.若串 S=English,其中串的个数是()A.9 B.16 C.36 D.285.1.数组A的每个元素占5 个字节,将其
30、按列优先次序存储在起始地址为1000的内存单元中,则元素A4的地 址 是(1145)5.2.若对n 阶对称矩阵A 以行序为主序方式将其下三角的元素(包括主对角线上所有元素)依次存放于一维数组Bl.(n(n+1)/2中,ao。存放于数组B 中,则 在 B 中确认定aij(i j)的位置k 的关系为()A.iX (i+1)/2+j B.jX(j+1)/2+I C.iX(j-1)D.jXm+i-15.3.设二维数组Al.m,l.n按行存储在数组Bl.m Xn中,则 二 维 数 组 元 素 在 一 维 数 组 B 中的下标为()A.(i-1)Xn+j B.(i-l)Xn+j-l C.iX(j-1)D.
31、jXm+i-15.5.设广义表L=(a,b,c),则L 的长度和深度分别为()A.1 和 1 B.l 和 3 C.l 和 2 D.2 和 35.6.有一个100X90的稀疏矩阵,非 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(L
32、S)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 中的叶子数位()A 5B 6C 7D86.3.由4 个结点可以构造出()种不同的二叉树。DA 10B 12C 14166 5 若一棵二叉树具有10个度为2 的结点,5 个度为1 的结点,则度为0 的结点个数是()A 9D
33、B 11C 15不确定6.6 设高度为h 的二叉树只有度为0 和 2 的结点则此类二叉树中所包含的结点数至少为()个。A 2hB 2h-lC 2h+lD h+16.7 设给定权值的叶子总数有n 个,其哈夫曼树的结点总数为()。A 不确定B 2nC2n+1D 2n-l6.10.根据使用频率,为 5 个字符设计的哈夫曼编码不可能是()。A 111,110,10,01,00B 000,001,010,011,1 C 100,11,10,1,0D 001,000,01,11,107.1.无向图6=(V,E)丫二包廉7后事由簿卜心心伯卜用方刀乂巳叫淇中对该图进行深度优先遍历,得到的顶点序列正确的是()A
34、 a,b,e,c,d,fB a,cfe,b,d7 2 一个n 个顶点的连通无向图,其边的个数至少为(A.n-1B.nC a,e,b,cfd)C.n+1D a,e,dfc,bD.nlog2n7.3.在图采用邻接表存储时,求最小生成树的Prim算法的时间复杂度为()A.O(n)B.O(n+e)C.O(n2)D.O(n3)7.4.G 是一个非连通的无向组,共有28条边,则该图至少有()个顶点。A.6B.7C.8D.97 6 一个有n 个顶点的无向图,最 少 有()个连通分量,最 多 有()个连通分量。A.OB.lC.n-1D.n7.7.在一个无向图中,所有顶点的度数之和等于所有边数()倍,在一个有向
35、图中,所有顶点的入度之和等于所有顶点的出度之和的()倍。A.l2B.2C.lD.48.1.若查找每个记录的概率均等,则在具有n个记录的顺序文件中采用顺序查找法查找一个记录,其平均查找长度ASL为()A.(n-1)fl B.n/2 C.(n+l)/2 D.n8 2具有12个关键字的有序表,折半查找的平均查找长度为()A.3.1 B.4 C.2.5 D,58.10.假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入散列表中,至少要进行()次探测。A.k-1 次 B.k 次 C.k+1 次 D.k(k+l)/2 次9.2.若对N个元素进行快速排序,如果初始数据已经有序,则时间复杂度为(A.
36、0(1)B.O(n)C.O(nA2)D.O(Iog2n)9 5一组记录的关键字向46,79,56,38,40,84,则利用快速排序方法,以第一个记录为轴值得到的一次划分结果为()。A.38,40,46,56,79,84,B.40,38,46,79,56,84 C.40,38,46,56,79,84 D.40,38,46,84,56,799.6.一组记录的关键字为45,80,55,40,42,85,则利用堆排序方法建立的初始堆为()。A.80;45,50,40,42,85 B.85,80,55,40,42,45 C.85,80,55,45,42,40 D.85,55,80,42,45,40判断题
37、(i s *r =i s/)一、正 确(35个)1 5数据的物理结构是指数据在计算机内的实际存储形式。2.2.顺序存储的线性表可以按序号随机存取。2.3.线性表采用链式表存储时;存储空间可以是不连续的。2.7.循环链表可以在尾部设置头指针。2.8.为了方便插入和删除,可以使用双向链表存放数据。3 2栈是实现过程和函数调用所必须的结构.3 3两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出的机会,应把两个栈的栈底分别设在这片内存空间的两端.3.5.栈与队列是一种特殊的线性表3.7.循环队列通常会浪费一个存储空间.3.8.循环队列也存在空间溢出问题.3.9.栈和队列的存储方式,既可以是顺序
38、方式,又可以是链式方式.3.10.任何一个递归过程都可以转换成非递归过程.4.1.KMP算法的特点是在模式匹配时指示主串的指针不会变小。43nest函数值序列的产生仅与模式串有关。4.6.串名的存储应先高就是按串名访问串值的一种方法。4.8.在插入和删除操作中,链式串一定比顺序串方便。4.10.在串的顺序存储中,通常将作为串的结束标记。5.2.二维以上的数组其实是一种特殊的广义表。5.3.稀疏矩阵压缩存储后,必会失去随机存取功能。5 5线性表可以看成是广义表的特例,如果广义表中的每个元素都是原子,则广义表便成为线性表。5.6.一个广义表可以为其他广义表所共享。5.9.广义表是由零或多个原子或子
39、表所组成的有限序列,所以广义表可能为空表。5.10.任何一个非空广义表,其表头可能是单个元素或广义表,其表尾必定是广义表。6.1.哈夫曼树的结点个数不可能是偶数。6.4.哈夫曼编码是前缀编码。6.5.非空的二叉树一定满足:某结点若有左孩子,则其中序前驱一定没有右孩子。6.7.由先序和后序遍历序列不能唯一确定一棵二叉树。6.9.一棵树的叶结点,在先序遍历和后序遍历下,皆以相同的相对位置出现。7.4.哈夫曼编码是前缀编码。7 6必须把般树转成二叉树后才能进行存储。7.10.在哈夫曼树中,权值相同的叶结点都在同一层上。8.10.装填因子是哈希表的一个重要参数,他反应哈希表的装满成度。9 2在大根堆中
40、,最大元素在根的位置。9.8.只有在初始数据表为逆序时,直接插入排序所执行的比较次数最多。9.9.简单选择排序算法的时间复杂性不受数据的初始状态影响,为。(n2)。二、错 误(46个)1.1.数据元素是数据的最小单位。1 2数据的逻辑结构是指数据的各数据项之间的逻辑关系。1 3算法的优劣与算法描述语言无关,但与所用计算机有关。1.4.程序一定是算法。1.6.数据结构的抽象操作的定义与具体实现有关。1.7.数据的逻辑结构表达了数据元素之间的关系,它依赖于计算机的存储结构。2.1.链表中的头结点仅起到标识的作用。2.4.顺序存储方式插入和删除时效率太低,因此它不如链式存储方式好。2.5.对任何数据
41、结构,链式存储结构一定优于顺序存储结构。2.6.在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上并不一定紧邻。2.9.在单链表中,要取得某个元素,只要知道该元素的指针即可,因此,单链表是随即存取的存储结构。2.10.取线性表的第i个元素的时间与i的大小有关。3.1.消除递归一定要用栈.3.4.用递归方法设计的算法效率更高.3.6.队列从逻辑上讲,是一端既能增加又能减少的线性表.4.2.只要串采取定长顺序存储,串的长度就可立即获得,不需要函数求。4.4.空格串就是又零个字符组成的字符序列。4 5从串中取若干个字符组成的字符序列称为串的子串。4.7.两个串含有相等的字符,它们一定相等。4
42、.9 串的存储密度与结点大小无关。5.1.数组是一种复杂的数据结构,数组元素之间的关系既不是线性的,也不是树形的。5.4.一个稀疏矩阵A采用三元组形式表示,若把三元组中有关行下标的值互换,并把m和n的值互换,则就完成了A的转置运算。5.7.广义表中原子个数即为广义表的长度。5.8.所谓取广义表的表尾就是返回广义表中最后一个元素。6.2.二叉树中序线索化后,不存在空指针域。6 3二叉树中序线索化后,任意一个结点均有指向前驱和后继的线索。6.6.必须把一般树转换成二叉树后才能进行存储。6.8.一棵树中的叶子树一定等于与其对应的二叉树的叶子树。6.10.在哈夫曼树中,权值相同的叶结点都在同一层上。7
43、.1.哈夫曼树的结点个数不可能是偶数。7.2.二叉树中序线索化后,不存在空指针域。7 3二叉树线索化后,任意一个结点均有指向其前驱和后继的线索。7 5非空的二叉树一定满足:某结点若有左孩子,则其中序前驱一定没有右孩子。7.7.由先序和后序遍历序列不能唯一确定一棵二叉树。7.8,一棵树中的叶子树一定等于与其对应的二叉树的叶子树。8.1.折半查找法的查找速度定比顺序查找快。8 2就平均查找长度而言,分块查找最小,折半查找次之,顺序查找最大。8.4.哈希查找不需要进行任何比较。8.7.有序的线性表无论如何储存,都能采用折半查找。8.9.哈希表的平均查找长度与处理冲突的方法无关。9.1.快速排序的速度在所有的排序方法中最快,而且所需附加空间也最少。9 3用Shell方法排序时,若关键字的初始排序越杂乱无序,则排序效率越低。9.4.对n个记录进行堆排序,在最坏情况下的时间复杂度是0(d)。9 5在任何情况下,快速排序方法的时间性能总是最优的。9.6.堆是满二叉树。9.7.快速排序和归并排序在最坏情况下的比较次数都是O(niogzn)。