2017年电大电大数据结构(本)形成性考核册(作业1-4)原题带答案

1、1数据结构（本）课程作业作业 1A.head = =NULLB . head-next= =NULLC . head-next= =headD . head!=NULL16 .在一个单链表中，p、q 分别指向表中两个相邻的结点，且q 所指结点是 p 所指结点的直接后继，现要删除q 所指结点，可用语句（C）oA . p=q-nextB . p-next=qC . p-next=q-nextD . q-next=NULL17 .在一个链队中，假设 f 和 r 分别为队头和队尾指针，则删除一个结点的运算为（C）oA . r=f-n ext;B. r=r- next;C . f=f-n ext;D.

2、f=r-n ext;18 .在一个链队中，假设 f 和 r 分别为队头和队尾指针，则插入 s 所指结点的运算 为（B）oA . f-next=s;仁 s;B. r-next=s;r=s;C. s-next=r;r=s; D . s-next=f;仁 s;19. 一个顺序表第一个元素的存储地址是90,每个元素的长度为 2,则第 6个元素的 地址是（B ）oA . 98 B . 100 C . 102 D . 10620 .有关线性表的正确说法是（ D）oA.每个元素都有一个直接前驱和一个直接后继B.线性表至少要求一个元素C. 表中的元素必须按由小到大或由大到下排序D. 除了一个和最后一个元素外，

3、其余元素都有一个且仅有一个直接前驱和一 个直接后继二、填空题1 .在一个长度为 n 的顺序存储结构的线性表中，向第 i（1 勺虫+1）个元素之前插入新元素时，需向后移动_n-i+1_个数据元素。2.从长度为 n 的采用顺序存储结构的线性表中删除第i（1 卫切+1）个元素，需向前 移动_ n-i_个元素。3.数据结构按结点间的关系，可分为 4 种逻辑结构： _集合_、线性结构_、树形结构_、_图状结构_o4.数据的逻辑结构在计算机中的表示称为_物理结构_或_存储结构_o5 .除了第 1 个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的数（本部分作业覆盖教材第 1-2 章的内容）一、单

4、项选择题1.在数据结构中，从逻辑上可以把数据结构分为（ C ）。A .动态结构和静态结构B .紧凑结构和非紧凑结构C .线性结构和非线性结构D.内部结构和外部机构2 .下列说法中，不正确的是（D ）oA .数据元素是数据的基本单位B .数据项是数据中不可分割的最小可标识单位C .数据可有若干个数据元素构成D .数据项可由若干个数据元素构成3 .一个存储结点存储一个（B）oA .数据项B .数据元素C .数据结构D .数据类型4 .数据结构中，与所使用的计算机无关的是数据的（C ）A .存储结构B .物理结构C.集合D.非集合8. 算法的时间复杂度与（C ）有关。A .所使用的计算机 B .与计

5、算机的操作系统C.与算法本身D .与数据结构9. 设有一个长度为 n 的顺序表，要在第 i 个元素之前（也就是插入元素作为新表的 第 i个元素），则移动元素个数为（ A ）oA . n-i+1B. n-iC. n-i-1D. i10.设有一个长度为 n 的顺序表，要删除第 i 个元素移动元素的个数为（ B ）A . n-i+1B. n-iC. n-i-1D. i11.在一个单链表中，指结点的直接后继，现要删除A . p=q-next B .12 .在一个单链表中p、q 分别指向表中两个相邻的结点，且 q所指结点，可用语句（p-next=q Cq 所指结点是 p 所C）op 所指结点之后插入一个

6、p-n ext=q n ext D . q-n ext=NULLs 所指的结点时，可执行（D ）C .逻辑结构D.物理和存储结构5 .下列的叙述中，不属于算法特性的是（ D ）A .有穷性C .可行性6.算法分析的目的是（CA.找出数据结构的合理性C .分析算法的效率以求改进7.数据结构是一门研究计算机中B .输入性D.可读性）。B .研究算法中的输入和输出的关系D .分析算法的易懂性和文档性（B ）对象及其关系的科学。A .数值运算B.非数值运算A . p-next= s; s next= p nextC . p=s-next13.非空的单向循环链表的尾结点满足点）oA. . P-next=

7、 =NULLC . P-next= =head14.链表不具有的特点是（A）oA .可随机访问任一元素C .不必事先估计存储空间15.带头结点的链表为空的判断条件是（B. p-next=s next;D . s-next=p-next; p-next=s;（C ）（设头指针为 head,指针 p 指向尾结B . P= =NULLD. P= = headB.插入删除不需要移动元素D.所需空间与线性表长度成正比B ）（设头指针为 head）o2据结构为 _线性结构_，每个结点可有任意多个前驱和后继结点数的结构为_ 非线性结构_o36.算法的 5 个重要特性是有穷性、确定性、 可形性、有零个或多个输

