数据结构导论2001年7月试题

1、00 一年下半年全国高等教育自学考试数据结构导论试卷、单项选择题1若给定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是（）2A. 0（1）B.0（n）C.0（n）D.0（nlog 2n）2在一个具有n个结点的单链表达中查找值为m的某结点,若查找成功，则平均比较（）A. nB.n/2C.（n-1）/2D.（n+1）/23 研究数据结构就是研究（）A.数据的逻辑结构B.数据的存储结构C.数据的逻辑结构和存储结构D.数据的逻辑结构，存储结构及其数据在运算上的实现4为了方便地对图状结构的数据进行存取操作，则其数据存储结构宜采用（）方式。A、顺序存储B、链式存储C、索引存储D、散列存储5.

2、 二维数组A1020, 510采用行序为主序方式存储，每个数据元素占4个存储单元，且 A10 , 5的存储地址是1000,则A18 , 9的地址是（ ）A、 1208B、 1212C、 13686设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有（A、13B、127下列几种结构中属于树型结构的是（D、 1364）个结点。D、25&设无向图G= （V、E）和G ' = （V E'）,女口 G'为G的生成树，则下面不正确的说法是（）A、G '为G的连通分量B、G '为G的无环子图C、G '为G的子图D、G '为G的极小连通子图且

3、 V ' =V9. 下列说法中不正确的是（）A、无向图的极大连通子图称为连通分量B、连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C、图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D、有向图的遍历不可采用广度优先搜索方法10. 对有序表（18, 20, 25, 34, 48, 62, 74 , 85）用二分查找法查找 85,所需的比较次数为（）A、1次B、2次C、3次D、4次11 .散列表的平均查找长度（）A、与处理冲突方法有关而与表的长度无关B、与处理冲突方法无关而与表的长度有关C、与处理冲突方法有关且与表的长度有关D、与处理冲突方法无关且与表的长度无关12. 对ISA

4、M文件的删除记录时，一般（）B、需移动记录C、需改变指针D、一旦删除就需做整理A、只需做删除标志13 顺序文件适宜于()A、直接存取B、成批处理C、按关键字存取D、随机存取14. 一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用()方法。A、快速排序B、堆排序C、插入排序D、二路归并排序15. 对下列四个序列用快速排序方法进行排序，以序列的第一个元素为基准进行划分。在第1趟划分过程中,兀素移动次数最多的是序列()A、 70, 75, 82, 90, 23, 16, 10, 68C、 82, 75, 70, 16, 10, 90, 68, 23 二、填空题1 .下列程序段的

5、时间复杂性的量级为0 (m*n )for (i=0; i<m; i+)for (j=0; j< n; j+)t=t+1;2. 索引文件由索引表 和主文件两部分组成。3. 在一个不带有头结点的非空单链表中，其结点形式为 结点，则需执行下列语句序列：B、 70, 75, 68, 23, 10, 16, 90, 82D、 23, 10, 16, 70, 82, 75, 68, 90data | next ,若要在指针q所指结点之后插入一个p=malloc(size); p->data=x;p->n ext=q->n ext ;q->n ext=p;4. 设链栈的栈

6、顶指针为Is,栈不空的条件为Is! =NULL或等价叙述5. 遍历图的基本方法有深度优先搜索和广度优先搜索。其中，深度优先搜索 是一个递归过程。栈的基本运算表示应为pop(S),pop(S),pop(S)。push (S,1), push (S,2) , push ( S,3) , push (S,4), pop(S),pop(S), push(S,5),输出端输入端栈S123456. 如图所示，设输入元素的顺序为1, 2, 3, 4, 5，要在栈S的输出端得到序列 43521，则应进行的操作用7. 下图为某树的静态双亲链表表示:0A-11B02C03D14E2则结点D、E的双亲结点分别为B、

7、C&在下列树中，结点 H的祖先为 A、D、G9静态查找表的顺序查找算法中，通常采用设置岗哨的方式以确保查找不成功时循环也能终止执行，若给 定值为K，表的长度为n,查找表的数据单元用R.item表示，键值用key表示，则在表尾设置岗哨的相应方法描述为R.item n+1.key=K10对于二叉树的查找，若根结点元素的键值大于被查找元素的键值，则应该在该二叉树的左子树 上继续查找。11 采用二次探测法解决冲突问题，对于键值为K，容量为m的闭散列表，若散列地址为do,则发生冲突后，其第三个后继散列地址d3为（do+22） mod m12 .对一组记录（54, 38, 96, 23, 15,

