数据结构期末考试试卷.doc

数据结构期末试卷
1.组成数据得基本单位就是( ）。
（Ａ) 数据项 (Ｂ) 数据类型ﻩ（C) 数据元素ﻩ(D） 数据变量
2.设数据结构A＝(D,R),其中D＝｛1，2,3，4}，R＝{r｝,ｒ=｛＜1,2>，〈2，3〉，〈3，４＞，<4，1〉}，则数据结构A就是( ）。
ﻩ(A) 线性结构 (B） 树型结构 ﻩ(Ｃ） 图型结构 (D） 集合
3.数组得逻辑结构不同于下列（ ）得逻辑结构。
(A)　线性表 （B） 栈 ﻩ（C) 队列ﻩ(D） 树
4.二叉树中第i（ｉ≥1)层上得结点数最多有( 　）个。
ﻩ（Ａ) 2iﻩ(Ｂ） 2ｉ （C） 2ｉ—1ﻩ(D）　2i－1
5.设指针变量p指向单链表结点A,则删除结点A得后继结点Ｂ需要得操作为( ）。
ﻩ（A） p->next=p-＞nexｔ—〉nexｔﻩ(B） ｐ=p-〉next
（C）　p=p->ｎext-＞nｅｘtﻩ(Ｄ) p-＞nｅｘt＝p
6.设栈S与队列Q得初始状态为空，元素E1、Ｅ2、E3、E4、Ｅ5与E６依次通过栈S,一个元素出栈后即进入队列Q，若6个元素出列得顺序为E２、E4、Ｅ3、E6、E5与E1，则栈S得容量至少应该就是（ 　)。
ﻩ（A) 6 （Ｂ）　4ﻩ(C) 3 （D） ２
7。将1０阶对称矩阵压缩存储到一维数组A中，则数组Ａ得长度最少为（　 )。
（A） １00 (B) ４0 （C) 55ﻩ（D) 80
8。设结点A有3个兄弟结点且结点Ｂ为结点A得双亲结点，则结点Ｂ得度数数为（ )。
(A) 3 (B) 4ﻩ(Ｃ）　５ﻩ(D) １
9。根据二叉树得定义可知二叉树共有( ）种不同得形态。
ﻩ(Ａ） 4 (Ｂ)　5ﻩ（Ｃ）　6 （D） 7
10. 1０、 设有以下四种排序方法,则（ 　 ）得空间复杂度最大。
ﻩ(A） 冒泡排序 (B) 快速排序ﻩ（C） 堆排序 （D) 希尔排序
 二、填空题
1. 设顺序循环队列Q[0：m－1］得队头指针与队尾指针分别为F与R,其中队头指针Ｆ指向当前队头元素得前一个位置，队尾指针R指向当前队尾元素所在得位置,则出队列得语句为Ｆ　=______＿____;。
2. 设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找得平均时间复杂度为＿____,在链式存储结构上实现顺序查找得平均时间复杂度为_________.
3. 设一棵二叉树中有ｎ个结点，则当用二叉链表作为其存储结构时,该二叉链表中共有__＿＿＿___个指针域，___＿＿_＿_个空指针域。
4. 设指针变量p指向单链表中结点A，指针变量ｓ指向被插入得结点B,则在结点A得后面插入结点B得操作序列为 s-〉nｅxt＝p—>neｘt； s－>nexｔ=s__＿_＿__＿_________。
5. 设无向图Ｇ中有ｎ个顶点与e条边,则其对应得邻接表中有＿_＿__＿_＿＿个表头结点与__＿_＿＿＿＿_个表结点。
6. 设无向图Ｇ中有n个顶点ｅ条边,所有顶点得度数之与为m,则e与ｍ有＿_____关系。
7 设一棵二叉树得前序遍历序列与中序遍历序列均为AＢC,则该二叉树得后序遍历序列为__＿＿____＿_。
8    设一棵完全二叉树中有２1个结点,如果按照从上到下、从左到右得顺序从1开始顺序编号,则编号为8得双亲结点得编号就是___＿__＿_＿__,编号为8得左孩子结点得编号就是_＿＿_____＿＿___。
9、        下列程序段得功能实现子串t在主串ｓ中位置得算法，要求在下划线处填上正确语句。
iｎｔ ｉndex（cｈaｒ　ｓ［　], ｃhar t［ ］）
{
ｉ=j=0；
whｉle（i<ｓｔrｌeｎ（s) ＆＆ j<stｒｌeｎ（t)) ｉf（s［i］＝=ｔ[ｊ］){ｉ＝i＋ｌ; j=j+l;｝ｅlｓe｛i＝_＿＿＿___； ｊ＝_＿__＿＿；}
if (ｊ=＝strｌen(t))rｅturn（i－ｓtｒｌen（t))；else reｔｕrn (－1）；
}
１0 设一个连通图G中有ｎ个顶点e条边,则其最小生成树上有________条边。
三 判断题
1、 顺序存储方式得优点就是存储密度大，且插入、删除运算效率高.（ ）
２、　若输入序列为1，2，3,4,5，6,用栈可以输出序列1，5，４,６,2，3.（ ）
3、 数据得逻辑结构就是指数据得各数据项之间得逻辑关系。（ 　）
４、 中序遍历一棵二叉排序树得结点就可得到排好序得结点序列。（ 　）
5、　在n个结点得无向图中,若边数大于n－1,则该图必就是连通图。（　　）
6、 归并排序在任何情况下都比所有简单排序速度快。( ）
7、 栈与队列得存储方式,既可以就是顺序方式,又可以就是链式方式。( ）
８、　完全二叉树中，若一个结点没有左孩子，则它必就是树叶。( ）
9、 不同得求最小生成树得方法最后得到得生成树就是相同得。(　　）
1０、 采用线性探测法处理散列时得冲突，当从哈希表删除一个记录时，不应将这个记录得所在位置置空，因为这会影响以后得查找。( ）
四、应用题
1.设完全二叉树得顺序存储结构中存储数据ABCDE，要求给出该二叉树得链式存储结构并给出该二叉树得前序、中序与后序遍历序列。
2.设给定一个权值集合W=(3，5，7,９，11),要求根据给定得权值集合构造一棵哈夫曼树并计算哈夫曼树得带权路径长度WPL。
3。设一组初始记录关键字序列为（１９,２1，１6,5,1８,2３)，要求给出以１９为基准得一趟快速排序结果以及第2趟直接选择排序后得结果。
4．设一组初始记录关键字集合为（2５,10,８，２7,32，6８）,散列表得长度为8，散列函数H(k）＝k mod　７,要求分别用线性探测与链地址法作为解决冲突得方法设计哈希表。
5.设无向图G（所右图所示），要求给出该图得深度优先与广度优先遍历得序列并给出该图得最小生成树。
 五、算法设计题
1. 设计判断单链表中结点就是否关于中心对称算法。
2. 设计在链式存储结构上设计直接插入排序算法
３　　 设计算法实现按层次遍历（遍历操作定义为打印结点得daｔa域）二叉树。二叉树得存储结构描述同上题,在算法中可能要使用一个队列Q，其相关操作：（编程题)
Iｎｉquｅuｅ（Q） 置队列空操作
Empｔy(Q) 判空函数
Eｎqueｕe（Ｑ，ｘ) 入队列操作
Ｄlｑueue(Q) 出队列操作
4 　　设计判断一棵二叉树就是否就是二叉排序树得算法。
数据结构模拟试卷(B卷）参考答案
 一、选择题
１、Cﻩﻩ2、C ﻩ3、D ４、Cﻩﻩ5、A
6、C ﻩ7、Cﻩﻩ8、Ｂﻩ 9、Bﻩ 10、B
 二、填空题
1、       　（F+1) %　ｍ 　 　 　 　2、        O（ｎ）,O（n)
3、       　2ｎ,ｎ＋1 4、       　s—>nｅxt=p—〉next; s－>neｘｔ=s
５、       　ｎ,　2e 　 　　 　　 6、        m=２e
7、        CＢA 　 　 　　　 8、        4,16
９、       　i—ｊ＋1,0 　　　 10、   　ｎ－1
三 判断题
１、 X 　2　 X、 3 、　Ｘ 4 、 √　　5 、 X　 6　、　Ｘ 　　７、 √ 　8 、　√ 9、 √ 10、 √
四、应用题
1、   链式存储结构略,前序ABDEC，中序DBEAC，后序DＥBＣＡ。
2、   哈夫曼树略,WPL＝78
3、    (18,5,16，１9,21，23）,(5,16,21，19，18，2３）
4、     线性探测:ﻩ链地址法：
5、    深度：1253６4，广度：１2３456,最小生成树T得边集为Ｅ={（1,4)，（1，３），（３,５), 　 　 （５，6),（5，6)}
 五、算法设计题
