湖南大学2003年数据结构题

湖南大学2003年数据结构试题注：答题（包括填空题、选择题）必须答在专用答题纸上，否则无效一、单项选择题（每小题1分，共15分）1．两个各有n个元素的有序列表并成一个有序表，其最少的比较次数是。A.nB.2n-1C.2nD.n-12.设循环队列中数组的下标范围是0~n-1，f表示队首元素的前驱位置，r表示队尾元素的位置，则队列中元素个数为。A.r-fB.r-f1C.(r-f1)modnD.(r-fn)modn3.一个5行6列的二维数组s采用从最后一行开始，每一行的元素从右至左的方式映射到一维数组a中，s和a的下标均从0开始，则s[3][3]在a中的下标是。A．7B.8C.9D.104．设只含根结点的二叉树的高度为1，则高度为n的二叉树中所含叶子结点的个数最多为个。A．2nB.nC.2n-1D.2n-15．设高度为h的二叉树上只有度为0和度为2的结点，则此二叉树中所包含的结点数至少为个（设只含根结点的二叉树的高度为1）。A.2hB2h-1C.2h1D.h16.对一棵二叉检索树进行得到的结点序列是一个有序序列。A．前序周游B.中序周游C.后序周游D.层次周游7．一棵前序序列为1，2，3，4的二叉树，其中序序列不可能是。A．4,1,2,3B.4,3,2,1C.2,4,3,1D.3,4,2,18．下列编码中不是前缀码。A．{00，01，10，11}B．{0,1,00,11}C．{0，10，110，111}D．{10，110，1110，1111}9．在含n个顶点和e条边的有向图的邻接矩阵中，零元素的个数为.A．eB．2eC．n2-eD．n2-2e10．具有n个顶点和e条边的图的深度优先搜索算法的时间复杂度为A．O(n)B．O(n3)C．O(n2)D．O(ne)11.如果具有n个顶点的图是一个环，则它有棵生成树。A．nB．nlC．n-lD．2n12堆排序算法在平均情况下的时间复杂度为。A．O(n)B．O(nlogn)C．O(n2)D．O(logn)13．在待排序数据已基本有序的前提下，下述排序方法中效率最高的是。A．直接插入排序B．直接选择排序C．快速排序D．归并排序14．在理想情况下，散列表中查找元素所需的比较次数为。A．nB．OC．n／2D．115．在一棵m阶B树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是。A．mB．m1C．m—lD．m／2二、判断题(判断下列各题是否正确，若正确，在括号内打“√”，否则打“╳”；每小题1分，共10分)1．已知指针curr指向链表中的某结点，执行语句curr=curr-next；不会删除该链表中的结点。()2．若二叉树的叶结点数为1，则其高度等于结点数(仅含根结点的二叉树高度为1)。（）3．按中序周游二叉树时，某个结点的直接后继是它的右子树中第一个被访问的结点。()4．完全二叉树的某结点若无左孩子，则它必是叶结点。()5．向二叉检索树中插入一个新结点，需要比较的次数不可能大于此二叉树的高度。()6．对一个堆按层次周游，一定能得到一个有序序列。()7．一棵树中的叶子结点数一定等于其对应的二叉树中的叶子结点数。()8．将一棵树转换为二叉树表示后，该二叉树的根结点没有右子树。()9．任何有向图的结点都可以排成拓扑序列，而且拓扑序列不唯一。()10．快速排序在最差情况下的时间复杂度是0(n2)，此时它的性能并不比冒泡排序更好。()三、填空题（每空2分，共20分）1．具有100个结点的完全二叉树的叶子结点树为。2．由权值分别为3，9，6，2，8的叶子结点生成一棵哈夫曼树，它的外部带权路径长度为＿＿＿。3．对含n个结点的完全二叉树按自上而下，从左到右的顺序结点编号（从0开始），则编号最小的叶子结点的编号是。4．n个顶点的连通无向图的邻接矩阵至少有个非零元素。5．在有序表A[1..20]中，若需查找的元素位于A[12]，则采用折半查找算法所比较的元素的下标依次为6．要将序列{60，10，8，40，90，70，100}建成堆，只需把8与相交换。7．从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为。8．已知广义表L=（（a，b，c），（d，e，f）），则运算head(tail(head(tail(L))))的结果是.9.模式串P=“abaa”的next函数值序列为。10．一个两层100阶的B树，最多可以有条记录四、解析题（共55分）1．对二叉树中结点进行按层次顺序（每一层从左至右）的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树的层次序列。现已知一棵二叉树的层次序列为ABCDEFGHIJ，中序序列为DBGEHJACIF，请画出该二叉树。（7分）2．证明若二叉排序树中的一个结点存在两个孩子，则（8分）①它的中序后继结点没有左孩子。②它的中序前趋结点没有右孩子。3．对下面的带权无向图采用prim算法从顶点①开始构造最小生成树。（写出假如生成树顶点集合S和选择边Edge的顺序）（10分）4．已知一组关键字序列为：（17，31，13，11，20，35，25，8，4，11，24，40，27），按照依次插入结点的方法生成一棵平衡二叉排序树。（10分）5．设散列函数为H（k）=k％13，散列表的地址空间为0到12，用线性探查法解觉冲突，将关键字（18，22，78，205，40，16，35，104，61）依次存入该散列表中，试构造散列表，并计算在等概率下的搜索成功的平均搜索长度ASL（搜索成功的平均搜索长度ASLsucc是指搜索到表中己有表项的平均探查次数。它是找到表中各个己有表项的探查次数的平均值）（10分）6．给出一组关键字T=（20，3，18，40，9，30，5，11，32，7，28），设内存工作区可容纳4个记录，写出用置换-选择排序得到的全部初始归并段。若某文件经内排序后得到50个初始归并段（初始顺串），若使用多路归并排序算法算法，并要求三趟归并完成排序，归并路数最少为多少？（10分）五、算法设计题（共50分）1．请写一算法，在顺序表中查找指定的数据，查找成功则将该记录放到顺序表的最前面，而把其他记录后退到有个位置。（10分）2．有一个由自然数构成的序列采用单链表存储，试编写算法判断该序列是否是fibonacci序列（fibonacci序列是1，1，2，3，5，8，13，21，34，…）。（10分）3．定义二叉树中两个结点之间的最小距离为：这两个结点的最近公共祖先结点分别到这两个结点的路径长度之和。请设计一个算法，找出给定二叉树中任意两个结点之间的最小距离。（15分）4．设有n个待排序元素存放在一个不带表头结点的单链表中，每个链表结点只存放一个元素，头指针为head。试设计一个算法，对其进行自然归并排序（按照下面的提示进行）。要求不移动个结点中的元素，只修改结点中的指针。排序完成后，head仍指示结果链表的第一个结点。（15分）提示：先对待排序的单链表进行一次扫描，将它划分为若干有序的子链表，然后反复进行二路归并，直到将所有子链表归并为一个有序链表为止。