《2022年数据结构严蔚敏清华大学习题及答案.docx》由会员分享，可在线阅读，更多相关《2022年数据结构严蔚敏清华大学习题及答案.docx（47页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选学习资料 - - - - - - - - - 第 1 章 绪论 . 3名师归纳总结 1、填空题 . 3第 1 页,共 31 页2、应用题 . 3第 2 章 线性表 . 41、填空题 . 42、挑选题 . 53、判定题 . 54、程序设计题. 5第 3 章 栈和队列 . 81、填空题 . 82、挑选题 . 83、判定题 . 9第 4 章 串 . 91、挑选题 . 92、判定题 . 9第 5 章 数组和广义表 . 91、填空题 . 92、挑选题 . 93、判定题 . 10 第 6 章 树和二叉树 . 10 1、填空题 . 10 2、挑选题 . 11 - - - - - - -精选学习资料 -
2、- - - - - - - - 3、判定题 . 11 名师归纳总结 4、应用题 . 11 第 2 页,共 31 页5、读程序写结果 . 18 第 7 章 图 . 19 1、填空题 . 19 2、挑选题 . 19 3、判定题 . 20 4、应用题 . 20 5、程序设计题. 25 第 8 章 动态储备治理 . 25 1、填空题 . 25 2、挑选题 . 25 3、判定题 . 25 4、应用题 . 25 5、程序设计题. 25 第 9 章 查找 . 26 1、挑选题 . 26 2、判定题 . 27 3、应用题 . 27 4、程序设计题. 28 第 10 章内部排序 . 29 1、填空题 . 29
3、- - - - - - -精选学习资料 - - - - - - - - - 2、挑选题 . 30 3、判定题 . 30 4、应用题 . 30 第 11 章外部排序 . 31 第 12 章文件 . 31 第 1 章 绪论 1、填空题1. 常见的数据结构有 _线性 _结构, _树形 _结构, _图形 _结构等三种；2. 常见的储备结构有 _次序储备 _结构, _链式储备 _结构等两种；3. 数据的基本单位是 _数据元素 _,它在运算机中是作为一个整体来处理的；4.数据结构中的结构是指数据间的规律关系,常见的结构可分为两大类,_线性结构_和_非线性结构 _；2、应用题1、给出以下算法的时间复杂度 .
4、 void funint n int i=1,k=100; whilein k=k+1; i=i+2; 名师归纳总结 - - - - - - -第 3 页,共 31 页精选学习资料 - - - - - - - - - 时间复杂度为 _O（n）_；2、给出以下算法的时间复杂度 . void fun2int n int i=1,k=100; whileinext=p-next _； _p-next=s _；4. 在单向链表中,如要删除某个结点2、挑选题p,一般要找到 _p 的前趋 _结点,才能实现该操作；1.将两个各有n 个元素的有序表归并成一个有序表,其最少的比较次数是；A；2.AnB2n 1C
5、2nDn-1 在单链表中,假如在结点p 之后插入一个新结点s,其操作为A （ A）s-next=p-next; p-next=s; （ B）p-next=s; s-next=p-next; （ C） s-next=p; p-next=s-next; （ D） p-next=s; s-next=p; 3. 如长度为 n 的线性表采纳次序储备结构,在其第 i 个位置删除一个元素的算法的平均时间复杂度为C ；1in A O0 B O1 C.On DOn2 4. 如长度为 n 的线性表采纳次序储备结构,在其第 i 个位置插入一个新元素需要移动的元素个数为B；1in+1 C. iD n-i-1 A n-
6、iBn-i+13、判定题1. 线性表中每一个元素都有一个前驱和一个后继；（ ）4、程序设计题1、单链表的结点结构定义如下：struct LinkNode 名师归纳总结 - - - - - - -第 5 页,共 31 页精选学习资料 - - - - - - - - - LinkNode *next; int data; ; 请依据述函数的功能写程序；void InsertLinkNode *h,LinkNode *s /h 指向链表的头结点（即使链表中没有元素,头结点也存在；）/链表中元素已经递增有序 /函数功能为将结点 s 插入到链表 h 中；插入后链表仍旧保持递增的次序 LinkNode *
7、p,*q;/q 指向 p 的前驱 q=h; p=h-next; whilep ifp-datas-data /查找到插入点位置,插入 s q-next=s; s-next=p; return; else q=p; 1 分 p=p-next; 1 分 /当表中没有比 s 大的结点时,插入到表尾 s-next=q-next; 2 分 q-next=s; 2 分 2、设次序表 L 是一个递增有序表,试写一算法,将 结构定义如下：x 插入 L 中,并使 L 仍是一个有序表；次序表的名师归纳总结 #define ListSize 100 / 假定表空间大小为100 第 6 页,共 31 页- - - -
8、 - - -精选学习资料 - - - - - - - - - struct SqList int elemListSize; / 数组 elem 用于存放表中的数据int length; / 当前的表长度; /以上为次序表的结构/函数头定义如下void InsertIncreaseList SqList &L ,int x int i; if L.length=ListSize cout0 & L.elem i-1 x ; i- L.elem i =L.elem i-1 ; / 比较并移动元素L.elem i =x; /插入 x L.length+; /表长增 1 / 3、单链表中结点的结构如
9、下所示：typedef struct node int data; struct node *next; node; 请设计满意下述功能的函数；要求：建立带头结点的单链表 H,要求函数从屏幕上读入 m 个整数,每读入一个,便生成相应的结点,并且把它插入到链表 H 的尾部；函数形式为 void CreateLinkListnode *H；参考程序：void CreateListnode *H /H 指向头指针int m,temp; coutm;/ int i=1; node *tail; 名师归纳总结 - - - - - - -第 7 页,共 31 页精选学习资料 - - - - - - - -
10、 - H-next=NULL; tail=H; whilei=m coutplease input your number:temp; node *t=new node ; t-data=temp; t-next=tail-next; tail-next=t; tail=t; i+; 第 3 章 栈和队列1、填空题1. 栈和队列在本质上都是 _线性表 _；2. 栈的操作特点是 _后进先出 _；队列的操作特点是 _先进先出 _；2、挑选题1. 排除递归不肯定需要使用栈,此说法 _A_；A. 正确 B. 错误2. 对于栈,输入序列为（1, 2, 3, 4）,不行能得到的输出序列有 _D_；A（ 1
11、, 2, 3, 4） B （ 4, 3, 2, 1）C （1, 3, 4, 2） D （3,1,2,4）3. 用单循环链表表示队列,正确的说法是B；A可设一个头指针使入队、出队都便利；B可设一个尾指针使入队、出队都便利；C 必需设头尾指针才能使入队、出队都便利；D 无论如何 ,只可能使入队便利；名师归纳总结 - - - - - - -第 8 页,共 31 页精选学习资料 - - - - - - - - - 3、判定题1. 栈的特点是先进先出； （ ）2. 可以在队列的任意位置插入元素；（ ）3. 递归程序化非递归程序必需用到栈；（）4.假如进栈的序列为（1, 2, 3, 4）,就（ 4,2,
12、3, 1）不行能是出栈序列； （ ）5.在用次序表表示的循环队列中,可用标志位来区分队空或队满的条件；（）第 4 章 串1、挑选题1. 设有两个串p 和 q,求 q 在 p 中首次显现的位置的运算称作（B）A连接B模式匹配C求子串D求串长2、判定题1. 空串和空格串是同一个概念,二者没有区分；（ ）第 5 章 数组和广义表1、填空题1.二维数组在内存中储备可以有两种储备方式,一种是 _行_优先储备, 一种是列优先储备；2.设广义表 L（）,（）,（）；就 headL 是（）；tailL 是（）,（） ； L 的长度是3；L 的深度是3 3.设广义表 L（a）,（ b）,（ c）就 headL
13、是 _（ a）_；tailL 是_（b）,（c）_ _；2、挑选题名师归纳总结 1. 在 C 语言中,假如有数组定义int A89 ；假定每个整型数据占2 字节,就数组元素A44 的第 9 页,共 31 页- - - - - - -精选学习资料 - - - - - - - - - 地址是（A）；A. A+80 B. A+76 C.A+82 D.以上都不对D；2. 广义表 A=（ a,b,c,d,e,f,g ） ,就下面式子的值为HeadTailHeadTailTailA A（g）B.dC.cD.d 3、判定题 1. 在 C 语言中,多维数组的储备实行的是行优先的方式；（ ）headtailhe
14、adtailA；2. 广义表在本质上也是线性表；（）3. 可以用三元组储备法来压缩储备稀疏矩阵；（ ）4. 已 知 广 义 表A=a,b,c,d,e,f,从A中 取 出 原 子e的 运 算 是 第 6 章 树和二叉树1、填空题1. 一棵 62 个叶结点的完全二叉树 ,最多有 _62*2=124 _个结点；2.如规定仅有根的二叉树的高度为1,那么高为h 的完全二叉树最多有_2h-1 _个结点,最少有 _2h-1 _个结点；3. 设 只 包 含 有 根 结 点 的 二 叉 树 的 高 度 为0 , 就 高 度 为k的 二 叉 树 的 最 大 结 点 数 为 -_2k+1-1 _,最小结点数为 _k
15、+1_ _；名师归纳总结 4. 设 仅 包 含 根 结 点 的 二 叉 树 的 高 度 为1 , 就 高 度 为k的 二 叉 树 的 最 大 结 点 数 为 -第 10 页,共 31 页- - - - - - -精选学习资料 - - - - - - - - - _2k-1 _,最小结点数为 _k_；2、挑选题1.具有 N 个结点的完全二叉树的深度是 _B_；A. log2N . B . log2N .+1 C . log 2N . D . log 2N .-12.设二叉树的树根为第一层,就第 i 层上至多有 _C_结点；A1 B2 C2i-1 D2i-1 3、判定题1. 二叉树的左右子树次序是
16、严格的,不能够任意转变；（ ）（ ）（ ）2.如根为第一层,就深度为k 的满二叉树的结点为2k-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 分）1
17、 分）第 11 页,共 31 页（ 2）依据题目所给频率值,画出相应的哈夫曼树；（ 11 分,每个结点- - - - - - -精选学习资料 - - - - - - - - - 0 100 1 45 0 55 1 1 9 1 0 1 22 23 27 0 28 d e f 12 0 16 c 7 a b （ 3）给出各个字符对应的哈夫曼编码；（ 6 分）a:1110 b:1111 c:110 d:00 e:01 f:10 （ 4）该段文字经过哈夫曼编码后,长度是多少；（ 4 分）7+9*4+12*3+22+23+27*2=244 或者 100+45+55+28+16=244 2. 设一棵二叉树
18、的先序遍历序列为abcde ,中序遍历序列为badce ,请画出对应的二叉树,并写出对应后序遍历序列； （ 15 分）参考答案如下：1 画出二叉树（ 10 分）名师归纳总结 错一个结点扣2 分；第 12 页,共 31 页- - - - - - -精选学习资料 - - - - - - - - - a b d c e （ 2）后序遍历序列为：bdeca （5 分）3.通信报文中显现的字符A、B、C、D、E,在报文中显现的频率分别为0.23 、0.2 、0.32 、0.12 、0.13 ,分别给出相应字符的哈夫曼编码（要求画出哈夫曼树,并且把权值小的结点放在左边）；（共 14 分）参考答案如下：为处
19、理便利,关键字都乘以 100 ,为 23 , 20,32 , 12,13 构造哈夫曼树为：（9 分 ,每个结点 1 分）0 100 1 43 57 0 1 0 1 20 23 25 32 B A 0 1 C 12 13 D E 所以编码为： A：01 B：00 C ：11 D ：100 E ：101 （5 分,每个编码 1 分）4. 某二叉树结点的中序序列为 H, B,C, D,E,F,G,后序序列为 B, D,C,H,F, G,E,名师归纳总结 请据此画出该二叉树,再给该树加上中序线索；（共 15 分）第 13 页,共 31 页- - - - - - -精选学习资料 - - - - - -
20、- - - 对应的二叉树为： （7 分 ,每个结点 1 分）E H C F G B D 对应中序线索树为：（8 分,每条线索1 分）E H C F G B D 5. 请证明对于任何一棵二叉树,假如其终端结点数为n0 ,度为 2 的结点数为n2,就 n0=n2+1 ；（ 10分）名师归纳总结 - - - - - - -第 14 页,共 31 页精选学习资料 - - - - - - - - - 证明：令树中结点总数为N,度为 1 的结点个数为n1；就树中结点数满意以下公式：n0+n1+n2=N 从度的角度来考虑,满意以下公式：2n 2+n1+1=N 从而得证： n0=n2+1 6. 请依据孩子 -兄弟表示法,将图1 所示树转化为二叉树； （共 14 分）A B E C F D G 解：图 1 A B C D E F G 名师归纳总结 （每个结点2 分）第 15 页,共 31 页