《数据结构》期末考试试题及答案《数据结构》期末考试试题及答案(２００3－2004学年第2学期）单项选择题１、Ｃ10、C1.对于一个算法,当输入非法数据时，也要能作出相应的处理,这种要求称为（（Ａ)、有序顺序表（B)、有序单链表（C）、有序顺序表和有序单链表都可以（D)、无限制４．顺序存储结构的优势是（（Ａ)、利于插入操作(B）、利于删除操作（C)、利于顺序访问（Ｄ）、利于随机访问５。深度为k的完全二叉树,其叶子结点必在第（6。具有６0个结点的二叉树，其叶子结点有12个,则度过１的结点数(Ａ)、１1（Ｂ）、１3（C)、4８（D）、３7７.图的Ｄepｔh—ＦirｓｔＳearch(DFS）遍历思想实际上是二叉树8.在下列链队列Ｑ中,元素a出队的操作序列为（ab（Ａ)、ｐ＝Q。ｆｒont-＞nｅxｔ;p—>next＝Ｑ。frｏnｔ—＞nｅｘt；(B)、p=Q．front—>neｘｔ；Q.fｒｏnt-〉ｎeｘt=ｐ—〉next;(C）、p＝Q.rear->ｎｅxt；p—>next=Q。rear—＞neｘt；(D)、p＝Q—〉nｅxt；Q—＞ｎｅxt=p->ｎｅxt;《数据结构》期末考试试题及答案Huffｍaｎ树的带权路径长度WPL等于((A)、除根结点之外的所有结点权值之和(Ｂ）、所有结点权值之(Ｃ）、各叶子结点的带权路径长度之和（D)、根结点的值10。
线索二叉链表是利用()域存储后继结点的地址。（A）、（B)、dａtａ(C）、rchｉ二、填空题逻辑结构决定了算法的设计，而存储结构决定了算法的实栈和队列都是一种特殊的线性表，栈的插入和删除只能在栈顶进行.线性表（ａ1,a2,…，an)的顺序存储结构中，设每个单元的长度为L，元素ａｉ的存储地址ＬOＣ（ai）为已知一双向链表如下（指针域名为ｎext和pｒioｒ):现将p所指的结点插入到ｘ和y结点之间，其操作步骤为：;个结点的生成树的边数为．6.已知一有向无环图如下：任意写出二种拓扑排序序列：、。７.已知二叉树的中序遍历序列为BCA,后序遍历序列为CBA，则该二叉树的先序遍历序列为数据结构考试题库 《数据结构》期末考试试题及答案，层序遍历序列为。三、应用题13，设关键字系列为｛２2，1２，２４，6，45，7数据结构考试题库，8，13,2１｝数据结构考试题库，要求用线性探测法处理冲突.（6写出A－B压缩存储的三元组表。(５分）已知一维数组中的数据为（18,12，2５,５3，18)，试写出插入排序（升序)过程。并指出具有个元素的插入排序的时间复杂度是多少？(５分)开始的最小生成树。（8分,要有过程）（１)求从顶点Ａ开始的最小生成树．（２）分别画出以Ａ为起点的DFS生成树和BFＳ生成树。
６。已知数据六个字母及在通信中出现频率如下表:0。１50.10．1０.３把这些字母和频率作为叶子结点及权值，完成如下工作（7分,要有过已知有如下的有向网：求顶点Ａ到其它各顶点的最短路径(采用ｒａ算法,要有过设计题(30分，每题1０分，用Ｃ语言写出算法,做在答题纸上)已知线性表（a1，a2，…,an)以顺序存储结构为存储结构，其类型定义如下:＃ｄｅfinｅLISＴ＿INＩT＿SＩZE1０0//顺序表初始分配容量tｙpedefｓtｒucｔＥlｅmtｙpｅeｌｅｍ;//顺序存储空间基址ｉntleｎgｔh;/／当前长度（存储元素个数）｝ＳｑLiｓt；设计一个算法，删除其元素值为ｘ的结点(假若x是唯一的).并求出其算法的平均时间复杂度。其算法函数头部如下:StatｕsLｉstＤelｅｔｅ（Ｓqlisｔ&L，Ｅleｍｔｙpe2.设顺序栈如左图所示。其中结点定义如下：ｏptypeｄｅfsｔruｃｔElemｔyｐebase；／/栈底指针Ｅlｅmｔyｐｅtｏp；//栈顶指针｝Stack；设计算法，将栈顶元素出栈并存入ｅ中.ｂasｅ3.设二叉链树的类型定义如下：typedｅfｉntEｌeｍｔyｐe;tyｐedefsｔｒuctnoｄe｛Eｌeｍtｙpｅdata；ｓtｒ＊lchiｌｄ,ｒｃｈild；}BｉnNode,＊BiｎＴｒｅｅ；试写出求该二叉树叶子结点数的算法:StａｔｕＬｅavｅｓ（ＢｉnTree&root,ｉｎta2a1《数据结构》期末考试试题及答案答案:选择题(每题１分)１0、C一、填空题1．设计、实现2．特殊、栈顶3．LOC（a1）＋（i—１）＊L4．p—＞next=q－〉nｅｘt；q－>ｎｅｘｔ-〉pｒiｏｒ=p；6．ＡＤCBＦＥG、ABCDＥFＦG7．ABC、ＡBＣ二、应用题1011关键安1312探测次(2)查找成功的平均查找长度:(１分)（５１+1＊２＋23+１＊７）/９=20/９查找不成功的平均查找长度:（1(2＋1+９+８+7+6＋5＋４+３+2+１)/１3=２（1）、构造（３分）（2）、1０１415１２５6(４2210１5２0５621《数据结构》期末考试试题及答案初始关键字:[18］１２255３１8趟：[12１8]2553１8趟：[1218２5］５3１８趟:[1２１8２553］18２5５３］（2）WＰＬ=0。
1＊3+0。13+0。22+0.+0。1５*3＋0３＊2１＝（3)A:010B:0１1C：1１0D：111Ｅ:00F；10１、(1０分）ＳｔaｔusＬｉstDeｌｅte（Sqｌｉst＆L，ＥleｍTyｐｅif(L-〉elｅｍ［i］==ｘ)breaｋ;ｉｆ(i＝L-〉ｌengｔh）retｕＲ;L-〉ｅlｅｍ［j]＝Ｌ-＞eｌeｍ[j+1];L—>lｅngth-－；设元素个数记为ｎ,则平均时间复杂度为：２（１０分）ｖoiｄpｏｐ(Staｃk＆S，Elｅｍtypｅｉｆ（S。ｔｏp＝＝Ｓ。bａsｅ）ｒeｔurｎＥＲROＲ；《数据结构》期末考试试题及答案S。top-—；e=＊ｓ。toｐ；ｖoｉdＣounｔLｅavｅｓ（ＢinTreｅT,ｉnｔｉｆ((!（T－>lｃｈiｌｄ)＆＆！（Ｔ-＞rcｈiｌd））ＣounｔLeａves（T—〉lcｈild，ｎ）；CｏｕntLeaｖｅs（T-＞rchiｌd，ｎ)；