当前位置：文档之家 › 华南理工大学《数据结构》课程习题集部分答案

华南理工大学《数据结构》课程习题集部分答案

  • 格式：docx
  • 大小：43.05 KB
  • 文档页数：12

《数据结构》课程习题集第 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．以下数据结构中，哪一个是线性结构（D）？A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串.6．下述哪一条是顺序存储结构的优点？（A）A．存储密度大 B．插入运算方便C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示.7．下面关于线性表的叙述中，错误的是哪一个？（B）A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

.8．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 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 4B. 4 5 1 3 2C. 4 3 1 2 5D. 3 2 15 4.12. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（D）。

A. a，c，b，dB. b, c，d，aC. c, d，b, aD. d, c，a，b .13. 用链接方式存储的队列，在进行删除运算时（D）。

A. 仅修改头指针B. 仅修改尾指针C. 头、尾指针都要修改D. 头、尾指针可能都要修改.14. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( D )。

A．仅修改队头指针 B. 仅修改队尾指针 C. 队头、队尾指针都要修改D. 队头,队尾指针都可能要修改.15．下面关于串的的叙述中，哪一个是不正确的？（B）A．串是字符的有限序列 B．空串是由空格构成的串C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储.16．串是一种特殊的线性表，其特殊性体现在( B)A．可以顺序存储B．数据元素是一个字符C．可以链接存储D．数据元素可以是多个字符.17．关于空串与空格串，下面说法正确的是( D)。

A．空串与空格串是相同的B．空串与空格串长度是相同的C．空格串中存放的都是空格D．空串中存放的都是NULL. 18．图中有关路径的定义是（A）。

A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列C．由不同边所形成的序列 D．上述定义都不是.19．设无向图的顶点个数为n，则该图最多有（B）条边。

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 .20．一个n个顶点的连通无向图，其边的个数至少为（A）。

A．n-1 B．n C．n+1 D．nlogn；.21．某内排序方法的稳定性是指( D )。

A．该排序算法不允许有相同的关键字记录B．该排序算法允许有相同的关键字记录C．平均时间为0（n log n）的排序方法D．以上都不对22．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（D）方法最快。

A．起泡排序 B．快速排列 C．Shell排序 D．堆排序 E．简单选择排序.23．排序趟数与序列的原始状态有关的排序方法是( C )排序法。

A．插入 B. 选择 C. 冒泡 D. 都不是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）A．5 B．6 C．7 D．827．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（E）A． 250 B． 500 C．254 D．505 E．以上答案都不对28. 有关二叉树下列说法正确的是（B）.A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2.29．二叉树的第I层上最多含有结点数为（C）.A．2I B． 2I-1-1 C． 2I-1 D．2I -1.30．对于有n 个结点的二叉树, 其高度为（C）.A．nlog2n B．log2n C．⎣log2n⎦|+1 D．不确定.31．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( C )次序的遍历实现编号。

