西南交大数据结构主观题作业

1、西南交大数据结构主观题作业弘成无锡数字化学习中心批次层次：专升本专业：计算机科学与技术姓名：刘鹏亮学号：1594067313 / 19第一次作业二、主观题（共3道小题）14.数据的物理结构包括的表示和的表示。参考答案：线性结构,非线性结构15.数 据 逻 辑 结 构 包括、禾廿四种，树结构和图结构统称为 。参考答案： 集合、线性结树、 图、非线性结构16.数据结构研究的是 和一以及它们之间的相互关系，并对于这种结构定义相应的 ，设计出相应的 。参考答案：逻辑结构，物理结构：运算，算法第二次作业三、主观题（共22道小题）24. 向一个长度为n的顺序表中的第i个元素之前插入一个元 参考答案：n-i

2、+1_25. 在一个长度为n的顺序表中删除第i个元素时，需要向前参考答案：n-i26. 在单链表中设置头结点的作用是 。参考答案：简单插入、删除算法27. 在单链中要删除某一指定结点，必须找到该结点的 参考答案：直接前驱28. 访问单链表中的结点，必须沿着 依次进参考答案：指针域29. 在双链表中每个结点有两个指针域，一个指向 参考答案：直接前驱结点,30. 在链表中，删除最后一个结点的算法时间复杂度参考答案：双向循环31. 访问一个线性表中具有给定值的时间复杂度的数量级是-参考答案：O(n)32. 由n个数据元素生成一个顺序表，若每次都调用插入算法杂度为 ，若每次都调用插入算法把一个元素插入

