数据结构-严蔚敏-清华大学出版社-习题及答案

第一章导言21.填空22.应用问题2第2章线性表31.填空32.选择题33.对错问题44.编程问题4第3章堆栈和队列71.填空72.选择题73.对错问题7第四章弦81.选择题82.对错问题8第5章数组和广义表81.填空82.选择题83.对错问题9第6章树和二叉树91.填空92.选择题93.对错问题104.申请问题105.阅读程序并写出结果17第7章图181.填空182.选择题183.对错问题194.申请问题195.编程问题24第8章动态存储管理241.填空242.选择题243.对错问题244.申请问题245.编程问题24第9章找到241.选择题242.对错问题253.申请问题264.编程问题27第十章内部排序281.填空282.选择题283.对错问题294.申请问题29第十一章外部排序30第十二章文件30第一章引言1。填空1.有三种常见的数据结构：线性结构、树形结构和图形结构。2.有两种常见的存储结构：顺序存储结构和链式存储结构。3.数据的基本单位是数据元素，在计算机中作为一个整体进行处理。4.数据结构中的结构是指数据之间的逻辑关系。常见的结构可以分为两类，线性结构和非线性结构。2.申请问题1.给出了后续算法的时间复杂度。空虚的乐趣int i=1，k=100同时(不精确=p-下一个_ _ _ _ _ _ _ _ _ _ _ _；_ _ _ _ _ p-next=s _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _；4.在单向链表中，要删除一个节点P，通常需要找到_p的前一个节点才能实现操作。2.选择题1.将两个具有n个元素的有序表合并到一个有序表中，比较的最小次数是a。(甲)n(乙)2n-1(丙)2n(丁)n-12.在单个链表中，如果在节点P之后插入一个新的节点S，它的操作就是as-下一个=p-下一个；p-next=s；(二)p-next=s；s-next=p-next；s-下一个=p；p-next=s-next；(四)p-next=s；s-next=p；3.如果长度为n的线性表采用顺序存储结构，则删除一个元素的算法的平均时间复杂度为(c)。(1in)A.O(0) B.O(1) C.O(n) D.O(n2)4.如果长度为n的线性表采用顺序存储结构，则在I位置插入新元素需要移动的元素数为(b)。(1in 1)a . n . I . b . n . I . 1 c . I . d . n . I . 13.真或假1.线性表中的每个元素都有一个前置任务和一个后续任务。()4.编程问题1.单个链表的节点结构定义如下：结构链接节点链接节点*下一步；int数据；请根据功能编写程序。无效插入(链接节点*h，链接节点*s)/h指向链表的头节点(即使链表中没有元素，头节点仍然存在。)/链表中的元素按顺序增加了/功能是将节点S插入链表H，插入后链表仍然保持递增顺序。LinkNode *p，* q；/q指向p的前身。q=h；p=h-下一个；而(p)if(p-data-data)/找到插入点并插入q-next=s；s-next=p；返回；其他q=p；(1分)p=p-下一个；(1分)/当表中没有大于S的节点时，将其插入表的末尾s-next=q-next；(2分)q-next=s；(2分)2.将序列表L设置为升序序列表，并尝试编写一个算法将X插入到L中，使L仍然是一个有序表。序列表的结构定义如下：#定义ListSize 100 /假设表空间大小为100结构SqList 国际机场)；/数组元素用于在表中存储数据整数长度；/当前表格长度；/以上是顺序表的结构/函数头的定义如下void InsertEndResilisT(SqList L，int x) int I；如果(长度=列表大小)计数为“OVERFLOW”；/判断是否发生溢出对于(i=L .长度；一号线1x；i -)一号=一号；/比较和移动元素1=x；/插入xl .长度；/将表格长度增加1/3.单链表中节点的结构如下：typedef结构节点 int数据；结构节点*下一步；节点；请设计一个满足以下功能的函数。要求：要建立一个带前导节点的单链表，该函数需要从屏幕上读入M个整数。每次读入一个整数，就会生成相应的节点，并将其插入链表的尾部。该函数的形式为空创建链表(节点*H)。参考程序：无效创建列表(节点*H)/指向头部的指针int m，temp输入数据的数量：“；cinm/int I=1；节点*尾部；下一个=空；尾部=H；而(i=m)请输入您的数字：节点* t=新节点；t-数据=温度；t-next=tail-next；tail-next=t；tail=t；我；第3章堆栈和队列1.填空1.堆栈和队列本质上是_ _ _线性表_ _ _ _ _ _ _ _ _ _ _。2.堆栈操作的特征是_ _ LIFO _ .队列的特征是先进先出。2.选择题1.没有必要使用堆栈来消除递归。这份声明。A.对b .错2.对于堆栈，输入序列是(1，2，3，4)，不能获得的输出序列是_D_。(一)(1，2，3，4)(二)(4，3，2，1)(三)(1，3，4，2)(四)(3，1，2，4)3.队列由一个循环链表表示。正确的说法是b可以设置头部指针，以便于进出；可以设置尾部指针以方便进出；必须设置头部和尾部指针，以便于进入和离开团队；在任何情况下，都只能为进入该小组提供便利。3.真或假1.堆栈的特点是先进先出。()2.您可以在队列中的任何位置插入元素。()3.递归编程非递归程序必须使用堆栈。()4.如果堆叠顺序是(1，2，3，4)，那么(4，2，3，1)不能是堆叠顺序。()5.在由序列表表示的循环队列中，标志位可用于区分空队或满队的情况。()第四章字符串1.选择题1.有两个字符串P和Q。找到Q在P中第一次出现的位置的操作叫做(B)A.连接b .模式匹配c .子字符串d .字符串长度2.真或假1.空字符串和空字符串是相同的概念，它们之间没有区别。()第5章数组和广义表1.填空1.二维数组可以通过两种方式存储在内存中，一种是_ _ rows _ _优先级存储，另一种是列优先级存储。2.建立一个广泛的列表。头(左)是()；尾部(L)是()，()；l的长度是3；l的深度是3。3.如果l=(a)、(b)、(c)，标题(L)为_ _(a)_ _ _；尾部(L)是_(b)、(c)_ _ _。2.选择题1.在c语言中，如果8 9中有数组定义；假设每个整数数据占用2个字节，数组元素44的地址是(A)。A.a80b.a76c.a82d .以上都不是真的2.广义意义表A=(a，b，(c，d)，(e，(f，g)；那么下面公式的值是(d)；头部(尾部(头部(尾部(尾部(A)A.(g)b .(d)c . c . d3.真或假1.在C语言中，多维数组以行优先的方式存储。()2.广义表在本质上也是线性的。()3.三值存储方法可以用来压缩和存储稀疏矩阵。()4.众所周知，广义表A=(a，b，c)，(d，E，f)，并且从A中提取原子E的操作是头(尾(A)。()第六章树和二叉树1.填空1.一个完整的二叉树，有62个叶节点，最大值为_ _ _ 62 * 2=124 _ _ _ _ _ _ _ _。2.如果仅具有根的二叉树的高度被指定为1，那么具有高度h的完整二叉树具有最多_ _ _ _ _ 2h-1 _ _ _ _ _ _ _ _ _个节点和至少_ _ _ _ _ 2(h-1)_ _ _ _ _个节点。3.如果仅包含根节点的二叉树的高度为0，则高度为k的二叉树的最大节点数为_ _ _ _ _ 2(k1)-1 _ _ _ _ _ _ _ _ _ _，最小节点数为_ _ _ _ _ k1 _ _ _ _ _ _ _ _ _ _。4.如果仅包含根节点的二叉树的高度为1，则高度为k的二叉树的最大节点数为2 k-1，最小节点数为k。2.选择题1.一个有N个节点的完整二叉树的深度是_ _ B _ _ _ _ _ _ _ _。(A) log2N (B) log2N 1(C) log2(N) (D) log2N -12.如果二叉树的根是第一层，那么在第一层上最多有_个节点。(甲)1(乙)2(丙)2i-1(丁)2i-13.真或假1.二叉树左右子树的顺序是严格的，不能任意改变。()2.如果根是第一层，深度为k的全二叉树的节点是2 k-1。()3.二叉树三叉链表的存储结构可以方便地访问父节点。()4.申请问题1.在一段文字中，有六个字符A、B、C、D、E和F，每个字符的出现频率分别为7、9、12、22、23和27。请回答以下问题：(1)什么是哈夫曼树？(3分)(2)根据主题给出的频率值绘制相应的哈夫曼树。(11分)(3)给每个字符对应的霍夫曼码。(6分)(4)霍夫曼编码后的文本长度是多少？(4分)参考答案如下：(1)答案是：具有最小加权路径长度的二叉树称为霍夫曼树。(3分)(2)根据主题给出的频率值绘制相应的哈夫曼树。(11分，每个节点1分)fc287912222355162745100abed1000001111(3)给每个字符对应的霍夫曼码。(6分)a :1110 b :1111 c :110d :00 e :01 f :10(4)霍夫曼编码后的文本长度是多少？(4分)(7 9)*4 12*3 (22 23 27)*2=244或100 45 55 28 16=2442.将二叉树的一阶遍历序列