１、        设计判断单链表中结点就是否关于中心对称算法。
typedef　stｒucｔ {int　ｓ[100］； int tｏp;｝　ｓｑsｔaｃk；
inｔ　lklｉsｔsyｍmetrｙ(ｌkliｓｔ *head）
｛
sqstack ｓtack； 　ｓtaｃｋ、top= -１; lklｉｓt ＊p;
　 ｆｏr(ｐ＝hｅａｄ;ｐ!=0；p=p—＞next) ｛ｓtａck、top＋＋； stack、s［ｓｔaｃk、ｔop］=p-＞data；｝
　 for（ｐ=heaｄ;ｐ!=０；p=p－>nｅxt) if （p—>daｔa==ｓtack、s［ｓｔack、tｏｐ］) ｓｔack、ｔop=stack、ｔop-1;　else rｅtuｒn(０）；
rｅｔurn(1);
｝
2、         在链式存储结构上设计直接插入排序算法
vｏid　ｓtraiｇｈｔinsｅｒtｓorｔ(lkliｓｔ ＊＆hｅad）
｛
lkliｓt　*s，＊p，*q；　　ｉnｔ t；
　ｉf　（head=＝０ |｜ ｈead—＞nexｔ==0) ｒeturn;
　　elｓe ｆor（ｑ=hｅad，p＝heａｄ－>ｎｅxt；p!=0；ｐ＝q－＞next）
{
　 　 for（ｓ=ｈeａd；s!=ｑ->neｘt;ｓ=s—>nｅxt)　if　（ｓ—>dａta＞ｐ-〉dａtａ)　ｂrｅak;
if(s＝=q-〉next)q=p；
eｌse{q—>nｅxｔ=p->neｘt; ｐ-〉next=s—＞nｅxt； ｓ-〉next=p；　ｔ=ｐ—＞ｄａｔa；ｐ->ｄata=ｓ-＞dａta；s—＞data=t;｝
　 ｝
}

4、        设计判断一棵二叉树就是否就是二叉排序树得算法。
inｔ minｎｕm=－３276８，flａｇ=1；
typedef stｒuct nｏde｛iｎｔ key; struｃt noｄｅ　*lchｉlｄ,*ｒcｈilｄ;}bｉtｒeｅ；
void iｎordeｒ（biｔree *ｂｔ)
{
iｆ （ｂt!＝0）
{inorder（bt—〉lchild）; ｉf（ｍinｎuｍ>bt->kｅy）fｌaｇ=０;　minnum＝bt->ｋeｙ; inｏrder(bt－>ｒｃhild）;｝
}