奥赛数据结构题汇总

《奥赛数据结构题汇总》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构练习一一、单项选择题1．若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用存储方式最节省运算时间。(1)单链表(2)双链表(3)单循环链表(4)带头结点的双循环链表2．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是(1)A，B，C，D(2)D，C，B，A(3)A，C，D，B(4)D，A，B，C3．串是。(1)不少于一个字母的序列(2)任意个字母的序列(3)不少于一个字符的序列(4)有限个字符的序列4．链表不具有的特点是。(1)可随机访问任一元素(2)插入删除不需要移动元素(

2、3)不必事先估计存储空间(4)所需空间与线性表长度成正比5．在有n个叶子结点的哈夫曼树中，其结点总数为。(1)不确定(2)2n(3)2n+1(4)2n-16．任何一个无向连通图的最小生成树(1)只有一棵(2)有一棵或多棵(3)一定有多棵(4)可能不存在7．将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为。(1)98(2)99(3)50(4)488.下列序列中，是执行第一趟快速排序后得到的序列(排序的关键字类型是字符串)。(1)[da，ax，eb，de，

3、bb]ff[ha，gc](2)[cd，eb，ax，da]ff[ha，gc，bb](3)[gc，ax，eb，cd，bb]ff[da，ha](4)[ax，bb，cd，da]ff[eb，gc，ha]9．用n个键值构造一棵二叉排序树，最低高度为。(1)n/2(2)n(3)[log2n](4)[log2n+1]10．二分查找法要求查找表中各元素的键值必须是排列。(1)递增或递减(2)递增(3)递减(4)无序11.对于键值序列(12，13，11，18，60，15，7，18，25，100)，用筛选法建堆，必须从键值为的结点开始。(1)100(2)12

4、(3)60(4)15三、填空题1．在带有头结点的单链表L中，第一个元素结点的指针是。2．在双循环链表中，在指针P所指结点前插入指针S所指的结点，需执行下列语句：S↑.next：=P；S↑．prior：=P↑．prior；P↑．prior：=S；：=S；A／＼BC／＼＼DEF／H3.[1..maxsize]为一个顺序存储的栈，变量top指示栈顶位置，栈为空的条件是，栈为满的条件是。4．具有100个结点的完全二叉树的深度为。5．有向图G用邻接矩阵A[1．．n，1..n]存储，其第i行的所有元素之和等于顶点i的。6．在顺序文件中，要存取第i个

5、记录，必须先存取。217．对于下面的二叉树，按中序遍历所得到的结点序列为。8．分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态为递增序列的表按递增顺序排序，最省时间的是算法，最费时间的是算法。9.对下图所示的网，执行prim算法可得到最小生成树，试在下表的空白处填上括当的内容，以说明该算法的执行过程。顶点134UV（U，V）代价（2,1）∞（2,3）4（2,4）2{2}{1,3,4}（U，V）代价（2,3）4{2,4}{1,3}（U，V）代价(3,1)1{2,3,4}{1}（U，V）代价{2,3,4,1}10.设散列函数为H（

6、key），用拉链（链地址）法解决冲突，H的值域为0，…，n-1，构造的散列表类型如下：TYPElink=↑node；Node=RECORDkey：keytype；next：link；…END；Openhash=array[0．．n-1]oflink；请在下列算法划线处填上适当内容，以完成在散列表HP中查找键值等于K的结点，若查找成功，返回该结点的指针，否则返回空指针。Functionresearch(K：keytype；HP：openhash)：link；BEGINI：=H(K)；SUC：=false；；while(P<>NIL)and

7、(notsuc)doifP↑.key<>Kthenelsesuc：=true；return(P)END四、应用题1．已知二叉树的后序和中序序列如下，构造出该二叉树。后序序列:ABCDEFG中序序列：ACBGEDF2．有一组关键码序列(38，19，65，13，97，49，41，95，1，73)，采用冒泡排序方法由小到大进行排序，请写出每趟的结果。213．设图G=(V，E)，V={1，2，3，4，5，6}，E={<1，2>，<1，3>，<2，5>，<3，6>，<6，5>，<5，4>，<6，4>}。请写出图G中顶点的所有拓扑序列。4．设散列函

8、数为H(K)=Kmod7，闭散列表的地址空间为0，…，6，开始时散列表为空，用线性探测法解决冲突，请画出依次插入键值23，14，9，6，30，12，18后的散列表。5．对下面两棵二叉树，分别画出它们的顺序存