数据结构(B卷)

1、数据结构试卷(B卷)班级:_学号:_姓名:_得分:_题号一二三四五六七八九十成绩复核得分            阅卷           题目部分，(卷面共有46题,100分,各大题标有题量和总分)一、判断正误(11小题,共11分)1集合与线性表的区别在于是否按关键字排序。(    ) 2两个栈共用静态存储空间，对头使用也存在空间溢出问题

2、。（    ）3栈和队列都是线性表，只是在插入和删除时受到了一些限制。（    ）4队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（    ）5广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（    ）6有n个数存放在一维数组A1n中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同 7快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少。（    ）8外部排序与外部设备的特性无关

3、。（    ）9影响外排序的时间因素主要是内存与外设交换信息的总次数。(  ) 10用希尔(Shell)方法排序时，若关键字的初始排序杂乱无序，则排序效率就低。（    ）11程序一定是算法。(    )二、单项选择题(24小题,共50分)1(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。   (2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。   (3) 静态链表与动态链表在元素

4、的插入、删除上类似，不需做元素的移动。以上错误的是 A、（1），（2）      B、（1）       C、（1），（2）,(3)      D、（2）2在一个长度为n的顺序表中，在第i个元素(1in+1)之前插入一个新元素时须向后移动（    ）个元素A、n-i       B、n- i+l    

5、60;  C、n-i-1       D、i3设栈的输入序列是l 2、.、m，若输出序列的第一个元素是n，则第i个输出元素是A、不确定    B、n-i+1    C、 i     D、 n-i4执行完下列语句段后，i值为     int   f(int x)     return  (x>0) ? x

6、* f(x-1):2);      int i  ;      i =f(f(1);A、2            B、 4          C、 8           D、无限递归5若一

7、个栈的输入序列为1,2,3,n，输出序列的第一个元素是i，则第j个输出元素是 A、 i-j-1          B、 i-j            C、 j-i+1      D、 不确定的6数组A0.5,0.6的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A5，5的地址是 A、 1175&

8、#160;          B、 1180           C、 1205           D、 12107一个有n个顶点的无向连通图，它所包含的连通分量个数为    A、 0      B、 l  

9、  C、 n    D、 n+l8下面的叙述中，不正确的是  A、关键活动小按期完成就会影响整个工程的完成时间  B、任何一个关键活动提前完成，将使整个工程提前完成  C、所有关键活动都提前完成则整工程将提前完成  D某些关腱活动若提前完成，将使整个丁程提前完成9散列函数有有一 个共同性质，即函数值应按_取其值域的每一个值。A、最大概率  B、最小概率C、同等概率  D、平均概率10下面关于B-树和B+树的叙述中，不正确的结论是  A、B-树和B+树都能有效地支持顺序查找 

10、B、B-树和B+树都能南有效地支持随机查找  C、B-树和B+树都是平衡的多分树   D、B-树和B+树都可以用于文件索引结构11对线性表进行二分检索时，要求线性表必须  A、以顺序存储方式存储              B、以链式存储方式存储  C、以顺序存储方式存储且数据有序    D、以链式存储方式存储且数据有序12在顺序表(n足够大)中进行顺序查找，其查找不成功的平均长度是

11、60;  A、(n+1)2    B、+1      C、n     D、n+113设有一个用线性探删法解决冲突得到的散列表如图所示：    散列函数为H(k)=kl1，若要查找元素14，探测的次数是    A、8    B、9    C、3      D、6 14下面排序方法中，时间复杂

12、性不是的是    A、直接插入排序  B、二路归并排序  C、冒泡排序    D、直接选择排序15对任意的7个关键字进行排序，至少要进行（    ）次关键字之间的两两比较。    A、13    B、14    C、15    C、16    E、1716下列排序算法中，在待排序数据已有序时，花费时间反而最多的是(  

13、   )排序。     A、 冒泡  B、 希尔  C、 快速  D、 堆  17对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是  A、直接插入    B、二分法插入    C、快速排序  D、归并排序18下述几种排序方法中，要求内存量最大的是    A、插入排序    B、选择排序    C、快速排序

14、0;   D、归并排序19在对一个元素进行直接选择排序过程中，第i趟需从（    ）个元素中选择出最小值元素。    A、n-i+1    B、n-i    C、 i    D、i+120下面给出的4种排序法中（  ）排序是不稳定排序法。    A、插入   B、冒泡    C、二路归并    D、堆21下列

15、排序算法中(    )不能保证每趟排序至少能将一个元素放到其最终的位置上。A.快速排序      B、 shell排序      C、 堆排序      D、冒泡排序  22下列排序方法中，哪一个是稳定的排序方法？A、直接选择排序      B、二分法插入排序      C、希尔排序  &

16、#160;     D、快速排序23算法的计算量的大小称为计算的A、效率          B、 复杂性       C、现实性           D、难度24下面说法错误的是  (1)算法原地工作的含义是指不需要任何额外的辅助空间  (2) 在相同的规模n下，复杂度O(n)的算法在时间

17、上总是优于复杂度O(2n)的算法   (3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界  (4)同一个算法，实现语言的级别越高，执行效率就越低   A、(1)      B、(1),(2)       C、(1),(4)       D、(3)三、填空题(11小题,共39分)1已给如下关于单链表的类型说明：    TYPE  

18、;       list=node ;node=RECORD   data:  integer;   next:  list; END; 以下程序采用链表合并的方法，将两个已排序的单链表合并成一个链表而不改变其排序性（升序），这里两链表的头指针分别为p和q.PROCEDURE mergelink(VAR p,q:list):  VAR h,r: list;  BEGIN   （1）_  h.next:= NIL; r:=h;&

19、#160; WHILE(p<>NIL) AND (q<>NIL)   DO       IF (p.data<=q.data)THEN  BEGIN   （2）_； r:=p; p:=p.next；  END     ELSE  BEGIN  （3）_； r:=q; q:=q.next;   END;  IF (p=NIL)  THEN  r.ne

20、xt:=q;    （4）_； p:=h.next; dispose(h); END; 2设二维数组A-20.30,-30.20, 每个元素占有4 个存储单元, 存储起始地址为200.如按行优先顺序存储,则元素 A25,18的存储地址为       ；如按列优先顺序存储,则元素A-18,-25的存储地址为       。3已知a数组元素共5个，依次为12，10，5，3，1；b数组元素共4个，依次为4,6,8,15，则执行如下所

21、示的过程语句sort后得到c数组各元素依次为15,12,10,8,6,5,4,3,1；数组a,b,c的长度分别为l=5,m=4,n=9请在程序中方框内填入正确的成分，完成上述要求。      PROCEDURE   sort;        VAR   i, j, k, x: integer;  d: ARRAY1.m OF  integer;      &

22、#160; BEGIN           FOR i:=1 TO  m DO   di:=(1)_;          i:=1; j:=1; k:=1;          WHILE (i<=l) AND (j<=m) DO              BEGIN IF ai>dj THEN BEGIN(2)_; (3)_END