南昌大学_2008～2009学年第二学期数据结构期末考试标准答案A

南昌大学 2008～2009学年第二学期期末考试试卷

                                                                

试卷编号：      ( A )卷

课程编号：H61030006课程名称： 数据结构考试形式：  闭卷     

适用班级：  计算机系07级  姓名：             学号：          班级：                            

学院： 信息工程学院  专业：  计算机科学与技术  考试日期：               

题号

一

二

三

四

五

六

七

八

九

十

总分

累分人 签名

题分

20

10

40

15

15

100

得分

考生注意事项：1、本试卷共 7 页，请查看试卷中是否有缺页或破损。如有立即举手报告以便更换。

              2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。

一、填空题(每空2分，共20分)           

得分	评阅人

1、数据结构有线性结构、树结构、图结构、集合结构等几种逻辑结构。

2、已知某算法的执行时间为（n+n2）/2+log2(2n+1)，n代表问题规模，则该算法的时间复杂度是   O(n2)  。

3、在一个长度为n的顺序表中插入一个元素，最少需要移动  0 个元素，最多需要移动  n 个元素。

4、如果指针p指向一棵二叉树的一个结点，则判断p没有左孩子的逻辑表达式为

  p->lchild==NULL  。

5、一个无向连通图有6个顶点7条边，则其生成树有  5条边。

6、如果一个有向图有5个顶点，则它最多有  20 条弧。

7、如果某有向图的所有顶点可以构成一个拓扑排序序列，则说明该有向图  无环         。

8、顺序存储的队列如果不采用循环方式，则会出现虚溢出问题。

	二、判断题（每题1分，共10分，对的打√，错的打×） 得分	评阅人

1、如果某数据结构的每一个元素都最多只有一个直接前驱和一个直接后继结点，则必为线性表。（× ）

2、快速排序法在最坏的情况下时间复杂度是O（n2）。（√ ）

3、若有一个叶子结点是某子树的中序遍历的最后一个结点，则它必须是该子树的先序遍历的最后一个结点。（× ）

4、有向图的邻接矩阵的第i行的所有元素之和等于第i列的所有元素之和。（ × ）

5、二叉排序树中，任一结点的值都大于或等于其孩子的值。（× ）

6、一棵二叉排序树，根元素不一定是值最大的元素。（√ ）

7、顺序栈进栈操作时，一般情况下需要判断栈是否已满。（√ ）

8、如果某排序算法是稳定的，那么该方法一定具有实际应用价值。（× ）

9、对长度为100的有序线性表用二分法查找时，最小比较次数为0。（× ）

10、进栈、出栈操作的时间复杂度为O（1）。（√ ）

	三、简答题（共40分） 得分	评阅人

1、排序。

（1）写出线性表（26，45，12，2，30，6，15，29，16，2，18）采用快速算法排序后，第一趟结束时的结果。（5分）

20    12    26    45    30

  

（2）线性表采用插入排序算法排序几趟后，有序部分是（16，20，40），无序部分是（18，25），则下一趟的排序需要移动几个元素？写出下一趟结束时的结果。（5分）

  16 18     20     40，需移动2个元素

2、给出如图1所示的二叉树的中序遍历结果。（5分）   

D    B    A    F    G    E    C

3、已知5个结点的权值分别是4，6，1，13，7，请画出这结点构成的Huffman树。（5分）

	4、已知图2是一个无向图： （1）画出该无向图的邻接链表。（5分） （2）基于你给出的邻接链表，求从顶点C出发的广度优先遍历。（5分） （1） （2）C    A    D    B    G    F    E 5、（1）根据线性表（23，49，28，10，30，5，16），画出二叉排序树。（5分） （2）根据上述二叉排序树，查找数7，需要比较哪几个数？（5分） （1） （2）23    10    5
	四、程序填空题（共15分） 得分	评阅人

1、已知QUEUE表示循环队列的数据结构，函数leavequeue是将队头元素的值放入变量e，然后删除队头元素，操作成功返回1，否则返回0。完成以下程序。（10分）

typedef struct

{

  int data[100];

  int front;      /*队头元素的下标*/

  int rear；     /*等于队尾元素的下标加1*/

}QUEUE;

leavequeue(QUEUE *Q,int *e)

{

if(Q->front==Q->rear )

{

return 0;

}

*e = Q->data[Q->front];

Q->front = ;

    return 1;

}    

    

2. 已知一个单链表的表头指针 为h，每个结点含元素值data和下一结点的地址next。链表一共有5个结点，其元素值分别为100，200，300，400，500，经过下列语句后，输出什么结果？（本题5分）

for(p=h; p->data<300; p=p->next)

{

p->next = p->next->next;

}

printf(“%d”,p->data);

300
	五、编程题（共15分） 得分	评阅人

1．编写算法，删除顺序表前面的10个元素。如果顺序表中的元素少于10个，则删完为止。（7分）

已知顺序表的数据结构如下：

typedef struct

{

    int elem[100];

    int length;

} SQ；

int delete(SQ *s)

  {

int i;

if(s->length <= 10)

{

s->length = 0;

     retrun 0;

}

for(i=0; i {

s->elem[i] = s->elem[i+10];

     }

s->length -= 10;

return 0;

}
	2. 两个字符数组s,t中各放有一个串，尝试编写算法，将所有t中含有而s中没有的字符加到s中（逐个加到s的后面）。（8分） typedef struct   { char data[100]; int length;    } LIST;    tAddTost(LIST *s,LIST *t)   {        int i,j,op; for(i=0; ilength; ++i) { op=0; for(j=0; jlength; ++j) if(s->data[j] == t->data[i] op++; if(op==0) {s->data[j+1] = t->data[i]; ++s->length;} } }