数据结构课后练习题讲解

1、数据结构习题习题- 3 -.1.1 单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和 运算等的学科。 A .操作对象 A 结构E.计算方法E.关系C.逻辑存储C.运算D.数据映象D.算法2.数据结构被形式地定义为（K , R），其中K是的有限集合, 合。 A 算法 A .操作R是K上的有限集E.数据元素E.映象C.数据操作C.存储D.逻辑结构D.关系3. 在数据结构中，从逻辑上可以把数据结构分成。A 动态结构和静态结构E.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4. 线性表的顺序存储结构是一种的存储结构， 线性表的链式存储结构是一种

2、的存储 结构。A .随机存取B .顺序存取C .索引存取D .散列存取5. 算法分析的目的是，算法分析的两个主要方面是。 A. 找出数据结构的合理性B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进 A. 空间复杂性和时间复杂性C. 可读性和文档性D. 分析算法的易懂性和文档性B. 正确性和简明性D. 数据复杂性和程序复杂性6计算机算法指的是，它必具备输入、输出和等五个特性。 A. 计算方法C. 解决问题的有限运算序列 A. 可行性、可移植性和可扩充性B. 排序方法D. 调度方法B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性7. 线性表的逻辑顺

3、序与存储顺序总是一致的，这种说法。A. 正确B. 不正确8. 线性表若米用链式存储结构时，要求内存中可用存储单兀的地址。A. 必须是连续的B. 部分地址必须是连续的C. 一定是不连续的D. 连续或不连续都可以9. 在以下的叙述中，正确的是。A. 线性表的线性存储结构优于链表存储结构B. 二维数组是其数据兀素为线性表的线性表C. 栈的操作方式是先进先出D. 队列的操作方式是先进后出10. 每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。A. 正确B. 不正确1.2 填空题(将正确的答案填在相应的空中)1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。集合、线性结构、树型结

