数据结构复习.doc

数据结构复习判断：1、（ F）一个栈的输入序列式12345，则栈的输出序列不可能是123452、（F）顺序存储方式的表，其逻辑次序和物理单元存储次序不是对应的3、（ T）具有12个结点的完全二叉树有5个度为2的结点4、（ F）向一棵二叉搜索树中插入一个新的元素时，若该新元素的值大于根结点的值，则应把它插入到根结点的左子树上5、（ F）有向图的邻接矩阵是对称矩阵6、（ T）L是头指针，带头结点的单链表为空的表达式是：L-next=NULL单选：1、 线性结构中元素之间存在（ A）关系A、一对一 B、一对多 C、多对一 D、多对多2、深度为5的二叉树至多有（ C）个结点A、16 B、32 C、31 D、103、下列关键码一次输入的序列中（ B）是一个堆 A、15，71，30，22，93，52 B、15，30，22，93，52，71C、15，52，22，93，30，71 D、93，30，52，22，15，715、线性表L在（ B）情况下适用于使用链式结构实现A、需经常修改L中的结点值 B、需不断对L进行删除插入C、L中含有大量结点 D、L中结点结构复杂6、对线性表进行二分查找时，要求线性表必须（ B）A、以链接方式存储 B、以顺序方式存储，且结点按关键字有序排列C、以顺序方式存储 D、以链接方式存储，且结点按关键字有序排列7、采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为（ D）A、O（n2） B、O（n2N） C、O（n） D、O（2N）8、用数组A【0，m-1】存放循环队列的元素值，若队头，头尾分别为front和rear，则循环队列中当前元素个数为（ D）A、（rear-front） mod m B、(rear-front+1) mod mC、(rear-front-1=m) mod m D、(rear-front+m) mod m9、从一颗二叉搜索树中搜索一个元素时，若给定值小于根结点的值，则需要向（ A）继续搜索A、左子树 B、右子树10、设串S=“abcd”，在insert(S,2,“mn”)的结果是（ C）A、abcdmn B、mnabcd C、amnbcd D、abmncd11、在线性表的第i个元素之前删除一个元素时，需将第n至第i个元素每个（ A）位置 A、向前移动一个 B、向前移动i个C、向后移动一个 D、向后移动i个12、设有6个结点的无向图，该图至少应有（ A）条边才确保是一个连通图A、5 B、6 C、7 D、813、有一个有序表是1,3,9,12,32,41,45,62,75,77,82,95,100，当二分查找值82为的结点时，（ C）次比较后查找成功A、1 B、2 C、4 D、814、设在栈中，由顶向下以存放元素c,b,a，在第四个元素d入栈前，栈中元素可以出栈，试问d入栈后，不可能的出栈序列是（ C） A、dcba B、cbda C、cadb D、cdba简答题：1. 画出循环队列q=(a1，a2,，an)的示意图，并在图中标明队头，队尾以及各元素入队列和出队列的顺序。2. 画出栈S=（a1，a2，an）的示意图，并在图中标明栈顶，栈底以及各元素的入栈和出栈的方向。3. 设哈希表的长度为13，哈希函数为H(K)=K%13，给定的关键字序列为：87,25,310,8,27,132,68,95,187,123,70,63,47。试画出用开放定址法，线性探测再散列和链地址法解决冲突时所构成的哈希表。87%13=925%13=12310%13=118%13=827%13=1132%13=268%13=395%13=4187%13=5123%13=670%13=5763%13=11047%13=8100123456789101112632713268951871237088747310254.如图所示为一有向图，试给出：（1）每个顶点的入度和出度（2）邻接矩阵5、试写出下面有向图中所有可能的拓扑序列。6二叉树以二叉链表结构存储，在下列中序遍历序列算法中填上正确的语句。 Status in_order (BiTree p)if ( p !=NULL) (1)in_order(p-lchild) ; printf ( p-data); (2)in_order(p-rchild) ; Status post_order (BiTree p)if ( p !=NULL) (1)post_order(p-lchild) ; (2)post_order(p-rchild) ; printf ( p-data); 7.画出以数据集4，6，7，11，18为结点权值所构造的哈夫曼树，并求其带权路径长度WPL。8设图G（V，E），V=1,2,3,4,5,6，E=(,)（1）画出该有向图，并写出图G中顶点的拓扑序列（写出一条即可）。（2）邻接矩阵1-29设某字典组成如下D=016, 087, 154, 170, 275, 426, 503, 509, 512, 612, 653, 677, 703, 765, 897, 908依次顺序表示在内存中，现用二分法的方法查找字典中是否有元素612，问需要进行多少次比较才能得到结论? 每次选择的比较对象是什么元素?解：比较次数为3次，第一次和509比较，第二次和677比较，第三次和612比较。10. 已知一个个数为12的数据元素序列为Dec, Feb, Nov, Oct, June, Sept, Aug, Apr, May, July, Jan, Mar，要求：（1）按各数据元素的顺序构造一棵二叉排序树。（2）设各数据元素的查找概率相等，给出该二叉排序树的平均查找长度。（注：字母的大小是指字母的ASCII码数值大小）（3）按各数据元素的顺序构造一棵平衡二叉树。解：（1）构造的二叉排序树：（2）平均查找长度为：（1*1+2*2+2*3+2*4+3*5+2*6）/12=46/12=23/611一组记录的关键码为一个字母序列（Q，D，E，X，A，P