2021年数据结构复习题及答案下载_Word模板_24

is_808969

暂无简介

2021年数据结构复习题及答案一、选取题。(每小题2分，共40分)(1)计算机辨认.存储和加工解决对象被统称为____A____。A.数据B.数据元素C.数据构造D.数据类型(2)数据构造普通是研究数据____A_____及它们之间联系。A.存储和逻辑构造B.存储和抽象C.抱负和抽象D.抱负与逻辑(3)不是数据逻辑构造是____A______。A.散列构造B.线性构造C.树构造D.图构造(4)数据构造被形式地定义为,其中D是____B_____有限集，R是____C_____有限集。A.算法B.数据元素C.数据操作D.逻辑构造(5)构成数据基本单位是___...

一、选取

题

快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题

。(每小题2分，共40分)(1)计算机辨认.存储和加工解决对象被统称为____A____。A.数据B.数据元素C.数据构造D.数据类型(2)数据构造普通是研究数据____A_____及它们之间联系。A.存储和逻辑构造B.存储和抽象C.抱负和抽象D.抱负与逻辑(3)不是数据逻辑构造是____A______。A.散列构造B.线性构造C.树构造D.图构造(4)数据构造被形式地定义为,其中D是____B_____有限集，R是____C_____有限集。A.算法B.数据元素C.数据操作D.逻辑构造(5)构成数据基本单位是____A______。A.数据项B.数据类型C.数据元素D.数据变量(6)设数据构造A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据构造A是____A______。A.线性构造B.树型构造C.图型构造D.集合(7)数据在计算机存储器内

表

关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf 视力表打印pdf 用图表说话 pdf

达时，物理地址与逻辑地址相似并且是持续，称之为___C____。A.存储构造B.逻辑构造C.顺序存储构造D.链式存储构造(8)在数据构造讨论中把数据构造从逻辑上分为___A____。A.内部构造与外部构造B.静态构造与动态构造C.线性构造与非线性构造D.紧凑构造与非紧凑构造(9)对一种算法评价，不涉及如下____B_____方面内容。A.健壮性和可读性B.并行性C.对的性D.时空复杂度(10)算法

分析

定性数据统计分析pdf 销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析

