文档介绍：武汉大学计算机学院
数据结构考试试题
一、单项选择题(每小题2分,共20分)
1. 下列说法中,不正确的是。
2. 若线性表最常用的运算是存取第i个元素及其前趋元素,则采用存储方式节省时间。
3. 在一个具有n个结点的有序单链表中插入一个新结点使得仍然有序,其算法的时间复杂度为。
(log2n) (1)
(n2) (n)
4. 设n个元素进栈序列是p1,p2,p3,…,pn,其输出序列是1,2,3,…,n,若pn=1,则pi(1≤i≤n-1)的值是。
-i+1 -i
5. 判定一个环形队列Q(存放元素位置为0~MaxSize-1)队满的条件是。
== +1==
==(+1)%MaxSize ==(+1)%MaxSize
6. 已知t='abcaabbcabcaabdab',该模式串的next数组值为。
A. -1,0,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1 B. 0,1,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1
C. -1,0,0,0,1,1,2,0,0,1,2,3,4,5,6,7,1 D. -1,0,0,0,1,1,2,3,0,1,2,3,4,5,6,0,1
7. 设二维数组A[6][10],每个数组元素占用4个存储单元,若按行优先顺序存放的数组元素,a[0][0]的存储地址为860,则a[3][5]的存储地址是。
A
8. 广义表((a,b,c,d))的表头是①,表尾是②。
A. a B. ( )
C. (a,b,c,d) D. ((a,b,c,d))
9. 在对n个元素进行冒泡排序的过程中,最好情况下的时间复杂度为。
A. O(1) B. (log2n)
C. O(n2) D. O(n)
10. 有一种排序方法,它每一趟都从未排序序列中挑选出最小元素,并将其放入已排序序列的一端
,该排序方法是。
A. 希尔排序 B. 归并排序
C. 直接插入排序 D. 简单选择排序
二、填空题(每题2分,共10分)
1. 有5个元素,其进栈次序为A、B、C、D、E,在各种可能的出栈次序中,以元素C、D最先出栈(即C第一个且D第二个出栈)的有CDBAE、。
2. 一棵二叉树的先序遍历序列为ABCDEF,中序遍历序列为CBAEDF,则后序遍历序列为。
图1 图G
3. 在二叉排序树中查找,最坏情况下成功查找长度为①;在平衡二叉树中查找,成功情况下平均查找长度为②。
4. 设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,在直接插入排序、快速排序、堆排序和基数排序中最好选用排序法。
5. 对于如图1所示的图G,用普里姆算法从顶点1开始求最小生成树,按次序产生的边是①,用克鲁斯卡尔算法产生的边次序是②