8、72, 60, 45, 83）进行直接插入排序时，当把第7个记录60插入到已排序的有序表时，为寻找其插入位置需比较3次。13. 对n个元素进行冒泡排序时，最少的比较次数是n-1三应用题1. 已知序列(17, 18, 60, 40, 7, 32, 73, 65, 趟的过程。解：依题意：初始(17, 18, 60, 40, 7, 32, 73, 65, 85)85），请给出采用冒泡排序法对该序列作升序排序时每1 趟(17, 18, 40,乙32,60,65,73,85)2 趟(17, 18, 7,32,40,60,65,73,85)3 趟(17, 7, 18,32,40,60,65,73,85)4

9、 趟(7, 17, 18,32,40,60,65,73,85)5 趟(7, 17, 18,32,40,60,65,73,85)第5趟兀素未交换，则排序结束。2. 如图所示，在栈的输入端有6个元素，顺序为A、B、C、D、E、F。能否在栈的输出端得到序列DCFEBA及EDBFCA ?若能，给出栈操作的过程，若不能，简述其理由。ABCDEF输出端输入端栈r解：（1）能得到序列 DCFEBA操作过程如下：push, push, push, push, pop, pop, push, push, pop, pop, pop, pop(2)不能得到EDBFCA因为要得到E需将A, B, C, D顺序入栈，

10、根据 LIFO原则，不可能B在C之前出栈。3 分别写出下列二叉树的先根、中根、后根遍历序列。 解：先根遍历序列：ABCDFGHE中根遍历序列：BADGFHCE后根遍历序列：BGHFDECA4已知无向图G的邻接表如下，请写出其从顶点V2开始的深度优先搜索序列。解：V2V4V0V1V3设散列iifiSJ为H(K) = K. mod 11 f做列我tt瞳为IN散列地址空何0 . , 10),蛉定丧(SUN, MON； TUE, WED.THU, FRJ, SAT)中，取肌诃的第-冷字母在英谄字母衷中的序号为琥值Q 构虚一幵般列舉*井用拴轻法解决有关地址冲突.(7分)评分细则：本小嚏共7分.菩错牛扣分

11、.四、iftttH (共14分)I、设以:叉进表为一丈栈的存储幼构.结点的结梅如下:Ichild 帕怡 rchild11中dau罐为駅数”试设计-个算世void change (bilrcpir r )；若詹点庄搂子的data域的 伉九于右踐子的dataS的值.則立换其左.右子神.(6S; oidchartgc(bitrcptrr)I bitrepir i iffr! = NULL)< if(r->khiM&&r->rchild&& (r->IchiJd>data>(r - >rchild )>dala) x =

12、r - > Ichildjr - > khid & r * > rchild：r * > ichild = x；(1分(1分<1 乂、change r > khjld)；changc( r - > rchild)；J注；算法中斗也取其它变最名；左右子祐的交换也可改为： X r - > rchild：r > rchild 世 a child；r->lchild=x;2 .已知奇偶转换排序如下所述：第一趟对所有奇数i，将ai和ai+1进行比较，第二趟对所有偶数i，将ai和ai+1进行比较，每次比较时若ai>ai+1，则将两者

13、交换，以后重复上述二趟过程交替进行，直至整个数组有序。（1）试问：排序结束的条件是什么？（2） 编写一个实现上述排序过程的算法：void oesort （int a , int n）。解：(1)在一趟奇排序和一趟偶排序时均不发生数据交换。(2)void oesort ( int a , int n )int i, flag, t; doflag=0;for (i=1; i<n; i+)if (ai > ai+1)flag=1;t= ai+1; ai+1= ai; ai=t; i+;while (flag!=0);Whe n you are old and grey and full

14、 of sleep,And no ddi ng by the fire, take dow n this book,And slowly read, and dream of the soft lookYour eyes had once, and of their shadows deep;How many loved your mome nts of glad grace,And loved your beauty with love false or true,But one man loved the pilgrim soul in you,And loved the sorrows

15、of your cha nging face;And bending dow n beside the glow ing bars,Murmur, a little sadly, how love fledAnd paced upon the mountains overheadAnd hid his face amid a crowd of stars.The furthest dista nee in the worldIs not betwee n life and deathBut whe n I sta nd in front of youYet you don't know thatI love you.The furthest dista nee in the worldIs not whe n I sta nd in front of youYet you can't see my loveBut whe n un doubtedly knowing the love from bothYet cannot be together.The furthest dista nee in the worldIs not being apart while being in loveBut whe n I p