试卷详情
-
数据结构-4
-
[单项选择]对一棵非空二叉树进行中序遍历,则根结点的左边( )
A. 只有左子树上的所有结点
B. 只有右子树上的所有结点
C. 只有左子树上的部分结点
D. 只有右子树上的部分结点
-
[单项选择]设深度为k的二叉树上只有度为0和度为2的结点,则这类二叉树上所含结点总数量少( )个。
A. k+1
B. 2k
C. 2k-1
D. 2k+1
-
[单项选择]由权值为4,2,8,7的四个叶子构成一棵哈夫曼树之后,此树的带权路径的长度为( )
A. 21
B. 42
C. 40
D. 44
-
[填空题]在索引顺序文件中需建立一张指示逻辑记录和物理记录之间的一一对应关系的______。它通常采用______结构来组织。
-
[填空题]以下为单链表的建表算法,分析算法,请在______处填上正确的语句。
lklist create_1klistl( )
/*通过调用intiate_lklist和insetr_lklist算法实现的建表算法。假定$是结束标志*/
{ ininiate_lklist(head);
i=1;
scanf("%",&x);
while(x!=$)
{______;
______;
scanf("%f",&x);
}
return(head);
}
该建表算法的时间复杂性约等于______,其量级为______。
-
[单项选择]一个长度为10的有序表,按照二分查找法对该表进行查找,在表内各元素等概率的情况下,查找成功所需要的平均比较次数为( )
A. 25/10
B. 27/10
C. 29/10
D. 31/10
-
[简答题]已知一棵具有2个结点的二叉树的前序遍历序列和后序遍历序列是AB和BA,请问:这棵二叉树是惟一的吗如果树是不惟一的,请画出满足此条件的不同的二叉树,并简单分析一下。
-
[简答题]已知有一组长度为9的关键字序列为{22,63,72,54,97,17,37,80,92},现在假设散列表的地址空间为T[0..10],请用除余法构造散列函数,如果存在冲突问题,请用线性探查法解决冲突,并给出相应的散列表。
-
[填空题]若二叉树的一个叶子是某子树的中序遍历序列中的第一个结点,则它必是孩子树的后序遍历序中的______个结点。
-
[填空题]设线性表L=(a1,a2,…,an)(n>2),表中元素按值的递增顺序排列。对一个给定的值k,分别用顺序检索和二分法检索查找与k相等的元素,比较次数分别为s和b,若检索不成功,则s和b的数量关系是______。
-
[填空题]______查找法的平均查找长度与元素个数n无关。
-
[单项选择]索引非顺序文件是指( )
A. 主文件无序,索引表有序
B. 主文件有序,索引表无序
C. 主文件有序,索引表有序
D. 主文件无序,索引表无序
-
[填空题]数组A[1..10,-2..6,2..8]以行优先顺序存储,设第一个元素的首地址是100,每个元素占3个存储长度的存储空间,则元素A[5,0,7]的存储地址为______。
-
[单项选择]下面四种内排序方法中,要求内存容量最大的是( )
A. 插入排序
B. 选择排序
C. 快速排序
D. 归并排序
-
[单项选择]采用分治法进行排序的方法是( )
A. 快速排序
B. 插入排序
C. 堆排序
D. 希尔排序
-
[单项选择]串是一种特殊的线性表,其特殊性体现在( )
A. 可顺序存储
B. 数据元素是一个字符
C. 可链接存储
D. 数据元素可以是多个字符
-
[单项选择]从一个包含2000个结点的散列表A[1..2000]中查找结点的平均比较次数( )从一个包含200个结点的散列表B[1..200]中查找结点的平均比较次数。
A. 大于
B. 小于
C. 等于
D. 不确定
-
[简答题]对于下面的3个广义表,请画出其图形表示式,并说明它们各属于什么类型的广义表。 (1)B(A(x,l(a,b)),y) (2)C(A(x,l(a,b)),B(A(x,l(a,b)),y)) (3)D(a,D(a,D(…)))
-
[填空题]在按照顺序存储方式存储的数组中,元素aij的存储地址应该是数组的______加上排在aij前面的元素所占用的单元数。
-
[简答题]从键盘上输入若干字符(每行长度不等),输入后把它们存储到一磁盘文件中,再从该文件中读出这些数据,将其中小写字母转换成大写字母再进行屏幕输出。
-
[填空题]以下是图的深度优先搜索算法,请在______处填充适当的语句。
Dfs(GraphTp g,int v)
{ ArcNodeTp*P;
printf("%",v);
visited[v]=1;
p=______;
while(p!=NULL)
{if(!______)Dfs(g,p—>adjvex);
p=______;
}
}
-
[填空题]对磁带上的顺序文件进行更新某个记录时,必须______整个文件。而在顺序文件的最后添加新的记录时,则不必______整个文件。
-
[单项选择]设有6个结点的无向图,该图至少应有( )条边才能确保是一个连通图。
A. 5
B. 6
C. 7
D. 8
-
[填空题]文件的记录均存放在数据集中,数据集中的一个结点称为______,它是一个______操作的基本单位。
-
[填空题]在顺序队列中,应该有队头和队尾两个指针来指示,队头指针和队尾指针的初值在队列的初始化时均应该设置为______,当对队列进行插入和删除的操作后,如果头指针和尾指针相等时,队列为______。
-
[单项选择]长度为12的有序表:Apr,Aug,Dec,Feb,Jan,Jul,Jun,Mar,May,Nov,Oct,Sep,按折半查找法对该表进行查找。在表内各元素等概率情况下查找成功所需的平均比较次数为( )
A. 35/12
B. 37/12
C. 39/12
D. 43/12
-
[填空题]根据文字说明,请在以下______处填充适当的语句。
采用静态链表作存储结构,设置一个大小为2n-1的数组,令数组的每个元素由四个域组成:wt是结点的权值;lehild、rchild分别为结点的左、右孩子指针;parent是结点的双亲在数组中的下标。其数组元素类型定义如下:
typedef struet
{ float wt; /*权值*/
int parent,lchild rchild; /*指针域*/
}node;
typedef node hftree[2*n-1];
在这种存储结构上的哈夫曼算法可描述如下:
void huffman(int k,float W[k],hftree T) /*求给定权值W的哈夫曼树T*/
{ int i,j,x,y;
float m,n;
for(i=0;i<2*k-1;i++)
{ T[i].parent=-1;T[i].lchild=-1;T[i].rchild=-1;
if(______)T[i].wt=W[i];
else T[i].wt=0
}
for(i=0;i<k-1;i++)
{ x=0;y=0;m=maxint;n=maxint;
for(j=0;j<k-i,j++)
if(T[j].wt<m)&&(T[j].parent==-1){n=m;y=___;m=___;x=j;}
else if(T[j].wt<n)&&(T[j].parent==-1)){n=T[j].wt;y=j;)
}
T[x].parent=______;T[y].parent=______;
T[k+i].wt=______;
T[k+i].lchild=______;T[k+i].rchild=______;
}
-
[填空题]以下为单链表的插入运算,分析算法,请在______处填上正确的语句。
void insert_lklist(lklist head,datatype x,int i)
/*在表head的第i个位置上插入一个以x为值的新结点*/
{ p=find_lklist(head,i-1);
if(p==NULL)error("不存在第i个位置");
else{s=______;s—>data=x;
s—>next=______;
p—>next=s;
}
}
-
[单项选择]深度为k的二叉树,所含叶子的个数最多为( )
A. 2K
B. K
C. 2K-1
D. 2K-1
-
[单项选择]将含100个结点的完全二叉树从根这一层开始,每层从左到右依次对结点编号,根结点的编号为1。编号为71的结点的双亲的编号为( )
A. 34
B. 35
C. 36
D. 无法确定
-
[单项选择]一棵二叉树满足下列条件:对任一结点,若存在左、右子树,则其值都小于它的左子树上所有结点的值,而大于右子树上所有结点的值。现采用【 】遍历方式就可以得到这棵二叉树所有结点的递增序列。
A. 先根
B. 中根
C. 后根
D. 层次
-
[填空题]在计算机软件系统中,有两种处理字符串长度的方法:一种是采用______,第二种是设置______。
-
[简答题]已知有如下一个关键字序列{96,47,104,32,73,136,15,38,90,180},按照上述插入顺序构造一棵二叉排序树,则请给出二叉排序树的构造过程,说明其深度,并在等概率的条件下求出平均查找长度。