《数据结构习题与解析》由会员分享，可在线阅读，更多相关《数据结构习题与解析（19页珍藏版）》请在金锄头文库上搜索。
1、第1-3章习题一、选择题1.若进栈序列为a，b，c，d，进栈过程中可以出栈，则 c 不可能是一个出栈序列。A) a,d,c,b B) b,c,d,a C) c,a,d,b D) c,d,b,a6.设用一维数组A1,n来存储一个栈，令An为栈底，用整型变量T指示当前栈顶位置，AT为栈顶元素。当从栈中弹出一个元素时，变量T将变化为 A 。A) T=T + 1 B) T=T 1 C) T不变 D) T= n7. 一个栈的入栈序列为a，b，c，d，e,则栈不可能的出栈序列是 C 。A) e d c b a B) d e c b a C) d c e a b D) a b c d e8.若语句S的执行时
2、间为O(1),那么下列程序段的时间复杂度为 B 。For(i = 0; i = n ; i+)For(j = 0; j next = P-next-next B) p = P-next; P-next = P-next-next C) delete(P-next) D) p = P-next-next30.在计算递归函数时，如不使用递归过程，则一般情况下必须借助于 A 数据结构。A) 栈 B) 树 C) 双向队列 D) 广义表41.下列叙述中，正确的是 B 。A) 用指针的方式存储一棵有n个结点的二叉树最少需要n+1个指针B) 不使用递归，也可以实现二叉树的前序、中序和后序遍历C) 已知树的前
3、序遍历并不能唯一确定一棵树，因为不知道树的根结点是哪一个D) 任一棵树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间50.以下有关数据结构的叙述，正确的是 C 。A) 线性表的线性存储结构优于链式存储结构 B) 二叉树的第i层上有2i-1个结点，深度为k的二叉树上有2k-1个结点C) 二维数组是其数据元素为线性表的线性表 D) 栈的操作方式是先进先出52.在一个单链表中，若要在指针P所指向的结点之后插入结点q，应执行的操作是 C 。A) P-next=q B) P-next=q; q-next=P-next-next C) q-next = P-next; P-next:=
4、q D)P-next=q; q-next=P-next56.若进栈序列为3,5,7,9,进栈过程中可以出栈，则 B 不可能是一个出栈序列。A) 7,5,3,9 B) 9,5,7,3 C) 9,7,5,3 D) 7,5,9,357.设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈，一个元素出栈后立即进入队列Q，若6个元素出队的顺序是e2,e4,e3,e6,e5,e1,则栈S的容量至少应该是 C 。A) 4 B) 6 C) 3 D) 259.有6个元素按6,5,4,3,2,1的顺序进栈，以下序列中，不合法的出栈序列是 A 。A) 3,4,6,5,2,1 B) 5,4,
5、3,6,1,2 C) 2,3,1,4,5,6 D) 4,5,3,1,2,661.下面关于线性表的叙述中，错误的是 B 。A) 线性表采用顺序存储，必须占用一片连续的存储单元 B) 线性表采用顺序存储，便于进行插入和删除操作C) 线性表采用链式存储，不必占用一片连续的存储单元 D) 线性表采用链式存储，便于插入和删除操作。62.下述 A 是顺序存储方式的优点。A) 存储密度大 B) 插入运算方便 C) 删除运算方便 D) 可方便地用于各种逻辑结构的存储表示64.向顺序栈中压入元素时，是 A 。A) 先移动栈顶指针，后存入元素 B) 先存入元素，后移动栈顶指针 C) 谁先谁后无关紧要 D) 同时进
6、行65.在一个顺序存储的循环队列中，队首指针指向队首元素的 A 。A) 前一个位置 B) 后一个位置 C) 队首元素位置 D) 任意位置67.栈和队列都是 A 。A) 限制存取点的线性结构 B) 限制存取点的非线性结构 C) 顺序存储的线性结构 D) 链式存储的线性结构68.用链表表示线性表的优点是 C 。A) 便于随机存储 B) 花费的存储空间较顺序存储少 C) 便于插入和删除操作 D) 数据元素的物理顺序与逻辑顺序相同69在一个具有n个单元的顺序栈中，假设以地址高端作为栈顶，以top作为栈顶指针，则当做退栈处理时，top的变化为 D 。A) top不变 B) top = 0 C) top
7、= top - 1 D) top = top + 172.以下 B 不是队列的基本运算。A) 从队尾插入一个新元素 B) 从队列中删除第i个元素 C) 判断一个队列是否为空 D) 读取队头元素的值74.在长度为n的顺序表中，向第i个元素(1 = I NEXT=S;REAR=S 。11.从一个长度为N的顺序表中删除第I(1 = I = N)个元素，需要向前移动 N-1 个元素。12.数据结构包括的3个方面的内容是：数据的 逻辑结构 、数据存储结构和数据的运算。13.单链表是 线性表 的链式存储表示。链栈和链队分别是 栈 和 队列 的链式存储表示。14.在具有N个单元、顺序存储的循环队列中，队满时
8、共有 N-1 个元素。15.数据结构即数据的逻辑结构包括 线性结构 、 树型结构 、和 图形结构 3种类型，数据的存储结构即物理结构包括 顺序 、 链接 、 索引 和 散列 4种基本类型。17. 队列 是这样一种线性表，即所有插入和删除操作都在表的两端进行。第4章 数组 习题11.二维数组MI,j的元素是4个字符(每个字符占一个存储单元)组成的串，行下标i的范围从0到4，列下标j的范围从0到5。M按行存储时元素M3,5的起始地址与M按列存储时元素 B 的起始地址相同。A) M2,4 B) M3,4 C) M3,5 D) M4,4二、填空题9.对于一个二维数组A1.m,1.n，若按列为主序存储，
9、则任意一个元素AI,i的相对地址是 (j-1)*n+i-1 。第7章查找相关习题17.有m个结点的霍夫曼树，其结点的个数为 C 。A) 2m B) 2m+1 C) 2m-1 D) 2(m+1)23.二分查找法适用于存储结构为 B 的、按关键字排好序的线性表。A) 顺序存储或链式存储 B) 顺序存储 C) 索引存储 D) 链式存储31.一个序列中有若干个元素，若只想得到其中1个元素之前的部分排序，最好采用 排序。AA) 堆排序 B) 插入排序 C) shell排序 D) 快速排序32.下列有关查找与排序的说法中正确的是 D 。A) 堆排序所需的时间与待排序的记录个数无关 B) 如果某种排序算法是
10、不稳定的，则该方法没有实际应用价值C) 任意一颗二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间 D) 中序遍历二叉树的结点就可以得到排好序的结点序列33.对5个不同的数据进行排序，最少需要比较 B 次。A) 3 B) 4 C) 5 D) 634.长度为12的按关键字排序的查找表采用顺序组织方式，若采用二分查找，则在等概率情况下，查找失败时的ASL值是 B 。A) 37/12 B) 62/13 C) 39/12 D) 49/1335.堆的形状是一棵 C 。A) 二叉排序树 B) 满二叉树 C) 完全二叉树 D) 不是二叉树36.静态查找表与动态查找表的根本区别在于 B 。A) 它们的逻辑结构不一样 B)
