数据结构期末考试复习总结
数据结构》期末考试题型及分值
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 顺序建BBST
2) 6-5-4-3-2-1 顺序建BBST
一.填空恵
I. 数据皓构是一门研吨耶畫值计兔的刃胖谀计间通屮计U
机的Mft/jfc 它ffl 之仙的拱* 和运算卷的学科. 1整掘第构被腦式地宦义为.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捋向， 不移动粘点人 其缺点是不劇枉幣机访何?只能嗽宇山间，忖外，琏伞鉛也卜坤加抬计域* 造由颗外存储宁间啣L 3,対性农造置头姑点沛件戶丿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 0
1 0 1 0 1
1 1 0 1 1
1 0 1 0 1
线性表为：（78，50，40，60， 34， 90) 0 1 1 1 0
2.请画出下图的邻接矩阵和邻接表。
<7 _1 F
1 2 data n ext
3 4 5 6 7
3.已知一个图的顶点集 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)20 4?画出向小根堆中加入数据 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);
用克鲁斯卡尔算法得到的最小生成树为：
4 5 2
图11
cout<
}
}
该算法的功能是： 递归地后序遍历链式存储的二叉树
五、算法填空(共 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 ;〃 return
else if(item
return Find( ______
else return Find( __
}//if
}
查找成功 _ true __ ;}
BST->left ,item); _BST->right __,item);