《华南理工大学数据结构课程习题集部分答案》由会员分享，可在线阅读，更多相关《华南理工大学数据结构课程习题集部分答案（12页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程习题集 第 1 页 （共 25 页）一、. 选择题 . 1. 算法的计算量的大小称为计算的（ B ）。A效率 B. 复杂性 C. 现实性 D. 难度.2. 算法的时间复杂度取决于（ C ）.A问题的规模 B. 待处理数据的初态 C. A和B D. 难确定.3. 下面关于算法说法错误的是（ D ）A算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的.4从逻辑上可以把数据结构分为（ C ）两大类。A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构.5
2、以下数据结构中，哪一个是线性结构（ D ）？A广义表 B. 二叉树 C. 稀疏矩阵 D. 串.6下述哪一条是顺序存储结构的优点？（ A ）A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示.7下面关于线性表的叙述中，错误的是哪一个？（ B ）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。.8若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。A顺序表 B双链表 C带
3、头结点的双循环链表 D单循环链表.9设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表.10. 链表不具有的特点是（ B ）. A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比.11. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（ D ）。A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4.12. 某堆栈的输入序列为a, b，c ，d,下面的四个
4、序列中，不可能是它的输出序列的是（ D ）。 A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b.13. 用链接方式存储的队列，在进行删除运算时（ D ）。A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改.14. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( D )。 A仅修改队头指针 B. 仅修改队尾指针 C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改.15下面关于串的的叙述中，哪一个是不正确的？（ B ）A串是字符的有限序列 B空
5、串是由空格构成的串C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储.16 串是一种特殊的线性表，其特殊性体现在 ( B )A可以顺序存储 B数据元素是一个字符 C可以链接存储 D数据元素可以是多个字符.17关于空串与空格串，下面说法正确的是( D )。 A空串与空格串是相同的 B空串与空格串长度是相同的 C空格串中存放的都是空格D空串中存放的都是NULL. 18图中有关路径的定义是（ A ）。 A由顶点和相邻顶点序偶构成的边所形成的序列 B由不同顶点所形成的序列C由不同边所形成的序列 D上述定义都不是.19设无向图的顶点个数为n，则该图最多有（ B ）条边。An-1 B
6、n(n-1)/2 C n(n+1)/2 D0 En2.20一个n个顶点的连通无向图，其边的个数至少为（ A ）。An-1 Bn Cn+1 Dnlogn；.21某内排序方法的稳定性是指( D )。 A该排序算法不允许有相同的关键字记录 B该排序算法允许有相同的关键字记录C平均时间为0（n log n）的排序方法 D以上都不对 22如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ D ）方法最快。A起泡排序 B快速排列 CShell排序 D堆排序 E简单选择排序 .23排序趟数与序列的原始状态有关的排序方法是( C )排序法。A插入 B. 选择 C. 冒泡 D. 都不
7、是24下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。( A )A选择排序法 B. 插入排序法 C. 快速排序法 D. 都不是25对序列15，9，7，8，20，-1，4进行排序，进行一趟后数据的排列变为4，9，-1，8，20，7，15；则采用的是（ C ）排序。A. 选择 B. 快速 C. 希尔 D. 冒泡26. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ D ）A5 B6 C7 D827一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ E ）A 250 B 500 C254 D505 E以上答案都不对 28. 有关二叉树
8、下列说法正确的是（ B ）.A二叉树的度为2 B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为2.29二叉树的第I层上最多含有结点数为（ C ）.A2I B 2I-1-1 C 2I-1 D2I -1.30对于有n 个结点的二叉树, 其高度为（ C ）.Anlog2n Blog2n Clog2n|+1 D不确定.31对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( C )次序的遍历实现编号。A先序 B. 中序 C. 后序 D. 从根开始按层次遍历.32. 对N
9、个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A ) A（N+1）/2 B. N/2 C. N D. （1+N）*N /2.33. 对线性表进行二分查找时，要求线性表必须（ B ）A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序.34当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( C ). A必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减.35. 具有12个关键字的有序表，折半查找的平均查找长度（ A ） .A. 3.1 B. 4
10、C. 2.5 D. 5.36. 既希望较快的查找又便于线性表动态变化的查找方法是 ( C ) A顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法查找二、填空题.1. 对于长度为255的表，采用分块查找，每块的最佳长度为_16_。.2. 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为_ n _次；当使用监视哨时，若查找失败，则比较关键字的次数为_n+1 _。.3在有序表A1.12中，采用二分查找算法查等于A12的元素，所比较的元素下标依次为_6.9.11.12_。.4. 在一棵二叉树中，第5层上的结点数最多为 16 个。.5.、n(n0)个结点构成的二叉树，叶结点最多f
11、loor(n+1)/2)个，最少有 1 个。若二叉树有m个叶结点，则度为2的结点有 m-1 个。.6二叉树中某一结点左子树的深度减去右子树的深度称为该结点的平衡因子。.7. 假定一棵二叉树的结点数为18，则它的最小深度为 5 ，最大深度为 16 ；.8. 在一棵二叉树中，度为零的结点的个数为n 0，度为2的结点的个数为 n 2，则有n0= n 2 +1 。.9. 现有按中序遍历二叉树的结果为abc，问有_5_种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是_。.10若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_比较_和记录的_移动_。.11直接插入排序用监视哨的作
12、用是_免去查找过程中每一步都要检测整个表是否查找完毕，提高查找效率。.12. 不受待排序初始序列的影响，时间复杂度为O(N2)的排序算法是_简单选择排序_，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是_直接插入排序_。.13.判断一个无向图是一棵树的条件是_n个定点，n-1条边的无向连通图。.14具有10个顶点的无向图，边的总数最多为_45_。.15若用n表示图中顶点数目，则有_条边的无向图成为完全图。.16空格串是指_由空格字符所组成的字符串_，其长度等于_空格个数_。.17设T和P是两个给定的串，在T中寻找等于P的子串的过程称为_模式匹配，又称P为_模式串_。.
13、18串的两种最基本的存储方式是_顺序储存_、_链式储存_；两个串相等的充分必要条件是_长度相等对应位置字符也相等 _。 .19. 已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是s=(LinkedList)malloc(sizeof(LNode)； s-data=x;s-next=r-next；r-next=s；r=s；。.20.向栈中压入元素的操作是_移动指针和插入。.21.在具有n个单元的循环队列中，队满时共有_n-1_个元素。.22用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_SXSSXSXX_。.23. 单链表是_线性表_的链接存储表示。 .24. 在双链表中，