A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历.32. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( 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.1B. 4C. 2.5D. 5.36. 既希望较快的查找又便于线性表动态变化的查找方法是 ( C ) A．顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法查找二、填空题.1. 对于长度为255的表，采用分块查找，每块的最佳长度为____16______。

.2. 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为__ n __次；当使用监视哨时，若查找失败，则比较关键字的次数为__n+1 __。

.3．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为__6.9.11.12____。

.4.. 在一棵二叉树中，第5层上的结点数最多为16个。

.5.、n(n>0)个结点构成的二叉树，叶结点最多floor((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. 不受待排序初始序列的影响，时间复杂度为O(N2)的排序算法是_简单选择排序_，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是_直接插入排序_。

.13.判断一个无向图是一棵树的条件是_n个定点，n-1条边的无向连通图。

.14．具有10个顶点的无向图，边的总数最多为_45_。

.15．若用n表示图中顶点数目，则有_______条边的无向图成为完全图。

.16．空格串是指_由空格字符所组成的字符串_，其长度等于_空格个数_。

.17．设T和P是两个给定的串，在T中寻找等于P的子串的过程称为_模式匹配，又称P为_模式串_。

.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. 在双链表中，每个结点有两个指针域，一个指向_前驱_，另一个指向_后继_。

.25．链接存储的特点是利用_指针_来表示数据元素之间的逻辑关系。

.26.顺序存储结构是通过_相邻位置_表示元素之间的关系的;链式存储结构是通过_指针_表示元素之间的关系的。

.27．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_（n-1）/2_。

.28．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_单链表_和_多重链表_；而又根据指针的连接方式，链表又可分成_动态链表_和_静态链表_。

.29．数据的物理结构包括_顺序储存_的表示和_链式储存_的表示。

.30．抽象数据类型的定义仅取决于它的一组_逻辑特性_，而与_在计算机内部如何表示和实现_无关，即不论其内部结构如何变化，只要它的_数学特性_不变，都不影响其外部使用。

.31．数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度.32. 数据结构是研讨数据的_逻辑结构和_物理结构，以及它们之间的相互关系，并对与这种结构定义相应的操作，设计出相应的算法_。

合集下载

数据结构习题(有答案)(精选文档)

数据结构习题(有答案)(精选文档)

数据结构习题(有答案) 第１章绪1。

1 有下列几种二元组表示的数据结构，试画出它们分别对应的图形表示，并指出它们分别属于何种结构。

（1) A= （ D,R )，其中,D = { ａ1，ａ2,ａ３，a４}, R={ ｝(2） B= （ D,R ),其中，D = ｛ a，ｂ,c,d，ｅ｝, R＝｛ (a,ｂ),(ｂ，c），（c，d）,(d，e）｝（3) C= （ D，Ｒ），其中，D = ｛ a，b，c,d，ｅ,f，g}, R=｛（d,b)，(d,g），(1）集合(2) 线性表a b c d e(３）树fgabcde(4）图1453621 / 48·····谢阅。

（b,a),（ｂ，c),（ｇ，e），（e，f)}（4) K= （ D,R ），其中,Ｄ= ｛ 1，2，3,4，5，６}, R=｛〈1，2＞,〈2，3＞，〈2，4＞，<3，４>，<３，５>，＜3，6>,<4,5〉,〈４，6〉}1.２设n为正整数,求下列各程序段中的下划线语句的执行次数。

（1) i=1；ｋ=0ｗhiｌe(i 〈=n-1){k+=１0＊i ；i＋+;（2) fｏr （ｉnt i=１；ｉ＜=n； i+＋）ｆor （int j＝１; j〈=ｎ; ｊ+＋)｛ｃ［i］［j］=0；解:(１) n－1（2) ∑∑∑====ninjnkn111312 / 48·····谢阅。

