《浙江工商大学数据结构期末复习题2》由会员分享,可在线阅读,更多相关《浙江工商大学数据结构期末复习题2(39页珍藏版)》请在金锄头文库上搜索。
1、1数 据 结 构 习 题 集一、选择题.在一个长度为 n 的顺序表中,向第 i 个元素(1in+1)之前插入一个新元素时,需向后移动 B 个元素。A. n-1 B. n-i+1 C. n-i-1 D. i.在一个具有 n 个单元的顺序栈中,假定以地址低端作为栈底,以 top 作为栈顶指针,则当做退栈处理时,top 变化为 C 。A. top 不变 . top -n C. top top-1 D. top=top+1.向顺序栈中压入元素时,是 A 。A. 先存入元素,后移动栈顶指针 B.先移动栈顶指针,后存入元素.在一个顺序存储的循环队列中,队首指针指向队首元素的 A 。A. 前一个位置 B.
2、后一个位置 C. 队首元素位置 D. 队尾元素位置.若进栈序列为 1,2,3,4,进栈过程中可以出栈,则 C 不可能是一个出栈序列。A. 3,4,2,1 B. 2,4,3,1 C. 1,4,2,3 D. 3,2,1,4.在具有 n 个单元的顺序存储的循环队列中,假定 front 和 rear 分别为队首指针和队尾指针,则判断队空的条件是 C 。A. front= =rear+1 B. front+1= =rear C. front= =rear D. front= =0.在具有 n 个单元的顺序存储的循环队列中,假定 front 和 rear 分别为队首指针和队尾指针,则判断队满的条件是 D
3、。A. rear % n= =front B. (rear-1) % n= =frontC. (rear-1) % n= =rear D. (rear+1) % n= =front.从一个具有 n 个节点的单链表中查找其值等于 x 结点时,在查找成功的情况下,需 平均比较 D 个结点。.在一个单链表中,已知*q 结点是*p 结点的前驱结点,若在*q 和*p 之间插入*s结点, 则执行 C 。A. s-next=p-next; p-next=s; B. p-next=s-next; s-next=p;C. q-next=s; s-next=p; D. p-next=s; s-next=q;10.
4、向一个栈项指针为 hs 的链栈中插入一个*s 结点时,则执行 C 。A. hs-next=s; B. s-next=hs-next; hs-next=s;C. s-next=hs;hs=s; D. s-next=hs; hs=hs-next;11.在一个链队列中,假定 front 和 rear 分别为队首指针和队尾指针,则进行插入*s 结点的操作时应执行 B 。A. front-next=s; front=s; B. rear-next=s; rear=s;C. front=front-next; D. front=rear-next;12.线性表是 A 。A. 一个有限序列,可以为空 B.
5、一个有限序列,不能为空2C. 一个无限序列,可以为空 D. 一个无限序列,不能为空13.对顺序存储的线性表,设其长度为 n,在任何位置上插入或删除操作都是等概率的,删除一个元素时大约要移动表中的 C 个元素。A. n+1 B. n-1 C. (n-1)/2 D. n14.线性表采用链式存储时,其地址 D 。A. 必须是连续的 B. 部分地址必须是连续的C. 一定是不连续的 D. 连续与否均可以15.设单链表中指针 p 指着结点(数据域为 m),指针 f 指着将要插入的新结点(数据域为 x),当 x 插在结点 m 之后时,只要先修改 B 后修改 p-link=f 即可。A. f-link=p;
6、B. f-link=p-link;C. p-link=f-link; D. f=nil;16.在双向链表存储结构中,删除 p 所指的结点时需修改指针 B 。A. (p-rlink) -rlink) -link=p; p-rlink=(p-rlink) -rlink;B. (p-llink) -rlink=p-rlink; (p-rlink) -llink=p-llink;C. p-llink=(p-llink) -llink; (p-llink) -llink) -rlink=p;D. (p-llink) -llink) -rlink=p; p-llink=(p-llink) -llink;1
7、7.在双向链表存储结构中,删除 p 所指的结点的前趋结点(若存在)时需修改指针 A 。A. (p-llink) -llink) -rlink=p; p-llink=(p-llink) -llink;B. (p-rlink) -rlink) -llink=p; p-rlink=(p-rlink) -rlink;C. (p-llink) -rlink=p-rlink; (p-rlink) -llink=p-llink;D. p-llink=(p-llink) -llink; (p-llink) -llink) -rlink=p;18.根据线性表的链式存储结构,每个结点所含指针的个数,链表分为单链表
8、和 B 。A. 循环链表 B. 多重链表 C. 普通链表 D. 无头结点链表19.在数据结构中,与所使用的计算机无关的数据叫 C 结构。A. 存储 B. 物理 C. 逻辑 D. 物理和存储20.二分法查找 A 存储结构。A. 只适用于顺序 B. 只适用于链式 C. 既适用于顺序也适用于链式D. 既不适合于顺序也不适合于链式21.在线性表的链式存储结构中,逻辑上相邻的元素在物理位置上 B 。A. 一定相邻 B. 不一定相邻 C. 有时相邻 23.假定在一棵二叉树中,双分支结点数为 15 个,单分支结点数为 32 个,则叶子结点 数为 B 。 A. 15 B. 16 C. 17 D. 4724.假
9、定一棵二叉树的结点数为 18 个,则它的最小高度 B 。 性质 2A. 4 B. 5 C. 6 D. 1825.在一棵二叉树中第五层上的结点数最多为 C 。 性质 1A. 8 B. 15 C. 16 D. 3226.在一棵具有五层的满二叉树中,结点总数为 A 。 性质 3A. 31 B. 32 C. 33 D. 1627.已知 8 个数据元素为(34、76、45、18、26、54、92、65) ,按照依次插入结点的方法生成一棵二叉排序树后,最后两层上的结点总数为 B 。 不理解?A. 1 B. 2 C. 3 D. 4328.由分别带权为 9、2、5、7 的四个叶子结点构造一棵哈夫曼树,该树的带
10、权路径长度为 C 。 A. 23 B. 37 C. 44 D. 46 为什么不是 46?29.在树中除根结点外,其余结点分成 m (m0) 个 A 的集合 T1,T2,T3.Tm,每个集合又都是树,此时结点 T 称为 Ti 的父结点,Ti 称为 T 的子结点(1im)。A. 互不相交 B. 可以相交 C. 叶结点可以相交 D. 树枝结点可以相交30.下面答案 D 是查找二叉树(又称二叉排序树) 。A. 二叉树中的每个结点的两棵子树的高度差的绝对值不大于B. 二叉树中的每个结点的两棵子树的高度差等于C. 二叉树中的每个结点的两棵子树是有序的D. 二叉树中的每个结点的关键字大于其左子树(如果存在)
11、所有结点的关键字值,且小于其右子树(如果存在)所有结点的关键字值。31.如果结点 A 有三个兄弟,而且 B 是 A 的双亲,则 B 的出度是 B 。A. 3 B. 4 C. 5 D. 132.一个深度为 L 的满 K 叉树有如下性质:第 L 层上的结点都是叶子结点,其余各层上每个结点都有 K 棵非空子树。如果按层次顺序从开始对全部结点编号,编号为 n 的有右兄弟的条件是 B 。A. (n-1) % k= =0 B. (n-1) % k!=0 C. n % k= =0 D. n % k!=033.在完全二叉树中,当 i 为奇数且不等于时,结点 i 的左兄弟是结点 D ,否则没有左兄弟。 A. 2
12、i-1 B. i+1 C. 2i+1 D. i-134.某二叉树 T 有 n 个结点,设按某种遍历顺序对 T 中的每个结点进行编号,编号值为 1,2,n 且有如下性质:T 中任一结点 V,其编号等于左子树上的最小编号减 1,而 V的右子树 的结点中,其最小编号等于 V 左子树上结点的最大编号加 1。这时按 B 编号。A. 中序遍历序列 B. 前序遍历序列 C. 后序遍历序列 D. 层次遍历序列35.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的 B 倍。A. 1/2 B. 1 C. 2 D. 436.对于一个具有 n 个顶点和 e 条边的无向图,若采用邻接表表示,则表头向量的大小 为 A 。 A. n B. n+1 C. n-1 D. n+e37.具有 n 个顶点的无向完全图,边的总数为 D 条。A. n-1 B. n C. n+1 D. n*(n-1)/238.设图 G 有 n 个顶点和 e 条边,当 G 是非孤立顶点的连通图时有 2e=n,故可推得深度优先搜索的时间复杂度为 A 。A. O(e) B. O(n) C. O(ne) D. O(n+e)39.最小代价生成树 D 。A.是唯一的 B.不是唯一的 C.唯一性不确定 D.唯一性与原因的边的权数有关40.在无向图 G 的邻接矩