2023年电大数据结构本期末复习材料

中央电大开放本科计算机科学与技术数据结构(本）期末综合练习一、单项选择题１.数据元素是数据的基本单位,它（C）。Ａ．只能有一个数据项组成B.至少有二个数据项组成C.可以是一个数据项也可以由若干个数据项组成D．至少有一个数据项为指针类型２．一种逻辑结构（A）存储结构。Ａ.可以有不同的B.只能有唯一的C.的数据元素在计算机中的表达称为D．的数据元素之间的关系称为3.线性表的顺序结构中，(C)。A．逻辑上相邻的元素在物理位置上不一定相邻B．数据元素是不能随机访问的C.逻辑上相邻的元素在物理位置上也相邻D.进行数据元素的插入、删除效率较高４．以下说法中不对的的是（B)。A．双向循环链表中每个结点需要包含两个指针域B．已知单向链表中任一结点的指针就能访问到链表中每个结点C.顺序存储的线性链表是可以随机访问的Ｄ.单向循环链表中尾结点的指针域中存放的是头指针5．以下表中可以随机访问的是（Ｄ）。Ａ.单向链表B．双向链表C．单向循环链表D.顺序表6．双向循环链表结点的数据类型为:struｃtnode｛ｉｎtdaｔa;strucｔｎｏde*nexｔ;/*指向直接后继*／sｔructnodｅ*prior;}；设p指向表中某一结点，要显示ｐ所指结点的直接前驱结点的数据元素，可用操作(B）。A．prｉntf(“%d”,p－＞neｘt->data)；B.pｒｉntｆ(“%d”,ｐ->prior->ｄａtａ);C.priｎtｆ(“%ｄ”,ｐ->ｐriｏr->ｎｅxt);Ｄ．prｉｎtf(“%ｄ”,p->data);7.设顺序存储的线性表长度为ｎ,对于删除操作，设删除位置是等概率的,则删除一个元素平均移动元素的次数为（Ａ）。A．(ｎ+１)／2Ｂ.ｎC．2nD.n-i８.一个栈的进栈序列是eｆgh，则栈的不也许的出栈序列是(D)（进出栈操作可以交替进行）。A．ｈgｆｅＢ.gfehC.fｇｅhD．ｅhfｇ9.设top是一个链栈的栈顶指针,栈中每个结点由一个数据域data和指针域next组成,设用x接受栈顶元素，则出栈操作为(A)。A.ｘ=ｔｏｐ－>daｔａ;toｐ=toｐ->ｎｅxt;B.ｔop＝top->next;x＝top->data;C．x=top->ｎext;ｔoｐ=top->data;D.toｐ->ｎｅxｔ=ｔop；ｘ=toｐ->daｔa；１0．设top是一个链栈的栈顶指针,栈中每个结点由一个数据域data和指针域next组成,设用x接受栈顶元素，则取栈顶元素的操作为（C)。A．ｔｏp－＞ｄaｔa=ｘ;B．toｐ=top－＞nｅxｔ;C.ｘ=tｏｐ->datａ;D.ｘ=top－>data;toｐ=top->ｎexｔ;１1．以下说法对的的是（Ｃ)。Ａ．队列是后进先出B.栈的特点是后进后出C．栈的删除和插入操作都只能在栈顶进行D.队列的删除和插入操作都只能在队头进行13．串函数StｒCｍp(“abＡ”,”ａba”)的值为(D）。Ａ.1B．0C.“aｂAabａ”Ｄ.-114．cｈaｒ*ｐ；p＝StrCａt(“ABD”,”ABC”);Priｎtf(“％s”,ｐ);的显示结果为(B)。A．-1B．ABDABＣC．ABD.115．设有一个12阶的对称矩阵Ａ，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中（矩阵A的第一个元素为a1，1，数组b的下标从1开始）,则矩阵A中第4行的元素在数组b中的下标i一定有(A)。A、７≤i≤10B、１1≤i≤15C、9≤i≤１４D、６≤i≤9１6.深度为5的满二叉树至多有（B）个结点(根结点为第一层)A．40B．３1C．34D.3517.已知一个图的边数为m，则该图的所有顶点的度数之和为（A)。A.2mＢ.ｍＣ．2ｍ+1Ｄ.m/218．已知一个图的所有顶点的度数之和为m，则该图的边数为(D）。A．２ｍB.mＣ.２m+1D.m/2１９.以下说法不对的的是（D)。A.连通图G一定存在生成树B.连通图Ｇ的生成树中一定包含G的所有顶点C．连通图G的生成树中不一定包含G的所有边D．连通图Ｇ的生成树可以是不连通的20.以下说法不对的的是(A)。A.连通图Ｇ的生成树一定是唯一的B.连通图Ｇ一定存在生成树C.连通图G的生成树中一定要包含Ｇ的所有顶点D．连通图Ｇ的生成树一定是连通并且不包含回路21.散列查找的原理是（Ａ）。A.在待查记录的关键字值与该记录的存储位置之间建立拟定的相应关系B.按待查记录的关键字有序的顺序方式存储C.按关键字值的比较进行查找D．基于二分查找的方法22.有序表为{1，2,4,6，10,１８，20，32},用课本中折半查找算法查找值１８，经(B)次比较后成功查到。Ａ.3B.２C．4D.523．排序过程中，每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子序列的适当位置，直到所有排好序为止,该排序算法是(A）。A.直接插入排序B.快速排序C．冒泡排序Ｄ．选择排序24．在排序过程中，可以通过某一趟排序的相关操作所提供的信息,判断序列是否已经排好序,从而可以提前结束排序过程的排序算法是(A)。A．冒泡B.选择C.直接插入Ｄ．折半插入2５．采用顺序查找法对长度为ｎ的线性表进行查找（不采用表尾设监视哨的方法）,最坏的情况下要进行（B）次元素间的比较。A.n+2B.nＣ.n-１D.n/２26．用折半查找法,对长度为12的有序的线性表进行查找，最坏情况下要进行(Ａ）次元素间的比较Ａ．４B．3Ｃ.５D.6２7.如图若从顶点a出发按广度优先搜索法进行遍历,则也许得到的顶点序列为(D)。ababecdhgfB．aｅbcghｄfC．aedfｂcghD.abecdfｇh图12８.如图若从顶点a出发按深度优先搜索法进行遍历，则也许得到的顶点序列为（B)。bcbcgdafeB.aｅdｂｇfｃC．aｃfｅbdgD.aecｂdgf2９.一棵哈夫曼树总共有23个结点，该树共有（D）个叶结点（终端结点）Ａ.10B．1３C．11D．1２3０.一棵哈夫曼树总共有25个结点，该树共有（A)个非叶结点（非终端结点)。A.12B．13C.１4D.1531．针对线性表，在存储后假如最常用的操作是取第i个结点及其前驱,则采用(D）存储方式最节省时间。A.单链表B.双链表C.单循环链表D.顺序表３2．线性表采用链式存储时，其地址(Ｃ）。A．一定是不连续的B.必须是连续的C.可以连续也可以不连续D.部分地址必须是连续的３３.数据结构中，与所使用的计算机无关的是数据的(D)结构。A.物理B．存储C.逻辑与物理D．逻辑34.带头结点的单向链表的头指针为heaｄ，该链表为空的鉴定条件是(Ｃ)的值为真。Ａ.head＝＝NＵLLB.heａd－>next==hｅadC.heaｄ->next==NULＬD．heａd＝=head－>nｅｘt３5．以下特性中,（D）不是算法的特性。A．有穷性B．拟定性C.可行性D.有0个或多个输出36.设顺序存储的线性表长度为n,对于插入操作，设插入位置是等概率的，则插入一个元素平均移动元素的次数为(Ａ）。Ａ.n/２Ｂ.ｎC.ｎ-1D.n-i＋13７．设有一个长度为n的顺序表,要在第i个元素之前（也就是插入元素作为新表的第ｉ个元素),则移动元素个数为(A)。A.ｎ-i＋１Ｂ．n-iC.n-i-1D.i38．一个栈的进栈序列是５,６，7，8，则栈的不也许的出栈序列是（A）(进出栈操作可以交替进行）A.5,8,6，7Ｂ.7，6，８，５Ｃ．7,6，5,８D．8,7,6,５３9.栈的插入删除操作在(D)进行。A.栈底B.任意位置C．指定位置Ｄ．栈顶4０.栈和队列的相同点是（Ｄ）。A．都是后进先出Ｂ.都是后进后出C.逻辑结构与线性表不同D.逻辑结构与线性表相同,都是操作规则受到限制的线性表4１.以下说法对的的是（C)。A.栈的特点是先进先出，队列的特点是先进后出B.栈和队列的特点都是先进后出Ｃ.栈的特点是先进后出，队列的特点是先进先出Ｄ.栈和队列的特点都是先进先出4２．在C语言中，运用数组a存放字符串“Hello”，以下语句中对的的是(A）。A.chara[10］=“Hｅlｌo”;Ｂ．chara［1０];a=“Helｌo”;C.cｈａrａ[1０]=‘Helｌo’；D．ｃhaｒa[１0]＝{‘H’,’e’,’l’，’ｌ’,’o’};43.元素2，４,6,８按顺序依次进栈,则该栈的不也许输出序列是（D）(进栈出栈可以交替进行)。A．8，6，4，2B.2，4，６,8C．4,2,8,6D．8，6,2，444.设有一个15阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储到一维数组ｂ中。(矩阵A的第一个元素为a1，1,数组ｂ的下标从1开始)，则数组元素ｂ［13]相应A的矩阵元素是（A）。A.ａ5,３B.a６，４C．a7,2D．ａ6，８４5.设有一个1５阶的对称矩阵Ａ，采用压缩存储的方式,将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始）,则矩阵中元素a7,6在一维数组Ｂ中的下标是（Ｃ)。A.４2B.１3C．27D.324６.一棵完全二叉树共有30个结点,则该树一共有（D)层(根结点所在层为第一层）。Ａ．6B．4C.3Ｄ．５4７.串函数StrCmｐ(“d”,“D”)的值为(B)。A.0B．１Ｃ．-1D．３48．以下说法对的的是(D)。A.连通图G的生成树中不一定包含G的所有顶点B.连通图G的生成树中一定要包含G的所有边Ｃ．连通图G的生成树一定是唯一的D.连通图G一定存在生成树49.在一棵二叉树中,若编号为ｉ的结点存在右孩子,则右孩子的顺序编号为（D)。Ａ.2ｉB.2i-1Ｃ.2i+2D．2i+150．对二叉排序树进行（Ｃ)遍历,遍历所得到的序列是有序序列。A.按层次Ｂ．前序Ｃ.中序D．后序5１.设一棵有n个结点采用链式存储的二叉树，则该树共有(Ｄ)个指针域为空。A．2nB．2n+１Ｃ．2n+2D．n+152.以下排序算法中，在一趟排序过程中,除了其它相关操作外，只进行一次元素间的互换的算法是（Ａ)。Ａ．直接选择B．冒泡C.直接插入D．折半插入bdbdfeca图１54.对长度为n的线性表进行顺序查找,在等概率情况下，平均查找长度为（B)。A．nB．（ｎ＋1)/２C．２nD．n－155．在有序表｛1，3，8，13，3３，42,46，６３，76,７8,86,97,100｝中,用折半查找值８6时，经（D）次比较后查找成功。A.6B．3C．8D.４56.如图若从顶点a出发按深度优先搜索法进行遍历,则也许得到的顶点序列为（A)。ababecdfgB.ａｅdcbgfC．ａｃfebdgＤ.aeｃbｄgf57.有一个长度为10的有序表，按折半查找对该表进行查找,在等概率情况下查找成功的平均比较次数为（Ａ）。A.29/1０B．31／１０C．2６/10Ｄ．29/958.一棵哈夫曼树有１2个叶子结点（终端结点），该树总共有(C)个结点。A．２2B.21C.２3D.２４59.一组记录的关键字序列为（37，70，47，29，31，85）,运用快速排序,以第一个关键字为分割元素，通过一次划分后结果为（A)。A.3１,２9，37，４7，70，85B．２9，31,3７，4７,７0,８５Ｃ.31，29，37,70,47,85D.31，2９,37,85，４7,7060．队列的删除操作在(Ａ)进行。Ａ．队头B.队尾C.队头或队尾Ｄ.在任意指定位置61．（A)是性质相同的数据元素的集合,是数据的子集。A.数据对象B.数据元素C．数据结构D．数据项62．设链表中的结点是NＯDE类型的结构体变量,且有NODE*ｐ;为了申请一个新结点,并由p指向该结点，可用以下语句(D)。A．p=(NODE*)mａlloc(siｚeof（p)）;B.p＝(*NＯDE)ｍａlloｃ(sizｅof(ＮODE));C．p＝(NＯDE)ｍalloc(sｉzeof(p)）；D.p＝(NODE＊)ｍaｌｌoc(sizｅｏf(NODＥ）);63．设顺序存储的线性长度为n,要在第i个元素之前插入一个新元素，按课本的算法当i=(C）时,移动元素次数为2A．n/２B．nC．n-1C．１６4.一个栈的进栈序列是1,2,３,4，则栈的不也许的出栈序列是（D)(进出栈操作可以交替进行)A.3,2，4，1Ｂ．3,2，1,4C.４,3，2,1D.1，4，2，365．设有一个带头结点的链队列，队列中每个结点由一个数据域datａ和指针域ｎext组成,fｒｏnt和ｒｅａｒ分别为链队列的头指针和尾指针。设ｐ指向要入队的新结点(该结点已被赋值）,则入队操作为（Ａ）。A.ｒear->neｘt=p；ｒeａr＝p；Ｂ．rear－>neｘt=p;p=rｅar;Ｃ.p＝rｅａr－>nｅxt;rｅaｒ＝p;D.ｒｅar=p;reａｒ->next＝p;６6.以下说法不对的的是(D)。Ａ．顺序栈中，栈满时再进行进栈操作称为“上溢”B．顺序栈中,栈空时再作出栈栈操作称为“下溢”C.顺序队列中，队列的头指针和尾指针均超越队列存储空间的上界,则队列已空D．顺序队列中,当尾指针已经超越队列存储空间的上界，则一定是队列已满67．设有一个2０阶的对称矩阵A，采用压缩存储方式，将其下三角部分以行序为主序存储到一维数组中（矩阵A的第一个元素为a1１,数组b的下标从1开始),则矩阵元素ａ8，5在一维数组b中的下标是(D)。A.30B.28C.４0Ｄ．３36８．已知一个图的所有顶点的度数之和为m，则ｍ一定不也许是(D）。A．4B．８Ｃ．12D.９6９.以下说法对的的是（C）。A．连通图G的生成树中可以包含回路B．连通图G的生成树可以是不连通的C．连通图G的生成树一定是连通而不包含回路的D.连通图G的生成树一定是唯一的7０．对ｎ个元素进行冒泡排序，通常要进行ｎ-1趟冒泡,在第ｊ趟冒泡中共要进行（C)次元素间的比较。A.jB.j－1C．n－jＤ.n-j－171.在排序过程中，可以有效地减少一趟排序过程中元素间的比较次数的算法是(C）。Ａ.冒泡B.选择C.折半插入D．直接插入7２.一棵哈夫曼树有n个叶子结点（终端结点）,该树总共有（B）个结点。Ａ．2ｎ－2B.2n-1C.2ｎD.2n+2７3．数据的（A）结构与所使用的计算机无关。Ａ．逻辑B.物理C.存储Ｄ．逻辑与存储74．从n个数中选取最大元素（B)。A．基本操作是数据元素间的互换B．算法的时间复杂度是Ｏ(n)C.算法的时间复杂度是Ｏ(n2）D．需要进行(ｎ+1）次数据元素间的比较75．设heaｄ为非空的单向循环链表头指针，p指向链表的尾结点,则满足逻辑表达式（B)的值为真。A．p－>next=NULＬB．ｐ->ｎeｘt==heaｄＣ.p-＞nｅｘt=headＤ．p＝=NULＬ7６.设顺序存储的线性表长度为n，要删除第i个元素,按课本的算法，当i＝(C)时,移动元素的次数为3。Ａ.3B．ｎ／２C.ｎ－３Ｄ.377．一个栈的进栈序列是ａ,b，ｃ,d,则栈的不也许的出栈序列是（D）。A．ｄｃbaB.bcadC.cbadD.ａdbc78．设有一个带头结点的链队列,队列中每个结点由一个数据域daｔa和指针域next组成，fｒont和reaｒ分别为链队列的头指针和尾指针，要执行出队操作,用ｘ保存出队元素的值,p为指向结点类型的指针,可执行如下操作：ｐ=frｏｎｔ->nｅxt;x=ｐ->data；然后指行（D)。Ａ．frｏnｔ=p->neｘt;B.fｒｏnt->neｘt＝p；Ｃ．front=ｐ;D.ｆronｔ－＞ｎext=p->ｎext;79.在C语言中,存储字符串“ABCＤ”需要占用（Ｃ)字节。A.4Ｂ．2C.５D.380.设有一个10阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中。(矩阵A的第一个元素为a１，１,数组b的下标从１开始)，则矩阵元素a5,３相应一维数组b的数组元素是(C）。A.b[18]B.b[8]C．b［13]D.b[1０］８1.设有一个1５阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中。(矩阵A的第一个元素为a１,１，数组b的下标从1开始),则数组元素ｂ[13]相应A的矩阵元素是(Ａ)。A．a5,３Ｂ．a6，4Ｃ．a7,2D．ａ６，882．深度为５的完全二叉树共有２0个结点,则第5层上有(C）个结点（根所在结点为第一层)。A.３Ｂ．８C.5D.68３．已知一个图的所有顶点的度数之和为m，且ｍ是以下4中情况之一,则m只也许是（D）。A.9B.7C.1５Ｄ.884．以下说法对的的是（C)。A.连通图G的生成树中不一定包含G的所有顶点B．连通图Ｇ的生成树中一定要包含G的所有边Ｃ.连通图G一定存在生成树Ｄ．连通图Ｇ的生成树一定是唯一的85．线性表只要以(Ｃ）方式存储就能进行折半查找。Ａ.链接B．顺序Ｃ．关键字有序的顺序Ｄ．二叉树８6.对二叉排序树进行(C)遍历，遍历所得到的序列是有序序列。A．按层次B.前序C．中序Ｄ．后序87．对n个元素进行冒泡排序若某趟冒泡中只进行了(C）次元素间的互换，则表白序列已经排好序。A．1Ｂ.2Ｃ.０D.n－188.在对一组元素（64,48，106，33,25，82,70，55,９3)进行直接插入排序时，当进行到要把第7个元素７0插入到已经排好序的子表时,为找到插入位置,需进行(C）次元素间的比较(指由小到大排序)。A．6B.2C.3D.4ababecdfgA．acｅbdｇfB．aｃfedgｂC.abecdgfＤ.aｂｅｃfdg90．一棵哈夫曼树有１0个非叶子结点（非终端结点），该树总共有（A）个结点。Ａ.２1Ｂ．20C．22D.1９91．一棵哈夫曼树有1２个叶子结点(终端结点),该树总共有(C）个结点。A．21B．2２C.23D.2４92.队列的插入操作在(B)进行。A.队头B.队尾Ｃ．队头或队尾D．在任意指定位置９3.队列的删除操作在（B)进行。A.队尾B．队头C.队头或队尾D.在任意指定位置9４.链表所具有的特点是（C）。A.可以随机访问任一结点B．占用连续的存储空间C.插人删除元素的操作不需要移动元素结点Ｄ.可以通过下标对链表进行直接访问９5．线性结构中数据元素的位置之间存在(C)的关系。Ａ.一对一B．一对多C.多对多Ｄ.每一个元素都有一个直接前驱和一个直接后继9６.算法的时间复杂度与(C)有关。A.所使用的计算机Ｂ.与计算机的操作系统C.与算法自身D.与数据结构97．４.在一个单链表中，p,q分别指向表中两个相邻的结点，且ｑ所指结点是p所指结点的直接后继，现要删除ｑ所指结点，可用的语句是（)。Ａ.ｐ=q-＞rieｘtB．p->nｅxt=qC.p->next=q->nextD.q->ｎｅxt=NＵLL98.在一个链队中,假设f和r分别为队头和队尾指针，则删除一个结点的运算为(C)Ａ．ｒ=ｆ-＞nｅxt;B.r=r->neｘt;C.f=f->next;D.f=r－>next；9９.元素3,6，9按顺序依次进栈，则该栈的不也许输出序列是(B）(进栈出栈可以交替进行)Ａ.9，6,３B.９，3，６C.6，3，9Ｄ.3，9，6100．设有一个10阶的对称矩阵Ａ,采用压缩存储的方式,将其下三角部分以行序为主存储到一维数组B中（数组下标从1开始）,则矩阵中元素戊．s在一维数组B中的下标是（)A.33B.32C.8５D.4110１．排序方法中，从尚未排序序列中挑选元素，并将其依次放入已排序序列(初始为空)的一端的方法,称为(D)排序。A．归并Ｂ.插人Ｃ.快速D.选择1０2.排序算法中，从未排序序列中依次取出元素与已排序序列(初始为空)中的元素进行比较(规定比较次数尽量少),然后将其放入已排序序列的对的位置的方法是(Ｃ）。A.冒泡B.直接插入Ｃ.折半插入D．选择排序二、填空题1．通常数据的逻辑结构涉及集合、__线性__、_树形＿_、图状__四种类型。2.通常可以把一本具有不同章节的书的目录结构抽象成＿__树形_结构。3．设有一个单向链表，结点的指针域为nｅxt,头指针为head，p指向尾结点,为了使该单向链表改为单向循环链表,可用语句___ｐ－>nｅxｔ=head;_____。4．要在一个单向链表中p所指向的结点之后插入一个s所指向的新结点,若链表中结点的指针域为next，可执行_s->nｅxt＝ｐ->next;＿_＿和p－>next=ｓ；的操作。5.设有一个单向循环链表,头指针为head,链表中结点的指针域为ｎｅxt,p指向尾结点的直接前驱结点，若要删除尾结点，得到一个新的单向循环链表，可执行操作_＿p->nexｔ=heａｄ；。6．设有一个非空的链栈，栈顶指针为hs,要进行出栈操作,用x保存出栈结点的值,栈结点的指针域为nｅxt,则可执行x=hs->daｔa;＿__hｓ=ｈｓ->ｎｅxt;__。7．在一个链队中,f和r分别为队头和队尾指针,队结点的指针域为next,则插入一个ｓ所指结点的操作为__ｒ－>ｎｅxｔ=s_;ｒ=s；８．在一个不带头结点的非空链队中,f和r分别为队头和队尾指针，队结点的数据域为datａ，指针域为next,若要进行出队操作,并用变量x存放出队元素的数据值,则相关操作为x=ｆ－＞ｄata；f＝f->next;。９．循环队列的队头指针为f，队尾指针为ｒ,当＿r==f＿时表白队列为空。1０．循环队列的最大存储空间为MaxＳｉｚｅ=８,采用少用一个元素空间以有效的判断栈空或栈满，若队头指针front=４，则当队尾指针rear=_4_时，队列为空,当ｒear＝_＿２＿__时,队列有6个元素。11.稀疏矩阵存储时，采用一个由＿_行号_＿、__＿列号_、__非零元__3部分信息组成的三元组唯一拟定矩阵中的一个非零元素。12．一棵二叉树没有单分支结点,有６个叶结点，则该树总共有＿＿11_＿_个结点。１3.一棵二叉树顺序编号为6的结点(树中各结点的编号与等深度的完全二叉树中相应位置上结点的编号相同),若它存在右孩子，则右孩子的编号为__＿_13____。14.按照二叉树的递归定义，对二叉树遍历的常用算法有__先序_、＿＿中序＿、__后序__三种。15.结构中的数据元素存在多对多的关系称为___图状___结构。1６．把数据存储到计算机中,并具体体现数据之间的逻辑结构称为＿_物理(存储）_结构。１７．结构中的数据元素存在一对多的关系称为_＿_树形____＿结构。efgibaefgibachd图3gfabdgfabdec图420.二叉树为二叉排序的充足必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法是_＿___错误____＿的。(回答对的或不对的）21．在队列的顺序存储结构中,当插入一个新的队列元素时,尾指针的值增1，当删除一个元素队列时,头指针的值增1。22．根据搜索方法的不同,图的遍历有__深度优先、＿广度优先__＿两种方法。23．循环队列的引入，目的是为了克服假上溢。2４.通常可以把某城市中各公交站点间的线路图抽象成_＿__＿图状___结构。25．结构中的元素之间存在多对多的关系称为___图状__＿结构。2６．要在一个单向链表中删除p所指向的结点,已知q指向p所指结点的直接前驱结点，若链表中结点的指针域为ｎext,则可执行_＿_＿ｑ-＞nexｔ=p－＞nexｔ;__。27.设有一个单向循环链表,结点的指针域为nｅxt，头指针为ｈeａd，指针ｐ指向表中某结点,若逻辑表达式_＿_p-＞neｘt=＝ｈeaｄ;__＿＿_的结果为真，则p所指结点为尾结点。28.设有一个链栈，栈顶指针为ｈｓ,现有一个ｓ所指向的结点要入栈，则可执行操作_s->ｎext=hs;和hs=s;29．顺序存储字符串“AＢCD”需要占用__＿５__个字节。3０．循环队列的最大存储空间为MaｘSiｚe=6，采用少用一个元素空间以有效地判断栈空或栈满，若队头指针ｆroｎt=４，当队尾指针rｅar=_＿__３____时队满，队列中共有_＿__5_＿＿＿个元素。3１.一棵二叉树叶结点（终端结点）数为5,单分支结点数为2，该树共有__11____个结点32．设一棵完全二叉树,其最高层上最右边的叶结点的编号为奇数，该叶节点的双亲结点的编号为10，该完全二叉树一共有_____2１___个结点。３３．一棵二叉树中顺序编号为5的结点(树中各结点的编号与等深度的完全二叉中相应位置上结点的编号相同），若它存在左孩子,则左孩子的编号为_＿__1０_＿＿＿。3４.结构中的数据元素存在一对一的关系称为_＿线性______结构。３５．一棵有n个叶结点的二叉树，其每一个非叶结点的度数都为2,则该树共有_＿_２ｎ-１____个结点。３6.图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是__对的＿＿＿＿的。(回答对的或不对的)3７．串的两种最基本的存储方式分别是_顺序存储＿____＿和＿＿_链式存储_____。38．按某关键字对记录序列排序，若关键字关键字相等的记录的记录在排序前和排序后仍保持它们的前后关系,则排序算法是稳定的，否则是不稳定的。39.设有一个不带头结点的单向循环链表，结点的指针域为next,指针p指向尾结点，现要使p指向第一个结点,可用语句__＿__＿＿ｐ=p-＞ｎeｘt;_。40.要在一个带头结点的单向循环链表中删除头结点，得到一个新的不带头结点的单向循环链表,若结点的指针域为next,头指针为hｅad，尾指针为p，,则可执行head＝head->ｎｅｘt；＿_＿_＿p->ｎｅｘt＝heａd；___。41．在双向链表中，每个结点有两个指针域，一个指向_结点的直接后继，另一个指向__结点的直接前驱。4２.设有一个头指针为head的单向链表，p指向表中某一个结点,且有p－>ｎｅxt==ＮULL,通过操作___p－>next＝hｅad;__,就可使该单向链表构导致单向循环链表。43．循环队列的最大存储空间为MaxSiｚe，队头指针为f，队尾指针为r,当_（r＋1)%MaｘSｉｚe＝f_时表白队列已满。4４．从一个栈顶指针为h的链栈中删除一个结点时，用x保存被删结点的值,可执行ｘ=h－＞ｄａｔa；和___h=h-＞neｘt；。(结点的指针域为neｘt)4５．程序段inｔｃount＝0;cｈar＊s=”ＡＢCＤ”；whiｌｅ(*s!=’\０’){s++；couｎt+＋；}执行后ｃｏｕnt＝＿_4_。46.两个串相等的充足必要条件是_串长度相等且相应位置的字符相等。47．一棵二叉树总结点数为11,叶结点数为5，该树有__4＿_个双分支结点,__2__个单分支结点。48.对二叉树的遍历可分为__先序、中序、后序、层次四种不同的遍历顺序。４9.设一棵完全二叉树,其最高层上最右边的叶结点的编号为偶数，该叶节点的双亲结点的编号为9,该完全二叉树一共有＿_＿_18__＿_个结点。50.双向循环链表中，ｐ指向表中某结点，则通过p可以访问到ｐ所指结点的直接后继结点和直接前驱结点，这种说法是__对的___＿__的(回答对的或不对的)。51．栈和队列的操作特点分别是＿_先进后出（后进先出）_和＿_先进先出（后进后出)＿__。52.一棵有１4个结点的完全二叉树，则它的最高层上有_＿__7___个结点。efgibacefgibachd图２５4.折半查找只合用于顺序存储结构存储的有序表。55．哈希函数是记录关键字值与该记录___存储地址__＿之间所构造的相应关系。56．深度为k的二叉树最多有2k-１结点。５７．二叉树排序中任一棵子树都是二叉排序树，这种说法是__对的_＿___的。(回答对的或不对的）58.串的两种最基本的存储方式是_＿＿顺序存储_和链式存储__59．结构中的元素之间存在多对多的关系称为___＿_图状＿__结构。60.设有一个链栈,栈顶指针为ｈs,现有一个ｓ所指向的结点要入栈,则可执行操作s-＞next=hs;_hs=s;。61．循环队列的最大存储空间为MaxＳｉｚe＝6,采用少用一个元素空间以有效地判断栈空或栈满，若队头指针ｆront=４,当队尾指针rｅar＝__３__时队满，队列中共有___５__个元素。62．‘Ａ‘在存储时占＿_1_个字节。“A”在存储时占__2__个字节。6３.程序段char*ｓ=”ａBcD”；n=0;ｗhｉlｅ（＊s!=’\０’）{ｉf(*s>＝’a’＆＆*s<=’z’)n+＋;s＋+;｝执行后n=__＿2_＿_三、综合题１.（1）已知某二叉树的后序遍历序列是ｄebca,中序遍历序列是dbeａc,试画出该二叉树（2）若上述二叉树的各个结点的字符分别代表不同的整数(其中没有相等的)，并恰好使该树成为一棵二叉排序树,试给出a、b、c、d、ｅ的大小关系ababced答:(１)（２）d<ｂ<ｅ<a＜c(３）abdec２．（1)设ｈead１和ｐ１分别是不带头结点的单向链表A的头指针和尾指针，ｈeａd2和p2分别是不带头结点的单向链表B的头指针和尾指针,若要把B链表接到A链表之后,得到一个以head1为头指针的单向循环链表,写出其中两个关键的赋值语句（不用完整程序,结点的链域为next)。（2）单向链表的链域为nｅxt,设指针ｐ指向单向链表中的某个结点，指针s指向一个要插入链表的新结点,现要把s所指结点插入p所指结点之后，某学生采用以下语句:p-＞ｎext＝ｓ;s-＞next=p-＞next；这样做对的吗?若对的则回答对的，若不对的则说明应如何改写答：（1）p１-＞neｘt＝heａｄ2；ｐ2->ｎeｘt=head１;(2)不对，s-＞ｎeｘt＝p-＞next；ｐ-＞next＝s;３.(1）设有一个整数序列｛40,28,6,72,1０0,3,５４｝依次取出序列中的数,构造一棵二叉排序树40284028723100546答:（1)（2）ASL=（1x1+２x2＋3x3+4)/７=18／74.（１）画出对长度为10的有序表进行折半查找的鉴定树（以序号1，2,……10表达树结点)（2）对上述序列进行折半查找，求等概率条件下，成功查找的平均查找长度528452849631071（２)AＳL=(1x１+2ｘ2+3x4＋4x3）/１0=29/１05．（1)运用筛选过程把序列{42,82，６7,10２，16,3２，５7,5２}建成堆（小根堆)，画出相应的完全二叉树（不规定中间过程）（2）写出对上述堆相应的完全二叉树进行中序遍历得到的序列16423252571642325257678210242826752573216102初始树堆初始树堆（2）10２，5２，42,８２,16，67，32,５76．（1）运用筛选法,把序列｛37,77,６２，97,1１，2７，５２，47}建成堆（小根堆）,画出相应的完全二叉树（2）写出对上述堆所相应的二叉树进行前序遍历得到的序列初始树堆答:（1）初始树堆373777624752271197(2）11，３7,4７,97,７7,27,6２，5２7．(1）一组记录的关键字序列为{４5,40,65，４３,３５,9５}写出运用快速排序的方法,以第一个记录为基准得到的一趟划分的结果(规定给出一趟划分中每次扫描和互换的结果)（2）同样对序列{４5,40，65,4３,3５,95}运用直接插入排序，写出逐次插入过程(从第一个元素一直到第六个元素)。答：（1)４5４0６5４３35９5(2）4０４565433595３５4０6５４3３５9５404345６53５９５35４0654365953５404３４565953５404343659５8．设有一个不带头结点的单向链表,头指针为heaｄ,结点类型为NODＥ，每个结点包含一个数据域data和一个指针域nｅxt，该链表有两个结点，p指向第二个结点（尾结点),按以下规定写出相应语句(不规定完整程序，(1)、（2)、(3)、(4）是一个连续的过程）。(１)新开辟一个结点,使指针s指向该结点，结点的数据成员data赋值为1(２）把该结点插入链表的尾部,释放指针ｓ的指向(3)删除链表的第一个结点（4)已知p1指向另一个新结点,把它插入到p所指结点和尾结点之间答:(1)ｓ＝(NＯDE*)malloc(siｚeof(NODＥ)）;ｓ->data＝1；（2)p->neｘt=s;s－>nｅxｔ=ＮULL；free（s)(3)hｅａd=hｅad-＞neｘｔ；（4）p1->ｎeｘｔ=ｐ->neｘt；113727475211372747526277979.(1)运用筛选过程把序列｛4２，82,６7,102,16，3２,57，5２}建成堆(小根堆),画出相应的完全二叉树（不规定中间过程）（2)写出对上述堆相应的完全二叉树进行中序遍历得到的序列答：（1）16421642325257678210242826752573216102初始树初始树堆(２）１02,52，42，82,１6,６7,3２，5７1０.(1）设有序列{10，12，15,19,２2,2５,100，130,150，200｝画出对上述序列进行折半查找的鉴定树(以序列中的元素作为树的结点）2212221213019150251520010010答:（1）（2)4次;3次1１.(1）设有一个整数序列{５0,38,16,82，11０，１3，６4},依次取出序列中的数,构造一棵二叉排序树（2）运用上述二叉排序树,为了查找110，经多少次元素间的比较能成功查到，为了查找15,经多少次元素间的比较可知道查找失败。答:5038503882131106416(2）三次;四次１2.(1)设有查找表{5，14,2,6,1８,7,4,16,３},依次取表中数据，构造一棵二叉排序树。24246167318514答：(1)（２)中序遍历:中序2,3，4，5,6，7，1４,1６,1813.（１）已知某二叉树的先序遍历序列是aeｃdb，中序遍历序列是eaｄcｂ,试画出该二叉树(2）给出上述二叉树的后序遍历序列(3）若上述二叉树的各个结点的字符分别是1,2，3，4，５,并恰好使该树成为一棵二叉排序树,试问a、ｂ、c、d、e的值各为多少？aecbaecbd（2)edbca（3）e=1,a＝2,d＝3,c=4，ｂ＝514.(1)设有一个整数序列｛40，2８,6,7２,100，３，５4｝依次取出序列中的数，构造一棵二叉排序树(2)对上述二叉排序树,在等概率条件下,求成功查找的平均查找长度答:(１）404028723100546（2)AＳL=（1x１+2x2+３x3+4)/７=18/71５.(1）给定数列{8,17，５,９,２１,10，７，19,6}，依次取序列中的数构造一棵二叉排序树(2）对上述二叉树给出中序遍历得到的序列851768517621971910（2)5，６，7,8，9,10，17,１8,19，211６．(1）运用筛选过程把序列{42,8２，67,１02，1６,32,57，52}建成堆(小根堆），画出相应的完全二叉树（不规定中间过程)(２）写出对上述堆相应的完全二叉树进行中序遍历得到的序列1642164232525767821024282675242826752573216102初始树堆初始树堆（2）10２,５２,42,82，16，67,３2，5７17．（1）以给定权重值１，2，12,13，20,2５为叶结点，建立一棵哈夫曼树(２)若哈夫曼树有n个非叶子结点,则树中共有多少结点。对给定的一组权重值建立的棵哈夫曼树是否一定唯一答：（1)28284513213573209131525012321（2)2ｎ-1不一定唯一四、程序填空题１．以下函数在a［0]到a［ｎ-1]中,用折半查找算法查找关键字等于k的记录,查找成功返回该记录的下标,失败时返回-１,完毕程序中的空格ｔypｅdefstrｕct{intkｅy；……}ＮOＤE;ｉｎｔBinary_Ｓearch(NODEa[]，intn，iｎtk)｛intｌｏw,mid,hiｇｈ;low=0；high=n-1;whｉｌe(__＿low<=hiｇｈ_＿＿__）{mｉd=(lｏｗ+high)/２；if(a[ｍid].keｙ==k)rｅtuｒｎ__ｍｉd)＿_____; elsｅif（_＿_a[mid].keｙ<k；＿____)low=ｍid+1; eｌse_＿high＝mid-1___；ﻩ｝＿_＿returｎ-１____； }2．以下函数为直接选择排序算法,对a[1],a[２],…a[n]中的记录进行直接选择排序，完毕程序中的空格tｙpｅdefstｒuｃt{ｉntkeｙ；……}NODE;vｏiｄseｌsoｒt（NODEa［],intn)｛ﻩｉnｔi,j，k;ﻩNODEtｅｍp；ﻩfｏr(ｉ=１;i＜=_＿n-１__;i++)ﻩ{ﻩ k＝i；ﻩﻩｆor(ｊ=i+1;j<＝＿__ｎ＿_＿__;ｊ++)ﻩﻩﻩif(a[j].ｋｅy<ａ［ｋ]．