北京科技大学2015年数据结构与算法分析试卷+答案.doc

1、 数据结构与算法分析 试卷 第 1 页 共 5 页 北 京 科技大学 2015-2016 学年 第 1 学期 数据结构与算法分析 试卷 院 (系 ) 班级 学号 姓名 试卷卷面成绩 占课程考核成绩 70% 平时成绩占30% 课程考核成绩 题号 一 二 三 四 五 六 七 小计 得分 一、 （ 30 分）选择题 1.设一组权值集合 W=2， 3， 4， 5， 6，则由该权值集合构造的哈夫曼树中带权路径长度之和为 ( )。 (A) 20 (B) 30 (C) 48 (D) 45 2.执行一趟快速排序能够得到的序列是 ( )。 (A) 41， 12， 34， 45， 27 55 72， 63 (B)

2、 45， 34， 12， 41 55 72， 63， 27 (C) 63， 12， 34， 45， 27 55 41， 72 (D) 12， 27， 45， 41 55 34， 63， 72 3. 设指针变量 p 指向单链表中结点 A，若删除单链表中结点 A，则需要修改指针的操作序列为（ ）。 (A) q=p-next； p-data=q-data； p-next=q-next； free(q)； (B) q=p-next； q-data=p-data； p-next=q-next； free(q)； (C) q=p-next； p-next=q-next； free(q)； (D) q=p-

3、next； p-data=q-data； free(q)； 4.时间复杂度不受数据初始状态影响而恒为 O(nlog2n)的是 ( )。 (A) 堆排序 (B) 冒泡排序 (C) 希尔排序 (D) 快速排序 5.设二叉树 的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是 ( )。 得 分 装 订 线 内 不 得 答 题 自 觉 遵 守 考 试 规 则，诚 信 考 试，绝 不 作 弊 数据结构与算法分析 试卷 第 2 页 共 5 页 (A) 空或只有一个结点 (B) 高度等于其结点数 (C) 任一结点无左孩子 (D) 任一结点无右孩子 6.一趟排序结束后不一定能够选出一个元素放在其最终

4、位置上的是 ( )。 (A) 堆排序 (B) 冒泡排序 (C) 快速排序 (D) 希尔排序 7. 设某棵二叉树中只有度数为 0 和度数为 2 的结点且度数为 0 的结点数为 n，则这棵二叉中共有（ ）个结点。 (A) 2n (B) n+l (C) 2n-1 (D) 2n+l 8.顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为 ( )。 (A) O(n) (B) O(n2) (C) O(n1/2) (D) O(1og2n) 9. 下列程序段的时间复杂度为（ ）。 i=0， s=0； while (snext=s;front=s; (B) s-next=rear;rear=s; (C)

5、 rear-next=s;rear=s; (D) s-next=front;front=s; 12.设某无向图中有 n个顶点 e 条边，则建立该图邻接表的时间复杂度为 ( )。 (A) O(n+e) (B) O(n2) (C) O(ne) (D) O(n3) 13.设某哈夫曼树中有 199 个结点，则该哈夫曼树中有 ( )个叶子结点。 (A) 99 (B) 100 (C) 101 (D) 102 14. 设无向图 G 中的边的集合 E=(a， b)， (a， e)， (a， c)， (b， e)， (e， d)， (d，f)， (f， c)，则从顶点 a出发进行深度优先遍历可以得到的一种顶点序

6、列为（ ）。 (A) aedfcb (B) acfebd (C) aebcfd (D) aedfbc 15.设用邻接矩阵 A 表示有向图 G的存储结构，则有向图 G中顶点 i 的入度为 ( )。 (A) 第 i行非 0 元素的个数之和 (B) 第 i 列非 0 元素的个数之和 (C) 第 i行 0元素的个数之和 (D) 第 i列 0 元素的个数之 和 数据结构与算法分析 试卷 第 3 页 共 5 页 二、判断题 (20 分 ) 1.调用一次深度优先遍历可以访问到图中的所有顶点。 ( ) 2. 完全二叉树中的叶子结点只可能在最后两层中出现。（ ） 3.冒泡排序在初始关键字序列为逆序的情况下执行的

7、交换次数最多。 ( ) 4.满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。 ( ) 5.设一棵二叉树的先序序列和后序序列，则能够唯一确定出 该二叉树的形状。 ( ) 6.层次遍历初始堆可以得到一个有序的序列。 ( ) 7.设一棵树 T可以转化成二叉树 BT，则二叉树 BT 中一定没有右子树。 ( ) 8.线性表的顺序存储结构比链式存储结构更好。 ( ) 9.中序遍历二叉排序树可以得到一个有序的序列。 ( ) 10.快速排序是排序算法中平均性能最好的一种排序。 ( ) 三 、 （ 30分）填空题 1.for(i=1， t=1， s=0;i， ， ， ， ， ，则给出该图的一种拓扑排序序列

8、 _。 4.设无向图 G中有 n个顶点，则该无向图中每个顶点的度数最多是 _。 5.设二叉树中度数为 0 的结点数为 50，度数为 1 的结点数为 30，则该二叉树中总共有 _个结点数。 6.设 F和 R 分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为 _。 7.设二叉树中结点的两个指针域分别为 lchild 和 rchild，则判断指针变量 p所指向的结点为叶子结点的条件是 _。 8.简单选择排序和直接插入排序算法的平均时间复杂度为 _。 9.快速排序算法的 空间复杂度平均情况下为 _，最坏的情况下为 _。 得 分 数据结构与算法分析 试卷 第 4 页 共 5 页 10.

9、 设一棵二叉树的中序遍历序列为 BDCA，后序遍历序列为 DBAC，则这棵二叉树的前序序列为 _。 四 、 （ 20 分） 算法设计及问答题 在链式存储结构上建立一棵二叉排序树。 (6 分 ) 设计判断二叉树是否为二叉排序树的算法。 (6 分 ) 在链式存储结构上设计直接插入排序算法 。 (8 分 ) 答案 一、选择题 （ 30分） 1.D 2.A 3.A 4.A 5.DB 6.D 7.C 8.A 9.A 10.D 11.C 12.A 13.B 14.A15.B 二、判断题 1.错 2.对 3.对 4.对 5.错 6.错 7.对 8.错 9.对 10.对 三、填空题 1. O(n) 2. s-

10、next=p-next; p-next=s 3. (1， 3， 2， 4， 5) 4. n-1 5. 129 6. F=R 7. p-lchild=0 struct node *lchild,*rchild;bitree; void bstinsert(bitree * bt-key=key;bt-lchild=bt-rchild=0; else if (bt-keykey) bstinsert(bt-lchild,key); else bstinsert(bt-rchild,key); void createbsttree(bitree * for(i=1;ilchild); if(minn

11、umbt-key)flag=0; minnum=bt-key;inorder(bt-rchild); 3. 在链式存储结构上设计直接插入排序算法 (8 分 ) void straightinsertsort(lklist * int t; if (head=0 | head-next=0) return; else for(q=head,p=head-next;p!=0;p=q-next) for(s=head;s!=q-next;s=s-next) if (s-datap-data) break; if(s=q-next)q=p; elseq-next=p-next; p-next=s-next; s-next=p; t=p-data;p-data=s-data;s-data=t;