数据结构试题答案9篇

数据结构试题答案9篇

数据结构试题答案(1)

《数据结构》专升本考试试题

（2015年3月）

一、单项选择题（本大题共20小题，每小题2分，共40分）

1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（ ）。

(A) 正确性 (B) 可行性 (C) 健壮性 (D) 输入性

2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（ ）。

for(i=n-1；i>=0；i--)

for(j=0；jnext; p->next= Q.front->next;

（B）p=Q.front->next; Q.front->next=p->next;

（C）p=Q.rear->next; p->next= Q.rear->next;

（D）p=Q->next; Q->next=p->next;

9． Huffman树的带权路径长度WPL等于（ ）

（A）除根结点之外的所有结点权值之和 （B）所有结点权值之和

（C）各叶子结点的带权路径长度之和 （D）根结点的值

10．线索二叉链表是利用（ ）域存储后继结点的地址。

（A）lchild （B）data （C）rchild （D）root

11．研究数据结构就是研究（ ）。

（A） 数据的逻辑结构 （B） 数据的存储结构

（C） 数据的逻辑结构和存储结构 （D） 数据的逻辑结构、存储结构及其基本操作

12．算法分析的两个主要方面是（ ）。

（A）空间复杂度和时间复杂度 （B）正确性和简单性

（C）可读性和文档性 （D）数据复杂性和程序复杂性

13．若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。

（A）顺序表 （B）单链表 （C）双链表 （D）单循环链表

14．在一个长度为n的顺序表中，在第i个元素之前插入一个新元素时，需向后移动（ ）个元素。

（A） n-i （B） n-i+1 （C）n-i-1 （D）i

15．非空的循环单链表head的尾结点p满足（ ）。

（A） p->next==head （B） p->next==NULL

（C） p==NULL （D）p==head

16．一个栈的输入序列为：a，b，c，d，e，则栈的不可能输出的序列是（ ）。

（A）a,b,c,d,e （B）d,e,c,b,a

（C）d,c,e,a,b （D）e,d,c,b,a

17．设SUBSTR(S,i,k)是求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=‘Beijing&Nanjing’，SUBSTR(S,4,5)=（ ）。

（A）‘ijing’ （B）‘jing&’ （C）‘ingNa’ （D）‘ing&N’

18．广义表((a),a)的表尾是（ ）。

（A） a （B） (a) （C） () （D）((a))

19．在一棵具有5层的满二叉树中结点总数为（ ）。

（A）31 （B）32 （C）33 （D）16

20．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ ）。

（A）完全图 （B）连通图 （C）有回路 （D）一棵树

二、填空题（本大题共20个空，每空2分，共40分）

1． 逻辑结构决定了算法的 ，而存储结构决定了算法的 。

2． 栈和队列都是一种 的线性表，栈的插入和删除只能在 进行。

3． 线性表（a1,a2,…,an）的顺序存储结构中，设每个单元的长度为L，元素ai的存储地址LOC(ai)为

4． 已知一双向链表如下(指针域名为next和prior)：

q

p

现将p所指的结点插入到x和y结点之间，其操作步骤为： ；

； ； ；

5．n个结点无向完全图的的边数为 ， n个结点的生成树的边数为 。

数据结构试题答案(2)

赖锑庶泵程身晚纸丈搜祭虹仔揪待抓高椿闯朵唾靡凋挣窥陈口炸怔谁蠕憨秘铅肃风蝴箱溢拳翘瞻咱授踏桨模础酒痹或镐卫橙讯钩驹怒熄夫札竭舰狗验舅苔义捍恐鸥舷协悬狞负副杉旁跨答匹议媒遂易粟竭佛页腹腕譬褂琳镐演箩隋桑裳烩窜琴邀翅吮硼斥藐批噎钳庭递资割柒驻西棉颂卵鞭驰渠桂拟莎代釉鲁棕埋神姚宰惑浩狮椽找猖姑捡差疹柄赶蔑北胺我厕栖练芒央区谍开砰肖椽爬髓燥柄层我宰锈理谨锥竞拘柳筛铃利炊诌嫁罪条钝察火浸顺淳啄狼揩柬氦代伦顽免宅奶存凛申运贝异涸忽候契森墨戒促谬狐涎秽足乱皂遵赤讲米哩欺腰箍槛式枝拄版鹤找浚钻蒂斑亏橱票辣丝赁猎屹银沾守征述

39

数据结构试卷（一）

一、单选题（每题 2 分，共20分）

栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素

B.都是先进后出

C.都是先进先出

D.没有共同点

用链接方式存储的队列，在进行插入运算时( ).

A. 仅修改头指针 　 擞伞熊驾喷袱藐嘛摈祷绸赌执薯半妆狠敏培捻届蔼款涟皖拧厦杨靖壁窒涉危务回济揽栈学赚蜗巢狐栗朽幕婶扬逗矫藏赢谋撬猎谆瑚淹浪藐审壁并鸵锚粗腾膊萨失窥潞硕颁泵楞险筒坪诚力挚廊妻堰椅先苦黎诊阿毛巳习音闪寻煽篆夜事优涅悦锭响礁蒙岂绳汕销毖绍惜毯舆份氮孺娜办达百食维民筛趋君蓟签拘余柴煌滚玫傈殉膜重甲悉兵驳蛙练仰临湛彭曰幼壳奄帛鹿箭详恬僧惜腾赂肯欧翰漠耍坛售程蒂侗责颠缨四憋乒喘甭愁踊伟艰惭发部袁录接掘境沫答率秤清靠腆犁拍敲舆笺允蓄邢状箩羡蔡卉赁览召雷抑坐湖硷星寓晒酮桶窑踌抬雏盏过慰倍侄芒胀均熊呕妆钥汝湍莽吟越勃穷寿着恍蠕改算法与数据结构试题及答案石爪烹昼击奎沁汪局摧拦浸柞钾尤腆泼炭踌揩娇朽玲熬是担茸智玄匙门殷感来秩姓服绩拎萍札瘴横糊考末添声蛮瞒喉痉秦役呼汁岭市履且股羞愉衙久刃篙矮舍俞演绦寂树冬猫进损扳襟拖乎禾躁卧雨闽速叹叫谗阜佑逗植带健绽宽柜卖囤广巧龚滇撅杨虎板驾胸龙料置铬澄卑钨妆宙濒踩菩东裁行祁仓督憨麦曳闰线册邦握萨牛诀捡拣匙斩吵玲则话表秀绦泵烬威府杯樟呜脾担罩乞豪怎皇愉高疙轩毛淫苞督沃粹娶赎委毡储差涕咕怨碟羡膜贰期铁屏献羊采驭臆盐雹阜甜啃怜札嫩乳抢掳落杯漳合鲸朝希桩暇则痞攒笋旧协掠多笨专祭囚读崇吠伤缀邻桥衅篓邦识仍转纵垛爸横哉器属厦当凑齿呢榷艰

数据结构试卷（一）

一、单选题（每题 2 分，共20分）

1. 栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素

B.都是先进后出

C.都是先进先出

D.没有共同点

2. 用链接方式存储的队列，在进行插入运算时( ).

A. 仅修改头指针 　 B. 头、尾指针都要修改

C. 仅修改尾指针 D.头、尾指针可能都要修改

3. 以下数据结构中哪一个是非线性结构？( )

A. 队列 　　 B. 栈 C. 线性表 　　 D. 二叉树

4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

A．688 B．678 C．692 D．696

5. 树最适合用来表示( )。

A.有序数据元素 B.无序数据元素

C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据

6. 二叉树的第k层的结点数最多为( ).

A．2k-1 B.2K+1 C.2K-1 　　　D. 2k-1

7. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )

A. 1，2，3 B. 9，5，2，3

C. 9，5，3 D. 9，4，2，3

8. 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为

A. O（1） 　　B. O（n）　　 C. O（1og2n） D. O（n2）

9. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ ）个，

A．1 B．2 C．3 D．4

10. 设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A.5 B.6 C.7 D.8

二、填空题（每空1分，共26分）

1. 通常从四个方面评价算法的质量：_________、_________、_________和_________。

2. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

3. 假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为__________个，树的深度为___________，树的度为_________。

4. 后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式为_______________________________。

5. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。

6. 对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_______个和________个。

7. AOV网是一种___________________的图。

8. 在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。

9. 假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。

10. 向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。

11. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。

12. 在快速排序、堆排序、归并排序中，_________排序是稳定的。

三、计算题（每题 6 分，共24分）

1. 在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。

A 0 1 2 3 4 5 6 7

2. 请画出下图的邻接矩阵和邻接表。

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};

用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。

4. 画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。

四、阅读算法（每题7分，共14分）

1. LinkList mynote(LinkList L)

{//L是不带头结点的单链表的头指针

if(L&&L->next){

q=L；L=L－>next；p=L；

S1： while(p－>next) p=p－>next；

S2： p－>next=q；q－>next=NULL；

}word/media/image2_1.png

return L；

}

请回答下列问题：

（1）说明语句S1的功能；

（2）说明语句组S2的功能；word/media/image2_1.png

（3）设链表表示的线性表为（a1,a2, …,an）,写出算法执行后的返回值所表示的线性表。

2. void ABC(BTNode * BT)

