《数据结构》模拟题（一）
一、单选题 （每空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）中的每个元素，请以线性表的 形式给出每插入一个元素后堆的状态。（为小根堆）