《华东理工大学数据结构（本）期末复习题及参考答案.docx》由会员分享，可在线阅读，更多相关《华东理工大学数据结构（本）期末复习题及参考答案.docx（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构（本）期末复习题1一、填空题（共10题，每题1分，共10分）超越高度. 一个算法必须在执行有穷步之后结束，这是算法特点的 O （1分）1 .广义表（a）,b）,c）,d）的表头是，表尾是O （分）2 .数组AL.5,L.6的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连 续内存单元中，那么A3, 4的地址是 o （1分）.拓扑排序输出时总是选择 的顶点输出。（1分）3 .从源点到汇点的 称为关键路径。（1分）.设有两个串p和q,求q在p中首次出现的位置的运算称作。 （1分）4 .栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算 的一端称为
2、o （1分）. 一棵深度为5的满二叉树有 个叶子结点。（1分）5 . 一个算法具有、输入和输出五个重要特性。 （1分）.设 s=9 YOU ARE JUDGING IT RIGHT OR WRONG9 , 顺序执行以下操作： SubString（sub 1 ,s, 1,8） ； SubString（sub2,s,20,5） ； StrCat（sub 1 ,sub2）;那么 最 后 subl 的 值为: O （分）二、单项选择题（共10题海题2分洪20分）.非空的循环单链表head的尾指针p满足（）。（2分）A.p-next=NULLB.p=NULLC.p-next=headD.p=head1
3、.判断线索二叉树中某结点p没有左孩子的条件是（）。（2分）A.p!=nullB.p-lchild!=nullC.p-ltag=OD.p-ltag=l.一棵二叉排序树，通过0可以得到结点的有序序列。（2分）A.前序遍历B.中序遍历C.后序遍历D.线索化2 . GetTail GetHead （a,b）,（c,d） = （）（2 分）A.（d）B.bC.（b）D.（a）3 .二叉树有30个叶子结点，那么二叉树的总结点数至少是（）。（2分）A.29B.58C.59D.606 .将7个不同的数据进行排序,A.6B.7C.217 .将7个不同的数据进行排序,A.6B.7C.21至少需要比拟（）次。（2分
4、）D.42至多需要比拟（）次。（2分）D.422.画出以下二叉树所对应的树或者森林。A（10 分）从顶点a出发的深度优先遍历序列和广度优先遍历序列;（10 分）3.如下图，求：（1）写出该图的邻接矩阵的表示；（2）根据邻接矩阵的表示,五、算法设计题（共2题，每题10分，共20分）二叉排序二叉排序1.设计一递归算法，将以二叉链表为存储结构的二叉树中的叶子结点全部删除。 树的存储结构如下：（10分）2,设计一递归算法，在以二叉链表为存储结构的二叉树中，统计二叉树中叶子结点的个数。（10 分）数据结构（本）期末复习题2一、填空题（共10题海题1分，共10分）1. n个顶点e条边的图采用邻接表存储时，
5、深度优先遍历算法的时间复杂度为O （分）标准答案：1. O（n+e）;2 .具有3个结点的二叉树有一种形态。（1分）标准答案:1. 5;3 .二叉树通行线索化时，如果某结点的左孩子为空，在线索化时应该指向该结点的O （分）标准答案：1.直接前驱；.二叉树进行线索化时，如果某结点的右孩子为空，在线索化时应该将该指针域线索化该结点的 O （1分）标准答案：1.直接后继；4 .设广义表 L=（）, （）,那么 Head（L）是。（1 分）标准答案：1.（）或空表；5 .在做进栈运算时，应先判别栈是否o（1分）标准答案：L满；6 .二维数组A1020采用列序为主方式存储，每个元素占10个存储单元，且的
6、存储地址是2000,那么A12的地址是 o （1分）标准答案：1.3260;.从逻辑结构方面可以把数据结构分成 和非线性数据结构。（1分）标准答案：1.线性数据结构；9.数组庆1.51.6的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续内存单元中，那么A3, 4的地址是 o （1分）标准答案：1. 1175;10.队列是一种先进先出的线性表，允许插入的一端称为。（1分）标准答案：1.队尾； 二、单项选择题（共10题，每题2分洪20分）.设哈希地址为。m-l,现哈希表长为25, k为关键字，用p去除k,将所得的余数作为k 的哈希地址，即H（k）=k%p。为了减少发生冲突的频率
7、，那么取p为（）。（2分）A.29B.25C.23D.19标准答案：C1 .假设一组记录的关键字码值为（44, 79, 56, 38, 40, 84）,那么利用快速排序的方法，以第 一个记录为基准得到的一次划分结果为（）。（2分）A.38, 40, 44, 56, 79, 84B.40, 38, 44, 56, 79, 84C.40, 38, 44, 79, 56, 84D.40, 38, 44, 84, 56, 79标准答案：B2 .二叉树有30个叶子结点，那么二叉树的总结点数至少是（）。（2分）A.29B.58C.59D.60标准答案：C3 .判断线索二叉树中某结点p有右孩子的条件是（）。
8、（2分）A.p!=nullB.p-rchild!=nullC.p-rtag=OD.p-rtag=l标准答案：c.非空的循环单链表head的尾指针p满足（）。（2分）A.p-next=NULLB.p二NULLC.p-next=headD.p=head标准答案：c.判断线索二叉树中某结点p没有右孩子的条件是（）。（2分）A.p !=nullB.p-rchild! =nullC.p-rtag=OD.p-rtag= 1标准答案：D.下面关于串的表达中，哪一个是不正确的？（2分）A.串是字符的有限序列.空串是由空格构成的串C模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储标准答案：
9、B.一棵二叉排序树，通过（）可以得到结点的有序序列。（2分）A.前序遍历B.中序遍历C.后序遍历D.线索化标准答案：B.平衡二叉排序树具有的特点是左子树与右子树的高度差的绝对值小于或者等于（）。（2 分）A.O B.l C.2D.3标准答案：B.设有100个元素，用折半查找法进行查找时，最小比拟次数为（）。（2分）A.7B.4C.2D.1标准答案：D三、问答题（共4题，每题5分，共20分）1 .简述线性数据结构与非线性数据结构的区别。（5分）标准答案：线性数据结构中数据的关系只有一种，每个结点元素的直接前驱和直接后继 是唯一的；非线性数据结构中数据的关系可以有两种或者多种，每个结点元素的直接前
10、驱 和直接后继是不唯一的。2 . 一棵度为2的树与一棵二叉树有何区别？（5分）标准答案：度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是 有序的。即，在一般树中假设某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即 使是一个孩子也有左右之分。3 .指出以下程序段的功能是什么？Void Demo(SeqStack *S, int m) SeqStackT; int i;InitStack(&T);While(! StackEmpty(S) If (i=Pop(S)!=m Push(&T,i)；)While (JStackEmpty(T) i=Pop(&T); Push(S
11、,i) (5 分)标准答案：该算法的功能是:利用栈T做辅助，过滤栈S中值为m的元素。4 .简要说明算法与程序的区别。(5分)标准答案：算法是解决特定问题的操作序列，可以用多种方式描述。程序是算法在计算 机中的实现，与具体的计算机语言有关。四、计算题(共3题，每题10分，共30分)1.某通讯系统使用 8 种字符，其概率分布分别 为:0.06, 0.28, 0.07, 0.08, 0.14, 0.22, 0.03, 0.12,试设计其哈夫曼编码 (10 分)标准答案：哈夫曼不唯一，其对应编码也不唯一。2.画出以下二叉树所对应的树或者森林。(10 分)C FM标准答案：还原成四棵树：出发的深度优先遍
12、历序列和广度优先遍历序列;(10 分)3.如下图，求：(1)写出该图的邻接矩阵的表示；(2)根据邻接矩阵的表示，从顶点a标准答案：(1)标准答案：(1)5：4TL3lchild=NULL) & (T-rchild=NULL) Free(T); / 删除度为 0 的结点；count_node(T-lchild); /递归删除左子树中 度为0的结点数count_node(T-rchild); /递归删除右子树中度为0的结点数2,设计一递归算法，在以二叉链表为存储结构的二叉树中，统计二叉树中叶子结点的个数。(10 分)标准答案：BSTNode *temp; Void Change(BSTree T)
13、/ *T 为树根指针 if (T-lchild!=null) | (T-rchild !=null) temp= T-lchild; T-lchild= T-rchild; T-rchild=temp; countJeaf(T-lchild); /递归求左子树的叶子结点数countJeaf(T-rchild); /递归求右子树的叶 子结冠数8 .判断线索二叉树中某结点p没有右孩子的条件是()。(2分)A.p!=nullB.p-rchild!=nullC.p-rtag=OD.p-rtag= 1.设 s=9 YOU ARE JUDGING IT RIGHT OR WRONG9 , 顺序执行以下操作
14、： SubString(sub 1 ,s, 1,8)； SubString(sub2,s,20,5)； StrCat(subl,sub2)；那么最后 sub 1 的值为()。(2 分)A.YOU AREB.RIGHTC.WRONGD.YOU ARE RIGHT9 .n个顶点的强连通图至少有()条边。(2分)A.n-1 B.n C.n+1 D.O三、问答题(共4题海题5分洪20分).有程序如下： void main()Stack S;Char x,y;InitStack(S);X=，c;y=k，；Push(S,x); Push(SJa); Push(S,y);Pop(S,x); Push(S；f
15、); Push(S,x);Pop(S,x); Push(S/s5);while(!StackEmpty(S) Pop(S,y);printf(y);Printf(x);(5分).设 s=I AM A STUDENT, t=GOOD, q=WORKER，求 Replace(s,STUDENTq)和 Concat(SubString(s,6,2), Concat(t,SubString(s,7,8) (5 分).指出以下程序段的功能是什么？Void Demo(SeqStack *S, int m) SeqStack T; int i;InitStack(&T);While(!StackEmpty(
16、S) If (i=Pop(S)!=m Push(&T,i);)While (!StackEmpty(T) i=Pop(&T); Push(S,i) (5 分).简述什么是哈夫曼树。(5分)四、计算题（共3题海题10分，共30分）.给定二叉树的两种遍历序列，分别是：前序遍历序列：ABCDEF中序遍历序列：BDCAEF, 试画出该二叉树并求其后序遍历序列。（10分）1 .某通讯系统使用8种字符,其概率分布分别为：0.06, 0.28, 0.07, 0.08, 0.14, 0.22,0.03, 0.12,试设计其哈夫曼编码。（10分）2 .如下图，求：（1）写出该图的邻接矩阵的表示；（2）根据邻接矩
17、阵的表示，从顶点a出发的深度优先遍历序列和广度优先遍历序列;出发的深度优先遍历序列和广度优先遍历序列;（1。分）五、算法设计题（共2题，每题10分，共20分）1 .设计一递归算法，在以二叉链表为存储结构的二叉排序树T上查找关键字为k的结点。 二叉排序树的存储结构如下：（10分）.设计一递归算法，在以二叉链表为存储结构的二叉树中，统计二叉树中叶子结点的个数。（10 分）数据结构（本）期末复习题1一、填空题（共10题海题1分，共10分）1. 一个算法必须在执行有穷步之后结束，这是算法特点的 O （1分）标准答案：1.有穷性；2.广义表（a）,b）,c）,d）的表头是，表尾是 O （分）标准答案:1
18、. （a）,b）,c）;2. （d）;3.数组AL.5.6的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连 续内存单元中，那么A3, 4的地址是 o （1分）标准答案：1. H75;4.拓扑排序输出时总是选择 的顶点输出。（1分）标准答案：1.入度为0;.从源点到汇点的 称为关键路径。（1分）标准答案：1.最长路径；.设有两个串p和q,求q在p中首次出现的位置的运算称作 o （1分）标准答案：1.子串定位；.栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算 的一端称为 o （1分）标准答案：1.栈底；一棵深度为5的满二叉树有 个叶子结点。（1分）标
19、准答案：1.16;一个算法具有、输入和输出五个重要特性。 （1分）标准答案：1.有穷性2确定性3可行性；10.设 s=9 YOU ARE JUDGING IT RIGHT OR WRONG5 ,顺序执行以下操作： SubString（subl,s,l,8） ； SubString（sub2,s,20,5） ； StrCat（subl,sub2）;那么 最 后 subl 的 值为： O （分）标准答案：1. YOU ARE RIGHT;二、单项选择题（共10题，每题2分洪20分）1 .非空的循环单链表head的尾指针p满足（）。（2分）A.p-next=NULLB.prNULLC.p-next-
20、headD.p=head标准答案：C2 .判断线索二叉树中某结点p没有左孩子的条件是（）。（2分）A.p!=nullB.p-lchild!=nullC.p-ltag=OD.p-ltag= 1标准答案：D3 .一棵二叉排序树，通过0可以得到结点的有序序列。（2分）A.前序遍历B.中序遍历C.后序遍历D.线索化标准答案：B. GetTail GetHead (a,b),(c,d)U = ()(2 分)A.(d) B 上 C.(b)D.(a)标准答案：C.二叉树有30个叶子结点，那么二叉树的总结点数至少是()。(2分)A.29B.58C.59D.60标准答案：C.将7个不同的数据进行排序，至少需要比
21、拟()次。(2分)A.6B.7C.21D.42标准答案：A.将7个不同的数据进行排序，至多需要比拟()次。(2分)A.6B.7C.21D.42标准答案：C.判断线索二叉树中某结点p没有右孩子的条件是()。(2分)A.p!=nullB.p-rchild!=nullC.p-rtag=0D.p-rtag= 1标准答案：D.设 sOU ARE JUDGING IT RIGHT OR WRONG9 , 顺序执行下歹U 操作： SubString(sub 1 ,s, 1,8)； SubString(sub2,s,20,5)； StrCat(subl,sub2)；那么最后 sub 1 的值为()。(2 分)
22、A.YOU AREB.RIGHTC.WRONGD.YOU ARE RIGHT标准答案：D.n个顶点的强连通图至少有()条边。(2分)A.n-1 B.n C.n+1 D.O标准答案：A 三、问答题(共4题，每题5分洪20分).有程序如下：void main()Stack S;Char x,y;InitStack(S);X=Q;尸心Push(S,x); Push(SJa); Push(S,y);Pop(S,x); Push(S/f); Push(S,x);Pop(S,x); Push(S；s,);while(!StackEmpty(S) Pop(S,y);printf(y);Printf(x);(
23、5分)标准答案：输出为“stack”。1 .设 s=I AM A STUDENT, t=GOOD, q=WORKER,求 Replace。/STUDENTq)和 Concat(SubString(s,6,2), Concat(t,SubString(s,7,8) (5 分)标准答案：Replace。,STUDENT,q尸I AM A WORKER”Concat(SubString(s,6,2尸“ AS”.指出以下程序段的功能是什么？Void Demo(SeqStack *S, int m) SeqStack T; int i;InitStack(&T);While(!StackEmpty(S)
24、 If (i=Pop(S)!=m Push(&T,i);)While (!StackEmpty(T) i=Pop(&T); Push(S9i) ) (5 分)标准答案：该算法的功能是:利用栈T做辅助，过滤栈S中值为m的元素。2 .简述什么是哈夫曼树。(5分)标准答案：带权路径长度WPL最小的二叉树称为哈夫曼树或者最优二叉树。四、计算题（共3题海题10分洪30分）.给定二叉树的两种遍历序列，分别是：前序遍历序列：ABCDEF中序遍历序列：BDCAEF, 试画出该二叉树并求其后序遍历序列。（10分）标准答案：后序遍历序列：DCBFEA.某通讯系统使用8种字符，其概率分布分别为：0.06, 0.28
25、, 0.07, 0.08, 0.14, 0.22,0.03, 0.12,试设计其哈夫曼编码。（10分）标准答案：哈夫曼不唯一，其对应编码也不唯一，写对即可得分。1 .如下图，求：（1）写出该图的邻接矩阵的表示；（2）根据邻接矩阵的表示，从顶点a出发的深度优先遍历序列和广度优先遍历序列;出发的深度优先遍历序列和广度优先遍历序列;标准答案：（1） 先序歹U：123,4,5.51 3 卜 4 a（10 分）（2）深度优先序列:1,2,4,53,广度优五、算法设计题（共2题，每题10分，共20分）1 .设计一递归算法，在以二叉链表为存储结构的二叉排序树T上查找关键字为k的结点。二叉排序树的存储结构如下
26、：（10分）标准答案：BSTNode *BSTSearch（BSTree *bt, KeyType k） / 在二叉排序树 T 上查找关键 字为 k 的结点 if (!bt) return NULL; else if (bt-key=k) return bt; else if (bt-key k) return (BSTSearch(bt-lchild , k); /在左子树中查找 else return (BSTSearch(bt-rchild , k); /在右子 树中查找2 .设计一递归算法，在以二叉链表为存储结构的二叉树中，统计二叉树中叶子结点的个数。(10 分)标准答案:BSTNod
27、e *temp; Void Change(BSTree T) / *T 为树根指针 if (T-lchild!=null) | (T-rchild !=null) temp二 T-lchild; T-lchiId= T-rchild; T-rchild=temp; count_leaf(T-lchild); /递归求左子树的叶子结点数counteaf(T-rchild); /递归求右子树的叶 子结点数数据结构（本）期末复习题2一、填空题（共10题海题1分，共10分）. n个顶点e条边的图采用邻接表存储时，深度优先遍历算法的时间复杂度为O （分）.具有3个结点的二叉树有一种形态。（1分）1 .二
28、叉树进行线索化时，如果某结点的左孩子为空，在线索化时应该指向该结点的O （分）2 .二叉树进行线索化时，如果某结点的右孩子为空，在线索化时应该将该指针域线索化该 结点的 O （1分）.设广义表 L=（）, （）,那么 Head（L）是。（1 分）3 .在做进栈运算时，应先判别栈是否o（1分）.二维数组A1020采用列序为主方式存储，每个元素占10个存储单元，且A00的存储地址是2000,那么A12的地址是 o （1分）.从逻辑结构方面可以把数据结构分成 和非线性数据结构。（1分）.数组AL5.6的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续内存单元中，那么A3, 4的地址
29、是 o （1分）.队列是一种先进先出的线性表，允许插入的一端称为。（1分）二、单项选择题（共10题，每题2分洪20分）.设哈希地址为。m-1,现哈希表长为25, k为关键字，用p去除k,将所得的余数作为k 的哈希地址，即H（k尸k%p。为了减少发生冲突的频率，那么取p为（）。（2分）A.29B.25C.23D.19.假设一组记录的关键字码值为（44, 79, 56, 38, 40, 84）,那么利用快速排序的方法，以第 一个记录为基准得到的一次划分结果为（）。（2分）A.38, 40, 44, 56, 79, 84B.40, 38, 44, 56, 79, 84C.40, 38, 44, 79
30、, 56, 84D.40, 38, 44, 84, 56, 791 .二叉树有30个叶子结点，那么二叉树的总结点数至少是（）。（2分）A.29B.58C.59D.60.判断线索二叉树中某结点p有右孩子的条件是（）。（2分）A.p!=nullB.p-rchild!=nullC.p-rtag=0D.p-rtag=l2 .非空的循环单链表head的尾指针p满足（）。（2分）A.p-next=NULLB.p=NULLC.p-next=hcadD.p-head.判断线索二叉树中某结点p没有右孩子的条件是（）。（2分）A.p! =nullB.p-rchild! =nullC.p-rtag=0D.p-rta
31、g= 13 .下面关于串的表达中，哪一个是不正确的？（2分）A.串是字符的有限序列.空串是由空格构成的串C模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储8 .一棵二叉排序树，通过0可以得到结点的有序序列。(2分)A.前序遍历B.中序遍历C.后序遍历D.线索化.平衡二叉排序树具有的特点是左子树与右子树的高度差的绝对值小于或者等于()。(2 分)A.OB.lC.2D.3.设有100个元素，用折半查找法进行查找时，最小比拟次数为()。(2分)A.7B.4C.2D.1三、问答题(共4题，每题5分，共20分)1 .简述线性数据结构与非线性数据结构的区别。(5分). 一棵度为2的树
32、与一棵二叉树有何区别？(5分)2 .指出以下程序段的功能是什么？Void Demo(SeqStack *S, int m) SeqStack T; int i;InitStack(&T);While(! StackEmpty(S) If (i=Pop(S)!=m Push(&T,i);)While (!StackEmpty(T) i=Pop(&T); Push(S,i) (5 分).简要说明算法与程序的区别。(5分)四、计算题(共3题，每题10分，共30分)1.某通讯系统使用 8 种字符，其概率分布分别 为:0.06, 0.28, 0.07, 0.08, 0.14, 0.22, 0.03, 0.12,试设计其哈夫曼编码 (10 分)