《数据结构》模拟题（一）
一、单选题 （每空2分，共10分）
1、某程序的时间复杂度为（3n+nlog2n+n2+8）, 其数量级表示为（ ）。
A．O（n） B．O（nlog2n）
C．O（n二叉树定义2） D．O（log2n）
2、队列的插入操作是在（ ）进行。
A．队首 B．队尾
C．队前 D．对后
3、二叉树上叶结点数等于（ ）。
A．分支结点数加1 B．单分支结点数加1
C．双分支结点数加1 D．双分支结点数 减1
4、每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（ ）排序
A．插入 B．交换
C．选择 D．归并
5、在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。
A．2 B．1
C．3 D．4
二、填空题（每空1分，共20分）
1、一个算法应具备的5个特性为 、 、 、
、 。
2、在采用独立结点构成的双向链表中，设p和q 分别是具有Dnode * 类型的指针变量。若双向链表中p结点之后插入一个q结点，其操作步骤为：
；
；
；
；
3、表示图的三种存储结构为 、 和 。
4、假定一棵二叉树广义表表示为a(b(c,d)，e(,f))，则对它进行的先序遍历结果为____________，中序遍历结果为____________，后序遍历结果为____________，按层遍历结果为____________。
5、当从一个小根堆中删除一个元素时，需要把________元素填补到________位置，然后再按条件把它逐层________调整。
6、二叉搜索树的中序遍历得到的结点序列为____ ____。
三、运算题（每小题5分，共10分）
1、已知一个中缀算术表达式为： 3+4*(25-(6/15))-8@ ，写出对应的后缀算术表达式。
2、对以下图，试给出一种拓扑序列，若在它的邻接表存储结构中，每个顶点邻接表中的边结点都是按照终点序号从大到小链接的，则按此给出唯一一种拓扑序列。
四、阅读算法，回答问题（每小题5分，共20分）
1、int AA(LNode *HL , ElemType x)
{
int n=0;
LNode *p=HL;
while (p!=NULL)
{
if (p->data= =x) n++;
p=p->next;
}
return n;
}
对于结点类型为LNode的单链表，以上算法的功能为：
2、int BB(ElemType A[], int n, KeyType K)
{
for (int i=0;i<n;i++)
if (A[i].key = =K) break;
if (i<n) return i;
else return –1;
}
该算法的功能是：
3、 void CC( Stack &S)
{
Pop(S);
Push(S,50);
Push(S,45);
Peek(S);
}
假定调用算法时栈S 中已有2个元素（23，16）的栈，其中23时栈底，调用后得到的栈内容为（从栈底开始排列）：
4、void DD(ElemType A[],int n)
{
ElemType x;
int i,j,flag;
for(i=1;i<n-1;i++)
{
flag=0;
for(j=n-1;j>=i;j__)
if (A[j].stn<A[j-1].stn)
{
x=A[j];
A[j]=A[j-1];
A[j-1]=x;
flag=1;
}
if (flag= =0) return;
}
}
该算法的功能是什么，一般称为什么算法？
五、算法填空，在画有横线的地方填写合适的内容(10分)。
计算二叉数的的深度。
int BtreeDepth (BTreeNode *BT)
{
if (BT= =NULL)
return 0;
else
{
int dep1,dep2;
dep1= ;
dep2= ;
if (dep1>dep2) ;
return ;
}
}
六、编写算法(10分)
编写一个算法，返回搜索树中的关键字最小的元素值。
《数据结构》模拟题（二）
一、单选题 （每空2分，共10分）
1、队列的删除操作是在（ ）进行。
A．队首 B．队尾
C．队前 D．对后
2、当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（ ）语句修改top指针。
A．top++; B．top=0;
C．top--; D．top=N;
3、由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。
A．51 B．23
C．53 D．74
4、在一棵二叉树中，第4层上的结点数最多为（ ）。
A．31 B．8
C．15 D．16
5、 向堆中插入一个元素的时间复杂度为（ ）。
A．O(log2n) B．O(n)
C．O(1) D．16 O(nlog2n)
二、填空题（每空1分，共20分）
1、数据的存储结构被分为____________、___________、____________和____________四种。
2、若对一棵二叉树的结点编号从0开始顺序编码，按顺序存储，把编号为0的结点存储到a[0]中，其余类推，则a[i]元素的左孩子元素为________，右孩子元素为________，双亲元素(i>0)为________。
3、从一个栈删除元素时，首先取出 ，然后再前移一位 。
4、后缀表达式“2 10 + 5 * 6 – 9 /”的值为 。
5、假定一棵树的广义表表示为A(B(C(D,E),F,G(H,I,J)),K)，则度为3、2、1、0的结点数分别为______、______、______和______个。
6、在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。
7、在索引表中，若一个索引项对应主表中的一条记录，则称此索引为________索引，若对应主表中的若干条记录，则称此索引为________索引。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论