8、入_有零个或多个输出_。7.数据结构中的数据元素存在多对多的关系称为图状结构结构。8.数据结构中的数据元素存在一对多的关系称为_树形结构_结构。9.数据结构中的数据元素存在一对一的关系称为_线性结构_结构。10.要求在 n 个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则 比较的次数和算法的时间复杂度分别为 n-1_和0(n)_。11.在一个单链表中 p 所指结点之后插入一个 s 所指结点时，应执行_s-next=p-next_ 禾口 p-next=s;的操作。12.设有一个头指针为head的单向循环链表， p指向链表中的结点， 若 p-next= =_ head_，贝 U p 所

9、指结点为尾结点。13.在一个单向链表中，要删除p 所指结点，已知 q指向 p 所指结点的前驱结点。贝 U 可以用操作 _ q-next=p-next _。14.设有一个头指针为 head 的单向链表，p 指向表中某一个结点，且有p-next= =NULL,通过操作_ p-next=head _就可使该单向链表构造成单向循环链表。15 .每个结点只包含一个指针域的线性表叫 _单链表_。16 .线性表具有_顺序存储_和_链式存储_两种存储结构。17 .数据的逻辑结构是从逻辑关系上描述数据，它与数据的关系_存储结构_无关，是独立于计算机的。18.在双向循环链表的每个结点中包含 _两个_指针域，其中

10、next 指向它的_直接 后继_，prior 指向它的_直接前驱_，而头结点的 prior 指向_尾结点_，尾结点的 next 指向_头结点_。19 .单向循环链表是单向链表的一种扩充，当单向链表带有头结点时，把单向链表中尾结点的指针域由空指针改为 _头结点的指针当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向_指向第一个结点的指针 _。20.线性链表的逻辑关系时通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种 _链式_存储结构，又称为 _链表_。三、问答题1. 简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？答：若用结

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

12、储单元的地址必须是连续的。优点：一般情况下，存储密度大，存储空间利用率高。缺点：(1)在做插入和删除操作时，需移动大量元素；(2)由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；(3)表的容量难以扩充。链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结优点：插入和删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低。3.什么情况下用顺序表比链表好？答：顺序表适于做查找这样的静态操作，链表适于做插入和删除这样的动态操作。 如果线性表的变化长度变化不大，且其主要操作是查找，则采用顺序表；如果线性表的 长度变化较大，且其主要操作是插入、删除操作，

13、则采用链表。4.头指针、头结点、第一个结点(或称首元结点)的区别是什么？头结点是在链表的开始结点之前附加的一个结点；第一个结点(或称首元结点)是 链表中存储第一个数据元素的结点；头指针是指向链表中第一个结点(或为头结点或为 首元结点)的指针。5.解释带头结点的单链表和不带头结点的单链表的区别。答：带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作 上。在结构上，带头结点的单链表，不管链表是否为空，均含有一个头结点，不带头 结点的单链表不含头结点。在操作上，带头结点的单链表的初始化为申请一个头结点。无论插入或删除的位 置是地第一个结点还是其他结点，算法步骤都相同。不带头结点的

