2008年1月全国自考试题数据结构试卷

(2) 简述算法f30的功能。 void f30(LinkList L) {

//L为带头结点单链表的头指针 LinkList p,q; P =L;

while (p &&p–>next){ q = p–>next; p–>next =q–>next; p =q–>next; free(q); } } (1) (2)

31.算法f31的功能是借助栈结构实现整数从10进制到8进制的转换，阅读算法并回答问题： (1) 画出n为十进制的1348时算法执行过程中栈的动态变化情况; (2) 说明算法中while循环完成的操作。 void f31(int n) //n为非负的十进制整数 { int e; SeqStack S; InitStack(& S); do{

Push(& S,n%8); n =n/8; }while (n);

while ( ! StackEmpty(& S)){ e =Pop(& S); printf (〞%ld〞,e);

5

} } (1) (2)

32.已知以二叉链表作二叉树的存储结构，阅读算法f32，并回答问题： (1) 设二叉树T如图所示,写出执行f32(T)的返回值; (2) 简述算法f32的功能。 int f32(BinTree T) { int m, n; if(! T) return 0; else{

m= f32(T–>lchild); n = f 32(T–>rchild); if(m>n)return m +1; else return n+1; } } (1) (2)

33.设有向图邻接表定义如下； typedef struct{

VertexNode adjlist[Max VertexNum];

int n,e; //图的当前顶点数和弧数 } ALGraph;

//邻接表类型

6

其中顶点表结点VertexNode结构为： vertex firstedge

边表结点EdegNode结构为： adjvex next

阅读下列算法f33，并回答问题： (1)已知有向图G的邻接表如图所示, 写出算法f33的输出结果; (2)简述算法f33的功能。 void dfs (ALGraph *G,int v) {

EdgeNode * p; visited[v]=TRUE;

printf(〞%c〞,G–>adjlist[v]·vertex);

for(p =G–>adjlist[v])·firstedge; p; p=p–>next) if(! visited[p–>adjvex])

dfs (G, p–>adjvex);

}

void f33(ALGraph *G) {

int v,w;

for(v=0; v n; v ++) { for(w=0;wn; w++) visited[w]=FALSE; printf(〞%d: 〞,v); dfs(G,v); printf(〞﹨n〞); } } (1) (2)

7

五、算法设计题(本大题10分)

34.假设以单链表表示线性表,单链表的类型定义如下:

typedef struct node { DataType data; struct node *next; } LinkNode, *LinkList;

编写算法,将一个头指针为head且不带头结点的单链表改造为一个含头结点且头指针仍为head的单向循环链表,并分析算法的时间复杂度。

8