数据结构形成性考核册答案.doc

《数据结构形成性考核册答案.doc》由会员分享，可在线阅读，更多相关《数据结构形成性考核册答案.doc（18页珍藏版）》请在三一文库上搜索。

1、数据结构（本）形成性考核作业答案作业1（本部分作业覆盖教材第1-2章的内容）一、单项选择题I. C2. D3. B4. C5. D6. C7. B8. C9. A10. BII. C12. D13. C14. A15. B16. C17. C18. B19. B20. D二、填空题1. n-i+12. n-i3. 集合线性结构树形结构图状结构4. 物理结构存储结构5. 线性结构非线性结构6. 有穷性 确定性 可形性有零个或多个输入 有零个或多个输岀7. 图状结构&树形结构9. 线性结构10. n-1 O（n）11. s->next=p->next;12. head13. q

2、>ncxi=p>ncxt;14. p->next=head;15. 单链表16. 顺序存储链式存储17. 存储结构1&两个 直接后继 直接前驱 尾结点 头结点19. 头结点的指针指向第一个结点的指针20. 链式链表三、问答题1. 简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算 机中的存储表示称为数据的存储结构。可见，数据的逻借结构是反映数据之间的固有关系，而数据的存储 结构是数据在讣算机中的存储表示。尽管因采用的存储结构不同，逻辑上相邻的结点，英物理地址未

3、必相 同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻借结构的特点。采用的存储结构不同， 对数据的操作在灵活性，算法复杂度等方面差别较大。2. 解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，要求内存中 存储单元的地址必须是连续的。优点：一般情况下，存储密度大，存储空间利用率高。缺点：（1）在做插入和删除操作时，需移动大量元素：（2）由于难以估计，必须预先分配较大的空间， 往往使存储空间不能得到充分利用：（3）表的容量难以扩充。链式结构存储时，相邻数据元素可随意存放，所占空

4、间分为两部分，一部分存放结点值，另一部分存 放表示结点间关系的指针。优点：插入和删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低。3. 什么情况下用顺序表比链表好？答：顺序表适于做查找这样的静态操作，链表适于做插入和删除这样的动态操作。如果线性表的变化 长度变化不大，且其主要操作是査找，则采用顺序表：如果线性表的长度变化较大，且其主要操作是插入、 删除操作，则采用链表。4. 解释头结点、第一个结点（或称首元结点）、头指针这三个概念的区别？答：头结点是在链表的开始结点之前附加的一个结点：第一个结点（或称首元结点）是链表中存储第一个 数据元素的结点；头指针是指向链表中第一个结点（或为

5、头结点或为首元结点）的指针。5. 解释带头结点的单链表和不带头结点的单链表的区別。答：带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作上。在结构上，带头结点的单链表，不管链表是否为空，均含有一个头结点，不带头结点的单链表不含头 结点。在操作上，带头结点的单链表的初始化为申请一个头结点。无论插入或删除的位置是地第一个结点还 是其他结点，算法步骤都相同。不带头结点的单链表，英算法步骤要分别考虑插入或删除的位程是第一个 结点还是其他结点。因为两种情况的算法步骤不同。四、程序填空题1.(1 ) p-xiata=i(2) p->next=NULL(3) q->next=

6、p(4) q=p2.(1 ) head=p(2) q=p(3) p->next=NULL(4) p->next=q->next<5) q->next=p3.(1 ) p=q->next(2) q->next=p->next五. 完成：实验1一 一线性表根据实验要求(见教材P2OI-2O2)认真完成本实验，并提交实验报告。作业2答案(本部分作业覆盖教材第3-5章的内容)一、单项选择题I. C 2. B 3. A 4. C 5. B 6. A 7. B 8. C 9. A 10. CII. B12. C13. B14. B15. A 16.C 17.

7、 B18. A 19. C 20. D21. B22. D23. C24. B25. D26. A 27. C 28.D 29. D 30. C 31.A 32. D二、填空题1. 后进先岀2. 下一个3. 增1增14. 假上溢5.栈是否满 s->top=MAXSIZE-l 栈顶指针 栈顶对应的数组元素栈是否空 s->top=-l栈顶元素修改栈顶指针5. bceda6. 终止条件递归部分7. LU->front=LU->rear8. 运算符 操作数 ab+c/fde/-9. s->next=h:10. h=h->next;11. r->next=s;1

