《数据结构历年试题及答案汇编》由会员分享，可在线阅读，更多相关《数据结构历年试题及答案汇编（15页珍藏版）》请在金锄头文库上搜索。
1、数据结构基础历年试题汇编一、2006年上半年 在以下情形中，_(35)_适合于采用队列数据结构。(35)A监视一个火车票售票窗口等待服务的客户D描述一个组织中的管理机构C统计一个商场中的顾客数D监视进入某住宅楼的访客 元素3、1、2依次全部进入一个栈后，陆续执行出栈操作，得到的出栈序列为_(36)_。(36)A3、2、1 B3、1、2C1、2、3 D2、1、3 一棵二叉树如下图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点(根结点的下标为1，若某结点的下标为i，则其左孩子位于下标2i处、右孩子位于下标2i+1处)，则该数组的大小至少为_(37)_；若采用二叉链表存储该二叉树(各
2、 个结点包括结点的数据、左孩子指针、右孩子指针)，则该链表中空指针的数目为_(38)_。(37)A6B10C12D15(38)A6B7 C12D14 以下各图用树结构描述了7个元素之间的逻辑关系，其中_(39)_适合采用二分法查找元素。 对于二维数组a04,15，设每个元素占1个存储单元，且以行为主序存储，则元素a2,1相对于数组空间起始地址的偏移量是_(40)_。(40)A5 B10C15D25 若n表示问题的规模、O(f(n)表示算法的时间复杂度随n变化的增长趋势，则算法时间复杂度最小的是_(59)_。(59)AO(n2)BO(n)C O(log n)DO(nlog n) 二、2006年下
3、半年 在链表结构中，采用 （35） 可以用最少的空间代价和最高的时间效率实现队列结构。 （35）A. 仅设置尾指针的单向循环链表 B. 仅设置头指针的单向循环链表 C. 仅设置尾指针的双向链表D. 仅设置头指针的双向链表 若需将一个栈 S 中的元素逆置，则以下处理方式中正确的是 （36） 。 （36）A. 将栈 S 中元素依次出栈并入栈 T，然后栈 T 中元素依次出栈并进入栈 S B. 将栈 S 中元素依次出栈并入队，然后使该队列元素依次出队并进入栈 S C. 直接交换栈顶元素和栈底元素 D. 直接交换栈顶指针和栈底指针 已知 N 个数已存入数组 A1.M的前 N 个元素中（N1)的满二叉树，
4、其结点总数为 （36） 。对非空满二叉树，由根结点开始，按照先根后子树、先左子树后右子树的次序，从 1、2、3、依次编号，则对于树中编号为 i 的非叶子结点，其右子树的编号为 （37） （高度为 3 的满二叉树如下图所示）。（36）A. 2 B. 2h-1 C. 2h 1 D. 2h-1+1（37）A. 2i B. 2i-1 C. 2i+1 D. 2i+2 在数据结构中，结点（数据元素）及结点间的相互关系组成数据的逻辑结构。按逻辑结构的不同，数据结构通常可分为（38） 两类。（38）A.线性结构和非线性结构 B.紧凑结构和稀疏结构 C.动态结构和静态结构 D.内部结构和外部结构采用哈希（或散列
5、）技术构造查找表时，需要考虑冲突（碰撞）的处理，冲突是指（39）。（39）A.关键字相同的记录被映射到不同的哈希地址 B.关键字依次被映射到编号连续的哈希地址C.关键字不同的记录被映射到同一个哈希地址D.关键字的数目超过哈希地址的数目数据结构中的树最适合用来表示（40）的情况。（40）A.数据元素有序 B.数据元素之间具有多对多关系 C.数据元素无序 D.数据元素之间具有一对多关系某循环队列的容量为M，队头指针指向队头元素，队尾指针指向队尾元素之后，如下图所示（M=8），则队列中的元素数目为（41）（MOD 表示整除取余运算）。（41）A. rear front B. front rear C. (rear front + M) MOD M D. (front rear + M) MOD M二叉排序树或者
