8. 9.
设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较________次就可以断定数据元素X是否在查找表中。
不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为____________。
10. 设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双
亲结点编号为____________，右孩子结点的编号为___________。
11. 设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的一趟快速排序
结果为___________________________。
12. 设有向图G中有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图的一种拓扑序
列为____________________。
13. 下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。
struct record{int key; int others;};
int hashsqsearch(struct record hashtable[ ],int k) {
int i,j; j=i=k % p;
while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1);} if (_______________________ ) return(j); else return(-1); }
14. 下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。
typedef struct node{int key; struct node *lchild; struct node *rchild;}bitree; bitree *bstsearch(bitree *t, int k) {
if (t==0 ) return(0);else while (t!=0)
if (t->key==k)_____________; else if (t->key>k) t=t->lchild; else_____________;
}
三、计算题(每题10分，共30分)
1.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。
2．已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探查法处理，试： （1）计算出每一个元素的散列地址并在下图中填写出散列表：
` 0 1 2 3 4 5 6
（2）求出在查找每一个元素概率相等情况下的平均查找长度。
3．已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。 四、算法设计题(每题15分，共30分)
1． 设计在单链表中删除值相同的多余结点的算法。 2． 设计一个求结点x在二叉树中的双亲结点算法。
6
数据结构试卷（四）
一、选择题(每题1分共 20分)
1．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（ ）。
(A) O(n) (A) 2k-1 (A) n (A) O(1) (A) n
(B) O(nlog2n) (B) 2 (B) e (B) O(n) (B) n-1
k
(C) O(1) (C) 2 (C) 2n (C) O(log2n) (C) m
k-1
(D) O(n) (D) 2-1 (D) 2e (D) O(n) (D) m-1
2k
2
2．设一棵二叉树的深度为k，则该二叉树中最多有（ ）个结点。
3．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（ ）。 4．在二叉排序树中插入一个结点的时间复杂度为（ ）。
5．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（ ）条有向边。
6．设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（ ）趟的分配和
回收才能使得初始关键字序列变成有序序列。
(A) 3
(B) 4
(C) 5
(D) 8
7．设用链表作为栈的存储结构则退栈操作（ ）。
(A) 必须判别栈是否为满
(B) 必须判别栈是否为空
(C) 判别栈元素的类型 (D) 对栈不作任何判别 (A) 快速排序 立的是（ ）。
二、填空题(每空1分共 20分)
1． 设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平均时间复杂度
为_________。
2． 设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为
_________________________________________________________（设结点中的两个指针域分别为llink和rlink）。
3． 根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为____________。 4． 深度为k的完全二叉树中最少有____________个结点。
5． 设初始记录关键字序列为(K1，K2，?，Kn)，则用筛选法思想建堆必须从第______个元素开始进行筛选。 6． 设哈夫曼树中共有99个结点，则该树中有_________个叶子结点；若采用二叉链表作为存储结构，则
该树中有_____个空指针域。
7． 设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储________个队列元素；当前
实际存储________________个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。
8． 设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中_______个数据元
素；删除第i个位置上的数据元素需要移动表中_______个元素。
9． 设一组初始记录关键字序列为(20，18，22，16，30，19)，则以20为中轴的一趟快速排序结果为
______________________________。
7
(A) N0=N1+1 (A) log2n+1
(B) N0=Nl+N2 (B) log2n-1
(C) N0=N2+1 (C) log2n
(D) N0=2N1+l (D) log2(n+1)
10.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（ ）。
(B) 冒泡排序
(C) 希尔排序
(D) 堆
8．下列四种排序中（ ）的空间复杂度最大。
9．设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成
10． 设一组初始记录关键字序列为(20，18，22，16，30，19)，则根据这些初始关键字序列建成的初始堆
为________________________。
11． 设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条
件是______________________。
12． 设无向图对应的邻接矩阵为A，则A中第i上非0元素的个数_________第i列上非0元素的个数（填
等于，大于或小于）。
13． 设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该二叉树的序
列为_____________。
14． 设散列函数H(k)=k mod p，解决冲突的方法为链地址法。要求在下列算法划线处填上正确的语句完成
在散列表hashtalbe中查找关键字值等于k的结点，成功时返回指向关键字的指针，不成功时返回标志0。
typedef struct node {int key; struct node *next;} lklist; void createlkhash(lklist *hashtable[ ]) {
int i,k; lklist *s;
for(i=0;i s=(lklist *)malloc(sizeof(lklist)); s->key=a[i]; k=a[i] % p; s->next=hashtable[k];_______________________; } } 三、计算题(每题10分，共30分) 1、画出广义表LS=(( ) , (e) , (a , (b , c , d )))的头尾链表存储结构。 2、下图所示的森林： (1) 求树（a）的先根序列和后根序列； (2) 求森林先序序列和中序序列； （3）将此森林转换为相应的二叉树； ABD(a)CEFIGHJ(b)K 2 3、设散列表的地址范围是[ 0..9 ]，散列函数为H（key）= （key +2）MOD 9,并采用链表处理冲突，请 画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。 四、算法设计题(每题10分，共30分) 1． 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设 计出三个单链表的算法，使每个单链表只包含同类字符。 2. 3. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。 在链式存储结构上建立一棵二叉排序树。 8 数据结构试卷（五） 一、选择题(20分) 1．数据的最小单位是（ ）。 (A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量 2．设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束 后前4条记录关键字为（ ）。 (A) 40，50，20，95 (B) 15，40，60，20 (C) 15，20，40，45 (D) 45，40，15，20 有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ ）。 (A) 15，25，35，50，20，40，80，85，36，70 (B) 15，25，35，50，80，20，85，40，70，36 (C) 15，25，35，50，80，85，20，36，40，70 (D) 15，25，35，50，80，20，36，40，70，85 4．函数substr(“DATASTRUCTURE”，5，9)的返回值为（ ）。 (A) “STRUCTURE” (C) “ASTRUCTUR” 间复杂度为（ ）。 (A) O(log2n) N0=（ ）。 (A) Nl+N2+??+Nm (B) l+N2+2N3+3N4+??+(m-1)Nm (D) 2Nl+3N2+??+(m+1)Nm (C) 7 (D) 1 (C) N2+2N3+3N4+??+(m-1)Nm (A) 25 (B) 10 (B) O(1) (C) O(n) 2 3．设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的 (B) “DATA” (D) “DATASTRUCTURE” 5．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时 (D) O(n) 6．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，??，度数为m的结点数为Nm，则 7．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（ ）次。 8．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可 以得到一种深度优先遍历的顶点序列为（ ）。 (A) abedfc 出元素是（ ）。 (A) n-i (B) n-1-i (C) n+1-i (D) 不能确定 10 设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准而得到一 趟快速排序的结果是（ ）。 二、填空题(共20分) 1. 2. 3. 设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是____________________。 在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。 设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。 (A) 40，42，45，55，80，83 (C) 42，40，45，55，80，85 (B) 42，40，45，80，85，88 (D) 42，40，45，85，55，80 (B) acfebd (C) aebdfc (D) aedfcb 9．设输入序列是1、2、3、??、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输 9 4. 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为__________表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_________表。 5. 6. 7. 8. 9. 设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为___________，中序遍历序列为___________，后序遍历序列为___________。 设一棵完全二叉树有128个结点，则该完全二叉树的深度为________，有__________个叶子结点。 设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的________，第i列中所有非零元素个数之和等于顶点i的__________。 设一组初始记录关键字序列(k1，k2，??，kn)是堆，则对i=1，2，?，n/2而言满足的条件为_______________________________。 下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。 void bubble(int r[n]) { for(i=1;i<=n-1; i++) { for(exchange=0,j=0; j<_____________;j++) if (r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;} if (exchange==0) return； } } 10. 下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。 struct record{int key; int others;}; int bisearch(struct record r[ ], int k) { int low=0,mid,high=n-1; while(low<=high) { ________________________________; if(r[mid].key==k) return(mid+1); else if(____________) high=mid-1;else low=mid+1; } return(0); } 三、应用题(32分) 1. 2. 3. 4. 设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为ABDEC，要求给出该二叉树的的后序遍历序列。 设无向图G（如右图所示），给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。 设一组初始记录关键字序列为(15，17，18，22，35，51，60)，要求计算出成功查找时的平均查找长度。 设散列表的长度为8，散列函数H(k)=k mod 7，初始记录关键字序列为(25，31，8，27，13，68)，要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。 四、算法设计题(28分) 1． 设计判断两个二叉树是否相同的算法。 2． 设计两个有序单链表的合并排序算法。 10