数据结构试题 java数据结构面试题.doc

《数据结构试题 java数据结构面试题.doc》由会员分享，可在线阅读，更多相关《数据结构试题 java数据结构面试题.doc（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据构造试题 java数据构造面试题一、选择题(30分)1.以下程序段的时间复杂度为( )。(A) O(m_n_t) (B) O(m+n+t) (C) O(m+n_t) (D) O(m_t+n)2.设顺序线性表中有n个数据元素，那么删除表中第i个元素需要挪动( )个元素。(A) n-i (B) n+l -i (C) n-1-i (D) i3.设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，那么二叉树B的根结点的左子树的结点数为( )。(A) N1-1 (B) N2-1 (C) N2+N3 (D) N1+N34.利用直接插入排序法的

2、思想建立一个有序线性表的时间复杂度为( )。(A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(1og2n)5.设指针变量p指向双向链表中结点A，指针变量s指向插入的结点_，那么在结点A的后面插入结点_的操作序列为( )。(A) p-right=s; s-left=p; p-right-left=s; s-right=p-right;(B) s-left=p;s-right=p-right;p-right=s; p-right-left=s;(C) p-right=s; p-right-left=s; s-left=p; s-right=p-right;(D) s-l

3、eft=p;s-right=p-right;p-right-left=s; p-right=s;6.以下各种排序算法中平均时间复杂度为O(n2)是( )。(A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 冒泡排序7.设输入序列1、2、3、n经过栈作用后，输出序列中的第一个元素是n，那么输出序列中的第i个输出元素是( )。(A) n-i (B) n-1-i (C) n+l -i (D) 不能确定8.设散列表中有m个存储单元，散列函数H(key)= key % p，那么p最好选择( )。(A) 小于等于m的最大奇数 (B) 小于等于m的最大素数(C) 小于等于m的最大偶数 (D) 小于等

4、于m的最大合数9.设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有( )个。(A) 4 (B) 5 (C) 6 (D) 710.设完全无向图中有n个顶点，那么该完全无向图中有( )条边。(A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) (n-1)/211.设顺序表的长度为n，那么顺序查找的平均比拟次数为( )。(A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/212.设有序表中的元素为(13，18，24，35，47，50，62)，那么在其中利用二分法查找值为24的元素需要

5、经过( )次比拟。(A) 1 (B) 2 (C) 3 (D) 413.设顺序线性表的长度为30，分成5块，每块6个元素，假如采用分块查找，那么其平均查找长度为( )。(A) 6 (B) 11 (C) 5 (D) 6.514.设有向无环图G中的有向边集合E=，那么以下属于该有向图G的一种拓扑排序序列的是( )。(A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，315.设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，那么由这组记录关键字生成的二叉排序树的深度为( )。(A) 4 (B) 5 (C) 6 (D) 7二、填空题(30分

6、)1.设指针p指向单链表中结点A，指针s指向插入的结点_，那么在结点A的前面插入结点_时的操作序列为：1) s-ne_t=_;2) p-ne_t=s;3) t=p-data;4) p-data=_;5) s-data=t;2.设某棵完全二叉树中有100个结点，那么该二叉树中有_个叶子结点。3.设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，那么该循环队列中最多存储_队列元素。4.对一组初始关键字序列(40，50，95，20，15，70，60，45，10)进展冒泡排序，那么第一趟需要进展相邻记录的比拟的次数为_，在整个排序过程中最多需要进

7、展_趟排序才可以完成。5.在堆排序和快速排序中，假如从平均情况下排序的速度最快的角度来考虑应最好选择_排序，假如从节省存储空间的角度来考虑那么最好选择_排序。6.设一组初始记录关键字序列为(20，12，42，31，18，14，28)，那么根据这些记录关键字构造的二叉排序树的平均查找长度是_。7.设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，那么这棵二叉树的前序序列为_。8.设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，那么这棵哈夫曼树的高度为_。9.设一组记录关键字序列为(80，70，33

8、，65，24，56，48)，那么用挑选法建成的初始堆为_。10.10.设无向图G(如右图所示)，那么其最小生成树上所有边的权值之和为_。三、判断题(20分)1.有向图的邻接表和逆邻接表中表结点的个数不一定相等。( )2.对链表进展插入和删除操作时不必挪动链表中结点。( )3.子串“ABC”在主串“AABCABCD”中的位置为2。( )4.假设一个叶子结点是某二叉树的中序遍历序列的最后一个结点，那么它必是该二叉树的先序遍历序列中的最后一个结点。( )5.希尔排序算法的时间复杂度为O(n2)。( )6.用邻接矩阵作为图的存储构造时，那么其所占用的存储空间与图中顶点数无关而与图中边数有关。( )7.中序遍历一棵二叉排序树可以得到一个有序的序列。( )8.入栈操作和入队列操作在链式存储构造上实现时不需要考虑栈溢出的情况。( )9.顺序表查找指的是在顺序存储构造上进展查找。( )10.堆是完全二叉树，完全二叉树不一定是堆。( )四、算法设计题(20分)1.设计计算二叉树中所有结点值之和的算法。2.设计将所有奇数移到所有偶数之前的算法。3.设计判断单链表中元素是否是递增的算法。第 7 页 共 7 页