《数据结构》模拟题（一）

一、单选题 （每空2分，共10分）

1、某程序的时间复杂度为（3n+nlog2n+n2+8）, 其数量级表示为（ ）。 A．O（n） B．O（nlog2n）

C．O（n2） 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、对以下图，试给出一种拓扑序列，若在它的邻接表存储结构中，每个顶点邻接表中的边结点都是按照终点序号从大到小链接的，则按此给出唯一一种拓扑序列。 2

0 5 7

1 3 6 4 8 9 四、阅读算法，回答问题（每小题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

if (A[i].key = =K) break; if (i

该算法的功能是：

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

flag=0;

for(j=n-1;j>=i;j__)

if (A[j].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、在索引表中，若一个索引项对应主表中的一条记录，则称此索引为________索引，若对

应主表中的若干条记录，则称此索引为________索引。

8、对于二分查找所对应的判定树，它既是一棵_ ____，又是一棵_____ __ ___。

三、运算题（每小题5分，共10分）

1、 空堆开始依次向堆中插入线性表（64,52, 12,48,45,26）中的每个元素，请以线性表的

形式给出每插入一个元素后堆的状态。（为小根堆）