湖南大学2003年数据结构试题

湖南大学 2003 年招收攻读硕士学位研究生
入学考试命题专用纸
招生专业：计算机应用技术、计算机软件与理论、软件工程硕士
考试科目：数据结构 试题编号：418(450)
注： 答题（包括填空题、选择题）必须答在专用答题纸上，否则无效
一、单项选择题（每小题1分，共15分）
1．两个各有n个元素的有序列表并成一个有序表，其最少的比较次数是
。
A.n B.2n-1 C.2n D.n-1
2.设循环队列中数组的下标范围是0~ n-1，f表示队首元素的前驱位置，r表示队尾元素的位置，则队列中元素个数为 。
A.r-f B.r-f 1 C.(r-f 1)mod n D.(r-f n)mod n
3.一个5行6列的二维数组s采用从最后一行开始，每一行的元素从右至左的方式映射到一维数组a中，s和a的下标均从0开始，则s[3][3]在a中的下标是 。
A．7 B. 8 C. 9 D. 10
4．设只含根结点的二叉树的高度为1，则高度为n的二叉树中所含叶子结点的个数最多为 个。
A．2n B.n C.2n -1 D.2n-1
5．设高度为h的二叉树上只有度为0和度为2的结点，则此二叉树中所包含的结点数至少为个（设只含根结点的二叉树的高度为1）。
A.2h B 2h-1 C.2h 1 D.h 1
6.对一棵二叉检索树进行 得到的结点序列是一个有序序列。
A．前序周游 B. 中序周游 C.后序周游 D. 层次周游
7．一棵前序序列为1，2，3，4的二叉树，其中序序列不可能是 。
A．4,1,2,3 B.4,3,2,1 C.2,4,3,1 D.3,4,2,1
8．下列编码中 不是前缀码。
A．{00，01，10，11} B．{0,1,00,11}
C．{0，10，110，111} D．{10，110，1110，1111}
9．在含n个顶点和e条边的有向图的邻接矩阵中，零元素的个数为 .
A．e B．2e C．n2-e D．n2-2e
10．具有n个顶点和e条边的图的深度优先搜索算法的时间复杂度为 A．O(n) B．O(n3) C．O(n2) D．O(n e)
11.如果具有n个顶点的图是一个环，则它有 棵生成树。
A．n B．n l C．n-l D．2n
12堆排序算法在平均情况下的时间复杂度为 。 A．O(n) B．O(nlogn) C．O(n2) D．O(logn)
13．在待排序数据已基本有序的前提下，下述排序方法中效率最高的是 。 A．直接插入排序 B．直接选择排序 C．快速排序 D．归并排序
14．在理想情况下，散列表中查找元素所需的比较次数为 。
A．n B．O C．n／2 D．1
15．在一棵m阶B树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是 。
A．m B．m 1 C．m—l D．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分）
提示：先对待排序的单链表进行一次扫描，将它划分为若干有序的子链
表，然后反复进行二路归并，直到将所有子链表归并为一个有序链表为止。