数据结构本形考作业答案.docx

1、形考作业一题目 1把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（ ）。选择一项：A. 逻辑结构B. 给相关变量分配存储单元C. 算法的具体实现D. 物理结构 题目 2下列说法中，不正确的是（ ）。选择一项：A. 数据可有若干个数据元素构成B. 数据元素是数据的基本单位C. 数据项是数据中不可分割的最小可标识单位D. 数据项可由若干个数据元素构成 题目 3一个存储结点存储一个（ ）。选择一项：A. 数据结构B. 数据类型C. 数据项D. 数据元素 题目 4数据结构中，与所使用的计算机无关的是数据的（ ）。选择一项：A. 物理结构B. 逻辑结构 C. 物理和存储结构D. 存储结构题目

2、5下列的叙述中，不属于算法特性的是（ ）。选择一项：A. 有穷性B. 可行性C. 可读性 D. 输入性题目 6正确获得 2.00 分中的 2.00 分A. 研究算法中的输入和输出的关系B. 分析算法的易懂性和文档性C. 分析算法的效率以求改进 D. 找出数据结构的合理性题目 7算法指的是（ ）。选择一项：A. 排序方法B. 解决问题的计算方法C. 计算机程序D. 解决问题的有限运算序列 题目 8算法的时间复杂度与（ ）有关。选择一项：A. 所使用的计算机B. 数据结构C. 算法本身 D. 计算机的操作系统题目 9设有一个长度为 n 的顺序表，要在第 i 个元素之前（也就是插入元素作为新表的第

3、i 个元素），插入一个元素，则移动元素个数为（ ）。选择一项：A. n-i+1 B. n-i-1C. n-iD. i题目 10设有一个长度为 n 的顺序表，要删除第 i 个元素移动元素的个数为（ ）。选择一项：A. n-i B. n-i-1C. n-i+1D. i题目 11在一个单链表中，p、q 分别指向表中两个相邻的结点，且 q 所指结点是 p 所指结点的直接后继，现要删除 q 所指结点，可用语句（ ）。选择一项：A. p-next=q-next B. p=q-nextC. q-next=NULLD. p-next=q题目 12在一个单链表中 p 所指结点之后插入一个 s 所指的结点时，可执

4、行（ ）。选择一项：A. p=s-nextB. p-next= s; s-next= p-nextC. p-next=s-next;D. s-next=p-next; p-next=s; 题目 13非空的单向循环链表的尾结点满足（ ）（设头指针为 head，指针 p 指向尾结点）。选择一项：A. p= headB. p=NULLC. p-next=head D. p-next=NULL题目 14链表不具有的特点是（ ）。选择一项：A. 可随机访问任一元素 B. 插入删除不需要移动元素C. 不必事先估计存储空间D. 所需空间与线性表长度成正比题目 15带头结点的链表为空的判断条件是（ ）（设头指

5、针为 head）。选择一项：A. head-next=NULL B. head-next=headC. head =NULLD. head!=NULL题目 16在一个长度为 n 的顺序表中为了删除第 5 个元素，由第 6 个元素开始从后到前依次移动了15 个元素。则原顺序表的长度为（ ）。选择一项：A. 21B. 19C. 20 D. 25题目 17有关线性表的正确说法是（ ）。选择一项：A. 表中的元素必须按由小到大或由大到下排序B. 除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继 C. 线性表至少要求一个元素D. 每个元素都有一个直接前驱和一个直接后继题目 18

6、向一个有 127 个元素的顺序表中插入一个新元素，并保持原来的顺序不变，平均要移动（ ）个元素。选择一项：A. 8B. 7C. 63D. 63.5 题目 19一个顺序表第一个元素的存储地址是 90，每个元素的长度为 2，则第 6 个元素的地址是（ ）。选择一项：A. 102B. 98C. 100 D. 106题目 20在双向循环链表中，在 p 所指的结点之后插入指针 f 所指的新结点，其操作步骤是（ ）。选择一项：A. f-prior=p; f-next=p-next; p-next=f;p-next-prior=f;B. p-next=f;f-prior=p;p-next-prior=f;f