3、到参考答案：OM，O(n2)33. 在链表中，可以用表尾指针代替表头指针。参考答案：双向34. 在链表中，可以用表尾指针代替表头指针。参考答案：双向35. 根据n个数据元素建立对应的顺序表和单链表存储结构，最坏的情况是。参考答案：0(n) ，O(n2)36. 求线性表的顺序存储和链式存储的长度的算法时间复杂度 参考答案：O(1.0(n)37. 在一个带头结点的单链表中，在表头插入或删除与在其他同？ 。参考答案：相同38. 在一个不带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？。参考答案：不相同39. 阐述顺序表和链表存储方式的特点。参考答案：顺序表存储方式为数

4、据分配连续的存储单元，数据元素按 辑相邻的数据元素物理也相邻，因此可以实现随即访问线性 。链表存储方式分配的存储单元可以不连续，通过每个结点 能顺序访问线性表中的数据元素。40. 若频繁地对一个线性表进行插入和删除操作，则该线性表 参考答案：若频繁地对一个线性表进行插入和删除操作，则 结构在插入和删除数据元素时不需要移动数据元素，只需要 逻辑关系。41. 在单链表、双向循环链表和单循环链表中，若仅知道指针 从相应的链表中删除？若可以，时间复杂度各为多少。参考答案：要实现删除P结点的操作，必须找到其前驱结点 以实现删除结点P。单链表不行，因此不知道头指针就无法 环链表可以可以实现删除P结点。单循

5、环链表删除P结点白时间复杂度为0(1)。42. 对链表设置头结点的作用是什么？参考答案：对带头结点的链表，在表的任何结点之前插入结点或删除 点的指针域，因为在带头结点的链表中任何元素结点都有前 结点或删除首元结点都要修改头指针，其算法要比不带头结 其次，带头结点的链表结构，初始化后的头指针就 指针，可以减少出错的可能性。43. 已知一个线性表用含头结点的单链表做存储结构，写一个 参考答案：int listle nght(li nklist L) int len gth=0;P=L->n ex t;while(p) len gth+;p=p->n ex t;return(length

6、);44. 已知一个顺序表L,其中的元素按值递增有序排列，设计表仍然递增有序，且空间复杂度为0 (1 )。参考答案：void in sertsq(sqlist L,elemtype x) n=Len gth-1;if(LT(L.elem n,x) n+;L.elem n=x;elsewhile( n>=0&&LT(x,L.elem n) L.elem n+1=L.elem n;n-；L.elem n+1=L.elem n;retur n;45. 写一个算法，从顺序表中删除值为x的所有元素参考答案：void delallsq(Sqlist &L) int i=0,j

7、=0;while(j<Len gth) if(L.elemj!=x)L.elemi+=L.elemjj+;Lon gth=i;第三次作业三、主观题(共50道小题)60. 循环队列的引入，目的是为了克服 。参考答案：顺序队列的假溢出61. 区分循环队列的空与满有 3种方法，它们是 一、参考答案：少用一个元素、 设空满标志、.62. 栈和队列的区别是，参考答案：栈只能在表一端讲行插入和删除操作，队列限制 操作63. 一个栈的输入序列是12345 ，则栈的输出序列43512 参考答案：错误的64. 设栈采取顺序存储结构，栈中已有i-1个元素，则第i 个参考答案：0( 1)65. 栈的特点是【I

8、，队列的特点是【I2，3, 4 ,则【】是不可能的出栈序列；若进是可能的出队序列。参考答案： 后进先出先进先出限制存取点的线性结构123,466. 若用不带头结点的单链表表示栈，则创建一个空栈要执行 参考答案：top=NULL67. 从循环队列中删除一个元素的操作是 。参考答案： Q.fron t=(Q.fro nt+1)%QSize68. 从循环队列中插入一个元素的操作是。参考答案：Q.rear=(Q.rear+1)%QSize69. 判断链队列中只有一个结点的条件是。参考答案：Q.fron t->next=Q.rear70. 如果栈的最大长度难以估计，最好使用 。参考答案：链栈71.

9、 为什么说栈是一种后进先出表？参考答案：因为栈是限定在表的一端进行插入和删除操作， 是一种后进先出表。72. 对于一个栈，其输入序列是 A,B,C，试给出全部可能的输 参考答案：可能的出栈序列是：ABC ACB BAC BCA CBA73. 何谓队列上溢？何为假溢出现象？有哪些解决假溢出问题 参考答案：队列上溢指在队列的顺序存储分配中，按照队列的操作规 而无法进入队列。假溢出指在队列的顺序存储分配中，分配给队列的存储空 进队的数据元素无法进队的现象。解决假溢出问题的方法是在队列的顺序存储分配中，分配 是用表示队头和队尾指针与分配给队列的存储空间长度进行入队操作：Q.rear=(Q.rear+1

10、)%MSize出队操作：Q.front=(Q.front+1)%MSize74. 队列可以用单循环链表来实现，故可以只设一个头指针或 参考答案：使用循环链表来表示队列，设置尾指针比较合适，因为入 队操作时可以根据尾指针很容易找到链表的头结点， 入队出 指针，则出队操作的算法时间复杂度为0(1)，入队操作的75. 深度为k的完全二叉树至少有个结点，至多参考答案：2k-12 K-176. 在一棵二叉树中，度为0的结点个数为n0，度为2的结参考答案：n2+177. 一棵二叉树第i层最多有个结点，一棵有n个结点的参考答案：2i-12 K-1,2k-178. 根据二叉树的定义，具有3个结点的二叉树共有种

11、不同 参考答案：579. 有一棵如下图所示的树，回答下列问题： 这棵树的根结点是。 这棵树的叶子结点是 结点c的度为。 这棵树的深度是 。 结点c的孩子结点是。 结点c的双亲结点是。 这棵树的度是。参考答案： a b,e,g,d 2 4 _ef a 380. 树与二叉树的两个主要差别是参考答案：树中结点的最大度没有限制，二叉树结点的最大 二叉树的的节点又左右之分。81. 设有如下图所示的二叉树，给出其前序、中序和后序遍历参考答案：前序序列：eadcbifghj中序序列：abcdiefhgj 后序序列：bcidahjgfe82.给出下图所示的树的二叉树表示14 / 1922 / 19参考答案：下

12、图为其树的二叉树表示有一份电文共有5个字符：a,b,c,d,e,83.它们出现的频率依求哈夫曼树的带权路径长度和每个字符的哈夫曼编码参考答案：字符编码:a： 011b： 10c: 00d： 010e： 1184.假设一棵二叉树采用顺序存储结构，如下图所示05101520eafdgcjhib回答些列问题： 画出二叉树表示。 写岀先序、中序和后序遍历结果 写出结点c的双亲结点和左、右孩子结点 画出此二叉树还原成森林的图参考答案：二叉树表示如下图所示fg 先序序列为：eadcbjfghi中序序列为：acbdjefhgi后序序列为：bcjdahigfe 结点c的双亲结点是d,左孩子为b，无右孩子 该二

13、叉树对应的森林为85. 有n个顶点的无向图最多有条边。参考答案：n(n-1)/286. 一个图的表示法是唯一的，而 表示法是不唯-参考答案：邻接矩阵,邻接表87. 具有10个顶点的无向图，边的总数最多为 。参考答案：4588. 在有n个顶点的有向图中，每个顶点的度最大可达 参考答案：2(n-1)89. 已知一个有向图采用邻接矩阵表示，计算第i个顶点的入参考答案：求第i列非0元素个数90. 从占用的存储空间来看，对于稠密图和稀疏图，采用邻接 参考答案：从占用存储空间看，稠密图采用邻接矩阵更好，91. 用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相 参考答案：用邻接矩阵表示图，矩阵元素的个数与

14、图的定点个数直接相 则邻接矩阵的大小为n2。92. 对于一个具有n个顶点和e条边的无向图，若采用邻接表 表中结点总数为【】。参考答案： n 2e93. 顺序查找含n个元素的顺序表，若查找成功，则比较关键不成功，则比较关键字的次数为次。参考答案：n ,n+194. 在含有n个元素的有序顺序表中进行二分查找，最大的比 参考答案：.log 2n +1_95. 用二分查找一个查找表，该查找表必须具有的特点是参考答案：顺序存储且关键字有序96.分块查找发将待查找的表均匀地分成若干块且块中诸记录的顺序可以是任意的，但块与块之间。参考答案：关键字有序96. 在分块查找方法中，首先查找 ，然后再查找相应的参考

15、答案：关键字表，对应的块97. 用二叉排序树在n个元素中进行查找，最坏情况下查找时 度为 。参考答案：0(n)，O(log门98. 折半查找的存储结构仅限于，且是。参考答案： 顺序存储结构 ，关键字有序排歹列99. 一个无序序列可以通过构造一棵树而变成有序序程。参考答案：二叉排序100. 画出对长度为10的右序表进行折半查找的一棵判定树平均查找长度=(1+2*2+4*3+3*4)/10=2.9102.设有数据集合d=1 , 12 , 5 , 8 , 3 , 10 , 7, 13 , 9，回答下列问题: 依次取d中各数据，构造一棵二叉排序树；如何依据此二叉排序树得到 d的一个有序序列。参考答案：构造的二叉排序树如下图所示。对该二叉排序树进行中序遍历，就可以得到d的一个有序1 ， 3， 5， 7， 8， 9， 10， 12， 13103. 每次从无序子表中取出一个元素，把它插入到有序子表次从无序子表中挑选出最小或最大元素，把它交换到有序表 参考答案：插入；直接诜择104. 每次通过基准元素间接比较两个元素，不满足约定要求使两个相邻有序表合并成一个有序表的排序方法叫做排参考答案：快速；_105.排序方法采用二分法的思想，排序方法将数据的组 参考答案：快速，