《数据结构模拟试题附答案》由会员分享，可在线阅读，更多相关《数据结构模拟试题附答案（20页珍藏版）》请在金锄头文库上搜索。
1、数据结构试卷(1)一、选择题(30 分)1. 设一组权值集合W=2, 3, 4, 5, 6，则由该权值集合构造的哈夫曼树中带权路径长度 之和为( )。(A) 20(B) 30(C) 40(D) 452. 执行一趟快速排序能够得到的序列是( )。(A)41，12，34，45，275572，63(B)45，34，12，41557263，27(C)63，12，34，45，275541，72(D)12，27，45，415534，63，723设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是()。(A) head=0(B) head-next=0(C) head-next=head(D
2、) head!=04时间复杂度不受数据初始状态影响而恒为O(nlogn)的是()。2(A) 堆排序 (B) 冒泡排序 (C) 希尔排序 (D) 快速排序5. 设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是()。(A) 空或只有一个结点(B) 高度等于其结点数(C) 任一结点无左孩子(D) 任一结点无右孩子6一趟排序结束后不一定能够选出一个元素放在其最终位置上的是()。(A) 堆排序(B) 冒泡排序(C) 快速排序(D) 希尔排序7设某棵三叉树中有40个结点，则该三叉树的最小高度为()。(A) 3(B) 4(C) 5(D) 68. 顺序查找不论在顺序线性表中还是在链式线性表
3、中的时间复杂度为()。(A) O(n)(B) O(n2)(C) O(n1/2)(D)O(1ogn)29二路归并排序的时间复杂度为()。(A) O(n)(B) O(n2)(C) O(nlogn)2(D)O(1ogn)210. 深度为 k 的完全二叉树中最少有()个结点。(A) 2k-1-1(B) 2k-1(C) 2k-1+1(D)2k-111. 设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针, 指针变量s指向将要入队列的结点X,则入队列的操作序列为()。(A) front-next=s；front=s；(B) s-next=rear；rear=s；(C) re
4、ar-next=s；rear=s；(D) s-next=front；front=s；12. 设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为()。(A)O(n+e)(B)O(n2)(C)O(ne)(D)O(n3)13. 设某哈夫曼树中有199个结点，则该哈夫曼树中有( )个叶子结点。(A)99(B)100(C)101(D)10214. 设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为()。(A)O(n)(B)O(n2)(C)O(nlogn)(D)O(1ogn)2215. 设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为()。(A)第i行非0元素的
5、个数之和(B)第i列非0元素的个数之和(C)第i行0元素的个数之和(D)第i列0元素的个数之和 二、判断题(20 分)1调用一次深度优先遍历可以访问到图中的所有顶点。（ ）2分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（ ）3冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（ ）4满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（ ）5设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（ ）6层次遍历初始堆可以得到一个有序的序列。（ ）7设一棵树T可以转化成二叉树BT,则二叉树BT中一定没有右子树。（）8线性表的顺序存储结构比链式存储结构更
6、好。（ ）9. 中序遍历二叉排序树可以得到一个有序的序列。（）10. 快速排序是排序算法中平均性能最好的一种排序。（ ）三、填空题（30 分）1. for（i=l, t=1, s=0； i=n； i+） t=t*i； s=s+1； 的时间复杂度为。2. 设指针变量p指向单链表中结点A,指针变量s指向被插入的新结点X,则进行插入操作的语句序列为（设结点的指针域为 next）。3. 设有向图 G 的二元组形式表示为 G =（D, R）, D=1, 2, 3, 4, 5, R=r, r=, , , , , ,则给出该图的一种拓扑排序序列。4. 设无向图G中有n个顶点，则该无向图中每个顶点的度数最多是
7、。5. 设二叉树中度数为0的结点数为50,度数为1的结点数为30,则该二叉树中总共有个结点数。6. 设 F 和 R 分别表示顺序循环队列的头指针和尾指针,则判断该循环队列为空的条件为 。7. 设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是。8. 简单选择排序和直接插入排序算法的平均时间复杂度为。9. 快速排序算法的空间复杂度平均情况下为,最坏的情况下为。10. 散列表中解决冲突的两种方法是和。四、算法设计题（20 分）1. 设计在顺序有序表中实现二分查找的算法。2. 设计判断二叉树是否为二叉排序树的算法。3. 在链式存储结构上设计直接
8、插入排序算法一、选择题(30 分) 1设某无向图有 n 个顶点，则该无向图的邻接表中有( )个表头结点。(A) 2n(B) n(C) n/2(D) n(n-1)2. 设无向图G中有n个顶点，则该无向图的最小生成树上有()条边。(A) n(B) n-1(C) 2n(D) 2n-13. 设一组初始记录关键字序列为(60， 80， 55， 40， 42， 85)，则以第一个关键字45 为基准 而得到的一趟快速排序结果是( )。(A) 40，42， 60，55，80，85(B)42，45，55， 60，85，80(C) 42，40， 55，60，80，85(D)42，40，60， 85，55，804.
9、 ( )二叉排序树可以得到一个从小到大的有序序列。(A) 先序遍历 (B) 中序遍历 (C) 后序遍历 (D) 层次遍历5. 设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结 点的左孩子结点的编号为( )。(A) 2i+1(B) 2i(C) i/2(D) 2i-16. 程序段 s=i=O； do i=i+l； s=s+i； while(iv=n)；的时间复杂度为()。(A) O(n)(B) O(nlog n) (C) O(n2)(D) O(n3/2)27. 设带有头结点的单向循环链表的头指针变量为head,则其判空条件是()。(A) head=0(B) head-n
10、ext=0(C) head-next=head(D) head!=08. 设某棵二叉树的高度为 10，则该二叉树上叶子结点最多有( )。(A) 20(B) 256(C) 512(D) 10249. 设一组初始记录关键字序列为(13， 18， 24， 35， 47， 50， 62， 83， 90， 115， 134),则利 用二分法查找关键字 90 需要比较的关键字个数为( )。(A) 1 (B) 2 (C) 3 (D) 410. 设指针变量 top 指向当前链式栈的栈顶，则删除栈顶元素的操作序列为( )。(A) top=top+1;(B) top=top-1;(C) top-next=top;
11、(D) top=top-next;二、判断题(20 分)1. 不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。( )2. 当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。( )3. 设某堆中有 n 个结点，则在该堆中插入一个新结点的时间复杂度为 O(logn)。 ()24. 完全二叉树中的叶子结点只可能在最后两层中出现。( )5. 哈夫曼树中没有度数为 1 的结点。( )6. 对连通图进行深度优先遍历可以访问到该图中的所有顶点。( )7. 先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。( )8. 由树转化成二叉树，该二叉树的右子树不一定为空。( )9.
12、线性表中的所有元素都有一个前驱元素和后继元素。( )10. 带权无向图的最小生成树是唯一的。( )三、填空题(30 分)1. 设指针变量p指向双向链表中的结点A,指针变量s指向被插入的结点X,则在结点A的后面插入结点X的操作序列为=p； s-right=p-right； =s；p-right-left=s；(设结点中的两个指针域分别为left和right)。2. 设完全有向图中有 n 个顶点,则该完全有向图中共有条有向条；设完全无向图中有 n 个顶点,则该完全无向图中共有条无向边。3. 设关键字序列为(K, K,，K),则用筛选法建初始堆必须从第个元素开始进l 2n行筛选。4. 解决散列表冲突
13、的两种方法是和。5. 设一棵三叉树中有50个度数为0的结点, 21个度数为2的结点,则该二叉树中度数为3 的结点数有个。6. 高度为 h 的完全二叉树中最少有个结点,最多有个结点。7. 设有一组初始关键字序列为(24, 35, 12, 27, 18, 26),则第3趟直接插入排序结束后的结果的是 。8. 设有一组初始关键字序列为(24, 35, 12, 27, 18, 26),则第3趟简单选择排序结束后的结果的是 。9. 设一棵二叉树的前序序列为ABC,则有种不同的二叉树可以得到这种序列。10. 下面程序段的功能是实现一趟快速排序,请在下划线处填上正确的语句。struct record int
14、 key;datatype others;void quickpass(struct record r, int s, int t, int &i)int j=t; struct record x=rs; i=s;while(ij)while (ix.key) j=j-1; if (ij) ri=rj;i=i+1;while () i=i+1; if (ij) rj=ri;j=j-1;四、算法设计题(20 分)1. 设计在链式结构上实现简单选择排序算法。2. 设计在顺序存储结构上实现求子串算法。3. 设计求结点在二叉排序树中层次的算法。一、选择题(30 分)1. 字符串的长度是指( )(B) 串中不同字母的个数(D) 串中不同数字的个数(A) 串中不同字符的个数(C) 串中所含字符的个数2. 建立一个长度为 n 的有序单链表的时间复杂度为( )(A) O(n) (B) O(1)3. 两个字符串相等的充要条件是(A) 两个字符串的长度相等(C)同时具备(A)和(B)两
