数据结构与算法试卷(B卷)

考核课程  数据结构与算法（ B 卷）考核班级  物联网141    

学生数  36   印数  40  考核方式   闭卷  考核时间 120   分钟

一、单项选择题（在每小题的四个备选答案中，选出一个正确答案。每小题1分，共33分）

1、算法是（  ）。

A. 计算机程序            B. 解决问题的计算方法            C. 排序算法            D. 解决问题的有限运算序列

2、一个顺序表的第一个元素的存储地址是90，每个元素的长度为2，则第8个元素的存储地址是（   ）。

A. 102            B. 104            C. 106            D. 108

3、在一个长度为n的顺序表中删除第i个元素，需要向前移动（   ）个元素。

A. n-i              B. n-i+1            C. n-i-1         D. i+1

4、在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next==head，则（   ）。

A. p指向头结点　        B. p指向尾结点            C. p的直接后继是头结点        

D. p的直接后继是尾结点

5、在以下的叙述中，正确的是（   ）。

    A. 线性表的顺序存储结构优于链表存储结构　        

B. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况

    C. 线性表的链表存储结构适用于频繁插入/删除数据元素的情况            

D. 线性表的链表存储结构优于顺序存储结构

6、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入一个结点s，则执行（   ）。

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

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

C. q->next=s; s->next=p;                               

D. p->next=s; s->next=q;    

7、在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是（   ）。

    A. p->next=q; q->prior=p; p->next->prior=q; q->next=q;

    B. p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;    

C. q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;    

D. q->next=p->next; q->prior=p; p->next=q; p->next=q;

8、在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是（   ）。

A. p=p->next;                B. p->next=p->next->next;           

C. p->next=p;                D. p=p->next->next;

9、在表长为n的顺序表中，当在任何位置删除一个元素的概率相同时，删除一个元素所需移动的平均个数为（   ）。

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

10、将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为（   ）。

A. O(1)        B. O(n)        C. O(m)        D. O(m+n)

11、线性表的顺序存储结构是一种（   ）存储结构。

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

12、循环链表的主要优点是（   ）。

A. 不再需要头指针            B. 已知某结点位置后能容易找到其直接前驱 

C. 在进行插入、删除运算时能保证链表不断开 

D. 在表中任一结点出发都能扫描整个链表    

13、在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（   ）。

    A. 访问第i个元素的前驱（1<）        B. 在第i个元素之后插入一个新元素()

    C. 删除第i个元素()                D. 对顺序表中元素进行排序

14、链表不具有的特点是（   ）。

A. 可随机访问任一元素　            B. 插入删除不需要移动元素        

C. 不必事先估计存储空间            D. 所需空间与线性表长度成正比

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

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

16、一个栈的输入序列为：1,2,3,4，则栈的不可能输出的序列是（   ）。

A. 1243          B. 2134        C. 1432        D. 4312        E. 3214

17、一个队列的入队序列是1，2，3，4，则队列的出队序列是（   ）。

    A. 1，2，3，4　                    B. 4，3，2，1    

    C. 1，4，3，2                        D. 3，4，1，2

18、正常情况下，删除非空的顺序存储结构的堆栈的栈顶元素，栈顶指针top的变化是（   ）。

A. top不变            B. top=0       C. top=top+1       D. top=top-1

19、栈的插入和删除操作在（   ）。

A. 栈底           B. 栈顶               C.  任意位置          D. 指定位置

20、在一个链队列中，假定front和rear分别为队头指针和队尾指针，删除一个结点的操作是（   ）。

A. front=front->next           B. rear= rear->next            

C. rear->next=front            D. front->next=rear

21、队和栈的主要区别是（   ）。

A. 逻辑结构不同                       B. 存储结构不同

C. 所包含的运算个数不同                D. 限定插入和删除的位置不同

22、队列的插入操作是在（   ）。

A. 队首　            B. 队尾            C. 队前            D. 队后

23、依次在初始为空的队列中插入元素a,b,c,d以后，紧接着做了两次删除操作，此时的队头元素是（   ）。

A. a            B. b                 C. c             D. D

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

    A. 31               B. 32           C.  33          D. 16

25、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..n]中，若结点R[i]有左孩子，则其左孩子是（   ）。

A. R[2i-1]            B. R[2i+1]            C. R[2i]               D. R[2/i]

26、对某二叉树进行先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果是（  ）。

    A. DBFEAC        B. DFEBCA        C. BDFECA        D. BDEFAC

27、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（   ）。

A. 不发生改变　            B. 发生改变            C. 不能确定            D. 以上都不对

28、下面说法中正确的是（   ）。

A. 度为2的树是二叉树                             B. 度为2的有序树是二叉树           

C. 子树有严格左右之分的树是二叉树                D. 子树有严格左右之分，且度不超过2的树是二叉树

29、一个具有n个顶点的有向图最多有（   ）条边。

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

30、无向图中一个顶点的度是指图中（   ）。

A. 通过该顶点的简单路径数                B. 与该顶点相邻接的顶点数        

C. 与该顶点连通的顶点数                   D. 通过该顶点的回路数

31、设有1024个无序的元素，希望用最快的速度挑选出其中前5个最大的元素，最好选用（   ）。

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

32、快速排序方法在（   ）情况下最不利于发挥其长处。

A. 要排序的数据量太大                B. 要排序的数据中有多个相同值      

C. 要排序的数据已基本有序            D. 要排序的数据个数为奇数

33、排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（   ）。

A. 希尔排序             B. 冒泡排序           C. 插入排序                D. 选择排序

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

1. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的      有限集合。

2. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。其中，逻辑结构有       、      、      、      四种，常见的存储结构有       、      两种。

三、算法描述题（共40分）

（1）已知数组A={30，4，48，25，95，13，90，27，18},试写出在快速排序的过程中每次划分后数据的排序情况。【9分】

（2）请将序列{12，70，34，66，24，56，50，90，86，36}调整为极大化堆（大顶堆）。画出每一步的图示。【6分】

（3）请给出下面算法的执行过程图示（结合行号，画出该行代码导致的指针指向变化情况）。变量head指向的链表如下图所示。【15分】

struct node_T{

    int  data;

    node_T  *next;

};

void  function(node_T  *&head)

{

1node_T  *p=head, *q=p->next;

2p->next =NULL;

3while(q)

4{

5    p=q; 

6    q=q->next; 

7    p->next=head; 

8    head=p;

9}

}

（4）请给出下图的邻接矩阵，并使用Dijkstra算法求顶点1到其余各个顶点的最短距离。【10分】

1．已有队列的定义如下：

#define MAX_LEN    1024

struct queue_t{

    int  array[MAX_LEN];

    int  head; //记录队头的位置

    int  tail; //记录队尾的位置

    int  length; //记录队列中元素的个数

};

其中，各个变量的含义如下图所示：

请完成如下的操作，给出完整的代码：

（1）init(queue_t  &q); //初始化队列q 【3分】

（2）int get(queue_t  &q); //从队列q中取出头元素 【6分】

（3）bool isEmpty(queue_t  &q); //判断队列是否为空  【1分】

2．已有线性表的节点定义如下：

#define MAX_LEN    1024

struct  list_t{

    int  array[MAX_LEN];

    int  length; //记录线性表中元素的个数

};

请完成如下的操作，给出完整的代码：

（1）void  insertAt(list_t  &list,  int  pos,  int  d); //在线性表list的第pos位置插入元素d 。【10分】