数据结构－03农信信管测验.doc

数据结构复习资料

华南农业大学期中测验
2004学年第二学期　 考试科目：　数据结构　　　
考试类型：（开卷/闭卷）　　　考试时间：　120  　分钟
学号                  姓名                 年级专业                     

单选题（每题2分，共 30 分）
研究数据结构就是研究（ ）
A．	数据的逻辑结构
B．	数据的存储结构
C．	数据的逻辑结构和存储结构
D．	数据的逻辑结构、存储结构及其数据在运算上的实现
链表不具有的特点是（  ）。
A.	可随机访问任一个元素       B. 插入删除不B.	需要移动元素
C. 不必事先估计存储空间       D. 所需空间与线性表的长度成正比
设一个栈的输入序列是A、B、C、D，下列出栈序列中不正确的是（  ）
A．ABCD   B. DCBA    C.  ACDB     D. DABC
一棵深度为7（根的层次号为0）的完全二叉树有（   ）个叶子结点。
A.  256     B. 255     C. 128      D. 127
二维数组A[4][5]采用行序为主序方式存储，每个数据元素占4个存 储单元，且A[2][2]的存储地址是1000，则A[3][3]的地址是（ ）
A．1005     B. 1006    C. 1024     D. 1026.
若循环队列用数组A[0,m-1]存放元素，其头尾指针分别为front 和rear，则当前队列的长度是（  ）。
A. (rear-front+m)%m             B. rear-front+1
C. rear-front-1                  D. (rear-front)%m 
7．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为0，则编号位39的结点的左孩子的编号为（ ）。
A．78    B. 79     C.  80       D.  81
8．利用逐点插入法建立序列（50，72，85，75，20，45，35，30，26）对应的二叉排序树以后，查找元素45要进行（  ）元素的比较。
A．3次   B. 4次    C. 7次     D. 9次
9．以下哪个数据结构，是非线性数据结构（）
A. 树     B. 字符串    C. 队    D. 栈
10. 两种常用的稀疏矩阵压缩存储方式是（   ）。
A. 二维数组和三维数组         B. 三元组和散列
C. 三元组表和十字链表         D. 散列和十字链表


判断题（每题2分，共10分）
线性表的每一个结点都有一个前驱和一个后继。
一维数组实质是线性表的一种。
顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。
任意一棵树均可转换成二叉树，再进行存储。
将一新结点插入二叉排序树中，该结点既可以成为叶子结点也可以成为非叶子结点。

完成算法设计（每空3,共18分）
2．	单链表的删除
typedef  struct Node
{ DataType info;
  struct Node *link;			
} *PNode,*LinkList;

int  delete_link( LinkList llist, DataType x )
/* 在llist带有头结点的单链表中删除第一个值为x的结点 */
    { PNode p, q;      	
	           ⑴           ;     /*找值为x的结点的前驱结点的存储位置 */
      while( p->link != NULL && p->link->info != x )
       	    ⑵    	;
      if( p->link == NULL )  			/* 没找到值为x的结点 */
		 { printf(”Not exist!\n ”);
           return(0);
		}
	  else 
{	q = p->link;	  			/* 找到值为x的结点 */
       		       ⑶               ; 	/* 删除该结点 */
       		       ⑷               ;      
           return(1); 
		}
 }
3．	进队列?
#define MAXNUM 100
struct SeqQueue
{ DataType a[Maxnum];
 int f,r;
};
typedef struct SeqQueue *PSeqQueue;
void  enQueue_seq( PSeqQueue paqu, DataType x )
/* 在队列中插入一元素x */
{
  if(            ⑸                )
      printf( "Full queue.\n" );
  else
	{
	  paqu->q[paqu->r] = x;
	            ⑹                ;
	 }
}



构造题（共8分x2=16分）

1．	假设一颗二叉树的前序遍历序列为 ABDFCE ，2．	中序遍历序列DFBACE。
要求：（1）画出该树(5分)
     （2）写出该树的后序遍历序列(5分)。
3．	用给出的一组字符A，4．	B，5．	C，6．	D，7．	E的权值是{3，8．	4，9．	5，10．	6，11．	8}，12．	按权值左小右大建立一棵哈夫曼树(6分)，13．	并给出每个字符的哈夫曼编码(2分)。
算法设计题（26分）
1．设计一个算法实现将由q所指向的新结点插入到单链表中指针p所指向的结点前。（12分）


2．设一棵二叉树以二叉链表为存储结构，类型定义如下：
struct node
{ int data;
  struct node *lchild,*rchild;
};
其中data域中存放一个整数。设计一个算法，求此二叉树中data域的值为最小的结点。（14分）
    
华南农业大学测验答题纸
2004学年第二学期　 考试科目：　数据结构　　　
考试类型：（闭卷）　　　考试时间：　120  　分钟
学号                  姓名                 年级专业                     

 
题号	一	二	三  	四	五	总分	   
得分							   
评阅人		 

1、	单选题（每题2分，2、	共 30 分）
 
题号	 1	2	3	4	5	6	7	8	9	10	   
答案											 
3、	判断题（每题2分，4、	共10分，5、	正确√、错误╳）
 
题号	 1	2	3	4	5	   
答案						 
6、	完成算法设计（每空3,共18分）


⑴                                   
⑵                                   
⑶                                   
⑷                                   
⑸                                   
⑹                                   
四、构造题（共16分）