数据结构》期末考试题型及分值1）简答题题*5 分=30 分简要回答要点2）分析题题*5 分=30 分给出结果3）设计题题*10 分=10 分设计思想及结果4）编程题题*10 分=10 分完整代码5）综合题题*20 分=20 分抽象数据类型的定义、表示、实现、算法分析{ 定义=功能ADT）表示=存储结构体实现=算法（基本操作）算法分析=时间、空间复杂度}考试概念有： 1.数据结构{ 一、线性表（栈-队-列-串-数组-广义表-逻辑结构-存储结构-运算结构）二、非线性表（集合- 树-图）}2. 抽象数据类型数据对象-数据关系- 基本操作3. 算法性质-要求（设计）-效率（度量）4. 实例查找：高效查找算法排序：高效的排序算法分析题考试题目参考1)1-2-3-4-5-6 顺序建BBST2) 6-5-4-3-2-1 顺序建BBST一.填空恵I.数据皓构是一门研吨耶畫值计兔的刃胖谀计间通屮计U机的Mft/jfc它ffl 之仙的拱*和运算卷的学科.1整掘第构被腦式地宦义为<I>.KJ ，其屮DJC桑—炖有隈整合.K 是和上的 曲 育磴懐M T*玉曇世髓恂包松勘机的 WM» 、MIMML 和It 据的 歳■ 这三牛育面前内粉.4+載据站构按世辑蚓构可付为两人陇*它n 分别兄—理旌址讯―和—，枚仙.段—気纨性蜡购巾兄冨之间存庄一对一共鑑.辑形毎构山元聊之间存住二^吐圭黄議・图形船构屮无JK 之伺存在 圭蚩圭关蝶”&左线性酷构中，第一牛蠕点 於哲前驰蠕点+乳余歸个坤点有n 貝有1个前鉴轴点;塩橋一个酣点 淮 启_恬统络点.耳余毎个结点有且只有1牛陆续轄点=孔在胃形時构屮.暂根结点液令血鱼一焙点.其余毎个结点有且只任」_牛前滋焙点t 叶了誌点没有 竝£—结乩 比余晦个怡点的后擁恰点数可叹任泌t_・乩在斟常站构屮.毎个结孤的前駆旳血致和后墟结点數可以 枉诡爭个■故据的存储结构可胡四种華木的存畤方链表平，’艺如分别足赎擀、捷式、背n 粗 離列io 敦据咐运许址常用的和飞种.它们分别是逊、刪障盘價「n? 11. -・个JT 法的效率可彷为吋觥_效睾和空“L 效事"11在戴呼表屮幅入琐则■一+元豪，需耍平均雀动盍屮 半元H ・具体聲动的兄■个叠与袁松和防L 素在农屮細但伍荣.IX 域性表中站点的理含址右規 帕,拮点创佝关采品―一对一一的.14, 问~亍长庫为Ti 脚问1B 豹第i 个元薦I 】WiWn+li 之前插入一个云冨涉 裔|疋麻移动 "1个兀轧 15. 向-个长度为机的向量中圮除蘭i 平元素tlWiWn 】时.需向前移动n-i 元亂简答题实例宀谕谨幢序投和链左存储庁式的伶点荐；烦序表的优点是町以琦机W 冋数挥元盍，缺点垦乂小同圭・不利干站般点（婚减结曲应住霍要桔曲吨累）.悽衣的优点皿冗用茹竹方式増减结血 儿常丹便【只需故变茹£1捋向， 不移动粘点人 其缺点是不劇枉幣机访何・只能嗽宇山间，忖外，琏伞鉛也卜坤加抬计域* 造由颗外存储宁间啣L3,対性农造置头姑点沛件戶丿J "T ｛至少说出两荼好处）（1） XI 带头结点的苗表，在表的任何绪点之前插入结点理删除表中任何站心•斯些'故的部 是修改前一亍结点的指针域，阖为任何兀索结点都右荊驰詰点〔若昭表没有头结点，眦苜兀索塔丿卅仃忒亭「门二 在耳前播入箱点和删除演箱点时操作貝朵曲）•（卩 刈带头站克的懺辄 表MHWB 向久绪克的II ：空菲¥1 •闵此空舉与*空崔的处世足头妙点苗忙卅出1-匣襄勾命空表处理一* 足甜点之IttfiHt 更方便“设计题:(1)1 +设计计算叉檜中所仃菇点值之和的算法。