7、-next=p-next;C. f-prior=p; f-next=p-next; p-next-prior=f; p-next=f; D. p-next=f; p-next-prior=f;f-prior=p;f-next=p-next;二、填空题（每小题 2 分，共 30 分）题目 21在一个长度为 n 的顺序存储结构的线性表中，向第 i(1in+1)个元素之前插入新元素时，需向后移动回答 n-i+1 个数据元素。题目 22从长度为 n 的采用顺序存储结构的线性表中删除第 i(1in+1)个元素，需向前移动回答n-i 个元素。题目 23数据结构按结点间的关系，可分为 4 种逻辑结构：_集合

8、_、_线性结构、_、_树形结构_、_图状结构_。题目 24数据的逻辑结构在计算机中的表示称为_存储结构_或_物理结构_。题目 25除了第 1 个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的数据结构为回答 线 性 结 构 ，每个结点可有任意多个前驱和后继结点数的结构为回答 非 线 性 结。答案：线性结构，非线性结构题目 26数据结构中的数据元素存在多对多的关系称为回答 图 状 结 构 结构。题目 27数据结构中的数据元素存在一对多的关系称为回答 树 形 结 构 结构。题目 28数据结构中的数据元素存在一对一的关系称为回答 线 性 结 构 结构。题目 29要求在 n 个数据元素中找其

9、中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为_ n-1_和_ O(n)_。题目 30在一个单链表中 p 所指结点之后插入一个 s 所指结点时，应执行回答s-next=p-next; 和 p-next=s;的操作。题目 31设有一个头指针为 head 的单向循环链表，p 指向链表中的结点，若 p-next=回答head ，则 p 所指结点为尾结点。题目 32在一个单向链表中，要删除 p 所指结点，已知 q 指向 p 所指结点的前驱结点。则可以用操作回答 。正确答案是：q-next=p-next;题目 33设有一个头指针为 head 的单向链表，p 指向表中某一个

10、结点，且有 p-next= =NULL，通过操作回答 ，就可使该单向链表构形成单向循环链表。正确答案是：p-next=head;题目 34单向循环链表是单向链表的一种扩充，当单向链表带有头结点时，把单向链表中尾结点的指针域由空指针改为回答 ；当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向回答 。答案：头结点的指针、指向第一个结点的指针题目 35线性链表的逻辑关系是通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种回答 存储结构，又称为回答 。答案：链式、链表三、问答题（第 1 小题 7 分，第 2 小题 8 分）题目 36简述数据的逻辑结构和存

11、储结构的区别与联系，它们如何影响算法的设计与实现？答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中的存储表示称为数据的存储结构。可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示。尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大。题目 37解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。答：顺序结构存储时，相邻数据元素的存放地址也相邻

12、，即逻辑结构和存储结构是统一的，要求内存中存储单元的地址必须是连续的。优点：一般情况下，存储密度大，存储空间利用率高。缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。优点：插入和删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低。四、程序填空题（每空 1 分，共 15 分）题目 38下列是用尾插法建立带头结点的且有 n 个结点的单向链表的算法，请在空格内填上适当的语句。N

13、ODE *create1(n)/* 对线性表(1,2,.,n),建立带头结点的单向链表 */NODE *head,*p,*q;int i;p=(NODE *)malloc(sizeof(NODE);head=p; q=p; p-next=NULL;for(i=1;idata=i; 回答 p-next=NULL;回答 q-next=p;回答 q=p; return(head);题目 39下列是用头插法建立带头结点的且有 n 个结点的单向链表的算法，请在空格内填上适当的语句。NODE *create2(n)/*对线性表(n,n-1,.,1),建立带头结点的线性链表 */NODE *head,*p,

14、*q;int i;p=(NODE *)malloc(sizeof(NODE);回答 head=p;p-next=NULL;回答 q=p;for(i=1;idata=i;if(i=1) 回答 p-next=NULL;else回答 p-next=q-next;回答 q-next=p;return(head);题目 40下列是在具有头结点单向链表中删除第 i 个结点的算法，请在空格内填上适当的语句。int delete(NODE *head,int i)NODE *p,*q;int j;q=head;j=0;while(q!=NULL)j+;if(q=NULL)return(0);回答 p=q-next回答 q-next=p-next;free(p);return(1);题目 41下列是在具有头结点单向列表中在第 i 个结点之前插入新结点的算法，请在空格内填上适当的语句。int insert(NODE *head,int x,int i)NODE *q,*p;int j;q=head;j=0;while(q!=NULL)j+; if(q=NULL) return(0); p=回答 (NODE *)malloc(sizeof(NODE);p-data=x;回答 p-next=q-next正确正确答案是：p-next=q-next获得 1.00 分中的 1.00 分;