2009-20101考试试卷数据结构数字081

1、。装。订。线。2009 年2010 年第一学期数据结构 试卷 A 卷学院班级学号分数时间共 120 分钟一、单项选择题( 102= 20)1、以下数据结构中，哪一个是线性结构（ ）？A、广义表C、稀疏矩阵B、二叉树D、串2、在一个以 h 为头的单循环链中，pA、p-next=NULLC、p-next-next= NULL指针指向链尾的条件是（）。B、p-next =hD、p！=NULL3、设 abcdef 以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（ ）。A、fedcbaB、 bcafedC、dcefbaD、 cabdef4、串的长度是指（）A、串中所含不同字母的个数

2、C、串中所含不同字符的个数B、串中所含字符的个数D、串中所空格字符的个数5、顺序表表示的循环队列中，队列满的条件是（）A、front=rearC、(front+1) %MAXSIZE=rear 6、在二叉树的第i 层上最多有（B、front=rear+1D、(rear+1)%MAXSIZE=front）个结点B、2i-1C、2i-1A、不确定D、2i）条边。7、要连通具有n 个顶点的有向完全图，需要（n2An(n-l)B1/2C1/2n(n-1)D2n得分阅卷人题号一二三四五六总分得分阅卷人8、从键盘依次输入关键字的值：v、i、s、u、a、l、c。建立二叉排序树，则其中序遍历序列为（）A、ai

3、slcuvC、acilsuvB、slcuviaD、aclisuv9、用线性探测法查找散列表，可能要探测多个散列地址，这些位置上的键值（）A、一定都是同义词C、都相同B、一定都不是同义词D、不一定都是同义词10、对序列15，9，7，8，20，-1，4进行排序，进行一趟后数据的排列变为9，7，8，15，-1，4，20；则采用的是（）排序。A. 选择B. 快速C.D. 冒泡二、填空题(102=20)1、数据元间的关系在计算机中有两种不同的表示方法：（1）和（2）。2、若经常需要对线性表进行和删除运算，则最好采用 （3）结构，若经常需要对线性表进行查找运算，则最好采用 （4） 结构。3、栈的修改是按（

4、5）原则进行，队列的修改是按（6）原则进行。4、深度为 6（根的层次为 1）的二叉树至多有 （7）个结点。5、将含 100 个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点，根结点的为 1，为 49 的结点X 的双亲为 （8）6、N 个顶点的连通图的生成树有 （9）条边。7、一个有向图 G中若有弧、和,则在图 G 的拓扑序列中，顶点vi,vj 和vk 的相对位置为_（10）_。得分题号12345题号678910得分阅卷人1、在循环队列中，front 指向队列中第一个元素的前一位置，rear 指向实际的队尾元素，队列为满的条件是 front=rear。（）2、对链表进行和删除操作时，不

5、必移动结点。（）3、栈可以作为实现递归调用的一种数据结构。（）4、在一个有向图的拓扑序列中，若顶点 a 在顶点 b 之前，则图中必有一条弧。()5、对有向图 G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。()6、“顺序查找法”是指在顺序表上进行查找的方法。（）7、向二叉排序树一个新结点时，新结点一定会成为二叉排序树的一个叶子结点。（）8、键值序列A，C，D，E，F，E，F是一个堆。9、算法就是程序（）（）10、完全二叉树肯定是平衡二叉树。（）四 应用题 (45= 20)1、将下图的森林转换为二叉树，画出二叉树。（5 分）AEIBCDFGJ得分阅卷人题

6、号12345678910阅卷人2、下图表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的 n-1 条公路，画出所有可能的方案。（10 分）v16v3195v5v4183、已知一个无向图的邻接表如下图所示。（本题 5 分）12345(1) 画出这个图。(2)以v1 为出发点，对图进行广度优先搜索，写出一种序列。231235414542V1V2V3V4V5五、算法设计题( 310= 30)1、设二叉树以二叉链表为结构，结点结构为。设计一个算法，查找在先根序列中处于第k 个位置的结点。2、分别编写在顺序表和结点的单链表上统计出值为 x 的元素个数的算法，统计结果由函数值返