计算机数据结构习题1附答案.docx
- 文档编号:15741159
- 上传时间:2023-07-07
- 格式:DOCX
- 页数:18
- 大小:119.33KB
计算机数据结构习题1附答案.docx
《计算机数据结构习题1附答案.docx》由会员分享,可在线阅读,更多相关《计算机数据结构习题1附答案.docx(18页珍藏版)》请在冰点文库上搜索。
计算机数据结构习题1附答案
第1章绪论
1.1简述下列术语:
数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。
解:
数据是对客观事物的符号表示。
在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。
数据对象是性质相同的数据元素的集合,是数据的一个子集。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
存储结构是数据结构在计算机中的表示。
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。
是对一般数据类型的扩展。
1.2填空题:
1.常见的数据结构有__结构,_____结构,____结构等三种。
2.常见的存储结构有_________结构,______结构等两种。
3.数据的基本单位是____,它在计算机中是作为一个整体来处理的。
4.数据结构中的结构是指数据间的逻辑关系,常见的结构可分为两大类,______和_____。
5.《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和________。
1.2设有数据结构(D,R),其中
,
,
试按图论中图的画法惯例画出其逻辑结构图。
解:
1.3设有以下三个函数:
,
,
请判断以下断言正确与否:
(1)f(n)是O(g(n))
(2)h(n)是O(f(n))
(3)g(n)是O(h(n))
(4)h(n)是O(n3.5)
(5)h(n)是O(nlogn)
解:
(1)对
(2)错(3)错(4)对(5)错
第二章序列
2.1描述以下三个概念的区别:
头指针,头结点,首元结点(第一个元素结点)。
解:
头指针是指向链表中第一个结点的指针。
首元结点是指链表中存储第一个数据元素的结点。
头结点是在首元结点之前附设的一个结点,该结点不存储数据元素,其指针域指向首元结点,其作用主要是为了方便对链表的操作。
它可以对空表、非空表以及首元结点的操作进行统一处理。
2.2填空题。
(1)在顺序表中插入或删除一个元素,需要平均移动元素,具体移动的元素个数与有关。
(2)顺序表中逻辑上相邻的元素的物理位置紧邻。
单链表中逻辑上相邻的元素的物理位置紧邻。
(3)在单链表中,除了首元结点外,任一结点的存储位置由指示。
(4)在单链表中设置头结点的作用是。
(5)线性表按照存储结构不同主要有两种实现方式,一种是_表,另一种是____表。
(6)顺序表采用__随机___访问机制对数据元素进行访问。
(7)在单向链表中,若要删除某个结点p,一般要找到____结点,才能实现该操作。
(8)若频繁地对线性表进行插入与删除操作,该线性表应采用__________存储结构。
(9)判断带头结点head的循环链表是空链表的条件是________。
(10)已知指针p指向单链表中某个结点,语句p->next=p->next->next的作用是_____。
(11)从一个具有100个结点的单链表中查找其值等于x结点时,在查找成功的情况下,需要平均比较的结点数是____。
(12)在一个长度为n的顺序表中,删除第i个元素时,需要移动______个元素。
2.3选择题、判断题:
1.若长度为n的线性表采用顺序存储结构,在其第i个位置删除一个元素的算法的平均时间复杂度为()。
(1≤i≤n)
A.O(0) B.O
(1) C.O(n) D.O(n2)
2.若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素需要移动的元素个数为( )。
(1≤i≤n+1)
A.n-i B.n-i+1 C.i D.n-i-1
3.线性表中每一个元素都有一个前驱和一个后继。
()
4.线性表的逻辑顺序与物理顺序总是一致的。
()
5.判断带头指针head的单向循环链表是否为空链表的条件是head->next==NULL。
()
6.带头结点的单链表A长度为m,带头结点的单链表B长度为n,若将B链接在A的末尾,其时间复杂度应为()。
A、O
(1)B、O(m)C、O(n)D、O(m+n)
7.在一个双向链表中,若要在p所指向的结点之后插入一个新结点,则需要相继修改()个结点的指针域的值。
A、1B、2C、3D、4
2.4已知L是无表头结点的单链表,且P结点既不是首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。
a.在P结点后插入S结点的语句序列是__________________。
//b.在P结点前插入S结点的语句序列是__________________。
c.在表首插入S结点的语句序列是__________________。
//d.在表尾插入S结点的语句序列是__________________。
(1)P->next=S;
(2)P->next=P->next->next;
(3)P->next=S->next;
(4)S->next=P->next;
(5)S->next=L;
(6)S->next=NULL;
(7)Q=P;
(8)while(P->next!
=Q)P=P->next;
(9)while(P->next!
=NULL)P=P->next;
(10)P=Q;
(11)P=L;
(12)L=S;
(13)L=P;
解:
a.(4)
(1)
b.(7)(11)(8)(4)
(1)
c.(5)(12)
d.(9)
(1)(6)
2.5在如下数组A中链接存储了一个线性表,表头指针为A[0].next,试写出该线性表。
其中数组A的定义如下:
structnode{
intdata;
structnode*next;
}A[8];
A01234567
data
60
50
70
90
30
40
next
3
5
7
2
0
4
1
解:
70,50,40,60,30,90
2.6设指针变量p指向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别为llink和rlink)。
解:
略。
第三章队列和栈
1、填空题
1.栈和队列在本质上都是___线性表__________。
2.栈的操作特点是__后进先出_。
队列的操作特点是_先进先出__。
3、栈结构中允许进行插入、删除操作的一端为___栈顶____。
4、已知循环队列的存储空间为数组data[21],且头指针和尾指针分别为8和3,则该队列的当前长度为__16__。
2、选择题
1.消除递归不一定需要使用栈,此说法___A____。
A.正确 B.错误
2.对于栈,输入序列为(1,2,3,4),不可能得到的输出序列有__D_____。
(A)(1,2,3,4) (B)(4,3,2,1)
(C)(1,3,4,2) (D)(3,1,2,4)
3.用单循环链表表示队列,正确的说法是B。
(A)可设一个头指针使入队、出队都方便;
(B)可设一个尾指针使入队、出队都方便;
(C)必须设头尾指针才能使入队、出队都方便;
(D)无论如何,只可能使入队方便。
4.在栈中存取数据的原则是。
A、先进先出B、后进后出C、先进后出D、随意进出
5.用长度为MAX的数组来存储循环队列,用front和rear分别表示队首和队尾指针,则队列长度为_____D_____。
A、(rear+front+MAX)%MAXB、rear-front
C、(rear-front-MAX)%MAXD、(rear-front+MAX)%MAX
6.链式栈与顺序栈相比,一个比较明显的优点是___B___。
A、插入操作更加方便B、通常不会出现栈满的情况
C、不会出现栈空的情况D、删除操作更加方便
7.在队列中存取数据的原则是A。
A、先进先出B、后进先出C、先进后出D、随意进出
8.设输入序列是1、2、3、……、n,经过栈的作用后输出序列的第一个元素是n,则输出序列中第i个输出元素是__B__。
A、n-iB、n-i+1C、n-i-1D、不能确定
3、判断题
1.栈的特点是先进先出。
(×)
2.可以在队列的任意位置插入元素。
(×)
3.递归程序化非递归程序必须用到栈。
(×)
4.如果进栈的序列为(1,2,3,4),则(4,2,3,1)不可能是出栈序列。
(√)
5.在用顺序表表示的循环队列中,可用标志位来区分队空或队满的条件。
(√)
6.栈是一种线性结构。
(√)
7.单向循环链表从任何一个结点出发,都能访问到所有结点。
(√)
8.顺序栈是线性结构,链栈不是线性结构。
(×)
9.堆的形状是一棵完全二叉树。
()
4、综合题:
1.简述栈和线性表的差别。
解:
线性表是具有相同特性的数据元素的一个有限序列。
栈是限定仅在表尾进行插入或删除操作的线性表。
第四章数组与矩阵
1、填空题
1.二维数组在内存中存储可以有两种存储方式,一种是___行__优先存储,一种是列优先存储。
2.采用三元组的存储方式对稀疏矩阵进行压缩存储,将失去其功能。
2、选择题
1.在C语言中,如果有数组定义intA[8][9];假定每个整型数据占2字节,则数组元素A[4][4]的位置是(A)。
A.A+80B.A+76C.A+82D.以上都不对
2、二维数组A按行顺序存储,其中每个元素占1个存储单元。
若A[1][1]的存储位置为420,A[3][3]的存储位置为446,则A[4][4]的存储位置为___B_
A、458B、459C、460D、461
3、判断题
1.可以用三元组存储法来压缩存储稀疏矩阵。
()
第五章树和二叉树
1、填空题
1.一棵62个叶结点的完全二叉树,最多有___62*2+1=125______个结点。
2.若规定仅有根的二叉树的高度为1,那么高为h的完全二叉树最多有___2^h-1___________个结点,最少有___2^(h-1)______个结点。
3.设只包含有根结点的二叉树的高度为0,则高度为k的二叉树的最大结点数为____2^(k+1)-1____________,最小结点数为____k+1____________。
4.设仅包含根结点的二叉树的高度为1,则高度为k的二叉树的最大结点数为____________,最小结点数为_____。
5.在一棵有n个结点的哈夫曼树中,叶子结点有__(n-1)/2+1__个。
6.深度为k的二叉树具有的结点数目,最少为____k_,最多为____2k-1__。
7.由n个结点构成的满二叉树中,叶子结点有__(n+1)/2__个。
2、判断题
1、在完全二叉树中,若某结点无左孩子,则它必是叶子结点。
( √ )
2、一组权值,可以构造出唯一形状的哈夫曼树。
(×)
3、二叉树的左右子树次序是严格的,不能够任意改变。
(√)
4、若根为第一层,则深度为k的满二叉树的结点为2^k-1。
(√)
5、二叉树的三叉链表存储结构可以方便的访问到双亲结点。
(√)
6、在哈夫曼树中不存在度为1的结点。
(√)
3、选择题
1、将一棵有100个结点的完全二叉树从上到下,从左到右依次对结点进行编号,根结点的编号为1,则编号为35的结点的右孩子的编号为__B_。
A、70B、71C、50D、36
2、具有N个结点的完全二叉树的深度是__B______。
(A)⌊log2N⌋(B)⌊log2N⌋+1
(C)⌊log2(N)⌋(D)⌊log2N⌋-1
3、设二叉树的树根为第一层,则第i层上至多有__C_____结点。
(A)1 (B)2 (C)2i-1 (D)2i-1
4、由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为___D__。
A、24B、48C、72D、53
5、将一棵有100个结点的完全二叉树从上到下,从左到右依次对结点进行编号,根结点的编号为1,则编号为99的结点的父结点的编号为__C__。
A、50B、51C、49D、99
4、解答题
1、在二叉树的顺序存储结构中,实际上隐含着双亲的信息,因此可和三叉链表对应。
假设每个指针域占4个字节,每个信息域占k个字节。
试问:
对于一棵有n个结点的二叉树,且在顺序存储结构中最后一个节点的下标为m,在什么条件下顺序存储结构比三叉链表更节省空间?
解:
采用三叉链表结构,需要n(k+12)个字节的存储空间。
采用顺序存储结构,需要mk个字节的存储空间,则当mk 时,采用顺序存储比采用三叉链表更节省空间。 2、一棵度为2的树与一棵二叉树有何区别? 解: 二叉树是颗有序树,但度为2的树则未必有序。 3、用三种顺序遍历下面的树 解: (1)先序: 123456879101112131514 (2)中序: 348675211091115131412 (3)后序: 876543210151413121191 4、找出所有满足下列条件的二叉树: (a)它们在先序遍历和中序遍历时,得到的节点访问序列相同; (b)它们在后序遍历和中序遍历时,得到的结点访问序列相同; (c)它们在先序遍历和后序遍历时,得到的节点访问序列相同。 解: (a)不含左子树的二叉树。 (b)不含右子树的二叉树。 (c)即不含左子树,也不含右子树的二叉树。 5、某颗二叉树树的先根序列为GFKDAIEBCHJ,后根序列为DIAEKFCJHBG,请画出其树形,并写出中根遍历序列; 解: 中根遍历序列: DIAEKFCJHBG 5、应用题 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分) (3)给出各个字符对应的哈夫曼编码。 (6分) a: 1110b: 1111c: 110d: 00e: 01f: 10 (4)该段文字经过哈夫曼编码后,长度是多少。 (4分) (7+9)*4+12*3+(22+23+27)*2=244 或者100+45+55+28+16=244 2.设一棵二叉树的先序遍历序列为abcde,中序遍历序列为badce,请画出对应的二叉树,并写出对应后序遍历序列。 (15分) 参考答案如下: (1)画出二叉树(10分) 错一个结点扣2分。 (2)后序遍历序列为: bdeca(5分) 3.通信报文中出现的字符A、B、C、D、E,在报文中出现的频率分别为0.23、0.2、0.32、0.12、0.13,分别给出相应字符的哈夫曼编码(要求画出哈夫曼树,并且把权值小的结点放在左边)。 (共14分) 参考答案如下: 为处理方便,关键字都乘以100,为{23,20,32,12,13} 构造哈夫曼树为: (9分,每个结点1分) 所以编码为: A: 01B: 00C: 11D: 100E: 101(5分,每个编码1分) 4.某二叉树结点的中序序列为H,B,C,D,E,F,G,后序序列为B,D,C,H,F,G,E,请据此画出该二叉树,再给该树加上中序线索。 (共15分) 对应的二叉树为: (7分,每个结点1分)对应中序线索树为: (8分,每条线索1分) 5.请证明对于任何一棵二叉树,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。 (10分) 证明: 令树中结点总数为N,度为1的结点个数为n1。 则树中结点数满足下列公式: n0+n1+n2=N 从度的角度来考虑,满足下列公式: 2n2+n1+1=N 从而得证: n0=n2+1 6.请按照孩子-兄弟表示法,将图1所示树转化为二叉树。 (共14分) 解: (每个结点2分) 7、设二叉树如图2所示。 分别写出它的先序遍历、中序遍历、后序遍历序列。 (共15分) 8. (1)写出如图所示二叉树的中序遍历结果。 (8分) (2)画出二叉树的中序后继线索。 (10分) (1)中序遍历结果: ADBCHFEG——共8分,每个字符1分 (2)二叉树的中序后继线索如图 ——共10分,每个后继线索2分 9.已知某二叉树的前序遍历序列为: ABCDEFG 和中序遍历序列为: CBEDAFG。 请画出该二叉树。 答案如下: 10.已知通信联络中只可能出现A、B、C、D、E、F、G、H共8种字符,其出现次数分别为5,28,7,9,14,23,3,11次。 (1)请画出赫夫曼树(权值小的结点在左边)。 (15分) (2)计算该树的带权路径长度。 (3分) (1)赫夫曼树构造如下。 树中结点位置正确者,每个1分,共15分。 (2)该树的带权路径长度为 (5+3+7+8)*4+(11+14)*3+(23+29)*2=271 ————3分 友情提示: 部分文档来自网络整理,供您参考! 文档可复制、编制,期待您的好评与关注!
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 数据结构 习题 答案