《数据结构题库3》由会员分享，可在线阅读，更多相关《数据结构题库3（19页珍藏版）》请在金锄头文库上搜索。
1、一、一、 单项选择单项选择1 1 . 下面关于线性表的叙述错误的是（ ）。 A . 线性表采用顺序存储必须占用一片连续的存储空间B . 线性表采用链式存储不必占用一片连续的存储空间C . 线性表采用链式存储便于插入和删除操作的实现D . 线性表采用顺序存储便于插入和删除操作的实现3choose2 2 . 在一个带有头结点的单链表 HL 中，若要向表头插入一个由指针 p 指向的结点，则执行( )。A . HL=p; p-next=HL;B . p-next=HL; HL=p;C . p-next=HL; p=HL; D . p-next=HL-next; HL-next=p3choose3 3
2、. 设栈 S 的初始状态为空，元素 a,b,c,d,e,f 依次通过栈 S，若出栈的顺序为 b,d,c,f,e,a,则 栈 S 的容量至少应该为_。 A . 3B . 4C . 5D . 60choose4 4 . ：假定一个链队的对首和对尾指针分别是 front 和 rear，则判断队空的条件为( )。 A . front=rearB . front!=NULLC . rear!=NULLD . front=NULL3choose5 5 . 在线性表的下列存储结构中，读取元素花 费时间最少的是 A . 单链表B . 双链表C . 循环链表D . 顺序表3choose6 6 . 4、若采用邻接
3、矩阵法存储一个 N 个顶点的 无向图，则该邻接矩阵是一个（） A 上三角矩 阵 B 稀疏矩阵 C 对角矩阵 D 对称矩阵 A . B . C . D . 3choose7 7 . 假定一个顺序循环队列的队首和队尾指针 分别用 front 和 rear 表示，则判断队空的条件 为（） A . front+1= =rearB . rear+1= =frontC . front= =0D . front= =rear3choose8 8 . 假设以行序为主序存储二维数组 A=array1.100，1.100，设每个数据元素占 2 个存储单元，基地址为 10，则 LOC5，5=（ ）。 A . 117
4、5B . 1180C . 1205D . 12100choose9 9 . 某无向图具有 n 个顶点，要连通该无向图 全部顶点至少需要（）条边 A . nB . n+1C . n-1D . n/22choose1010 . 下列关于栈的叙述中，正确的选项是（） A . 在栈中只能删除数据B . 在栈中只能插入数据C . 栈是先进先出的线性表D . 栈是先进后出的线性表3choose1111 . 在一个长度为 n 的顺序线性表中顺序查找 值为 x 的元素时，查找成功时的平均查找长度 （即 x 与元素的平均比较次数，假定查找每个 元素的概率都相等）为 ( ) A . nB . n/2 C . (n
5、+1)/2 D . (n-1)/2E . F . G . H . I . 2choose1212 . 邻接表是图的一种（）。 A . 顺序存储结构B . 链接存储结构C . 索引存储结构D . 散列存储结构1choose1313 . 采用邻接表存储的图，其深度优先遍历类 似于二叉树的（）。 A . 中序遍历B . 先序遍历C . 后序遍历D . 按层次遍历1choose1414 . 数组通常具有的两种基本操作 A . 建立和删除B . 索引和修改C . 查找和修改D . 查找和索引2choose1515 . 下列关于队列的叙述正确的是（） A . 在队列中只能插入数据B . 在队列中只能删除数
6、据C . 队列是先进先出的线性表D . 队列是先进后出的线性表2choose1616 . 具有 65 个结点的完全二叉树的高度为 _。（根的层次号为 1） A . 7B . 8C . 6D . 92choose1717 . 对二叉树从 1 开始进行连续编号，要求每 个结点的编号大于其左右孩子的编号，同一个 结点的左右孩子中，其左孩子的编号小于其右 孩子的编号，则可以采用（）次序的遍历实现 编号 A . 先序B . 中序C . 后序D . 从根开始的的层次遍历2choose1818 . 采用线性链表表示一个向量时，要求占用 的存储空间地址（） A . 必须是连续的B . 部分地址必须是连续的C
7、. 一定是不连续的D . 可连续可不连续3choose1919 . 广义表中的元素分为（ ） A . 原子元素 B . 表元素 C . 原子元素/表元素 D . 任意元 素 A . B . C . D . 2choose2020 . 若元素的入栈顺序为 1，2，3.，n， 如果第 2 个出栈的元素是 n，则输出的第 i(1n- 1，则图必为连通图。 正确 错误 答案：错误 解析： 挑错0judge20 . 在链式存储表中存取表中的数据元素 时，不一定要循链顺序访问。 正确 错误 一、 填空1 . 广义表（a）,a）的表尾。答案：（a） 解析： 挑错（a）blank2 . 设一棵二叉树的前序序列
8、为 ABC，则有种不同的二叉树可以得到这种序列。 答案：5 解析： 挑错5blank3 . 完全二叉树中第 5 层上最少有个结点，最多有个结点。 答案：1，16 解析： 挑错1*16blank4 . 任意一个非空广义表的表头可以是原子元素，也可以是，而表尾必定是。 答案：子表，子表 解析： 挑错子表*子表blank5 . 在一棵二叉树中，第 5 层上的结点数最多为. 答案：16 解析： 挑错16blank6 . 假定一棵树的广义表表示为 A（C，D（E，F，G），H（I，J），则树中所含的结点数为个，树的深度为，树的度为答案：9，3，3 解析： 挑错9*3*3blank7 . 具有 n（n-1
9、）条弧的有向图成为答案：有向完全图 解析： 挑错有向完全图blank8 . 设哈夫曼树中共有 99 个结点，则该树中有个叶子结点；若采用二叉链表作为存储结构，则该树中有个空指针域。 答案：50，51 解析： 挑错50*51blank9 . 设一棵二叉树的前序遍历序列和中序遍 历序列均为 ABC，则该二叉树的后序遍历序列为。 答案：， 解析： CBA 挑错*blank10 . 当栈中元素为 n 个，作进栈运算时发 生上溢，则说明该栈的最大容量为。 答案：n 解析： 挑错nblank11 . 求具有最小带权外部路径长度的扩充二叉树的算法称为算法，对于给出的一组权 w=10，12，16,21,30,
10、通过该 算法求出的扩充二叉树的带权外路径长度是. 答案：哈夫曼，200 解析： 挑错哈夫曼*200blank12 . 是由零个或多个字符组成的有序数列。 答案：串 解析： 挑错串blank13 . 设一棵二叉树的中序遍历序列为 BDCA，后序遍历序列为 DBAC，则这棵二叉树的前序序列为。 答案：CBDA 解析： 挑错CBDAblank14 . 把数据存储到计算机中，并具体体现数据之间的逻辑结构称为存储结构。 答案：物理 解析： 挑错物理blank15 . 广义表(a),a)的表头是，表尾是。 答案：(a)，(a) 解析： 挑错(a)*(a)blank16 . 在数据结构中，用一组地址连续的存
11、 储单元一次存储数据元素的方式是结构。 答案：顺序存储 解析： 挑错顺序存储blank17 . 根据初始关键字序列 (19，22，01，38，10)建立的二叉排序树的高度为答案：3 解析： 挑错3blank18 . 含 n 个顶点的无向连通图中至少含有条边。 答案：n-1 解析： 挑错n-1blank19 . 称算法的时间复杂度为 O(f(n)，其含义是指算法的执行时间和的数量级相同。 答案：f(n) 解析： 挑错f(n)blank20 . 设一棵完全二叉树有 128 个结点，则该完全二叉树的深度为，有个叶子结点一、 单项选择1 . 若非空二叉树的前序序列与后序序列的 次序正好相反，则该二叉树
12、一定是（）的二 叉树 A . 空或仅有一个结点B . 其分支结点无左子树C . 其分支结点无右子树D . 其分支结点的度都为 1答案：D 解析： 挑错3choose2 . 在一个单链表中，已知 q 所指结点是 p 所指结点的前驱结点，若在 p 和 q 之间插入 s 结点，则执行： A . s-link=p-link;p-link=s;B . p-link=s-link;s-link=p;C . q-link=s; s-link=p;D . p-link=s; s-link=q答案：C 解析： 已知 q-link=p，那么插入应该执行 s-link=p;q-link=s; 选 C。 挑错2cho
13、ose3 . 在初始为空的栈中一次插入元素 f，e，d，c，b，a 以后，连续进行了三次删 除操作，此时栈顶元素是 A . dB . cC . bD . e答案：A 解析： 挑错0choose4 . 对顺序表上的插入、删除算法的时间复 杂性分析来说，通常以（ ）为标准操作 A . 条件判断 B . 结点移动C . 算术表达式D . 赋值语句答案：B 解析： 挑错1choose5 . 对稀疏矩阵进行压缩存储目的是（ ）。A . 便于进行矩阵运算 B . 便于输入和输出 C . 节省存储空间 D . 降低运算的时间答案：C 解析： 挑错2choose6 . 8. 从一个栈顶指针为 HS 的链栈中删
14、除 一个结点时，用 x 保存被删除结点的值，则 执行_ A . x = HS; HS = HS-next;B . x = HS-data;C . HS = HS-next; x = HS-data;D . x = HS-data; HS = HS-next答案：D 解析： D 挑错3choose7 . 设树 T 的度为 4，其中度为 1，2，3，4 的结点个数分别为 4，2，1，1.则 T 中的叶 子节点数为 A . 5B . 6C . 7D . 8答案：D 解析： 树中各节点的分支总数为： 4*1+2*2+1*3+4*1=15；树中的总结点数为 15+1=16；非叶子节点总数为：4+2+1+
15、1=8. 因此，叶子节点数为 16-8=8. 挑错3choose8 . 设按照从上到下、从左到右的顺序从 1 开始对完全二叉树进行顺序编号，则编号为 i 结点的左孩子结点的编号为_ A . 2i+1B . 2iC . i/2D . 2i-1答案：B 解析： 挑错1choose9 . 若带头结点的单链表的头指针为 head， 则判断链表是否为空的条件是( ) A . head=NULLB . head-next=NULLC . head!=NULLD . head-next!=head答案：B 解析： 挑错1choose10 . 设有 6 个结点的无向图，该图至少应 有( )条边才能确保是一个连
16、通图。 A . 5B . 6C . 7D . 8答案：A 解析： 挑错0choose二、 多项选择11 . 线性表的特点正确的（） A . 存在唯一的一个被称作”第一个“的数据元素。B . 不存在唯一的一个被称作”第一个“的数据元素。C . 存在唯一的一个被称作”最后一个“的数据元素。D . 不存在唯一的一个被称作”最后一个“的数据元素。 答案：A，C 解析： 挑错0*2mulchoose12 . 下列说法是正确的是： A . 在线性表中数据元素之间仅有线性关系B . 在图形结构中节点之间的关系可以是任意的C . 简单路径，序列中顶点可以重复出现D . 邻接表是图的一种链式存储结构答案：A，B，D 解析： 挑错0*1*