8、2. f=f->next;13. 字符14. 顺序存储方式链式存储方式15. 0空格字符的个数16. 特殊稀疏1& () () 219. ( (d,e,f)20. 串长度相等且对应位置的字符相等21. i(i-l)/2+j22. 行下标、列下标、非零元素值三、问答题1. 简述栈和一般线性表的区别。答：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以任线 性表的任何位置进行插入和删除操作。2. 简述队列和一般线性表的区别。队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的删除只能在队头进行，而一般的 线性表可以在线性表的任何位垃进行插入和删

9、除操作。3. 链栈中为何不设头结点？答：因为链栈只在链头插入和删除结点，不可能在链表中间插入和删除结点，算法实现很简单，所以 一般不设垃头结点。4. 利用一个栈，则:（1）如果输入序列由A, B, C组成，试给出全部可能的输出序列和不可能的输岀序列。（2）如果输入序列由A, B, C, D组成，试给出全部可能的输出序列和不可能的输岀序列。答：（1）栈的操作特点是后进先岀，因此输岀序列有：A入，A出，BN, B出，C入C出，输岀序列为A BC。A入，A岀，BN, C入，C出，B出，输出序列为A CB。A入，BN, B出，A岀，C入，C出，输出序列为BACoA入，BN, B出，C入，C岀，A岀，输

10、出序列为BCAoA入，BN, C入，C岀，B岀，A出，输岀序列为CBAo由A, B, C组成的数据项，除上述五个不同的组合外，还有一个C, A, B组合。但不可能先把C岀 栈，再把A岀栈，（A不在栈顶位苣），最后耙B出栈，所以序列CAB不可能由输入序列A, B, C通过 栈得到。（2）按照上述方法，可能的输出序列有：ABCD, ABDC, ACBD, ACDB, ADCB, BACD, BADC, BCAD, BCDA, BDCA, CBAD, CBDA, CDBA, DCBAo不可能的输岀序列有：DABC, ADBC, DACB, DBAC, BDAC, DBCA, DCAB, CDAB,

11、CADB, CABD5. 用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234,为了得到1342出栈顺序，相应的 S和X操作串是什么？答：应是SXSSXSXX。各操作结果如下：S1入栈X1出栈输出序列：1S2入栈S3入栈X3岀栈输出序列：13S4入栈X4岀栈输出序列：134X2岀栈输出序列:13426. 有5个元素，苴入栈次序为：A、B、C、D、E,在各种可能的出栈次序中，以元素C、D最先的 次序有哪几个？答：从题中可知，要使C第一个且D第二个岀栈，应是A入栈，B入栈，C入栈，C岀栈，D入栈。 之后可以有以下几种情况：（1）B出栈，A岀栈，E入栈，E出栈，输岀序列为：CDBAE.（2）B

12、出栈，E入栈，E出栈，A出栈，输岀序列为CDBEA。<3） E入栈，E岀栈，B出栈，A出栈，输出序列为CDEBA所以可能的次序有：CDBAE, CDBEA, CDEBA7. 写出以下运算式的后缀算术运算式（1）3x2+x-l/x+5（A+B）*C-D/（E+F）+G答；对应的后缀算术运算式（1）3x2*x+lx/-5+ AB-C*DEF+/-G+8. 简述广义表和线性表的区别和联系。答：广义表是线性表的的推广，它也是n（n>0）个元素如an的有限序列，其中缶或者是原子或 者是一个广义表。所以，广义表是一种递归数据结构，而线性表没有这种特性，线性表可以看成广义表的 特殊情况，当去都是

13、原子时，广义表退化成线性表。四、程序填空题1（1）q->front->next=p->next;（2）free（p）;（3）q->rear=q->front五、综合题1答：出队序列是e2, e4, e3, e6, e5, el的过程：el入栈（栈底到栈顶元素是el）e2入栈（栈底到栈顶元素是el,e2）e2出栈（栈底到栈顶元素是el）e3入栈（栈底到栈顶元素是el,e3）e4入栈（栈底到栈顶元素是el,e3,e4）e4岀栈（栈底到栈顶元素是el,e3）e3岀栈（栈底到栈顶元素是el）e5入栈（栈底到栈顶元素是el,e5）亡6入栈（栈底到栈顶元素是el,e5,e6）

14、00） e6出栈（栈底到栈顶元素是el,e5）（ID e5出栈（栈底到栈顶元素是el）el出栈（栈底到栈顶元素是空）栈中最多时有3个元素，所以栈S的容量至少是3。2.算法设计如下：/*只有一个指针rear的链式队的基本操作*/Sinclude <stdio. h>typedef char elemtype;struct node /*定义链队列结点*/elemtype data;struct node *next;；typedef struct queue /*肚义链队列数据类型*/struct node *rear; LinkQueue;void initqueue (LinkQ

15、ueue *Q)/*初始化队列*/0=(struct queue *)malloc(sizeof(struct queue): Q->rear=NULL;void enqueue (LinkQueue *Q, elemtype x)/*入队算法*/struct node *s,*p;s=(struct node *)malloc(sizeof(struct node); s->data=x;辻(Q->rear=NULL)/*原为空队时*/Q->rear=s;s->next=s;else/*原队不为空时*/p=Q->rear->next; /*p 指向第

16、一个结点*/Q->rear->next=s; /*将 s 链接到队尾*/Q->rear=s;/*Q->rear 指向队尾*/s->next=p;void delqueue (LinkQueue *Q) 出队算法*/struct node *t;辻(Q->rear=NULL)printf ("队列为空！ n");return(0);else if (Q->rear->next=Q->rear)tQ-ear;Q->rear=NULL;else /*有多个结点时*/t二Q-Arear-next; Q->rear-&

17、gt;next=t->next;free(t);/*只有一个结点时*/*t指向第一个结点*/*引成循环链*/elemtype gethead(LinkQueue *Q)/*取队首元素算法*/if (Q->rear=NULL) printf C*队列为空！ n");else return(Q->rear->next->data);int emptyqueue(LinkQueue *Q)/*判断队列是否为空算法*/if (Q->rear=NULL) return(1);/*为空，则返回 true*/else return(0); /*不为空,则返回 f

18、lase*/ _ _void dispqueue(LinkQueue *Q)/*显示队列中元素算法*/struct node *p=Q->rear->next;printf (，?队列元素:");while (p!:zQ->rear)printf (/z%c "、p->data);p=p->next;printfp->data);六、完成：实验2一栈、队列、递归程序设计 根据实验要求(见教材P2O3)认真完成本实验，并提交实验报告。作业3答案（本部分作业覆盖教材第6-7章的内容）一.单项选择题1.B2B3D4. C5B6. A7. A 8

19、. C 9. A 10. D11.A12. C13. C14. B15. B16.C17. B 18. C 19. A 20. B21.D22. B23. B24. B25. C26.A27. A 28. C二.填空题1.子树树木或后继结点数2 树中所有结点的度的最大值3. 分支结点4. 叶子结点5. 子树的根非终端结点终端结点后继结点孩子结点6. 祖先7. 树中结点的最大层数8 Llog2nJ+l9 根结点左子树右子树10. 左子树根结点右子树11. 左子树右子树根结点12. 权13. 带权路径长度之和14. 最优二叉树最小的二叉树15. 6916. 2m-117. 多对多1&所有顶

20、点一次19. 先序20. 按层次21. n222. 邻接矩阵邻接表23. 2(n-l)24. nl25. 栈三、综合题1. 写出如下图所示的二叉树的先序、中序和后序遍历序列。答：二叉树的左义是递归的，所以，一棵二叉树可看作由根结点，左子树和右子树这三个基本部分组 成，即依次遍历整个二叉树，又左子树或者右子树又可看作一棵二叉树并继续分为根结点、左子树和右子 树三个部分，这样划分一直进行到树叶结点。(1) 先序为“根左右”，先序序列为：fdbaccgihl(2) 中序为“左根右”，中序序列为：abcdefghij(3) 后序为“左右根S后序序列为：acbedhjigf2已知某二叉树的先序遍历结果是

21、：A, B, D, G, C, E, H, L, I, K, M, F和J,它的中序遍历 结果是：G, D, B, A, L, H, E, K, I, M, C, F和J,请画岀这棵二叉树，并写出该该二叉树后续遍 历的结果。(1) 二叉树图形表示如下：(2) 该二叉树后序遍历的结果是：G、D、B、L、H、K. M. L E、J. F、C和A°3答（1）已知深度为k的二叉树最多有2k-l个结点（K21）,29-1<892<210.1,故树的高度为10（2）对于完全二叉树来说，度为1的结点只能是0或1因为 n=n0+nl+n2 和 n0=n2+l得：设nl=0, 892=n0

22、+0+n2=2n2+l得n2不为整数出错设 nl=h 892=n0+1 +n2=2n2+2得 n2 =445-* n0=n2+1=446叶子结点数为446。（3）由得单支结点数为1（4）对于n个结点的完全二叉树，最后一个树叶结点，即序号为n的叶结点其双亲结点 即为最后 一个非终端结点，序号为 892/2=446。4.（1）先序序列和中序序列相同的二叉树为空树或任一结点均无左孩子的非空二叉树（2）中序和后序序列相同的二叉树为空树或任一结点均无右孩子的非空二叉树（3）先序和后序序列相同的二叉树为空树或仅有一个结点5.（1）哈夫曼树如图B4所示。图B4(2) 其带权路径长度WPL值为270。(3)

23、每个字符的哈夫曼编码为:A: 100, B: 11, C: 1010, D:000, E:0010, F: 10110, G: 1011 h H:0011.1：016答(1) 深度优先遍历:vl,v2,v3,v&v5,v7,v4,v6广度优先通历：vl,v2,v4,v6,v3,v5,v7,v8(2) G 的拓扑序列为：vl,v2,v4,v6,v5,v5,v3,v5,v7,v8(3) 最短路径为：vl,2v5,v7,v87. gl的图示和图gl的邻接表如下图所示。vl图G 图G的邻接矩阵如下图所示：厂0101010011000111110001100丿图G的邻接矩阵vlv2v3v4v52

24、4A1445A2I I IJ2图G的邻接表 VI、V2、V3、V4、V5 的度分别为：2, 3, 2, 3, 2四、程序分析题1 return cl+1(2) NodeLevel(BT->right,X)(3) (c2>=l) return c2+l2. (l)for(j=0; j<n; j+)(2) dfstree (GA, j, n);五. 算法设计题1. 写一个将一棵二叉树复制给另一棵二叉树的算法。define NULL 0typedef struct btnodeelemtype data;struct btnode *lchild, *rchild;bitnode,

25、 *bitree;bitree *CopyTree( bitnode *p )/*复制一棵二叉树*/bitnode *t:if ( p!=NULL ) t=(bitnode *)malloc (sizeof (bitnode): t->data=p->data;t->lchild=CopyTree(p->lchild);t->rchild=CopyTree(p->rchild); return(t);elsereturn(NULL);/*CopyTree*/int BTreeLeafCount(struct BTreeNode* BT)if(BT=NULL)

26、 return 0;else if(BT->left=NULL && BT->nght=NULL) return 1;else return BTreeLeafCount(BT">left)+BTreeLeafCount(BT->right);六、完成：实验3一栈、队列、递归程序设计 实验4图的存储方式和应用根据实验要求（见教材P2O3）认真完成本实验，并提交实验报告。作业4答案（本部分作业覆盖教材第8-9章的内容）一、单项选择题1. D2C3B4. C 5 D6 A7C8D9. B10D11C12. C13. A14. C 15. D 16.

27、 B17. B18. D19. D20. A21D22. D23. A24. A 25. C 26. C27. B28. A29. B30. C二、填空题1. 哈希表查找法2. 数据项的值记录3. 主关键字4. 数学期望值5. 顺序6. 二分查找升序或降序排列7. 顺序存储结构&索引顺序査找顺序査找9. 均小于根结点的值均大于根结点的值二叉排序树10. 自变量 函数值11. 9, 14,16 , 1712. 内部排序外部排序13. 交换排序14. 315. 4 816. 堆排序快速排序17. 主关键字18. 关键字相等的记录19.19. 堆尾堆顶向下三、综合题1. 已知序列(70, 8

28、3, 100, 65, 10, 32, 7. 9),请写岀对此序列采用插入排序法进行升序排序时 各趟的结果。答：原始序列：(70), 83, 100, 65, 10, 32, 7, 9第 1 趟：(70, 83), 100, 65, 10, 32, 7, 9第2趟:(70,83,100), 65, 10,32,7,9第3趟：(65,70,83,100), 10,32,7,9第4趟：(10,65,70,83, 100),32,7,9第5趟：(10,32,65,70, 83, 100),7,9第6趟：(7,10,32,65, 70, 83,100),9第7趟:(7,9, 10, 32, 65, 7

29、0,83,100)2. 已知序列(10, 18, 4, 3, 6, 12, h 9, 15, 8),请写出对此序列采用归并排序法进行升序排序 时各趟的结果。答：原始序列：10, 18, 4, 3, 6, 12, 1, 9, 15, 8第 1 趟：10, 183, 46, 121, 98, 15第 2 趟:3, 4, 10, 18, 1, 6, 9, 128, 15第 3 趟：3, 4, 10, 1& 1, 6, 8, 9, 12, 15第 4 趟：L 3, 4, 6, 8, 9, 10, 12, 15, 18J3已知序列(17, 18, 60, 40, 7, 32, 73, 65, 8

30、5)采用冒泡排序法排序的各趟的结果如下:原始初始：17, 18, 60, 40, 7, 32, 73, 65, 85第1趟：17,18,40,7,32, 60,65,73,85第2趟：17,18,7,32,40, 60,65,73,85第3趟：17,7,18,32,40, 60,65,73,85第4趟：7,17,18,32,40, 60,65,73,85第5趟：7,17,18,32,40, 60,65,73,854. 已知序列(503, 87, 512, 61, 908, 170, 897, 275, 653, 462)请给出釆用快速排序法对该序 列作升序排列时的每一趟结果。原始序列：503,

31、 87, 512, 61, 908, 170, 897, 275, 653, 462第 1 趟：462, 87, 275, 61, 170)503(897, 908, 653, 512第 2 趟：170, 87, 275, 61 462, 503(897, 908, 653, 512第 3 趟：87, 61170275 462> 503(897, 908, 653, 512第 4 趟：61 87170275 462, 503(897, 908, 653, 512第 5 趟:61 , 87, 170, 275 462, 503(897, 908, 653, 512第6趟：61 ,87. 1

32、70, 275, 462, 503(897, 908, 653, 512第7趟：61 ,87, 170, 275, 462, 503(512, 653897908第8趟：61 ,87, 170, 275, 462, 503, 512, 653 897(908第9趟：61 ,87, 170, 275, 462, 503, 653, 897(908第10趟：61 ,87, 170, 275, 462, 503, 653, 897, 9085. 设一组记录的关键字序列为（49, 83, 59, 41. 43, 47）,采用堆排序算法完成以下操作：（要求 小根堆，并画岀中间过程）（1）以二叉树描述6个

33、元素的初始堆（2）以二叉树描述逐次取走堆顶元素后，经调整得到的5个元素、4个元素的堆 答：（1）(1)原序列1615205364715162053764nl趟15162075364n-j次151672053641571620536471516205364(3)平均査找长度二(1*1+2*2+3*3) /6=14/6中序遍历：2, 3, 4, 5, 6, 7, 14, 16, 18四、程序填空题(1) (Dj>=o<2)aj(3) j(4) temp2.(1) j<=n-l(2) i<=n-j(3) ai=ai+l(4) ai+l=temp(5) 当某趟冒泡中没有出现交换

34、则已排好序结朿循环。五. 算法设计题1.编写折半查找算法。折半査找算法如下：int Binary_Search (NODE a, int n, int k)*在肛0到an-l中.用折半査找算法査找关键字等于k的记录.査找成功返回该记录的下标，失败时返回-1*/int low, mid, high;low=0;high=n-l;while(low<=high)/*查找成功，返回查找到的记录的下标权/*収后半査找区间*/*取前半査找区何*/*查找失败*/mid=(low+high)/2; if(amid. key=k) return mid;else if(amidkey<k) low

35、=mid+l;else high=mid-l;return T;2. 编写顺序查找算法。顺序査找算法如下：int search (NODE a J, int n, int k)/*在a0a旷1中顺序査找关键字等于k的记录。查找成功时返回该记录的下标，失败时返回-1*/int i=0;while(i<n && ai.key!=k) /*没有査到同时査找过程没有结束则继续查找*/ i卄；if (aij. key=k)/*査找成功*/return i;else return T;/*査找失败*/六、完成：实验3一栈、队列.递归程序设计 实验4图的存储方式和应用根据实验要求（见教材P2O3）认真完成本实验，并提交实验报告。