数据结构模拟试卷..docVIP

注：1）请书写在答题纸上，写在试卷上不得分； 2）试卷与答题纸一起上交。 一、选择题（每个空只有一个正确答案） 1、若某线性表中最常用的操作是在最后一个元素之前插入和删除元素，则采用___________最节省运算时间。 A、单链表 B、仅有头指针的单循环链表 C、仅有尾指针的单循环链表 D、双链表 2、哈夫曼树的带权路径长度WPL等于___________。 A、除根以外的所有结点的权植之和 B、所有结点权值之和 C、各叶子结点的带权路径长度之和 D、根结点的值 3、设输入序列为1,2,3,4,5，借助一个栈不可能得到的输出序列是___________。 A．1,2,3,4,5 B．1,4,3,2,5 C．4,1,3,2,5 D．1,3,2,5,4 4、对于下面二叉树，按后序遍历所得的结点序列为___________。 A．1234567 B．1245367 C．4251637 D．4526731 5、栈和队列都是___________。 A．顺序存储的线性结构 B．链式存储的线性结构 C．操作受限制的线性结构 D．操作受限制的非线性结构 6、已知完全二叉树有30个结点，则整个二叉树有___________个度为1的结点。 A．0 B．1 C．2 D．不确定 7、若长度为n的线性表采用顺序存储结构，将其第i个位置的元素删除算法的时间复杂度为 A． B． C．O(logn) D． 8、设有二维数组A(1..12，1..10)，其每个元素占4个字节，数据按列优先顺序存储，第一个元素的存储地址为100。则元素A(5，5)的存储地址为 。 A．176 B．276 C．208 D．308 9、算法分析的两个主要方面是 。 A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 10、设栈的输入序列是（1、2、3、4），则 不可能是其出栈序列。 A．1243 B．2134 C．1432 D．4312 11、在单链表中，指针p指向链表某结点，现将指针s所指结点插到p所指结点之后，则其实现语句应为 A．s-next=p+1;p-next=s; B．p-next=s; s-next=p-next; C．s→next=p→next; p→next=s→next; D．s→next=p→next;p→next=s; 12、栈和队列的共同点是 。 A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有共同点 13、假定一个顺序循环队列的队首和队尾指针分别用front和rear表示，则判队空的条件是 。 A．front+1= =rear B．front= =rear+1 C．front= =0 D．front= =rear 14、若串S=’AND’，n（n0）个结点的二叉链表中，非空链域的个数为____④ _______。 4、下面程序段的时间复杂度是 ⑤ 。 for(j=0; j＜n;j++) for(i=0; i＜n;i++) p*=2; 5、在对有10个数据的有序表作二分查找时，有____⑥_______个结点的查找长度是4。 6、单链表表示法的基本思想是用 ⑦ 表示结点间的逻辑关系。 7、在下列树中，结点G的子孙结点有 ⑧ 。 8、深度为6（根的层次号为1）的完全二叉树至多有______ ⑩ _____个结点。 三、判断题： 1. 线性表采用链表存储时，结点内部的存储空间一定是连续的。 ( ) 2．队列只能采用链式存储方式。 ( ) 3. 消除递归必须使用栈。 （ ） 4．由二叉树的先序序列和中序序列能唯一确定一棵二叉树。 （ ） 5．存在有偶数个结点的满二叉树。