2011-2012学年第一学期数据结构复习题.doc

《2011-2012学年第一学期数据结构复习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2011-2012学年第一学期数据结构复习题一、编程与简答题1.简述数据结构的三种结构2.简答线性表的顺序存储结构与链式存储结构的优点和缺点。3.画出下面数据序列（10、3、1、9、4、20、2、5）的排序二叉树。4.假设用于通信的电文仅由6个字母{A，B，C，D，E，F}组成，字母在电文中出现的次数分别为1，3，5，11，10，15。画出这6个字母构成哈夫曼树，并为这6个字母设计哈夫曼编码。5.定义一个函数，将一数组中数据按升序排序。6.定义一个方法，采用二分法对指定有序表数据进行查找，有序表：（8，12，1

2、6，30，45，56，64，78，82，89，90）7.简述栈和队列的相同点和不同点。8.简述什么是算法,简述算法的主要特点。9.将下面的森林变换成二叉树11.什么是AOV和AOE网，请举例说明12.定义一个方法,用递归求N!13.编程定义一个方法，对整型数组实现直接插入排序。14.编程定义一个方法，对整型数组实现冒泡排序。15.编程定义一个方法，对整型数组实现快速排序。16.编程定义一个方法，对整型数组实现直接选择排序。17.写出下面二叉树的前序、中序、后序序列。（1）前序遍历序列;（2）中序遍历序列;（3）

3、后序遍历序列：18.有如下图，用Kruskal算法建立其最小生成树。19.什么是稀疏矩阵？其特点有哪些？20.对于如下所示的稀疏矩阵A（1）写出该稀疏矩阵A的三元组表示；（2）画出稀疏矩阵A的三元组的顺序存储结构；（3）画出稀疏矩阵A十字链表存储结构21.定义一个方法,用递归求两个数的最大公因数。22.编程实现顺序队列的入队与出列操作。23.编程实现顺序栈的压栈与出栈操作。24.什么是完全二叉树？什么是满二叉树?。25.对于给定关键字序列A={24，15，19，3，12，27，31，10，39}，利用余数法构造

4、哈希函数，并实现y=31和y=18时的哈希查找过程。26.什么是最短路径？什么是关键路径？27.已知一个无向图的顶点集为{a,b,c,d,e}，其邻接矩阵如下所示（1）画出该图的图形；（2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。28.将下图中带权无向图和带权有向图转换为邻接矩阵。GCFDBAA（b）带权的有向图（a）带权的无向图29.下面为六大城市航班航程里程表。1)画出六大城市的交通网络图。2)画出该图的邻接矩阵。3)从上海出发，试写出上海到昆明的最短路径.上海（SH）北

5、京（BJ）南京（NJ）大连（DL）哈尔滨（HEB）昆明（KM）西安（XA）青岛（QD）上海（SH）-9005001800----北京（BJ）900-6001000----南京（NJ）500600--17001900--大连（DL）18001000---100010001000哈尔滨（HEB）--1700-----昆明（KM）--19001000---1500西安（XA）---1000----青岛（QD）---1000-1500--30.在学生信息管理系统中，需要通过学号、班级、年龄段等信息查找相关学生资料，查询

6、结果以列表形式显示。要求：以学生的学号进行排序，写出冒泡排序、插入排序、快速排序、直接选择排序、希尔排序、堆排序程序。学号姓名性别年龄班级20060301张彭男19媒体060120060302刘烨女20媒体060120060303宋琪女18媒体060120060304李美丽女21媒体0601王小强男22媒体060120060305二、填空题1、从逻辑上可以把数据结构分为（）两大类。2、以下数据结构中，（）是非线性数据结构。3、最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。4、

7、设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）。5、假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）。6、设有广义表D(a,b,D),其长度为（）.7、下面程序段的时间复杂度为（）for(inti=0;i

8、叉树的第I层上最多含有结点数为（）三、选择题1、设无向图的顶点个数为n，则该图最多有（）条边。A．n-1B．n(n-1)/2C．n(n+1)/2D．02、下列哪一种图的邻接矩阵是对称矩阵？（）A．有向图B．无向图C．AOV网D．AOE网3、在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动()个元素。A．n-iB．nC．iD．n-i+14、栈和队列的共同