两个方面是__A____。A.空间复杂性和时间复杂性B.对的性和简要性C.可读性和文档性D.数据复杂性和程序复杂性(11)线性表是具备n个___C_____有限序列（n≠0)。A.表元素　　　　　　　　B.字符C.数据元素　　　　　　　D.数据项(12)线性表存储构造是一种____B____存储构造。A.随机存取B.顺序存取C.索引存取D.HASH存取(13)在一种长度为n顺序表中，向第i个元素（1≤i≤n＋１）之前插入一种新元素时，需要向后移动____B____个元素。A.n-iB.n-i+1C.n-i-1D.i(14)链表是一种采用____B____存储构造存储线性表；A.顺序B.链式C.星式D.网状(15)下面关于线性表论述错误是___D_____。A.线性表采用顺序存储必要占用一片持续存储空间B.线性表采用链式存储不必占用一片持续存储空间C.线性表采用链式存储便于插入和删除操作实现D.线性表采用顺序存储便于插入和删除操作实现(16)设指针q指向单链表中结点A，指针p指向单链表中结点A后继结点B，指针s指向被插入结点X，则在结点A和结点B之间插入结点X操作序列为__B______。A.s->next=p->next；p->next=-s；B.q->next=s；s->next=p；C.p->next=s->next；s->next=p；D.p->next=s；s->next=q；(17)设指针变量p指向单链表结点A，则删除结点A后继结点B需要操作为___A_____。A.p->next=p->next->nextB.p=p->nextC.p=p->next->nextD.p->next=p(18)下列说法哪个对的？____D______ A.堆栈是在两端操作、先进后出线性表B.堆栈是在一端操作、先进先出线性表C.队列是在一端操作、先进先出线性表D.队列是在两端操作、先进先出线性表(19)栈和队列共同点是 _____C_______。A.都是先进后出B.都是先进先出C.只容许在端点处插入和删除元素D.没有共同点(20)栈与普通线性表区别重要在_____D______。A、元素个数B、元素类型C、逻辑构造D、插入、删除元素位置(21)链栈与顺序栈相比，比较明显长处是_____D_____。A、插入操作更加以便　　　　　B、删除操作更加以便C、不会浮现下溢状况　　D、不会浮现上溢状况(22)如下数据构造中哪一种是非线性构造___D______。A.队列 B.栈 C.线性表 D.二叉树 (23)若已知一种栈入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为 _____C______。A.i B.B.n=i C.n-i+1 D.不拟定(24)当运用大小为N一维数组顺序存储一种栈时，假定用top==N表达栈空，则向这个栈插入一种元素时，一方面应执行 ____B______语句修改top指针。A.top++ B.top-- C.top=0 D.top(25)4个元素进S栈顺序是A,B,C,D，经运算POP(S)后，栈顶元素是___C_______。A.A B.B C.C D.D(26)一种栈输入序列是a,b,c,d,e,则栈不也许输出序列是____C_____。A.edcba B.decba C.dceab D.abcde(27)设输入序列是1、2、3、……、n，通过栈作用后输出序列第一种元素是n，则输出序列中第i个输出元素是____C______。A.n-i B.n-1-i C.n+1-i D.不能拟定(28)字符A、B、C、D依次进入一种栈，按出栈先后顺序构成不同字符串，至多可以构成___B___个不同字符串？A.15 B.14 C.16 D.21(29)设指针变量top指向当前链式栈栈顶，则删除栈顶元素操作序列为____D_______。A.top=top+1； B.top=top-1； C.top->next=top; D.top=top->next；(30)设栈S和队列Q初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一种元素出栈后即进入队列Q，若6个元素出列顺序为E2、E4、E3、E6、E5和E1，则栈S容量至少应当是____C_____。A.6 B.4 C.3 D.2(31)若用一种大小为6数组来实现循环队列，且当前rear和front值分别为0和3。当从队列中删除一种元素，再加入两个元素后，rear和front值分别为 ____B_____。A.1和5 B.2和4 C.4和2 D.5和1(32)设顺序循环队列Q[0：M-1]头指针和尾指针分别为F和R，头指针F总是指向队头元素前一位置，尾指针R总是指向队尾元素当前位置，则该循环队列中元素个数为____C_____。A.R-F B.F-R C.(R-F+M)%M D.(F-R+M)%M (33)设指针变量front表达链式队列队头指针，指针变量rear表达链式队列队尾指针，指针变量s指向将要入队列结点X，则入队列操作序列为 ____C_____。A.front->next=s；front=s； B.s->next=rear；rear=s； C.rear->next=s；rear=s； D.s->next=front；front=s；(34)如下陈述中对的是___A______。A.串是一种特殊线性表 B.串长度必要不不大于零 C.串中元素只能是字母 D.空串就是空白串(35)下列关于串论述中，对的是 ___D______。A.串长度是指串中不同字符个数 B.串是n个字母有限序列C.如果两个串具有相似字符，则它们相等 D.只有当两个串长度相等，并且各个相应位置字符都相符时才相等(36) 字符串长度是指___C______。A.串中不同字符个数 B.串中不同字母个数 C.串中所含字符个数 D.串中不同数字个数(37)两个字符串相等充要条件是____C______。A.两个字符串长度相等 B.两个字符串中相应位置上字符相等C.同步具备(A)和(B)两个条件 D.以上

答案

八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案