｝ﻩ fｏr(inｔk=1； k〈=n; ｋ＋＋）c[ｉ]［j］=c[i］［j]+a[ｉ］［k]*ｂ［k］[j］｝（3) x=０；ｙ=０;for （int ｉ＝1; i＜=n; i++)fｏr (inｔ j=1; j<＝ｉ; ｊ+＋)for (inｔk=1; k〈＝ｊ; k ＋＋）(３）62)1)(nn(n21)(216)12)(1(2121212)1(1112111111++=+•+++•=+=+==∑∑∑∑∑∑∑∑========nnnnniii ijnininiijjkniijni3 / 48·····谢阅。

数据结构课后习题答案1--7

数据结构课后习题答案1--7

习题11．解释以下概念：逻辑结构，存储结构，操作，数据结构，数据结构的表示，数据结构的实现，抽象数据类型，算法，算法的时间代价，算法的空间代价，大O 表示法。

2．理解以下关系：算法与数据结构的关系；数据结构与抽象数据类型的关系；算法和数据结构与问题求解的关系。

3. 写出下列程序段的平均情况下的时间代价O表示式。

(1) a=b+c;d=a+e(2) sum=0;for (i=0;i<3;i++)for (j=0;j<n;j++)sum++;(3) x=n;y=0;while (x>=(y+1)*(y+1))y++;(4) s=0;if(even(n))for (i=0;i<n;i++)sum++;elses=s+n;(5) x=66;n=200;while (n>0){if(x>lO0){ x=x-10;n=n-1;}elsex=x+1;}4．对于给定的n个元素，可以构造出的逻辑结构有，，，四种。

5.按增长率由小到大的顺序排列下列各函数：2100, (32)n, (23)n, (43)n, n n, n32, n!, n, log2n, n/log2n习题22.1已知L是无头结点的单链表，且p结点既不是第一个结点，也不是最后一个结点，试从下列提供的语句中选出合适的语句序列：(1)在p结点之后插入s结点：(2)在p结点之前插入s结点：(3)在单链表L首插入s结点：(4)在单链表L后插入s结点：提供的语句：①p->next＝s；②p->next＝p->next->next；③p->next=s->next；④s->next=p->next；⑤s->next＝L；⑥s->next=p；⑦s->next=NULL；⑧q＝p；⑨while(p->next!=q)p=p->next；⑩while(p->next!=NULL)p=p->next；⑾p=q；⑿p=L；⒀L＝s；⒁L＝p；2.2已知p结点是某双向链表的中间结点，试从下列提供的语句中选出合适的语句序列。

数据结构课后习题标准答案

数据结构课后习题标准答案

数据结构课后习题标准答案————————————————————————————————作者：————————————————————————————————日期：7_1对于图题7.1（P235）的无向图，给出：（1）表示该图的邻接矩阵。

（2）表示该图的邻接表。

（3）图中每个顶点的度。

解：（1）邻接矩阵：0111000100110010010101110111010100100110010001110（2）邻接表：1：2----3----4----NULL;2: 1----4----5----NULL;3: 1----4----6----NULL;4: 1----2----3----5----6----7----NULL;5: 2----4----7----NULL;6: 3----4----7----NULL;7: 4----5----6----NULL;（3）图中每个顶点的度分别为：3，3，3，6，3，3，3。

7_2对于图题7.1的无向图，给出：（1）从顶点1出发，按深度优先搜索法遍历图时所得到的顶点序（2）从顶点1出发，按广度优先法搜索法遍历图时所得到的顶点序列。

（1）DFS法：存储结构：本题采用邻接表作为图的存储结构，邻接表中的各个链表的结点形式由类型L_NODE规定，而各个链表的头指针存放在数组head中。

数组e中的元素e[0],e[1],…..,e[m-1]给出图中的m条边，e中结点形式由类型E_NODE规定。

visit[i]数组用来表示顶点i是否被访问过。

遍历前置visit各元素为0，若顶点i被访问过,则置visit[i]为1.算法分析：首先访问出发顶点v.接着，选择一个与v相邻接且未被访问过的的顶点w访问之，再从w 开始进行深度优先搜索。

每当到达一个其所有相邻接的顶点都被访问过的顶点，就从最后访问的顶点开始，依次退回到尚有邻接顶点未曾访问过的顶点u,并从u开始进行深度优先搜索。

这个过程进行到所有顶点都被访问过，或从任何一个已访问过的顶点出发，再也无法到达未曾访问过的顶点，则搜索过程就结束。

数据结构的课后习题答案

数据结构的课后习题答案

M L= P;
(3) D
(4) D
(5) D
(6) A
7试分别以不同的存储结构实现单线表的就地逆置算法，即在原表的存储空间将线性表（a1,a2,…,an）逆置为(an,an-1,…,a1)。
【解答】
（1）用一维数组作为存储结构
void invert(SeqList *L, int *num)
{ int j;
p->next=pa; /*A的长度大于B的长度*/
if(pb!=NULL)
p->next=pb; /*B的长度大于A的长度*/ C=A; Return(C);
}
实习题
约瑟夫环问题
约瑟夫问题的一种描述为：编号1,2,…,n的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个报数上限值m,从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。
ElemType tmp;
for(j=0;j<=(*num-1)/2;j++)
{ tmp=L[j];
L[j]=L[*num-j-1]; L[*num-j-1]=tmp;}
}
（2）用单链表作为存储结构
void invert(LinkList L)
{
Node *p, *q, *r;
if(L->next ==NULL) return; /*链表为空*/
明原因（即写出以“S”表示进栈、“X”表示出栈的栈序列操作）。