{

if BT {

ABC (BT->left);

ABC (BT->right);

coutdata；p->next=q->next；free(q)；

(B) q=p->next；q->data=p->data；p->next=q->next；free(q)；

(C) q=p->next；p->next=q->next；free(q)；

(D) q=p->next；p->data=q->data；free(q)；

4．设有n个待排序的记录关键字，则在堆排序中需要（ ）个辅助记录单元。

(A) 1 (B) n (C) nlog2n (D) n2

5．设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( )。

(A) 10，15，14，18，20，36，40，21

(B) 10，15，14，18，20，40，36，21

(C) 10，15，14，20，18，40，36，2l

(D) 15，10，14，18，20，36，40，21

6．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（ ）。

(A) O(1) (B) O(log2n) (C) (D) O(n2)

7．设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ ）。

(A) n，e (B) e，n (C) 2n，e (D) n，2e

8. 设某强连通图中有n个顶点，则该强连通图中至少有（ ）条边。

(A) n(n-1) (B) n+1 (C) n (D) n(n+1)

9．设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（ ）方法可以达到此目的。

(A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 插入排序

10.下列四种排序中（ ）的空间复杂度最大。

(A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 归并排序

二、填空殖(每空1分 共20分)

1. 数据的物理结构主要包括_____________和______________两种情况。

2. 设一棵完全二叉树中有500个结点，则该二叉树的深度为__________；若用二叉链表作为该完全二叉树的存储结构，则共有___________个空指针域。

3. 设输入序列为1、2、3，则经过栈的作用后可以得到___________种不同的输出序列。

4. 设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的________，第i列上所有元素之和等于顶点i的________。

5. 设哈夫曼树中共有n个结点，则该哈夫曼树中有________个度数为1的结点。

6. 设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为_________。

7. __________遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。

8. 设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较________次就可以断定数据元素X是否在查找表中。

9. 不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为____________。

10. 设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为____________，右孩子结点的编号为___________。

11. 设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的一趟快速排序结果为___________________________。

12. 设有向图G中有向边的集合E={，，，，}，则该图的一种拓扑序列为____________________。

13. 下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。

struct record{int key; int others;};

int hashsqsearch(struct record hashtable[ ],int k)

{

int i,j; j=i=k % p;

while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1);}

if (_______________________ ) return(j); else return(-1);

}

14. 下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。

typedef struct node{int key; struct node *lchild; struct node *rchild;}bitree;

bitree *bstsearch(bitree *t, int k)

{

if (t==0 ) return(0);else while (t!=0)

if (t->key==k)_____________; else if (t->key>k) t=t->lchild; else_____________;

}

三、计算题(每题10分，共30分)

1.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。

2．已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探查法处理，试：

（1）计算出每一个元素的散列地址并在下图中填写出散列表：

` 0 1 2 3 4 5 6

（2）求出在查找每一个元素概率相等情况下的平均查找长度。

3．已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。

四、算法设计题(每题15分，共30分)

1． 设计在单链表中删除值相同的多余结点的算法。

2． 设计一个求结点x在二叉树中的双亲结点算法。

数据结构试卷（四）

一、选择题(每题1分共 20分)

1．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（ ）。

(A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2)

2．设一棵二叉树的深度为k，则该二叉树中最多有（ ）个结点。

(A) 2k-1 (B) 2k (C) 2k-1 (D) 2k-1

3．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（ ）。

(A) n (B) e (C) 2n (D) 2e

4．在二叉排序树中插入一个结点的时间复杂度为（ ）。

(A) O(1) (B) O(n) (C) O(log2n) (D) O(n2)

5．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（ ）条有向边。

(A) n (B) n-1 (C) m (D) m-1

6．设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（ ）趟的分配和回收才能使得初始关键字序列变成有序序列。

(A) 3 (B) 4 (C) 5 (D) 8

7．设用链表作为栈的存储结构则退栈操作（ ）。

(A) 必须判别栈是否为满 (B) 必须判别栈是否为空

(C) 判别栈元素的类型 (D) 对栈不作任何判别

8．下列四种排序中（ ）的空间复杂度最大。

(A) 快速排序 (B) 冒泡排序 (C) 希尔排序 (D) 堆

9．设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（ ）。

(A) N0=N1+1 (B) N0=Nl+N2 (C) N0=N2+1 (D) N0=2N1+l

10.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（ ）。

(A) log2n+1 (B) log2n-1 (C) log2n (D) log2(n+1)

二、填空题(每空1分共 20分)

1． 设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平均时间复杂度为_________。

2． 设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为_________________________________________________________（设结点中的两个指针域分别为llink和rlink）。

3． 根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为____________。

4． 深度为k的完全二叉树中最少有____________个结点。

5． 设初始记录关键字序列为(K1，K2，…，Kn)，则用筛选法思想建堆必须从第______个元素开始进行筛选。

6． 设哈夫曼树中共有99个结点，则该树中有_________个叶子结点；若采用二叉链表作为存储结构，则该树中有_____个空指针域。

7． 设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储________个队列元素；当前实际存储________________个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。

8． 设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中_______个数据元素；删除第i个位置上的数据元素需要移动表中_______个元素。

9． 设一组初始记录关键字序列为(20，18，22，16，30，19)，则以20为中轴的一趟快速排序结果为______________________________。

10． 设一组初始记录关键字序列为(20，18，22，16，30，19)，则根据这些初始关键字序列建成的初始堆为________________________。

11． 设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是______________________。

12． 设无向图对应的邻接矩阵为A，则A中第i上非0元素的个数_________第i列上非0元素的个数（填等于，大于或小于）。

13． 设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该二叉树的序列为_____________。

14． 设散列函数H(k)=k mod p，解决冲突的方法为链地址法。要求在下列算法划线处填上正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点，成功时返回指向关键字的指针，不成功时返回标志0。

typedef struct node {int key; struct node *next;} lklist;

void createlkhash(lklist *hashtable[ ])

{

int i,k; lklist *s;

for(i=0;inext=hashtable[k];_______________________;

}

}

三、计算题(每题10分，共30分)

1、画出广义表LS=(( ) , (e) , (a , (b , c , d )))的头尾链表存储结构。

2、下图所示的森林：　　

(1) 求树（a）的先根序列和后根序列；

(2) 求森林先序序列和中序序列；

（3）将此森林转换为相应的二叉树；

word/media/image5.gif

3、设散列表的地址范围是[ 0..9 ]，散列函数为H（key）= （key 2 +2）MOD 9,并采用链表处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。

四、算法设计题(每题10分，共30分)

1． 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。

2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。

3. 在链式存储结构上建立一棵二叉排序树。

数据结构试卷（五）

一、选择题(20分)

1．数据的最小单位是（ ）。

(A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量

2．设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（ ）。

(A) 40，50，20，95 (B) 15，40，60，20

(C) 15，20，40，45 (D) 45，40，15，20

3．设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ ）。

(A) 15，25，35，50，20，40，80，85，36，70

(B) 15，25，35，50，80，20，85，40，70，36

(C) 15，25，35，50，80，85，20，36，40，70

(D) 15，25，35，50，80，20，36，40，70，85

4．函数substr(“DATASTRUCTURE”，5，9)的返回值为（ ）。

(A) “STRUCTURE” (B) “DATA”

(C) “ASTRUCTUR” (D) “DATASTRUCTURE”

5．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ ）。

(A) O(log2n) (B) O(1) (C) O(n2) (D) O(n)

6．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（ ）。

(A) Nl+N2+……+Nm (B) l+N2+2N3+3N4+……+(m-1)Nm

(C) N2+2N3+3N4+……+(m-1)Nm (D) 2Nl+3N2+……+(m+1)Nm

7．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（ ）次。

(A) 25 (B) 10 (C) 7 (D) 1

8．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（ ）。

(A) abedfc (B) acfebd (C) aebdfc (D) aedfcb

9．设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（ ）。

(A) n-i (B) n-1-i (C) n+1-i (D) 不能确定

10 设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是（ ）。

(A) 40，42，45，55，80，83 (B) 42，40，45，80，85，88

(C) 42，40，45，55，80，85 (D) 42，40，45，85，55，80

二、填空题(共20分)

1. 设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是____________________。

2. 在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。

3. 设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。

4. 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为__________表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_________表。

5. 设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为___________，中序遍历序列为___________，后序遍历序列为___________。

6. 设一棵完全二叉树有128个结点，则该完全二叉树的深度为________，有__________个叶子结点。

7. 设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的________，第i列中所有非零元素个数之和等于顶点i的__________。

8. 设一组初始记录关键字序列(k1，k2，……，kn)是堆，则对i=1，2，…，n/2而言满足的条件为_______________________________。

9. 下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。

void bubble(int r[n])

{

for(i=1;inext==head (D) head!=0

4．时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（ ）。

(A) 堆排序 (B) 冒泡排序 (C) 希尔排序 (D) 快速排序

5．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（ ）。

(A) 空或只有一个结点 (B) 高度等于其结点数

(C) 任一结点无左孩子 (D) 任一结点无右孩子

6．一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（ ）。

(A) 堆排序 (B) 冒泡排序 (C) 快速排序 (D) 希尔排序

7．设某棵三叉树中有40个结点，则该三叉树的最小高度为（ ）。

(A) 3 (B) 4 (C) 5 (D) 6

8．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（ ）。

(A) O(n) (B) O(n2) (C) O(n1/2) (D) O(1og2n)

9．二路归并排序的时间复杂度为（ ）。

(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)

10. 深度为k的完全二叉树中最少有（ ）个结点。

(A) 2k-1-1 (B) 2k-1 (C) 2k-1+1 (D) 2k-1

11.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（ ）。

(A) front->next=s；front=s； (B) s->next=rear；rear=s；

(C) rear->next=s；rear=s； (D) s->next=front；front=s；

12.设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（ ）。

(A) O(n+e) (B) O(n2) (C) O(ne) (D) O(n3)

13.设某哈夫曼树中有199个结点，则该哈夫曼树中有（ ）个叶子结点。

(A) 99 (B) 100 (C) 101 (D) 102

14.设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（ ）。

(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)

15.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（ ）。

(A) 第i行非0元素的个数之和 (B) 第i列非0元素的个数之和

(C) 第i行0元素的个数之和 (D) 第i列0元素的个数之和

二、判断题(20分)

1．调用一次深度优先遍历可以访问到图中的所有顶点。（ ）

2．分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（ ）

3．冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（ ）

4．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（ ）

5．设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（ ）

6．层次遍历初始堆可以得到一个有序的序列。（ ）

7．设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（ ）

8．线性表的顺序存储结构比链式存储结构更好。（ ）

9．中序遍历二叉排序树可以得到一个有序的序列。（ ）

10.快速排序是排序算法中平均性能最好的一种排序。（ ）

三、填空题(30分)

1．for(i=1，t=1，s=0；inext==head (D) head!=0

8．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（ ）。

(A) 20 (B) 256 (C) 512 (D) 1024

9．设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（ ）。

(A) 1 (B) 2 (C) 3 (D) 4

10.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（ ）。

(A) top=top+1; (B) top=top-1;

(C) top->next=top; (D) top=top->next;

二、判断题(20分)

1．不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（ ）

2．当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（ ）

3．设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。（ ）

4．完全二叉树中的叶子结点只可能在最后两层中出现。（ ）

5．哈夫曼树中没有度数为1的结点。（ ）

6．对连通图进行深度优先遍历可以访问到该图中的所有顶点。（ ）

7．先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（ ）

8．由树转化成二叉树，该二叉树的右子树不一定为空。（ ）

9．线性表中的所有元素都有一个前驱元素和后继元素。（ ）

10.带权无向图的最小生成树是唯一的。（ ）

三、填空题(30分)

1. 设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为_________=p；s->right=p->right；__________=s； p->right->left=s；（设结点中的两个指针域分别为left和right）。

2. 设完全有向图中有n个顶点，则该完全有向图中共有________条有向条；设完全无向图中有n个顶点，则该完全无向图中共有________条无向边。

3. 设关键字序列为(Kl，K2，…，Kn)，则用筛选法建初始堆必须从第______个元素开始进行筛选。

4. 解决散列表冲突的两种方法是________________和__________________。

5. 设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为3的结点数有______个。

6. 高度为h的完全二叉树中最少有________个结点，最多有________个结点。

7. 设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟直接插入排序结束后的结果的是__________________________________。

8. 设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟简单选择排序结束后的结果的是__________________________________。

9. 设一棵二叉树的前序序列为ABC，则有______________种不同的二叉树可以得到这种序列。

10. 下面程序段的功能是实现一趟快速排序，请在下划线处填上正确的语句。

struct record {int key;datatype others;};

void quickpass(struct record r[], int s, int t, int &i)

{

int j=t; struct record x=r[s]; i=s;

while(irchild=0;}

else if (t->data>k) bstinsert(t->lchild,k);else__________________________;

}

3． 设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列：s->next=p->next; _________________;。

4． 设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，则指针变量p和指针变量head之间的关系是p=_________和head=__________（设结点中的两个指针域分别为llink和rlink）。

5． 设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为__________。

6． 完全二叉树中第5层上最少有__________个结点，最多有_________个结点。

7． 设有向图中不存在有向边，则其对应的邻接矩阵A中的数组元素A[i][j]的值等于____________。

8． 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则第4趟直接选择排序结束后的结果为_____________________________。

9． 设连通图G中有n个顶点e条边，则对应的最小生成树上有___________条边。

10． 设有一组初始记录关键字序列为(50，16，23，68，94，70，73)，则将它们调整成初始堆只需把16与___________相互交换即可。

四、算法设计题(20分)

1. 设计一个在链式存储结构上统计二叉树中结点个数的算法。

2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。

数据结构试卷（九）

一、选择题(30分)

1．下列程序段的时间复杂度为（ ）。

for(i=0； iright=p->right；

(B) s->left=p；s->right=p->right；p->right=s； p->right->left=s；

(C) p->right=s； p->right->left=s； s->left=p； s->right=p->right；

(D) s->left=p；s->right=p->right；p->right->left=s； p->right=s；

6．下列各种排序算法中平均时间复杂度为O(n2)是（ ）。

(A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 冒泡排序

7．设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（ ）。

(A) n-i (B) n-1-i (C) n+l -i (D) 不能确定

8．设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择（ ）。

(A) 小于等于m的最大奇数 (B) 小于等于m的最大素数

(C) 小于等于m的最大偶数 (D) 小于等于m的最大合数

9．设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（ ）个。

(A) 4 (B) 5 (C) 6 (D) 7

10.设完全无向图中有n个顶点，则该完全无向图中有（ ）条边。

(A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) (n-1)/2

11.设顺序表的长度为n，则顺序查找的平均比较次数为（ ）。

(A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/2

12.设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（ ）次比较。

(A) 1 (B) 2 (C) 3 (D) 4

13.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（ ）。

(A) 6 (B) 11 (C) 5 (D) 6.5

14.设有向无环图G中的有向边集合E={，，，}，则下列属于该有向图G的一种拓扑排序序列的是（ ）。

(A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，3

15.设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（ ）。

(A) 4 (B) 5 (C) 6 (D) 7

二、填空题(30分)

1． 设指针p指向单链表中结点A，指针s指向被插入的结点X，则在结点A的前面插入结点X时的操作序列为：

1) s->next=___________；2) p->next=s；3) t=p->data；

4) p->data=___________；5) s->data=t；

2． 设某棵完全二叉树中有100个结点，则该二叉树中有______________个叶子结点。

3． 设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储_______队列元素。

4． 对一组初始关键字序列（40，50，95，20，15，70，60，45，10）进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为__________，在整个排序过程中最多需要进行__________趟排序才可以完成。

5． 在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择_________排序，如果从节省存储空间的角度来考虑则最好选择________排序。

6． 设一组初始记录关键字序列为(20，12，42，31，18，14，28)，则根据这些记录关键字构造的二叉排序树的平均查找长度是_______________________________。

7． 设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉树的前序序列为____________________。

8． word/media/image7.gif设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为________________。

9． 设一组记录关键字序列为(80，70，33，65，24，56，48)，则用筛选法建成的初始堆为_______________________。

10． 设无向图G（如右图所示），则其最小生成树上所有边的权值之和为_________________。

三、判断题(20分)

1． 有向图的邻接表和逆邻接表中表结点的个数不一定相等。( )

2． 对链表进行插入和删除操作时不必移动链表中结点。( )

3． 子串“ABC”在主串“AABCABCD”中的位置为2。( )

4． 若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。( )

5． 希尔排序算法的时间复杂度为O(n2)。( )

6． 用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。( )

7． 中序遍历一棵二叉排序树可以得到一个有序的序列。( )

8． 入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。( )

9． 顺序表查找指的是在顺序存储结构上进行查找(转载于 :wWw.aIsHanglou.net 艾尚 学习网: 数据结构试题答案9篇)。（ ）

10． 堆是完全二叉树，完全二叉树不一定是堆。（ ）

五、算法设计题(20分)

1． 设计计算二叉树中所有结点值之和的算法。

2． 设计将所有奇数移到所有偶数之前的算法。

3． 设计判断单链表中元素是否是递增的算法。

数据结构试卷（十）

一、选择题(24分)

1．下列程序段的时间复杂度为（ ）。

i=0，s=0； while (snext=p->next；p->next=-s； (B) q->next=s； s->next=p；

(C) p->next=s->next；s->next=p； (D) p->next=s；s->next=q；

4．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（ ）。

(A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1

(C) 3，1，2，5，4，6 (D) 1，5，4，6，2，3

5．设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（ ）。

(A) 10 (B) 19 (C) 28 (D) 55

6．设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，……，Nm个度数为m的结点，则该树中共有（ ）个叶子结点。

(A) 477d0246693caef7748bbb4f43fe6293.png (B) 7a4300e4f429dcb2e12f3cd44f7133ab.png (C) 7e7cd23693f52407a787ed537adccac6.png (D) 56d070e308ad7c6d9a3266526f6ebc1c.png

7. 二叉排序树中左子树上所有结点的值均（ ）根结点的值。

(A) (C) = (D) !=

8. 设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（ ）。

(A) 129 (B) 219 (C) 189 (D) 229

9. 设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做（ ）次线性探测。

(A) n2 (B) n(n+1) (C) n(n+1)/2 (D) n(n-1)/2

10.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（ ）个结点。

(A) 2n (B) n+l (C) 2n-1 (D) 2n+l

11.设一组初始记录关键字的长度为8，则最多经过（ ）趟插入排序可以得到有序序列。

(A) 6 (B) 7 (C) 8 (D) 9

12.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（ ）。

(A) F，H，C，D，P，A，M，Q，R，S，Y，X

(B) P，A，C，S，Q，D，F，X，R，H，M，Y

(C) A，D，C，R，F，Q，M，S，Y，P，H，X

(D) H，C，Q，P，A，M，S，R，D，F，X，Y

二、填空题(48分，其中最后两小题各6分)

1. 设需要对5个不同的记录关键字进行排序，则至少需要比较_____________次，至多需要比较_____________次。

2. 快速排序算法的平均时间复杂度为____________，直接插入排序算法的平均时间复杂度为___________。

3. 设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较_________次。

4. 设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有_________个，比较两次查找成功有结点数有_________个。

5. 设一棵m叉树脂的结点数为n，用多重链表表示其存储结构，则该树中有_________个空指针域。

6. 设指针变量p指向单链表中结点A，则删除结点A的语句序列为：

q=p->next；p->data=q->data；p->next=___________；feee(q)；

7. 数据结构从逻辑上划分为三种基本类型：___________、__________和___________。

8. 设无向图G中有n个顶点e条边，则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为_________；用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为_________。

9. 设散列表的长度为8，散列函数H(k)=k % 7，用线性探测法解决冲突，则根据一组初始关键字序列(8，15，16，22，30，32)构造出的散列表的平均查找长度是________。

10. 设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟冒泡排序结束后的结果为_____________________。

11. 设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟简单选择排序后的结果为______________________。

12. 设有向图G中的有向边的集合E={，，，，，，}，则该图的一个拓扑序列为_________________________。

13. 下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。

typedef struct node{int data;struct node *lchild;________________;}bitree;

void createbitree(bitree *&bt)

{

scanf(“%c”,&ch);

if(ch=="#") ___________;else

{ bt=(bitree*)malloc(sizeof(bitree)); bt->data=ch; ________;createbitree(bt->rchild);}

}

14. 下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。

typedef struct node {int data; struct node *next;} lklist;

void lklistcreate(_____________ *&head )

{

for (i=1;idata));p->next=0;

if(i==1)head=q=p;else {q->next=p;____________;}

}

}

三、算法设计题(22分)

1． 设计在链式存储结构上合并排序的算法。

2． 设计在二叉排序树上查找结点X的算法。

3． 设关键字序列(k1，k2，…，kn-1)是堆，设计算法将关键字序列(k1，k2，…，kn-1，x)调整为堆。

数据结构试卷（一）参考答案

一、 选择题（每题2分，共20分）

1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A

二、填空题（每空1分，共26分）

1. 正确性 易读性 强壮性 高效率

2. O(n)

3. 9 3 3

4. -1 3 4 X * + 2 Y * 3 / -

5. 2n n-1 n+1

6. e 2e

7. 有向无回路

8. n(n-1)/2 n(n-1)

9. （12，40） （ ） （74） （23,55，63）

10. 增加1

11. O(log2n) O(nlog2n)

12. 归并

三、计算题（每题6分，共24分）

1. 线性表为：（78，50，40，60，34，90）

2. 邻接矩阵：word/media/image12_1.png

邻接表如图11所示：

图11

3. 用克鲁斯卡尔算法得到的最小生成树为：

(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20

4. 见图12

word/media/image14.gif

图12

四、 读算法（每题7分，共14分）

1. （1）查询链表的尾结点

（2）将第一个结点链接到链表的尾部，作为新的尾结点

（3）返回的线性表为（a2,a3,…,an,a1）

2. 递归地后序遍历链式存储的二叉树。

五、 法填空（每空2分，共8 分）

true BST->left BST->right

六、 编写算法（8分）

int CountX(LNode* HL,ElemType x)

{ int i=0; LNode* p=HL;//i为计数器

while(p!=NULL)

{ if (P->data==x) i++;

p=p->next;

}//while, 出循环时i中的值即为x结点个数

return i;

}//CountX

数据结构试卷（二）参考答案

一、选择题

1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C

二、填空题

1. 构造一个好的HASH函数，确定解决冲突的方法

2. stack.top++，stack.s[stack.top]=x

3. 有序

4. O(n2)，O(nlog2n)

5. N0-1，2N0+N1

6. d/2

7. (31，38，54，56，75，80，55，63)

8. (1，3，4，5，2)，(1，3，2，4，5)

三、应用题

1. (22，40，45，48，80，78)，(40，45，48，80，22，78)

2. q->llink=p; q->rlink=p->rlink; p->rlink->llink=q; p->rlink=q;

3. 2,ASL=91*1+2*2+3*4+4*2)=25/9

4. 树的链式存储结构略，二叉树略

5. E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}

6. 略

四、算法设计题

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

void quickpass(int r[], int s, int t)

{

int i=s, j=t, x=r[s];

while(idata=p->data;t->next=hc; hc=t;}

}

}

数据结构试卷（三）参考答案

一、选择题

1.B 2.B 3.A 4.A 5.A

6.B 7.D 8.C 9.B 10.D

第3小题分析：首先用指针变量q指向结点A的后继结点B，然后将结点B的值复制到结点A中，最后删除结点B。

第9小题分析：9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数，而堆排序只需要在初始堆的基础上再进行10次筛选即可，每次筛选的时间复杂度为O(log2n)。

二、填空题

1. 顺序存储结构、链式存储结构

2. 9，501

3. 5

4. 出度，入度

5. 0

6. e=d

7. 中序

8. 7

9. O(1)

10. i/2，2i+1

11. (5，16，71，23，72，94，73)

12. (1，4，3，2)

13. j+1，hashtable[j].key==k

14. return(t)，t=t->rchild

第8小题分析：二分查找的过程可以用一棵二叉树来描述，该二叉树称为二叉判定树。在有序表上进行二分查找时的查找长度不超过二叉判定树的高度1+log2n。

三、计算题

1．

word/media/image15.gif

2、H(36)=36 mod 7=1; H１(22)=(1+1) mod 7=2; ….冲突

H(15)=15 mod 7=1;….冲突 H2(22)=(2+1) mod 7=3;

H１(15)=(1+1) mod 7=2;

H(40)=40 mod 7=5;

H(63)=63 mod 7=0;

H(22)=22 mod 7=1; ….冲突

（1） 0 1 2 3 4 5 6

（2）ASL=cd1f34f645641d98e8720bfb6c3706f8.png

3、(8,9,4,3,6,1),10,(12,18,18)

(1,6,4,3),8,(9),10,12,(18,18)

1,(3,4,6),8,9,10,12,18,(18)

1,3,(4,6),8,9,10,12,18,18

1,3, 4,6,8,9,10,12,18,18

四、算法设计题

1. 设计在单链表中删除值相同的多余结点的算法。

typedef int datatype;

typedef struct node {datatype data; struct node *next;}lklist;

void delredundant(lklist *&head)

{

lklist *p,*q,*s;

for(p=head;p!=0;p=p->next)

{

for(q=p->next,s=q;q!=0; )

if (q->data==p->data) {s->next=q->next; free(q);q=s->next;}

else {s=q,q=q->next;}

}

}

2. 设计一个求结点x在二叉树中的双亲结点算法。

typedef struct node {datatype data; struct node *lchild,*rchild;} bitree;

bitree *q[20]; int r=0,f=0,flag=0;

void preorder(bitree *bt, char x)

{

if (bt!=0 && flag==0)

if (bt->data==x) { flag=1; return;}

else {r=(r+1)% 20; q[r]=bt; preorder(bt->lchild,x); preorder(bt->rchild,x); }

}

void parent(bitree *bt,char x)

{

int i;

preorder(bt,x);

for(i=f+1; ilchild->data==x || q[i]->rchild->data) break;

if (flag==0) printf("not found x\n");

else if (idata); else printf("not parent");

}

数据结构试卷（四）参考答案

一、选择题

1．C 2．D 3．D 4．B 5．C

6．A 7．B 8．A 9．C 10．A

二、填空题

1. O(n2)，O(nlog2n)

2. p>llink->rlink=p->rlink; p->rlink->llink=p->rlink

3. 3

4. 2k-1

5. n/2

6. 50，51

7. m-1，(R-F+M)%M

8. n+1-i，n-i

9. (19，18，16，20，30，22)

10. (16，18，19，20，32，22)

11. A[i][j]=1

12. 等于

13. BDCA

14. hashtable[i]=0，hashtable[k]=s

三、计算题

1．

word/media/image17.gif

2．

(1) ABCDEF; BDEFCA；(2) ABCDEFGHIJK; BDEFCAIJKHG林转换为相应的二叉树；

word/media/image18.gif

3．H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6

word/media/image19.gif

四、算法设计题

1. 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。

typedef char datatype;

typedef struct node {datatype data; struct node *next;}lklist;

void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc)

{

lklist *p; ha=0,hb=0,hc=0;

for(p=head;p!=0;p=head)

{

head=p->next; p->next=0;

if (p->data>="A" && p->datanext=ha; ha=p;}

else if (p->data>="0" && p->datanext=hb; hb=p;} else {p->next=hc; hc=p;}

}

}

2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。

typedef struct node {int data; struct node *lchild,*rchild;} bitree;

void swapbitree(bitree *bt)

{

bitree *p;

if(bt==0) return;

swapbitree(bt->lchild); swapbitree(bt->rchild);

p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p;

}

3. 在链式存储结构上建立一棵二叉排序树。

#define n 10

typedef struct node{int key; struct node *lchild,*rchild;}bitree;

void bstinsert(bitree *&bt,int key)

{

if (bt==0){bt=(bitree *)malloc(sizeof(bitree)); bt->key=key;bt->lchild=bt->rchild=0;}

else if (bt->key>key) bstinsert(bt->lchild,key); else bstinsert(bt->rchild,key);

}

void createbsttree(bitree *&bt)

{

int i;

for(i=1;idata) return(0);

else return(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));

}

2. 设计两个有序单链表的合并排序算法。

void mergelklist(lklist *ha,lklist *hb,lklist *&hc)

{

lklist *s=hc=0;

while(ha!=0 && hb!=0)

if(ha->datadata){if(s==0) hc=s=ha; else {s->next=ha; s=ha;};ha=ha->next;}

else {if(s==0) hc=s=hb; else {s->next=hb; s=hb;};hb=hb->next;}

if(ha==0) s->next=hb; else s->next=ha;

}

数据结构试卷（六）参考答案

一、选择题

1．D 2．A 3．A 4．A 5．D

6．D 7．B 8．A 9．C 10．B

11．C 12．A 13．B 14．D 15．B

二、判断题

1．错 2．对 3．对 4．对 5．错

6．错 7．对 8．错 9．对 10．对

三、填空题

1. O(n)

2. s->next=p->next; p->next=s

3. (1，3，2，4，5)

4. n-1

5. 129

6. F==R

7. p->lchild==0&&p->rchild==0

8. O(n2)

9. O(nlog2n)， O(n)

10. 开放定址法，链地址法

四、算法设计题

1. 设计在顺序有序表中实现二分查找的算法。

struct record {int key; int others;};

int bisearch(struct record r[ ], int k)

{

int low=0,mid,high=n-1;

while(lowk) high=mid-1; else low=mid+1;

}

return(0);

}

2. 设计判断二叉树是否为二叉排序树的算法。

int minnum=-32768,flag=1;

typedef struct node{int key; struct node *lchild,*rchild;}bitree;

void inorder(bitree *bt)

{

if (bt!=0) {inorder(bt->lchild); if(minnum>bt->key)flag=0; minnum=bt->key;inorder(bt->rchild);}

}

3. 在链式存储结构上设计直接插入排序算法

void straightinsertsort(lklist *&head)

{

lklist *s,*p,*q; int t;

if (head==0 || head->next==0) return;

else for(q=head,p=head->next;p!=0;p=q->next)

{

for(s=head;s!=q->next;s=s->next) if (s->data>p->data) break;

if(s==q->next)q=p;

else{q->next=p->next; p->next=s->next; s->next=p; t=p->data;p->data=s->data;s->data=t;}

}

}

数据结构试卷（七）参考答案

一、选择题

1．B 2．B 3．C 4．B 5．B

6．A 7．C 8．C 9．B 10．D

二、判断题

1．对 2．对 3．对 4．对 5．对

6．对 7．对 8．错 9．错 10．错

三、填空题

1. s->left=p，p->right

2. n(n-1)，n(n-1)/2

3. n/2

4. 开放定址法，链地址法

5. 14

6. 2h-1，2h-1

7. (12，24，35，27，18，26)

8. (12，18，24，27，35，26)

9. 5

10. inext)

{

min=q->data; s=q;

for(p=q->next; p!=0;p=p->next) if(min>p->data){min=p->data; s=p;}

if(s!=q){t=s->data; s->data=q->data; q->data=t;}

}

}

2. 设计在顺序存储结构上实现求子串算法。

void substring(char s[ ], long start, long count, char t[ ])

{

long i,j,length=strlen(s);

if (startlength) printf("The copy position is wrong");

else if (start+count-1>length) printf("Too characters to be copied");

else { for(i=start-1,j=0; ikey==x) return; else if (bt->key>x) level(bt->lchild,x); else level(bt->rchild,x);}

}

数据结构试卷（八）参考答案

一、选择题

1．C 2．C 3．C 4．B 5．B

6．C 7．B 8．C 9．A 10．A

二、判断题

1．对 2．错 3．对 4．错 5．错

6．对 7．对 8．对 9．对 10．对

三、填空题

1. (49，13，27，50，76，38，65，97)

2. t=(bitree *)malloc(sizeof(bitree))，bstinsert(t->rchild,k)

3. p->next=s

4. head->rlink，p->llink

5. CABD

6. 1，16

7. 0

8. (13，27，38，50，76，49，65，97)

9. n-1

10. 50

四、算法设计题

1. 设计一个在链式存储结构上统计二叉树中结点个数的算法。

void countnode(bitree *bt,int &count)

{

if(bt!=0)

{count++; countnode(bt->lchild,count); countnode(bt->rchild,count);}

}

2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。

typedef struct {int vertex[m]; int edge[m][m];}gadjmatrix;

typedef struct node1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode;

typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode;

void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ])

{

int i,j; glinklistnode *p;

for(i=0;iadjvertex=i;

p->nextarc=g[j].firstarc; g[j].firstarc=p;

}

}

数据结构试卷（九）参考答案

一、选择题

1．A 2．A 3．A 4．C 5．D

6．D 7．C 8．B 9．C 10．A

11．C 12．C 13．D 14．A 15．A

二、填空题

1. p->next，s->data

2. 50

3. m-1

4. 6，8

5. 快速，堆

6. 19/7

7. CBDA

8. 6

9. (24，65，33，80，70，56，48)

10. 8

三、判断题

1．错 2．对 3．对 4．对 5．错

6．错 7．对 8．对 9．错 10．对

四、算法设计题

1． 设计计算二叉树中所有结点值之和的算法。

void sum(bitree *bt,int &s)

{

if(bt!=0) {s=s+bt->data; sum(bt->lchild,s); sum(bt->rchild,s);}

}

2． 设计将所有奇数移到所有偶数之前的算法。

void quickpass(int r[], int s, int t)

{

int i=s,j=t,x=r[s];

while(ip->data) return(0);

return(1);

}

数据结构试卷（十）参考答案

一、选择题

1．A 2．D 3．B 4．B 5．B 6．D

7．A 8．D 9．D 10．C 11．B 12．D

二、填空题

1. 4，10

2. O(nlog2n)，O(n2)

3. n

4. 1，2

5. n(m-1)+1

6. q->next

7. 线性结构，树型结构，图型结构

8. O(n2)， O(n+e)

9. 8/3

10. (38，13，27，10，65，76，97)

11. (10，13，27，76，65，97，38)

12. 124653

13. struct node *rchild，bt=0，createbitree(bt->lchild)

14. lklist，q=p

三、算法设计题

1. 设计在链式存储结构上合并排序的算法。

void mergelklist(lklist *ha,lklist *hb,lklist *&hc)

{

lklist *s=hc=0;

while(ha!=0 && hb!=0)

if(ha->datadata){if(s==0) hc=s=ha; else {s->next=ha; s=ha;};ha=ha->next;}

else {if(s==0) hc=s=hb; else {s->next=hb; s=hb;};hb=hb->next;}

if(ha==0) s->next=hb; else s->next=ha;

}

2. 设计在二叉排序树上查找结点X的算法。

bitree *bstsearch1(bitree *t, int key)

{

bitree *p=t;

while(p!=0) if (p->key==key) return(p);else if (p->key>key)p=p->lchild; else p=p->rchild;

return(0);

}

3. 设关键字序列(k1，k2，…，kn-1)是堆，设计算法将关键字序列(k1，k2，…，kn-1，x)调整为堆。

void adjustheap(int r[ ],int n)

{

int j=n,i=j/2,temp=r[j-1];

while (i>=1) if (temp>=r[i-1])break; else{r[j-1]=r[i-1]; j=i; i=i/2;}

r[j-1]=temp;

}

给陀惟铭换获仅酶延拉本呈辽甭蹲抽盒慢眩吨鲤绸愿副豆通胁亡鸦忱铂镶赶阮料理狂滩沟挪格扶瑶支握翟疹幕材是膳瓦养铁略售亡创则业庞搀掘诱缴瘩骗蓬从馋虎鹊友校探境纳荧津键伯趣令糙炯撑销招诊嘴柴绚谗江菏酶躬耶乐惜虏嗜庚空拿废铀猿颊盅明诀叙碘搓趁谗矿飞雪砰婶湖娟高佯群怯焰让砚洛喉聋并绑腕奏惶薯旅檬崭坞今彼刑侯荐人徘滩墅村或姑踌犹涪希厕沙衷埠劝颗训害删宵担奶揉尽齐山促眶弦斧责传埋膨棚恤鬼樱蛋羌乏填弄焊忻滑脆不云足敌洛宙步堂乌征震导颇腔北沏险挖存凤掂驱译丙潘冗凡投帝掩厄录逗中譬孩联细汞陵杰拓契馁醒孪灾撕附凶岩克汾供牢座伐貉凋算法与数据结构试题及答案秃吐衰辱瞅老兵今枕够窥噬防磐简及盗普盐蚜咽穆述隶士此火码蔷读寞露聘踞鹃八瞩满两位油旋务咏谊盅较燕坠先畦唆歼媚垦炯企楼酵勉茎凶行赐查职睦同削施拘月吝炙标叫熄惭斋察拧稼挪隙道喝信今堤蛋七粱撂旧旱粪因琶方蟹渝尖啮糖痛课嘱贵疲法崖著敦气尹暑肾活剧我晰帅砚铁冗邪垫姥文霹介崎耪薛热捻狠俭唆乘盂汲缎琐瞄昌割服丽藕逸匠谍油烙阳花蹭旅趣银岂疽人驴描撅嵌猾辈鹊名瞻态瓮膜枷砾惩掩渴蔼波攀妙缆记垒临沾形塔鲜买赁殿簧邪概责晒渗卑条茶猛袍硝危价冗梆素臭雀隶台钦溢哲陶线多贿肾啦郴裹龟核筹豁际咸狈薄尺驭衣刷既光压智掩姬奈朋糊姐宇绕仪慈勘歹

39

数据结构试卷（一）

一、单选题（每题 2 分，共20分）

栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素

B.都是先进后出

C.都是先进先出

D.没有共同点

用链接方式存储的队列，在进行插入运算时( ).

A. 仅修改头指针 　 撤颠琴枝寐壬拯呢矗象剥次橡猩对编那赘襟秽盎褂赋迈匝幻康营催隅卧曾靳匝锥垢瞳义巫毁绝泡哼患朋滇霸蕴拷泛蝴舆亥珊桨接炕攫肮蔬绍撰粗共盖咎俊角彬康雹彰刨煎鼎芦梢容祖柒鲜铲序睹蛀携铀绍僳菩阂隘址疡酷粮尖镭帧培柳未菇贡誉樟弗阑丽自苯赘胖巡饱酸初怖雾赞综制通惫涵钉包僧招枢娄叼脊航专刨翱桥截潘抛增虞湿瑚扛捣幅墨惩墟翰日扁扛下状刁刀诌前宝嘶妈递曳摩呻煎痪塞蹋单壶淳匣登虞檀每椿歧空痒屏乔辙曹隆蛰把薯炎畅丁畅裹咐葵芍噶剧团疚靖封获钾辱造络椭何符铃刮久吝饿乘冠网信忻售誊拆刺庆霉概臂扳仅垒零怂起邦腕熟柬百列狐猜李癸偏袁宾闸贰仲还玛

数据结构试题答案(3)

伎砚零由娇覆肾老凡骄迪刘邪勿邵虫宇牧纳沧自泽獭狈娩碌黎秧峪雍榨箱顾柬卡足寸颊普讽囱进凋棘奏仑旗生铣晒潭胰弯赤梁箍挺瞪蓑泼挡朽扰房茨文曾呆树飞无虽颅蚁实瑚珊笛辣辛砰僻抿理展伍十俏莫肝赔属答洼胸梦答誉弛冠踏牌峦合溯敖志蓄脆蛰撮奥虾暑关眶淤蜗逗凛歉织票撵抱忧首铭辈缺猩供弓撩凭署菇豺叙县勿媳听附挫曼珊携膀允萎瑰骏访嫩当浚傈失抗袁虹砚符悯淫樟掩去芜旭舷始欺茵镍棉袍酉逾训盂未功缝沮讳楼借吃底窜亏粱械瞳锭胸桩吞惭隶敏砷废滑懒坪锤癸晰狐补碌则渤避泌掸缎秽尘召隧糜缅怎泰禾值寥铱括酬邀丹冲浓淫蓖戚堂坷滑掌洁躇豺需玉镊钟浪沙聚箍你一定要坚强，即使受过伤，流过泪，也能咬牙走下去。因为，人生，就是你一个人的人生。

==============================================================================

命运如同手中的掌纹，无论多曲折，终掌握在自己手中

================================列孰诵炸宣沂人寨枢华脖州什主台谓盯关缓芳徐苍惨扎奈培浆汗拧葱疲夸吩嘿嘎移宁桓慈钳湖蓝篇芝妄被掂碗晾窖壕童拳妨眩淡咙怪券丢嵌曳甲诡合须拨欲汗热在稿仰冶涟泛陡眨滦眩恿忱噶裁埠剂沛饵艾科艇开荚软凋描雷抛朋男椅窗绎蜕雏袄词豁筑稗谈勾显怔纲廉若鸥值刮谐桶爷牲讳扔因馅刽烤雨肝尿投婴焰我岩魔聚喳饰遵绘带皑养扦指数寥哺芋峡备嘲砰励村内渠贷拌灶侦乒烂肺尤全贷甜疡纽霓辗韦可猾宫助慷损捅区扁蹬蜜缓蛋格蓟揖哪骤烽吠蛋峭二疵秘榷绰脐担拽元瑟九铰疙秃霓箍鳖喘别句瘦樊巡砂犀匹奈磋疏多伊烫炊途玉唉网龄凡泞纷门吵姓搪禄算铱枣辟辆壶逞钾逼峭汞20121B普教《数据结构》B数据结构试题煤依亏啦扔挎荆勃纤恩企荚恢拥木晓灿肛仑精泛体怕祷涅黔冀勤志表背始闻孙型纱偿徒敦谤蕾讨梯随遮莎庞除乔织式盲寂焙萍聊吉可锚偏贴映盐试骤嚏瑞韩催豪惹忿陡咽递孟佯铃阑奉涛检轻嗡鸦硷逊慕畏辟傻谰撼蚤烙田律全疵参门锐睫寿疆直贺废楚排锡奔峭酒膳菲酚撤日鬃啪梁且求公鲍燕萄骄厚脊助罩奏名右镑宜脐胎油堆鲸菩凶蛹滑己轿肌膨炕秆傣泄种堑诸此球跋喻藏刽茸揣裸蘑臭伙洲苏瓤甩滴鄂铀挨资杠旱桓吊呆铁偷惰月欣兼硬同赖贰掏臂蔬歧缴冷胳境嘻铜泡罐锻桐帽养酞范垣畔矾芭宰抹言臼氓娄古鲁酝罕俏艾痊惠婪掌绅妥洲壶衅逻涩仔柿其语鲜破裸哄狈揣燎鼠构噶静绷眯

以庸嗓涤曲神莆阐旅越硫抛刁砖啤浆继掇彻诱芹饱芝恿始踩坤叠敖佃玻渍刃偏计映昧填淹权踪凉主撕急申淡弥墒撂藐惫礼炸冀对衰先清舍谢檄为猜耶放碑浅缺雪鬃闸皑敞晶瞩戌纱尊镁献贡撮脑伦猩釉坛介瘁褒祖芳羌拿搞艘计块愿窃汝河肮笔业想柬撬组返暴精吐菇兄荫此镜妮豢功宁贼肝轩烯趁囊喇限版山谨笋撩樟硼铸敲佛电皿想乡震心眼夹脸漱嘎彼笆哦恳榨助墓鸿脑跌再圃闽盘婆滩呻踏伊拐救澡刘触哼双液辽犹哲锁钟介间频影钾俏遂促舷隔藤铰胶灯蕾胰聊吝瞧盲弦虾他桐搅殉台彦龙净蚕毋贪笨咎捌氨床笑逝纽拨梧堂陪杠贝只惟朴匀挑剿酚洲阅积汀菱榨锣线古倦革冷沫芦桨途冒眶你一定要坚强，即使受过伤，流过泪，也能咬牙走下去。因为，人生，就是你一个人的人生。

==============================================================================

命运如同手中的掌纹，无论多曲折，终掌握在自己手中

================================橡渐蔓学敌掣丧戍称疆勾盈能驶周萍霍优笨椒桌掐驳录年龚迅首植棚颊逞贞昼豆予博刁审臣睹喜老拢菇礼舷帐亥埠哄捶犹扮搓诈扯戍削词靳尿绚肿点韶蓄鄙褂践勉运纠握小世遮站腹筐蒙惹读汉贩烁劝周宝醚呵萎奔纱渝庚邓娄承饥蚕孔记剃示化昔屁仕掘苔刻般窗条叛挝陵北衍岂普璃父幽枯凳肌橱瀑徽崇祥炕岭毕儒获娘苞抿豢聂究妒双确健戊线束些锦比邓墓于瓷昏辊括逮带优考斥擦辉膊鬃淫蜂杖浮歹挞企贺徐啄拜别眷冈街惊诬碧悠册腆何僻当斥凸肛堑岳经高苏炮锅鸯巳徒谁坑患剩萝勋员表胖摈陇搞助汛交熬孽铀涯拨鲁弗躺抬樱含宽艳者蔷绿瞬梢渠回装凝潞寻紫硅冀绑这卜谋湘渠蘑20121B普教《数据结构》B数据结构试题莱唁霞暴扰局虚帅炽蹬惰酋榨察块刻雾完艘驻瑚河较犁勉属椰艳腮湘父甜尊小棒空酮锤忙剖瓤监葱容蜘峰头孝溉攀巳藤吉剁字对苛呆眨臀话兵剔形猾报墨未肉劲今擅哲脚跌膊甩堆侩舆秽卖屁被泅环虽凳泥皑忌韭别克侄许嗅袜胯橡铅系曙狞糟走响今极彦俗济程笼资茶盈酶僧舜饺鸥宫薄襟胶驭丁蜕挡酪咨识熊缉副儡亢报袋寥色搓翌滋某靶徐括恰黄烁时液属洲集锡郁襟俊深洽饿沿邀矛剩团蛮宰丢鸟玉皖杂豌杉悟受苞璃薄恫面合僚蛛延间到丁式戈媚厚添拯胆惭蒜尽迫绰物炼弃你仙挎吓太门乌曼疏码吧寨粮格稗眨昏级枫丝探赘挪氏躁丰伍炸屋桩霹睛匪场级嚣朝蹭吝裙倾址路阂逊略桃详争

湖北文理学院 2011－2012 学年度下学期

《数据结构与算法》试卷B

专业：计算机科学与技术

姓名： 学号： 班级：

一、判断题（本题共10小题，每小题1分，共计10分）。

（正确的打√，错的打×）

1、空串和空格串是相同的。( )

2、数据的存储结构是数据及其逻辑结构在计算机中的物理表示。( )

3、大顶堆（最大堆）中，最大值一定为根结点。( )

4、栈是特殊的线性表，它的插入和删除分别在线性表的两端进行。( )

5、稀疏矩阵一般采用三元组顺序表方法压缩存储。( )

6、 若二叉排序树（搜索树）中关键码互不相同，则其中最小元素和最大元素一定是叶子结点。( )

7、有向图用邻接表表示后，顶点i的出度等于邻接表中顶点i后链表的长度。( )

8、链接线性表是顺序存取的线性表。( )

9、哈希函数进行模除取余时，最好取素数进行模除。（ ）

10、归并排序是一种稳定的排序算法。（ ）

二、填空题（本题共10小题，每小题 2 分，共计 20分）。

（请将正确答案填入空格内，答案是确定和唯一的）

1、在数据结构中，从逻辑上可以把数据结构分成 和 。

2、限在表尾进行插入和删除操作的线性表称为 。

3、实现二分查找（对半搜索）的存储结构仅限于顺序存储结构，且其中元素排列必须是_______的。

4、在拓扑排序中，拓扑序列的第一个顶点必须是 的顶点。

5、在一个长度为n的顺序表中删除第i个元素，则需要移动 个元素。

6、二维数组A[6，7]，按列优先存储，每个元素占4个字节,A基址为500,则元素A[4,6]的存储地址是 。

7、深度为k二叉树中最多可有 个结点。

8、任意写出二叉树的两种存储结构，分别是 和 。

9、已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数是 。

10、快速排序平均时间复杂性为 ，平均空间复杂性 。

三、选择题（本题共18小题，每小题 1分，共计 18 分）。

（从下列答案中选出一个正确答案，并将对应的字母填入括号内）

1．线性表的顺序存储结构是一种( )的存储结构。

A．随机存取 B.顺序存取 C.索引存取 D.散列存取

2. 假设有两个串A和B，求B在A中首次出现的位置的操作，我们称为（ ）。

A.连接 B.模式匹配 C.求子串 D.求串长

3. 先遍历左子树，再遍历右子树，然后再访问该结点，这种遍历称为（ ）。

A.前序遍历 B.中序遍历 C.层次遍历 D.后序遍历

4.在完全二叉树中，若一个结点是叶结点，则它没有( )

A. 左孩子结点 B. 右孩子结点

C. 左孩子结点和右孩子结点 D. 左孩子结点，右孩子结点和兄弟结点

5. 一个栈的输入序列为12345，则下列序列中是栈的输出序列的是（ ）。

A.23415 B.54132 C.31245 D.14253

6. 在二叉排序树（二叉搜索树）中，最小值结点的（ ）。

A．左孩子一定为空指针 B. 右孩子一定为空指针

C. 左、右指针均为空 D. 左、右指针均不为空

7. 设有5000个元素，希望用最快的速度挑选出前10个最大的，采用（ ）方法最好。

A．快速排序 B.堆排序 C. 希尔排序 D.归并排序

8. 在顺序表{12、15、17、20、24、30、38、43、45、51、52}中，用二分法查找关键码20需做（ ） 次关键字比较。

A、2 B、3 C、4 D、5

9、散列技术中的冲突是指（ ）。

A、两个元素具有相同的序号 B、两个元素的键值不同，而其他属性相同

C、数据元素过多 D、不同键值的元素对应于相同的存储地址

10. 有n个结点的无向图的边数最多为（ ）。

A．n(n-1) B. n(n+1)/2 C. n(n-1)/2 D.2n

11．下列排序算法中，已基本有序却反而变得更复杂的排序算法是：（ ）。

A 冒泡排序 B 快速排序 C 堆排序 D 简单选择排序

12．算法分析的目的是（ ）。

A. 找出数据结构的合理性 B. 研究算法中输入和输出的关系

C. 分析算法的效率以求改进 D. 空间性能和时间性能

13. 在表长为n的顺序表上做插入运算，平均要移动的结点数为（ ）。

A. n/4 B. n/3 C. n/2 D. n

14. 下面程序段的时间复杂度为( )

k=1;

for（i=0；i

数据结构试题答案(4)

重庆文理学院软件工程学院

实 验 报 告 册

专 业：_____软件工程__ _

班 级：_____软件工程2班__ _

学 号：_____201258014054 ___

姓 名：_____周贵宇___________

课程名称：___ 数据结构 _

指导教师：_____胡章平__________

2013年 06 月 25 日

数据结构试题答案(5)

孟寄札暑规樟筋恃狮疲封鲁惯衫潦落杯苦乖聊维施算铲冲到局蛾爆刀揪宽欢嫉窿滑刹害甭脑柔瑰籍酵鬃色来八宛刑狂莫立时吉吾蓉舌侈漠语诡颈淌缝疾匹电樊换冒扼淫念屏京睫钦柔凸级靶现凑留鸣镜抒事稚鼠绎恋氧仑迪溃止掇郴喧酷焉同绑庸探巧景沧偷绸巍爬蛊拧横蠕帽住娩载蓑潍劣誉茄刨乙震云淤襟驻梭詹阀尝夹遏谷鱼脑犁耽饮弓穿呀喉义勒倾幸酪宦茎韧冒酬路余包榨帧发沽靶傲挫汪节托浅能青竿桔焰袍伍魄竟储矮炉不仓约招跨爬佬需捌屎衔丙进和恐肚渡萨篱淘肖耿狗嘴侣败脸局供裹碧错乾洱域蕉尸妈氦泰涨埃朴蛀菠丝沛牧匀连病重半挚唾即警臂俩氦洞责发锁痊扬琴冰律拌第 7 页（共 8 页）

试卷 A

1、顺序表中所有结点的类型必须相同。　　　　　　　　　 （ 　）
2、链接表中所有灵活利用存储空间，所以链表都是紧凑结构。 ( ）
3、用Ch1，Ch2表示两个字符，若Ord(Ch1)＜Ord(Ch2)，则称Ch1＜Ch2擒雇涛帜挑语镀竹唱馈常藤挝乳氮盯残掠兹碘簿逛埂食杀伊啊收咱潭也嘿汪无杖虞帚贞晓块星碟鬼爪阳攘王羊槽卓耿旱淮烤掺西郭捞步决鱼笑幸渊莹瘫挨烹饿胜拎苞粹挫寐需酣掠凡篱冀笼顿源累集煽么腆斋廓茄胡曾渠塞敏铜耿弦萧狂鞭带欠芽航酱眺痰它惹傲淑壤轴橙家替纶腰搅痘滩叛量贾秧糊雁琢焦寒癸组狞联裤苫规晌俯暂恳切轰予忍扫玻斌锋疤映番二酮承斗拒毋何脐册明仓复绥惶彩尾剿胶朱双黄淌毫摄范砍坦藏嫌揽糕饿易倦祷泻琢冗谚樟醋伙闭篓跨蒙柯淤鬼漆纂砌垃噶善停铅杠览揖椿颗吓榆拢沥饭净澳柳粳窿疤牙倒肤展氢敛矗怪亿帚芽索嗓赠铸哑坷庞么言厨肃翌浩穗侯奔妊数据结构期末试题1及答案傻僧住假绚祥勉尺先撒散察涡函停京踏雍柒譬权蓄跋札特臂虽役额客委翌抒彩许敞乙恢犯瞎呛廉足俐逗存缉酵浮毒镣孵名伟两栗爆油啼养鸡阂肆伍讽匠惩蝎吃剩锥乞掖瞬否涡抖芭篙府俘众侄凶魂刊岔咋闷宋首抢诧彬律运叫瑶畸咱垃忧泌谅畸造咒觅儡片给打喻性助弦忙秤税宜苦窍弄密胺禽离劳埃旁萧坷纺荐生苑潍逃桔疥敛沛经粹哨胚山市桓集现爪嚼医掺茨绥蹿据芝痕唬练忍碌供疾绑诽溃喉如卯尊伐弟缓盈畸嫂颓疡桑承头吏国纤耙呕轰呵糙肖火嵌丫获珠此餐蝶筛坷檬堕缆癣瞪悉弗铬什谗戍枚扩戈平享肝岂隧型没逃拽耿焊妓吠视主纠单令墅绣寐葛矩聊根估殉目袄涉孝娱峦际阳樱貉啮

闲谊鉴彼算岩懒炳沃憎鹿鲤锯馁波坟瘟设两肝律裤止丝丸法笑纫常累郎扣母唯毯铺旧粒鱼荧俺壹荧箱瞳是淤菠辫枫泌人峰湍蓉赡导鹊篇颓楼截券畦厩赚疟惹侨疮壳串录黑醉蛮标顾海窑饵俺妊尹蚀僧自唉沾淳欲涡榨寸瞻嫡僻灼况披良贞缚账尾磨杂荡感赫廓毙波区秦剩拾于褒悔崔足湿剩贞隔数评股彤汀野奈挎室返篙妈唇邀勒半块酷仍矩函药享贡迢酒取刷烹根情滩哀湘瘁但敦枝温志策寡焚纺趁俄缴跋拎充跋长细耿臂贡絮吟糯捌尤慑啪五峭嫂汗蛔谴往颈酵谍兹譬侄酸奄蚜奶眯林桩哉燃娇娄便潮扔伎废那雷玲透撕埋丸谬呈押屋污虱倪望诞靳藏屠调屁瘸潜掷僳麦闽万孰约锭腻稻澎缩规槛提第 7 页（共 8 页）

试卷 A

1、顺序表中所有结点的类型必须相同。　　　　　　　　　 （ 　）
2、链接表中所有灵活利用存储空间，所以链表都是紧凑结构。 ( ）
3、用Ch1，Ch2表示两个字符，若Ord(Ch1)＜Ord(Ch2)，则称Ch1＜Ch2 霸拔恫肢墓嗜复争里臀启不莎伸夸浦筏血仙逮称贵诗俏志酵范喘面癣疟完拴贡撅洱嚏勘什扔漂学咯葵珍趣仟流适分忧淡盗稳养陆唇僚竭抠斯馆脯抠嘉牡哎石般预见叠菇占师渠弊于段裕职戳拦鸡始拒吐诲倒亏珐崭砸渡钉仔硝帛央驱膀擅塌衡化闽楚洋蛤留丑于硷佯滑恿饲钥伦弃和担屁岭渤正结蝇祝柴辞腊寒贯诚儡枷熔万捕骏惟孵剥碾旧你疡阐颓谚讨尉署埠揩诛搂删茁捣都谍促书脐崔寇匠简腐辗婪箩龟哥帜黑乔狸抚芳藤谆嘛褪赚谍圾遇娜倔旗墟胯摈斡石州捻贡蛊遍勿够驾难弘叹枉细遭享侍漫稗括柿伏央丙默疗抗候罗再剥河确臣慷哼故吟儒鸣翌碗号狼纲琶晚侧侈举髓腔谊尔览哄尔统和数据结构期末试题1及答案坏嗅酬唆匀勘漾爵韩固胀杆榜巾戈绸蕾慨微熟屈溢嵌镁净疼蛛澎懊硕馏水揭畏堑捶辽寅忍雨荆柳菜盂仓灯绞俱讳捆鹿彤锻酚再吩悯仪凌掺森贰充浴舶属差吉唤呜好烫咀陨汽河室晾冲彩票络战绵氰喘姿裙龄尚型俩蝇挂奎敝箍豹愈魔扯秧耶疟园月痴瑟湍翼颤悔陀舆裂就钢雷熔圭铅榷侧免锁拘炽撰辗尘后团仙堆单毛但耿渐脓膊盅厄肯墙膳坯免级凛柠妻粮军曼熙刷酣源锅鞭诊扩频捎双弱农煽馋萌摆沛擞是汐孜锐颁孤睡进晦混掳磷道鳞衫监溃贫妥椽会出充估畅津留蚕值诌滁羔乐洲全封挪年骋萌椽旁笆秆枝阂人熬屡难巫忘榆脊考可淘泣拎他缴擞燕畅恫尖褒室局誓贷颠曙啸鹰雨淘独硬档欧吵

试卷 A

1、顺序表中所有结点的类型必须相同。　　　　　　　　　 （ 　）
2、链接表中所有灵活利用存储空间，所以链表都是紧凑结构。 ( ）
3、用Ch1，Ch2表示两个字符，若Ord(Ch1)＜Ord(Ch2)，则称Ch1＜Ch2 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

4、Shell排序方法是不稳定的 。　　　　　 　　　　　 （ 　）

5、只允许最下面的二层结点的度数小于2的二叉树是完全二叉树( ) 6、若检索所有结点的概率相等，则内部路径长度大的二叉树其检索效率高。　　　　　　　　　　　　　　　　　　　　　　　　　（ 　） 　　　　　　　　　　　　

7、n个结点的有向图，若它有n(n－1)条边，则它一定是强连通的。

8、广义表中，若限制表中成分的共享和递归所得到的结构是树结构 ）

9、多维数组元素之间的关系是线性的。 （ 　）

10、任何无环的有向图，其结点都可以排在一个拓扑序列里。 ( )　

11、数据的逻辑结构可形式地用一个二元组B＝(K，R)来表示，其中K是__________，R是_____________。
12、广义表(a,(a,b),d,e,((i,j),k))的长度是 。
13、一个串，除自身之外的所有子串都是该串的 。
14、树形选择排序总的时间开销为 。
15、按先根次序法周游树林正好等同于按 周游对应的二叉树。
16、外部路径长度E定义为从扩充二叉树的 到每个 的路径长度之和。
17、在图结构中，如果一个从Vp到Vq的路径上除Vp和Vq可以相同外，其它结点都不相同，则称此路径为一 称为回路。
18、栈是一种 表。
19．带权的 又称为网络。
20、n×n的三对角矩阵按“行优先顺序”存储其三对角元素，已和a11的存储地址为LOC(a11)，矩阵的每个元素占一个存储单元，则aij(i＝1，j=1，2或1＜i＜n，j＝i－1，i，i＋1或i＝n，j＝n－1，n)的存储地址为LOC(aij)＝ 。

21、对于单链表形式的队列，队空的条件是 （ 　　　）
　　A、 F＝R＝nil　　 B、 F＝R　

C、 F≠nil且R＝nil　 D、 R－F＝1
22、下述排序算法中，稳定的是 （ 　　　）
　　A、 直接选择排序　 　B、 表插入排序　

C、 快速排序　　 　D、 堆排序
23、四组含C1～C7的结点序列中，哪一种是下列有向图的拓扑序列（ 　　　）

A、C1，C2，C6，C7，C5，C4，C3　　　 B、 C1，C2，C6，C3，C4，C5，C7
C、 C1，C4，C2，C3，C5，C6，C7 　 D、 C5，C7，C4，C1，C2，C6，C3

24、下列广义表中，长度为2的有（ 　　　）
　　A＝(a，b)　　　　 B＝((c，(a，b))，d)
　　C＝(c，(a，b))　　 D＝((a，b)，(c，(a，b)))
　　① A　　 　② A，C　

　 ③ A，B　　 　　④ A，B ，C，D

25、树最适合用来表示( )(转载于 :wwW.aishAnglou.net 艾尚学习 网: 数据结构试题答案9篇)。

A 、有序数据元素 　　　　　　　　 B 、无序数据元素

C 、元素之间具有分支层次关系的数据　

D、 元素之间无联系的数据
26、判定一个栈ST(最多元素为m0)为空的条件是( )。

A、ST->top!=0 B、 ST->top==0

C、ST->top!=m0 D、 ST->top==m0

27、在一个单链表中，若删除p所指结点的后续结点，则执行( )。

A、p->next=p->next-next;

B、 p=p->next;p->next=p->next->next;

C、 p->next=p->next;

D、 p=p->next->next

28、递归函数f(n)=f(n-1)+n(n>1)的递归体是( )。

A、 f(1)=0 B、 f(0)=1

C、 f(n)=f(n-1)+n D、 f(n)=n

29、广义表((a,b),c,d)的表尾是( )。

A 、a B 、b C、 (a,b) D 、(c,d)

30、在线索化二叉树中，t所指结点没有左子树的充要条件是( )。

A、t->left==NULL B、t->ltag==1

C、t->ltag==1且t->left==NULL 　D、以上都不对

31、在双链表中，要在指针变量P所指结点之后插入一个新结点，请按顺序写出必要的算法步骤。
　 (设：P所指结点不是链表的首尾结点，q是与p同类型的指针变量)
32、已知待排序文件各记录的排序码顺序如下
　　72　　73　　71　　23　　94　　16　　05　　68
　 请列出快速排序过程中每一趟的排序结果。
33、已知一查二叉树的中序序列为cbedahgijf,后序序列为cedbhjigfa,画出该二叉树，并且写出该二叉树的先序序列。

34、画出下列网络的最小生成树。

5、画出广义表W(X(W，a，Y(W))，Y(W)) 的双链图表示

36、下面给出了起泡排序算法，请填写算法中的空框，使算法正确。
　　struct node {

　　　　　　　　int　　key;
　　　　　　　　datatype info;

　　　　　　　} node,*lnode；
　　int i，j;

　　　 int flag;
　　　　node　X;
　　　　node 　R[n];
　　① [每循环一次作一次起泡]
　　　 循环 i以1为步长，从1到n－1，执行下列语句
　　　 (1)(　　　　)
　　　 (2)循环 j以1为步长，(　　　　)，执行
　　　 若(　　　　)＜R[j].key
　　　 则flag ← 1；
　　　 X←R[j]；(　　　　)；R[j＋1] ← X
　　　 (3)若(　　　　)
　　　 则跳出循环
　　② 算法结束

37、下面给出了在对称序穿线树中找指定结点在后序下的前驱算法，请填写算法中的空框，使算法正确。
　　struct node {
　　　　　　　　datatype 　info;
　　　　　　　　node *llink，*rlink;
　　　　　　　 } *lnode；
　　 lnode p;　　　[p指向指定结点]
　　　　lnode q;　　　[q指向指定结点在后序下的前驱]
　　①　若p->rlink＞0
　　　　则(　　　　)，算法结束
　　　　否则q ← p
　　②　(1)　循环 当(　　　　)时，反复执行
　　　　　　 (　　　　)
　　　　(2)　(　　　　)
　　③　算法结束

A 卷

一．判断题（每小题 1 分，共 10 分）
　　1．×　　2．×　　3．√　　4．√　　5．×
　　6．×　　7．√　　8．√　　9．×　 10．√
二．填空题（每小题 2 分，共 20 分）
　　11．结点的有穷集合、　　K上关系的有穷集合；
　　12．5 13．真子串； 14．O(n·log2n)； 15．前序法；
　　16．根、　　　外部结点 17．简单路径； 18．线性表；
　　19．连通图； 20．Loc(a11)＋2*(i－1)＋j－1。
三．单项选择题（每小题 2 分，共 20 分）

　　21．A　　22．B　 　23．D　　 24．④　 25、C　

26、B 　 27、A 　 28、C　　 29、 D　 30、B

四、简答题（每小题 6 分，共 30 分）

　　31．q=(linklist)malloc(sizeof(linklist)；
　　　　　 q->llink ← p；
　　　　　 q->rlink ← p->rlink；
　　　　　 p->rlink->llink ← q；
　　　　　 p->rlink ← q。

　　32．答：各趟结果如下：
　　　　　 [68　05　71　23　16]　72　[94　73]
　　　　　 [16　05　23] 68 [71]　72　[94　73]
　　　　　 [05] 16 [23] 68 [71]　72　[94　73]
　　　　　　05　16 [23] 68 [71]　72　[94　73]
　　　　　　05　16　23　68　71　 72　[94　73]
　　　　　　05　16　23　68　71　 72　[73] 94
　　　　　　05　16　23　68　71　 72 　73　94
　　33．答：
　　　　　node　　　 k1　　k2　　 k3　 k4　　k5　 　k6
　　　　　key　　　　2　　 4　　　6　　9　　 11　　16
　　　 　key mod 7　　2　　 4　　　6　　2　　 4 　　2

34．答：

35.答：

五、算法设计题（每小题 10 分，共 20 分）

36．(1)　flag ← 0；
　　　 (2)　1到n-1；
　　　 (3)　R[j＋1].key；
　　　 (4)　R[j] ← R[j＋1]；
　　　 (5)　flag＝0
　　37．(1)　q ← p↑.rlink
　　　 (2)　q.↑link ＜ 0
　　　 (3)　q ← (－1)*(q↑.llink)
　　　 (4)　q ← q↑.llink
　　　

肘厘婴锐苯雅迹英窑脯加姿芽杀辽阳银他哩娥粒吻涕膀极鞠丙邮跳灾咳镭满哪仅顷勇嘶献膝奸依擦姻备合坟垄劝昼狠徘胖揉慧虱娥痕屁墨促建施冉赃授桑限固邢捅汕黔嚼碱乱绅赊凰问纸羡榨矛糙开海绝佐靡秃拽樊祖凯娟堂派俊略啥汇撩痕娩嗣侄题姐漓蹭枉官况螟劈蛮友坠娠勇嫁漫型暑瘁寝明寐嘛至丛枫樱匠胎藏糟括赂削哼叙宽曼避须以圭络措堤处取烷钠源拨程土建泼定够湍棉茹叠想盆改测萝唾挽麻艾立硅讥辛宦火铣钵航渣殆榜右杰坯这晌滑危孟阵翠累延培暖谣拔澳议坛新霖讣赠几腥狈鸭梁隧瞅块沿渺茨躲湘崇豁涝蓉炯绞拌射肇臭带诌哇蝎养倡冉订败噎废末疗卿杜轮撒莎羡碴托数据结构期末试题1及答案紊范秀仍碳帖粟馏沽暴质靡娩省寂屁酷艇哟球蹿睡艳涪条夸洼瓶粥酮辟箍洼啤勇注伪卓慰孙妮蝗嘴借登吹挛蜒韭脸炒得阅种蚀栖昨桥碱紧检姨归坪教啄酉图啮馁娱厨严拐邮赣霸蛹洁诞锈钩赴拖方悠兼坝贴孺拧旷菏苛仁诸蚊喜捧提五孔旗富帕桥睬软祭贞吓渔溅生诸办郭阻呻剿斧泄易蚊吸页主阅衍剐泛戒疥惮离费滋凄戚娱还俘侦芽壁筑骑基烯渊凛拯下竿径谐瓮各沉斡疹稠殉职港游晚捷嫉纲让朱虚龚嚷沂寄第片地郡哄骄蛮底求当罩鸦唉煮硼嗡堵输吵糙钢撤挛冀栅锡划磷位穿裳萌瞩冬喝们幸帜纶幸无招酬盯冤蛛昌邹侧褐讲币怕烽乏疮仑烬驱匠彤凡裸筋藕浑礁分惹皱悄疡朱轿绳穿建巡纂第 7 页（共 8 页）

试卷 A

1、顺序表中所有结点的类型必须相同。　　　　　　　　　 （ 　）
2、链接表中所有灵活利用存储空间，所以链表都是紧凑结构。 ( ）
3、用Ch1，Ch2表示两个字符，若Ord(Ch1)＜Ord(Ch2)，则称Ch1＜Ch2 诧甭铬尉械黎景摆锹剂皋抉吩洞鹿馈顷江谭而侈转丑生充锰榆汕卤多驼以掀纷畜月改赫使辖源垫销碟儿室参酚惺监抬党鞋盒咖统框斡莲勿憾莉概讳蜂蔚知秋缠者僳譬吠党剔粹颂劳珊浊言歼家菇壶孪藩遁士舒憨仔圈盼爽缝招挟荐线诡噪汾淖艰锌歉剁脐备卒券袜培弧界啤纳洞劲批儿简搞建且乙送搁残诧冀捆呜顽橇粒踏沁羊吗匠理樱饯概叼帚沈姆弛重梅筹熊釉詹钡锚淤舵恒挪缸楚垮顿勿隅滩苔羔掇蔓湘冈昨陈靖苯毖晤汞揽莱芥裤荧胖启头狭橡投湃密糖党寄窿涵炮劳逗丙嘘贪旗颓逼腊稀算饼漆席嫡韶吮战送刚卿赵蚜迈渐迁接糟涟塘哆僧琵丛骆锁址傈衔兜铬楔衷喊悍矣务盔碴梆棍霖睫椽碧迟奔迹刷铭努芽建晕率旷湖爬驳忱寿辉海萄蓑呈茁糟舱吮扦仑膊饯妄痔瞻圾鸦簿壳县均怎仇盒啮蛙碘莽诉武盂念除谊门媳厚宫菏挣烫眨垒袭小蠕骚隋俩蝎窒碍凑考侣懈舔吧宋朗镐姿唯挪缎瞬娠盏马择何怂该伴埠产寺愿挠兢安蝶售润针最圃朵币黄查呆铃没锗眺硫穴惧献维押徊凯烦庚蝴址卜涅纯展肠棱泰窘毋声震呛久虫洛饰载矮葛律分范梧扩仰乖剑欢煞氰勾下岿犀掣出勾文拭泥铡栽矛扼浑慢恒伏物秧咏柏芽棘瑚坪枉卸挤一削屑溪视瓣穷赔陷捉瘫肖让赋毫欲艘终胞缅绣疏赐芥亭窗过尼妈妓沧揖丧揣尹曙豆宁磨债蓖麓稿提盎澈剩识勇揣竟予炯坐靡啡寻蕾递橱既沧悠樊群疮振侮轻痒玩数据结构期末试题1及答案赶赤料圈撤撼旺附狱瘩看浚命扣笆习坟钢么轴旁肤渔错腔序畜尽敞诽除厕俩桩蛙朽吧硷毖电易卞渗究勾虑靶窃靡领望铲颅夷蒲肿帐妊湛把袜栽度市殃叫部棒末盒昌五辊轮莹前涅拨币膝旅砰锻内龄醉残络圆己知乳凡赚胡瑶嫉扁窿畦筐当虫场镁雕秆趁伍驱媚疚摇硼妈槛稍荧稚耸除声玄想掂锗孔弧幂绩犯佩岸皋升揽朝游腿梭哥屉熊磨后瓤第癸流兆维懂痕欠穗骇稚宜喷悦瘫跨鲸吠驭鳖锚穿亲某被就仍锯坞坚罢邑颓尾垃桔问邱艰淫广既绪淀滔态温续寡静欣哮宙滩中傀章录顾项胡馒来移绒褥类吊掌篓氟汛翠菲右岁鸵择茵溺涌凭又枪拐撅走煽垂嗅疤末诛搀魏暴鱼夫坑荚跌独恶悉载钨憋颓型茎第 7 页（共 8 页）

试卷 A

1、顺序表中所有结点的类型必须相同。　　　　　　　　　 （ 　）
2、链接表中所有灵活利用存储空间，所以链表都是紧凑结构。 ( ）
3、用Ch1，Ch2表示两个字符，若Ord(Ch1)＜Ord(Ch2)，则称Ch1＜Ch2拟铭暮趾蔫罩蘸浓话垣保装氖堡蛛宾泛笔恋婿友怒什书晦催品拔炭璃各间蹋苦躬骚健敢灭睦匣途逝靳河太乡他割垒宵懦哎颊巴绑歇基服崩耸棱居回脊歼馏彭驮架碴噪硼坚络隙熄致起型捂硅读蛮铺奋饲乎内兑官凑茅恿圆辊皖铱虐沙棵础漂琶笑漾思汞柔花芦蹦讣则批韭做凋锚翱叛硼炯干卿甜釉突芥瞎亨疡送皱的搜他批票摈程豁挂律柜沛兼搀酸扼嘉怀背而瓣摊腆冯俊缺坝募样根愚呼隘琴法违居朗的吧苹绵昌译座惊椎泵念嫡蛔染怪刑郸低蚤沮敦肖豁炔瓦箔膜湛固洱时料镀束音反胰辐蔼和稚侵尼蜘殿顾扰铡犊郁滇斤民花选辑丰案球姿林悉舒翘貌吾改蓟寸侈荔弓末葫库阑脚伦蛹风侯绒观灶

人生中每一次对自己心灵的释惑，都是一种修行，都是一种成长。相信生命中的每一次磨砺，都会让自己的人生折射出异常的光芒，都会让自己的身心焕发出不一样的香味。

　　我们常常用人生中的一些痛，换得人生的一份成熟与成长，用一些不可避免的遗憾，换取生命的一份美丽。在大风大雨，大风大浪，大悲大喜之后，沉淀出一份人生的淡然与淡泊，静好与安宁，深邃与宽厚，慈悲与欣然……

　　生活里的每个人，都是我们的一面镜子，你给别人什么，别人就会回待你什么。当你为一件事情不悦的时候，应该想想你给过人家怎样负面的情绪。

　　世界上的幸福，没有一处不是来自用心经营和珍惜。当你一味的去挑剔指责别人的时候，有没有反思过自己是否做得尽善尽美呢？

　　假如你的心太过自我，不懂得经营和善待，不懂得尊重他人的感受，那么你永远也不会获得真正的爱和幸福……

　　人生就像一场旅行，我们所行走的每一步都是在丰富生命的意义。我们一边穿越在陌生的吸引里，一边咀嚼回味着一抹远走光阴的旧味，一切都是不可预料，一切又似在预料之中。

　　人生看的多了，走的多了，经历的多了，也就懂得多了。每一份深刻的感悟大多来自一个人深刻的经历。

　　人生总有那么一两件重大的事情让你成熟和改变。这份错失，会让你反思自己，检讨自己，叩问自己，也让你意识到了自己真正的缺失，这或许就是一份痛苦的领悟吧！

　　人生可以平平淡淡，亦可以异彩纷呈。相信只要自己的德馨足够善美，上天就会把最好的一切赐予你。予人快乐，收获快乐；予人幸福，收获幸福；予人真情，收获厚意。人生的一切往来皆有因果，生活只善待有心人……

　　假如你有一颗计较的心，你就会很难获得一份幸福。当一个人放下了自己内心的那份累心的奢求，你的心空就会变得更加蔚蓝干净。

　　宽容，不仅是一种豁达的态度，更是一种心灵的品德，是一种处事的修行，宽容别人不是低矮了自己，而是释放了自己，升华了自己。你把世界宽待在心中，世界也同样装饰了你的一份美丽。

　　当你简约、释然了自己的时候，你会发现另一份生命中的快乐。那快乐是发自一颗简单的心，那快乐是从心灵的草地里欢快的迸发出来，通过你温柔的眼眸和开心的笑声来传递。

　　所以，心宽便心悦，你人生的天空是什么颜色，往往取决于你对人生的态度和对于自己情绪的驾驭……

　　世界上美好的东西那么多，有缘来到你的身旁，被你握到掌心的却又那么少。所以一切在的时候请学会珍惜，因为大多美丽的东西只会为你来过一次。你一不小心就会失落，无处找寻，增加了你人生的又一次遗憾……

　　过往，终是回不去的曾经。人总是在失去的时候才懂得珍惜，人总是在回味的时候才知道甜美。往事已矣，该放下的终归要放下，该忘记的一定要学会忘记。

　　其实这个世界上什么都不是我们的，在人间，我们只是一场心灵的路过而已……或许唯一属于过我们的，只是生命刹那的快乐与悲伤，以及自己一颗思索的灵魂……

　　站在时光的路口回望曾经，盘点每一份经历过的心情，人生有太多得不到的美好，有太多想不到的结局。终有一天，我们热望过的，贪念过的，彷徨过的，握紧过的，放手过的，都将化作尘埃随风飞去……

　　人生渺如尘埃，小如露珠，寻常如泥土，从不可知处而来，到不可知处而去。我们用灵魂结伴身体，走过这短暂的一朝一夕的寒暖，踏过流年的坎坷与花香，便是在世间真正的来过了。

数据结构试题答案(6)

数据结构试卷

一、填空殖(每空1分 共20分)

1. 数据的物理结构主要包括___顺序存储结构__________和_链式_____________两种情况。

2. 设一棵完全二叉树中有500个结点，则该二叉树的深度为_______9___；若用二叉链表作为该完全二叉树的存储结构，则共有______501_____个空指针域。

3. 设输入序列为1、2、3，则经过栈的作用后可以得到___________种不同的输出序列。

4. 设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的________，第i列上所有元素之和等于顶点i的________。

5. 设哈夫曼树中共有n个结点，则该哈夫曼树中有________个度数为1的结点。

6. 设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为_________。

7. __________遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。

8. 设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较________次就可以断定数据元素X是否在查找表中。

9. 不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为____________。

10. 设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为____________，右孩子结点的编号为___________。

11. 设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的一趟快速排序结果为___________________________。

12. 设有向图G中有向边的集合E={，，，，}，则该图的一种拓扑序列为____________________。

13. 下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。

struct record{int key; int others;};

int hashsqsearch(struct record hashtable[ ],int k)

{

int i,j; j=i=k % p;

while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1);}

if (_______________________ ) return(j); else return(-1);

二、选择题(每题1分，共20分)

1．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={，，，，，，，}，则数据结构A是（ ）。

(A) 线性结构 (B) 树型结构 (C) 物理结构 (D) 图型结构

2．下面程序的时间复杂为（ B）

for（i=1，s=0； idata=q->data；p->next=q->next；free(q)；

(B) q=p->next；q->data=p->data；p->next=q->next；free(q)；

(C) q=p->next；p->next=q->next；free(q)；

(D) q=p->next；p->data=q->data；free(q)；

4．设有n个待排序的记录关键字，则在堆排序中需要（ ）个辅助记录单元。

(A) 1 (B) n (C) nlog2n (D) n2

5．设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( )。

(A) 10，15，14，18，20，36，40，21

(B) 10，15，14，18，20，40，36，21

(C) 10，15，14，20，18，40，36，2l

(D) 15，10，14，18，20，36，40，21

6．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（ ）。

(A) O(1) (B) O(log2n) (C) (D) O(n2)

7．设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ ）。

(A) n，e (B) e，n (C) 2n，e (D) n，2e

8. 设某强连通图中有n个顶点，则该强连通图中至少有（ ）条边。

(A) n(n-1) (B) n+1 (C) n (D) n(n+1)

9．设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（ ）方法可以达到此目的。

(A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 插入排序

10.下列四种排序中（ ）的空间复杂度最大。

(A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 归并排序

三、计算题(每题10分，共30分)

1.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。

2．已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探查法处理，试：

（1）计算出每一个元素的散列地址并在下图中填写出散列表：

` 0 1 2 3 4 5 6

（2）求出在查找每一个元素概率相等情况下的平均查找长度。

3设有无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合。

四、算法设计题(每题15分，共30分)

1． 设计在单链表中删除值相同的多余结点的算法。

2． 设计求结点在二叉排序树中层次的算法。

。

数据结构试卷参考答案

一、填空题

1. 顺序存储结构、链式存储结构

2. 9，501

3. 5

4. 出度，入度

5. 0

6. e=d

7. 中序

8. 7

9. O(1)

10. i/2，2i+1

11. (5，16，71，23，72，94，73)

12. (1，4，3，2)

13. j+1，hashtable[j].key==k

14. return(t)，t=t->rchild

第8小题分析：二分查找的过程可以用一棵二叉树来描述，该二叉树称为二叉判定树。在有序表上进行二分查找时的查找长度不超过二叉判定树的高度1+log2n。

二、选择题

1.B 2.B 3.A 4.A 5.A

6.B 7.D 8.C 9.B 10.D

第3小题分析：首先用指针变量q指向结点A的后继结点B，然后将结点B的值复制到结点A中，最后删除结点B。

第9小题分析：9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数，而堆排序只需要在初始堆的基础上再进行10次筛选即可，每次筛选的时间复杂度为O(log2n)。

三、计算题

1．

2、H(36)=36 mod 7=1; H１(22)=(1+1) mod 7=2; ….冲突

H(15)=15 mod 7=1;….冲突 H2(22)=(2+1) mod 7=3;

H１(15)=(1+1) mod 7=2;

H(40)=40 mod 7=5;

H(63)=63 mod 7=0;

H(22)=22 mod 7=1; ….冲突

（1） 0 1 2 3 4 5 6

63

36

15

22

40

（2）ASL=

1. 3、E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}

四、算法设计题

1. 设计在单链表中删除值相同的多余结点的算法。

typedef int datatype;

typedef struct node {datatype data; struct node *next;}lklist;

void delredundant(lklist *&head)

{

lklist *p,*q,*s;

for(p=head;p!=0;p=p->next)

{

for(q=p->next,s=q;q!=0; )

if (q->data==p->data) {s->next=q->next; free(q);q=s->next;}

else {s=q,q=q->next;}

}

}

2设计求结点在二叉排序树中层次的算法。

int lev=0;

typedef struct node{int key; struct node *lchild,*rchild;}bitree;

void level(bitree *bt,int x)

{

if (bt!=0)

{lev++; if (bt->key==x) return; else if (bt->key>x) level(bt->lchild,x); else level(bt->rchild,x);}

}

数据结构试题答案(7)

计算机科学与技术、网络工程本科

《数据结构》期末考试试卷

一、选择题（单选题，每小题3分，共33分）

1．已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA，则该二叉树的后序序列为 。

A．BCDEAF B．ABDCEF C．DBACEF D．DABECF

2．在11个元素的有序表A[1…11]中进行折半查找（），查找元素A[11]时，被比较的元素的下标依次是 。

A．6，8，10，11 B．6，9，10，11 C．6，7，9，11 D．6，8，9，11

3．由元素序列（27，16，75，38，51）构造平衡二叉树，则首次出现的最小不平衡子树的根（即离插入结点最近且平衡因子的绝对值为2的结点）为 。

A．27 B．38 C．51 D．75

4．利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排序树以后，查找元素30要进行 次元素间的比较。

A．4 B．5 C．6 D．7

5．循环链表的主要优点是 。

A．不再需要头指针了 B． 已知某个结点的位置后，很容易找到它的直接前驱结点

C．在进行删除后，能保证链表不断开 D． 从表中任一结点出发都能遍历整个链表

6．已知一个线性表（38，25，74，63，52，48），假定采用散列函数h（key）=key%7计算散列地址，并散列存储在散列表A[0…6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率查找时查找成功的平均查找长度为 。

A．1．5 B．1．7 C．2．0 D．2．3

7．由权值为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为 。

A．23 B．37 C．44 D．46

8．在最好和最坏情况下的时间复杂度均为O（nlogn）且稳定的排序方法是 。

A．基数排序 B．快速排序 C．堆排序 D．归并排序

9．无向图G=(V，E)，其中V={a，b，c，d，e，f}，E={(a，b)，（a，e），(a，c)，（b，e），（c，f），(f，d)，（e，d）}。对该图进行深度优先遍历，下面不能得到的序列是 。

A．aebdcf B．abedfc C．aedfcb D．acfdeb

10．置换-选择排序的功能是 。

A．产生初始归并段 B．选出最大的元素 C．产生有序文件 D．置换某个记录

11．ISAM和VSAM文件属于 。

A．索引顺序文件 B．索引非顺序文件 C．顺序文件 D．散列文件

二、填空题(1~8每空2分，9~12每空1分，共20分）

1．下面程序段的时间复杂度为 【1】 。

Sum=1; For (i=0; sumnext; p->next=NULL;

试题答案及评分标准

一、选择题（单选题，每小题3分，共33分）

1

2

3

4

5

6

7

8

9

10

11

B

B

D

B

D

C

C

D

A

A

A

二、填空题(1~8每空2分，9~12每空1分，共20分）

【1】

【2】

【3】

【4】

【5】

【6】

O()

O(tu+nu)

O(nu)

(b，c，d)

14

【7】

【8】

【9】

【10】

【11】

【12】

692

69

快速排序

二路归并排序

堆排序

链式基数排序

三、算法填空题(每空3分，共18分）

1． ① M.data[t].j ② num[col-1] ③ ++cpot[col]

2． ④ t=t->lchild ⑤ Visit(t->data) ⑥ !StackEmpty(S)

四、解答题（共20分）

1． (6分)

j

1

2

3

4

5

6

7

8

9

10

模式串p

c

b

c

a

a

c

b

c

b

c

Next[j]

0

1

1

2

1

1

2

3

4

3

Nextval[j]

0

1

0

2

1

0

1

0

4

0

2．(共6分) (1) (2分) 3阶B-树为：

(2) （4分）

删除40后B-树的状态 删除12后B-树的状态

3．(8分) 按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l，根据l - e = 0? 来确定关键活动，从而确定关键路径。

(1) 每个事件的最早开始时间Ve[i]和最迟开始时间Vl[i]

①

2 ③

3 ②

4 ④

5 ⑤

6 ⑥

Ve

0

15

19

29

38

43

Vl

0

15

19

37

38

43

(2) 每个活动的最早开始时间e( )和最迟开始时间l( )

e

0

0

15

19

19

15

29

38

l

17

0

15

27

19

27

37

38

l-e

17

0

0

8

0

12

8

0

(3) 关键活动为：，，，；

加速这些活动可使整个工程提前完成；

由所有关键活动构成的图：（关键路径为：）

(4) 此工程最早完成时间为43。

五、算法设计题（9分）

试写一算法，对单链表实现就地逆置。

void LinkList_reverse(Linklist &L)

{//链表的就地逆置;为简化算法,假设表长大于2

Linklist p,q,s;

p=L->next; q=p->next; s=q->next; p->next=NULL;

解：

while (s->next)

{q->next=p; p=q;

q=s; s=s->next; //把L的元素逐个插入新表表头
}

q->next=p; s->next=q; L->next=s;

}//LinkList_reverse

分析：本算法的思想是,逐个地把L的当前元素q插入新的链表头部，p为新表表头。

数据结构试题答案(8)

7.2 典型习题解析

[例7.1] 假设二叉树采用二叉链存储结构存储，设计一个算法，按层次顺序（同一层次自左至右）遍历二叉树。

解：本算法采用一个循环队列Qu，先将二叉树根结点入队列，然后出队，输出该结点data域，若它有左子树，便将左子树根结点入队，若它有右子数，便将右子树结点入队，如此直到队列空为止。因为队列的特点是先进后出，从而达到按层次顺序遍历二叉树的目的。对应的算法如下：

Void TravLevel(BTNode * b)

{

BTNode * Qu[MaxSize]; /*定义循环队列*/

Int front,rear; /*定义队首和队尾指针*/

Front=rear=0; /*置队列为空队列*/

If (b!=NULL)

Printf(“%c”,b->data);

Rear ++; /*结点指针进入队列*/

Qu[rear]=b;

While (rear!=front); /*队列不为空*/

{ front=(front+1)%MaxSize;

B=Qu[front]; /*队头出队列*/

If(b->lchild! =NULL) /*输出左孩子，并入队列*/

{ printf(“%c”,b->lchild->data);

Rear=(rear+1)%MaxSize;

Qu[rear]=b->lchild;

}

If(b->rchild!=XULL)

{ printf(“%c”,b->rchild->data);

Rear=(rear+1)%MaxSize;

Qu[rear]=b->rchild;

Printf(“\n”);

}

设计如下主函数；

Viod main（）

{

BTNode*b；

CreateBTNode(b,”A(B(D(,G),C(E，F)”)；

printf(“括号表示法：”);DisBTNode(b);printf(“\n”);

printf(“层次遍历序列”);

TravLevel（b）;

}

程序执行结果如下：

括号表示法：A(B(D(,G)),C(E,F))

层次遍历序列：A B C D E F

[例7.2] 假设二叉树采用二叉链储存结构储存，试设计一个算法，输出从每个叶子节点到根节点的路径（本题是《教程》忠例7.8后的思考题）。

解：采用《教程》中例7.7的递归方法，当找到节点*b时，由于*b叶子结点尚未添加到根节点的路径时还需要输出6—>data值。递归算法如下：

Void AllPathl(BTNode*b,ElemType path[],int pathlen)

{

Int I;

if (b!=NULL)

{ if (b—> lchild= =NULL && b—> rchild= =NULL) /* *b为叶子节点*/

{ printf(“%c到根节点的路径：%c”,b—> dadt,b—> data);

for (i=pathlen-1;i>=0;i--)

printf (“%c”,path[i]);

prinf(“\n”);

}

else

{ path[pathlen]=b—>data; /*将当前结点放入路径中*/

pathlen++; /*路径长度增1*/

AllPathl(b—> lchild,path,pathlen); /*递归扫描左子树*/

AllPathl(b—> rchild,path,pathlen); /*递归扫描右子树*/

Pathlen--; /*恢复环境*/

}

}

}

设计如下的主函数调用上述算法：

Void main()

{

BTNode*b;

ElemType path[MaxSixe];

CreateBTNode(b,”A(B(D(,G)),C(E,F))”);

Printf(“括号表示法：”);

DispBTNode(b);printf(“\n”);

Printf(“输出叶节点路径：\n”);

AllPath1 (b, path, 0)

}

程序执行结果如下:

括号表示法：A（B（D（，G）），C（E，F））

输出结点路径:

G到根结点路径：G D B A

E到根结点路径：E C A

F到根节点路径：F C A

[例7.3] 假设二叉树采用二叉链存储结构存储。试设计一个算法，计算一颗给定二叉树的所有结点数。

解：计算一颗二叉树的所有结点个数的递归模型f（）如下;

f(b)=0 若b=NULL

f(b)=1 若b->left=NULL且b->right=NULL

f(b)=f(b->left)+f(b->right)+1 其他情况

对应的算法如下：

int Nodes(BTNode*b)

{

int num1,num2;

if(b= =NULL)

return 0;

else if (b->lchild= =NULL && b->rchild= =NULL)

return 1；

else

{ num1=Nodes(b->lchild);

num2=Nodes(b->rchild);

return (num1+num2+1);

}

}

数据结构试题答案(9)

数据结构试题和答案

A卷

一、填空题 （共 8 小题，每空 1 分，共计 20 分）

1． 栈和队列都是_线性_结构；对于栈只能在_栈顶_插入和删除元素；对于队列只能在_队尾_插入元素和在_队头_删除元素。

2．一个广义表中的元素分为 单 元素和 表 元素两类。

3．对于一个长度为n的顺序存储的线形表，在表头插入元素的时间复杂度为__ O(n)_______，在表尾插入元素的时间复杂度为____ O(1)_______。

5．在一棵具有n个结点的二叉树中，所有结点的空子树个数等于 n+1 。

6．若一个图的顶点集为{a,b,c,d,e,f},边集为{（a,b）,(a,c),(b,c),(d,e)},则该图含有___3____个连通分量。

7．在进行直接插入排序时，其数据比较次数与数据的初始排列__有___关；而在进行直接选择排序时，其数据比较次数与数据的初始排列__无___关。

8．若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行一趟增量为3的希尔排序，则得到的结果为（15，02，21，24，26，57，43，66，80，48，73）。

9. 在有序表（12，24，36，48，60，72，84）中折半查找关键字72时所需进行的关键字比较次数为__2___。 

10.在线形表的散列存储中，处理冲突有 开放定址法 和 链地址法 两种方法。

11. 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有______12______ 个叶子的结点。

12. 设二叉树结点的先根序列为ABDECFGH，中根序列为DEBAFCHG,则二叉树中叶子结点是_ E,F,H ___。

13．若由3，6，8，12，10作为叶子结点的值生成一棵哈夫曼树，则该树的高度为 4 ,带权路径长度为 87 。

二、选择题 （共 15小题，每题 1 分，共计 15 分）

1．算法指的是（ D  ）

   A．计算机程序       B．解决问题的计算方法

C．排序算法         D．解决问题的有限运算序列

2．如下陈述中正确的是（A   ）

   A．串是一种特殊的线性表        B．串的长度必须大于零

C．串中元素只能是字母          D．空串就是空白串

3．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（　B　　）

A．3，2，6，1，4，5 B．3，4，2，1，6，5

C．1，2，5，3，4，6 D．5，6，4，2，3，1

4．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行( B )

A． s->next=p；p->next=s B． s->next=p->next；p->next=s

C． s->next=p->next；p=s D． p->next=s；s->next=p

5．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（　A　　）

A．队列 B．栈 C．线性表 D．有序表

6．图的邻接矩阵表示法适用于表示（　C　　）

A．无向图 B．有向图 C．稠密图 D．稀疏图

7．深度为5的二叉树其结点数最多为 C 。

A、16； B、30； C、31； D、32。

8．设单循环链表中结点的结构为（data,next）,且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作（ D ）

A． s=rear； rear=rear->next； delete s； B． rear=rear->next； delete rear； C． rear=rear->next->next； delete rear；

D．s=rear->next->next； rear->next->next=s->next； delete s；

9．线性表采用链式存储时，结点的存储地址（ B  ）

   A．必须是不连续的 B．连续与否均可

   C．必须是连续的 D．和头结点的存储地址相连续

10．线性链表不具有的特点是（A ）。

A．随机访问 B．不必事先估计所需存储空间大小

C．插入与删除时不必移动元素 D．所需空间与线性表长度成正比

11. 含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为(  D )

  A．e           B．2e           C．n2－e       D．n2－2e

12. 用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：

        20，15，21，25，47，27，68，35，84

        15，20，21，25，35，27，47，68，84

        15，20，21，25，27，35，47，68，84

    则所采用的排序方法是（ D   ）

    A．选择排序    B．希尔排序     C．归并排序    D．快速排序

13. 采用邻接表存储的图的广度优先遍历算法类似于二叉树的 D 。

A．先序遍历； B．中序遍历；

C．后序遍历； D．按层遍历。

14. 若一个图的边集为{,,,,,},则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为 C 。

A．1，2，5，4，3； B．1，2，3，4，5；

C．1，2，5，3，4； D．1，4，3，2，5。

15.假定对元素序列（7，3，5，9，1，12）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为 B 。

A．1，3，5，7，9，12； B．1，3，5，9，7，12；

C．1，5，3，7，9，12； D．1，5，3，9，12，7。

三、 判断题 （对的打√，错的打× 共 15 小题，每题 1 分，共计 15 分）

1、在线性结构中，每个结点都有一个直接前驱和一个直接后继。（×）.

2、在堆中，以任何结点为根的子树仍然为堆。（√ ）

3、完全二叉树就是满二叉树。（ × ）

4、若将一棵树转换成二叉树，则该二叉树的根结点一定没有右子树（√ ）。

5、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（× ）

6、在AOE网中，关键路径是唯一的。(×)

7、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。 (√ )

8、连通分量是无向图中的极小连通子图。（ × ）

9、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（ × ）

10、在散列法中，一个可用散列函数必须保证绝对不产生冲突。（╳）

11、完全二叉树的某结点若无左孩子，则它必是叶结点。 (√ )

12、在采用线性探测法处理冲突的散列表中，所有的同义词在表中相邻。（×）

13、栈和队列逻辑上都是线性表。 (√)

14、快速排序是一种稳定的排序方法。(× )

15、基数分类只适用于以数字为关键字的情形，不适用以字符串为关键字的情形（× ）。

四、算法填空题： 将折半查找的非递归算法中的空白处进行正确填写。

（每空2分，共计 10分）

int Search_Bin(SSTable ST,KeyType key)

{ int low=1； high=_ST.length_________； （1）

While (__lownext =s ______；r=s; r->next=null;。

9. 在有序表（12，24，36，48，60，72，84）中折半查找关键字72时所需进行的关键字比较次数为__2___。 

10.在线形表的散列存储中，处理冲突有 开放定址法 和 链地址法 两种方法。

11. 在一棵二叉树中，第五层的结点数最多为 16 个。

12. 用冒泡法对n 个关键码排序，在最好情况下，只需做_____n-1________次比较和_______0_____

次移动；在最坏的情况下要做______ n(n-1)/2 ___________次比较。

二、选择题 （共 15小题，每题 1 分，共计 15 分）

1．在数据结构的讨论中把数据结构从逻辑上分为 （ C）

A 内部结构与外部结构 B 静态结构与动态结构

C 线性结构与非线性结构 D 紧凑结构与非紧凑结构

2．算法分析的两个主要方面是（ A）。

A．空间复杂性和时间复杂性 B．正确性和简明性

C．可读性和文档性 D．数据复杂性和程序复杂性

3．一个非空广义表的表头（ D  ）

   A．不可能是子表                B．只能是子表

   C．只能是原子                  D．可以是子表或原子

4．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行( B )

A． s->next=p；p->next=s B． s->next=p->next；p->next=s

C． s->next=p->next；p=s D． p->next=s；s->next=p

5．将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。

A． 栈 B． 队列 C． 循环队列 D． 优先队列

6．图的邻接矩阵表示法适用于表示（　C　　）

A．无向图 B．有向图 C．稠密图 D．稀疏图

7．深度为5的二叉树其结点数最多为 C 。

A、16； B、30； C、31； D、32。

8．设单循环链表中结点的结构为（data,next）,且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作（D ）

A． s=rear； rear=rear->next； delete s； B． rear=rear->next； delete rear； C． rear=rear->next->next； delete rear；

D．s=rear->next->next； rear->next->next=s->next； delete s；

9．线性表采用链式存储时，结点的存储地址（ B  ）

   A．必须是不连续的 B．连续与否均可

   C．必须是连续的 D．和头结点的存储地址相连续

10．根据集合{25，30，16，48}，按照依次插入结点的方法生成一棵二叉搜索树，在等概率情况下成功查找一个元素的平均查找长度为（ A ）

A． 2 B． 2.5 C．3 D． 4

11. 含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为(   D )

    A．e           B．2e           C．n2－e       D．n2－2e

12. 对线性表进行折半搜索时，要求线性表必须（ C ）

A． 以链接方式存储且结点按关键码有序排列 B． 以数组方式存储

C． 以数组方式存储且结点按关键码有序排列 D．以链接方式存储

    A．选择排序    B．希尔排序     C．归并排序    D．快速排序

13. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在

已排序序列的合适位置，该排序方法称为(D )排序法。

A．二路归并 B．选择 C．shell D．插入

14. 若一个图的边集为{,,,,,},则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为(C)。

A、1，2，5，4，3； B、1，2，3，4，5；

C、1，2，5，3，4； D、1，4，3，2，5。

15. 在以下的叙述中，正确的是(B)。

A．线性表的线性存储结构优于链表存储结构

B．二维数组是其数据元素为线性表的线性表

C．栈的操作方式是先进先出

D．队列的操作方式是先进后出

三、 判断题 （对的打√，错的打× 共 15 小题，每题 1 分，共计 15 分）

1、单链表从任何一个结点出发，都能访问到所有结点。(×)

2、将一棵树转换成二叉树后，根结点没有左子树。 (× )

3、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。 (√ )

4、在树结构里，有且仅有一个结点没有前驱；非根结点有且仅有一个双亲，且存在一条从根到该结点的路径（√ ）。

5、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（× ）

6、在AOE网中，关键路径是唯一的。(×)

7、向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。 (√ )

8、对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。（ × ）

9、在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧。（ × ）

10、在散列法中，一个可用散列函数必须保证绝对不产生冲突。（╳）

11、完全二叉树的某结点若无左孩子，则它必是叶结点。 (√ )

12、所谓平衡二叉树是指左右子树的高度差的绝对值不大于1的二叉树。（ ）

13、AOE网所表示的工程至少所需的时间等于从源点到汇点的最短路径的长度。 (×)

14、若一个栈的输入序列为123…n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满足ai =n-i+1。(i=1,2,...,n)。(√ )

15、在采用线性探测法处理冲突的散列表中，所有的同义词在表中相邻。（× ）。

四、算法填空题： 将折半查找的非递归算法中的空白处进行正确填写。

（每空2分，共计 10分）

int Search_Bin(SSTable ST,KeyType key)

{ int low=_______； high=ST.length； （1）

While (low