void sunifbitive *bt.int {iRbTfm {s=s+bt-xlata; siun(bt-"f lchild^); suni (^bt->rchild s):} }(2)设计在链式结构上实现简单选择排字算法。

void simples el ectsor lkli st(lklist 水&he^ad) {lklist 屮mt mint;if(liead==0 liead->iiext=O) lPtumi for(q=h?ad: q!=O;q=q->neKt) {mui=q->(1ata:尸q;for(p=q->next: p!=0;p=p->mext) if(mm>p->dataXmin=p->data: 円;} if(s !=q){t^s->da1a; s->data=q->data; q->data^t:} } }数据结构试卷（一）三、计算题（每题 6分，共24 分）1.在如下数组A 中链接存储了一个线性表，表头指针为 A [0].next ，试写出该线性表。

0 1 1 1 010 1 0 111 0 1 11 0 1 0 1 线性表为：（78，50，40，60， 34， 90)1112.请画出下图的邻接矩阵和邻接表。

<7_1 F1 2 data n ext3 45 6 73.已知一个图的顶点集 V 和边集E 分别为：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。

(1,2)3, (4,6)4,(1,3)5, (1,4)8, (2,5)10, (4,7)204•画出向小根堆中加入数据 4, 2, 5, 8, 3时，每加入一个数据后堆的变化。

见图12四、阅读算法(每题 7分，共14分)1. LinkList mynote(LinkList L){//L 是不带头结点的单链表的头指针if(L&&L-> next){q=L ； L=L — >next ; p=L ;S1: while(p — >n ext) p=p — >next ; S2：p — >next=q ; q — >next=NULL ;}return L ; }请回答下列问题： (1) 说明语句S1的功能； 查询链表的尾结点(2) 说明语句组S2的功能；将第一个结点链接到链表的尾部，作为新的尾结点(3) 设链表表示的线性表为(a 1,a 2,…,a n ),写出算法执行后的返回值所表示的线 性表。

返回的线性表为(a 2,a 3,— ,a n :a i )2. void ABC(BTNode * BT) {if BT {ABC (BT->left); ABC (BT->right);用克鲁斯卡尔算法得到的最小生成树为：452 图11cout<<BT->data<<''; } }该算法的功能是： 递归地后序遍历链式存储的二叉树五、算法填空(共 8分) 二叉搜索树的查找 一锻归算法：bool Fi nd(BTreeNode* BST,ElemType & item) {if (BST==NULL) return false; //统计出单链表HL 中结点的值等于给定值 X 的结点数。

int CountX(LNode* HL,ElemType x) int Cou ntX(LNode* HL,ElemType x){ int i=0: LNode* p=HL://i 为计数器while(p!=NULL)_{if (P->data==x) i++; _________ p=p->n ext:"/while, 出循环时 i 中的值即为 x 结点个数 return i:}//Cou ntX数据结构试卷(二) 三、应用题(36分)1. 设一组初始记录关键字序列为(45, 80, 48, 40, 22, 78)，则分别给出第4趟简单选择 排序和第4趟直接插入排序后的结果。

(22 , 40, 45, 48, 80, 78) , (40 , 45, 48, 80, 22, 78)2. 设指针变量p 指向双向链表中结点 A 指针变量q 指向被插入结点 B,要求给出在结点 A 的后面插入结点B 的操作序列(设双向链表中结点的两个指针域分别为 llink 和rlink )。

q->ll in k=p; q->rli nk=p->rli nk; p->rl in k->ll in k=q; p->rli nk=q;3.设一组有序的记录关键字序列为 (13 , 18, 24, 35, 47, 50,62, 83, 90)，查找方法用二分查找，要求计算出查找关键字 62时的比较次数并计算出查找成功时的平均查找长度。

2, ASL=91*1+2*2+3*4+4*2)=25/9查找失败 else {if(item==BST->data){ item=BST->data ;〃 returnelse if(item<BST->data)return Find( ______ else return Find( __}//if}查找成功 _ true __ ;} BST->left ,item); _BST->right __,item);4. 设一棵树T 中边的集合为{(A , B), (A , C), (A, D), (B , E), (C, F), (C, G)}，要求用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉树。

树的链式存储结构略，二叉树略5. 设有无向图G,要求给出用普里姆算法构造最小生成树所走过的边的集合。

E={(1 , 3), (1 , 2), (3, 5), (5, 6) , (6 , 4)}6. 设有一组初始记录关键字为(45 , 80 , 48 ,40 , 22 , 78),要求构造一棵二叉排序树并给出构造过程。

四、算法设计题(16分)1. 设有一组初始记录关键字序列( K , K2,…,K n),要求设计一个算法能够在0(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于K,右半部分的每个关键字均大于等于K。

设有一组初始记录关键字序列( K i , K2,…,K.),要求设计一个算法能够在0(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于K,右半部分的每个关键字均大于等于K。