2023年电大数据结构本期末综合练习一

数据结构（本)期末综合练习一一、单项选择题1.数据元素是数据的基本单位,它()。A．只能有一个数据项组成B.至少有二个数据项组成Ｃ．至少有一个数据项为指针类型Ｄ．可以是一个数据项也可以由若干个数据项组成2．()是性质相同的数据元素的集合,是数据的子集。A．数据对象B．数据元素C．数据结构D.数据项３．线性表的顺序结构中,（)。A．逻辑上相邻的元素在物理位置上不一定相邻B．逻辑上相邻的元素在物理位置上也相邻C.数据元素是不能随机访问的D.进行数据元素的插入、删除效率较高4.设链表中的结点是ＮＯDE类型的结构体变量,且有NODＥ*ｐ；为了申请一个新结点，并由p指向该结点,可用以下语句（)。A．p=(ＮＯDE*)ｍalloc（ｓizeof(ｐ));B.p=(*NODE)ｍａlｌｏc(sｉzｅof(ＮOＤE)）;C.p＝(NODE)malloｃ(siｚeof（p)）；D．p＝(NODE*)mａlｌoc(sizeof(ＮODE));5．以下表中可以随机访问的是(）。A.单向链表Ｂ．顺序表C．单向循环链表D．双向链表6.设顺序存储的线性长度为ｎ,要在第i个元素之前插入一个新元素,按课本的算法当i=()时，移动元素次数为2A.n/2B．nC.n－17．设顺序存储的线性表长度为n，对于删除操作，设删除位置是等概率的,则删除一个元素平均移动元素的次数为(）。Ａ．(ｎ+1）/2B．ｎC.2nD.ｎ-i8．一个栈的进栈序列是1，2，3，4,则栈的不也许的出栈序列是()(进出栈操作可以交替进行）A.３,２,4,1B．３，2,1，4C.4,３，2，1D.１,4，２，３9.设top是一个链栈的栈顶指针,栈中每个结点由一个数据域ｄａtａ和指针域next组成,设用x接受栈顶元素,则出栈操作为()。A.ｔop=top->nｅxt;x=ｔop－>datａ;B.x=tｏｐ-＞data;top＝ｔop-＞nexｔ;C.ｘ=top-＞nｅxt;ｔop=toｐ－>data;D.tｏp->next=toｐ;ｘ=top－>dａｔa;１0．设有一个带头结点的链队列，队列中每个结点由一个数据域ｄatａ和指针域next组成，froｎt和reaｒ分别为链队列的头指针和尾指针。设p指向要入队的新结点(该结点已被赋值)，则入队操作为(）。A．ｒear->next＝p;ｒeａｒ=ｐ；B.rear－>nｅxt=p;ｐ=rear;C.ｐ=reaｒ－>ｎext;rear=p；Ｄ．reaｒ=ｐ;reａr->nｅｘt＝ｐ;１1．以下说法对的的是（)。A．队列是后进先出B．栈的特点是后进后出Ｃ.栈的删除和插入操作都只能在栈顶进行D.队列的删除和插入操作都只能在队头进行1２．以下说法不对的的是(）。A.顺序栈中，栈满时再进行进栈操作称为“上溢”B.顺序栈中，栈空时再作出栈栈操作称为“下溢”Ｃ.顺序队列中,队列的头指针和尾指针均超越队列存储空间的上界,则队列已空Ｄ.顺序队列中，当尾指针已经超越队列存储空间的上界，则一定是队列已满13．串函数StrCｍp(“abA”,”aｂa”)的值为(）。A．1B.0Ｃ.“abＡａbａ”D１4．设有一个2０阶的对称矩阵A，采用压缩存储方式,将其下三角部分以行序为主序存储到一维数组中(矩阵Ａ的第一个元素为a1１,数组b的下标从1开始），则矩阵元素a8,５在一维数组b中的下标是（)。Ａ．30B.2８C.4０D15．设有一个1２阶的对称矩阵Ａ，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中(矩阵A的第一个元素为a1,1,数组ｂ的下标从１开始），则矩阵Ａ中第4行的元素在数组ｂ中的下标i一定有()。A．7≤ｉ≤１0B．１1≤i≤15C.9≤ｉ≤14D．６≤i≤1６．深度为5的完全二叉树第5层上有４个结点,该树一共有（）个结点。A.２８B．３0C．31D１７．已知一个图的边数为m,则该图的所有顶点的度数之和为(）。A．２mB．mＣ.2m＋1D.m／218．已知一个图的所有顶点的度数之和为m,则m一定不也许是(）。Ａ.4B.8Ｃ.12D19.以下说法不对的的是（)。A.连通图G一定存在生成树B.连通图G的生成树中一定包含G的所有顶点C．连通图G的生成树中不一定包含G的所有边Ｄ.连通图Ｇ的生成树可以是不连通的２０.以下说法对的的是()。Ａ.连通图G的生成树中可以包含回路B.连通图G的生成树可以是不连通的C.连通图G的生成树一定是连通而不包含回路的Ｄ.连通图G的生成树一定是唯一的2１．散列查找的原理是()。A．在待查记录的关键字值与该记录的存储位置之间建立拟定的相应关系B．按待查记录的关键字有序的顺序方式存储C.按关键字值的比较进行查找D.基于二分查找的方法２2.对n个元素进行冒泡排序，通常要进行ｎ-1趟冒泡，在第ｊ趟冒泡中共要进行（）次元素间的比较。Ａ．jB.j－1C.n-jＤ23.排序过程中,每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子序列的适当位置，直到所有排好序为止,该排序算法是（)。A.直接插入排序B.快速排序C．冒泡排序D．选择排序24．在排序过程中，可以有效地减少一趟排序过程中元素间的比较次数的算法是(）。Ａ.冒泡B．选择Ｃ.折半插入D.直接插入２5．采用顺序查找法对长度为ｎ的线性表进行查找(不采用表尾设监视哨的方法),最坏的情况下要进行（)次元素间的比较。A．ｎ＋2B．nC.n-1D．n／２26．如图若从顶点a出发按深度优先搜索法进行遍历,则也许得到的顶点序列为（）。abecabecdfB．ａbeｄcfC．acｅbdfＤ．ａcfbｄe图127．如图若从顶点a出发按广度优先搜索法进行遍历，则也许得到的顶点序列为（）。ababecdhgfB.aｅbcghdfＣ.aedfbcghＤ．ａｂecdfｇh图228.一棵哈夫曼树有n个叶子结点(终端结点),该树总共有（)个结点。A.2n-2Ｂ.2n-１C.２nD.29.一棵哈夫曼树总共有23个结点，该树共有（）个叶结点（终端结点）Ａ．10Ｂ．11Ｃ.12D．3０．数据的()结构与所使用的计算机无关。A．逻辑Ｂ．物理C．存储D.逻辑与存储二、填空题1.通常数据的逻辑结构涉及__＿_、＿_＿＿、＿_＿_、___＿四种类型。２．通常可以把一本具有不同章节的书的目录结构抽象成＿＿__＿__＿结构。3．设有一个单向链表,结点的指针域为ｎext,头指针为head，p指向尾结点，为了使该单向链表改为单向循环链表,可用语句_＿______。4．要在一个单向链表中ｐ所指向的结点之后插入一个s所指向的新结点，若链表中结点的指针域为next,可执行________和p->nｅxt=s;的操作。5.设有一个单向循环链表，头指针为hｅad,链表中结点的指针域为next,p指向尾结点的直接前驱结点，若要删除尾结点,得到一个新的单向循环链表,可执行操作_____＿__。6.设有一个非空的链栈，栈顶指针为ｈs,要进行出栈操作,用x保存出栈结点的值，栈结点的指针域为neｘt,则可执行x=hs-＞ｄata;_____＿＿_。7.在一个链队中，ｆ和ｒ分别为队头和队尾指针,队结点的指针域为next,则插入一个s所指结点的操作为_______＿；ｒ=s；8．在一个不带头结点的非空链队中,f和r分别为队头和队尾指针,队结点的数据域为ｄaｔａ,指针域为ｎext,若要进行出队操作，并用变量x存放出队元素的数据值,则相关操作为x＝ｆ-＞ｄata;___＿____。9.循环队列的队头指针为f，队尾指针为r,当_____时表白队列为空。１0.循环队列的最大存储空间为ＭａxSｉze=8,采用少用一个元素空间以有效的判断栈空或栈满,若队头指针frｏｎt=4,则当队尾指针rｅar=_＿＿___＿_时，队列为空，当ｒear=＿____＿__时，队列有6个元素。11．“A”在存储时占_______＿个字节。12．稀疏矩阵存储时,采用一个由____、_＿__、____3部分信息组成的三元组唯一拟定矩阵中的一个非零元素。１3．一棵二叉树没有单分支结点,有6个叶结点,则该树总共有___＿___＿个结点。１4.一棵二叉树顺序编号为6的结点(树中各结点的编号与等深度的完全二叉树中相应位置上结点的编号相同),若它存在右孩子,则右孩子的编号为＿__＿＿___。15.按照二叉树的递归定义，对二叉树遍历的常用算法有__＿_、____、__＿＿三种。16.结构中的数据元素存在多对多的关系称为________结构。1７.把数据存储到计算机中,并具体体现数据之间的逻辑结构称为_______＿结构。1８．结构中的数据元素存在一对多的关系称为＿__＿___＿结构。19．如图3所示的二叉树,其后序遍历序列为。eefgibachd图320.如图４所示的二叉树，其前序遍历序列为_＿____＿＿_。ggfabdec图４21．二叉树为二叉排序的充足必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法是__________的。(回答对的或不对的)22.在队列的顺序存储结构中，当插入一个新的队列元素时，指针的值增1，当删除一个元素队列时，指针的值增1。２3．根据搜索方法的不同，图的遍历有____、____两种方法24.循环队列的引入,目的是为了克服。三、综合题1．(1)已知某二叉树的后序遍历序列是ｄebca，中序遍历序列是ｄｂｅac，试画出该二叉树(2)若上述二叉树的各个结点的字符分别代表不同的整数(其中没有相等的),并恰好使该树成为一棵二叉排序树，试给出a、b、c、d、e的大小关系(3）给出该树的前序遍历序列2.（１)设head1和p1分别是不带头结点的单向链表Ａ的头指针和尾指针,hｅａd2和p2分别是不带头结点的单向链表B的头指针和尾指针,若要把B链表接到A链表之后，得到一个以ｈeaｄ1为头指针的单向循环链表,写出其中两个关键的赋值语句（不用完整程序,结点的链域为nｅｘt)。（2）单向链表的链域为ｎexｔ，设指针p指向单向链表中的某个结点,指针s指向一个要插入链表的新结点，现要把s所指结点插入p所指结点之后,某学生采用以下语句：p->nｅｘt=s;ｓ->ｎｅxt=ｐ->next；这样做对的吗?若对的则回答对的,若不对的则说明应如何改写3.（1）设有一个整数序列{４０，２8，6,72，１00，3,5４}依次取出序列中的数,构造一棵二叉排序树(2)对上述二叉排序树,在等概率条件下,求成功查找的平均查找长度4．(1）画出对长度为10的有序表进行折半查找的鉴定树(以序号1,2,……10表达树结点)（2）对上述序列进行折半查找，求等概率条件下,成功查找的平均查找长度５.（１)运用筛选过程把序列{42，82,6７，102,16，3２，57,52}建成堆(小根堆),画出相应的完全二叉树（不规定中间过程)(2）写出对上述堆相应的完全二叉树进行中序遍历得到的序列6．（1)运用筛选法，把序列{３7,77，6２，９7,１1，27，52，4７}建成堆(小根堆)，画出相应的完全二叉树（2)写出对上述堆所相应的二叉树进行前序遍历得到的序列四、程序填空题1．以下函数在a[0]到a［n-1]中,用折半查找算法查找关键字等于ｋ的记录,查找成功返回该记录的下标，失败时返回－1，完毕程序中的空格typedefsｔrｕct{inｔkey;……}NOＤＥ;intBinａry_Search（NODEa[],intn，intk）{iｎtlow,mｉｄ,ｈigh;low=0；hiｇh＝n－１；ｗhilｅ(_＿_(1)_____){mid=(lｏw+ｈigh)/2;iｆ(a[ｍｉd］.key==k）return_＿（2)＿__＿__;ﻩｅlseif(___(3)＿__＿_)ｌow=mid+1; ｅlｓe_＿(4)__＿_＿_； }___(5）_____； }2．以下函数为直接选择排序算法,对a[１],a[2],…a[n］中的记录进行直接选择排序,完毕程序中的空格tyｐedｅｆｓtｒuct{intkｅy;……}NＯＤE;voidsｅｌsｏrt（NOＤＥa[］,ｉｎｔn)｛ﻩinｔi,ｊ，k; NODEtemp； for(i=1;i<=＿__(1)＿_＿＿_;i＋+）ﻩ{ﻩ ｋ=i; for(ｊ=i+1;j<=＿_＿(2)_＿_＿_;j＋+)ﻩ ﻩｉf（ａ［j].key<a［ｋ].keｙ)__(３)_＿___＿;ﻩ if(ｉ!=k）ﻩﻩ{ﻩﻩﻩtemp＝a[i]; ___(4)_＿_＿_； ___＿(5)____；ﻩﻩ} }}3．以下函数为链队列的入队操作，x为要入队的结点的数据域的值,front、reａr分别是链队列的队头、队尾指针stｒuｃtnｏde{ElemTypｅdａｔａ;stｒuctnoｄe*nｅｘt；｝;sｔruｃtnode＊front，*rear;voiｄInQuｅue(ElemTypex){structnoｄe＊p;p＝(sｔructnｏde*)＿＿_（1）_＿__＿；p->ｄａta=ｘ;p->next=NＵLＬ;_＿_(2)_＿＿__;reaｒ＝_＿_(3）＿____；｝4．以下程序是中序遍历二叉树的递归算法的程序，完毕程序中空格部分(树结构中左、右指针域分别为left和right,数据域ｄaｔa为字符型,BT指向根结点）。voｉdInordeｒ(stｒｕctBＴｒｅｅＮｏde*BT){iｆ(ＢＴ!=NULL）{（1);(2）;（３)；}}答案一、单项选择题1.D2．A3.Ｂ4．D5.Ｂ6．C7.A8.D9.Ｂ1０.Ａ11.C12.D13．D14．D1５．A１6.D１7．A18．D１9．D２0.Ｃ21．A22．C2３．A2４．C25．B26．Ｂ27．D28.B29.C30.Ａ二、填空题1.集合;线性；树形；图状2．树形3．ｐ－＞ｎexｔ=head；4.s->ｎｅxt=p->ｎｅｘt;５．p－>nexｔ＝heａd；6.ｈs=hｓ->nexｔ;7.r->nexｔ=ｓ8.f=f－>nｅxｔ;９．