计算机数据结构习题1附答案.doc

第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，一般要找到_p的前趋_结点，才能实现该操作。（8）若频繁地对线性表进行插入与删除操作，该线性表应采用_链式_存储结构。（9）判断带头结点head的循环链表是空链表的条件是_head-next=head_。（10）已知指针p指向单链表中某个结点，语句p-next=p-next-next的作用是_删除P后面的结点_。(11)从一个具有100个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需要平均比较的结点数是_50.5_ 。（12）在一个长度为n的顺序表中，删除第i个元素时，需要移动_n-i_个元素。2.3选择题、判断题：1.若长度为n的线性表采用顺序存储结构，在其第i个位置删除一个元素的算法的平均时间复杂度为(C )。(1in)AO(0) BO(1) C.O(n) DO(n2)2. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素需要移动的元素个数为(B )。(1in+1)An-i Bn-i+1 C. i Dn-i-13.线性表中每一个元素都有一个前驱和一个后继。（ ）4.线性表的逻辑顺序与物理顺序总是一致的。( )5 判断带头指针head的单向循环链表是否为空链表的条件是head-next=NULL。（）6.带头结点的单链表A长度为m，带头结点的单链表B长度为n，若将B链接在A的末尾，其时间复杂度应为 （ A ） 。A、 O(1) B、O(m) C、O(n) D、O(m+n)7.在一个双向链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改（ C ）个结点的指针域的值。A、1 B、2 C、3 D、42.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中链接存储了一个线性表，表头指针为A0.next，试写出该线性表。 其中数组A的定义如下： struct node int data;struct node *next;A8; A 0 1 2 3 4 5 6 7 data605070903040next3572041解：70,50,40,60,30,902.6设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。解：略。第三章 队列和栈1、填空题1.栈和队列在本质上都是_线性表_。2.栈的操作特点是_后进先出_。队列的操作特点是_先进先出_。3、栈结构中允许进行插入、删除操作的一端为_栈顶_。4、已知循环队列的存储空间为数组data21，且头指针和尾指针分别为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)%MAX B、 rear-front C、(rear-front-MAX)%MAX D、(rear-front+MAX)%MAX6链式栈与顺序栈相比，一个比较明显的优点是_B_。 A、插入操作更加方便 B、通常不会出现栈满的情况 C、 不会出现栈空的情况 D、删除操作更加方便 7在队列中存取数据的原则是 A 。A、 先进先出 B、后进先出 C、先进后出 D、随意进出8设输入序列是1、2、3、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是_B_。A、n-i B、n-i+1 C、n-i-1 D、不能确定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语言中，如果有数组定义 int A89；假定每个整型数据占2字节，则数组元素A44的地址是（ A ）。A. A+80 B. A+76 C.A+82 D.以上都不对2、二维数组A按行顺序存储，其中每个元素占1个存储单元。若A11的存储地址为420，A33的存储地址为446，则A44的存储地址为_B_A、458 B、459 C、460 D、4613、判断题1.可以用三元组存储法来压缩存储稀疏矩阵。（ ）第五章 树和二叉树1、填空题1.一棵62个叶结点的完全二叉树,最多有_62*2+1=125_个结点。2.若规定仅有根的二叉树的高度为1，那么高为h的完全二叉树最多有_2h-1_个结点，最少有_2(h-1)_个结点。3.设只包含有根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为_2(k+1)-1_，最小结点数为_k+1_。4.设仅包含根结点的二叉树的高度为1，则高度为k的二叉树的最大结点数为_2k-1_，最小结点数为_k_。5.在一棵有n个结点的哈夫曼树中，叶子结点有_（n-1）/2+1_ _ 个。6深度为k的二叉树具有的结点数目，最少为_k_ ，最多为_2k-1_ 。7.由n个结点构成的满二叉树中，叶子结点有_(n+1)/2_个。2、判断题1、在完全二叉树中，若某结点无左孩子，则它必是叶子结点。（）2、 一组权值，可以构造出唯一形状的哈夫曼树。( )3、 二叉树的左右子树次序是严格的，不能够任意改变。（ ）4、 若根为第一层，则深度为k的满二叉树的结点为2k-1 。（ ）5、 二叉树的三叉链表存储结构可以方便的访问到双亲结点。 （ ）6、 在哈夫曼树中不存在度为1的结点。（ ）3、选择题1、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为35的结点的右孩子的编号为_B_。A、70 B、71 C、50 D、362、具有N个结点的完全二叉树的深度是_B_。(A) log2N (B) log2N +1 (C) log2(N) (D) log2N -13、设二叉树的树根为第一层，则第i层上至多有_C_结点。(A)1 (B)2 (C)2i-1 (D)2i-14、由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为_D_。A、 24 B、48 C、72 D、535、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为99的结点的父结点的编号为_C_。A、50 B、51 C、49 D、994、解答题1、在二叉树的顺序存储结构中，实际上隐含着双亲的信息，因此可和三叉链表对应。假设每个指针域占4个字节，每个信息域占k个字节。试问：对于一棵有n个结点的二叉树，且在顺序存储结构中最后一个节点的下标为m，在什么条件下顺序存储结构比三叉链表更节省空间？解：采用三叉链表结构，需要n(k+12)个字节的存储空间。采用顺序存储结构，需要mk个字节的存储空间，则当mkn(k+12)时，即时，采用顺序存储比采用三叉链表更节省空间。2、一棵度为2的树与一棵二叉树有何区别？解：二叉树是颗有序树，但度为2的树则未必有序。3、用三种顺序遍历下面的树解：(1) 先序：1 2 3 4 5 6 8 7 9 10 11 12 13 15 14(2) 中序：3 4 8 6 7 5 2 1 10 9 11 15 13 14 12(3) 后序：8 7 6 5 4 3 2 10 15 14 13 12 11 9 14、找出所有满足下列条件的二叉树： (a) 它们在先序遍历和中序遍历时，得到的节点访问序列相同； (b) 它们在后序遍历和中序遍历时，得到的结点访问序列相同； (c) 它们在先序遍历和后序遍历时，得到的节点访问序列相同。解：(a) 不含左子树的二叉树。(b) 不含右子树的二叉树。(c) 即不含左子树，也不含右子树的二叉树。5、某颗二叉树树的先根序列为GFKDAIEBCHJ，后根序列为DIAEKFCJHBG，请画出其树形，并写出中根遍历序列；解： 中根遍历序列：DIAEKFCJHBG5、应用题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: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=244fc287912222355162745100abed10000011112. 设一棵二叉树的先序遍历序列为abcde，中序遍历序列为badce，请画出对应的二叉树，并写出对应后序遍历序列。（15分）参考答案如下：(1)画出二叉树（10分）错一个结点扣2分。 abcde （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分）ABDEC010001111004357202325321213所以编码为：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分）CFBDGHE对应的二叉树为：（7分,每个结点1分）对应中序线索树为：（