都不对(38)串是一种特殊线性表，其特殊性体当前____B_______。A.可以顺序存储 B.数据元素是一种字符C.可以链接存储 D.数据元素可以是各种字符(39)设有两个串p和q，求q在p中初次浮现位置运算称作 ____B______。A.连接 B.模式匹配 C.求子串 D.求串长(40)设串sI="ABCDEFG",s2="PQRST",函数con(x,y)返回x和y串连接串,subs(s,i,j)返回串s从序号i字符开始j个字符构成子串，len(s)返回串s长度，则con(subs(s1,2,1en(s2))，subs(sl,len(s2)，2))成果串是__D___。A.BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF(41)函数substr(“DATASTRUCTURE”，5，9)返回值为___A______。A.“STRUCTURE” B.“DATA” C.“ASTRUCTUR” D.“DATASTRUCTURE”(42)设串S=”IAMATEACHER!”，其长度是____D______。A.16 B.11 C.14 D.15 (43)假定在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶子结点数为____B____。A.15B.16C.17D.47(44)假定一棵二叉树结点数为18个，则它最小高度____B____。A.4B.5C.6D.18(45)在一棵二叉树中第五层上结点数最多为____C____。A.8B.15C.16D.32(46)在一棵具备五层满二叉树中，结点总数为____A____。A.31B.32C.33D.16(47)已知8个数据元素为(34、76、45、18、26、54、92、65)，按照依次插入结点办法生成一棵二叉排序树后，最后两层上结点总数为____B____。A.1B.2C.D.4(48)由分别带权为9、2、5、7四个叶子结点构造一棵哈夫曼树，该树带权途径长度为____C____。A.23B.37C.44D.46(49)在树中除根结点外，别的结点提成m(m≥0)个____A____集合T1,T2,T3...Tm,每个集合又都是树，此时结点T称为Ti父结点，Ti称为T子结点(1≤i≤m)。A.互不相交B.可以相交C.叶结点可以相交D.树枝结点可以相交(50)如果结点A有三个兄弟，并且B是A双亲，则B出度是____B____。A.3B.4C.5D.1(51)在一种有向图中，所有顶点入度之和等于所有顶点出度之和____B____倍。A.1/2B.1C.2D.4(52)具备n个顶点无向完全图，边总数为____D____条。A.n-1B.nC.n+1D.n*(n-1)/2(53)在无向图G邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于____C____。A.i+jB.i-jC.1D.0(54)图深度优先或广度优先遍历空间复杂性均为____A____。(访问标志位数组空间)A.O(n)B.O(e)C.O(n-e)D.O(n+e)(55)请指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用折半法查找核心码12需做____C___次核心码比较。A.2B.3C.4D.5(56)对线性表进行折半查找时，必要规定线性表____C____。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按核心字有序排列D.以链接方式存储，且结点按核心字有序排列(57)设二叉排序树中有n个结点，则在二叉排序树平均查找长度为___B_____。A.O(1)B.O(log2n)C.O(n)D.O(n2)(58)依次插入序列(50，72，43，85，75，20，35，45，65，30)后建立二叉搜索树中，查找元素35要进行__A___元素间比较。A.4次B.5次C.7次D.10次(59)设散列表中有m个存储单元，散列函数H(key)=key%p，则p最佳选取___B_____。A.不大于等于m最大奇数B.不大于等于m最大素数C.不大于等于m最大偶数D.不大于等于m最大合数(60)____D_____是HASH查找冲突解决办法。A.求余法B.平方取中法C.二分法D.开放地址法(61)当α值较小时，散列存储普通比其她存储方式具备_____B______查找速度。A.较慢B.较快C.相似D.不拟定(62)对线性表进行折半查找最以便存储构造是____B_______。A．顺序表B．有序顺序表C．链表D．有序链表(63)如果规定一种线性表既能较快查找，又能适应动态变化规定，可以采用_____D____查找办法。A．分块B．顺序C．折半D．散列(64)散列函数有一种共同性质，即函数值应按___C______取其值域每一种值。A．最大概率B．最小概率C．同等概率D．平均概率(65)下述排序算法中，稳定是___B_____。A.直接选取排序　　B.直接插入排序　　C.迅速排序D.堆排序(66)下列排序算法中，____A____需要辅助存储空间最大。A.迅速排序B.插入排序C.希尔排序D.基数排序(67)下列各种排序算法中平均时间复杂度为O(n2)是___D_____。A.迅速排序B.堆排序C.归并排序D.冒泡排序(68)在基于核心码比较排序算法中，____C_____算法在最坏状况下，核心码比较次数不高于O(nlog2n)。A.起泡排序B.直接插入排序C.二路归并排序D.迅速排序(69)一组记录为{46，79，56，38，84，40}，则采用冒泡排序法按升序排列时第一趟排序成果是___B_____。A.46,79,56,38,40,84B.46,56,38,79,40,84C.38,40,46,56,84,79D.38,46,79,56,40,84(70)每次从无序表中取出一种元素，把它插入到有序表中恰当位置，此种排序办法叫做___A_____排序。A.插入B.堆C.迅速D.归并(71)每次从无序表中挑选出一种最小或最大元素，把它互换到有序表一端，此种排序办法叫做___B_____排序。A.插入B.堆C.迅速D.归并(72)设一组初始记录核心字序列(5，2，6，3，8)，以第一种记录核心字5为基准进行一趟迅速排序成果为____C____。A.2，3，5，8，6B.3，2，5，8，6C.3，2，5，6，8D.2，3，6，5，8(73)下列排序办法中，哪一种办法比较次数与纪录初始排列状态无关___D_____。A.直接插入排序B.起泡排序C.迅速排序D.直接选取排序(74)设有核心码初始序列{Q，H，C，Y，P，A,M,S,R,D,F,X}，新序列{F，H，C，D，P，A，M，Q，R，S，Y,X}是采用____C____办法对初始序列进行第一趟扫描成果。A.直接插入排序B．二路归并排序C．以第一元素为分界元素迅速排序D．基数排序(75)在待排序文献已基本有序前提下，下述排序办法中效率最高是__C____。A.直接插入排序B.直接选取排序C．迅速排序D．归并排序(76)若需在O(nlog2n)时间内完毕对数组排序，且规定排序是稳定，则可选排序办法是___C_____。A.迅速排序B．堆排序C．归并排序D．直接插入排序(77)将两个各有n个元素有序表归并成一种有序表，其至少比较次数是___B_______。A．nB．2n-1C．2nD．n-1(78)下列排序算法中，____C____算法也许会浮现下面状况：初始数据有序时，耗费间反而最多。A.堆排序B．冒泡排序C．迅速排序D．SHELL排序二、填空题。(每空1分，共10分)(1)数据构造是一门研究非数值计算程序设计问题中计算机数据以及它们之间关系和运算等学科。(2)数据构造涉及数据逻辑构造构造和物理构造构造。(3)数据构造从逻辑上划分为三种基本类型：____线性数据构造_______、____树型构造______和_____图构造______。(4)数据物理构造被分为___顺序存储______、___链式存储_____、____索引存储______和______散列表（Hash）存储_____四种。(5)一种抽象数据类型涉及_____变量取值范畴_____和____操作类别_____两个某些。(6)数据逻辑构造是指数据元素间逻辑关系，数据存储构造是指数据元素存储方式或者数据元素物理关系。(7)数据构造是指数据及其互相之间____关系__________。当结点之间存在M对N（M：N）联系时，称这种构造为________网状构造________。当结点之间存在1对N（1：N）联系时，称这种构造为_____树构造__________。(8)对算法从时间和空间两方面进行度量，分别称为空间复杂度和时间复杂度分析。(9)算法效率可分为______空间_________效率和______时间_________效率。(10)for(i=1，t=1，s=0；i<=n；i++){t=t*i；s=s+t；}时间复杂度为___Ο(n)______。(11)线性表是n个元素_________有限序列____________________。(12)线性表存储构造有_________顺序存储和链式存储____________________。(13)设线性表中有n个数据元素，则在顺序存储构造上实现顺序查找平均时间复杂度为_____Ｏ(n)______，在链式存储构造上实现顺序查找平均时间复杂度为____O(n)_______。(14)设顺序线性表中有n个数据元素，则第i个位置上插入一种数据元素需要移动表中___n-i+1____个数据元素；删除第i个位置上数据元素需要移动表中___n-i____个元素。(15)若频繁地对线性表进行插入与删除操作，该线性表应采用_____链式_________存储构造。(16)链式存储构造中结点包括______数据__________域和_____指针__________域。(17)对于一种长度为n单链存储线性表，在表头插入元素时间复杂度为___Ο(1)______，在表尾插入元素时间复杂度为_____Ο(n)_______。(18)栈插入和删除只能在栈栈顶进行，后进栈元素必然先出栈，因此又把栈称为____FILO________表；队列插入和删除运算分别在队列两端进行，先进队列元素必然先出队列，因此又把队列称为 _____FIFO______表。(19)s=”Iamaman”长度为____10_______ 。(20)s1=”hello“,s2=”boy”,s1,s2连接后为：________helloboy______________ 。(21)s=”thisisthemainstring”,sub=”string”,strindex(s,sub)是：_______13_______。(22)inta[10][10],已知a=1000,sizeof(int)=2,求a[3][3]地址：_______1066___________ 。(23)设有两个串p和q，求q在p中初次浮现位置运算称为________模式匹配________。(24)在树型构造中，树根结点没有______前趋______结点，别的每个结点有且仅有______一______个前驱结点；树叶结点没有______后继______结点，别的每个结点______后继______结点数不受限制。(25)在一棵二叉树中，度为0结点个数为n0，度为2结点个数为n2，则：n0=______n2+1______。(26)由分别带权为3,9,6,2,5共五个叶子结点构成一棵哈夫曼树，则带权途径长度为______55______。(27)在图G邻接表表达中，每个顶点邻接表中所含结点数，对于无向图来说等于该顶点______度数______，对于有向图来说等于该顶点______出度数______。(28)假定一种图具备n个顶点和e条边，则采用邻接矩阵表达空间复杂性为______O(n2)______，采用邻接表表达空间复杂性为______O(n+e)______。(29)对于长度为n线性表，若进行顺序查找，则时间复杂度为______O(n)____；若采用折半法查找，则时间复杂度为______O(log2n)____。(30)假设在有序线性表A[1..20]上进行折半查找，则比较一次查找成功结点数为____1_______，则比较二次查找成功结点数为____2_______，则比较三次查找成功结点数为____4_______，则比较四次查找成功结点数为_____8______，则比较五次查找成功结点数为____5_______，平均查找长度为_____log2(n+1)-1______。(31)在一棵二叉排序树中，每个分支结点左子树上所有结点值一定_____不大于______该结点值，右子树上所有结点值一定____不不大于_______该结点值。(32)对一棵二叉排序树进行中序遍历时，得到结点序列是一种_______增序序列_______________。(33)对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0元素是_____70_________，散列地址为6是____34,20,55_________。(34)在线性表散列存储中，装填因子a又称为装填系数，若用m表达散列表长度，n表达待散列存储元素个数，则a等于____n/m_______。(35)散列表中解决冲突两种办法是____开放地址法_________和____链地址法_________。(36)在散列存储中，装填因子a值越大，则_______产生冲突也许性就越大____________；a值越小，则_____产生冲突也许性就越小___________。(37)散列法存储基本思想是由________核心码直接______________决定数据存储地址。(38)构造哈希函数办法有(写二个)______________直接定址法，数字分析法，平方取中法，折叠法，除留余数法，随机数法_________________________________________。(39)在分块查找中一方面查找_____索引________，然后再查找相应______块_________。(40)散列表查找效率重要取决于散列表造表时选取_____哈希函数________和______装填因子_________。(41)对两棵具备相似核心字集合而形状不同二叉排序树，____中序_______遍历它们得到序列顺序是同样。(42)当待排序记录数较大，排序码较随机且对稳定性不作规定期，宜采用______迅速_________排序；当待排序记录数较大，存储空间容许且规定排序是稳定期，宜采用______归并_________排序。(43)在堆排序过程中，对任一分支结点进行筛运算时间复杂度为___O(log2n)_____，整个堆排序过程时间复杂度为____O(nlog2n)____。(44)当向一种大根堆插入一种具备最大值元素时，需要逐级____向上_____调节，直到被调节到_____根结点_______位置为止。(45)对一组初始核心字序列（40，50，95，20，15，70，60，45，10）进行冒泡排序，则第一趟需要进行相邻记录比较次数为____8______，在整个排序过程中最多需要进行_____8_____趟排序才可以完毕。(46)在在插入排序、选取排序、迅速排序、堆排序、归并排序和基数排序中，平均比较次数至少排序是___迅速_______，需要内存容量最多是____归并______。(47)堆排序是不稳定，空间复杂度为____O(1)_____。在最坏状况下，其时间复杂度也为___O(nlog2n)______。(48)若待排序文献中存在各种核心字相似记录，通过某种排序办法排序后，具备相似核心字记录间相对位置保持不变，则这种排序办法是____稳定_______排序办法。(49)在对一组记录(50,40,95，20，15,70,60,45,80)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较____3_____次。(50)二路归并排序时间复杂度是___O(nlog2n)______。(51)对于n个记录集合进行归并排序，所需附加空间消耗是___O(n)______。(52)设表中元素初始状态是按键值递增，分别用堆排序、迅速排序、冒泡排序和归并排序办法对其仍按递增顺序进行排序，则______冒泡排序_________最省时间，____迅速排序________最费时间。三、判断题。(每小题1分，共10分)(×)1．数据元素是数据最小单位。(×)2．数据项是数据基本单位。(√)3．顺序存储线性表可以随机存取。(√)4．线性表中元素可以是各种各样，但同一线性表中数据元素具备相似特性，因而，是属于同一数据对象。(×)5．在单链表中，任何两个元素存储位置之间均有固定联系，由于可以从头结点查找任何一种元素。(×)6．在单链表中，要获得某个元素，只要懂得该元素指针即可，因而，单链表是随机存取存储构造。(×)7．链表每个结点中，都正好包括一种指针。(×)8．数组是同类型值集合。(√)9．使用三元组表达稀疏矩阵元素，有时并不能节约存储时间。(√)10.线性表可以当作是广义表特例，如果广义表中每个元素都是原子，则广义表便成为线性表。(√)11.由树转换成二叉树，其根结点右子树总是空。(×)12.后序遍历树和中序遍历与该树相应二叉树，其成果不同。(×)13.若有一种结点是某二叉树子树中序遍历序列中最后一种结点，则它必是该子树前序遍历序列中最后一种结点。(√)14.若一种树叶是某子树中序遍历序列中最后一种结点，则它必是该子树前序遍历序列中最后一种结点。(×)15.已知二叉树前序遍历和后序遍历序列并不能唯一地拟定这棵树，由于不懂得树根结点是哪一种。(×)16.在哈夫曼编码中，当两个字符浮现频率相似时，其编码也相似，对于这种状况应作特殊解决。(√)17.有回路图不能进行拓扑排序。(×)18.连通分量是无向图中极小连通子图。(√)19.散列法存储基本思想是由核心码值决定数据存储地址。(√)20.散列表查找效率取决于散列表造表时选用散列函数和解决冲突办法。(√)21.m阶B-树每一种结点子树个数都不大于或等于m。(√)22.中序遍历二叉排序树结点就可以得到排好序结点序列。(√)23.在二叉排序树上插入新结点时，不必移动其他结点，仅需改动某个结点指针，由空变为非空即可。(√)24.当待排序元素诸多时，为了互换元素位置，移动元素要占用较多时间，这是影响时间复杂性重要因素。(√)25.对于n个记录集合进行迅速排序，所需要平均时间是O(nlog2n)。(√)26.对于n个记录集合进行归并排序，所需要平均时间是O(nlog2n)。(√)27.堆中所有非终端结点值均不大于或等于（不不大于或等于）左右子树值。(×)28.磁盘上顺序文献中插入新记录时，必要复制整个文献。(×)29.在索引顺序文献中插入新记录时，必要复制整个文献。(×)30.索引顺序文献是一种特殊顺序文献，因而普通存储在磁带上。四、简答题。(共6小题，每小题约5分，共32分)1.简述下列术语：数据、数据项、数据元素、数据逻辑构造、数据存储构造、数据类型和算法。数据：数据是信息载体，是计算机程序加工和解决对象，涉及数值数据和非数值数据。数据项：数据项指不可分割、具备独立意义最小数据单位，数据项有时也称为字段或域。数据元素：数据元素是数据基本单位，在计算机程序中普通作为一种整体进行考虑和解决，一种数据元素可由若干个数据项构成。数据逻辑构造：数据逻辑构造就是指数据元素间关系。数据存储构造：数据物理构造表达数据元素存储方式或者数据元素物理关系。数据类型：是指变量取值范畴和所可以进行操作总和。算法：是对特定问题求解环节一种描述，是指令有限序列。2.简述栈和线性表区别。答：普通线性表使用数组来表达。线性表普通有插入、删除、读取等对于任意元素操作。而栈只是一种特殊线性表。栈只能在线性表一端插入（称为入栈,push）或者读取栈顶元素或者称为“弹出、出栈”(pop)。3.简述栈和队列这两种数据构造相似点和不同点。答：相似点：栈和队列都是特殊线性表，只在端点处进行插入，删除操作。不同点：栈只在一端（栈顶）进行插入，删除操作；队列在一端（top）删除，一端(rear)插入。4.如果进栈元素序列为A，B，C，D，则也许得到出栈序列有多少种?写出所有也许序列。答：也许序列有14种：ABCD；ACBD；ACDB；ABDC；ADCB；BACD；BADC；BCAD；BCDA；BDCA；CBAD；CBDA；CDBA；DCBA。5.如果进栈元素序列为1，2，3，4，5，6，能否得到4，3，5，6，1，2和1，3，5，4，2，6出栈序列?并阐明为什么不能得到或如何得到。答：不能得到4，3，5，6，1，2，最先出栈是4,则按321方式出，不也许得到1在2前序列，可以得到1，3，5，4，2，6，按如下方式进行push(1)，pop()，push(2)，push(3)，pop()，push(4)，push(5)，pop()，pop()，pop()，push(6)，pop()。6.设s=“IAMASTUDENT”,t=“GOOD”，q=“WORKER”。求：StrLength(s)，StrLength(t)，SubStr(s，8，7)，SubStr(t，2，1)，StrIndex(s,“A”)，StrIndex(s，t)，StrRep(s，“STUDENT”，q)，SubStr(SubStr(s，6，2)，StrConcat(t，SubStr(s，7，8)))。答：StrLength(s)=14，StrLength(t)=4，SubStr(s，8，7)=”STUDENT”，SubStr(t，2，1)=”O”,StrIndex(s,“A”)=3，StrIndex(s，t)=0，StrRep(s，“STUDENT”，q)=”IAMAWORKER”,7.简述下列每对术语区别：空串和空格串；串变量和串常量；主串和子串；串变量名字和串变量值。答：空串：不含任何字符；空格串：所含字符都是空格。串变量和串常量:串常量在程序执行过程中只能引用不能变化；串变量值在程序执行过程中是可以变化和重新赋值。主串与子串：子串是主串一种子集。串变量名字与串变量值:串变量名字表达串值标记符。8.设有二维数组A(6×8)，每个元素占6个字节存储，顺序存储，A起地址为1000，计算：(1)数组A体积(即存储量)；(2)数组最后一种元素A起地址；(3)按行优先存储时，元素A1,4起地址；(4)按列优先存储时，元素A4,7起地址。 (1)6*8*6=288(2)1000+47*6=1282(3)1000+(8+4)*8=1096(4)1000+(6*7+4)*8=13689.分别画出含三个结点无序树与二叉树所有不同形态。答：无序树形态如下：二叉树形态如下：10.分别写出图1中所示二叉树先序遍历、中序遍历、后序遍历结点访问序列。答：先序遍历序列:ABDEHICFJG中序遍历序列:DBHEIAFJCG后序遍历序列:DHIEBJFGCA11.试找出分别满足下列条件所有二叉树。(1)先序序列与中序序列相似。(2)后序序列与中序序列相似。(3)先序序列与后序序列相似。答：(1)先序序列和中序序列相似：空树或缺左子树单支树；(2)后序序列和中序序列相似：空树或缺右子树单支树；(3)先序序列和后序序列相似：空树或只有根结点二叉树。12.已知一棵二叉树中序序列和后序序列分别为BDCEAFHG和DECBHGFA，试画出这棵二叉树。答：这棵二叉树为:13.分别写出图2中所示二叉树先序遍历、中序遍历、后序遍历结点访问序列。答：先序遍历序列:ABDGCEHF中序遍历序列:DGBAEHCF后序遍历序列:GDBHEFCA14.给定权值(7,18,3,32,5,26,12,8)，构造哈夫曼树。答：哈夫曼树为:15.假设用于通信电文仅由8个字母构成，字母在电文中浮现频率分别为7,19,2,6,32,3,21,10，试为这8个设计哈夫曼编码。答：哈夫曼树为:在上述哈夫曼树每个左分支上标以0，右分支上标以1，并设这8个字母分别为A、B、C、D、E、F、G和H，则它们哈夫曼树为分别为:A：0000B：10C：00110D：0010E：01F：00111G：11H：000116.画出无向图G1邻接矩阵和邻接表达意图，并写出每个顶点度。答：（1）邻接矩阵:（2）邻接链表：（3）每个顶点度：顶点度V13V23V32V43V5317.画出有向图G2邻接矩阵、邻接表和逆邻接表达意图，并写出每个顶点入度和出度。答：（1）邻接链表：（2）逆邻接链表：（3）顶点入度出度V130V222V312V413V521V62318.相应图G3，写出从v1出必深度优先遍历序列和广度优先遍历序列各三个。答：深度优先查找遍历序列：V1V2V3V4V5；V1V3V5V4V2；V1V4V3V5V2广度优先查找遍历序列：V1V2V3V4V5；V1V3V2V4V5；V1V4V3V2V519.何谓二叉排序树?答：一棵二叉排序树(又称二叉查找树)或者是一棵空树，或者是一棵同步满足下列条件二叉树：(1)若它左子树不空，则左子树上所有结点键值均不大于它根结点键值。(2)若它右子树不空，则右子树上所有结点键值均不不大于它根结点键值。(3)它左、右子树也分别为二叉排序树。20.顺序查找时间为O(n)，二分查找时间为O(log2n)，散列查找时间为O(1)，为什么有高效率查找办法而不放弃低效率办法?答：衡量算法原则有诸多，时间复杂度只是其中之一。尽管有些算法时间性能较好，但是其她方面也许就存在着局限性。例如散列查找时间性能很优越，但是需要关注如何合理地构造散列函数问题，并且总存在着冲突等现象，为理解决冲突，还得采用其她办法。二分查找也是有代价，由于事先必要对整个查找区间进行排序，而排序也是费时，因此常应用于频繁查找场合。对于顺序查找，尽管效率不高，但却比较简朴，惯用于查找范畴较小或偶而进行查找状况。21.简述多重散列法解决冲突基本思想。答：此法规定设立各种散列函数Hi，i=1，…，k。当给定值K与闭散列表中某个键值是相对于某个散列函数Hi同义词因而发生冲突时，继续计算该给定值K在下一种散列函数Hi+1下散列地址，直到不再产生冲突为止。22.简述公共溢出区法解决冲突基本思想。答：散列表由两个一维数组构成。一种称为基本表，另一种称为溢出表。插入一方面在基本表上进行；如果发生冲突，则将信息存人溢出表。23.在结点个数为n(n>1)各棵树中，高度最小树高度是多少?它有多少个叶结点?多少个分支结点?高度最大树高度是多少?它有多少个叶结点?多少个分支结点?答：结点个数为n时，高度最小树高度为1，有两层，它有n-1个叶结点，1个分支结点；高度最大树高度为n-l，有n层，它有1个叶结点，n-1个分支结点。24.什么是内部排序?什么是排序办法稳定性?答：假定给定具有n个记录文献(r1，r2，…，rn)，其相应核心字为(k1，k2，…，kn)，则排序就是拟定文献一种序列r1，r2，…，rn，使得k1≤k2≤…≤kn，从而使得文献中n个记录按其相应核心字有序排列。如果整个排序过程在内存中进行，则排序叫内部排序。假设在待排序文献中存在两个或两个以上记录具备相似核心字，若采用某种排序办法后，使得这些具备相似核心字记录在排序先后相对顺序依然保持不变，则以为该排序办法是稳定，否则就以为排序办法是不稳定。五、分析题。(每小题4分，共8分)1.分析下面语句段执行时间复杂度。(1)for(i＝1；i<＝n；i++)for(j＝1；j<＝n；j++)s++；(2)for(i＝1；i<＝n；i++)for(j＝i；j<＝n；j++)s++；(3)for(i＝1；i<＝n；i++)for(j＝1；j<＝i；j++)s++；(4)i＝1；k＝0；while(i<＝n-1){k+＝10*i；i++；}(5)for(i＝1；i<＝n；i++)for(j＝1；j<＝i；j++)for(k＝1；k<＝j；k++)x=x+1；(1)Ο(n2)(2)Ο(n2)(3)Ο(n2)(4)Ο(n-1)(5)Ο(n3)2.写出下列程序段运营成果(栈中元素类型是char)：main(){ SeqStack s，*p;；charx，y；p=&s;Init_Queue(p);x=‘c’； y=‘k’；push(p，x)；push(p，’a’)；push(p，y);x=pop (p);push(p，’t’); push(p，x)；x=pop(p)；push(p，’s’);while(!Empty_SeqStack(p)) {y=pop(p)； printf(“％c”，y)；}printf(“％c＼n”，x)； }答：stack3.写出下列程序段运营成果(队列中元素类型是char)：main() { SeQueue a，*q;charx，y；q=&a； x=’e’； y=’c’;Init_Queue(q);In_Queue(q，’h’); In_Queue(q，’r’); In_Queue(q，y);x=Out_Queue(q)；In_Queue(q，x)；x=Out_Queue(q);In_Queue(q，’a’)；while(!Empty_SeqStack(q)) {y=Out_Queue(q)； printf(“%c”，y)；}printf(“%C\n”，x)；}答：char

本文档为【2021年数据结构复习题及答案】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。

2021年数据结构复习题及答案

热门搜索

历史搜索