4、构非线性结构2. 在线性结构中， 第一个结点前驱结点， 其余每个结点有且只有个前驱结点； 最后 一个结点后续结点，其余每个结点有且只有个后续结点。无、一、无、一3. 在树形结构中， 树根结点没有结点， 其余每个结点有且只有个前驱结点， 叶子结 点没有结点，其余每个结点的后续结点可以。前驱、一、后继、零个至多个4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。任意多个5. 线性结构中兀素之间存在关系， 树形结构中兀素之间存在关系， 图形结构中兀素 之间存在关系。一对一、一对多、多对多6. 算法的五个重要特性是7. 下面程序段的时间复杂度是。for (i=0;in;i+)for (j=0;

5、jm;j+)Aij=0;O(m*n)8. 下面程序段的时间复杂度是。i=s=0;while (sn)i+;/*i=i+1*/s+=i;/*s=s+1*/O()9. 下面程序段的时间复杂度是。s=0;for (i=0;i n;i+)for (j=0;j n;j+)s+=Bij;sum=s;0(n 2)10. 下面程序段的时间复杂度是。i=1;while (ilink=P-link:P-link=SB . P-Iink=S-link;S-link=P C. P-link=P;P-link=S ;D . P-link=S;S-link=P ;3、在已知头指针的单链表中，要在其尾部插入一新结点，其算法

6、所需的时间复杂度为( )2A . 0( 1)B. 0( log2n)C. O (n)D. 0 (n )4、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为()A.顺序表C .用尾指针表示的单循环链表5、线性表是()A. 个有限序列，可以为空 C . 一个无限序列，可以为空B. 用头指针表示的单循环链表D.单链表B. 一个有限序列，不能为空D . 一个无限序列，不能为空-5 -6、在n个结点的双链表的某个结点前插入一个结点的时间复杂度是()2A O(n)BO(1)CO(log2n)D O( n2)7、线性表采用链式存储时，结点的地址()A 必须是连续的B 必须是不连续的C 连续与否

7、均可D 必须有相等的间隔8、 在单链表中，增加头结点的目的是()A 使单链表至少有一结点B 标志表中首结点位置C 方便运算的实现D 说明单链表是线性表的链式存储实现9、 带头结点的单链表head为空的判定条件是()A head = NULL ;B head - link = NULL ;Chead - link = head ；D head ! = NULL ；10、 在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度为 ()2A .0( 1)B .0( n)C.O( n )D .0( log?n)11、 下列有关线性表的叙述中，正确的是()A 线性表中的元素之间是线性关系

8、B 线性表中至少有一个元素C 线性表中任何一个元素有且仅有一个直接前趋D .线性表中任何一个元素有且仅有一个直接后继12、在单链表中，存储每个结点需有两个域，一个是数据域，另一个是指针域，它指向该结点的()A 直接前趋B 直接后继 C 开始结点D 终端结点13、将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是()。A nB.2n-1C.2nD.n-114、 链表不具有的特点是()。A 随机访问B不必事先估计存储空间C 插入删除时不需移动元素D所需的空间与线性表成正比15、 在一个单链表中，已知q 所指结点是结点，则执行的操作是()。A s-link=p-link;p-link

9、=s;C p-link=s-link;s-link=p;16、 链表具有的特点是()。A. 可随机访问任一元素C. 不必事先估计存储空间p 所指结点的直接前趋，若在p，q 之间插入 sB q-link=s;s-link=p;D p-link=s;s-link=q;B. 插入、删除需要移动元素D. 存储空间是静态分配的17、 一个顺序表一旦说明，其中可用空间大小()A .已固定B .可以改变C.不能固定D .动态变化18、若某线性表中最常用的操作是取第 i个元素和找第i个元素的前趋元素，则采用()存储方式最节省时间。A 顺序表B 单链表C. 双向链表D .单循环链表19、两个指针P和Q,分别指向

10、单链表的两个元素，P所指元素是Q所指元素的前驱的条- 4 -)。w n)。x。a1, a 2, . a n)件是( )。A P-link=QB Q-link=PCP=QD P-link=Q-link20、下面关于线性表的叙述中，错误的是()。A 线性表采用顺序存储，必须占用一片连续的存储单元B 线性表采用顺序存储，便于进行插入和删除操作C 线性表采用链接存储，不必占用一片连续的存储单元D 线性表采用链接存储，便于进行插入和删除操作21、 在n个结点的顺序表中，算法的时间复杂度是0(1)的操作是(A .访问第i个结点(1 i n)和求第i个结点的直接前趋(2 iB .在第i个结点后插入一个新结点

11、(1 i link;p-link=p-link-link;free(q);B p=p-link;q=p-link;p=q-link;free(q);C. q=p-link_link;p=p_link;free(q);Dp=p-link-link;q=p-link;free(q);二、算法设计题 :1. 写一算法实现：在带头结点单链表 list 中第 i 个元素之前插入元素值注：单链表的存储结构见课本 40 页顶部 void insertList_link(LinkList list,int i,DataType x) int j=0;LinkList p=list;while (p-link

12、& jlink; j+; LinkList s=(LinkList)malloc(sizeof(struct Node);s-info=x;s-link=p-link;p-link=s;2. 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表( 逆置为(a n, a n-1,.,a 1)。注：顺序表的存储结构见课本 32页void reverse_list(PSeqList list)DataType e;for (int i=0,j=list-n-1;ielementi; list-elementi=list-elementj; list-elementj=e;习 题 三 栈和队

13、列一、选择题：1、循环队列是空队列的条件是（）AQ - r = = Q - fB(Q - r + 1 ) %maxsize = Q - fCQ - r = = 0DQ - f = = 02、链栈与顺序栈相比，比较明显的优点是（）A 插入操作更加方便B 删除操作更加方便C .不会出现下溢的情况D .不会出现上溢的情况3、若一个栈的输入序列是1 ,2,3, n,输出序列的第一个元素是n,则第i个输出元素是（）A . n - i B . n -i + 1 C. iD .不确定4、 栈与一般线性表的区别主要在（）A .元素个数B .元素类型C .逻辑结构D .插入、删除元素的位置5、 一个链栈的栈顶指

14、针是top，则执行出栈操作时（栈非空），用x保存被删除结点，则执行（）A x = top; top = top - link ；B x = top - info ；C top = top - link; x = top - info ；D x = top - info; top = top - link ；6、 一个栈的入栈序列是a,b,c,d,e ,则栈的不可能的输出序列是（）。A e,d,c,b,aB d,e,c,b,aC d,c,e,a,bD a,b,c,d,e）数据结构最佳。7、设计一个判别表达式中左、右括号是否配对出现的算法,采用（A 线性表的顺序存储结构C 队列B .栈D 线性表的

15、链式存储结构- 11 -8、容量是 10 的循环队列的队头位置D0q-front 为 2,则队的第一个数据元素的位置是（A2B3C19、循环队列 q 的出队操作是（ ）A . q-f=(q-f+1)%maxsize;B. q-f=q-f+1;C. q-r=(q-r+1)%maxsize;D . q-r=q-r+1;10、 在一个非空链队列中，若f,r分别为队首、队尾指针，则插入s所指结点的操作为()。A . f-link=s; f=sB. r-link=s;r=s;C. s-li nk=r;r=s;D . s-li nk=f;f=s11、 循环队列Q的入队操作应为()。A . Q-r= Q -

16、r+1; Q -qQ -r=x;B . Q -qQ -r+=x;C . Q -r=( Q -r+1)%maxsize; Q -qQ -r=x;D . Q -qQ -r=x; Q -r=( Q -r+1)%maxsize;12、栈和队列都是（）。A .限制存取点的线性结构B .限制存取点的非线性结构C .顺序存储的线性结构D .链式存储的线性结构13、实现递归调用属于（）的应用。A .队列B .栈C.数组D .树二、填空题：1、 循环队列用数组 datam存放其元素值，已知其头、尾指针分别是front和rear,则当前队列中元素的个数是（rear+m-fro nt）%m）。2、 栈顶的位置是随着

17、（入栈、出栈）操作而变化的。3、 假设以S和X分别表示进栈和退栈操作，则对输入序列a, b, c, d, e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为（ bceda）。4、队列的队尾位置随着（入队）而变化。5、在（队列中只有一个元素的情况下）的情况下，链队列的出队操作需要修改尾指针。6、 从栈顶指针为top的链栈中删除一个结点，并将被删除的结点的值保存在x中，其操作步骤为（）;top=top-link;。7、 用数组Am来存放循环队列 Q的元素，且它的头、尾指针分别为 f和r，队列满足条 件（Q-r+1）%m= Q- f,则队列中当前的元素个数为（m-1 ）。8、 顺序栈sta

18、ck存储在数组stack-smax中，对stack进行出栈操作，执行的语句序列 是（stackn -）。9、以下运算实现在循环队列中的初始化操作void in itqueue（PSeqQueue q）q-f=0;（ q-r=0;）;三、算法设计题教材 P115 3 , 7习题四树和二叉树6.1单项选择题(A)(B)(C)(D)2.卜列编码屮属前缀码的是(图 8.7 ) 4棵二叉树(A) 1,01,000,001(B) 1,01,011,010(C) 0,10,110,11(D) 0,1,00,113.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是A. ac

19、bed B. decab C. deabc D.cedba4. 设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 。A . a在b的右方B. a在b的左方C. a是b的祖先D. a是b的子孙5假定在一棵二叉树中，双分支结点数为15,单分支结点数为30个，则叶子结点数为个。A . 15B. 16C. 17D. 476. 按照二叉树的定义，具有3个结点的二叉树有 种。A. 3B. 4C. 5D. 67. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论是正确的。A. 树的先

20、根遍历序列与其对应的二叉树的先序遍历序列相同B. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同- 35 -D.以上都不对8.深度(k=0)为5的二叉树至多有63 个结点。A. 16B.32 C. 31D. 109.树最适合用来表示 。A.有序数据元素C.元素之间具有分支层次关系的数据B.无序数据元素D.元素之间无联系的数据10.设有13个值，用它们组成一棵赫夫曼树，则该赫夫曼树共有A. 13B. 12C. 26D. 25()个结点。6.2 应用题1.有一棵树如图8.12所示，回答下面的问题: 这棵树的根结点是_ K1 ;这棵树的叶子

21、结点是 _ K2,K5,k7,k4_ ;结点k3的度是2; 这棵树的度是_3_; 这棵树的深度是_3_; 结点k3的子女是_ k5,k6_ ;结点k3的父结点是_ k1_;2.深度为k ( k=0 )的完全二叉树至少有_2k个结点。至多有_2k+1-1_个结点, 而下，从左到右次序给结点编号(从0开始)，则编号最小的叶子结点的编号是若按自上k-1。3.结点最少的树为空树_，结点最少的二叉树为空二叉树4. 由如图8.17所示的二叉树, 该二叉树对应的森林是 ？。abcdeg图8.17 一棵二叉树5.已知一棵树如图8.20所示，画出其转换为的一棵二叉树。（2）a: 00111 b: 01c:001

22、0d:100e:000f:11g:00110h:101（3）带权的外部路径长度 WPL= 2716.有一份电文中共使用8个字符：a、b、c、d、e、f、g、h,它们出现的频率是 5, 29, 7,8, 14, 23, 3, 11（ 9 分）（1）试画出对应的哈夫曼树；（2）每个字符的哈夫曼编码；（3）求带权外部路径长度（WPL）。6.3算法设计题：试编写算法，统计二叉树的叶子的个数。其存储结构见课本P134int Cou ntLeaf (PB in TreeNode T)if (!T) return 0;else if (!T-lli nk)& (!T-rli nk)return 1;/对叶子

23、结点计数return Cou ntLeaf( T-lli nk)+Cou ntLeaf( T-rli nk); / Cou ntLeaf6.4证明题：证明：在非空二叉树的第i层上，至多有2,个结点(i 0)。用归纳法证明。归纳基： i=0层时，只有一个根结点：i 0 2=2 =1归纳假设：假设对所有的j层，0=j v2/ gg VJ dist6-0.0. 19,2, 15,0, 29, 5 , 29, 1 , 25,2心V4 dist6=0f0t 19,2, 15,0, 29, 5 , 29, 1 , 25,2结果：V0T V2路径长度：15V0V2T V1路径长度：19V0t V2T V5路

24、径长度：25V0T V2T V5t V3路径长度：29V0T V2T V1t V4路径长度：294.已知AOE网有9个结点：V1,V2,V3,V4,V5,V6,V7,V8, V9,其邻接矩阵如下:(1) 请画出该AOE图。(2) 计算完成整个计划需要的时间。(3) 求出该AOE网的关键路径。OG645OGOGOGOGOGOGOGOGOG1OGOGOGOGOGOGOGOG1OGOGOGOGOGOGOGOGOG2OGOGOGOGOGOGOGOGOG97OGOGOGOGOGOGOGOG4OGOGOGOGOGOGOGOGOG2OGOGOGOGOGOGOGOG4OGOGOGOGOGOGOGOGOG(1)

25、该AOE图为: 各事件的最早、最晚开始时间:123456789ee064577614181le0668701614181各活动的最早、最晚开始时间:权 64511297424e 0006457771614l02366877101614e = ee(i) l = le(j)weight(vi,j)完成整个计划需要18天。关键路径为：(V1, V2, V5, V7, 29)和(V1, V2, V5，V8, V9,)习题九 排序9.1单项选择题1. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是。A. 希尔排序B.起泡排序C.插入排序 _D.选择排序10个最大的元素，最好选用D.基数

26、排序OD.归并排序2. 设有1000个无序的元素，希望用最快的速度挑选出其中前 排序法。A.起泡排序B.快速排序_C.堆排序3. 在待排序的兀素序列基本有序的前提下，效率最咼的排序方法是 A.插入排序B.选择排序C.快速排序4. 一组记录的排序码为(46, 79, 56, 38 , 40, 84),则利用堆排序的方法建立的初始堆为。A. 79, 46, 56, 38, 40, 80_ B. 38, 46, 56, 79,40, 84,C. 84, 79, 56, 46, 40, 38D.84, 56, 79, 40, 46, 385. 一组记录的关键码为(46, 79, 56, 38 , 40

27、, 84),则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 。A. 38 , 40, 46, 56, 79, 84B.40, 38, 46, 79, 56, 84C. 40, 38, 46, 56, 79, 84D.40, 38, 46, 84, 56, 796. 一组记录的排序码为(25, 48, 16 , 35, 79 , 82, 23 , 40, 36, 72),其中含有 5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为。A. 16,25,35,48,23,40,79,82,36,72B. 16,25,35,48,79,82,23,36,40,72C.

28、16,25,48,35,79,82,23,36,40,72D. 16,25,35,48,79,23,36,40,72,827. 排序方法中，从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 。A.希尔排序B.起泡排序C.插入排序D.选择排序8. 排序方法中，从未排序序列中挑选兀素，并将其依次放入已排序序列(初始时为空)的一端的方法，称为。A.希尔排序B.归并排序C.插入排序D.选择排序9. 用某种排序方法对线性表(25 , 84 , 21, 47, 15 , 27, 68 , 35 , 20)进行排序时，元 素序列的变化情况如下：

29、 25, 84, 21, 47, 15, 27, 68, 35, 20 20, 15, 21, 25, 47, 27, 68, 35, 844520242535274768,84 15, 20, 21, 25, 27, 35, 47, 68, 84则所采用的排序方法是。A.选择排序B.希尔排序C.归并排序D.快速排序10. 下述几种排序方法中，平均查找长度最小的是 。A.插入排序B.选择排序_C.快速排序D.归并排序11. 下述几种排序方法中，要求内存量最大的是 。A.插入排序B.选择排序C.快速排序_D.归并排序12快速排序方法在情况下最不利于发挥其长处。A.要排序的数据量太大B.要排序的数

30、据中含有多个相同值C.要排序的数据已基本有序D.要排序的数据个数为奇数9.2填空题(将正确的答案填在相应的空中)1. 在对一组记录(54, 38，96, 23，15，72，60，45, 83)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较_5_o2. 在堆排序，快速排序和归并排序中，若只从存储空间考虑，则应首先选取堆排序方法，其次选取 快速排序_方法，最后选取_归并排序方法；若只从排序结果的稳定 性考虑，则应选取 归并排序_方法；若只从平均情况下排序最快考虑，则应选取快速排序方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取一堆排序方法。3. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有希尔排序、选择排序、快速排序和堆排序 。4. 在在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是一快速排序_，需要内存容量最多的是一基数排序_。5. 在堆排序和快速排序中，若原始记录接近正序或反序，则选用 亠堆排序_，若原始记录无序，则最好选用快速排序_o6. 在插入和选择排序中，若初始数据基本正序，则选用 插入排序_;若初始数据基本反序，则选用选择排序_。7. 对n个元