数据结构形考作业答案.docx
- 文档编号:16462135
- 上传时间:2023-07-13
- 格式:DOCX
- 页数:53
- 大小:390.06KB
数据结构形考作业答案.docx
《数据结构形考作业答案.docx》由会员分享,可在线阅读,更多相关《数据结构形考作业答案.docx(53页珍藏版)》请在冰点文库上搜索。
数据结构形考作业答案
形考作业一
题目1
把数据存储到运算机中,并具体表现数据元素间的逻辑结构称为()°
选择一项:
CA.逻辑结构
CB.给相关变量分派存储单元
CC.算法的具体实现
”D.物理结构
题目2
以下说法中,不正确的选项是()0
选择一项:
厂A.数据可有假设干个数据元素组成
CB.数据元素是数据的大体单位
CC.数据项是数据中不可分割的最小可标识单位
QD.数据项可由假设干个数据元素组成
題目3
一个存储结点存储一个()。
选择一项:
厂A.数据结构
CB.数据类型
CC.数据项
QD.数据元素
题目4
数据结构中,与所利用的运算机无关的是数据的()。
选择一项:
CA.物理结构
“B.逻辑结构
CC.物理和存储结构
「D.存储结构
題目5
以下的表达中,不属于算法特性的是()。
选择一项:
CA・有穷性
B.可行性
C.可读性
D.输入性
題目6
正确
取得分中的分
'A.研究算法中的输入和输出的关系
CB.分析算法的易懂性和文档性
介C.分析算法的效率以求改良
「D.找出数据结构的合理性
題目7
算法指的是()。
选择一项:
「A.排序方式
CB.解决问题的计算方式
CC.运算机程序
“D.解决问题的有限运算序列
题目8
算法的时刻复杂度与()有关。
选择一项:
CA.所利用的运算机
CB.数据结构
3C.算法本身
「D.运算机的操作系统
題冃9
设有一个长度为n的顺序表,要在第i个元素之前(也确实是插入元素作为新表的第i个元素),插入一个元素,那么移动元素个数为()。
选择一项:
"A.n-i+1
CB.n-i-1
CC.n-i
「D.i
题目10
设有一个长度为n的顺序表,要删除第i个元素移动元素的个数为()。
CC.n-i+1
「D.i
題目11
).
在一个单链表中,P、q别离指向表中两个相邻的结点,且q所指结点是P所指结点的直接后继,现要删除q所指结点,可用语句(
C.q->next=NULL
C
D.p->next=q
題目12
在一个单链表中P所指结点以后插入一个s所指的结点时,可执行()
选择一项:
「A.p=s->next
C
B.p->next=s;s->next=p->nextC
C.p->next=s->next;
D.s->next=p->next:
p->next=s;
題目13
非空的单向循环链表的尾结点知足()(设头指针为head,指针p指向尾结点)。
选择一项:
「A.p==head「B.p==NULL
C.p->next==head「D.p->next==NULL
題目14
)。
链表不具有的特点是(
題目15
带头结点的链表为空的判左条件是()(设头指针为head).
选择一项:
A.head->next==NULL
B.head->next==head
C.head==NULL
D.head!
=NULL
题目16
在一个长度为n的顺序表中为了删除第5个元素,由第6个元素开始从后到前依次移动了15个元素。
那么原顺序表的长度为()。
选择一项:
A.21
B.19
C.20
D.25
題目17
有关线性表的正确说法是()。
选择一项:
A.表中的元素必需按由小到大或由大到下排序
B.除一个和最后一个元素外,其余元素都有一个且仅有一个直接前驱和一个直接后
继
C.线性表至少要求一个元素
D.每一个元素都有一个直接前驱和一个直接后继
題目18
向一个有127个元素的顺序表中插入一个新元素,并维持原先的顺序不变,平均要移动()个元素。
选择一项:
A.8
B.7
C.63
D.
題目19
一个顺序表第一个元素的存储地址是90,每一个元素的长度为2,那么第6个元素的地址是()°
选择一项:
A.102
B.98
C.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->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(l£i£n+l)个元素之前插入新元素时,需向后移动回答个数据元素。
题目22
从长度为n的釆纳顺序存储结构的线性表中删除第i(l£i£n+l)个元素,需向前移动回答
I个元素。
题目23
数据结构按结点间的关系,可分为4种逻辑结构:
集合、—线性结构、
、—树形结构、—图状结构。
题目24
数据的逻辑结构在运算机中的表示称为存储结构或物理结构
題目25
除第1个和最后一个结点外,其余结点有且只有一个前驱结点和后继年点的数据结构为回答pw丽,每一个结点可有任意多个前驱和后继结点数的结构为回答而1
O
答案:
线性结构,非线性结构
题目26
数据结构中的数据元素存在多对多的关系称为回答结构。
题目27
结构。
数据结构中的数据元素存在一对多的关系称为回答I树懊
线性结构
題目28
结构。
数据结构中的数据元素存在一对一的关系称为回答I
題目29
要求在n个数据元素中找其中值最大的元素,设大体操作为元素间的比较。
那么比较的次数和算法的时刻复杂度别离为_n-1和_0(n)o
題目30
在一个单链表中P所指结点以后插入一个S所指结点时,应执行回答
s-/,ne>:
t=p->next:
和p->next=s;的操作o
题目31
设有一个头指针为head的单向循环链表,p指向链表中的结点,假设p->next=回答
I,那么P所指结点为尾结点。
題目32
在一个单向链表中,要删除P所指结点,已知q指向P所指结点的前驱结点。
那么能够用
正确答案是:
q->next=p->next;
题目33
设有一个头指针为head的单向链表,p指向表中某一个结点,且有p->next=二NULL,通过
操作回答,就可使该单向链表构形成单向循环链表。
正确答案是:
p->next=head;
題目34
单向循环链表是单向链表的一种扩充,当单向链表带有头结点时,把单向链表中尾结点的指针域由空指针改成回答:
当单向链表不带头结点时,那么把单向链表中尾结点
的指针域由空指针改成指向回答。
答案:
头结点的指针、指向第一个结点的指针
題目35
线性链表的逻借关系是通过每一个结点指针域中的指针来表示的。
其逻辑顺序和物理存储
顺序再也不一致,而是一种回答I存储结构,又称为回答I。
答案:
链式、链表
三、问答题(第1小题7分,第2小题8分)
题目36
简述数据的逻借结构和存储结构的区别与联系,它们如何阻碍算法的设讣与实现?
答:
假设用结点表示某个数拯元素,那么结点与结点之间的逻借关系就称为数据的逻辑结构。
数据在运算机中的存储表示称为数据的存储结构Q可见,数据的逻辑结构是反映数据之间的固有关系,而数据的存储结构是数据在运算机中的存储表示。
尽管因采纳的存储结构不同,逻辑上相邻的结点,其物理地址未必相同,但可通过结点的内部信息,找到瓦相邻的结点,从而保留了逻辑结构的特点。
采纳的存储结构不同,对数据的操作在灵活性,算法复杂度等方而不同较大。
题目37
说明顺序存储结构和链式存储结构的特点,并比较顺序存储结构和链式存储结构的优缺点。
答:
顺序结构存储时,相邻数据元素的寄存地址也相邻,即逻辑结构和存储结构是统一的,要求内存中存储单元的地址必需是持续的。
优势:
一样情形下,存储密度大,存储空间利用率高。
缺点:
(1)在做插入和删除操作时,需移动大量元素;
(2)由于无法计算,必需预先分派较大的空间,往往使存储空间不能取得充分利用:
(3)表的容量难以扩充。
链式结构存储时,相邻数据元素可随意寄存,所占空间分为两部份,一部份寄存结点值,另一部份寄存表示结点间关系的指针。
优势:
插入和删除元素时很方便,利用灵活。
缺点:
存储密度小,存储空间利用率低。
四、程序填空题(每空1分,共15分)
題目38
以下是用尾插法成立带头结点的且有n个结点的单向链表的算法,请在空格内填上适当的语句。
NODE*createl(n)
/*对线性表(1,2小),成立带头结点的单向链表♦/
NODE*head,*p,*q;
inti;
p=(NODE*)malloc(sizeof(NODE));head=p;q=p;p_>next二NULL;
for(i=l;i<=n;i++)
p=(NODE*)malloc(sizeof(NODE));
回答Ip_>data=i
回答Iq'>next=p
回答IK
}
return(head);
}
题目39
以下是用头插法成立带头结点的且有n个结点的单向链表的算法,请在空格内填上适当的语句。
NODE*create2(n)
/*对线性表(n,n-11),成立带头结点的线性链表*/
{
NODE*head,*p,*q;
inti;
p=(NODE*)malloc(sizeof(NODE));
回答IK
p->next=NULL;
回答Iq=P
for(i=l;i<=n;i++)
p=(NODE*)malloc(sizeof(NODE));
p->data=i;
辻(i==l)
回答Ip->next=XULL
else
回答I
}
return(head);
}
题目40
以下是在具有头结点单向链表中删除第i个结点的算法,请在空格内填上适当的语句。
intdelete(NODE*head,inti)
{
NODE*p,*q;
intj;
q=head;
j二0;
while((q!
二NULL)&&(j q指向它*/ 回答Iq=q_>next } if(q二二NULL)return(0); 回答帀E 回答|q->next=p->next free(p); return (1); } 题目41 以下是在具有头结点单向列表中在第i个结点之前插入新结点的算法,请在空格内填上适当的语句。 intinsert(NODE*head,intx,inti) { NODE*q,*p; intj; q二head; j二0; wh订e((q! =NULL)&&(j {q=q->next: j卄;} if(q==NULL)return(0); -回姣 p->data=x; 正确 正确答案是: p->next=q->next取得分中的分 回答Iq_>next=p return (1); } 形考任务2 题目1 假设让元素1,2,3依次进栈,那么出栈顺序不可能为()。 选择一项: A.2,b3 B.3,L2 C.3,2,1 题目2 一个队列的入队序列是1,2,3,4。 那么队列的输出序列是()。 选择一项: A.3,2,4,1 B.h2,3,4 C.4,3,2,1 D.L4,3,2 題目3 向顺序栈中压入新元素时,应当()。 选择一项: A.先存入元素,再移动栈顶指针 B.先移动栈顶指针,再存入元素 C.前后顺序无关紧要 D.同时进行 在一个栈顶指针为top的链栈中,将一个P指针所指的结点入栈,应执行()。 选择一项: r C.p->next=top->next;top=top->next;r D.p->next=top->next;top->next=p; 題目5 在一个栈顶指针为top的链栈中删除一个结点时,用X保留被删结点的值,那么执行(). 选择一项: "A.x=top->data;top=top->next: r B.x=top->data; r C.top=top->next;x=top->data;r D.x=top;top=top->next; 题目6 判立一个顺序队列(最多元素为m)为空的条件是( 选择一项: 「A.rear=m-lr B.front==rear+l (i C.front==rear 题目7 )0 判左一个循环队列Q(最多元素为m)为满的条件是( C.Q->front==(Q->rear+1)%m 「D.Q->front=Q->rear+1 題目8 判定栈满(元素个数最多n个)的条件是( 选择一项: r A.top==0 B.top! =0 C.top=-l D.top==n-l 设有一个20阶的对称矩阵A(第一个元素为芯,),采纳紧缩存储的方式,将其下三角部份以行序为主序存储到一维数组B中(数组下标从1开始),那么矩阵元素弘二在一维数组B中的下标是()。 选择一项: C.21 D.28 題目10 在解决运算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区,主机将要输岀的数据依次写入缓冲区中,而打印机那么从缓冲区中掏出数据打印,该缓冲区应该是一个()结构。 选择一项: C.数组 D.堆栈 题目11 一个递归算法必需包括()O 选择一项: A.递归部份 B.迭代部份 C.终止条件和迭代部份 D.终止条件和递归部份 题目12 在一个链队中,假设f和r别离为队头和队尾指针,那么删除一个结点的运算为()。 选择一项: A.f=r->next; B.r=r->next; C.r=f->next; D.f=f->next; 题目13 在一个链队中,假设f和r别离为队头和队尾指针,那么插入s所指结点的运算为 ()。 选择一项: A.s->next=r;r=s; B.r->next=s;r=s; C.s«>next=f;f=s; D.f->ncxt=s;f=s; 题目14 数组3经初始化chara[]=“English”;a[7]中寄存的是()° 选择一项: A.HhM B.字符串的终止符 C.变量h D.字符h 題目15 设主串为“ABcCDABcdEFaBc”,以下模式串能与主串成功匹配的是()。 选择一项: A.BCd B.Bcd C.Abe D.ABC 題目16 字符串al='AEIJING\a2=/zAEI\a3="AEFANG",a4「AEFI"中最大的是()。 选择一项: A.a3 B.al C.a4 D.a2 题目17 两个字符串相等的条件是()。 选择一项: A.两串的长度相等,而且对应位置上的字符相同 B.两串的长度相等 C.两串的长度相等,而且两串包括的字符相同 D.两串包括的字符相同 一维数组A采纳顺序存储结构,每一个元素占用6个字节,第6个元素的存储地址为100,那么该数组的首地址是()o 选择一项: A.64 B.90 D.70 题目19 一个非空广义表的表头()。 选择一项: A.能够是子表或原子 c B•只能是原子 cc.不可能是原子 CD・只能是子表 C C C 題目20 对稀疏矩阵进行紧缩存储,可采纳三元组表,一个10行8列的稀疏矩阵A,其相应的三元组表共有6个元素,矩阵A共有()个零元素。 选择一项: A.8 B.10 C.72 (5- D.74 题目21 对稀疏矩阵进行紧缩存储,可釆纳三元组表,一个10行8列的稀疏矩阵A共有73个零元素,A的右下角元素为6,其相应的三元组表中的第7个元素是()。 选择一项: A.(10,8,7) B.(10,8,6) C.(7,10,8) D.(7,8,10) 题目22 对一个栈顶指针为top的链栈进行入栈操作,通过指针变量p生成入栈结点,并给 该结点赋值a,那么执行: p=(structnode*)malloc(sizeof(structnode): p- >data=a;和()。 选择一项: A.p->next=top;p=top; B.top->next=p;p=top; C.p->nex=top;top=p; D.top=top->next: pe=top; C (5- 題目23 头指针为h“d的带头结点的单向链表为空的判泄条件是()为真。 选择一项: A.head==NULL B.head->next==NULL C.head->next! =NULL D.head->next! =NULL 题目24 设有一个对称矩阵A,采纳紧缩存储的方式,将其下三角部份以行序为主序存储到一维数组B中(数组下标从1开始),B数组共有55个元素,那么该矩阵是()阶的对称矩 阵。 选择一项: A.20 B.15 C.10 D.5 题目25 数组a经初始化chara[]=“English”;a[l]中寄存的是()° 选择一项: A.HnM B.字符n C.MEM D.字符E 二、填空题(每题2分,共30分) 題目26 循环队列队头指针在队尾指针回答位豊,队列是“满”状态。 題目27 循环队列的引入,目的是为了克服回答。 判泄一个循环队列LU(最多元素为m)为空的条件是回答ILU_frOnt==LU_>rear。 题目29 题干 向一个栈顶指针为h的链栈中插入一个S所指结点时,可执行回答s->next=h;和h二S;操作。 (结点的指针域为next) 题目30 从一个栈顶指针为h的链栈中删除一个结点时,用X保留被删结点的值,可执行X二h-题目 31 在一个链队中,设f和r别离为队头和队尾指针,那么插入s所指结点的操作为回答和r=s;r->next=s;(结点的指针域为next) 題目32 在一个链队中,设f和: r别藹为队头和队尾指针,那么删除一个结点的操作为回答f二&>next;o(结点的指针域为next) 題目33 串是一种特殊的线性表,其特殊性表此刻组成串的数据元素都是回答 rw 题目34 : 空格串的长度是回答「空格字祢 題目35 设广义表L二((),()),那么表头是,表尾是,L的长度是 那么表头是(),表尾是(()),L的长度是Z 題目36 广义表A((a>b,c),(d,e,f))的表尾为回答((def))。 题目37 设有n阶对称矩阵A,用数组s进行紧缩存储,当j时,A的数组元素a,相应于数组s 的数组元素的下标为回答I讥卜1)卫幻。 (数组元素的下标从1开始) 对稀疏矩阵进行紧缩存储,矩阵中每一个非零元素对应的三元组包括该元素的、 和三项信息。 答案: 行下标、列下标和非零元素值 題目39 循环队列用a[0],…,乳7]的一维数组寄存队列元素,(采纳少用一个元素的模式),设 front和rear别离为队头和队尾指针,且front和rear的值别离为2和7,当前队列中 的元素个数是回答5。 題目40 循环队列的引入,目的是为了克服回答。 三、问答题(每题5分,共20分) 题目41 完成 总分值 题干 栈、队列和线性表的区别是什么? 答: 栈是一种先进后岀的线性表,栈的插入和删除操作都只能在栈顶进行,而一样的线性表能够在线性表的任何位置进行插入和删除操作。 队列是一种先进先出的线性表,队列的插入只能在队尾进行,队列的删除只能在队头进行,而一样的线性表能够在线性表的任何位置进行插入和删除操作。 題目42 设栈S和队列Q的初始状态为空,元素el,e2,e3,e4,e5和e6依次通过S,—个元素出栈后即进队列Q,假设6个元素出队的序列是e2,e4,e3,e6,e5,eb那么栈S的容量至少应该是多少? 出队序列是e2,e4,e3,e6,e5,el的进程: (10)e6出栈(栈底到栈顶元素是el,e5) (11)e5出栈(栈底到栈顶元素是el) (12)el出栈(栈底到栈顶元素是空) 栈中最多时有3个元素,因此栈S的容量至少是3。 題目43 有5个元素,英入栈顺序为: A.B、C、D、E,在各类可能的出栈顺序中,以元素C、D最先的顺序有哪几个? 从题中可知,要使C第一个且D第二个出栈,应是A入栈,B入栈,C入栈,C出栈,D入栈。 以后能够有以下几种情形: (1)B出栈,A出栈,E入栈,E出栈,输岀序列为: CDBAE。 (2)B出栈,E入栈,E出栈,A岀栈,输出序列为CDBEA. (3)E入栈,E出栈,B出栈,A出栈,输岀序列为CDEBA 因此可能的顺序有: CDBAE,CDBEA,CDEBA 題目44 简述广义表和线性表的区别和联系。 广义表是线性表的的推行,它也是n(n>0)个元素加,比,••“/,・・・,比的有限序列,其中直或是原子或是一个广义表。 因此,广义表是一种递归数据结构,而线性表没有这种特性,线性表能够看成广义表的特殊情形,当加都是原子时,广义表退化成线性表。 形考任务三 一、单项选择题(每题2分,共32分) 题目1 假泄一棵二叉树中,双分支结点数为15,单分支结点数为30,那么叶子结点数为 ()。 选择一项: A.17 B.16 C.15 D.47 题目2 二叉树第k层上最多有()个结点。 选择一项: C.2k-I D.2k 题目3 设某一二叉树先序遍历为abdec,中序遍历为dbeac,那么该二叉树后序遍历的顺序是(). 选择一项: A.abedc B.abdec C.debac D.debca 题目4 将含有150个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号,根结点的编号为1,那么编号为69的结点的双亲结点的编号为()。 选择一项: A.35 B.33 C.34 D.36 題目5 若是将给左的一组数据作为叶子数值,所构造岀的二叉树的带权途径长度最小,那么该树称为()。 选择一项: A.平稳二叉树 B.完全二叉树 C.二叉树 D.哈夫曼树 題目6 在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,那么度为0的结点个数为()。 选择一项: A.5 B.4 C.7 D.6 題目7 在一棵度具有5层的满二叉树中结点总数为()。 选择一项: A.31 B.32 C.16 D.33 題目8 利用n个值作为叶结点的权生成的哈夫曼树中共包括有()个结点。 选择一项: A.n+1 B.2*
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 作业 答案