学生姓名__________ 学号_________________院系___________ 班级___________ -------------------------------密------------------------------封----------------------------线--------------------------------- 烟台大学 2005～2006 学年第 1 学期 算法与数据结构试卷 A 考试时间为 120 分钟 四 三 一 二 题号 得分 阅卷人 五 总分 合分人 （答案填在后面的答题卡中，答在原题中的无效） 一、单项选择题（每题 1 分，共 20 分） 1、在数据结构中，从逻辑上可以把数据结构分为（ ）。 A、动态结构和静态结构 C、线性结构和非线性结构 D、内部结构和外部结构 B、紧凑结构和非紧凑结构 2、若某线性表中最常用的操作是取第 I 个元素和找第 I 个元素的前趋元素，则采用（ ）存储方式最节 省时间。 A、单链表 B、双链表 C、单向循环链表 D、顺序表 3、在含有 n 个结点的顺序存储的线性表中，在任一结点前插入一个结点所需移动结点的平均次数为 （ 4、非空循环单链表 head 的尾结点*p 满足（）。 D、(n+1)/2 C、(n-1)/2 ）。 A、n B、n/2 A、p->next=null B、p=null C、p->next=head D、p=head 5、一个栈的入栈序列是 a,b,c,d,e,则栈的不可能的输出序列是（ C、d c e a b B、d e c b a A、e d c b a ）。 D、a b c d e 6、表达式 a*(b+c)-d 的后缀表达式是（） A abcd+- B abc*+d- 7、循环队列的出队操作为（ C ）。 abc+*d- D -+*abcd A、sq.front=(sq.front+1)% maxsize； B、sq.front=sq.front+1； C、sq.rear=(sq.rear+1)% maxsize； D、sq.rear=sq.rear+1； 8、数组 A 中，每个元素 A[I，J]的长度为 3 个字节行下标 I 从 1 到 8，列下标从 1 到 10，从首地址 SA 开始连续存放在存储内，该数组按行存放是，元素 A[8，5]的起始地址为（ ）。 A、SA+141 B、SA+144 C、SA+222 D、SA+225 9、设有两个串 P 和 Q，求 Q 在 P 中首次出现的位置的运算称为（ ）。 A、连接 B、模式匹配 C、求子串 D、求串长 10、深度为 5 的二叉树至多有( )个结点。 A、16 B、32 C、31 D、10 11、设森林 T 中有 4 棵树，第一、二、三、四棵树的结点个数分别是 n1,n2,n3,n4,那么当把森林 T 转换 成一棵二叉树后，且根结点的右子树上有（ ）个结点。 A、n1-1 B、 n1 12、以下说法错误的是( C、 n1+n2+n3 ) D、 n2+n3+n4 A、一般在哈夫曼树中，权值越大的叶子离根结点越近 B、哈夫曼树中没有度数为 1 的分支结点 C、若初始森林中共有 n 棵二叉树，最终求得的哈夫曼树共有 2n-1 个结点 1 

