《数据结构导论 模拟试题》由会员分享，可在线阅读，更多相关《数据结构导论 模拟试题（18页珍藏版）》请在金锄头文库上搜索。
1、数据结构导论数据结构导论 模拟试题模拟试题（一）单项选择题（一）单项选择题1. 在二维数组中，每个数组元素同时处于（在二维数组中，每个数组元素同时处于（C ）个向量中。）个向量中。A. 0 B. 1 C. 2 D. n2. 已知单链表已知单链表 A 长度为长度为 m，单链表，单链表 B 长度为长度为 n，它们分别由表头指针所，它们分别由表头指针所指向，若将指向，若将 B 整体连接到整体连接到 A 的末尾，其时间复杂度应为（的末尾，其时间复杂度应为（ B ） 。A. O(1) B. O(m) C. O(n) D. O(m+n)3. 假定一个链式队列的队头和队尾指针分别为假定一个链式队列的队头和队
2、尾指针分别为 front 和和 rear，则判断队空，则判断队空的条件为的条件为(D)。A. front = rear B. front != NULLC. rear != NULL D. front = NULL4. 若让元素若让元素 1,2,3 依次进栈，则出栈次序不可能出现依次进栈，则出栈次序不可能出现(C)种情况。种情况。A. 3,2,1 B. 2,1,3 C. 3,1,2 D. 1,3,25. 图的广度优先搜索类似于树的（图的广度优先搜索类似于树的（D）遍历。）遍历。A. 先根先根 B. 中根中根 C. 后根后根 D. 层次层次6. 下面程序段的时间复杂度为下面程序段的时间复杂度为(
3、C)。for(int i=0; ilink=s; B. s-link=top-link; top-link=s;C. s-link=top; top=s; D. s-link=top; top=top-link;10. 一棵具有一棵具有 35 个结点的完全二叉树的高度为个结点的完全二叉树的高度为(A)。假定空树的高度为。假定空树的高度为-1。A. 5 B. 6 C. 7 D. 811. 一个有一个有 n 个顶点和个顶点和 n 条边的无向图一定是条边的无向图一定是(D) 的。的。A连通连通 B不连通不连通 C无回路无回路 D有回路有回路12. 在一个长度为在一个长度为 n 的顺序表的任一位置插入
4、一个新元素的时间复杂度为的顺序表的任一位置插入一个新元素的时间复杂度为（A ） 。A. O(n) B. O(n/2) C. O(1) D. O(n2)13. 已知广义表为已知广义表为 A(a,b,c),(d,e,f)，从，从 A 中取出原子中取出原子 e 的运算是（的运算是（ C ） 。ATail(Head(A) BHead(Tail(A)CHead(Tail(Head(Tail(A) DHead(Head(Tail(Tail(A)14. 在一棵树的静态双亲表示中，每个存储结点包含在一棵树的静态双亲表示中，每个存储结点包含(B)个域。个域。A 1 B 2 C 3 D 415. 有向图中的一个顶
5、点的度数等于该顶点的有向图中的一个顶点的度数等于该顶点的(C)。A入度入度 B出度出度 C入度与出度之和入度与出度之和 D(入度入度+出度出度)/15. 与邻接矩阵相比，邻接表更适合于存储与邻接矩阵相比，邻接表更适合于存储(C)。A无向图无向图 B连通图连通图 C稀疏图稀疏图 D稠密图稠密图17. 较快的数据搜索方法是（较快的数据搜索方法是（ D ）搜索方法。）搜索方法。A. 顺序顺序 B. 折半折半 C. 单链单链 D. 散列散列18. 在闭散列表中，散列到同一个地址而引起的在闭散列表中，散列到同一个地址而引起的“堆积堆积”问题是由于问题是由于（B）引起的。）引起的。A. 同义词之间发生冲突
6、同义词之间发生冲突 B. 非同义词之间发生冲突非同义词之间发生冲突C. 同义词之间或非同义词之间发生冲突同义词之间或非同义词之间发生冲突 D. 散列表散列表“溢出溢出”19. 根据根据 n 个元素建立一个有序单链表的时间复杂度为（个元素建立一个有序单链表的时间复杂度为（C ） 。A. O(1) B. O(n) C. O(n2) D. O(nlog2n)20. 假定一个顺序存储的循环队列的队头和队尾指针分别为假定一个顺序存储的循环队列的队头和队尾指针分别为 front 和和rear，则判断队空的条件为，则判断队空的条件为(D)。A. front+1=rear B. rear+1=frontC.
7、front=0 D. front=rear21. 假定一棵二叉树的第假定一棵二叉树的第 i 层上有层上有 3i 个结点，则第个结点，则第 i+1 层上最多有层上最多有(B)个结个结点。点。A. 3i B. 6i C. 9i D. 2i22. 对于具有对于具有 e 条边的无向图，它的邻接表中共有条边的无向图，它的邻接表中共有(C)个边结点。个边结点。Ae-1 Be+1 C2e D3e23. 图的深度优先搜索遍历类似于树的（图的深度优先搜索遍历类似于树的（ A ）次序遍历。）次序遍历。A. 先根先根 B. 中根中根 C. 后根后根 D. 层次层次24栈栈 S 最多能容纳最多能容纳 4 个元素。现有
8、个元素。现有 6 个元素按个元素按 A、B、C、D、E、F 的的顺序进栈顺序进栈, 问下列哪一个序列是可能的出栈序列问下列哪一个序列是可能的出栈序列?(C )A. E、D、C、B、A、F B. B、C、E、F、A、D C. C、B、E、D、A、F D. A、D、F、E、B、C25将一棵有将一棵有 100 个结点的完全二叉树从根这一层开始，每一层从左到右个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为依次对结点进行编号，根结点编号为 1，则编号为，则编号为 49 的结点的左孩子的的结点的左孩子的编号为：编号为：( A )/左孩子：左孩子：2*i，右孩子：，右孩子：
9、2*i+1.A. 98 B. 99 C. 50 D. 4826. 对下列关键字序列用快速排序法进行排序时，速度最快的情形是：对下列关键字序列用快速排序法进行排序时，速度最快的情形是：( B )A. 21、25、5、17、9、23、30 B. 25、23、30、17、21、5、9C. 21、9、17、30、25、23、5 D. 5、9、17、21、23、25、3027对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为(C)A. 顺序表顺序表 B. 用头指针表示的单循环链表用头指针表示的单循环链表C. 用尾指针表示的单循环链表用尾指
10、针表示的单循环链表 D. 单链表单链表28假设以第一个元素为分界元素，对字符序列（假设以第一个元素为分界元素，对字符序列（Q, H, C, Y, P, A, M, S, R, D, F, X）进行快速排序，则第一次划分的结果是：）进行快速排序，则第一次划分的结果是：(C)A. (A, C, D, F, H, M, P, Q, R, S, X, Y) B. (A, F, H, C, D, P, M, Q, R, S, Y, X) C. (F, H, C, D, P, A, M, Q, R, S, Y, X) D. (P, A, M, F, H, C, D, Q, S, Y, R, X)29下面是
11、三个关于有向图运算的叙述：下面是三个关于有向图运算的叙述：( D )（1）求有向图结点的拓扑序列，其结果必定是唯一的）求有向图结点的拓扑序列，其结果必定是唯一的（2）求两个指向结点间的最短路径，其结果必定是唯一的）求两个指向结点间的最短路径，其结果必定是唯一的（3）求）求 AOE 网的关键路径，其结果必定是唯一的网的关键路径，其结果必定是唯一的其中哪个（些）是正确的？其中哪个（些）是正确的？A. 只有（只有（1） B. （1）和（）和（2） C. 都正确都正确 D. 都不正都不正确确30若进栈序列为若进栈序列为 a, b, c，则通过入出栈操作可能得到的，则通过入出栈操作可能得到的 a, b,
12、 c 的不的不同排列个数为同排列个数为: ( B )A. 4 B. 5 C. 6 D. 731. 以下关于广义表的叙述中以下关于广义表的叙述中,正确的是：正确的是：( A )A. 广义表是由广义表是由 0 个或多个单元素或子表构成的有限序列个或多个单元素或子表构成的有限序列B. 广义表至少有一个元素是子表广义表至少有一个元素是子表C. 广义表不能递归定义广义表不能递归定义 D) 广义表不能为空表广义表不能为空表32. 排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？时就交换位置。这
13、是哪种排序方法的基本思想？( D )A. 堆排序堆排序 B. 直接插入排序直接插入排序 C. 快速排序快速排序 D. 冒泡排序冒泡排序33 已知一个有向图的邻接矩阵表示，要删除所有从第已知一个有向图的邻接矩阵表示，要删除所有从第 i 个结点发出的个结点发出的边，应该：边，应该：( B)A. 将邻接矩阵的第将邻接矩阵的第 i 行删除行删除 B. 将邻接矩阵的第将邻接矩阵的第 i 行元素全部置为行元素全部置为0C. 将邻接矩阵的第将邻接矩阵的第 i 列删除列删除 D. 将邻接矩阵的第将邻接矩阵的第 i 列元素全部置为列元素全部置为034 有一个含头结点的双向循环链表，头指针为有一个含头结点的双向循
14、环链表，头指针为 head, 则其为空的条件则其为空的条件是：是：( )A. head-priro=NULL B. head-next=NULL C. head-next=head D. head-next- priro=NULL此答案有问题：此答案有问题：Head-next=Head-prior=Head;35. 在顺序表在顺序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 )中，用折半法查找关键中，用折半法查找关键码值码值 11，所需的关键码比较次数为：，所需的关键码比较次数为：( C )A. 2 B. 3 C. 4 D. 536. 以下哪一个不是队列的基本运算？以下哪一个不是队列的基本运算？( A )A. 从队尾插入一个新元素从队尾插入一个新元素 B. 从队列中删除第从队列中删除第 i 个元素个元素C. 判断一个队列是否为空判断
