数据结构考题

单元练习1数据有逻辑结构和（储存结构）两种结构。数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构线性结构中的元素之间存在一对一的关系。树形结构中的元素之间存在一对多的关系。图形结构中的元素之间存在多对多的关系。数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为顺序储存结构链式存储的存储结构所占空间分为两部分，一部分存放结点的值，另一部分存表示结点间的关系指针单元练习2顺序表相对于链表的优先的是：节省存储和随机存储。链表相对于顺序表的优点的是：插入、删除方便。当线性表的元素总数基本稳定，且很少进行插入、删除操作，但要求以最快速度存取表中元素时，应采取竝存储结构。在一个长度为n的顺序表中删除第i个元素，要移动n-i个元素。在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移动n-i+l个元素。线性表的元素总数不确定，且经常需要进行插入和删除操作，应采用链式存储结构。t20j-I：如图M小的链我小'笫杵指计P所用的沽，■：之||I插入数山域仇为-和h的网平结点.剛可用下列两个语旬：和P->next=S;来冥观谏操一411一411卜和I--iS已知一个顺序表的线性表，设每个节点占m个存储单位，若第一个节点的地址为B,则第i个节点的地址为B+(i-l)*m两个指针P和Q,分别指向单向链表的两个元素，P所指的元素是Q所指的元素的前驱的条件是p->fromt==Lt.己知践性表中的元盍星无序的.井-凶带表头结点的单涨发作存储m试写一尊法，删除注中所有大T-mm，小的兀盘，试完成下列程用坦空口X^iii-d-elele1llilislhead;dnCalyptini»nnitij.jcJ[q-hea^l->juext;while(pMSOJLL)[if«fh->da[2j<=tiiin卜11 4 |7山3=口口、p[时;»ih?xi:]eljie{q->tiexi=n->anixi.dCHicf]>j;]j=q->HKXI:]单元练习3在线性结构中，允许插入、删除的一端称为栈顶在顺序表中，当栈顶指针top=-1时，表示栈空如进栈的次序的A、B、C、D、E,执行3次出栈操作后，栈顶元素为B4个元素按A、B、C、D顺序进S栈，执行两次Pop(S,x)运算后，x的值是C插入和删除操作只能在一端进行的相形表，称为栈设有编号为1,2,3,4的四辆列车，顺序进入一个栈结构的站台，不可能的出站顺序是1423经过下列栈的运算后(InitStack(s);Push(s,a);Pop(s);),在执行ReadTop(s)的值是a写出运方下列程序段的输出结果voidntainOIS;cJiaLk,y；hiitStackfS). //初始化找k-nc严叫"；Push瞎x):PiiishCS「H巧；Push时型:卩op^S,j):PusbCS,"-"):Vtj.wh祐，k)；PapfS.k>：Pueli洛Ts:(tSEniiilyfS)){lJupfS,y):tdut«^;}；cout<<.x;答:屯tack■单元练习4在队列中存取数据应遵循的原则是先进先出队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。在队列中，允许插入的一端称为队尾在队列中，允许删除的一端称为队首队列在进行出队操作时，首先要判断队列是否为空解决顺序队列“假溢出”的方法是循环队列循环队列的队首指针为front，队尾指针为rear，则队空的条件是front==rear队列Q经过下列运算：InitQueue(Q);InQueue(Q,a);InQueue(Q,b);QutQueue(Q,x);ReadFront(Q,x);QFmpty;后的值是(0)。队列Q经过InitQueue(Q);InQueue(Q,a);InQueue(Q,b);QutQueue(Q,x);ReadFront(Q,x);后，x的值是a队列是限定在端点进行操作的线性表。如进队的序列为A、B、C、D,则出队额序列是ABCD4个元素按A、B、C、D顺序连续进队Q,则队尾元素是D4个元素按A、B、C、D顺序连续进队Q,执行一次OutQueue(Q)操作后，对头元素是B四个元素按A、B、C、D顺序连续进队Q,执行四次OutQueue(Q)操作后，在执行QEmpty(Q);后的值是1队列Q,经过下列运算后(InitQueue(Q);InQueue(Q，a);InQueue(Q，b)InQueue(Q，x;);ReadFront(Q,x);)，x的值是bo循环队列SQ队满的条件端点(SQ->rear+l)%MAXLEN==SQ->front若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0,当从列队中删除一个元素后,再加入两个元素后,fronth和rear的值分别为4和2单元练习7在树中，一个结点所拥有的子树成为该结点的度度为零的结点称为叶子结点。树中结点的最大层次称为树的深度对于二叉树来说，第i层上至多有2i-1个结点。深度为h的二叉树至多有2h-l个结点。有20个结点的完全二叉树，编号为10的结点的父结点的编号是5已知完全二叉树的第8层有8个结点，则其页结点树是68由树转换成二叉树时，其根节点无有子树三个结点可以组成2种不同形态树。将一颗完全二叉树按层次编号,对于任意一个编号为i的结点,其左孩子结点的编号为2iAEF119)跆定如下圏所示的二AEF119)跆定如下圏所示的二XR.:K］汎字城肪垮列为：玄BEFHCG「根据二叉树的定义，具有3个结点的二叉树有5种树形o下列4操树中■IB)£礎宪全二夏関.A.B.CxC,E.K下列4操树中■IB)£礎宪全二夏関.A.B.CxC,E.K仃、H、IA.B.D,II、T-E.<2、F,GC-卜I、D»]-2、E、A，F、C\GD-H--1-<0、Fj--R■■F-.G-hC-.ABC门HAHDFHCFGD.^HCTJRFGII门仍对丁下边的二咒其中序序列为A.DBEiHAFCU B.DBEIFAFCG把一颗树转化为二叉树后，这颗二叉树的形态是唯一的将一颗有100个结点的完全二叉树从上到下，从左到右一次编号，根节点额编号为1，则编号为45的结点的有孩子编号为9^

