数据结构年试题及答案汇编.docVIP

数据结构基础历年试题汇编 一、2006年上半年 ● 在以下情形中，___(35)___适合于采用队列数据结构。 (35)A．监视一个火车票售票窗口等待服务的客户　　D．描述一个组织中的管理机构 　　C．统计一个商场中的顾客数　　　　　　　　　D．监视进入某住宅楼的访客 ● 元素3、1、2依次全部进入一个栈后，陆续执行出栈操作，得到的出栈序列为___(36)___。 (36)A．3、2、1　　　　 B．3、1、2　　　　C．1、2、3　　　 D．2、1、3 ● 一棵二叉树如下图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点(根结点的下标为1，若某结点的下标为i，则其左孩子位于下标2i处、右孩子位于下标2i+1处)，则该数组的大小至少为___(37)___；若采用二叉链表存储该二叉树(各 个结点包括结点的数据、左孩子指针、右孩子指针)，则该链表中空指针的数目为___(38)___。 (37)A．6　　　B．10　　　C．12　　　D．15 (38)A．6　　　B．7　　　 C．12　　　D．14 ● 以下各图用树结构描述了7个元素之间的逻辑关系，其中___(39)___适合采用二分法查找元素。 　　● 对于二维数组a[0…4,1…5]，设每个元素占1个存储单元，且以行为主序存储，则元素a[2,1]相对于数组 HYPERLINK 空间起始地址的偏移量是___(40)___。 (40)A．5　　　　　　 B．10　　　　　　C．15　　　　　　D．25 ● 若n表示问题的规模、O(f(n))表示算法的时间复杂度随n变化的增长趋势，则算法时间复杂度最小的是___(59)___。 (59)A．O(n2)　　　　　　B．O(n)　　　　　C． O(log n)　　　　　D．O(nlog n) 二、2006年下半年 ●? 在链表结构中，采用 （35） 可以用最少的 HYPERLINK /article/17/21/2007/20070321790.html \t _blank 空间代价和最高的时间效率实现队列结构。 （35）A.? 仅设置尾指针的单向循环链表????? B.? 仅设置头指针的单向循环链表 C.? 仅设置尾指针的双向链表??????????D.? 仅设置头指针的双向链表 ●? 若需将一个栈 S 中的元素逆置，则以下处理方式中正确的是 （36） 。 （36）A.? 将栈 S 中元素依次出栈并入栈 T，然后栈 T 中元素依次出栈并进入栈 S B.? 将栈 S 中元素依次出栈并入队，然后使该队列元素依次出队并进入栈 S C.? 直接交换栈顶元素和栈底元素 D.? 直接交换栈顶指针和栈底指针 ●? 已知 N 个数已存入数组 A[1..M]的前 N 个元素中（NM），为在 A[i]（1≤i≤N）之前插入一个新数，应先 （37） ，以挪出一个空闲位置插入该数。 （37）A.? 从 A[i]开始直到 A[1]，每个数向后移动一个位置 B.? 从 A[1]开始直到 A[i]，每个数向后移动一个位置 C.? 从 A[i]开始直到 A[N]，每个数向前移动一个位置 D.? 从 A[N]开始直到 A[i]，每个数向后移动一个位置 ●? 若某二叉树的先序遍历序列和中序遍历序列分别为 PBECD、BEPCD，则该二叉 树的后序遍历序列为 （38） 。 （38）A. PBCDE??????????? B. DECBP?????? C. EBDCP??????? D. EBPDC ●? 无向图的邻接矩阵一定是 （39） 。 （39）A.? 对角矩阵?????? B.? 稀疏矩阵??? C.? 三角矩阵??? D.? 对称矩阵 ●? 对具有 n 个元素的有序序列进行二分查找时， （40） 。 （40）A.? 查找元素所需的比较次数与元素的位置无关 B.? 查找序列中任何一个元素所需要的比较次数不超过log2(n+1)? C.? 元素位置越靠近序列后端，查找该元素所需的比较次数越少 D.? 元素位置越靠近序列前端，查找该元素所需的比较次数越少 三、2007年上半年 ● 若将下图(a)所示的无向图改为完全图，则还需要增加 （36） 条边；下图(b)的邻接矩阵表示为 （37） （行列均以A、B、C、D、E为序）。 （36）A. 1 B. 2 C. 5 D. 15 （37） ● 若线性表（23, 14, 45, 12, 8, 19, 7）采用散列法进行存储和查找。设散列函数为H(Key)=Key mod 7并采用线性探查法（顺序地探查可用存储单元）解决冲突，则构造的散列表为 （38） ，其中，mod表示整除取余运算。 （38） ● 在执行递归过程时，通常使用的数据结构是 （39） 。 （39