《2013秋学期数据结构-期未复习（成人2012）-参考答案.doc》由会员分享，可在线阅读，更多相关《2013秋学期数据结构-期未复习（成人2012）-参考答案.doc（8页珍藏版）》请在金锄头文库上搜索。
1、2013年秋学期数据结构期未考试-复习题（2012级）-参考答案一判断题。1. 具有相同逻辑结构的数据可以采用不同的存储结构。 ( )2. 算法分析的前提是算法的时空效率高。 ( )3. 程序设计框图就是一种图形化的算法。( )4. 线性表的顺序存储结构要比链式存储结构节省存储空间。( )5. 任何一个链表都可以根据需要设置一个头结点。( )6. 在长度为n的顺序表的第i个位置插入一个数据元素,i的合法值为1=iprior=q-prior; p-next=q;q-prior=s;_。(空白处为一条赋值语句) (s-prior-next=s; )8. 栈和队列的逻辑结构都是_。（操作受限的线性表
2、）9. 实现二叉树的按层次遍历算法时需要用到_结构。（队列）10. 实现二叉树的中序递归遍历算法的非递化时需要用到_结构。（栈）11. 已知一棵哈夫曼树含有n0个叶子结点，则该树中共有_个非叶子结点。(n0-1)12. 已知一棵哈夫曼树含有n0个叶子结点，则该树中共有_个结点。(2n0-1)13. 采用逐点插入法建立序列(34,17,9,26,56,43,79,51,15,31)的二叉排序树后，查找数据元素51共进行_次元素间的比较。（4）14. n个顶点的连通无向图，其边的条数至少为_。（n-1）15. n个顶点的连通有向图，其有向边的条数至少为_。（n）16. 第一个顶点和最后一个顶点相同
3、的路径称为回路或者环，除第一个顶点和最后一个顶点外，其余顶点都不重复的回路，称为_。（简单回路）17. 对线性表采用折半查找方法，该线性表必须采用_存储结构，并且_。（顺序、元素按关键字排列有序）18. 在按值有序的线性表(5,8,11,12,15,20,32,41,57)中采用折半查找法查找20需要进行_次元素间的比较。（3）19. 若每个记录的查找概率相等，则在具有n个记录的顺序文件中采用顺序查找法的平均查找长度ASL=_(n+1)/2_。20. 索引文件包括_索引表_和_主表（基本文件）_两个部分。21. 具有144项的表分成_块最好，若每块的最佳长度为8，则平均查找长度为_或_。（12
4、、13/8（折半）22. 散列函数建立了_之间的对应关系。_(记录的关键字与存储地址)23. 一个好的散列函数是指_。(使得到的哈希地址尽可能均匀分布在事先已知的空间范围，并函数尽可能简单)24. 处理冲突的方法通常有_、_、_。(开放定址法_、_再哈希法_和_链地址法_)25. 当参加排序的数据量较大,元素的分布又比较随机,并且只需要选出最大或最小的部分元素时，宜选择_排序。（堆）三选择题( 1. 数据的不可分割的最小数据单位是_。 A(A)数据项 (B)数据记录(C)数据元素(D)数据变量2. 抽象数据类型（ADT）的三个组成部分分别为_。B(A)数据元素、逻辑结构和存储结构(B)数据对象
5、、数据关系和基本操作(C)数据项、数据元素和数据类型(D)数据元素、数据结构和数据类型3. 若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为_。D(A)无头结点的双向链表(B)带头指针的循环链表(C)无头结点的单链表(D)带尾指针的循环链表4. 若长度为n的非空线性表采用顺序存储结构,删除表的第i个数据元素,i的合法值应该是_。C(A)i0(B)i=n(C)1=i=n(D)1=in+15. 若长度为n的线性表采用顺序存储结构,在表的第i个位置插入一个数据元素,需要移动表中_个元素。D(A)i (B)n+i (C)n-i-1 (D)n-i+16. 链表所占用的存储空间
6、一定是_。D(A)无序的 (B)连续的(C)不连续的(D)部分连续7. 关于栈和队列的说法中正确的是_。A(A)栈和队列都是线性结构 (B)栈是线性结构，队列不是线性结构(C)栈不是线性结构，队列是线性结构 (D)栈和队列都不是线性结构8. 假设以数组AM存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为_。A(A)(rear-length+M-1)M(B) (rear-length)M(C)(rear-length+M)M(D) (rear-length+M+1)M 9. 一个栈的输入序列为1 2 3 4 5，则下列序列中不
7、可能是栈的输出序列的是_。C(A) 2 3 4 1 5(B) 3 2 1 5 4(C) 3 4 5 1 2(D) 1 2 3 4 510. 若一棵度为7的树有8个度为1的结点，有7个度为2的结点，有6个度为3的结点，有5个度为4的结点，有4个度为5的结点，有3个度为6的结点，有2个度为7的结点，该树一共有_个叶结点。D(A) 35(B) 28(C) 77(D) 7811. 已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为_。C(A)6(B)7(C)8(D)912. 设某棵二叉树中有1000个结点，则该二叉树的最小高度是_。D(A)8(B)9(C)10(D)1113. 任何一棵非空
8、二叉树中的叶结点在前序遍历、中序遍历与后序遍历中的相对位置_。A(A)不会发生改变(B)都会发生改变(C)有可能会发生改变(D)部分会发生改变14. 分块索引是指在文件的索引表中_。D(A)为每个字段设一个索引项(B)为每个记录设一个索引项(C)为每组字段设一个索引项(D)为每组记录设一个索引项15. 按排序过程中依据的原则分类，快速排序属于_。B(A)插入类的排序方法(B)交换类的排序方法(C)选择类的排序方法(D)归并类的排序方法16. 在二叉排序树中进行查找的效率有关的是_。A(A)二叉排序树的深度(B)二叉排序树的结点的个数(C)被查找结点的度(D)二叉排序树的存储结构17. 对n个记
9、录的文件进行排序，下列排序方法中所需要的辅助存储空间最小的为_。B(A)快速排序(B)堆排序(C)希尔排序(D)归并排序18. 一趟排序结束后不一定能够选出一个元素放在其最终位置上的是_。B(A)冒泡排序(B)希尔排序(C)快速排序(D)堆排序19. 下列查找方法中，不属于动态的查找方法是_。A(A)散列法(B)平衡树法(C)二叉排序树法 (D)斐波那契查找法20. 若有16个元素的有序表存放在一维数组A17中，第一个元素放A1中，现进行二分查找，则查找A11的比较序列的下标依次为_。D(A) 9，13，11(B) 9，12，11(C) 9，13，10，11(D) 8，12，10，11四简答题
10、1. 什么是数据？什么是结构？“数据结构”课程主要研究什么内容？答：一切可以用计算机存储和表示的对象；包括数字、声音、图像等 结构：也叫关系，有集合，线性表，树和图 研究内容：数据的逻辑结构，物理结构及操作实现2. 依次读入数据元素a,b,c,d,e,f,g，进栈时每进一个元素，下一个操作可以是进栈或出栈，如此进行则至栈空时出栈的元素能构成的序列是以下的哪个序列，如能请写出操作过程，如不能则请说明原因。b,d,f,e,c,g,a，e,f,d,g,b,c,a 答：前者可以。后者不可以。3. 已知某二叉树的前序序列为ABDEGCFHI，中序序列为DBGEACHFI，请画出该二叉树，及中序线索树。答
11、：4. 假设某通信电文使用的字符集为a，b，c，d，e，f，g，h，各字符在电文中出现的频度分别为：0.07，0.26，0.02，0.29，0.13，0.09，0.03，0.11，试（1）构造哈夫曼树(要求树中左孩子结点的权值不大于右孩子结点的权值)；(2)为这8个字符设计哈夫曼编码。答：(1) (2) a：0101；b：10；c：01000；d：11；e：011；f：000；g：01001；h：0015. .折半查找过程可以利用一棵判定树来描述。请画出n=13时的判定树。6. 对关键字表26，65，78，52，41，13，49，59进行升序排序，分别采用起泡排序和快速排序、简单选择排序和堆排序算法，写出每一趟结束时的结果，并指出相应排序方向的稳定性。答：起泡排序：初始：26，65，78，52，41，13，49，59一趟
