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