14、单链表，其算法步骤 要分别考虑插入或删除的位置是第一个结点还是其他结点。因为两种情况的算法步骤不 同。四、程序填空题1.下列是用尾插法建立带头结点的且有 n 个结点的单向链表的算法，请在空格内 填上适当的语句。NODE *create1( n)/*对线性表(1,2,.,n),建立带头结点的单向链表 */NODE *head,*p,*q;int i;p=(NODE *)malloc(sizeof(NODE);head=p; q=p; p-n ext=NULL;for(i=1;idata=i;(2)_ p-next=NULL;(3)_ q-next=p;(4)q=p_;retur n(head);

15、42.下列是用头插法建立带头结点的且有 n 个结点的单向链表的算法，请在空格内 填上适当的语句。点值，另一部分存放表示结点间关系的指针。NODE *create2( n)5/*对线性表(n,n-1,.,1),建立带头结点的线性链表*/NODE *head,*p,*q;int i;p=(NODE *)malloc(sizeof(NODE);(1)head=p_ ;p-next=NULL;(2)q=p_ ;for(i=1;idata=i;if(i=1)(3) p-next=NULLelse(4)p-next=q-next_ ;(5)q-next=p;return(head);1 .若让元素 1,

16、2, 3 依次进栈，则出栈顺序不可能为（C ）C. 3, 1, 2一个队列的入队序列是A. 4, 3 , 2 , 1C. 1, 4, 3, 21,B. 2, 1, 3D. 1, 3, 22,B.D.向顺序栈中压入新元素时，应当1,3,4。则队列的输出序列是（B ）2, 3,2, 4,A.先移动栈顶指针，再存入元素C.先后次序无关紧要在一个栈顶指针为 top 的链栈中，将一个A.B.C.D.先存入元素，再移动栈顶指针.同时进行p 指针所指的结点入栈，应执行（C ）top- next=p;p-n ext=top_ n ext; top-next=p;p_n ext=top;top=p;p-n ex

17、t=top_ n ext; top=top_ next;在一个栈顶指针为 top 的链栈中删除一个结点时，用x 保存被删结点的值，则执行A.B.C.D.x=top;top=top_next;x=top_data;top=top_ n ext;x=top_data;x=top_data; top=top_next;一般情况下，将递归算法转换成等价的非递归算法应该设置（3.下列是在具有头结点单向列表中删除第i 个结点，请在空格内填上适当的语句。int delete（NODE *head,i nt i）NODE *p,*q;int j;q=head;j=0；while（q!=NULL ）&（jn e

18、xt;j+;if（q=NULL）return（0）;（1） p=q_next_ ;（2） q_n ext=p_ n ext_ ;free（p）;return（1）;五、完成：实验 1 线性表根据实验要求（见教材 P201-202）认真完成本实验，并提交实验报告。数据结构（本）课程作业2（本部分作业覆盖教材第 3-5 章的内容）一、单项选择题B .队列C.堆栈或队列D.数组表达式 a*(b+c)_d的后缀表达式是（B ）.abcd*+_判断一个顺序队列B . abc+*d_ C . abc*+d_ D . _+*abcdsq （最多元素为 m0）为空的条件是（ C ）。A . sq_rear_s

19、q_front= m0B . sq_rear_sq_front_1= =mC. sq_front=sq_rearD. sq_front=sq_rear+1判断一个循环队列 Q （最多元素为 m）为空的条件是（A ）A . Q-front=Q_rearB . Q-front!=Q_rearC . Q_front=（Q-rea 叶 1）% m0D . Q_front!=（Q_rea 叶 1）%m010.判断栈 S 满（元素个数最多 n 个）的条件是（C ）A. s_top=0B . s_top!=0C . s_top=n-1D . s_top!=n-111. 一个队列的入队顺序是a,b,c,d,则

20、离队的顺序是（B）oA . a,d,cbB . a,b,c,d C . d,c,b,a D . c,b,d,a12.如果以链表作为栈的存储结构，则退栈操作时（C ）oA .必须判断栈是否满B.判断栈元素类型C .必须判断栈是否空D .对栈不作任何判断13 .在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（B ）结构。A.堆栈 B .队列 C .数组 D .先性表14. 一个递归算法必须包括（B）oA.递归部分B.终止条件和递归部分C .迭代部分D .终止条件和迭代部分6715.从一

21、个栈顶指针为 top 的链栈中删除一个结点时，用变量 x 保存被删结点的值，则C .只能是原子.可以是子表或原子执行（A）A . x=top-data; top=top-next; B.x=top-data;C. top=top-next; x=top-data; Dtop=top-next; x=data;30 .常对数组进行的两种基本操作是（A.建立与删除BC.查找和修改DC） o.索引与、和修改.查找与索引16.在一个链队中，假设 f 和 r 分别为队头和队尾指针，则删除一个结点的运算为（C ）A . r=f-next;Br=r-next; C . f=f-next; D . f=r-n

22、ext;31.设二维数组 A56按行优先顺序存储在内存中，已知 A00起始地址为 1000，每 个数组元素占用 5 个存储单元，则元素 A44的地址为（A ）o17 .在一个链队中，假设 f 和 r 分别为队头和队尾指针，贝 U 插入 s 所指结点的运算为（B ）A. 1140 B . 1145 C . 1120 D . 1125A . f-next=s; f=s;BC. s-next=r;r=s;D18.以下陈述中正确的是（A ）A.串是一种特殊的线性表C .串中元素只能是字母.r-n ext=s;r=s;.s-n ext=f;f=s;B .串的长度必须大于零D .空串就是空白串19 .设有

23、两个串 p 和 q,其中 q 是 p 的子串，q 在 p 中首次出现的位置的算法称为 （C ）A.求子串BC.匹配D20.串是（D ）oA.不少于一个字母的序列C.不少于一个字符的序列21.串的长度是指（ B）oA.串中所含不同字母的个数C.串中所含不同字符的个数.连接.求串长B.任意个字母的序列D .有限个字符的序列B .串中所含字符的个数D .串中所含非空格字符的个数22.若串 S= “ English”，其子串的个数是（ D ）A. 9 B . 16 C . 36 D . 2823 .串与普通的线性表相比较，它的特殊性体现在（ C）oA.顺序的存储结构B.链接的存储结构C.数据元素是一个

24、字符D.数据元素可以任意24 .空串与空格串（B）oA.相同B.不相同C.可能相同 D .无法确定25 .两个字符串相等的条件是（D ）A .两串的长度相等B.两串包含的字符相同C .两串的长度相等，并且两串包含的字符相同D .两串的长度相等，并且对应位置上的字符相同26 .在实际应用中，要输入多个字符串，且长度无法预定。则应该采用（ A ）存储比较合适（）。A .链式 B .顺序 C .堆结构 D .无法确定27. 一维数组 A 采用顺序存储结构，每个元素占用6 个字节，第 6 个元素的存储地址为100，则该数组的首地址是（C ）A . 64B. 28C. 70D. 9028.稀疏矩阵采用压

25、缩存储的目的主要是（A.表达变得简单BC .去掉矩阵中的多余元素D29. 一个非空广义表的表头（C）oA.不可能是原子BD）o.对矩阵元素的存取变得简单.减少不必要的存储空间的开销.只能是子表32 .设有一个 20 阶的对称矩阵 A，采用压缩存储的方式，将其下三角部分以行序为主序 存储到一维数组 B 中（数组下标从 1 开始），则矩阵中元素 a9,2在一维数组 B 中的下标是（D）oA. 41B. 32 C . 18 D . 38二、填空题1.栈是限定在表的一端进行插入和删除操作的线性表，又称为_后进先出_o2.循环队列队头指针在队尾指针 _下一个_位置，队列是“满”状态3 .在队列的顺序存储

26、结构中，当插入一个新的队列元素时，尾指针_增1_，当删除一个元素队列时，头指针 _ 增 1_o4.循环队列的引入，目的是为了克服 _假上溢_o5.向顺序栈插入新元素分为三步：第一步进行栈是否满判断，判断条件是s-top=MAXSIZE-1 _;第二步是修改 _栈顶指针_ ;第三步是把新元素赋给栈顶对应的数组元素 _。同样从顺序栈删除元素分为三步：第一步进行 _ 栈是否空判断，判断条件是 _ s-top=-1_。第二步是把_栈顶元素_;第三步修改栈顶指针_o6 .假设以 S 和 X 分别表示入栈和出栈操作，则对输入序列 a,b,c,d,e系列栈操作SSXSXSSXXX 之后，得到的输出序列为 _

27、 bceda_o7. 一个递归算法必须包括 _终止条件_和_ 递归部分_o8 .判断一个循环队列 LU （最多元素为 m ）为空的条件是LU-front=LU-rear _o9.在将中缀表达式转换成后缀表达式和计算后缀表达式的算法中，都需要使用栈，对于前者，进入栈中的元素为表达式中的 _ 运算符_，而对于后者，进入栈的元素为_ 操作数_， 中缀表达式（a+b）/c-（f-d/c）所对应的后缀表达式是 ab+c/fde/-o10.向一个栈顶指针为 h 的链栈中插入一个 s 所指结点时，可执行_s-next=h_和 h=s;操作。（结点的指针域为 next）11.从一个栈顶指针为 h 的链栈中删除

28、一个结点时，用x 保存被删结点的值，可执行 x=h-data;和_ h=h-next_。（结点的指针域为 next）12.在一个链队中，设 f 和 r 分别为队头和队尾指针，贝 U 插入 s 所指结点的操作为 r-next=s_ 禾口 r=s;（结点的指针域为 next）13.在一个链队中，设 f 和 r 分别为队头和队尾指针，则删除一个结点的操作为_f=f-next_o（结点的指针域为 next）14 .串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是_字符_o15.串的两种最基本的存储方式是 _顺序存储方式_和_链式存储方式_o16.空串的长度是_0_;空格串的长度是 _ 空格字符

29、的个数 _o17.需要压缩存储的矩阵可分为 _特殊_矩阵和_稀疏_矩89阵两种。18._ 设广义表 L=(), (),则表头是_() _ ，表尾是_ ()_L 的长度是2。19._ 广义表 A (a,b,c) ,(d,e,f)的表尾为_ (d,e,f) _。20 .两个串相等的充分必要条件是 _ 串长度相等且对应位置的字符相等。21.设有 n 阶对称矩阵 A， 用数组 s 进行压缩存储， 当 i _j 时， A 的数组元素 a.j相应 于数组 s 的数组元素的下标为_ i(i-1)/2+j _ 。(数组元素的下标从 1 开始)22.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元

30、素的行下标_ 、 列下标和非零元素值 _三项信息。三、问答题1. 简述栈和一般线性表的区别。答：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。2. 简述队列和一般线性表的区别。队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的删除只能在队头进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。3. 链栈中为何不设头结点？答：因为链栈只在链头插入和删除结点，不可能在链表中间插入和删除结点，算法实现很简单，所以一般不设置头结点。4. 利用一个栈，则：(1) 如果输入序列由 A，B，C 组成，试给出全部可能的输

31、出序列和不可能的输出 序列。(2) 如果输入序列由 A，B，C，D 组成，试给出全部可能的输出序列和不可能的 输出序列。答：(1)栈的操作特点是后进先出，因此输出序列有：S2 入栈S3 入栈X3 出栈输出序列： 13S4 入栈X4 出栈输出序列： 134X2 出栈输出序列： 13426 .有 5 个元素， 其入栈次序为:A、B、C、D、E,在各种可能的出栈次序中， 以元素 C、入, A 出,B 入,B 出, C 入 C 出，输出序列为 ABC。入, A 出,B 入, C 入,入, B 入,B 出, A 出,入, B 入,B 出, C 入,入, B 入, C 入，C 出,输出序列为 ACB输出序

32、列为 BAC输出序列为 BCA输出序列为 CBAC 出，B 出,C 入，C 出,C 出，A 出,B 出，A 出,由 A , B, C 组成的数据项，除上述五个不同的组合外，还有一个C, A , B 组合。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

33、 , CDBEA , CDEBA7 .写出以下运算式的后缀算术运算式 3x2+x-1/x+5(A+B)*C-D/(E+F)+G答；对应的后缀算术运算式 3x2A*x+1x/-5+ AB+C*DEF+/-G+8 .简述广义表和线性表的区别和联系。答：广义表是线性表的的推广，它也是 n(n0)个元素 4 耳a為的有限序列，其中 a 或者是原子或者是一个广义表。所以，广义表是一种递归数据结构，而线性表没有这 种特性，线性表可以看成广义表的特殊情况，当a 都是原子时，广义表退化成线性表。四、程序填空题1.在下面空格处填写适当的语句，以使下面的链式队列取出元素的算法完整。int write(L in k

34、Queue *q)QueueNode *p;if (q-fro nt=q-rear)/*队空 */printf(“underflow ” );exit(0);while (q-fro nt- n ext != NULL)p=q-fron t- n ext;(1) q-front-n ext=p-n ext;但不可能先把 C 出栈，再把 A 出栈，(A 不在栈顶位置)，最后把 B 出栈，所以序列 CAB 不可能由输入序列 A , B, C 通过栈得到。(2)按照上述方法，可能的输出序列有：ABCD , ABDC , ACBD , ACDB , ADCB , BACD , BADC , BCAD

35、, BCDA , BDCA ,CBAD , CBDA , CDBA , DCBA。不可能的输出序列有：DABC , ADBC , DACB , DBAC , BDAC , DBCA , DCAB , CDAB , CADB , CABD5.用 S 表示入栈操作,X 表示出栈操作,若元素入栈顺序为 1234 ,为了得到 1342 出栈 顺序,相应的 S 和 X 操作串是什么？答：应是 SXSSXSXX。各操作结果如下：S 1 入栈X 1 出栈输出序列：1printf( “4d ,p -data);(2) free(p);_(3) q-rear=q-front;/*队空时，头尾指针指向头结点*/五

36、、综合题1 .设栈 S 和队列 Q 的初始状态为空，元素 e1,e2,e3,e4,e5 和 e6 依次通过 S, 个 元素出栈后即进队列 Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e1则栈S的容量至少 应该是多少？答：出队序列是 e2,e4,e3,e6,e5,e1 的过程：10112.设用循环单链表实现循环队列， 该队列只使用一个尾指针rear，其相应的存储结构和基本算法如下；（1）初始化队列 initqueue（Q）:建立一个新的空队列 Q（2 ）入队列 enqueue（Q,x）:将元素 x 插入到队列 Q 中。（3）出队列 delqueue（Q）:从队列 Q 中退出一个元素。

37、（4）取队首元素 gethead（Q）:返回当前队首元素。（5 ）判断队列是否为空：emptyqueue（Q）。（6 ）显示队列中元素：dispqueue（Q）。算法设计如下：/*只有一个指针 rear 的链式队的基本操作*/#i nclude typedef char elemtype;struct node /*定义链队列结点*/elemtype data;struct node *n ext;typedef struct queue /*定义链队列数据类型*/struct node *rear; Lin kQueue;elemtype gethead(L in kQueue *Q) /*

38、 if (Q-rear=NULL)printf(队列为空!n);elseretur n( Q-rear- n ext-data);int emptyqueue(LinkQueue *Q) /*判断队列是否为空算法*/if (Q-rear=NULL) return(1);/*为空，则返回 true*/else return(0); /*不为空，则返回 flase*/void dispqueue(LinkQueue *Q)/*显示队列中元素算法 */struct node *p=Q-rear- n ext;printf(队列元素:);while (p!=Q-rear)prin tf(%c ,p-d

39、ata);p=p-n ext;prin tf(%cn,p-data);六、完成：实验 2栈、队列、递归程序设计A.abdec B . debac C . debca D . abedcel 入栈（栈底到栈顶元素是 el）e2 入栈（栈底到栈顶元素是 e1,e2 ）e2 出栈（栈底到栈顶元素是 e1）e3 入栈（栈底到栈顶元素是 e1,e3 ）e4 入栈（栈底到栈顶元素是 e1,e3,e4 ）e4 出栈（栈底到栈顶元素是 e1,e3 ）e3 出栈（栈底到栈顶元素是 e1）e5 入栈（栈底到栈顶元素是 e1,e5 ）e6 入栈（栈底到栈顶元素是 e1,e5,e6 ）e6 出栈（栈底到栈顶元素是 e

40、1,e5 ）Oe5 出栈（栈底到栈顶元素是 e1）（12） el 出栈（栈底到栈顶元素是空）栈中最多时有 3 个元素，所以栈 S 的容量至少是 3void delqueue(LinkQueue *Q) /* 出队算法 */struct node *t;if (Q-rear=NULL)printf(队列为空!n); return(0);else if (Q-rear- n ext=Q-rear) /*t=Q-rear;Q-rear=NULL;else /*有多个结点时*/t=Q-rear- next;Q-rear- n ext=t- next;free(t);只有一个结点时*/*t指向第一个结点

41、*/*引成循环链*/void initqueue(LinkQueue *Q)/*初始化队列 */Q=(struct queue *)malloc(sizeof(struct queue);Q-rear=NULL;根据实验要求（见教材 P203）认真完成本实验，并提交实验报告。数据结构（本）课程作业作业 3（本部分作业覆盖教材第6-7 章的内容）void enq ueue(L in kQueue *Q,elemtype x) /* struct n ode *s,*p;s=(struct n ode *)malloc(sizeof(struct n ode);s-data=x;if (Q-rea

42、r=NULL)/*Q-rear=s; s-n ext=s;else/*入队算法*/原为空队时*/原队不为空时*/p=Q-rear-next; /*p 指向第一个结点 */Q-rear-next=s; /*将 s 链接到队尾 */Q-rear=s; /*Q-rear指向队尾 */s-n ext=p;一、单项选择题1.假定一棵二叉树中, 双分支结点数为15,单分支结点数为 30，则叶子结点数为4.B )。A. 15.472.二叉树第 k 层上最多有（个结点。A . 2kC . 2k-1二叉树的深度为A. 2kC. 2k-1.2k-1-1.2kk,则二叉树最多有（ D ）个结点设某一二叉树先序遍历为

43、C )。.2k-1.2k-1abdec,中序遍历为 dbeac,则该二叉树后序遍历的顺序是取队首元素算法*/12A.33 B .34 C . 35 D . 366.如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该 树称为（A ）。A.哈夫曼树B .平衡二叉树C .二叉树D.完全二叉树7.下列有关二叉树的说法正确的是（ A）oA.二叉树中度为 0 的结点的个数等于度为 2 的结点的个数加 1B.二叉树中结点个数必大于 0C.完全二叉树中，任何一个结点的度，或者为0 或者为 2D.二叉树的度是 28.在一棵度为 3 的树中，度为 3 的结点个数为 2，度为 2 的结点个数

44、为 1，则度为 0 的 结点个数为（C ）oA. 4 B . 5 C . 6 D . 79.在一棵度具有 5 层的满二叉树中结点总数为（ A）oA. 31 B . 32 C . 33 D . 1610. 利用 n 个值作为叶结点的权生成的哈夫曼树中共包含有（D ）个结点。A. n B. n+1 C. 2*n D. 2*n-118 .在图的存储结构表示中，表示形式唯一的是（ C）oA . n B . n：1 C . nJ D . n/219 . 一个具有 n 个顶点的无向完全图包含（ A ）条边。A . n （n_1）B . n （n 1） C . n （nJ） /2 D . n （n -1）

45、/220.对于具有 n 个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（ B ）A . nB. n2C . n_1D . （nd）221.对于一个具有 n 个顶点和 e 条边的无向图，若采用邻接表表示，则所有顶点 邻接表中的结点总数为（D）oA . nB. e C . 2n D . 2e22 .在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（B）邻接点。A .入边B.出边C .入边和出边D.不是入边也不是出边23 .邻接表是图的一种（B) oA .顺序存储结构B.链式存储结构C .索引存储结构D.散列存储结构24.如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定

46、是（B）o11.利用 3、6、& 12 这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶A .完全图 B .连通图 C .有回路 D . 一棵树子的最长带权路径长度为（A）oA. 18 B. 16 C. 12 D. 3012 .在一棵树中，（C）没有前驱结点。A.分支结点 B .叶结点 C .树根结点 D .空结点13 .在一棵二叉树中，若编号为 i 的结点存在右孩子，则右孩子的顺序编号为（ C ）A . 2iB. 2i-1 D . 2i+1 C . 2i+214 .设一棵哈夫曼树共有 n 个叶结点，则该树有（B ）个非叶结点。A.nB.n-1C. n+1D. 2n15.设一棵有n 个

47、叶结点的二叉树，除叶结点外每个结点度数都为2,则该树共有（B ）个结点。A . 2nB.2n -1C. 2n+1D. 2n+216.在一个图G 中，所有顶点的度数之和等于所有边数之和的（C )倍A . 1/2 B . 1 C . 2 D . 417 .在一个有像图中，所有顶点的入度之和等于所有顶点的出度之和的（B ）倍25.下列有关图遍历的说法不正确的是（ C）oA 连通图的深度优先搜索是一个递归过程B. 图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C. 非连通图不能用深度优先搜索法D. 图的遍历要求每一顶点仅被访问一次26.无向图的邻接矩阵是一个（ A）oA.对称矩阵B .零矩阵 C

48、 .上三角矩阵D .对角矩阵27.图的深度优先遍历算法类似于二叉树的（ A ）遍历。A.先序B .中序 C .后序 D .层次28.已知下图所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（C）oA . V1V2MMV3V5WV7B .C . VMMWWeV?D . V1VVW2WM二、填空题1 .结点的度是指结点所拥有的子树树木或后继结点数_o2._ 树的度是指 _树中所有结点的度的最大值 _o3._ 度大于 0 的结点称作分支结点或非终端结点 o4._度等于 0 的结点称作叶子结点或终端结点 _o5.在一棵树中，每个结点的 _子树的根_或者说每个结点的_

49、后继结点称为该结点的_孩子结点_，简称为孩子。6.从根结点到该结点所经分支上的所有结点称为该结点的祖先_o7.树的深度或高度是指 树中结点的最大层数 o8.具有 n 个结点的完全二叉树的深度是5.将含有 150 个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为 1，则编号为 69 的结点的双亲结点的编号为（ B ）。A .邻接矩阵表示法.邻接表表示法C.逆邻接表表示法D.邻接表和逆邻接表13|llog2n -1 _o9.先序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，访问二叉树的根结点；先序遍历二叉树的左子树_，先序遍历二叉树14的_

50、右子树 。10 .中序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，中序遍历二叉树的 _左子树_;访问而叉树的 _根结点_，中序遍历二叉树 的_右子树_。11.后序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，后序遍历二叉树的 _左子树_;后序遍历二叉树的 _右子树_，访问而叉树 的_根结点_。12.将树中结点赋上一个有着某种意义的实数，称此实数为该结点的_权_。13._ 树的带权路径长度为树中所有叶子结点的 _带权路径长度之和_ 。14.哈夫曼树又称为 _最优二叉树_，它是 n 个带权叶子结点构成的所有二叉树中带权路径长度 WPL _最小的二叉

51、树 _ 。15.若以 4，5 ,6，7，8 作为叶子结点的权值构造哈夫曼树，则其带权路径长度是69。16.具有 m 个叶子结点的哈夫曼树共有 _2m-1_结点。17.在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种_多对多_的关系。18.图的遍历是从图的某一顶点出发， 按照一定的搜索方法对图中 _所有顶点_各做_一次_访问的过程。19.图的深度优先搜索遍历类似于树的 先序_遍历。20.图的广度优先搜索类似于树的按层次 遍历。21.具有 n 个顶点的有向图的邻接矩阵，其元素个数为_n2.22.图常用的两种存储结构是邻接矩阵 和 邻接表23.在有 n 个顶点的有向图中，每个顶

52、点的度最大可达_2(n-1)_。24.在一个带权图中，两顶点之间的最段路径最多经过_n-1条边。25.为了实现图的深度优先搜索遍历，其非递归的算法中需要使用的一个辅助数据答：二叉树的定义是递归的，所以，一棵二叉树可看作由根结点，左子树和右子树这三个基本部分组成，即依次遍历整个二叉树，又左子树或者右子树又可看作一棵二叉 树并继续分为根结点、左子树和右子树三个部分.，这样划分一直进行到树叶结点(1)先序为根左右，先序序列为：fdbacegihl(2) 中序为左根右，中序序列为：abcdefghij(3) 后序为左右根，后序序列为：acbedhjigf2.已知某二叉树的先序遍历结果是： A，B，D，

53、G，C，E，H，L，I，K，M，F 和 J,它的中序遍历结果是：G，D，B，A，L，H，E，K，I，M，C，F 和 J,请画出这 棵二叉树，并写出该二叉树后续遍历的结果。(1)二叉树图形表示如下：BCDEF; GHIJLKM(2 )该二叉树后序遍历的结果是：G、D、B、L、H、K、M、I、E、J、F、C 和A。3.已知一棵完全二叉树共有 892 个结点，求树的高度叶子结点数单支结点数最后一个非终端结点的序号已知深度为 k 的二叉树最多有2k-1 个结点(K 1)，29-1892data=X) return 1; /*根结点的层号为 1*/* 向子树中查找 X 结点*/else int c1=N

