试卷详情
-
数据结构-2
-
[单项选择]设计一个判别表达式中左、右括号是否配对出现的算法,采用( )数据结构最佳。
A. 线性表的顺序存储结构
B. 栈
C. 队列
D. 线性表的链式存储结构
-
[填空题]树的结点数目至少为______,二叉树的结点数目至少为______。
-
[填空题]散列函数的作用是:______。
-
[填空题]对于数组,通常具有的基本操作有______种,它们分别是______。
-
[填空题]在结点数目相同的二叉树中,______的路径长度最短。
-
[填空题]以下算法在指针T所指的二叉排序树上的查找键值等于K的结点。成功时回送指向该结点的指针;否则回送空指针。请分析程序,并在______上填充合适的语句。
bitreptr search_bst(bitreptr T,keytype K)
{ if(T==NULL)return(NULL);
else switch
{ case T—>key==K:______;
case______: return(search_bst(T—>lchild,K));
case______: return(search_bst(T—>rchild,K));
}
}
-
[填空题]内部排序的方法可以分为五类:______、______、______、______、______。
-
[单项选择]设有一顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素出栈的顺序是s2,s3,s4,s5,s6,s1,则栈的容量至少应该是
( )
A. 2
B. 3
C. 5
D. 6
-
[填空题]以下运算实现在链栈上的初始化,请在______处用适当的语句予以填充。
void InitStack(LStackTp*ls){______;)
-
[单项选择]深度为6(根的层次为1)的二叉树至多有( )个结点。
A. 31
B. 32
C. 63
D. 64
-
[单项选择]在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的 ( )
A. 先根遍历
B. 中根遍历
C. 后根遍历
D. 按层次遍历
-
[填空题]以下运算实现在链队上的入队列,请在______处用适当的语句予以填充。
void EnQueue(QueptrTp*lq,DataType x)
{ LqueueTp*P;
p=(LqueueTp*)malloc(sizeof(LqueueTp));
______=x;
p—>next=NULL;
(1q—>rear)—>next=______;
______;
}
-
[单项选择]二维数组M[i,j]的元素是4个字符(每个字符占一个存储单元)组成的串,行下标i的范围从0到4,列下标j的范围从0到5。M按行存储时元素M[3,5]的起始地址与M按列存储时元素( )的起始地址相同。
A. M[2,4]
B. M[3,4]
C. M[3,5]
D. M[4,4]
-
[单项选择]已知一个向量的第一个元素的存储地址是loO,每个元素的长度为2,则第6个元素的地址是 ( )
A. 120
B. 112
C. 110
D. 114
-
[简答题]对于如下一个有序的关键字序列{5,9,12,18,23,31,37,46,59,66,71,78,85),现在要求用二分法进行查找值为18的关键字,则经过几次比较之后能查找成功
-
[填空题]假设在线索二叉树中,结点的标志域的值为0时,表示其指针域是指向孩子的指针,当结点的标志域为1时,表示其指针域是指向前趋或者后继的线索,则一个结点是叶结点的充要条件是______。
-
[简答题]已知有一关键字序列为{505,94,512,61,908,170,897,275,653,463),如果我们采用快速法对此序列进行排序(按照升序排序),请给出每一趟排序的结果。
-
[单项选择]一个栈的入栈序列为a1,a2,a3,a4,a5,则此栈不可能的输出序列是 ( )
A. a5,a4,a3,a2,a1
B. a4,a5,a3,a2,a1
C. a4,a3,a5,a1,a2
D. a1,a2,a3,a4,a5
-
[简答题]若输入12000个不同的整数,其值介于0和19999之间,采用散列表存储这些数,散列函数为h(k)=k/2,请设计实现的算法。
-
[填空题]对快速排序来讲,其最好情况下的时间复杂度是______,其最坏情况下的时间复杂度是______。
-
[单项选择]在单链表中,删除p所指结点的直接后继的操作是 ( )
A. p—>next=p—>next—>next;
B. p=p—>next;p—>next=p—>next—>next;
C. p—>next=p—>next;
D. p=p—>next—>next;
-
[单项选择]在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的 ( )
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 按层次遍历
-
[单项选择]以下有关数据结构的叙述,正确的是 ( )
A. 线性表的线性存储结构优于链式存储结构
B. 二叉树的第i层上有2i-1个结点,深度为K的二叉树上有2k-1个结点
C. 二维数组是其数据元素为线性表的线性表
D. 栈的操作方式是先进先出
-
[单项选择]设rear是指向非空带头结点的循环单链表的尾指针,则删除起始结点的操作可表示为( )
A. s=rear;
B. rear=rear—>next; rear=rear—>next; free(rea; free(;
C. rear=rear—>next—>next;
D. s=rear—>next—>next; free(rea; rear—>next—>next=s—>next; free(;
-
[单项选择]已知一个单链表中有3000个结点,每个结点存放一个整数,( )可用于解决这3000个整数的排序问题且不需要对算法作大的变动。
A. 直接插入排序方法
B. 简单选择排序方法
C. 快速排序方法
D. 堆排序方法
-
[填空题]无向图的邻接矩阵是______,并且主对角线上的元素的值为______。
-
[单项选择]在一棵二叉树中,第k层上最多有( )个结点。
A. 2k
B. 2k-1
C. 2k
D. 2k-1
-
[填空题]从一个顺序存储的循环队列中删除一个元素时,应该______。
-
[填空题]以下为顺序表的插入运算,分析算法,请在______处填上正确的语句。
void insert_sqlist(sqlist L,datatype x,int i)/*将X插人到顺序表L的第i-1个位置*/
{ if(L.1ast==maxsize)error("表满");
if((i<1)||(i>L.last+1))error("非法位置");
for(j=L.last;j≥i;j--)
L.data[i-]=X;
L.last=L.last+1;
}