2007-2008学年《数据结构》A.doc

华侨大学《数据结构》试卷（A）
系别： 班级： 学号：
姓名： 考试日期： 年 月 日
题号一二三四五总分得分一、选择题（每题1.5分，共15分）
1、若长度为n的线性表采用顺序存储结构，删除它的第i数据元素之前，需要先依次向前移动（）个数据元素。
A.n-i B.n+i C.n-i-1 D.n-i+1
2、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（）。
A.顺序表 B.用头指针表示的单循环链表
C.用尾指针表示的单循环链表 D.单链表
3、将一个递归算法改为对应的非递归算法时，通常需要使用（）。
A.栈 B.队列 C.循环队列 D.优先队列
4、设有两个串t和p，求p在t中首次出现的位置的运算叫做（）。
A.求子串 B.模式匹配 C.串替换 D.串连接
5、设有一个二维数组A[20][30]，以行为主序储存，假设A[0][0]存放位置在64410，每个元素占据一个储存空间，则A[4][5]存储在（）位置。
A.69210 B.62610 C.76910 D.72410
6、由权值分别为3,8,6,2,5的叶子结点生成一棵赫夫曼树，它的带权路径长度WPL为（）。
A.24 B.48 C.72 D.53
一个无向连通图的生成树是含有该连通图的全部顶点的（）。
A.极小连通子图 B.极小子图 C.极大连通子图 D.极大子图
8、具有n个顶点的有向完全图可包含（）条有向边。
A．n-1 B．n C．n(n-1)／2 D．n(n-1)
9、设有一个用开放定址法的线性探测再散列处理冲突的哈希表如下：
0123456789101325801617614哈希函数为H（key）=key%11，若要查找关键字14的记录，所需的探测次数是（）。
A.3 B.6 C.7 D.9
10、在下列排序方法中，不稳定的排序是（）。
A.直接插入排序 B.归并排序 C.快速排序 D.冒泡排序
二、填空题（每空1分，共10分）
1、数据的逻辑结构被分为集合、 和 网状结构四种。
2、在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的 、 和值三项。
3、一棵高度为5的二叉树中最少含有 个结点，最多含有 个结点；一棵高度为5的完全二叉树中，最少含有 个结点，最多含有 个结点。
4、在线性表中采用折半查找法（二分查找法）查找一个数据元素，线性表中元素应该按值有序，并且采用 存储结构。
5、若对序列(49，38，65，97，76，13，27，50)采用简单选择排序法排序，则第二趟结束后序列的状态是 。
三、解答题（每题5分，共30分）
1、指出下面算法中，带下划线语句的语句频度，并估计该算法的时间复杂度。
intSum_fact(intn)
{
ints=0,m,k,t;
for(m=1;m<=n;m++){
t=1;
for(k=1;k<=m;k++)t*=k;
s+=t;
}
returns;
}
2、设进栈序列为A,B,C,D,E，试问能否分别得到D,C,E,B,A和C,D,A,B,E的出栈序列？若不能得到，请说明理由；若可以得到，则写出以“push”表示进栈，“pop”表示出栈的栈操作序列。
3、已知二叉树bt的中序遍历序列为：BDACEFHGJIK，先序遍历序列为：EABDCFGHIJK，请构造该二叉树（画出树形），并画出对应的后序线索二叉树（不带头结点）。
A
B
C
E
D
F
无向图G
4、试画出如下图所示的无向图G的邻接表表示，要求邻接表中的各顶点的邻接链表中表结点按顶点序号从小到大排列。根据你所给出的邻接表，写出从A出发的广度优先搜索序列,并画出从顶点A出发的广度优先搜索（bfs）生成树。
5、已知表长为14的有序顺序表，试画出对其进行折半查找时的判定树，并计算等概率下查找成功的平均查找长度和查找不成功的平均查找长度。
6、已知待排序序列为（48，70，33，65，24，56，12，92，86，22），给出采用快速排序算法进行关键字从小到大排序时第一趟分划的详细过程。（取第一个关键字为支点关键字）
四、算法阅读题（每题5分，共15分）
1、设list为带头结点的单链表头指针，阅读下面算法，指出该算法的功能。
typedefstructNode{
charname[10];
intage,score;
structNode*next;
}*LinkList;
voidfun1(LinkList&list,intorder)//order表示结