2010级数据结构带答案_武科大

课程名称：   数据结构 A     适用专业年级：2010计算机\网络\软件 

考生学号：                          考 生 姓 名：                  

………………………………………………………………………………………………………

一、选择题（每小题2分，共20分）

1、将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是（   ）

    A.n-1        B.n        C.2n-1        D.2n

2、指针p1和p2分别指向两个无头结点的非空单循环链表中的尾结点，要将两个链表链接成一个新的单循环链表，应执行的操作为（ ）

A.p1－＞next=p2－＞next;p2－＞next=p1－＞next;

B. p2－＞next=p1－＞next;p1－＞next=p2－＞next;

C. p=p2－＞next; p1－＞next=p;p2－＞next=p1－＞next;

D. p=p1－＞next; p1－＞next= p2－＞next；p2－＞next=p;

3、如果将矩阵An×n的每一列看成一个子表，整个矩阵看成是一个广义表L，即L=((a11,a21,…,an1),( a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素，则求得a21的运算是（   ）

A. head (tail (head (L)))        B. head (head(head(L)))

C. tail (head (tail (L)))        D. head (head (tail (L)))

4、具有n个顶点、e条边的无向图的邻接矩阵中，零元素的个数为（   ）

A.e        B.2e        C.n2-2e        D.n2-1

5、若非连通无向图G含有21条边，则G的顶点个数至少为（   ）

A．7        B．8        C．21        D．22

6、某索引顺序表共有元素395个，平均分成5块。若先对索引表采用顺序查找，再对块中元素进行顺序查找，则在等概率情况下，分块查找成功的平均查找长度是（   ）

A.43        B.79        C.198        D.200

7、要以O（nlogn）时间复杂度进行稳定的排序，可用的排序方法是（   ）

A.归并排序        B.快速排序        C.堆排序        D.冒泡排序

8、设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是(    )      

 A．8         B．3         C．5       D．9 

9、已知有向图G=(V，E)，其中V={V1，V2，V3，V4}，E={，，，，}，图G的拓扑序列是（   ）

A.V1,V2,V3,V4         B.V1,V3,V2,V4

C.V1,V3,V4,V2    D.V1,V2,V4,V3

10、在下图中，从顶点1出发进行深度优先遍历可得到的序列是(   )

A.1 2 3 4 5 6 7

B.1 4 2 6 3 7 5

C.1 4 2 5 3 6 7

D.1 2 4 6 5 3 7

二、填空题（每空2分，共30分）

1、数据结构由数据的逻辑结构、存储结构和数据的（1）三部分组成。

2、设长度为n的链队列用只设尾指针的单循环链表表示，则出队操作的时间复杂度为（2），若用只设头指针的单循环链表表示，则出队操作的时间复杂度为（3）。

3、向一个栈顶指针为top的链栈中插入一个s指针所指结点的操作语句是（4）和（5）。

4、长度为11的有序表，采用折半查找，在等概率情况下查找成功的平均查找长度为（6）。

5、设一棵完全二叉树具有1000个结点，则此完全二叉树有(7)个叶子结点，有(8)个度为2的结点，有(9)个结点只有非空左子树，有(10)个结点只有非空右子树。

6、已知链表结点定义如下：

typedef  struct  node{

char  data［16］；

struct node   *next;

} LinkStrNode；

如果每个字符占1个字节，指针占4个字节，则该链表的存储密度是（11）。

7、使用一个100个元素的数组存储循环队列，如果采取少用一个元素空间的方法来区别循环队列的队空和队满，约定队头指针front等于队尾指针rear时表示队空。若为front=8，rear=7，则队列中的元素个数为（12）。

8、用5个权值{3, 2，4，5，1}构造的哈夫曼(Huffman)树的带权路径长度是（13）。

9、快速排序、简单选择排序和直接插入排序三种排序方法中，当待排关键字序列基本有序时，运行效率最高的是（14），比较次数与待排记录初始状态无关的是（15）。

三、分析题（共26分）

1(8分)已知一个森林的前序遍历序列为CBADHEGF，后序遍历序列为ABCDEFGH，画出森林。

2(8分)已知待排记录的关键字序列为{25，96，11，63，57，78，44}，请回答下列问题：

(1)写出堆排序的初始堆（大根堆）关键字序列；

写出堆排序1趟以后（交换与调整之后）的关键字序列；

(2)写出快速排序1趟以后的关键字序列；

写出快速排序2趟以后的关键字序列。

3(5分)假设具有n个结点的完全二叉树顺序存储在向量BT[1.. n]中，阅读下列算法，并回答问题：

若向量BT为：

画出执行函数f（BT,7,1）的返回结果，简述函数f的功能。

  BinTree  f(DataType   BT[],int n,int i)

 {

BinTree  p;

if  (i＞n)  return  NULL;

p=（BinTNode*）malloc(sizeof(BinTNode));

p－＞data=BT[i];

p－＞lchild=f(BT,n,i*2);

p－＞rchild=f(BT,n,i*2+1);

return   p;

}

4(5分)如图所示，在n×n矩阵A中，所有下标值满足关系式i+j＜n+l的元素aij的值均为0，现将A中其它元素按行优先顺序依次存储到长度为n(n+1)/2的一维数组sa中，其中元素a1，n存储在sa［0］。

(1)设n=10，元素a4，9存储在sa［p］，写出下标p的值；

(2)设元素ai，j存储在sa［k］中，写出由i,j和n计算k的一般公式。

四、程序设计题（共24分）

1(10分)将二叉树bt中每一个结点的左右子树互换的C语言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队，出队和判别队列是否为空的函数，请填写算法中得空白处，完成其功能。

typedef struct node{

int data;

struct node *lchild, *rchild; 

}btnode; 

void  EXCHANGE(btnode *bt)

{ btnode *p, *q;

  if (bt)

{ ADDQ(Q,bt);

   while(!EMPTY(Q))

     { p=DELQ(Q);

  q=(1)___; 

p->rchild=(2)___; 

(3)___=q;

if(p->lchild) (4)___;

if(p->rchild) (5)___;

}

}   

}

2(6分)已知有向图的邻接表和邻接矩阵定义如下：

﹟define  MaxNum  50                        ∥图的最大顶点数

typedef  struct  node {

      int  adjvex;                        ∥邻接点域

struct  node  *next;                        ∥链指针域

}   EdgeNode;                        ∥边表结点结构

typedef   struct{

    char  vertex；                        ∥顶点域

    EdgeNode  *firstedge;                        ∥边表头指针

}   VertexNode;                        ∥顶点表结点结构

typedef   struct {

    VertexNode   adjlist [MaxNum];                        ∥邻接表

    int  n,e;                        ∥图中当前顶点数和边数

}  ALGraph;                        ∥邻接表描述的图

typedef  struct{

   char   vertex[MaxNum];                        ∥顶点表

   int   adjmatrix [MaxNum][MaxNum];                        ∥邻接矩阵

   int   n,e;                        ∥图中当前顶点数和边数

} AMGraph;                        ∥邻接矩阵描述的图

下列算法是将邻接表描述的图G1改为邻接矩阵描述的图G2，在空白处填上适当内容使算法完整：

void   f（ALGraph G1,AMGraph *G2）

{   int    i,   j;

    EdgeNode   *p;

G2－＞n=G1.n;

     G2－＞e=     (1)     ;

for   (i=0;  i＜G1.n;  i++)

{    G2－＞vertex[i]=     (2)     ;

p=G1.adjlist[i].firstedge;

for   (j=0;   j＜G1.n;  j++） G2－＞adjmatrix[i][j]=0;

while   (p)

{    G2－＞adjmatrix[i][p－＞adjvex]=1;

     (3)     ;

}

    }

}

3(8分)假设线性表采用顺序存储结构，其类型定义如下：

#define  ListSize  100

typedef  struct  {

int  data［ListSize］;

int  length;

}  SeqList;

编写算法，将顺序表L中所有值为奇数的元素调整到表的前端。

请先用简短的中文说明你的算法思路，然后编程：void  f (SeqList *L)