发布时间 : 星期一 文章2009-2010数据结构试题2更新完毕开始阅读
数据结构试卷二
一、选择题（20分，每题1分）
1、数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（ b ）
A 低 B 高 C 相同 D 不好说
2、在一个长度为n的顺序表中删除第i个元素（0<=i<=n）时，需向前移动（ c ）个元素。
A n-1 B n-i+1 C n-i-1 D i
3、线性表的顺序存储结构是一种（ a ）的存储结构
A 随即存取 B 顺序存取 C 索引存取 D 哈希存取
4、在一个单链表中，已知q节点是p节点的前驱节点，若在q和p之间插入s节点，则须执行（ ）
A s.next=p.next;p.next=s B q.next=s;s.next=p C p.next=s.next;s.next=p D p.next=s;s.next=q
5、栈通常采用的两种存储结构为（ ）
A 散列方式和索引方式 B 顺序存储结构和链式存储结构 C 链表存储结构和数组 D 线性存储结构和非线性存储结构 6、一个队列的进队序列为1、2、3、4，则出队序列为（ ）
A 1、2、3、4 B 4、3、2、1 C 1、4、3、2 D 3、2、4、1 7、判断顺序栈（最多节点数为m）为栈满的条件是（ ） A top=0 B top=m C top！=0 D top！=m ？8、循环队列为空队列的判断条件是（ ）
A Q.rear=Q.front B (Q.rear+1)%MaxSize=Q.front C Q.rear=0 D Q.front=0
9、在一棵度为3的树中，度为3的节点数为2个，度为2的节点数为1个，度为1的节点数为1，则度为0的节点数为（ ）个n=n0+n1+n2+n3 n=0*n0+1*n1+2*n2+3*n3+1 A 4 B 5 C 6 D 7 10、下面叙述正确的是（ ）
A 二叉树是特殊的树 B 二叉树等价于度为2的树
C 完全二叉树必须为满二叉树 D 二叉树的左右子树没有次序之分 11、对于顺序存储的有序表（5，12，20，26，37，42，46，50，64），若采用折半查找，则查找元素26的比较次数为（ ）
A 2 B 3 C 4 D 5 12、若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为（ ）
A n B n+1 C (n-1)/2 D (n+1)/2
13、在对n个元素尽享直接插入排序的过程中，共需要进行（ ）趟。 A n B n+1 C n-1 D 2n
14、假定对元素序列（7，3，5，9，1，12，8，15）进行快速排序，则进行第一次划分后，得到的左区间中的元素个数为（ ）
A 2 B 3 C 4 D 5
15、在平均情况下速度最快的排序方法为（ ）
A 简单选择排序 B 归并排序 C 堆排序 D 快速排序 二、填空题（15分，每题1分）
1、数据逻辑结构包括（ 线性、树形、图形 ）三种类型，树形结构和图形结构合称（ 非线性结构 ）。
2、数据结构按逻辑结构可分为两大类，分别是（ 线性结构 ）和（非线性结构 ）。 3、线性表是一种典型的（ 线性 ）结构。
4、在线性表的顺序存储结构中，元素之间的逻辑关系是通过（ 首节点位置 ）决定的；在线性表的连接存储中，元素之间的逻辑关系是通过（ 指针 ）决定的。
5、当对一个线性表经常进行存取操作，而很少进行插入和删除操作，则采用（ 顺序 ）存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用（ 链式 ）存储结构为宜。 6、带有头节点的单链表head为空的条件是（ head.next=null ）
7、设有一空栈，现有输入序列1，2，3，4，5，经过push ,push,pop,push,pop,push,push后，输出序列为（ 2\\3\\5\\4\\1 ）
8、一个循环队列能容纳的最多节点的数目为60，当front=47，rear=23时，该队列当前有的节点数为（37 ）
9、线性表、栈和队列是（ 线性 ）结构，可以在线性表的（ 任意 ）位置插入和删除元素；对于栈只能在（ 栈顶 ）插入和删除元素；对于队列只能在（ 队尾 ）插入元素和在（ 队头）删除元素
10、在一棵二叉排序树上按（ 中序 ）遍历得到的节点序列是一个有序序列 11、由三个节点构成的二叉树，共有（ 5 ）不同的状态
12、设高度为h的二叉树中只有度为0和2的节点，则此类二叉树中所包含的节点至少为（ （2*h）-1 ）
13、二叉树的三叉链表比二叉列表多一个指向（ 双亲 ）指针域
14、以折半查找方法在一个查找表上进行查询时，该查找表必须组织成（ ）存储的（ ）表
15、若对一组记录（46，79，56，38，40，80，35，50，74）进行直接插入排序，当把第8个记录插入到前面已排序的有序表时，为寻找插入位置需比较（ 7）次。 三、判断题（15分，每题1分） 1、数据元素是数据的最小单位 F
2、数据是由一些类型相同的数据元素构成的。T 3、逻辑结构相同的数据，节点类型也一定相同。 F
4、健壮的算法不会因非法输入数据而出现莫名其妙的执行结果。 T 5、程序一定是算法 F
6、静态链表与动态链表的插入、删除操作类似，不需做元素的移动 T 7、在双链表中，可以从任一节点开始沿同一方向查找到任何其他节点 F 8、顺序栈中元素值的大小是有序的 T 9、空栈没有栈顶指针 F
10、栈和队列都是限制存取端的线性表 T
11、队列的输入序列为123….n，输出序列为a1a2…..an，则有ai 13、二叉树中每个节点的度不能超过2，所以二叉树是一种特殊的树 14、顺序查找法使用于存储结果为顺序或链式存储的线性表 15、对于n个记录的集合进行冒泡排序，所需要的平均时间是O(n) 四、简答题（40分，每题5分） 1、简述逻辑结构与存储结构的关系 2、当为解决某一问题而选择数据结构时，应从哪些方面考虑？ 3、简述在什么情况下使用顺序表比使用链表好？ 4、设有一个数列的输入顺序为123456，若采用栈结构，并以A和D分别表示进栈和出栈操作，试问通过进栈和出栈操作的合法序列，能否得到输出顺序为325641，如果能，使用A和D写出操作过程，若不能，说明原因。 5、简述队列和栈这两种数据结构的相同点和不同点 6、简述分块查找的基本思想 7、比较直接插入排序和希尔排序的不同点 8、数据元素进栈的次序为a、b、c、d，进栈过程中允许出栈，试写出各种可能的出栈元素序列。 五、应用题（10分，每题5分） 1、现有按后根遍历二叉树的结果为C、B、A，有几种不同的二叉树可以得到这一结果？ 并画出所有符合条件的二叉树。 2、已知散列函数为H(k)=k，关键值序列为19、14、23、1、68、20、84、27、55、11、10、79，处理冲突的方法为线性探测法，散列表长度为13，试画出该散列表，并计算等概率情况下查找成功的平均查找长度。