云南大学2003年硕士研究生入学考试《数据结构》试题
2007-02-01 23:30:55   来源：   评论：0 点击：

云南大学2003年硕士研究生入学考试试题

考试科目：《数据结构》

专业：系统分析与集成

一、填空（共3题，每题10分，共30分）

1、数据是对客观事物的        ，在计算机科学中是指        的总称。数据元素是       ，一个数据元素可由若干个        组成，数据对象是        的集合。

2、线性表是        队和栈是        的线性表，其中栈的插入和删除都在        进行，而对的插入在        进行，删除在    

进行。

3、一棵树中结点的度是        ，树的度是        ，二叉树的度

        。有向图中顶点V的入度是        ，出度是        。

二、解答与证明（共6题，每题10分，共60分）

1、设有三对角矩阵 ，按行将三条对角线上的元素存入一维数组 求

（1）用i，j表示k的下标变换公式；

（2）用k表示i，j的下标变换公式；

2、用带结点的链表分别表示栈和队列，栈的头指针用head表示，队头指针用front表示，尾指针用rear表示，分别求空栈和空队列的条件。若对为循环链队列且只有一个尾指针，则空队列的条件又如何表示？

3、证明：具有n个节点的完全二叉树的深度为 。

4、推导AOE网（边表示活动的网）中求关键路径的递推公式。

5、在7至22岁的青少年中选取一批样本数据，每个年龄段男女各取100名为一组样本，组内已有顺序编号为00至99，每个样本为5位编码，反映其性别、年龄和组内编号，设计一个哈希函数，使全部样本对应的哈希地址在1至3200之间且无冲突。

6、根据邻接矩阵A画出它对应的图，再画出其邻接表。

三、算法设计，可用类Pascal或C语言（共3题，每题20分，共60分）

1、在带头结点的链表中结点a前插入b；

2、用直接插入排序将n个整数 按增序排列；

3、在有序表（增序） 中折半查找关键字为r的元素。