98甲《数据结构与算法》试题.doc

98甲《数据结构与算法》试题
一. 单项选择(每题1分,共12分)
,可以将数据结构分成( )。
A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构
C. 线性结构和非线性结构 D. 内部结构和外部结构
,a2,…,an,进行插入操作的时间复杂性是( )。
A. O(n) B. O(n-i) C. O(n/2) D. O(n-1)
,2,3,…,n,元素经过栈后到达输出序列,若输出序列p1,p2,…,
pn的p1是n,则pi是( )。
A. i B. n C. n-i D. 不确定
( )。
A. rear = front B. rear+1 = front C. rear = Max D. front =0
,使用的操作是( )。
A. 连接 B. 求子串 C. 求串长 D. 模式匹配
,平均查找长度是( )。
A. B. C. D.
( )。
A. O(n) B. O(1) C. O(nlogn) D. O(logn)
,其先序序列是( )。
A. acbed B. cedba C. decab D. deabc
,具有分支结点数目是( )。
A. 2m-1 B. m-1 C. m+1 D. 2m+1
,具有边数目( )。
A. n-1 B. n+1 C. n D. n/2
( )。
A. 插入排序 B. 快速排序 C. 选择排序 D. 堆排序
,最好的方法是( )。
A. 插入排序 B. 快速排序 C. 选择排序 D. 冒泡排序
二. 根据题意,给出题目的结果(每题5分,共30分)
1. 求模式串的Next数组和改进的Next数组。
a a b a a b a a
Next[j]
改进Next[j]
2. 根据给定的关键字序列,构造平衡二叉查找树,要求边构造,边平衡。
关键字序列: 23,14,55,67,72,60,6,29,45,18。
3. 证明:对任一棵二叉树,如果叶结点数为n0,而其度为2的结点数为n2,则n0=n2+1
。
、6、12、14、39、53,散列函数H(key)=key mod 7,解
决冲突的方法是线性探测再散列,散列空间是0~9,构造散列表,求成功和失败的平均查
找长度。
、63、12、84、45、98、57、32、79、66、15进行快速排序的第一趟结果
。
,在4台磁带机上进行归并,给出初始归
并段的分布情况。是否需要增加虚段?
三. 完善给定的算法(每空2分,共20分)
1. Int weight[n+1][n+1];
Struct dege
{ int beg, en;
int length; }
Struct dege tree[n];
Void prim(weight, tree)
{
for