数据结构(C语言)试卷(4)

1．组成数据的基本单位是（  ）

Ａ．数据项 Ｂ．数据类型

C．数据元素 ．数据变量

2．下面程序段的时间复杂度为（  ）。

 for(i=0;i ．O(m2)      ．O(n2)

 ．O(m+n)      ．O(m*n)

3．在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n+1)时，需向前移动（  ）个元素。

A．n-i ．n-i+1

C．n-i-1 ．i

4．在一个单链表中，已知*q结点是*p结点的前趋结点，若在*q和*p之间插入*s结点，则需执行（  ）。

A．sB．q->next=s; s->next=p;

C．p->next=s->next; s->next=p; D．p->next=s; s->next=q;

5．若让元素a，b，c依次进栈，则出栈次序不可能出现（  ）种情况。

 A．cba  B．bac

C．cab  D．acb

6．在一个链队列中，假定front和rear分别为队头和队尾指针，则插入*s结点的操作应执行（  ）。

Ａ．front-Ｂ．s->next=rear; rear=s;

C． D．s->next=front; front=s;

7．当采用顺序存储方式存储队列时，可能出现存储空间剩余，而不允许继续入队的情况，称为（  ）。

 ．溢出 ．队列不能用顺序存储方式

 ．数组存储空间过小  D．假溢出

8．一棵深度为k的满二叉树有（  ）个结点。

 A．2k ．2k-1

 ．2．2k

9．一棵完全二叉树的结点按层次遍历从1开始编号，如果编号为m的结点有双亲，则双亲的编号为（  ）。

A．2×m  B．m/2

C．m＋1  ．m-1

10．快速排序在（  ）情况下最不利于发挥其长处。

A．被排序的数据量很大 B．被排序的数据完全无序

C．被排序的数据已基本有序 D．被排序的数据中最大的值与最小值相差不大

二．填空题（30分）：每空2分，

1. 数据的逻辑结构被分为          、          、          和          四种。

2．在一个长度为n的顺序表中删除一个元素，最少需移动        个元素，最多需移动________个元素。

3．对于一个顺序栈作进栈运算时，应先判断栈是否为    ，判断的条件是              ，作出栈运算时，应先判断栈是否为    ，判断的条件是                。

4．栈的原则是                 。

5．在一棵二叉树上第5层的结点数最多为         。

6．设一颗完全二叉树共有50个叶子结点，则它共有________个度为2的结点。

7．在一个具有n个顶点的无向完全图中，包含有          条边，在一个具有n个顶点的有向完全图中，包含有          条边。

三．判断题（5×2分）

1．完全二叉树未必是满二叉树。(  )

2．线性表中的每个元素都有一个前驱元素和后继元素。(  )

3．二叉排序树采用先序遍历可以得到结点的有序序列。(  )

4．采用顺序结构存储线性表时，其地址可以是不连续的。(  )

5．一个有序的单链表不能采用折半查找法进行查找。(  ) 

四．应用题（20分）

1.画出带头结点的单链表、单循环链表和双向循环链表的示意图，并归纳三者的不同之处。（9分）

2.对于给定的一组关键码：83，40，63，13，84，35，画出用简单选择排序对上述序列进行操作的各趟结果。（5分）

3.下图所示的二叉树的先序、中序、后序的遍历结果。（6分）

五．算法设计题（20分）

1．有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大升序排列。要求写出完整代码。（12分）

2．写出折半查找的算法，并回答其使用的局限性。（8分）

答案及评分标准：

数据结构(C语言)答案及评分标准

一．选择题（10×2分）：每小题只有一个正确答案，错选或不选均不给分。

1．集合 线性结构 树型结构 图型结构 

2．0   n－1

3．满  top==MAXSIZE-1  空  top==-1。

4．后进先出

5．16

6．49

7．n

三．判断题（5×2分）

1．√；2．×；3．×；4．×；5．√

四．应用题（4×5分）

1.  

单链表：只有从头结点出发，才能访问到所有结点。

单循环链表：从任意一结点出发，均可访问到其他结点。

双向循环链表：既可以方便的找到前趋结点，又可方便的找到后继结点。

2．

83，40，63，13，84，35

13，40，63，83，84，35

13，35，63，83，84，40

13，35，40，83，84，63

13，35，40，63，84，83

13，35，40，63，83，84

3．

先序：ABDCEFG

中序：DBAFGEC

后序：DBGFECA

4．解决单链表的“第一个结点问题”，使头指针变量不为空。

五．算法设计题（20分）

1．

#define MAXSIZE 20

typedef int datatype;

typedef struct

{

}SeqList;

SeqList *init_SeqList();

void input(SeqList *L);

void output(SeqList *L);

void merge(SeqList *A,SeqList *B,SeqList *C);

main()

{

}

SeqList *init_SeqList()

{

}

void merge(SeqList *A,SeqList *B,SeqList *C)

{

}

void input(SeqList *L)

{

}

void output(SeqList *L)

{

}

2．

int Binary_Search(S_TBL tbl,KeyType kx)

{

    return flag;   

}

折半查找的局限性：

1．查找表要有序；

2．需要顺序存储结构