《数据结构》试卷五.doc

《数据结构》试卷五 一、填空题：（共２０分） 1、“好”算法应达到的目标正确性，易读性，健壮性和 。 2、广义表的尾元素为 。 3、一维数组存储地址计算公式为 (设b为基地址，每个元素所占存储单元数为l，下标取值范围为(c1,d1)) 4、栈简称 结构，它是一种后进先出结构。 5、一棵深度为K，且有2-1个结点的二叉树称为 。 6、树的带权路径长度为 。 7、P=BEIJING，R=JING，则R在P中位置为 。 8、关键字是数据元素中用以标识一个数据元素的某一个 的值， 若此关键字可唯一标识一个记录，则称此关键字为 。 9、设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，已知T1、T2和T3的结点个数分别n1、n2和n3，则二叉树B的根结点的左子树和右子树中的结点个数分别为n1—1和。10、如果对于给定的一组权值，所构造出的二叉树的带权路径长度最小，则该树称为________。 A[2i-1] (B) A[2i+1] (C) A[i/2](D) A[2i] 3、若进栈序列为1,2,3,4,假定进栈和出栈可以穿插进行，则可能出栈序列为----------( ) (A)2,4,1,3 (B)3,1,4,2 (C) 3,4,1,2 (D)1,2,3,4 4、对如下无向图G，若从顶点V1开始，按深度优先有哪些信誉好的足球投注网站进行遍历，则可能的访问顺序为-----------( ) (A) V1,V2,V3,V4,V5,V6,V7,V8 (C) V1,V2,V3,V4,V8,V5,V6,V7 (B) V1,V2,V4,V8,V5,V6,V3,V7 (D) V1,V2,V4,V5,V8,V3,V6,V7 V1 ／ ＼ V2 V3 ／ ＼ ／ ＼ V4 V5 V6 V7 ＼ ＼ ／ ／ ＼ ││ ／ ＼││／ V8 5、进行二分法查找，则线性表---------------( ) (A)必须以顺序方式存储 (B) 必须以链接方式存储,且数据元素已按值排好序 (C)必须以链接方式存储 (D) 必须以顺序方式存储,且数据元素已按值排好序 6、从未排序序列中挑选元素，并将其依次放入已排序序列(初始时为空)一端，这种排序方法称为------------( ) (A) 选择排序 (B) 归并排序 (C) 直接插入排序 (D) 快速排序 7、某二叉树的前序遍历结点访问顺序为A B C D E F G，中序遍历结点访问顺序为C B D A F G E,则其后序遍历结点访问顺序为----------------( ) (A) C D B G F E A (B) C D G F E A B (C) C D B A G F E (D) C D B F A G E 8、对n个记录的序列进行快速排序，所需的辅助空间为( ) (A) O(1) (B) O(logn) C) O(n) (D) O(n) 9、下列哪一个关键码序列不符合堆的定义? A)A、C、D、G、H、M、P、Q、R、X B)A、C、M、D、H、P、X、G、Q、R C)A、D、P、R、C、Q、X、M、H、G D)A、D、C、M、P、G、H、X、R、Q 2 10 12 13 3 4 5