资源描述
18.（10分）已知一个长度为12的表为（Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec）1）试将表中元素依次插入到一棵初始为空的二叉排序树（字符串之间按字典顺序比较大小）。画出该二叉排序树，并求出等概率情况下查找成功的平均查找长度。 设哈希表度为13 哈希函数 H （k）=边，其中 i为关键字k 中第一个字母在字母表中的序号 （例如A和D的序号分别为1和4）,用链地址法解决冲突,请画出通过依次插表中元素所构造的散列表并 求出在等概率情况下查找成功的平均查找长度。20.（8分）若对序列（25， 19， 7， 41， 29， 12， 23， 26）按升序排序，请分别给出（1）步长为4的一趟希尔排序的结果；（ 2）初始大根堆。22. （6分）函数f22定义如下，其中函数调用Insert（L, i,在顺序表L的第i位置插入k。voidf22(SqList &L, int i) if (i 0) f22(L, i-1);for (int k=1; knext;L-next =;while ( p ) LinkList s _=;p-next = L-next;L-next =p = s;24.（6分） s是一个升序静态査找表请简要说明函数调用f24（s, 1,s.length 的意）义。int f24(SSTable s, int low, int high, KeyType k) if (lowhigh) return 0; int mid=(low+high)/2;if (k=s.elemmid.key) return mid;25if (ks.elemmid.key) return f24(s,mid+1,high,k); else return f24(s,low,mid-1,k);（6分）请对以下函数填空 实现求二叉树T中各结点的子孙总数并填结点的DescNU域中的算法int f25(BiTree T) if () return -1;else T-DescNum= f25(T-lchild) +return T-DescNum;26（6分）图的邻接矩阵表示和算法f26描述如下:#define MaxNu5mtypedef struct char vexsMaxNum; int arcsMaxNumMaxNum; intn,e; MGraph;int f26(MGraph G, int i) int d=0;for (int j=0; j 0) f22(L, i-1);foHinrtJCMl、X*人Mi、Jc+iHnseHtF i、10;(1) Law” 6C2) LH ( 1、2, 3, 2, L 1 )23(6迸鐸23 Hnt sisovoid 23pinkllisb GLLinkLisrtp M Llvnexrt、Llvn(Dxt: NULL ;whil(DpLinkLisrts M plvnexlrt“plvnex什 H Llvnex什Llvn(DxrtM 0p H s；24(6进蠶 E24(s1、m. lengthin 什H)24(SSTable s、in 什 low、incthigh、KeyType 幵+ifHowhighNtDrtuHn 0;inrtmidHHow+high、2、iH)(THS elg【艮drIcesHe 什um mid;if (levs-。一纟【midlceY)Hetum 24s、mid+l、high、10 ;elseHe 什umH)24How、midll、5:;inbH)25 (BiTHtDe T 亠if ( )Hertum 1、 else TVDescNUIP 25Alvlchilft25TIVINchildHectum TVDescNum、(6)MaxNim 5typedeHJstruct char vexsMaxNum;int arcsMaxNumMaxNum; int n,e; MGraph;int f26(MGraph G, int i) int d=0;for (int j=0; jnext;while ( p ) / p指向当前被考察的结点q = p;while (q-next/ 考察 q所指后继结点 if (q-next-data != p-data) q = q-next;else /修改指针并释放结点空间 s=q-next;q-next=s-nextf;ree(s); p = p-next;/ while p/purge1. (10分)己知有向图G定义如下：G=(V，E)V=a,b,c,d,e,fE=,(1) 画出图G。(2) 画出图G的邻接矩阵011100000000010010000010000000000110写出G的全部拓扑有序序列。afcbdeafcdbeafcdebafdcbeafdcebfacbdefacdbefacdebfadcbefadcebacbfdeacfbdeacfdbeacfdeb4. （10分）设哈希函数为H （key） =ky MOD 1用线性探测再散列的方法处理冲突。请画出依次插入元素29 15 48 47，23，41，73，37后，该哈希表的状态，并在各元素下面标出其冲突次数。+-&U4-(d)poq百=4 -PONo= q一a)HJDN3I 左 (GODeHJD 也tiIs s (OOD .1 (ooz) MW艇o6pn00L9pjzs寸cn号zHo(OODTrIf-二H2曹国)缶理也snss(GOD Zwo EIrp.1宀)SMH0最占- TspdlnN占巾唱)J!KlpsJlwos诊 SB-ILBMgg SI43So i -1HyQPONMOUU.I+-)dMOU二pdMOU *QPON一(畐二 EodApmoIH PSUOOJH E*OPONe観塔一兰一 P)OAOlltlKn(oQe曲 ii ,131葺活iwl-=rM熒 jgD TV+Z0汗nN也 qmA7ISTInNHHt?noo (SMKUIHlpBsiouqM -(二E*z.s)qsnd (+二9二04)104二 91 YIOOLnd丄巴-(X .s)qsnd-(s) dod*z+ (s) doduxpul-(寸.s)qsnd-(“ .s)qsnd-(s)舟PSUIGs 3SS 即 POA .1 、二w二 VW二on.丄 I+qg-n 0( = h上 1+二T 二+qMHA 二弁)Jo 31 搜董W 二田 H Eq uis 凶卷旺VW1唔UWE(宣.且 JAoaJI 書 _ _ &畠+M H8HI oHq mHJ藝=m.Ho-n 二+ BMuqnHP JOJ -CI2 & 二JCg色USUJa ROAnnsw (OOD zo UJrQoJ負) =(o e =(o 寸) n =vmqJAHyJJSseoJu (PFq?HJJSseuJu 酉ON Mou H H一 OslocerrMemory allocation failare!next=NULL;if (HL=NULL)HL=;elseLNode* P=HL;While (P-next!=NULL) p-next=newptr;二、编写算法（共8 分）编写从类型为List的线性表L中将第i个元素删除的算法（假定不需要对i的值进亍有效性检查也不用判别L 是否为空表。）void Deelte（List& L, nit ）i一、阅读算法（每题7分，共14分）1. 30 24 16 10 2 102. 该函数的功I提：统计出BT所指向的二叉树的结点总数和叶子总数二、算法填空（共8分，每一空2 分）newptr=NULL newptr-=dat newptr p=p-netx三、编写算法（8分）void Dele te（Lis t& L, int i）for（int j=i-1;jinlk；h-ilk= NT HL ；或者 0 ； （2分） whie（p!NULL） s=p；p=p-inlk；s-ink=h-lk; （2 分） h-ilnk=s； 什么是表头吉点？ （2分）如果该链表无表头吉点贝嘛程序该做怎样的修改？ （4 分）2、（13分）对以下函数填空实现以带头结点的单链表h为存储结构的直接选择H序。单链表的结 点吉构定义为typeedfstructnodeint key; s tructnode *nex;tJD;vodi zxjzpx（JD *）h JD *p，*q，*m; int x;p=h-netx; whlie（p!=NULL） q=p-next;m=p; while（q!=NULL） if （m-key-qkey）_ （_;2分） （_;2分） if （p!=m） x=p-key;p-key=m-eky;m-key=x; （_2;分） 直接选择排序属于稳_定（ /不稳定）排序。（2分）该排序算法总的键值比较次数为。_（_2分）并分析十么情况下有最小移动记录次数?什么情况下有最大移动记录次数?算却W均时间复杂度为多 少？（3分）3、（13分）对以下函数填空实现以带头结点的单链表h为存储结构的直接选择H序。单链表的吉 点结构定义为typeedfstructnodeint key;s tructnode *nex;tJD;vodi zxjzpx（JD *）h JD *p,*q,*m;int x;p=h-netx;whlie（p!=NULL） q=p-next;m=p;while（q!=NULL） if （m- key-qkey）_ （_;2分）（_;2 分）if （p!=m） x=p-key;p-key=m-eky;m-key=x; （_2;分） 直接选择排序属于稳_定（ /不稳定）排序。 （2分）该排序算却总的键值比较次数为。_ （_2分）并分析十么情况下有最小移动记录次数?什么情况下有最大移动记录次数?算却的平均时间复杂度为多 少? （3 分）1、struotode *bk（2分）NULL；或者 0 ； （2 分）s-ink=h-lk： （2 分）什么是表结点？答:表头结点是有时为了操作方便而在链表勺第一结点之前添加的一个结点,该结点结构与表中结点相同, 但数据域还存放表中数据，或者闲置不用，或者存放特殊信息。表头结点的链域存放指向链表中第一个结(oz) /(。1)。(O E律g4MM(OD (qsE 更总殳建fe.1 fim.omfefim(oz) SM(oz)虫那dud(oz) M7LHL(宙)K- (ODE (。1)三百As/s )4cmN丄 d)4qM(ODTmNHq(OI) qud 耳* upo舀)(q* ponmjuau 3(。舎o哑令.0 4 on(v.4tqvA2pvA2qvApwAaAq.evHtt3.poqGHM.(B) =9口首(08) /32/A-.7 二 z .N G v kinuB- (091 曲薫 9CH* mrrw 咅更工 o mrr#* o 0 T-.4rg olilinit 魯畐) n Iwltf 1T1M ,ims (OOD Z su (09)，14d, -5Z) TR 7_z- TumETTOb要求：(1)画出图G （2 分）(2)给出图G的邻接矩车；（2分）(3)给出图G的邻接表（2 分）(4)给出图G的一种拓扑序列。（2分）、应用题：1、 （4 分，画对根结点1 分，左子树正确1.5分，右子树正确1.5分）I后序序列为：DCJHEBKIFCA （2分）2、前序序列补充完整为： ABCDEFGH（1 分）中序序列补充完整为： CBDEAGHF（1 分）后序序列补充完整为： CEDBHGFA（1 分）3分，画对根结点1分，左子树正确1分，右子树正确1分）3、 （4 分，画对各树根结点2 分，画对各子树子女结点2分）ABDCMS厂、EG&KH八I丿该森林的先序序列为：ABCMNSDEFHKIJ （2 分）4分）画对各结点线索指针得2分，标志位正确得1分，表头结点正确得4、 （1）（2分,如果画的是无向图不給分）2）（2分，上小题答错的学生，如果这里给出的答案符合他自己所画的图，给全分）01110001010000100101000003）（2分，第1小题答错的学生，如果这里给出的答案符合他自己画的图，给全分） 可能的拓扌K排序为：abde或adbe （2分）
展开阅读全文