(专升本)数据结构A卷参考答案

专升本)数据结构A卷参考答案:

简答题

1,数据结构是相互之间存在一种或多种特定关系的数据元素的集合.这种数据元素相互之间的关系称为结构.可以将数据结构形式化地定义为二元组:Data_Structure=(D,S)其中:D是数据元素的有限集,S是D上关系的有限集.

数据结构课程主要讨论数据的逻辑结构,物理结构和操作三个方面的问题.

2,算法的时间复杂度是指算法中各语句的频度之和T(n),其中频度指语句的执行次数,n指问题的规模,一般为数据的输入量.

渐近时间复杂度:当问题的规模n趋于无穷大时,T(n)的数量级(阶).记为T(n)=O( f(n) ).

这里\"O\"是一种近似表示法,其含义是:在n较大时,该算法的运行时间和f(n)成正比,或者说,T(n)的数量级和f(n)的数量级相同.

实际中,将渐近时间复杂度简称为时间复杂度,用以描述算法的时间特性.

3,顺序表的优点:

(1)可直接求出存储地址(随机存储结构),结构简单,便于随机访问表中的任一元素.

(2)存储密度高.

顺序表的缺点:

(1)不便于插入和删除.(移动元素次数多,平均约需移动一半元素)

(2)不便于扩充表的容量.

(3)不能有效地利用内存空间.

单链表的优点:

(1)结点空间可动态申请动态释放.

(2)每个结点有指针域指示逻辑顺序,进行插入删除操作时不需移动元素.

单链表的缺点:

(1)不能随机访问表中任一元素,效率低.

(2)存储量可随意扩充,但新增加的存储空间可能与以前的不邻接,故需要设立一些存放地址用的存储单元.

4,入栈算法:

int push (qstype *s, elemtype x)

{

if (s→top==MAXNUM-1)

return 0;

else { s→top++;

s→stack [s→top]=x;

return 1; }

}

出栈算法:

elemtype pop(qstype *s)

{

if (s→topnext!=NULL)

if (p->data!=p->next->data)

p=p->next;

else

{ q=p->next;

p->next=q->next;

free(q);

}

}

return head;

}

2,#define m 100

typedef struct btreenode

{ elemtype data;

struct btreenode *left;

struct btreenode *right;

} btree; /*二叉链表的形式化定义*/

void postorder(btree * b)

{

btree * stack[m],*p;

int tag[m],top=0;

p=b;

do

{

while (p!=NULL)

{ top++;

stack[top]=p;

tag[top]=0;

p=p->left;

}

if (top>0)

{ p=stack[top];

if (tag[top]==1)

{ top--;

printf(\"%d\

}

if (top>0)

{ p=p->right;

tag[top]=1;

}

}

}while (p!=NULL&&top!=0)

}