下载文档原格式
第三章栈、队列和数组一、名词解释：1.栈、栈顶、栈底、栈顶元素、空栈2.顺序栈3.链栈4.递归5.队列、队尾、队头6.顺序队7.循环队8.队满9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上（下）三角矩阵二、填空题：1.栈修改的原则是_________或称________，因此，栈又称为________线性表。
在栈顶进行插入运算，被称为________或________，在栈顶进行删除运算，被称为________或________。
2.栈的基本运算至少应包括________、________、________、________、________五种。
3.对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“________”。
4.对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。
5.一般地，栈和线性表类似有两种实现方法，即________实现和________实现。
6.top=0表示________，此时作退栈运算，则产生“________”；top=sqstack_maxsize-1表示________，此时作进栈运算，则产生“________”。
7.以下运算实现在顺序栈上的初始化，请在________处用适当的句子予以填充。
int InitStack(SqStackTp *sq){ ________;return(1);}8.以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。
Int Push(SqStackTp *sq,DataType x){ if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);}else{________________:________________=x;return(1);}}9.以下运算实现在顺序栈上的退栈，请在________________用适当句子予以填充。
2021年小学信息技术教师专业技能数据结构练习题及参考答案（三）1.每个结点只存储一个数据元素，存储结点存放在连续的存储空间，该存储方式是（ A ）存储方式。
A．顺序 B. 链式 C. 索引 D. 散列2.对于顺序表的优缺点，下面说法错误的是（ C ）。
A．无需为表示节点间的逻辑关系而增加额外的存储空间。
B．可以方便的随机存取表中的任一结点。
C．删除和插入运算较方便。
D.由于顺序表要求占用连续的空间，存储分配只能预先进行（静态分配）。
3.下面( B )的时间复杂性最好，即执行时间最短。
A.O（n）B.O（log2n）C.O（nlog2n）D.O（n2）4.在带头结点的单链表h中，若要向表头插入一个由指针p所指向的结点，则执行（ D ）。
A. h=p, p->next=hB. p->next=h, h=pC. p->next=h, p=hD. p->next=h->next, h->next=p5.与线性表的链接存储相符的特性是( A )。
A．插入和删除操作灵活B．可随机访C．存储空间静态分配D．不需另外开辟空间来保存元素间的关系6.用某种排序方法对序列（25，84，21，47，15，27，68，35，20）进行排序，记录序列的变化情况如下： 25 84 21 47 15 27 68 35 20 20 15 21 25 4727 68 35 84 15 20 21 25 35 27 47 68 84 15 20 21 25 27 35 47 68 84 则采用的排序方法是（ C ）。
A．直接选择排序 B. 冒泡排序 C. 快速排序 D. 二路归并排序7.下列关于线性表的叙述中，不正确的是( C )。
A．线性表是n个结点的有穷序列B．线性表可以为空表C．线性表的每一个结点有且仅有一个前趋和一个后继D．线性表结点间的逻辑关系是1:1的联系8.将长度为m的单链表链接在长度为n的单链表之后的算法的时间复杂度为( B )。
数据结构参考答案及评分标准一、选择题（2分*15=30分）1．A 2．C 3．B 4．D 5．B 6．D7．D8．D9．B10. B11.C12.C13.A14.A15.C二、填空题（每空2分,共20分）1．(n-1)/22．栈3．head(tail(tail(head(tail(head(A))))))4．2k-1、2k-15．n-16．n、n+17．直接插入排序8．第I列非零元素个数三、综合题（40分）1．（1）查找29和90都需要4次比较才能成功（2分）（2）若采用顺序查找，分别需要5次和10次才能查找成功（2分）（3）(4分)2．（1）（4分）（2）GDACBFE（4分）3．（图4哈夫曼编码为：概率为0.23的字符编码为：00概率为0.11的字符编码为：010概率为0.05的字符编码为：0110概率为0.03的字符编码为：0111概率为0.29的字符编码为：10概率为0.14的字符编码为：110概率为0.07的字符编码为：1110概率为0.08的字符编码为：11114．（1）（4分）（1）每个事件的最早开始时间Ve和最晚开始时间Vl（2）每个活动的最早开始时间e（）和最晚开始时间l（）（4分）（3）此工程最早完成时间为43。
（2分）（4）关键路径为<1,3><3,2><2,5><5,6>（2分）四、算法题（共10分，根据完成情况酌情给分）V oid inorderList(LinkList *&L, ElemType x)/*L是一个从小到大有序排列的单链表，表头指针为L*/{LinkList *s,*p,*q;S=(LinkList *)maloc(sizeof(LinkList));S－>data=x;S－>next=NULL;If(L= =NULL || x<L－>data){ S－>next=L;L=s;}else{q=L;p=p－>next;while (p!=NULL && x>p－>data) {q=p;p= p－>next;}s－>next=p;q－>next=s;}}。
第三章栈、队列和数组一、名词解释：1.栈、栈顶、栈底、栈顶元素、空栈2.顺序栈3.链栈4.递归5.队列、队尾、队头6.顺序队7.循环队8.队满9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上（下）三角矩阵二、填空题：1.栈修改的原则是_________或称________，因此，栈又称为________线性表。
在栈顶进行插入运算，被称为________或________，在栈顶进行删除运算，被称为________或________。
2.栈的基本运算至少应包括________、________、________、________、________五种。
3.对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“________”。
4.对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。
5.一般地，栈和线性表类似有两种实现方法，即________实现和________实现。
6.top=0表示________，此时作退栈运算，则产生“________”；top=sqstack_maxsize-1表示________，此时作进栈运算，则产生“________”。
7.以下运算实现在顺序栈上的初始化，请在________处用适当的句子予以填充。
int InitStack(SqStackTp *sq){ ________;return(1);}8.以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。
Int Push(SqStackTp *sq,DataType x){ if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);}else{________________:________________=x;return(1);}}9.以下运算实现在顺序栈上的退栈，请在________________用适当句子予以填充。
一、单选题：C D B A A A C B C C二、填空题：n n/2 7 n2+2n3+…..+(m-1)n m+1 只有根节点的二叉树逆序1000000 2000 最大24三、应用题1、参考答案A B C D E F G H10 001 11 0001 0110 0111 010 00002、0 1 2 3 4 5 6 7 8 9 1012 100 25 16 17 18 8 40 7(1) (2) (1) (1) (1) (1) (1) （3）(4)搜索成功的平均搜索长度为ASL succ = 19(1 + 2+ 1 + 1 + 1 + 1 +1+ 3+ 4) = 533、4、最小生成树或最小生成树不唯一，有两棵，如上所示。
5、四、算法设计题1、void Bucketsort ( ElementType A[ ], int N )12 45635 6 11 1618 1 24563{int Counter[ 3 ];int i, j, k;for ( i = 0; i < 3; i++ )Counter[ i ] = 0;for ( i = 0, i < N; i++ ) {if ( A[ i ] == false )Counter[ 0 ] ++;elseif ( A[ i ] == maybe )Counter[ 1 ] ++;elseCounter[ 2 ] ++;}k = 0;for ( i = 0; i < Counter[ 0 ]; i++ )A[ i ] = false;k += Counter[ 0 ];for ( i = 0; i < Counter[ 1 ]; i++ )A[ k+i ] = maybe;k += Counter[ 1 ];for ( i = 0; i < Counter[ 2 ]; i++ )A[ k+i ] = true;}2、int BinaryTree<Type> :: leaf ( BinTreeNode<Type> * ptr ) {if ( ptr == NULL ) return 0;else if ( ptr->leftChild == NULL && ptr->rightChild == NULL ) return 1;else return leaf ( ptr->leftChild ) + leaf ( ptr->rightChild );}3、int max=0;int Find_All_Path(Graph *G,int S,int T, int K)/{G->setMark(S,VIEITED);if(S==T) //找到了一条简单路径{ if (max<K) max=K; return(max); }elsefor(int p=G->first(S);p<G->n();p=G->next(S,p){if(G->getMark(p)==UNVISITED) Find_All_Path(G,p,T,k+1); //继续寻找}G->setMark(S,UNVIEITED); }。
《数据结构（C语言版第2版）》（严蔚敏著）第三章练习题答案第3章栈和队列1．选择题（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。
A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1答案：C解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。
（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。
A．i B．n-i C．n-i+1 D．不确定答案：C解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，…，n，而输出序列的第一个元素为n，说明1，2，3，…，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，…，pi=n-i+1。
（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。
A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n答案：D解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（n+r-f)%n。
（4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。
A．x=top->data;top=top->link；B．top=top->link;x=top->link；C．x=top;top=top->link；D．x=top->link；答案：A解释：x=top->data将结点的值保存到x中，top=top->link栈顶指针指向栈顶下一结点，即摘除栈顶结点。
数据结构习题及答案（3）第九章排序⼀、选择题1.在所有排序⽅法中，关键字⽐较的次数与记录得初始排列次序⽆关的是（）（A）希尔排序（B）起泡排序（C）插⼊排序（D）选择排序参考答案：D2.设有1000个⽆序的元素,希望⽤最快的速度挑选出其中前10个最⼤的元素,最好（）排序法。
（A）起泡排序（B）快速排序（C）堆排序（D）基数排序参考答案：C3.在待排序的元素序列基本有序的前提下,效率最⾼的排序⽅法是（）（A）插⼊排序（B）选择排序（C）快速排序（D）归并排序参考答案：A4.⼀组记录的排序码为(46,79,56,38,40,84),则利⽤堆排序的⽅法建⽴的初始推为（）。
（A）79,46,56,38,40,80 （B）84,79,56,38,40,46（C）84,79,56,46,40,38 （D）84,56,79,40,46,38参考答案：B5.⼀组记录的关键码为(46,79,56,38,40,84),则利⽤快速排序的⽅法,以第⼀个记录为基准得到的⼀次划分结果为（）。
（A）38,40,46,56,79,84（B）40,38,46,79,56,84（C）40,38,46,56,79,84（D）40,38,46,84,56,79参考答案：C6.⼀组记录的排序码为(25,48,16,35,79,82,23,40,36,72),其中含有5个长度为2的有序表,按归并排序的⽅法对该序列进⾏⼀趟归并后的结果为（）。
（A）16,25,35,48,23,40,79,82,36,72（B）16,25,35,48,79,82,23,36,40,72（C）16,25,48,35,79,82,23,36,40,72（D）16,25,35,48,79,23,36,40,72,82参考答案：A7.排序⽅法中,从未排序序列中依次取出元素与⼰排序序列(初始时为空)中的元素进⾏⽐较,将其放⼊⼰排序序列的正确位置上的⽅法,称为（）（A）希尔排序（B）起泡排序（C）插⼊排序（D）选择排序参考答案：C8.排序⽅法中,从未排序序列中挑选元素并将其依次放⼊⼰排序序列(初始为空)的⼀端的⽅法,称为（）（A）希尔排序（B）归并排序（C）插⼊排序（D）选择排序参考答案：D9.⽤某种排序⽅法对线性表(25,84,21,47,15,27,68,35,20)进⾏排序时,元素序列的变化情况如下:(1)25,84,21,47,15,27,68,35,20 (2)20,15,21,25,47,27,68,35,84(3)15,20,21,25,35,27,47,68,84 (4)15,20,21,25,27,35,47,68,845则所采⽤的排序⽅法是（）。
2021数据结构作业3 树与二叉树参考答案2021数据结构作业3-树与二叉树-参考答案作业3.树非编程作业：1．请分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
参考答案：具备3个结点的树：具有3个结点的二叉树：2．未知二叉树的先序结点序列就是eabdcfhgikj，中序结点序列就是abcdefghijk，请构造二叉树，并写出其层次遍历序列和后序遍历序列。
参考答案：eaf层次：eafbhdgickjbh后序---cdbagjkihfedcgikj3．将下图所示的森林转换成一棵二叉树。
agkbcdhijlef参考答案：转换成的二叉树为：abcdghikljef4．将下图所示的二叉树还原成树或森林。
abcdlfeghmknji参考答案：切换为森林：aegbcdfhijlmnk5．假设用于通信的电文由7个字母组成{a,b,c,d,e,f,g}，字母在电文中出现的频率分别为0.17、0.09、0.12、0.06、0.32、0.03、0.21。
精义这7个字母设计哈夫曼编码，并排序其有向路径长度wpl。
参考答案：哈夫曼树为：0.1810.39g0.610.210.290.32e0.17a0.090.09b0.12wpl=4*(0.03+0.06)+3*(0.12+0.17+0.09)+2*(0.32+0.21)=2.56a:101b:001c:100d:0001e: 11f:0000g:01编程作业：二叉树采用二叉链表存储，试设计算法实现：1．createbt(bitree&t)：从键盘输入二叉树的先序结点序列字符串（以”#”代表空结点），创建其二叉链表；如输入：ab#d##ce#f###则建立如下图所示二叉树的二叉链表2．exchangebt(bitreet):设计递归算法实现二叉树中所有结点的左右孩子交换；3．countleaf(bitreet,telemtypex,int&count):统计数据以值x的结点为根的子树中叶子结点的数目；4．dispbitree(bitreet,intlevel):按树状打印二叉树。
数据结构练习(三)参考一、选择题1•顺序查找法适合于存储结构为________ 的线性表A) 哈希存储| B )顺序存储或链式存储C)压缩存储 D )索引存储2. —个长度为100的已排好序的表，用二分查找法进行查找，若查找不成功，至少比较__________ 。
A) 9 B)8 C)7 |D) 63. 采用顺序查找方法查找长度为n的线性表时，平均比较次数为_________ 。
A) n B) n/2 G 5+1)/2 D) (n-1 ) /24. 对线性表进行折半查找时，要求线性表必须________ 。
A )以顺序方式存储以顺序方式存储，且结点按关键字有序排列C )以链表方式存储D )以链表方式存储，且结点按关键字有序排列5. 采用二分查找法查找长度为n的线性表时，每个元素的平均查找长度为 ______ 。
A) O (n2) B) O (nlog2n) C) O (n) D) O (log2n)6. 有一个长度为12的有序表R[0…11]，按折半查找法对该表进行查找，在表内各元素等概率查找情况下查找成功所需的平均比较次数为 _________ 。
A) 35/12 B) 37/12 C) 39/12 D) 43/127. 有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，99｝，当采用折半查找法查找关键字为82的元素时，________ 次比较后查找成功。
A) 1 B.2 C)4 D ) 88. 当采用分块查找时，数据的组织方式为________ oA )数据分成若干块，每块内存数据有序B )数据分成若干块,每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C)数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D )数据分成若干块，每块(出最后一块外)中的数据个数需相同9. 采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同, 假设采用顺序查找来确定结点所在的块时，每块应有个结点最佳A)10 |B)25 C)610. 不能生成右图所示二叉排序树的关键字序列是A) 45312 B ) 42531 C ) 45213 D ) 4231511. _____ 按遍历二叉排序树，可以得到按值递增或递减次序的关键码序列A)先序 B )中序C)后序D)层序12. 在一棵平衡二叉树中，每个结点的平衡因子的取值范围是_________ 。
A) -1 —1 B ) -2 —2 C) 1 —2 D) 0 —113. 具有5层结点的AVL树至少有________ 个结点A) 10 B) 12 C) 15 D) 1714. 在含有15个结点的平衡二叉树上，查找关键字为28的结点，则依次比较的关键字可能是 _______ 。
A) 30，36 B) 38，48，28C) 48，18，38，28 D) 60，30，50，40，38，3615. 一棵深度为k的平衡二叉树，其每个非叶子结点的平衡因子均为0,则该树共有 ______ 个结点。
A) 2k-1-1 B ) 2k-1C) 2k-1 +1 D)2k-116. 查找效率最高的二叉排序树是_______ 。
A •所有结点的左子树都为空的二叉排序树B •所有节点的右子树都为空的二叉排序树C~|平衡二叉树 D .没有左子树的二叉排序树17. 下面关于B-树和B+树的叙述中，不正确的结论是 ________ 。
A)B-树和B+树都能有效地支持顺序查找B ) B-树和B+树都能有效地支持随机查找C) B-树和B+树都是平衡的多分支树D ) B-树和B+树都可用于文件索引结构18. 设有n个关键字，哈希查找法的平均查找长度是_________ 。
A) O (1) B ) O (n ) C) O (log2n ) D) O (n2)19. 将10个元素散列到100000个单元的哈希表，则_________ 产生冲突。
A) 一定会 B )一定不会C)仍可能会D)以上都不对20. 设哈希表长m=14，哈希函数H (key ) =key Mod 11.表中已有4个结点H (15 ) =4，H (38 ) =5，H (61 ) =6，H (84) =7,其余地址为空，如用二次探测再散列法处理冲突，则关键字为49的结点的地址是________ 。
A) 8 B ) 3 C) 5 D ) 921•假设有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入哈希表中，至少要进行 __________ 次探查。
A) k-1 B) k C) k+1 D) k (k+1 ) /222. 若采用链地执法构造哈希表，哈希函数为H (key ) =key Mod 17 ，贝嚅 (1^个链表，这些链表的首指针构成一个指针数组，该数组的下标范围为(2 )。
_(1 ) A) 17 B) 13 C) 16 D)任意(2 ) A) 0 —17 B) 1 —17 | C ) 0 —16 D) 1 —1623. 直接插入排序在最好情况下的时间复杂度为_________ 。
A) O (n) B) O (nlog2n) C) O (log2n) D) O (n2)24. 稳定的排序算法是________ 。
A)直接插入排序B)直接选择排序C)堆排序D)快速排序25. 数据序列｛8，9，10，4，5，6，20，1，2｝只能是________ 算法的两趟排序后的结果。
A)直接选择排序B )冒泡排序C)直接插入排序 D )堆排序26. 对数据序列｛15，9，7，8，20，-1，4｝进行排序，进行一趟后数据的排序变为｛9，15，7，8，20，-1，4｝，则采用的是________ 算法。
A)直接选择排序 B )冒泡排序C)直接插入排序 D )堆排序27. 以下排序方法中，____ 在初始序列已基本有序的情况下，排序效率最高。
A )归并排序B)直接插入排序C)快速排序 D )堆排序28. 不稳定的排序方法是________ 。
A )冒泡排序B)直接插入排序C )希尔排序 D )归并排序29. 以下排序算法中，________ 不能保证每趟排序至少能将一个元素放到其最终位置上。
A )快速排序B )希尔排序C )堆排序D )冒泡排序30. 在以下排序方法中，关键字比较的次数与记录的初始排列次序无关的oA )希尔排序B )冒泡排序C )插入排序|D )直接选择排序31. 在排序算法中，每次从未排序的记录中选取最小(或最大)关键字的记录, 加入到已排序记录的末尾，该排序方法是 ________ OA )希尔排序B )冒泡排序C )插入排序D )直接选择排序32. 采用直接选择排列，比较次数与移动次数分别是 ________ OA ) O (n ), O (log 2n )B ) O (log 2n ), O (n 2)C ) O (n 2), O (n )D ) O (n log 2n ), O ( n )33. 以下序列不是堆的是 _______ O A ) {100 , 85 , 98 , 77, 80 , 60 , 82 , 40 , 20 , 10 , 66}B) {100 , 98 , 85 , 82 , 80 , 77 , 66 , 60 , 40 , 20 , 10}C) {10 , 20 , 40 , 60 , 66 , 77 , 80 , 82 , 85 , 98 , 100}D) {100 , 85 , 40 , 77 , 80 , 60 , 66 , 98 , 82 , 10 , 20}34. 堆排序是 (1) 类排序，堆排序平均时间复杂度和需要附加的存储35. 对n 个记录的文件进行堆排序，最坏情况下的执行时间是 _________ OA ) O (log 2n )B ) (n )C ) O (n Iog 2n )D ) O (n 2)36. 设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的 元素，最好选用—排序法。
A )冒泡排序B )快速排序 排序 D )基数排序37. 在非空m 阶B —树上，除根结点以外的所有其他非终端结点 ________ OA )至少有 m/2棵子树B )至多有 m/2棵子树 C) 至少有 m/2棵子树C )至少有 m/2棵子树38. 对于哈希函数H(key)=key%13 ，被称为同义词的关键字是 ___________ < 空间复杂度分别是 (2) O (1) .A )插入 B )交换 (2) .A ) O (n 2)和 O (1 ) C ) O (nlog 2n )和 O (n ) C )归并 D )|选择B) O (nlog 2n )和 O (1)D ) O (n 2)和 O (n )A ）要排序的数据量太大B ）要排序的数据中含有多个相同值C ）要排序的数据个数为奇数排序的数据已基本有序 42. 下列序列中， 是执行第一趟快速排序后得到的序列（关键字为字符串）A. [da,ax,eb,cd,bb]ff[ha,gc]B. [cd,eb,ax,da]ff[ha,gc,bb]C. [gc,ax,eb,cd,bb]ff[da,ha]D. [ax,bb,cd,da]ff[eb,gc,ha]43. 一个记录的关键字为{46，79，56，38，40，84}，采用快速排序以第一个记录为基准得到的第一次划分结果为 __________ 。
A ） {38,40,46,56,38,79,84}B ） {40,38,46,79,56,84}C ） {40,38,46,56,79,84}D ） {40,38,46,56,79}44. 对下列关键字序列用快速排序法进行排序时，速度最快的情形是 _______ 。
A ） {21，25，5，17，9，23，30}B ） {25,23,30,17,21,5,9}C ） {21,9,17,30,25,23,5}D ） {5,9,17,21,23,25,30}45. 下列排序方法中， ________ 在一趟结束后不一定能选出一个元素放在其最 终位置上。
A ）直接选择排序B ）冒泡排序C ）归并排序D ）堆排序46. 将两个各有n 个元素的有序表归并成一个有序表，其最少的比较次数 匸 。
A ）B ） 2n-1C ） 2nD ） n-1二、填空题：1. 在n 个记录的有序顺序表中进行折半查找，最大的比较次数是—log 2n+ 1 _02. 设线性表{a 1，，，a 2,，…，a sQQ }的元素的值从小到大排列，对一个给定的K 的 值用二分法查找线性表，在查找不成功的情况下至多需要比较_ log 2 nB ) 23 和 39 A ） 35 和 4125 和 51 39. 堆的形状是一棵 ________ 。
