DS考试大题集锦.pdf

《DS考试大题集锦.pdf》由会员分享，可在线阅读，更多相关《DS考试大题集锦.pdf（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、 三.解答题（共38分）17（5分）请直 接 在以 下 二叉 树中 添 加后 序线 索。18.（10分）已知 一 个长 度 为12的 表为 （Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec）（1）试将 表中 元 素依 次插 入 到一 棵初 始 为空 的 二叉 排序 树（字 符串 之 间按 字 典顺 序比 较 大小）。画出 该 二叉 排序树，并 求 出等 概率 情 况下 查找 成 功的 平 均查 找长 度。（2）设哈 希表 长 度为13，哈 希函 数H（k）=i/2，其 中i为关 键 字k中 第一 个 字母 在字 母 表中 的序 号（例 如A和

2、D的 序号 分 别为1和4），用 链地 址 法解 决 冲突。请 画出 通 过依 次插 入 表中 元素 所 构造 的 散列 表，并求出 在等 概 率情 况下 查 找成 功的 平 均查 找 长度。20.（8分）若 对 序列（25，19，7，41，29，12，23，26）按 升序 排 序，请分 别 给出 （1）步长 为4的 一趟 希尔 排 序的 结 果；（2）初始 大根 堆。22（6 分）函数f22定 义如 下，其 中函 数调 用Insert(L,i,k)在顺序 表L的第i位置 插 入k。void f22(SqList&L,int i)if(i 0)f22(L,i-1);for(int k=1;kn

3、ext;L-next=;while(p)LinkList s=;ECBDKAFG p-next=L-next;L-next=;p=s;24.（6 分）s是一 个升 序静 态 查找 表，请 简要 说明 函 数调 用f24(s,1,s.length,k)的意义。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;if(ks.elemmid.key)return f24(s,mid+1,high,k);else retur

4、n f24(s,low,mid-1,k);25（6 分）请对 以 下函 数填 空，实 现求 二 叉树T中 各结 点的 子 孙总 数，并 填入 结 点的DescNum域中 的算 法。int f25(BiTree T)if()return-1;else T-DescNum =f25(T-lchild)+;return T-DescNum;26（6 分）图的 邻 接矩 阵表 示 和算 法f26描述 如下：#define MaxNum 5 typedef struct char vexsMaxNum;int arcsMaxNumMaxNum;int n,e;MGraph;int f26(MGraph

5、G,int i)int d=0;for(int j=0;j 0)f22(L,i-1);ECBDKS AS FJan Feb Mar Apr June May July Aug Sep Oct Nov Dec 成功的平均查找长度42/12 成功的平均查找长度18/12 for(int k=1;knext;L-next=NULL ;while(p)LinkList s=p-next ;p-next=L-next;L-next=p ;p=s;24.（6分）s是 一个 升 序静 态查 找 表，请简 要 说明 函数 调 用f24(s,1,s.length,k)的意义。int f24(SSTable s,

6、int low,int high,KeyType k)if(lowhigh)return 0;int mid=(low+high)/2;if(k=s.elemmid.key)return mid;if(ks.elemmid.key)return f24(s,mid+1,high,k);else return f24(s,low,mid-1,k);答：在s中递 归折 半 查找k。25（6分）请对 以 下函 数 填空，实 现 求二 叉 树T中各结 点 的子 孙总 数，并 填入 结 点的DescNum域中 的 算法。int f25(BiTree T)if(!T )return-1;else T-De

7、scNum =f25(T-lchild)+f25(T-rchild)+2 ;return T-DescNum;26（6分）图的 邻 接矩 阵 表示 和算 法f26描述 如下：#define MaxNum 5 typedef struct 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

8、)q=q-next;else/修改指针 并 释放 结点 空 间 s=q-next;q-next=s-next;free(s);p=p-next;/while p/purge 1（10分）己知 有向 图G 定义 如下：G=（V，E）V=a,b,c,d,e,f E=,(1)画 出图G。（2）画出 图G 的邻 接矩阵。011000000000010000010010000000001110 （3）写出G 的全部 拓扑有 序序列。afcbde afcdbe afcdeb afdcbe afdceb facbde facdbe facdeb fadcbe fadceb acbfde acfbde acf

