数据结构试题答案.pdf

1 期中练习 一、单项选择题 期中练习 一、单项选择题(共 60 分，每小题 2 分) 1下面关于算法说法错误的是（ D ）（ D ） A算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 D. 以上几个都是错误的 2顺序表是线性表的（ C ） C ）存储表示。 A. 有序 B. 连续 C. 数组 C. 数组 D. 顺序存取 3一种抽象数据类型包括数据和( B B )两个部分。 A. 数据类型 B. 操作 B. 操作 C. 数据抽象 D. 类型说明 4当需要用一个形式参数直接改变对应实际参数的值时，则该形式参数应说明为( D ( D )。 A.基本类型 B.结构类型 C. 数组型 D. 指针型 D. 指针型 5以下说法正确的是（ B B ） 。 A. 数据结构的逻辑结构唯一地决定了该数据结构的存储结构。 B. 数据结构的逻辑结构独立于其存储结构。 B. 数据结构的逻辑结构独立于其存储结构。 C. 数据结构的存储结构独立于该数据结构的逻辑结构。 D. 数据结构仅由其逻辑结构和存储结构决定。 6下面关于线性表的叙述中，错误的是哪一个？ （A ） A线性表采用顺序存储，便于进行插入和删除操作。 （A ） A线性表采用顺序存储，便于进行插入和删除操作。 B线性表采用顺序存储，必须占用一片连续的存储单元。 C线性表采用链接存储，不必占用一片连续的存储单元。 D线性表采用链接存储，便于插入和删除操作。 7链表不具有的特点是： （C ） （C ） A插入、删除不需要移动元素 B不必事先估计存储空间 C可随机访问任一元素 C可随机访问任一元素 D所需空间与线性长度成正比 8非空的循环链表 head 的尾结点指针 p 满足： （D ）（D ） Ap =head Bp-next=NILL Cp=NILL D p-next= head D p-next= head 9. 对于一个头指针为 head 的带头结点的线性链表，判定该表为空表的条件是： （D ）（D ） Ahead=NULL Bhead!=NULL Cheadnext=head Dheadnext=NULL Dheadnext=NULL 10. 栈和队列都是（ C ） （ C ） A顺序存储的线性结构 B. 链式存储的非线性结构 C. 限制存取点的线性结构 C. 限制存取点的线性结构 D. 限制存取点的非线性结构 11为增加内存空间的利用率和减少溢出的可能性, 由两个栈共享一片连续的内存空间时, 应将两栈的( A )( A )分别设在这片内存空间的两端. A. 栈底 A. 栈底 B. 栈顶 C. 长度 D. 深度 12.从一个顺序存储的循环队列中删除一个元素时，首先需要( B )( B )。 A. 队头指针加一 B. 取出队头指针所指的元素 B. 取出队头指针所指的元素 C. 队头指针减一 D. 取出队尾指针所指的元素 13假定一个顺序存储的循环队列的队头和队尾指针分别为 front 和 rear，则判断队空 的条件为 ( C )( C )。 A. front+1 = rear B. rear+1 = front C. front = rear C. front = rear D. front = 0 14. 若用一个大小为 6 的数组来实现循环队列,且当前 rear 和 front 的值分别为 0 和 3,当从队列中删 除一个元素,再加入两个元素后,rear 和 front 的值分别为多少？ ( A ) A. 2 和 4 ( A ) A. 2 和 4 B. 1 和 5 C. 4 和 2 D. 5 和 1 15. 一个栈的输入序列为 1 2 3 4 5，则下列序列中不可能是栈的输出序列的是 ( A ) ( A ) A. 5 4 1 3 2 A. 5 4 1 3 2 B. 2 3 4 1 5 C. 2 3 1 4 5 D. 1 5 4 3 2 16、设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈 S。若每个元素出栈后 立即进入队列 Q,且 7 个元素出队的顺序是 bdcfeag, 则栈 S 是容量至少是多少？ ( B ) ( B ) A. 4 B. 3 B. 3 C. 2 D. 1 17. 有关二叉树下列说法正确的是 ( A ) A一棵二叉树的度可以小于 2 ( A ) A一棵二叉树的度可以小于 2 B 二叉树的度为 2 C二叉树中至少有一个结点的度为 2 D二叉树中任何一个结点的度都为 2 18一棵具有 35 个结点的完全二叉树的高度为( B )( B )。假定空树的高度为 0。 A. 5 B. 6 B. 6 C. 7 D. 8 19在一非空二叉树的中序遍历序列中，根结点的右边（A ） 。 A只有右子树上的所有结点 （A ） 。 A只有右子树上的所有结点 B只有右子树上的部分结点 C只有左子树上的部分结点 D只有左子树上的所有结点 20已知一棵二叉树的前序遍历结果为 ABCDEF,中序遍历结果为 CBAEDF,则后序遍历的结果为（A ） 。 ACBEFDA （A ） 。 ACBEFDA B FEDCBA C CBEDFA D不定 21. 某二叉树中序序列为 A,B,C,D,E,F,G，后序序列为 B,D,C,A,F,G,E 则前序序列是：( B ) AE,G,F,A,C,D,B BE,A,C,B,D,G,F BE,A,C,B,D,G,F CE,A,G,C,F,B,D D上面的都不对 22. 上题的二叉树对应的森林包括多少棵树 ( B )。 Al B2 B2 C3 D概念上是错误的 23在一棵树中，( C )( C )没有前驱结点。 A. 分支结点 B. 叶子结点 C. 树根结点 C. 树根结点 D. 空结点 24树的后根遍历序列等同于该树对应的二叉树的( B ). ( B ). A. 先序序列 B. 中序序列 B. 中序序列 C. 后序序列 25在下列存储形式中，哪一个不是树的存储形式？（ D ） （ D ） A双亲表示法 B孩子链表表示法 C孩子兄弟表示法 D顺序存储表示法 D顺序存储表示法 26在一棵树的左孩子-右兄弟表示法中，一个结点的右孩子是该结点的( A )( A )结点。 A. 兄弟 A. 兄弟 B. 父子 C. 祖先 D. 子孙 27下述编码中哪一个不是前缀编码（B ）（B ） 。 A （1，01，000，001） B （0，1，00，11） B （0，1，00，11） C （0，10，110，111） D （00，01，10，11） 28设有 13 个权值，用它们组成一棵哈夫曼树，则该哈夫曼树共有( C )( C )个结点。 A. 13 B. 12 C. 25 C. 25 D. 26 29利用 3,6,8,12 这四个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权路径长度为( C )。( C )。 A29 B38 C55 C55 D. 58 30已知一棵完全二叉树第 6 层(设根为第 1 层)有 8 个叶结点，则完全二叉树的结点个数最多是( C )。 A. 39 B. 52 C. 111 C. 111 D.119 1 【D 】 2 【C 】 3 【B 】 4 【D 】 5 【B 】 6 【A 】 7 【C 】 8 【D 】 9 【D 】 10 【C 】11 【A 】12 【B 】13 【C 】14 【A 】15 【A 】16 【B 】17 【A 】18 【B 】 19 【A 】20 【A 】21 【B 】22 【B 】23 【C 】24 【B 】25 【D 】26 【A 】27 【B 】 28 【C 】29 【C 】30 【C 】 2 二、判断题二、判断题(共 10 分，每小题 1 分) ()() 1数据元素是数据的最小单位。 ()()2数据结构是数据对象与对象中数据元素之间关系的集合。 ()()3顺序表可以利用一维数组表示，因此顺序表与一维数组在结构上是一致的，它们可以通用。 () () 4在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。 ()()5顺序表和一维数组一样，都可以按下标随机（或直接）访问。 ()()6线性表若采用链式存储表示时存储单元的地址可连续可不连续。 ()()7链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要系统中还有足够的 可用空间，就不会产生溢出的问题。 ()()8线性表若采用链式存储表示, 在删除时不需要移动元素。 ()()9在对双向循环链表做删除一个结点操作时，应先将被删除结点的前驱结点和后继结点链接好再 执行删除结点操作。 ()()10在一个循环队列 Q 中，判断队满的条件为 Q.rear % MaxQsize+1 = Q.front。 三、综合应用题三、综合应用题(共 30 分，每小题 10 分) 1.写出下列程序段的输出结果（栈的元素类型 SElemType 为 char） 。 Void main( ) Stack S; Char x, y ; InitStack(S) ; x=c; y=k; Push(S, x) ; Push(S, a) ; Push(S, y) ; Pop(S, x) ; Push(S, t) ; Push(S, x) ; Pop(S, x) ; Push(S, s) ; while(!StackEmpty(S) Pop(S,y);printf(y); ; printf(x); 答：输出为“stack” 。 2二叉树采用二叉链表存储,请回答下面递归程序实现的功能,并在空格处 填上适当的语句。 （两个空，每空 4 分，回答功能 2 分。共 10 分） BiTNode *Copy(BiTree bt) BiTree p; if(bt) p=【 (BiTree )malloc(sizeof(BiTNode) 】 ; p-data=bt-data; p-lchild= Copy(bt-lchild); 【p-rchild=Copy(bt-rchild) 】; return(p); else return(0); 答：复制一棵二叉树复制一棵二叉树。 评分标准：两个空，每空 4 分，回答功能正确 2 分。共 10 分。 3.设有一个由正整数组成的无序单链表，编写完成下列功能的算法： (1)找出最小结点，且打印该数值； (2)若该数值是奇数，则将其与直接后继结点的数值交换； (3)若该数值是偶数，则将其直接后继结点删除。 解： Status sub(LinkList int temp; p=Lnext; q=p; while(p!=NULL) if(pdata next=NILL Cp=NILL Dp-next= head 3若用一个大小为 6 的数组来实现循环队列,且当前 rear 和 front 的值分别为 0 和 3, 当从队列中删除一个元素,再加入两个元素后,rear 和 front 的值分别为多少？ 【 】 A. 2 和 4 B. 4 和 2 C. 5 和 1 D. 1 和 5 4一棵具有 35 个结点的完全二叉树的高度为( )。假定空树的高度为 0。 【 】 A. 5 B. 6 C. 7 D. 8 5树的后根遍历序列等同于该树对应的二叉树的 【 】 A. 先序序列 B. 后序序列 C. 中序序列 6在树的左孩子-右兄弟表示法中，一个结点的右孩子是该结点的( )结点。 【 】 A. 兄弟 B. 父子 C. 祖先 D. 子孙 7下述编码中哪一个不是前缀编码 【 】 A （1，01，000，001） B （0，10，110，111） C （0，1，00，11） D （00，01，10，11） 8.求最短路径的算法有 【 】 A. Prim 和 Kruskal 算法 B. 深度优先遍历算法和广度优先遍历算法 C. 拓扑排序算法 D. Dijkstra 算法和 Floyd 算法 9散列(Hash)查找法的时间复杂度为 【 】 A. O(1) B. O(n) C. O(log n) D. O(n2) 10. 在下列排序算法中不需要对排序码进行比较就能进行排序的是 【 】 A基数排序 B快速排序 C直接插入排序 D堆排序 一、 填空题：(共 20 分，第 1-9 小题每空 1 分，第 10 小题 7 分) 一、 填空题：(共 20 分，第 1-9 小题每空 1 分，第 10 小题 7 分) 1数据结构的逻辑结构包括线性结构和【 】结构两大类。 2抽象数据类型的一个特点是抽象数据类型的用户看不到抽象数据类型的数据存储 及其【 】的实现。 3算法的一个特性是【 】 ，即算法必须执行有限步就结束。 4. 对于一个具有 n 个结点的线性链表，在已知的结点*p 后插入一个新结点的时间 复杂性为【 】 。 5在具有 n 个单元的循环队列中，队满时共有【 】个元素。 6. 在一棵二叉树中，度为零的结点的个数为 N0,度为 2 的结点的个数为 N2,则有 N0=【 】 。 7由三个结点构成的二叉树，共有【 】种不同的结构形态。 8先序序列遍历森林正好等同于按【 】遍历对应的二叉树；后序序列遍历 森林正好等同于【 】遍历对应的二叉树。 9.已知一棵二叉树的中序序列和后序序列如下，求该二叉树的深度和度为 2 结点数、 度为 1 结点数及叶子结点数。 中序序列：D，C，B，G，E，A，H，F，I，J，K 后序序列：D，C，E，G，B，F，H，K，J，I，A 则：深度： 【 】 ，度为 2 结点数： 【 】 ，度为 1 结点数： 【 】 ，叶子结点数： 【 】 。 10给出一组关键字 T=(20，4，34，5，16，33，18，29，2，40，7)，要求从小到 大进行排序，试给出快速排序(选第一个记录为枢轴)第一趟排序结果 【 】 。 二、 综合题(共 40 分，每小题 10 分) 二、 综合题(共 40 分，每小题 10 分) 1. 给定有序表（5，13，19，21，37，56，64， ，75，80，88，92） ，用折半查找法在其中 查找 64，试用图示法表示查找过程。 解： 5 13 19 21 37 56 64 75 80 88 92 2. 已知序列(278, 109, 63, 930, 589, 184, 505, 269, 8, 83)(278, 109, 63, 930, 589, 184, 505, 269, 8, 83),请 给出采用基数排序法对该序列作升序排序时的每一趟收集的结果。 答：采用基数排序的各趟收集结果如下： 第一趟(按个位)： 第二趟(按十位)： 第三趟(按百位)： 3.如图 1 所示，画出它的邻接表(要求表结点中第一个顶点号小于第二个 顶点号)存储结构，并按邻接表的存储结构分别给出它的 DFS 和 BFS 的 顶点访问序列。 学院 专业班级 学号 姓名 密封线 （1、请勿在密封线之上答题；2、请在答题纸上方留下相同密封距离） 第 页 2 图 1 4.请构造哈希表 HT. 已知关键字集合（19, 01, 23, 14, 55, 68, 11, 82, 3619, 01, 23, 14, 55, 68, 11, 82, 36）, 设哈希表 HT 表长为 11，哈希函数 H(key)=key mod 11H(key)=key mod 11, 处理冲突函数 Hi(key)=(H(Key)+dHi(key)=(H(Key)+di i)mod 11)mod 11 (1)采用开放定址法中线性探测再散列处理冲突(提示：d d1 1=1, d=1, d2 2=2, d=2, d3 3=3,=3, ) (2)采用二次探测再散列处理冲突 提示：di=1 2 , -12 , 22 , -22,+k2,(k56, 继续在右子表中查找 5 13 19 21 37 56 64 75 80 88 92 low mid high 64lchild) / 对叶子结点计数 CountLeaf( bt-lchild, i); CountLeaf( bt-rchild,i); 解法二：/采用二叉链表存贮二叉树，n 为全局变量，用于累加二叉树的叶子结点的个数。 /本算法在先序遍历二叉树的过程中，统计叶子结点的个数。第一次被调用时，n=0。 void CountLeaf(BiTree bt) / n 为全局变量，第一次被调用时，n=0 if(bt)if(bt-lchild=null /若 T 所指结点为叶子，则累加 CountLeaf (bt-lchild); CountLeaf (bt-rchild); 评分标准：解法一或解法二任写一个即可。全对得 10 分。思路正确，有个别语句错得 6 分。 写出递归结构，但算法基本不正确得 2 分。其它不得分。 第 页 共两页 1 北 京 工 商 大 学 算法与数据结构 试卷(A) 北 京 工 商 大 学 算法与数据结构 试卷(A) 题 号 题 号 一 二 三 四 总分总分 得 分 得 分 一、选择题(共 20 分，每小题 2 分) 一、选择题(共 20 分，每小题 2 分) 1顺序表是线性表的（ ）存储表示。 【 】 A. 数组 B. 连续 C. 有序 D. 顺序存取 2以下说法正确的是（ ） 。 【 】 A. 数据结构的逻辑结构唯一地决定了该数据结构的存储结构。 B. 数据结构的逻辑结构独立于其存储结构。 C. 数据结构的存储结构独立于该数据结构的逻辑结构。 D. 数据结构仅由其逻辑结构和存储结构决定。 3链表不具有的特点是： 【 】 A插入、删除不需要移动元素 B不必事先估计存储空间 C可随机访问任一元素 D所需空间与线性长度成正比 4为增加内存空间的利用率和减少溢出的可能性, 由两个栈共享一片连续的 内存空间时, 应将两栈的( )分别设在这片内存空间的两端. 【 】 A. 深度 B. 长度 C. 栈顶 D. 栈底 5. 若用一个大小为 6 的数组来实现循环队列,且当前 rear 和 front 的值分别 为 0 和 3,当从队列中删除一个元素,再加入两个元素后,rear 和 front 的 值分别为多少？ 【 】 A. 2 和 4 B. 1 和 5 C. 4 和 2 D. 5 和 1 6已知一棵二叉树的先序遍历结果为 ABCDEF, 中序遍历结果为 CBAEDF, 则 后序遍历的结果为 【 】 ACBEFDA B FEDCBA C CBEDFA D不定 7在下列存储形式中，哪一个不是树的存储形式？ 【 】 A顺序存储表示法 B双亲表示法 C孩子链表表示法 D孩子兄弟表示法 8利用 3,6,8,12 这四个值作为叶子结点的权，生成一棵哈夫曼树，该树的 带权路径长度为 【 】 A58 B55 C38 D. 29 9下列四个序列中，哪一个是堆 【 】 A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15 C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15 10对关键码序列 28，16，32，12，60，2，5，72 快速排序，从小到大 一次划分结果为 【 】 A. (2,5,12,16)28(60,32,72) B. (2,16,12,5)28(60,32,72) C. (5,16,2,12)28(32,60,72) D. (5,16,2,12)28(60,32,72) 二、判断题(共 20 分，每小题 2 分)二、判断题(共 20 分，每小题 2 分) 1 数据结构是数据对象与对象中数据元素之间关系的集合。 【 】 2 在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。 【 】 3 链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要 系统中还有足够的可用空间，就不会产生溢出的问题。 【 】 4 在栈空的情况下不能做退栈运算，否则产生下溢。 【 】 5 在对双向循环链表做删除一个结点操作时，应先将被删除结点的前驱结点和 后继结点链接好再执行删除结点操作。 【 】 6 在一个循环队列 Q 中，判断队满的条件为 Q.rear % MaxQsize+1 = Q.front。 7 若一个叶子结点是某子树的中序遍历序列的最后一个结点，则它必是该子树 的先序遍历中的最后一个结点。 【 】 8. 采用邻接表存储的图的深度优先遍历算法类似于二叉数的按层遍历。 【 】 9. 缩短关键路径上活动的时间一定能够缩短整个工程的时间。 【 】 10在索引表顺序表查找方法中，对索引表可以使用顺序表查找方法， 也可以使用折半查找方法。 【 】 三、综合题(共 40 分，每小题 10 分) 三、综合题(共 40 分，每小题 10 分) 1. 已知有 6 个顶点(顶点编号为 05)的有向带权图 G, 其邻接矩阵 A 为上三角矩阵， 按行为主序(行优先)存储在如下的一维数组中。 3 6 5 5 3 4 7 要求：(1) 写出图 G 的邻接矩阵 A 。 (2) 画出有向带权图 G。 (3) 求图 G 的关键路径，并计算该关键路径的长度。 考试纪律承诺考试纪律承诺 本人自愿 遵守学校考试 纪律，保证以 诚信认真的态 度作答试卷。 如有违纪，愿 接受学校相关 纪律处分。 学院 专业班级 学号 姓名 密封线 （1、请勿在密封线之上答题；2、请在答题纸上方留下相同密封距离） 第 页 共两页 2 2如图 1 所示，画出它的邻接表(要求表结点中第一个顶点号小于第二个 顶点号)存储结构，并按邻接表的存储结构分别给出它的 DFS 和 BFS 的 顶点访问序列。 图 1 3.请构造哈希表 HT. 已知关键字集合（19, 01, 23, 14, 55, 68, 11, 82, 3619, 01, 23, 14, 55, 68, 11, 82, 36）, 设哈希表 HT 表长为 11，哈希函数 H(key)=key mod 11H(key)=key mod 11, 处理冲突函数 Hi(key)=(H(Key)+dHi(key)=(H(Key)+di i)mod 11)mod 11 (1)采用开放定址法中线性探测再散列处理冲突(提示：d d1 1=1, d=1, d2 2=2, d=2, d3 3=3,=3, ) (2)采用二次探测再散列处理冲突 提示：di=1 2 , -12 , 22 , -22,+k2,(k=x ) p=pnext ; if(p=NULL) return 0;/链表中没有小于链表中没有小于 x 的结点的结点 else /此时此时 p 指向第一个小于指向第一个小于 x 的结点的结点 i+ ; q=pnext ; while (q!= NULL) if(qdata!=pdata) i+; /出现新小值出现新小值 p=q ; q=qnext ; return i; 评分标准：全对得 10 分。思路正确，有个别语句错得 6 分。 7 4 3 5 5 6 1 2 3 4 5 6 2 3 1 3 1 2 2 4 1 4 4 3 4 1 5 5 6 5 6 6 3 第 页 共两页 1 北 京 工 商 大 学 算法与数据结构 试卷(B) 北 京 工 商 大 学 算法与数据结构 试卷(B) 题 号 题 号 一 二 三 四 总分 总分 得 分 得 分 一、 单项选择题(共 20 分，每小题 2 分) 一、 单项选择题(共 20 分，每小题 2 分) 1一种抽象数据类型包括数据和( )两个部分。 【 】 A. 数据类型 B. 操作 C. 数据抽象 D. 类型说明 2非空的循环链表 head 的尾结点指针 p 满足： 【 】 Ap =head Bp-next=NILL Cp=NILL Dp-next= head 3若用一个大小为 6 的数组来实现循环队列,且当前 rear 和 front 的值分别为 0 和 3, 当从队列中删除一个元素,再加入两个元素后,rear 和 front 的值分别为多少？ 【 】 A. 2 和 4 B. 4 和 2 C. 5 和 1 D. 1 和 5 4一棵具有 35 个结点的完全二叉树的高度为( )。假定空树的高度为 0。 【 】 A. 5 B. 6 C. 7 D. 8 5树的后根遍历序列等同于该树对应的二叉树的 【 】 A. 先序序列 B. 后序序列 C. 中序序列 6在树的左孩子-右兄弟表示法中，一个结点的右孩子是该结点的( )结点。 【 】 A. 兄弟 B. 父子 C. 祖先 D. 子孙 7下述编码中哪一个不是前缀编码 【 】 A （1，01，000，001） B （0，10，110，111） C （0，1，00，11） D （00，01，10，11） 8.求最短路径的算法有 【 】 A. Prim 和 Kruskal 算法 B. 深度优先遍历算法和广度优先遍历算法 C. 拓扑排序算法 D. Dijkstra 算法和 Floyd 算法 9散列(Hash)查找法的时间复杂度为 【 】 A. O(1) B. O(n) C. O(log n) D. O(n2) 10. 在下列排序算法中不需要对排序码进行比较就能进行排序的是 【 】 A基数排序 B快速排序 C直接插入排序 D堆排序 二、 填空题：(共 20 分，第 1-9 小题每空 1 分，第 10 小题 7 分) 二、 填空题：(共 20 分，第 1-9 小题每空 1 分，第 10 小题 7 分) 1数据结构的逻辑结构包括线性结构和【 】结构两大类。 2抽象数据类型的一个特点是抽象数据类型的用户看不到抽象数据类型的数据存储 及其【 】的实现。 3算法的一个特性是【 】 ，即算法必须执行有限步就结束。 4. 对于一个具有 n 个结点的线性链表，在已知的结点*p 后插入一个新结点的时间 复杂性为【 】 。 5在具有 n 个单元的循环队列中，队满时共有【 】个元素。 6. 在一棵二叉树中，度为零的结点的个数为 N0,度为 2 的结点的个数为 N2,则有 N0=【 】 。 7由三个结点构成的二叉树，共有【 】种不同的结构形态。 8先序序列遍历森林正好等同于按【 】遍历对应的二叉树；后序序列遍历 森林正好等同于【 】遍历对应的二叉树。 9.已知一棵二叉树的中序序列和后序序列如下，求该二叉树的深度和度为 2 结点数、 度为 1 结点数及叶子结点数。 中序序列：D，C，B，G，E，A，H，F，I，J，K 后序序列：D，C，E，G，B，F，H，K，J，I，A 则：深度： 【 】 ，度为 2 结点数： 【 】 ，度为 1 结点数： 【 】 ，叶子结点数： 【 】 。 10给出一组关键字 T=(20，4，34，5，16，33，18，29，2，40，7)，要求从小到 大进行排序，试给出快速排序(选第一个记录为枢轴)第一趟排序结果 【 】 。 三、 综合题(共 40 分，每小题 10 分) 三、 综合题(共 40 分，每小题 10 分) 1. 已知二叉树的中序遍历结果为 DBHEAFICG DBHEAFICG , 先序遍历结果为 ABDEHCFIG ABDEHCFIG ， 请画出该二叉树，并将它转换为森林。 解： 2. 已知序列(278, 109, 63, 930, 589, 184, 505, 269, 8, 83)(278, 109, 63, 930, 589, 184, 505, 269, 8, 83),请 给出采用基数排序法对该序列作升序排序时的每一趟收集的结果。 答：采用基数排序的各趟收集结果如下： 第一趟(按个位)： 第二趟(按十位)： 第三趟(按百位)： 考试纪律承诺考试纪律承诺 本人自愿 遵守学校考试 纪律，保证以 诚信认真的态 度作答试卷。 如有违纪，愿 接受学校相关 纪律处分。 本人签名： 学院 专业班级 学号 姓名 密封线 （1、请勿在密封线之上答题；2、请在答题纸上方留下相同密封距离） 第 页 共两页 2 3.分别回答以下序列是否为堆。如果不是,则把它调整为堆，写出调整后的 堆序列。 (1) (100,86,48,73,35,39,42,57,66,21) (100,86,48,73,35,39,42,57,66,21) (2) (5, 16,20,23,40,38,29,61,35,76) (5, 16,20,23,40,38,29,61,35,76) (3) (100,85,40,75,80,60,65,95,82,10,20) (100,85,40,75,80,60,65,95,82,10,20) 4. 试对下图所示的 AOE 网，解答下列问题。 (1) 这个工程最早可能在什么时间结束。 (2) 求每个事件的最早发生时间 vej和最迟发生时间 vli。 (3) 求每个活动的最早开始时间 e(k )和最迟开始时间 l(k )。 (4) 确定哪些活动是关键活动, 并回答出关键路径。 b a1=1 a4=5 a c e a8=10 a3=3 a6=8 d a7=7 f 四、算法题(共 20 分，每小题 10 分) 四、算法题(共 20 分，每小题 10 分) 1已知一个带头结点的线性链表 L，结点值为整数。编写算法， 统计该线性链表中结点值等于定值 x 的结点数。 已知线性链表的结点类型为： typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList; 解：int count (LinkList L, int x) 2编写递归算法。给定一棵用二叉链表表示的二叉树，其根结点指针为 bt， 求二叉树叶子结点数目的函数 CountLeaf（） 。 已知二叉树的二叉链表存储表示为： typedef struct BiTNode / 结点结构结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针左右孩子指针 BiTNode, *BiTree; 解： 学院 专业班级 08 学号 姓名 密封线 （1、请勿在密封线之上答题；2、请在答题纸上方留下相同密封距离） a2=6 a5=1 1 算法与数据结构计算类 10123 计算类 10123 试试卷 B卷 B 标准答案及评分标准： 2012-5-28 一、 单项选择题(共 20 分，每小题 2 分) 一、 单项选择题(共 20 分，每小题 2 分) 1. B 2. D 3. A 4. B 5. C 评分标准 6. A 7. C 8. D 9. A 10.A 每小题选对得 2 分 二、填空题：(共 20 分，第 1-9 小题每空 1 分，第 10 小题 7 分) 二、填空题：(共 20 分，第 1-9 小题每空 1 分，第 10 小题 7 分) 题号 答案 评分标准 1 非线性 答对得 1 分 2 操作 答对得 1 分 3 有穷性 答对得 1 分 4 O(1) 答对得 1 分 5 n-1 答对得 1 分 6 N2+1 答对得 1 分 7 5 答对得 1 分 8 先序 ， 中序 每空 1 分, 全答对得 2 分 9 4、3、4、4 每空 1 分, 全答对得 4 分 10 7,4,2,5,16,18,20,29,33,40,34 答对得 7 分 三、综合题(共 40 分，每小题 10 分) 三、综合题(共 40 分，每小题 10 分) 1、该二叉树为： A B C D E F G H I 该二叉树对应的森林为： A C G B E F I D H 评分标准：正确画出二叉树五分，正确画出对应的森林五分。 2.答：采用基数排序的各趟收集结果如下： 第一趟(按个位)：930， 63， 83，184，505，278, 8，109，589，269 第二趟(按十位)：505， 8，109，930， 63, 269，278， 83，184, 589 第三趟(按百位)： 8， 63， 83，109，184, 269，278，505，589, 930 第一趟(按个位)：930， 63， 83，184，505，278, 8，109，589，269 第二趟(按十位)：505， 8，109，930， 63, 269，278， 83，184, 589 第三趟(按百位)： 8， 63， 83，109，184, 269，278，505，589, 930 评分标准：正确写出 1 趟得 3 分，写对两趟得 7 分，全对得 10 分。 3.答： (1)、(2)是堆。 (3)不是堆，调整为大根堆如下： (100,95,65,85,80,60,40,75,82,10,20) 评分标准： (1)、(2) 小题各 2 分，(3)小题判断正确得 2 分，调整为大根堆正确得 4 分，共计 10 分。 4 ve vl k e(k) l(k) l(k)-e(k) 关键活动 a 0 0 0 0 1 0 5 0 5 b 1 6 1 6 2 0 4 0 4 c 6 10 6 10 3 0 0 0 a3 0 0 0 a3 d 3 3 3 3 4 1 6 1 6 e 11 11 11 11 5 6 10 6 10 f 21 21 21 21 6 3 3 0 a6 3 3 0 a6 7 3 14 3 14 8 11 11 0 a8 11 11 0 a8 故，此工程最早完成时间为 21, 关键路径为 a d e f 。 评分标准：回答问题正确得 2 分。 填表共 8 分。 （其中正确填出 ve 得 2 分、正确填出 vl 得 2 分，正确填出 e(k)得 1 分、 正确填出 l(k)得 1 分。正确填出 l(k)-e(k)得 1 分、正确填出关键活动得 1 分。 ） 四、算法题(共 20 分，每小题 10 分) 四、算法题(共 20 分，每小题 10 分) 1int count (LinkList L, int x) int i=0; LNode *p; p=Lnext; while (p!= NULL) if (pdata= x) i+ ; p=pnext; /while return i ; 评分标准：全对得 10 分。思路正确，有个别语句错得 6 分。 2 2解法一： void CountLeaf (BiTree bt, int *i) if(bt) if (!bt-lchild) / 对叶子结点计数 CountLeaf( bt-lchild, i); CountLeaf( bt-rchild,i); 解法二：/采用二叉链表存贮二叉树，n 为全局变量，用于累加二叉树的叶子结点的个数。 /本算法在先序遍历二叉树的过程中，统计叶子结点的个数。第一次被调用时，n=0。 void CountLeaf(BiTree bt) / n 为全局变量，第一次被调用时，n=0 if(bt)if(bt-lchild=null /若 T 所指结点为叶子，则累加 CountLeaf (bt-lchild); CountLeaf (bt-rchild); 评分标准：解法一或解法二任写一个即可。全对得 10 分。思路正确，有个别语句错得 6 分。 写出递归结构，但算法基本不正确得 2 分。其它不得分。 第 页 共两页 1 北 京 工 商 大 学 算法与数据结构 试卷(A) 北 京 工 商 大 学 算法与数据结构 试卷(A) 题 号 题 号 一 二 三 四 五 总分 总分 得 分 得 分 一、简答题（共 20 分，每小题 4 分） 一、简答题（共 20 分，每小题 4 分） 1栈和队列的定义及特性是什么? 2. 什么是完全二叉树？ 3BFS 算法的基本思想是什么？ 4. 简述哈希表处理冲突的方法。 5请列出五种排序名称。 二、判断题(共 10 分，每小题 1 分) 二、判断题(共 10 分，每小题 1 分) 1数据元素是数据的最小单位。 【 】 2数据结构是数据对象与对象中数据元素之间关系的集合。 【 】 3在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。 【 】 4链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要 系统中还有足够的可用空间，就不会产生溢出的问题。 【 】 5在单链表中任何两个元素的存储位置之间都有固定的联系，因为可以从 头结点进行查找任何一个元素。 【 】 6在栈空的情况下不能做退栈运算，否则产生下溢。 【 】 7在对双向循环链表做删除一个结点操作时，应先将被删除结点的前驱结点和 后继结点链接好再执行删除结点操作。 【 】 8在一个循环队列 Q 中，判断队满的条件为 Q.rear%MaxQsize +1= Q.front。 【 】 9若一个叶子结点是某子树的中序遍历序列的最后一个结点，则它必是该子树 的先序遍历中的最后一个结点。 【 】 10在索引表顺序表查找方法中，对索引表可以使用顺序表查找方法， 也可以使用折半查找方法。 【 】 三、选择题(共 20 分，每小题 2 分) 三、选择题(共 20 分，每小题 2 分) 1.在下列选项中，哪个不是一个算法一般应该具有的基本特征 【 】 A确定性 B可行性 C输入 D无穷性 2在一个长度为 n 的顺序表的表尾插入一个新元素的时间复杂度为： 【 】 A. O(n) B. O(log2n) C. O(n2) D. O(1) 3设线性链表中结点的结构为（data, next） 。已知指针 p 所指结点不是尾结点， 若在*p 之后插入结点*s，则应执行下列哪一个操作？ 【 】 A.s-next= p; p-next= s; B. p-next= s; s-next= p; C. s-next= p-next; p-next= s; D. s-next= p-next; p= s; 4带表头的双向循环链表空表的表示是什么？ 【 】 A. HeadNULL; B. Head-next = Head-prior= Head C. Head