数据结构导论2009年1月真题及答案解析（02142）
-
下列算法的功能是求出指定结点在给定的二叉排序树中所在的层次。请完善该算法。
Void level(BSTree root，p)
{ int level=0;
if( !root )
(1)_________;
else {
level++;
while( root->key!=p->key ) {
if( root->key
key ) (2)_________ ;
else
(3)_________ ;
level++;
}
(4)_________;
}
}
-
完善下列折半插入排序算法。
Void binasort( struct node r[MAXSIZE], int n )
{ for( i=2; i<=n; i++ ) {
r[0]=r[i]; low=1; high=i-1;
while( low<=high ) {
mid=（1）_________;
if( r[0].key
high="(2)_________;
else low=(3)_________;
}
for( j=i-1; j>=low; j-- )
(4)_________;
r[low]=r[0];
}
}
-
用快速排序法对数据序列(49，38，65，97，16，53，134，27，39)进行排序，写出其第一趟排序的全过程。
-
已知某图的邻接表存储结构如题31图所示：
题31图
(1)画出该图。
(2)根据该邻接表从顶点A出发，分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。
-
假定采用H(k)=k mod 7计算散列地址，引用线性探测的开放定址法解决冲突，试在0~6的散列地址空间中，对关键字序列(38，25，74，63，52，48)构造散列表，并求出等概率情况下查找成功的平均查找长度。
-
冒泡排序最好的时间复杂度为_________，平均时间复杂度为_________，是一种稳定的排序算法。
-
已知一棵二叉树的前序序列是ABCDEFG，中序序列是CBDAEGF。请构造出该二叉树，并给出该二叉树的后序序列。
-
将题30图所示的由三棵树组成的森林转化为一棵二叉树。
题30图
-
在插入排序、冒泡排序、快速排序、归并排序等排序算法中，占用辅助空间最多的是 _________。
-
假定对线性表R[0…59]进行分块检索，共分为10块，每块长度等于6。若检索索引表和块均用顺序检索的方法，则检索每一个元素的平均检索长度为_________。
-
文件在外存储器上的组织结构主要有三种：顺序文件、散列文件和索引文件，其中 _________特别适应磁带存储器，也适应磁盘存储器。
-
设有一稠密图G，则G采用 _________存储结构较省空间。设有一稀疏图G，则G采用 _________存储结构较省空间。
-
在一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较_________个元素结点。
-
在循环队列中，存储空间为0~n-1。设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front，队满标志为 _________。
-
深度为k的二叉树至多有 _________个结点，最少有 _________个结点。
-
在栈结构中，允许插入的一端称为 _________;在队列结构中，允许插入的一端称为 _________。
-
在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向 _________和 _________。
-
在有n个元素的链队列中，入队和出队操作的时间复杂度分别为_________和_________。
-
在数据结构中，数据的存储结构有顺序存储方式、链式存储方式、_________和散列存储方式等四种。
-
作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为_________。
-
采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是( )
- A.插入和快速
- B.冒泡和快速
- C.选择和插入
- D.选择和冒泡
-
已知8个元素(34，76，45，18，26，54，92，65)，按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为( )
- A.4
- B.5
- C.6
- D.7
-
二分查找算法的时间复杂度是( )
- A.O(n2)
- B.O(nlog2n)
- C.O(n)
- D.O(log2n)
-
设图的邻接矩阵为
，则该图为( )- A.有向图
- B.无向图
- C.强连通图
- D.完全图
-
有m个叶子结点的哈夫曼树，其结点总数是( )
- A.2m-1
- B.2m
- C.2m+1
- D.2(m+1)
-
有n个结点的无向图的边数最多为( )
- A.n+1
- B.
- C.n(n+1)
- D.2n(n+1)
-
具有n个结点的二叉树，拥有指向孩子结点的分支数目是( )
- A.n-1
- B.n
- C.n+1
- D.2n
-
对一棵有100个结点的完全二叉树按层序编号，则编号为49的结点，它的左孩子的编号为( )
- A.99
- B.98
- C.97
- D.50
-
向一个栈顶指针为hs的链栈中插入一个*s结点时，应执行的操作为( )
- A.hs->next=s;
- B.s->next=hs; hs=s;
- C.s->next=hs->next; hs->next=s;
- D.s->next=hs; hs=hs->next;
-
设循环队列的元素存放在一维数组Q[0‥30]中，队列非空时，front指示队头元素的前一个位置，rear指示队尾元素。如果队列中元素的个数为11，front的值为25，则rear应指向的元素是( )
- A.Q[4]
- B.Q[5]
- C.Q[14]
- D.Q[15]
-
定义二维数组A[1‥8，0‥10]，起始地址为LOC，每个元素占2L个存储单元，在以行序为主序的存储方式下，某数据元素的地址为LOC+50L，则在以列序为主序的存储方式下，该元素的存储地址为( )
- A.LOC+28L
- B.LOC+36L
- C.LOC+50L
- D.LOC+52L
-
若线性表最常用的操作是存取第i个元素及其前趋的值，那么最节省操作时间的存储方式是( )
- A.单链表
- B.双链表
- C.单循环链表
- D.顺序表
-
设单链表中指针p指向结点A，要删除A之后的结点(若存在)，则修改指针的操作为( )
- A.p->next=p->next->next
- B.p=p->next
- C.p=p->next->next
- D.p->next=p
-
数据的不可分割的最小标识单位是( )
- A.数据项
- B.数据记录
- C.数据元素
- D.数据变量
-
上列程序的时间复杂度为( )
- A.O(m+n×t)
- B.O(m+n+t)
- C.O(m×n×t)
- D.O(m×t+n)
，则该图为( )
