《数据结构试卷(1)1.doc》由会员分享，可在线阅读，更多相关《数据结构试卷(1)1.doc（4页珍藏版）》请在金锄头文库上搜索。
1、专 业 班 级 姓 名 学 号 装 订 线安庆职业技术学院电子信息系2010-2011学年度第一学期期末考试数据结构试卷（B卷）命题教师: 刘震题号一二三四总分统分人得分分值得分阅 卷 人一 选择题(共10小题，每题 2分，共计 20分)1下列时间复杂度中最坏的是_D_。A. O(1) B. O(n) C. O(log2n) D. O(n2)2算法能正确地实现预定功能的特性称为_A_。 A. 正确性 B. 易读性 C. 健壮 D. 高效率在3. 数据元素是数据的基本单位，其内_C_数据项。 A. 只能包括一个 B. 不包含 C. 可以包含多个 D. 必须包含多个4. 在长为n的顺序表中，删除第
2、i个元素(1in+1)需要向前移动（ A ）个元素。A. n-i B. n-i+1 C. n-i-1 D. i5. 一个队的入队顺序是1、2、3、4、5，则此队的出队顺序为（ D ）。A. 5、4、3、2、1 B. 4、5、3、2、1C. 4、3、5、1、2 D. 1、2、3、4、56. 栈是一种特殊的线性表，其特殊性表现在（ B ）。A. 可以顺序存储 B.只能从端点进行插入和删除 C. 可以链式存储 D. 可以在任何位置进行插入和删除7. 一棵二叉树中，第k层上最多有（ D ）个结点。A. 2k B.2k-1 C.2k D.2k-18. 按照二叉树的定义，具有3个结点的二叉树有（ C ）种
3、不同形态。A. 3 B. 4 C. 5 D. 69. n个顶点的有向图中最多有（ B ）条弧。 A. n(n-1)/2 B. n(n-1) C. n(n+1) D. n(n+1)/210.有向图中，所有顶点入度和是所有顶点出度和的（ B ）倍。 A. 0.5 B. 1 C. 2 D. 411. 一棵完全二叉树的顺序存储方式中，若编号n的结点有右孩子，则其左孩子的编号为（ A ）。A. 2n+1 B. 2n-1 C. n D. n/212. 若某线性表中最常用的操作是随机访问元素，则应采用（ D ）存储方式。A.单链表 B.双链表 C.单向循环链表 D.顺序表13. 连通分量是_A_的极大连通子
4、图。A.无向图 B.有向图 C. 树 D.图14. 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是_B_。A.完全图 B.连通图 C.有回路 D.一棵树15. 冒泡排序的方法是_A_的排序方法。A.稳定 B. 不稳定 C. 外部 D.选择16. 排序是根据_B_的大小重新安排各元素的顺序。A.数组 B. 关键字 C. 元素 D. 结点17.对线性表进行折半查找时，要求线性表必须_B_。A.关键值有序的链表 B.关键值有序的顺序表 C.链表但关键值不一定有序 D.顺序表但关键值不一定有序18记录中的各个数据项的类型_C_。 A. 不能相同 B. 必须相同 C.不必相
5、同 D. 不确定19. 设森林T中有三棵树，第一、二、三棵数的结点个数分别为n1、n2、n3，那么将森林转换成二叉树后，其根结点的右子树上有_B_个结点。A.n1-1 B.n2+n3 C.n1+n2+n3 D.n120. 某二叉树的前序遍历结点访问顺序为ABDGCEFH，中序遍历结点访问顺序为DGBAECHF，则其后序遍历结点访问顺序为_D_。A.BDGCEFHA B.GDBECFHA C. BDGAECHF D. GDBEHFCA分值得分阅 卷 人二、判断题（共10小题，每题 1分，共计 10分）（ 对 ） 1、满二叉树一定是完全二叉树。（ 错） 2、二叉树就是度为2的树。（ 对 ） 3、
6、存在这样的二叉树，其后序遍历与中序遍历得到的访问序列相同。（ 错） 4、链式存储的线性表可以实现随机存取。（ 错 ） 5、由空格组成的串叫空串。（ 对） 6、在赋权有向无环图中，可能有多条关键路径。（ 对 ） 7、栈是一种后进先出的线性结构。（ 对 ） 8、选择排序是不稳定的。（ 错 ） 9、在线性结构的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。（ 错 ）10、二叉树按某种顺序线索化后，任一结点均有指向其直接前驱和直接后继的线索。分值得分阅 卷 人三、填空题（共15空，每空 2分，共计 30分）1、算法的基本特征为 有穷性、确定性、有效性、输入和输出；2、在单链表中，若删除指
7、针p所指结点的直接后继，则需要执行下列三条语句：q=p-next；p-next=q-next 或p-next=p-next-next；free（q）；3、在有头结点的单循环链表L中，指针p所指结点是最后一个结点的条件是:p-next= =L。4、栈是一种受限制的线性表，也叫FILO结构，FILO的含义是:先进后出。5、对于队列，只能在队尾插入元素，只能在队头删除元素。6、图的遍历方式通常有深度优先遍历和广度优先遍历两种。7、在具有n个结点的按结点数据有序的线性单链中插入一个新结点并使链表依然有序的操作的时间复杂度是(n)。8、对于顺序栈，在执行进栈操作之前要先判断栈是否栈满,在执行出栈操作之前
8、要先判断栈是否栈空。9、在具有n个单元的循环队列中，队列满时共有n-1个数据在队列中。10、一棵含有11个顶点的正则二叉树（没有度为1的结点的二叉树）的最大深度可以是6,最小深度可以是4。分值得分阅 卷 人四、简答和应用题(共5小题，分值4+9+9+9+9分，共计 40分)1、 算法：int BtreeFN(BKBTree root)int m,n; if(!root) return 0;elsem=BtreeFN(root-lchild); n=BtreeFN(root-rchild); return (mn?m:n)+1; 该递归算法的功能是求二叉树的深度。2、某二叉树后序遍历的结果是AB
9、CDEFG，中序遍历的结果是ADBCGFE.（1）画出此二叉树；（2）写出其先序遍历的结果。3、已知序列28，10，20，7，35。（1）以该序列为权构造一棵有5个叶子结点的Huffman树。（2）求上边构造的哈夫曼树的带权路径长度WPL.4、已知如图所示的赋权无向图：求其最小生成树（要求画出生成的过程）。5、写出有序查找表的折半查找的算法。 数据结构B卷参考答案一、 单项选择题（2分10=20分）题号12345678910答案DACADBDCBB题号11121314151617181920答案ADABABBCBD二、 判断题（1分10=10分）题号12345678910答案三、填空题（2分1
10、5=30分）1有穷性，有效性2 p-next=q-next 或 p-next=p-next-next3p-next= =L 4先进后出（First In Last Out）5 队尾，队头6 深度优先，广度优先7. (n)8. 栈满，栈空9. n-110. 6 , 4四、应用题（40分）1（4分）二叉树的深度。2（9分）(1) .5分(2)GDACBFE .4分 3（9分）(1) 6分(2)WPL=(20+28+35)*2+（7+10）*3=217 3分4（9分）(对一个图1.5分,五个图全对给9分)（9分） int BinarySearch(SSTable SST,KeyDT key, int (*compare)(KeyDT,KeyDT) int low,high,mid; 2分 low=0; high=SST.len-1; 3分while(low=high)mid=(low+high)/2;if(!(*compare)(key,SST.listmid.key) break;else if( (*compare)(key,SST.listmid.key)high)mid=-1;return mid; 9分第 1 页 共 4 页
