《数据结构题库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*