9、dbe acfdeb 4(10分）设哈希函数 为H（key）=key MOD 11,用线性 探测再 散列的 方法处 理冲突。请画出依 次插入 元素29，15，48，47，23，41，73，37后，该哈希表 的状态，并在 各元素 下面标 出其冲 突次数。0 1 2 3 4 5 6 7 8 9 10 冲突次数：4（10分）0 1 2 3 4 5 6 7 8 9 10 23 47 15 48 37 29 41 73 1 2 2 四、算法 设计题（共20分）1（10分）写 出在带 头结点 的单链 表上实 现线性 表操 作LENGTH（L）的算法。1.LENGTH(L)（10分）int LENGTH(L

10、)int length=0;Nodt*p=L-head;while(p)length+;p=p-next;return length;每行语 句1分 2（10分）填 空完成 先序遍 历建立 二叉树 的如下 算法。Status CreateBiT ree(BiT ree&T)scanf(&ch);if(ch=)T=NULL;else /生成根结点 CreateBiT ree();/构造左子 树 CreateBiT ree();/构造右子 树 return OK;2（10分）Status CreateBiTree(BiTree&T)scanf(&ch);if(ch=)T=NULL;else T=n

11、ew Node(ch);/生 成根结 点 (4分)CreateBiTree(T-lchild);/构造左 子树 (3分)CreateBiTree(T-rchild);/构造右 子树 (3分)return OK;2（10分）以 顺序表 为存储 结构，写出折 半插入 排序的 算法。voi d BiInserti onSort(SqList&L)for(i=2;i=L.length;+i)L.r0=L.ri;/将 L.ri 暂存到 L.r0 low=1;high=i-1;while(low=high)m=(low+high)/2;/折 半 if(L.r0.key=high+1;-j)L.rj+1=L

12、.rj;/记 录后移 L.rhigh+1=L.r0;/插 入 /for /BInsertSort 每条指 令1分 1.voi d AE(Stack&S)InitStack(S);Push(S,3);Push(S,4);int x=Pop(S)+2*Pop(S);Push(S,x);int i,a5=1,5,8,12,15;for(i=0;i5;i+)Push(S,2*ai);while(!StackEmpty(S)coutPop(S)left,c1,c2);c1+;if(BT-left=NULL&BT-right=NULL)c2+;ABC(BT-right,c1,c2);/if 该函数执 行的

13、功 能是什 么？一、算法填空（共8分）向单链表 的末尾 添加一 个元素 的算法。Void InsertRear(LNode*&HL,const ElemType&item)LNode*newptr;newptr=new LNode;If(_)cerrMemory allocation failare!next=NULL;if(HL=NULL)HL=_;else LNode*P=HL;While(P-next!=NULL)_;p-next=newptr;二、编写算法（共8分）编写从类 型为List的线性表L 中 将第i 个元素 删除的 算法，（假 定不需 要对i 的值进 行有效 性检查,也 不用

14、判别L是否为空 表。）voi d Delete(List&L,int i)一、阅读算法（每题7分，共14分）1.30 24 16 10 2 10 2.该函数的 功能是：统计 出BT所 指向的 二叉树 的结点 总数和叶 子总数 二、算法填空（共8分，每一 空2分）newptr=NULL newptr-=data newptr p=p-next 三、编写算法（8分）void Delete(List&L,int i)for(int j=i-1;jlink;h-link=_ NULL；或者 0 ；（2分）while(p!=NULL)s=p;p=p-link;_ s-link=h-link;_（2分）h

15、-link=s;什 么 是 表 头 结 点？（2分）如 果 该 链 表 无 表 头 结 点，则 原 程 序 该 做 怎 样 的 修 改？（4分）2、（13分）对以 下 函 数 填 空，实 现 以 带 头 结 点 的 单 链 表h为 存 储 结构 的 直 接 选 择 排 序。单 链 表 的 结点 结构 定 义 为 typedef struct nodeint key;struct node*next;JD;void zjxzpx(JD*h)JD*p,*q,*m;int x;p=h-next;while(p!=NULL)q=p-next;m=p;while(q!=NULL)if(m-keyq-ke

16、y)_;（2分）_;（2分）if(p!=m)x=p-key;p-key=m-key;m-key=x;_;（2分）直 接 选 择 排 序 属 于_(稳 定/不 稳 定)排 序。（2分）该 排 序 算 法 总 的 键 值 比 较 次 数 为_。（2分）并 分 析 什 么 情 况 下 有 最 小 移 动 记 录 次 数？什 么 情 况 下 有 最 大 移 动 记 录 次 数？算 法 的 平 均 时 间 复 杂 度 为 多少？（3分）3、（13分）对以 下 函 数 填 空，实 现 以 带 头 结 点 的 单 链 表h为 存 储 结构 的 直 接 选 择 排 序。单 链 表 的 结点 结 构 定 义 为

17、 typedef struct nodeint key;struct node*next;JD;void zjxzpx(JD*h)JD*p,*q,*m;int x;p=h-next;while(p!=NULL)q=p-next;m=p;while(q!=NULL)if(m-keyq-key)_;（2分）_;（2分）if(p!=m)x=p-key;p-key=m-key;m-key=x;_;（2分）直 接 选 择 排 序 属 于_(稳 定/不 稳 定)排 序。（2分）该 排 序 算 法 总 的 键 值 比 较 次 数 为_。（2分）并 分 析 什 么 情 况 下 有 最 小 移 动 记 录 次

18、数？什 么 情 况 下 有 最 大 移 动 记 录 次 数？算 法 的 平 均 时 间 复 杂 度 为 多少？（3分）1、struct node*link;(2分)NULL；或者 0 ；(2分)s-link=h-link;（2分）什么是表头 结点？答：表头 结点是 有时为 了操作 方便而 在链表 的第一 结点之 前添加的 一个结 点，该结点 结构与 表中结 点相同，但数据域 不存放 表中数 据，或者闲 置不用，或 者存放 特殊信 息。表 头结点 的链域 存放指 向链表 中第一 个结 点的指针。（2分，回答对 点 给1 分；点0.5分；点0.5分。）如果该链表 无表头结 点该做 怎样的修 改？修

19、改如下：void invert(LNode*h)LNode*s,*p;p=h；(1分)h=NULL;（1分）while(p!=NULL)s=p;p=p-link;s-link=h;（1分）h=s;（1分）2、m=q;(2分)q=q-link;（2分）p=p-link;（2分）不稳定（2分）n(n-1)/2（2分）当待排序 序列为“正序”时，有最小 移动次 数0；（1分）当待排序 序列为“逆序”时，有最大 移动次 数3(n-1)；（1分）算法的平 均时间 复杂度 为O（n2）。（1分）3、p-rchild;（2分）q-L Tag!=1;（2分）1（1分）；NULL；或者 0；1、（6分）已 知

20、二 叉树 的 层 次 序 列 为ABCDEFGHIJK，中 序 序 列 为DBGEHJACIKF，请 构 造 一 棵 二 叉树，并 写 出 其 后 序 序 列。2、（10分）已 知二 叉 树 的 先 序、中 序 和 后 序 序 列 如 下，其 中 有 一 些 看 不 清 的 字 母 用*表 示，请 先 补 充*处 的 字 母，再 构 造 一 棵 符 合 条 件 的 二 叉 树（画 出 图 示），最 后 画 出 带 头 结 点 的 中 序 线 索 链 表。前 序 序 列：*BC*G*中 序 序 列：CB*EAGH*后 序 序 列：*EDB*F A 3、（6分）将 下 列 二叉 树 还 原 成 森

21、 林，并 写 出 先 序 遍 历 森 林 序列。ABECFGMDNSHKIJ 5、（8分）已 知 图G=（V，E），其 中V=a,b,c,d,e，E=,要 求：（1）画 出 图G；（2分）（2）给 出 图G的 邻 接 矩 阵；(2分)（3）给 出 图G的 邻 接 表；（2分）（4）给 出 图G的 一 种 拓 扑 序 列。（2分）三、应用 题：1、（4分，画 对根结 点1分，左子 树正 确1.5分，右 子树正 确1.5分）后序序列 为：DGJHEBKIFCA（2分）2、前序序列 补充完 整为：ABCDEFGH（1分）中序序列 补充完 整为：CBDEAGHF（1分）后序序列 补充完 整为：CEDB

22、HGFA（1分）（3分，画 对根结 点1分，左子 树正 确1分，右子树 正确1分）ABCDEFGHIJKABFCDGEH （4分）画 对各结 点线索 指针 得2分，标志位 正确 得1分，表头结 点正确得 3、（4分，画 对各树 根结 点2分，画对各子 树子女 结点2分）该森林的 先序序 列为：ABCMNSDEFGHKIJ（2分）4、（1）（2分,如果 画的是 无向图 不給分）（2）（2分，上小 题答错 的学生，如果 这里给 出的答 案符合 他自己 所画的图，给全 分）0 1 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 （3）a b c d e (2分，第1小题答 错的学生，如果 这里给 出的答 案符合 他自己 画的图，给全 分)（4）可能的 拓扑排 序为：abdce 或 adbce(2分)ABECFGMDNSHKIJabcde2 3 4 3 5 5 3 5