《北大网络教育数据结构作业.doc》由会员分享，可在线阅读，更多相关《北大网络教育数据结构作业.doc（6页珍藏版）》请在三一办公上搜索。
1、数据结构1. 鼓励独立完成作业，严惩抄袭2.4.1 在一个长度为n的顺序存储线性表中，删除第i个元素(1in)时，需要依次前移_个元素。A. A. n-i正确答案：A2.2.4.2 在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为：C. C. (n+1)/2正确答案：C3. 2.4.3 在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行D. D. p-next = q-next ; q-next = p;正确答案：D4.2.4.4 在一个单链表HL中，若要删除由指针q所指向结点的后继
2、结点，则执行C. C. p = q-next ; q-next = p-next;正确答案：C5.3.5.1 在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的_A. A. 行号正确答案：A6. 3.5.2 设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为_。B. B. O(n)正确答案：B7.6.2.1 下列关键字序列中，_是堆。D. D. 16, 23, 53, 31, 94, 72正确答案：D8.6.2.2 堆的形状是一棵_。C. C. 完全二叉树正确答案：C10. 2.1 线性表的两种存储结构顺序表和链表中：（1）两种存储表示各有哪些主要优缺点?（2）
3、如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 给予解释？（3）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？给予解释？ 正确答案：（1）顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素，修改效率不高。 链接存储表示的存储空间一般在程序的运行过程
4、中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。（2）选链式存储结构。它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O（1）。（3）选顺序存储结构。顺序表可以随机存取，时间复杂度为O（1）。11. 2.2 写出下面函数被调用执行后，得到的以HL为表头指针的单链表中的数据元素序列。void AA(LNode * & HL)InitList(HL);In
5、sertRear(HL,30);InsertRear(HL,50);int a5 = 15,8,9,26,12;for ( int i=0; ilink,*pr=NULL; While(p!=NULL) First-link=pr; /逆转first指针 pr=first;first=p;p=p-link; /指针前移 first-link=pr; 13. 2.5 判断以下叙述的正确性，对于被判断为错误的叙述给出理由。(1)分配给单链表的内存单元地址必须是连续的。(2)与顺序表相比，在链表上实现顺序访问，其算法的效率比较低。(3)向顺序表中插入一个元素，平均要移动约一半的元素。(4)在带表头结
6、点的循环单链表中，任何一个结点的指针都不可能为空。(5)在有n个元素的顺序表中，删除任意一个元素所需移动结点的平均次数为n-1个。 正确答案：(1)错误。分配给单链表的内存单元地址可以是不连续的。 (2)错误。在顺序表和链表上实现顺序访问，其算法的时间复杂度都是O(n). (3)正确。 (4)正确。 (5)错误。删除第1个元素移动结点次数为n-1个，删除最后一个元素没有结点移动。删除任意一个元素所需移动结点的平均次数为删除约一半的元素的情况，为n/214. 3.1 已知一个稀疏矩阵如下图所示：(参见教科书上第三章【习题 3-1】)0 4 0 0 0 0 00 0 0 -3 0 0 18 0 0
7、 0 0 0 00 0 0 5 0 0 00 -7 0 0 0 2 00 0 0 6 0 0 0具有6行7列的一个稀疏矩阵(1)写出它的三元组线性表；(2)给出它的顺序存储表示；(3)给出它的转置矩阵的三元组线性表和顺序存储表示；正确答案：(1) ( (1,2,4),(2,4,-3),(2,7,1),(3,1,8),(4,4,5),(5,2,-7),(5,6,2),(6,4,6) ) (2) 1 2 2 3 4 5 5 6 2 4 7 1 4 2 6 4 4 -3 1 8 5 -7 2 6 (3) (1,3,8),(2,1,4),(2,5,-7),(4,2,-3),(4,4,5), (4,6,
8、6),(6,5, 2),(7,2,1) 1 2 2 4 4 4 6 7 3 1 5 2 4 6 5 2 8 4 -7 -3 5 6 2 115. 3.3 分别计算出下列每个广义表的长度和深度。(参见教科书上第三章【习题 3.2】)(1) A=()(2) B=(a,b,c)(3) C=(a,(b,(c)(4) D=(a,b),(c,d)(5) E=(a,(b,(c,d),(e)(6) F=(a,(b,(),c),(d),e)正确答案：(1) A：长度：1 深度：2 (2) B：长度：3 深度：1 (3) C：长度：2 深度：3 (4) D：长度：2 深度：2 (5) E：长度：3 深度：3 (6) F：长度：1 深度：416. 3.4 设A=1,2,3，B=3,4,5，求下列结果：(1) A + B （集合的并）(2) A * B （集合的交）(3) A - B （集合的差）正确答案：(1)集合的并A+B=1,2,3,4,5 (2)集合的交A*B=3 (3)集合的差A-B=1,2窗体底端