oo4,分别匮出具有3oo4,分别匮出具有3个箱点前胡和三伞结点的二叉轉的所有不同形东.•:J三个姑点的枸⑵三个皓点的二夏树树人/OA2C©E6ORrLOA2C©E6ORrL把下列=般树转换为二彌(\)A13BHE©5.A13BHE©5.杷-卜列淼林转换为二叉摘AEGCEDHFe,杷下列AEGCEDHFe,杷下列二叉树加IS为栽林K：还厢后的二戛树沟二\8□9355<j)\77.某二夏树的錯点数据黑用顺M存「酉其结羁如下:⑴再出该_叉树〔3分）（即岗出按层次垢出的箱点序列t2^>⑴层找適历的踣点序列：EAFDHCGIB试訓出柑问的呛大鮭初井计训人潸权坷壮也*T1-C2flS)*2t-((j>7^)*a^l>a')*l15313.绪定一亍祝•琨W=M^生入8i:.^WPL,■fi.12.阖F!AF1)11CG1L(J单元练习8A.rhr,8.[1.11A<1&I).掀厂胆沉光迸行遍也,MlnJ'fllifi?fi;的种顶恵r?列为A.rhr,8.[1.11A<1&I).掀厂胆沉光迸行遍也,MlnJ'fllifi?fi;的种顶恵r?列为d.f.cJ".Cih〔D汇.d1\t.b；E七下图氏猖从顶点"岀疑；⑷如下图所示，从顶点&出易1心紀疋优论辿f」迪!乩副可能爲剋的一种1S点序列为hic.Cid.单元练习9静态查找表所含元素个数在查找阶段是固定不变的。在关键字序列(7,10,12,18,28,36,45,92)中，用二分查找法查找关键字92要比较4次才找到。散列表的查找效率主要取决于散列表造表时选取的散列函数和处理(冲突)的方法。设散列函数H和减值kl,k2,若klHk2，而H(kl)=H(k2),则这种情况为冲突散列表查找法德平均查找长度与元素个数n无关。查找表是以集合为查找结构的。对线性表进行二分查找时，要求线性表必须依顺序方式存储，且结点按关键字有序排序衡量查找算法效率的主要目标是平均查找长度一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时，4次比较查找成功。有一个长度为12的有序表，按二分查找法对其惊醒查找，在表内各元素等概率情况下查找成功所需的平均比较次数为37/12设哈希表长m=14，哈希函数H(key)=key%11o表中有4个结点：Addr(15)=4Addr(38)=5Addr(61)=6Addr(84)=7其余为空。如果用二次探测在散列处理冲突，关键字为49的结点地址是9对于包含n个元素的散列表进行查找，平