54、odeLevel(BT-left,X);if(c1=1)_(1) return c1 _ ;int c2=_NodeLevel(BT-right,X)_;_if_ (3)_ (c2=1) return c2+1_ ;/若树中不存在 X 结点则返回 0else return 0;(1) 哈夫曼树如图 B-4 所示D30I20B10Av1v2v3v4v524A1445A1223AF图 G 的邻接矩阵图 G 的邻接表点即为最后一个非终端结点，序号为 892/2=446。4 给岀满足下列条件的所有二叉树。(1) 先序和中序相同(2) 中序和后序相同(3) 先序和后序相同图 G 的邻接矩阵如下图所示:(

55、2) 其带权路径长度WPL 值为 270oG= ( V , E)172.下面函数的功能是按照图的深度优先搜索遍历的方法，输出得到该图的生成树中的各 条边，请在划有横线的地方填写合适内容。void dfstree(adjmatrix GA, int i, i nt n)int j；visitedi=1;(1) for(j=0; jdata=p-data;t-lchild=CopyTree(p-lchild);t-rchild=CopyTree(p-rchild);return(t);elsereturn(NULL);/*CopyTree*/2 .根据下面函数声明编写岀求一棵二叉树中叶子结点总数的

56、算法，该总数值由函数返回。假定参数 BT 初始指向二叉树的根结点。int BTreeLeafCount(struct BTreeNode* BT);int BTreeLeafCount(struct BTreeNode* BT)else if（BT-left=NULL & BT-right=NULL） return 1;else return BTreeLeafCount（BT-left）+BTreeLeafCount（BT-right）;六、完成：实验 3栈、队列、递归程序设计实验 4图的存储方式和应用根据实验要求（见教材 P203）认真完成本实验，并提交实验报告。数据结构（本）课程作业（4

57、）（本部分作业覆盖教材第 8-9 章的内容）一、单项选择题1.顺序查找方法适合于存储结构为（D ）的线性表。A.散列存储B.索引存储C.散列存储或索引存储D.顺序存储或链接存储2.对线性表进行二分查找时，要求线性表必须（ C）oA .以顺序存储方式B.以链接存储方式C .以顺序存储方式，且数据元素有序D.以链接存储方式，且数据元素有序3.对于一个线性表，若要求既能进行较快地插入和删除，又要求存储结构能够反映 数据元素之间的逻辑关系，则应该（B）oA.以顺序存储方式B.以链接存储方式C.以索引存储方式D.以散列存储方式4.采用顺序查找方法查找长度为n 的线性表时，每个元素的平均查找长度为（C）o

58、A. nB. n/2C. （n+1）/2D. （n-1）/25. 哈希函数有一个共同的性质，即函数值应当以（ D ）取其值域的每个值。A.最大概率 B.最小概率C.平均概率D.同等概率6. 有一个长度为 10 的有序表，按折半查找对该表进行查找，在等概率情况下查找 成功的平均比较次数为（A ）oA. 29/10 B . 31/10 C . 26/10 D . 29/97.已知一个有序表为11,22,33,44,55,66,77,88,99，则顺序查找元素 55 需要比 较（C ）次。A. 3 B . 4 C . 5 D . 68. 顺序查找法与二分查找法对存储结构的要求是（ D）oA.顺序查找

59、与二分查找均只是适用于顺序表B.顺序查找与二分查找均既适用于顺序表，也适用于链表C. 顺序查找只是适用于顺序表18D. 二分查找适用于顺序表9. 有数据53,30,37,12,45,24,96，从空二叉树开始逐个插入数据来形成二叉排序 树，若希望高度最小，应该选择的序列是（ B）oA. 45,24,53,12,37,96,30B. 37,24,12,30,53,45,96C. 12,24,30,37,45,53,96D. 30,24,12,37,45,96,5310 .对有 18 个元素的有序表作二分（折半）查找，则查找 A3的比较序列的下标 可能为（D）oA . 1、2、3 B . 9、5、

60、2、3if(BT=NULL) retur n 0;C . 9、5、39、4、2、31911.对于顺序存储的有序表5, 12, 20, 26, 37, 42, 46, 50, 64，若采用折半查79, 46, 56, 38, 40, 8484, 79, 56, 38, 40, 46找，则查找元素 26 的比较次数是（C ）。A.3 B. 3 C. 4D.512.在所有的排序方法中，关键字比较的次数与记录初始排列秩序无关的是（C ）。A. 冒泡排序 B.希尔排序C.直接选择排序 D.直接插入排序13.从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已排序序列的正确的位置上，此方