数据结构试题A

的答案，并将其号码填在题干的括号内。每小题2分，共30分）

1． 若某线性表中最常用的操作是取第I个元素和找第I个元素的前趋元素，则采用（ D）

存储方式最节省时间。 A)单链表 B)双链表 C)单向循环链表 D)顺序表 2．串是任意有限个（ C ） A)符号构成的序列 B)符号构成的集合 C)字符构成的序列 D)字符构成的集合

3．设矩阵A的任一元素aij(1i,j10)满足：

aij0;(ij,1i,j10) a0;(ij,1i,j10)ij 现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有4个单元，则元素A[9,5]的首地址为（ D ）。 A)2340 B)2336 C)21 D)2160

4．如果以链表作为栈的存储结构，则退栈操作时（ C） A)必须判别栈是否满 B)对栈不作任何判别 C)必须判别栈是否空 D)判别栈元素的类型

5．设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（ D ） A)front=front+1 B)front=(front+1)%m C)rear=(rear+1)%m D)front=(front+1)%(m+1)

6．深度为6（根的层次为1）的二叉树至多有（ D）结点。 A) B)32 C)31 D)63

7．将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。则编号为49的结点X的双亲的编号为（ A）。 A)24 B)25 C)23 D)无法确定 8．设有一个无向图G=(V,E)和G’=(V’,E’)，如果G;G的生成树，则下面不正确的说法是（B ）。 A)G’为G的子图 B) G’为G的连通分量 C) G’为G的极小连通子图且V’=V D) G’为G的一个无环子图

9．下列序列中，( A )是执行第一趟快速排序后得到的序列。(排序的关键字类型是字符 串)

A)[da，ax，eb，cd，bb]ff[ha，gc] B) [ge，ax，eb，cd，bb] ff [da，ha] C)[cd，eb，ax，da] ff [ha，gc，bb] D) [ax，bb，cd．da] ff [eb，gc，ha] 10．二分查找要求被查找的表是( C )。

A)键值有序的链接表 B)链接表但键值不一定有序 C)键值有序的顺序表 D)顺序表但键值不一定有序

11．当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为( D )。 A)n2 B)nlog2n c)log2n D)n-1

12．堆是一个键值序列(k1，k2，…，kn)，对i=1，2，…，n/2，满足( C)。

A)ki≤k2i≤k2i+1 B)kiC) ki≤k2i且ki≤k2i+1 (2i+l≤n) D) ki≤k2i或ki≤k2i+1 (2i+1≤n) 13．使用双向链表存储数据，其优点是可以( A )。 A)提高检索速度 B)很方便地插入和删除数据 C)节约存储空间 D)很快回收存储空间

14．设计一个判别表达式中左右括号是否配对出现的算法，采用( B )数据结构最佳。 A)线性表的顺序存储结构 B)栈

C)队列 D)线性表的链式存储结构

15．设高度为k的二叉树上只有度为0和2的结点，则此类二叉树中所含的结点数至少为( C )。

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

二、填空题(每空2分，共28分)

1．设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是 r->next=s r=s；r->next=NULL。

2．在单链表中，指针p所指结点为最后一个结点的条件是 p->next==NULL 。 3．设一个链栈的栈顶指针是ls，栈中结点格式为

，栈空的条件是

____ ls==NULL， _______。如果栈不为空，则退栈操作为p=ls； ls=ls->link _ ；free(p)。

4．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有 12 个叶子结点。

5．树有三种常用的存储结构，即孩子链表法，孩子兄弟链表法和 双亲表示法 。 6．n个顶点的连通图的生成树有 n-1 条边。

7．一个有向图G中若有弧、和，则在图G的拓扑序列中，顶点vi，vj和vk的相对位置为 ________ i，j，k 。

8．设表中元素的初始状态是按键值递增的，分别用堆排序，快速排序、冒泡排序和归并排序方法对其进行排序(按递增顺序)，__ 冒泡排序、 最省时间， __ 快速排序 最费时间。

9．下面是将键值为x的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。 typedef struct node { int key；

struct node *left, *right； }

void searchinsert( int x; pnode t) /* t为二叉排序树根节点的指针*/ { if （ t==NULL, _____ ） { p= malloc(suze)；

p->key=x; p->left = NULL；

p->right=NULL； t=p；

} else

if(xkey) searchinsert (x, t->left)

else searchinsert(x,t->right) _____

}

10.线性表的 _循环链表、_ 主要有点是从表中任一结点出发能访问到所有结点。而使用___________双向链表__ ，可根据需要在前后两个方向上方便地进行查找。

