学生姓名__________ 学号_________________院系___________ 班级___________ -------------------------------密------------------------------封----------------------------线--------------------------------- 烟台大学文经学院 2005～2006 学年第 1 学期 算法与数据结构试卷 A 考试时间为 120 分钟 四 三 一 二 题号 得分 阅卷人 五 总分 合分人 （答案填在后面的答题卡中，答在原题中的无效） 一、单项选择题（每题 1 分，共 16 分） 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、以下说法错误的是( ) A、一般在哈夫曼树中，权值越大的叶子离根结点越近 B、哈夫曼树中没有度数为 1 的分支结点 C、若初始森林中共有 n 棵二叉树，最终求得的哈夫曼树共有 2n-1 个结点 D、若初始森林中共有 n 棵二叉树，进行 2n-1 次合并后才能剩下一棵最终的哈夫曼树 12、任何一个带权的无向连通图的最小生成树（ ） A、只有一棵 B、有一棵或多棵 C、一定有多棵 D、可能不存在 1 

-------------------------------密------------------------------封----------------------------线--------------------------------- 13、在有向图的邻接表表示中，下面哪一种操作最费时间？（ ） A、求某顶点的出度 B、求某顶点的入度 C、求图中顶点的个数 D、求从某顶点的出发的弧 14、哈希表的平均查找长度（ ）。 A、与处理冲突的方法有关而与表的长度无关 B、与处理冲突的方法无关而与表的长度有关 C、与处理冲突的方法有关且与表的长度有关 D、与处理冲突的方法无关且与表的长度无关 15、设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查 找法查找键值为 35 的结点时，经（ ）次比较后查找成功。 A、2 B、3 C、4 D、 6 16、一组记录的排序码为（46，79，56，38，40，84），一趟排序的结果为（40，38，46，56，79，84）， 则采用的是（ ）排序算法。 B、直接插入 A、起泡 C、快速 D、2-路归并 二、判断题（正确打√，错误打×，每题 1 分，共 10 分） 1、数据元素是数据的最小单位。 2、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。 3、在顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢”。 4、使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间。 5、二叉树是树的特殊形式。 6、已知二叉树的前序遍历和后序遍历序列不能唯一地确定这棵树。 7、用邻接矩阵法存储一个图时，所占用的存储空间大小不仅与图中结点个数有关，而且与图的边数有关。 8、连通分量是无向图中极小连通子图。 9、采用分块查找方法，既能实现线性表所希望的较快的查找速度，又能适应动态变化的需要。 10、如果某种排序算法是不稳定的，则该方法没有实际意义。 三、名词解释（每题 4 分，共 12 分） 1、数据结构 2、二叉树 四、简答题（每题 6 分，共 42 分） 1． 画出和下列已知序列对应的二叉树 T：中序遍历序列为：BDCEAFHG；后序遍历序列为：DECBHGFA 2． 画出如图 3.2 中的二叉树对应的树（森林）。 3． 给定权值 2，3，4，6，8，10，12，构造相应的哈夫曼树，并计算其带权路径长度。 4． 给出邻接矩阵如图 3.4，顶点集是{V1,V2,V3,V4,V5},从结点 V1 出发(1)画广度优先生成树（2）按 prim 3、强连通图 算法求最小生成树 5． 对图 3.5 所示的有向网，试利用 Dijkstra 算法求从源点 1 到其他各顶点的最短路径。 A B D 图 3.2 E F H I C J G K 图 3.4 1 5 12 8 9  8  9  2 4  10  2 4             1   12  5   10  10 4 15 5 10 4 6 30 10 图 3.5 2 4 3 20 2 1 15 6． 用图示给出关键字序列（92，37，86，33，12，57，25）初始建小顶堆和输出前两个最小关键字后 2 

-------------------------------密------------------------------封----------------------------线--------------------------------- 重建堆的过程。 7． 已知散列函数为 H(K)=K mod 13,健值序列为 47，26，120，08，39，68，96，23，70，63，57，采 用链地址法处理冲突，试构造散列表，并计算查找成功的平均查找长度。 五、算法设计题（每题 10 分，共 20 分） 1．设 BT 是二叉树根结点的指针，编写递归算法求二叉树 BT 的高度 2．编写算法实现快速排序。 答 题 卡 一、单项选择题 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