模拟试卷0612(含参考答案)数据结构.doc

PAGE PAGE 5 数据结构模拟试题及答案 选择题（30分）（每题2分） 下列程序段的时间复杂度为： A i=1;j=0; while(i+j=n) { if (ij) j++; else i++; } A. O（n） B. O（nlog2n） C. O（i*j） D. O（i+j） 2．一个图1单链表表示的整数数列如下: 结点head-next-next 和*P的值分别为：B 1947 19 47 64 93 P head 图1 图1 3．顺序表是线性表的( )B A) 链式存储结构 B)顺序存储结构 C)索引存储结构 D)散列存储结构 4．线性表若采用链式存储结构时，要求内存中可用存储单元的地址 ( ) D A) 必须是连续的 B) 部分地址必须是连续的 C) 一定是不连续的 D) 连续或不连续都可以 5．一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是( )C A) e,d,c,b,a B)d,e,c,b,a C) d,c,e,a,b D) a,b,c,d,e 6.表达式a×(b＋c)－d的前缀表达式是（ ）。D （A）abcd×＋－ （B）abc＋×d－ （C）abc×＋d－ （D）－×a＋bcd 7．在下列链表中，不能从任一结点出发访问到表中的所有结点的是( )：A A) 单链表 B) 单向循环链表 C) 双向循环链表 D) 循环链表 8.判定一个栈ST(最多元素为m0)为栈满的条件是（ ）。C （A）ST-〉top!=0 （B）ST-〉top==0 （C）ST-〉top==m0 （D）ST-〉top==m0-1 9．一个所有非终端结点都有非空的左右子树的二叉树，叶子结点的个数为n，那么二叉树上的结点总数为（ ）C A. 2n B. 2n+1 C. 2n-1 D. 不能唯一确定 c75 c 7 5 2 a b d 4 图2 A.46 B.36 C.47 D.48 11.在单链表结构的栈中，弹栈得到的结点和压栈成为的结点分别为（ ）：D A.头结点和首结点 B. 头结点和尾结点 C. 尾结点和尾结点 D. 首结点和首结点 12．在一个具有n个节点的无向图，其生成树需要几条边（ ）：C A. n B. n+1 C. n-1 D.n/2 13． 非空的循环单链表head的尾节点（由r所指向）满足 C AB A B C 图3 C) r-next=head D) r=head 14.一棵深度为5的完全二叉树，从1开始对结点按照层次编号， 则编号为13的结点，其父结点编号为（ ）：B A.10 B.6 C.5 D.7 15．对于图3所示的二叉树，先根序列和后根序列分别为（C ）： A) ABC和BCA B) ACB和 BCA C) ABC和CBA D) ACB和CBA 填空（30分）（每空2分） head指向单链表的表头，p指向单链表的表尾结点，则执行p-next=head后，该单链表构成 循环链表 2．在单链表中，若p和s是两个指针，且满足p-next与s相同，则语句p-next=s-next的作用是 删除 s指向的结点。 3．在一个长度为n的顺序表中的第i(1≤i≤n＋1)个元素之前插入一个元素时，需向后移动的元素个数为 n-i+1 。 4．设r指向单循环链表的最后一个结点，要在最后一个结点之后插入指针s所指的结点，需要执行的3个语句是 s-next=r-next ；r-next=s;r=s; 5．二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法 不正确 （正确/不正确）。 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较 3 次。 已知二叉树有50个叶子结点，并且仅有一个孩子的结点数为30，则总结点数为 129 。 8．二叉树按某种顺序线索化后，某结点的右链域或者指向右孩子，或者指向 该结点的直接后继 。 9．有4棵树构成的森林，树上的结点个数分别为n1,n2,n3,n4，则这个森林转换成二叉树后，这颗二叉树上根结点的右子树上结点的个数为： n2+n3+n4 10．对二叉链表的访问只能从 根 指针开始。 以下3个题目为算法填空题，每空