三、应用题（本题共28分）

1.树的后根遍历方法是：

若树非空，则

1）依次后根遍历根的各个子树T1，T2，……，Tm； 2）访问根节点。

对图1所示的树，用后根遍历方法进行遍历，请写出遍历所得到的结点访问序列。（4分）

A B C D E F G H I J K

图1 树

EBFGCKHIJDA

2.将图2的森林转换成二叉树。（4分）

A E I B C D F G J

图2 森林

分析：先将每棵树转换成二叉树，然后再将各二叉树的根结点作为兄弟连接在一起。而树转换成二叉树的方法是，先将兄弟结点连在一起，然后除最左边的孩子外，断开其它双亲到孩子的连线。

答案：如图6所示。

A E I B C D F G J

（a）先将各树转换成二叉树

A E I B F J G C D （b）以结点为中心旋转45°

A B E C F I D G J

（c）将各二叉树组合在一起 图6 森林转换成二叉树

3.图3表示一个地区的交通网，顶点表示城市，边表示连接城市间的公路，边上的权表示修

1 19 21 33 5 16 11 6 14 18 2 5 6 6 3 4 图建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路，画出所有可能的方案。（4分）

3网 分析：本题实际上是求最小生成树问题。由于图中有两条权值为6的边，故可以得到两种方案。

答案：如图7所示。

1 16 11 6 5 18 2 5 6 3 1 16 11 6 5 18 2 5 3 4 6 4 图7 由网络得到的最小生成树

4．已知一个无向图的邻接表如图4所示。 2 4 V1 5 4 V2 4 5 V3 V4 V5 3 3 ∧ ∧ 1 1 ∧ ∧ 2 2 ∧ 图4邻连表

1)画出这个图。

2)以v1为出发点，对图进行广度优先搜索，写出所有可能的访问序列。(本题4分，每

小题2分)

1）如图8所示。

1 2 4 5 3

图8 图4所示邻接表所对应的图

（2）v1v2v4v5v3和v1v4v2v3v5。

5．设n个元素的有序表为R，K为一个给定的值，二分查找算法如下： int binswarth(sqlist R；keytype K) { L=1； h=n；suc=0； while((L<=h)＆＆(!suc)

{ mid=(L+h)／2； switch

{ K=R[mid].key：suc=L；break； kR[mid].key：L=mid+1 } }

if(suc) return(mid) else return(0)； }

将上述算法中划线语句改为：K2)若算法不能正常工作，给出一个查找序列和一个出错情况的查找键值；若能正常工作，请给出一个查找序列和查找某个键值的比较次数。(本题6分，每小题3分)

分析：经过改动以后，有可能出现死循环，比如当查找的键值k小于有序表中的最小键值时，就会出现死循环。

答案：(1)算法不能正常运行。

(2)假设有序表的查找序列为(7，10，12，16，24，39，42)，当待查的键值为k=5时，出现死循环。

6．有一组键值25，84，21，47，15，27，68，35，24，采用快速排序方法由小到大进行排序，请写出每趟的结果，并标明在第一趟排序过程中键值的移动情况。(本题6分)

25 84 2l 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] 得到： 15 20 2l 25 27 35 47 68 84 第一趟排序过程中键值的移动情况如图9所示。

② ④ 25 84 2l 47 15 27 68 35 20 ③ ①

x 四、设计题（共14分）

1. 设一颗二叉树以二叉链表为存储结构，结点结构为

。设计一个算法，

求在先根序列中处于第k个位置的结点。（本题6分）

．分析：因为是求前根序列中处于第k个位置的结点，所以本算法是按前根遍历来实现的。在这当中，访问根结点的操作就是计算器count加1，然后判断count是否等于k，等于k就退出并返回指向对应结点的指针，否则继续按前根遍历往下查找。

答案：Viod search(bitreptr t；integer k) { if(t!=NULL) { count++；

if(count==k)return(t)； else{ search(t->lchild, k)； search(t->rehild，k)； } } }

2. 设某个单链表L的结点结构为

，试画出该链表的结构图，并用C语言编

写算法，判断该链表的元素值是否是递增的。（本题8分）

分析：判断一个单链表是否递增，只要从起始结点开始，依次向后比较前一个结点的键值是否小于后一个结点的键值。

答案：单链表L的结构如图10所示。 L a1 a2 …an ∧

图10 单链表L的结构

参：

int isviset(lklist L) //1分 { p=L; //1分 while(p->next!=NULL) //1分

if(p->datanext->data) //1分

p=p->next; //1分 else

return(0); //1分 return(1); //1分 }