(1)

(2)

四、算法阅读题（本大题共4小题，每小题5分，共20分）

30.假设以带头结点的单链表表示线性表,阅读下列算法f30,并回答问题:

(1)    设线性表为( a₁, a_2­, a₃, a_4­­­, a­₅, a₆, a₇ ), 写出执行算法f30后的线性表；

(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);

}

}

(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;                    //邻接表类型

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

边表结点EdegNode结构为：

阅读下列算法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 <G–>n; v ++) {

for(w=0;w<G–>n; w++)

   visited[w]=FALSE;

printf(〞%d: 〞,v);

dfs(G,v);

printf(〞﹨n〞);

}

}

(1)

(2)

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

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

typedef struct node {

   DataType data;

   struct node *next;

} LinkNode, *LinkList;

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

全国2007年10月高等教育自学考试

数据结构试题

课程代码：02331

一、单项选择题（本大题共15小题，每小题2分，共30分）

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1.下面程序段的时间复杂度为(      )

  s=0；

  for(i=1；i<n；i++)

    for(j=1；j<i；j++)

      s+=i*j；

A.O(1)                                  &nbs