-------------------------------密------------------------------封----------------------------线--------------------------------- D、若初始森林中共有 n 棵二叉树，进行 2n-1 次合并后才能剩下一棵最终的哈夫曼树 13、任何一个带权的无向连通图的最小生成树（ ） A、只有一棵 B、有一棵或多棵 C、一定有多棵 D、可能不存在 14、在有向图的邻接表表示中，下面哪一种操作最费时间？（ ） A、求某顶点的出度 B、求某顶点的入度 C、求图中顶点的个数 D、求从某顶点的出发的弧 15、以下说法正确的是（ ） A、连通图的生成树，是该连通图的一个极小连通子图。 B、无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。 C、任何一个有向图，其全部顶点可以排成一个拓扑序列。 D、有回路的图不能进行拓扑排序。 ）。 16、哈希表的平均查找长度（ A、与处理冲突的方法有关而与表的长度无关 B、与处理冲突的方法无关而与表的长度有关 C、与处理冲突的方法有关且与表的长度有关 D、与处理冲突的方法无关且与表的长度无关 17、用线性探测法查找散列表，可能要探测多个散列地址，这些位置上的键值（ ） A、一定都是同义词 B、一定都不是同义词 C、都相同 D、不一定都是同义词 18、设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查 找法查找键值为 35 的结点时，经（ ）次比较后查找成功。 A、2 B、3 C、4 D、 6 19、一组记录的排序码为（46，79，56，38，40，84），一趟排序的结果为（40，38，46，56，79，84）， 则采用的是（ ）排序算法。 B、直接插入 A、起泡 C、快速 D、2-路归并 20、一个含 1000 个记录的文件，利用内部排序的方法得到 10 个初始顺串，对其进行 3-路平衡归并，若 每次访问外存可以读/写 100 个记录，则归并排序过程中对外存读记录和写记录的总次数为（ ）。 A、20 B、30 C、40 D、60 二、判断题（正确打√，错误打×，每题 1 分，共 10 分） 1、数据元素是数据的最小单位。 2、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。 3、在顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢”。 4、使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间。 5、二叉树是树的特殊形式。 6、已知二叉树的前序遍历和后序遍历序列不能唯一地确定这棵树。 7、用邻接矩阵法存储一个图时，所占用的存储空间大小不仅与图中结点个数有关，而且与图的边数有关。 8、连通分量是无向图中极小连通子图。 9、采用分块查找方法，既能实现线性表所希望的较快的查找速度，又能适应动态变化的需要。 10、如果某种排序算法是不稳定的，则该方法没有实际意义。 三、简答题（每题 6 分，共 48 分） 1． 模式串 t= ‘ababcacb’，求 t 的 next 函数值。 2． 画出 和下 列已 知序列 对应 的二 叉树 T：中 序遍 历序 列为： A B C BDCEAFHG；后序遍历序列为：DECBHGFA 3． 画出如图 3.3 中的二叉树对应的树（森林）。 4． 给定权值 2，3，4，6，8，10，12，构造相应的哈夫曼树，并 D 图 3.3 E F G H I J K 2 

-------------------------------密------------------------------封----------------------------线--------------------------------- 计算其带权路径长度。 5． 给出邻接矩阵如图 3.5，顶点集是{V1,V2,V3,V4,V5},从结点 V1 出发(1)画广度 优先生成树（2）按 prim 算法求最小生成树 6． 对图 3.6 所示的有向网，试利用 Dijkstra 算法求从源点 1 到其他各顶点的 最短路径。 7． 用图示给出关键字序列（92，37，86，33，12，57，25）初 始建小顶堆和输出前两个最小关键字后重建堆的过程。 8． 已知散列函数为 H(K)=K mod 13,健值序列为 47，26，120， 08，39，68，96，23，70，63，57，采用链地址法处理冲突， 试构造散列表，并计算查找成功的平均查找长度。 10 4 15 5 10 四、算法设计题（第一题 6 分，第二、三题各 8 分，共 22 分） 1．设 BT 是二叉树根结点的指针，编写递归算法求二叉树 BT 的 高度 4 6 10 图 3.6    1   12  5   10  30 10  2 4          图 3.5 1 5 12 8 9  8  9  4 2  20 2 2 1 15 4 3 2．设有两个非递减有序的顺序结构线性表 LA 和 LB，结点的关 键字为整数，长度分别为 m 和 n。LA 的空间足够大，编写算 法实现将表 LB 合并到表 LA 中，合并后的表 LA 仍然是非递减有序的。（要求算法复杂度为 O(m+n)）。 3．编写算法实现快速排序。 一、单项选择题 答 题 卡 1． 11． 2． 12． 3． 13． 4． 14． 5． 15． 6． 16． 7． 17． 8． 18． 9． 19． 10． 20． 二、判断题 1． 2． 3． 4． 5． 6． 7． 8． 9． 10． 三、简答题 3 

-------------------------------密------------------------------封----------------------------线--------------------------------- 四、算法设计题 4