数据结构测试题1.ppt

* 判断 1. 在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是: p-llink：=q； q-rlink：=p； p-llink-rlink：=q； q-llink：=q； * 2．线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。 3．向量、栈和队列都是 结构，可以在向量的 位置插入和删除元素；对于栈只能在 插入和删除元素；对于队列只能在 c 插入元素和 删除元素 * 4. 在一个长度为n的顺序表中第i元素（1=i=n）之前插入一个元素时，需向后移动 个元素 5 ．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为12345，为了得到13542出栈顺序，相应的S和X的操作串为_______。 * 6．从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（ ）个结点。 A．n B．n/2 C．(n—1)/2 D．(n+1)/2 7. 对稀疏矩阵进行压缩存储目的是( ) A．便于进行矩阵运算 B。便于输入和输出 C．节省存储空间 D。降低运算的时间复杂度 * * 8. 在下面的程序段中，对x的赋值语句的频度为( ) for i :=1 to n do for j:=1 to n do for k:=1 to n2 do x:=x+1; A. O(2n) B.O(n4) C. O(n2) D.O(log2n) * 9. 下述哪一条是顺序存储结构的优点？（ ） A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便的用于各种逻辑结构的存储表示 10. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间. A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 * 11. 下面的叙述不正确的是（ ） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 * 12. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（ ）。 A. 不确定 B. n-i+1 C. i D. n-i * 13. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 14. 一个递归算法必须包括（ ）。 A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分 * 15. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。 A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈 * 由带权值为{59，4，37，51，2}的叶子结点构造一棵哈夫曼树，则该树的带权路径长度为 。 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶子结点。 * 某二叉树T有n个节点，设按某种顺序对T中的每个结点进行编号，编号为1，2，… ，n，且有如下性质：T中任一节点V，其编号等于左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。这时是按（ ）编号的。 中序遍历序列 B. 先序遍历序列 C. 后序遍历序列 层次顺序 * 已知某二叉树的后序遍历序列是dabec,中序遍历序列是deabc，它的先序遍历序列是( ) A acbed B decab C deabc D cedba 对一个满二叉树，m个树叶，n个结点， 深度为h， 则( ) A． n=h+m B. h+m=2n C.