2020年新编电大数据结构本形成性考核册作业4原题带答案名师精品资料

1、电大 数据结构（本）形成性考核 课程作业 答案 一、单项选择题 ）。 B紧凑结构和非紧凑结构 D内部结构和外部机构 1在数据结构中，从逻辑上可以把数据结构分为（C D ）。 A 动态结构和静态结构 C线性结构和非线性结构 2下列说法中，不正确的是（ A 数据元素是数据的基本单位 B数据项是数据中不可分割的最小可标识单位 C数据可有若干个数据元素构成 D数据项可由若干个数据元素构成 3一个存储结点存储一个（B ）。 A 数据项B数据元素 C数据结构 D数据类型 4数据结构中，与所使用的计算机无关的是数据的（ A 存储结构 B 物理结构 ）。 C逻辑结构 D物理和存储结构 5下列的叙述中，不属于算

2、法特性的是（D ）。 B输入性 A有穷性 C可行性 D可读性 6算法分析的目的是（ C ）。 A找出数据结构的合理性 C分析算法的效率以求改进 B研究算法中的输入和输出的关系 D分析算法的易懂性和文档性 7数据结构是一门研究计算机中（ A 数值运算B非数值运算 C集合D非集合 B ）对象及其关系的科学。 8算法的时间复杂度与（ A所使用的计算机 C与算法本身 9设有一个长度为 C ）有关。 B与计算机的操作系统 D与数据结构 n 的顺序表，要在第 i 个元素之前（也就是插入元素作为新表的第 i 个元素），则移动元素个数为（ A ）。 A n-i+1 Bn-i C n-i-1 Di 10设有一个

3、长度为 A n-i+1 n 的顺序表，要删除第 i 个元素移动元素的个数为（ B Bn-iC n-i-1 Di ）。 11在一个单链表中， 语句（ C ）。 p、q分别指向表中两个相邻的结点，且q 所指结点是 p 所指结点的直接后继，现要删除 q 所指结点，可用 A p=q-next 12在一个单链表中 Bp-next=q Cp-next=q next D q-next=NULL p 所指结点之后插入一个 s 所指的结点时，可执行（ D ）。 A p-next= s; s next= p next B p-next=s next; C p=s-next 13非空的单向循环链表的尾结点满足（ D

4、 s-next=p-next; p-next=s; C ）（设头指针为 head，指针 p 指向尾结点） 。 A. P-next= =NULL BP= =NULL C P-next= =head D P= = head 14链表不具有的特点是（A ）。 B插入删除不需要移动元素 D所需空间与线性表长度成正比 B ）（设头指针为 head）。 A可随机访问任一元素 C不必事先估计存储空间 15带头结点的链表为空的判断条件是（ A head = =NULL B head-next= =NULL C head-next= =head D head!=NULL 16在一个单链表中， p、q分别指向表中

5、两个相邻的结点，且q所指结点是 p所指结点的直接后继，现要删除 q 所指结点，可用 语句（ C ）。 A p=q-next Bp-next=q Cp-next=q-next D q-next=NULL 17 在一个链队中，假设 f 和 r 分别为队头和队尾指针， 则删除一个结点的运算为（ C ）。 A r=f-next; B r=r-next; Cf=f-next; D f=r-next; 18 在一个链队中，假设 f 和 r 分别为队头和队尾指针， 则插入 s 所指结点的运算为（ B ）。 A f-next=s; f=s; B r-next=s;r=s; C s-next=r;r=s; D

6、s-next=f;f=s; 19. 一个顺序表第一个元素的存储地址是90，每个元素的长度为 2，则第 6 个元素的地址是（ B ） A98 B100 C 102D 106 20有关线性表的正确说法是（D ）。 A每个元素都有一个直接前驱和一个直接后继 B线性表至少要求一个元素 C表中的元素必须按由小到大或由大到下排序 D除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继 二、填空题 1在一个长度为 n 的顺序存储结构的线性表中，向第 i（1i n+1） 个元素之前插入新元素时，需向后移动n-i+1 个数据元素 2从长度为 n 的采用顺序存储结构的线性表中删除第 i（1i

7、 n+1） 个元素 ，需向前移动 n-i 个元素。 3数据结构按结点间的关系，可分为 4 种逻辑结构： 集合 、 线性结构 、 树形结构 、 图状结构 。 4数据的逻辑结构在计算机中的表示称为 物理结构 或 存储结构 。 5除了第 1 个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的数据结构为 线性结构 ，每个结点可有任意 多个前驱和后继结点数的结构为 非线性结构 。 7数据结构中的数据元素存在多对多的关系称为 8数据结构中的数据元素存在一对多的关系称为 9数据结构中的数据元素存在一对一的关系称为 10要求在 n 个数据元素中找其中值最大的元素， 和 _ O（n）_ 。 6算法的

8、5 个重要特性是 有穷性 、 确定性 、 可形性 、 有零个或多个输入 有零个或多个输出 。 _图状结构 _结构。 _树形结构 _结构。 _线性结构 _结构。 n-1 设基本操作为元素间的比较。 则比较的次数和算法的时间复杂度分别为 11在一个单链表中 p 所指结点之后插入一个 s 所指结点时，应执行 _ s-next=p-next _和 p-next=s; 的操作。 12设有一个头指针为 head 的单向循环链表， p 指向链表中的结点，若 p-next= =_ head _ ，则 p 所指结点为尾结点。 13在一个单向链表中，要删除 p 所指结点，已知 q 指向 p 所指结点的前驱结点。则

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

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

11、可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示。尽管因采用的存储 结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。 采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大。 2解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。 答： 顺序结构存储时， 相邻数据元素的存放地址也相邻， 即逻辑结构和存储结构是统一的， ，要求内存中存储单元的地址必须是连续的 优点：一般情况下，存储密度大，存储空间利用率高。 缺点：( 1)在做插入和删除操作时，需移动

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

13、别是什么？ 头结点是在链表的开始结点之前附加的一个结点；第一个结点(或称首元结点)是链表中存储第一个数据元素的结点；头指针是 指向链表中第一个结点(或为头结点或为首元结点)的指针。 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-next=NULL; for(i=1;idata=i; ( 2) p-next=NULL ( 3) q-next=p; ( 4) q=p; return(head); 2下列是用头插法建立带头结点的且有n 个结点

15、的单向链表的算法，请在空格内填上适当的语句 NODE *create2(n) /* 对线性表 (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=NULL; else ( 4) p-next=q-next ; ( 5) q-next=p ; return(head); 3下列是在具有头结点单向列表中删除第i 个结点，请在空格内填上适当的语句。

16、 int delete(NODE *head,int i) NODE *p,*q; int j; q=head; j=0; while(q!=NULL) j+; if(q=NULL) return(0); ( 1) p=q-next ; ( 2) q-next=p-next ; free（p）; return（1）; 五、完成：实验 1线性表 根据实验要求（见教材 P201-202）认真完成本实验，并提交实验报 数据结构（本）课程作业 2 本部分作业覆盖教材第 3-5 章的内容） 一、单项选择题 1若让元素 1，2，3 依次进栈，则出栈顺序不可能为（C ） A 3，2，1B2，1，3 C3，1

17、，2 D1，3，2 2一个队列的入队序列是 1，2，3，4 A4，3，2，1 B1，2，3， C1，4，3，2 D3，2，4， 3向顺序栈中压入新元素时，应当（ A先移动栈顶指针，再存入元素 C先后次序无关紧要D 则队列的输出序列是（ B ）。 4 1 A ）。 B 先存入元素，再移动栈顶指针 同时进行 4在一个栈顶指针为 top 的链栈中，将一个 p 指针所指的结点入栈，应执行（ A top-next=p; B p-next=top-next; top-next=p; C p-next=top; top=p; D p-next=top-next; top=top-next; 5在一个栈顶指针

18、为 top 的链栈中删除一个结点时，用 x保存被删结点的值，则执行（ B ） A x=top;top=top-next; B x=top-data; C top=top-next; x=top-data; D x=top-data; top=top-next; A 栈 C堆栈或队列 B队列 D数组 6一般情况下，将递归算法转换成等价的非递归算法应该设置（A ） 7表达式 a*(b+c)-d 的后缀表达式是（ A abcd*+- B abc+*d- C abc*+d- D -+*abcd 8判断一个顺序队列 sq（最多元素为 m0）为空的条件是（ A sq-rear-sq-front= m 0

19、B sq-rear-sq-front-1= = m 0 Csq-front=sq-rear D sq-front=sq-rear+1 9判断一个循环队列 Q（最多元素为 m0）为空的条件是（ A Q-front=Q-rear C Q-front=(Q-rear+1)% m 0 B Q-front!=Q-rear D Q-front!= (Q-rear+1)%m 0 10判断栈 S满（元素个数最多 n 个）的条件是（ C ） A s-top=0 B s-top!=0 C s-top=n-1 D s-top!=n-1 11一个队列的入队顺序是 B ）。 A a,d,cb Ba,b,c,d a,b,

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

21、被删结点的值， 则执行（ A ）。 A x=top-data; top=top-next; B x=top-data; C top=top-next; x=top-data; D top=top-next; x=data; 16在一个链队中，假设 f 和r 分别为队头和队尾指针， 则删除一个结点的运算为（ C ）。 A r=f-next; B r=r-next; C f=f-next; D f=r-next; 17在一个链队中，假设 f 和r 分别为队头和队尾指针， 则插入 s 所指结点的运算为 B ）。 A f-next=s; f=s; r-next=s;r=s; Cs-next=r;r=s

22、; s-next=f;f=s; 18. 以下陈述中正确的是 ）。 A串是一种特殊的线性表 C串中元素只能是字母 B 串的长度必须大于零 D 空串就是空白串 19设有两个串 p 和 q ，其中 q 是 p 的子串， q 在 p 中首次出现的位置的算法称为（ C ）。 A求子串B 连接 求串长 C 匹配 D 20 串是（ D ）。 A 不少于一个字母的序列 B 任意个字母的序列 C 不少于一个字符的序列 D 有限个字符的序列 21 串的长度是指（ B ）。 A 串中所含不同字母的个数 B 串中所含字符的个数 C 串中所含不同字符的个数 D 串中所含非空格字符的个数 22. 若串 S=“Englis

23、h ”，其子串的个数是（D ）。 A 9 B 16 C 36 D 28 C ）。 链接的存储结构 C数据元素是一个字符 数据元素可以任意 ）。 24空串与空格串（B A相同B 不相同 可能相同 D 无法确定 23串与普通的线性表相比较，它的特殊性体现在（ A顺序的存储结构 D ）。 25两个字符串相等的条件是（ A 两串的长度相等 B两串包含的字符相同 两串的长度相等，并且两串包含的字符相同 两串的长度相等，并且对应位置上的字符相同 26 在实际应用中，要输入多个字符串，且长度无法预定。则应该采用（ A链式 A ）存储比较合适（ ）。 27. 一维数组 A64 C70 B 顺序 C 堆结构 D

24、 无法确定 A 采用顺序存储结构，每个元素占用 6 个字节，第 6 个元素的存储地址为 100 ，则该数组的首地址是（ C ）。 28 90 28稀疏矩阵采用压缩存储的目的主要是（D A表达变得简单 C 去掉矩阵中的多余元素 ）。 对矩阵元素的存取变得简单 减少不必要的存储空间的开销 29一个非空广义表的表头（ C A 不可能是原子 ）。 只能是子表 C 只能是原子 可以是子表或原子 30常对数组进行的两种基本操作是 A建立与删除B C查找和修改 C ）。 索引与、和修改 查找与索引 31. 设二维数组 A56 按行优先顺序存储在内存中，已知 A00 起始地址为 1000，每个数组元素占用 5

25、 个存储单元，则元素 A44 的地址为（ ）。 A1140 B 1145 C 1120 D 1125 20 阶的对称矩阵 A，采用压缩存储的方式， 32设有一个 则矩阵中元素 a9,2 在一维数组 B 中的下标是（ D ）。 A41 32 18 将其下三角部分以行序为主序存储到一维数组 B中（数组下标从 1 开始）， 38 二、填空题 1栈是限定在表的一端进行插入和删除操作的线性表，又称为后进先出 。 2循环队列队头指针在队尾指针下一个 位置，队列是“满”状态 3在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针 增 1 ，当删除一个元素队列时，头指针 增 1 。 4循环队列的引入，目的

26、是为了克服假上溢 。 5向顺序栈插入新元素分为三步：第一步进行栈是否满 判断，判断条件是 s-top=MAXSIZE-1 ；第二步是修改 栈顶指针 ；第三步是把新元素赋给 栈顶对应的数组元素 。同样从顺序栈删除元素分为三步：第一步进行 栈是否 空 判断，判断条件是 s-top=-1 。第二步是把 栈顶元素 ；第三步 修改栈顶指针 。 6假设以 S 和 X 分别表示入栈和出栈操作，则对输入序列 a,b,c,d,e 一系列栈操作 SSXSXSSXXX 之后，得到的输出序列为 bceda 。 7一个递归算法必须包括终止条件 和 递归部分 。 8判断一个循环队列 LU （最多元素为 m0）为空的条件是

27、LU-front=LU-rear 。 9在将中缀表达式转换成后缀表达式和计算后缀表达式的算法中，都需要使用栈，对于前者，进入栈中的元素为表达式中的 运算符 ，而对于后者，进入栈的元素为 操作数 ，中缀表达式 （a+b）/c-（f-d/c） 所对应的后缀表达式是ab+c/fde/-。 10向一个栈顶指针为 h 的链栈中插入一个 s 所指结点时，可执行 _ s-next=h 和 h=s;操作。 （结点的指针域为 next） 11从一个栈顶指针为 h 的链栈中删除一个结点时， 用 x 保存被删结点的值， 可执行 x=h-data;和_ h=h-next 。（结点的指 针域为 next） 12在一个链

28、队中， 设 f 和 r 分别为队头和队尾指针， 则插入 s 所指结点的操作为 _ r-next=s 和 r=s; （ 结点的指针域为 next） 13在一个链队中，设 f 和 r 分别为队头和队尾指针，则删除一个结点的操作为 _ f=f-next 。 （结点的指针域为 next） 14 串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是 字符 。 15串的两种最基本的存储方式是顺序存储方式 和 链式存储方式 。 16空串的长度是0 ；空格串的长度是 空格字符的个数 。 17需要压缩存储的矩阵可分为特殊 矩阵和 稀疏 矩阵两种。 18设广义表 L= （），（），则表头是 （） ，表尾是 （

29、） ，L 的长度是 2 。 19广义表 A（a,b,c）,（d,e,f）的表尾为（ d,e,f）。 20两个串相等的充分必要条件是 串长度相等且对应位置的字符相等_。 21设有 n阶对称矩阵 A，用数组 s 进行压缩存储，当 i j 时，A 的数组元素 aij 相应于数组 s的数组元素的下标为 _ i（i-1）/2+j 。 （数组元素的下标从 1 开始） 22对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的_行下标 、_列下标 _和 _非零元素值 三项信息。 三、问答题 1简述栈和一般线性表的区别。 答：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线

30、性表可以在线性表的任何位置进行插入和 删除操作。 2简述队列和一般线性表的区别。 队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的删除只能在队头进行，而一般的线性表可以在线性表的任何 位置进行插入和删除操作。 3链栈中为何不设头结点？ 答：因为链栈只在链头插入和删除结点，不可能在链表中间插入和删除结点，算法实现很简单，所以一般不设置头结点。 4利用一个栈，则： （1）如果输入序列由 A，B，C 组成，试给出全部可能的输出序列和不可能的输出序列。 （2）如果输入序列由 A ，B，C，D 组成，试给出全部可能的输出序列和不可能的输出序列 答： （1）栈的操作特点是后进先出，因此输出序列

31、有： A 入， A 出， B 入， B 出， C入 C出，输出序列为 ABC 。 A 入， A 出， B 入， C 入， C 出， B 出， 输出序列为 ACB 。 A 入， B 入， B 出， A 出， C 入， C 出， 输出序列为 BAC 。 A 入， B 入， B 出， C 入， C 出， A 出， 输出序列为 BCA 。 A 入， B 入， C 入， C 出， B 出， A 出， 输出序列为 CBA 。 由 A，B，C组成的数据项，除上述五个不同的组合外，还有一个C，A，B 组合。但不可能先把 C出栈，再把 A出栈，（A不在 栈顶位置），最后把 B 出栈，所以序列 CAB 不可能由输

32、入序列 A， B，C 通过栈得到。 （2）按照上述方法，可能的输出序列有： ABCD ，ABDC ， ACBD ，ACDB ，ADCB ，BACD ，BADC ，BCAD ，BCDA ，BDCA ，CBAD ，CBDA ，CDBA ，DCBA 。 不可能的输出序列有： DABC ，ADBC ，DACB ，DBAC ，BDAC ，DBCA ，DCAB，CDAB，CADB ，CABD 5用 S表示入栈操作， X 表示出栈操作，若元素入栈顺序为1234，为了得到 1342出栈顺序，相应的 S和X 操作串是什么？ 答： 应是 SXSSXSXX 。各操作结果如下 S 1 入栈 X 1 出栈 输出序列：

33、1 S 2 入栈 S 3 入栈 X 3 出栈 输出序列： 13 S 4 入栈 X 4 出栈 输出序列： 134 X 2 出栈 输出序列： 1342 6有 5 个元素，其入栈次序为： A、B、 C、D、 E，在各种可能的出栈次序中，以元素C、D 最先的次序有哪几个？ 答：从题中可知，要使 （1）B 出栈， （2）B 出栈， （3）E 入栈， A 出栈， E 入栈， E出栈， C 第一个且 D 第二个出栈，应是 A 入栈， B 入栈， C 入栈， E入栈， E 出栈， B 出栈， C 出栈， D 入栈。之后可以有以下几种情况： E 出栈，输出序列为： A 出栈，输出序列为 A 出栈，输出序列为 C

34、DBAE 。 CDBEA 。 CDEBA 所以可能的次序有： CDBAE ，CDBEA ，CDEBA 7写出以下运算式的后缀算术运算式 3x2+x-1/x+5 （A+B）*C-D/（E+F）+G 答；对应的后缀算术运算式 3x2*x+1x/-5+ AB+C*DEF+/-G+ 8 简述广义表和线性表的区别和联系。 答：广义表是线性表的的推广，它也是n（n0）个元素 a1 ,a2ai an的有限序列，其中 ai 或者是原子或者是一个广义表。所以，广义 表是一种递归数据结构，而线性表没有这种特性，线性表可以看成广义表的特殊情况，当ai 都是原子时，广义表退化成线性表。 四、程序填空题 1在下面空格处

35、填写适当的语句，以使下面的链式队列取出元素的算法完整。 int write(LinkQueue *q) QueueNode *p; if (q-front=q-rear) /*队空 */ printf( “underflow ”); exit(0); while (q-front-next != NULL) p=q-front-next; (1) q-front-next=p-next; printf( “%4d”,p -data); (2) free(p); ( 3) q-rear=q-front; /* 队空时，头尾指针指向头结点 */ 五、综合题 1设栈 S和队列 Q的初始状态为空，元素

36、 e1,e2,e3,e4,e5和e6依次通过 S，一个元素出栈后即进队列 Q，若 6个元素出队的序 列是 e2,e4,e3,e6,e5,e1，则栈 S 的容量至少应该是多少？ 答：出队序列是 e2,e4,e3,e6,e5,e1 的过程： e1 入栈（栈底到栈顶元素是 e1 ） e2 入栈（栈底到栈顶元素是 e1,e2 ） e2 出栈（栈底到栈顶元素是 e1 ） e3 入栈（栈底到栈顶元素是 e1,e3 ） e4 入栈（栈底到栈顶元素是 e1,e3,e4 ） e4 出栈（栈底到栈顶元素是 e1,e3 ） e3 出栈（栈底到栈顶元素是 e1 ） e5 入栈（栈底到栈顶元素是 e1,e5 ） e6

37、入栈（栈底到栈顶元素是 e1,e5,e6 ） e6 出栈（栈底到栈顶元素是 e1,e5 ） e5 出栈（栈底到栈顶元素是 e1 ） e1 出栈（栈底到栈顶元素是空） 栈中最多时有 3 个元素，所以栈 S 的容量至少是 3。 2 假设用循环单链表实现循环队列，该队列只使用一个尾指针 rear ，其相应的存储结构和基本算法如下； （ 1）初始化队列 initqueue（Q）: 建立一个新的空队列 Q。 （ 2）入队列 enqueue（Q,x）: 将元素 x 插入到队列 Q中。 （ 3）出队列 delqueue（Q）: 从队列 Q中退出一个元素。 （ 4）取队首元素 gethead（Q）: 返回当前

38、队首元素。 （ 5）判断队列是否为空： emptyqueue（Q） 。 （ 6）显示队列中元素： dispqueue（Q） 。 算法设计如下： /* 只有一个指针 rear 的链式队的基本操作 */ #include typedef char elemtype; struct node /* 定义链队列结点 */ elemtype data; struct node *next; ; typedef struct queue /*定义链队列数据类型 */ struct node *rear; LinkQueue; void initqueue（LinkQueue *Q）/* 初始化队列 */

39、Q=（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）; 原为空队时 */ Q-rear=s; s-next=s; else /* s-data=x; if (Q-rear=NULL) /* 原队不为空时 */ p=Q-rear-next; /*p Q-rear-next=s; /* 指向第一个结点 */ 将

40、s 链接到队尾 */ Q-rear=s; /*Q-rear 指向队尾 */ s-next=p; void delqueue(LinkQueue *Q) /* struct node *t; if (Q-rear=NULL) 出队算法 */ printf( 队列为空 !n); return(0); else if (Q-rear-next=Q-rear) /* 只有一个结点时 */ t=Q-rear; Q-rear=NULL; else /* 有多个结点时 */ t=Q-rear-next; Q-rear-next=t-next; /*t /* 指向第一个结点 */ 引成循环链 */ free(

41、t); elemtype gethead(LinkQueue *Q) if (Q-rear=NULL) printf( 队列为空 !n); /* 取队首元素算法 */ else return(Q-rear-next-data); int emptyqueue(LinkQueue *Q) /* if (Q-rear=NULL) return(1); /* else return(0); /*不为空 , 则返回 void dispqueue(LinkQueue *Q) 判断队列是否为空算法 */ 为空 , 则返回 true*/ flase*/ /* 显示队列中元素算法 */ struct node

42、 *p=Q-rear-next; printf( 队列元素 :); while (p!=Q-rear) printf(%c ,p-data); p=p-next; printf(%cn,p-data); 六、完成：实验 2栈、队列、递归程序设计 根据实验要求（见教材 P203）认真完成本实验，并提交实验报告。 数据结构（本）课程作业 作业 3 （本部分作业覆盖教材第 6-7 章的内容） 一、单项选择题 1. 假定一棵二叉树中，双分支结点数为15，单分支结点数为 30，则叶子结点数为（ B ） A15 B 16 C 17 D 47 2二叉树第 k 层上最多有（ B ）个结点。 A 2k B 2k

43、-1 C 2k-1 D 2k-1 3二叉树的深度为 k,则二叉树最多有（ D ）个结点。 A2k B 2k-1 C2k-1 D 2k-1 4. 设某一二叉树先序遍历为 abdec，中序遍历为 dbeac，则该二叉树后序遍历的顺序是（ C ）。 Aabdec B debac C debca D abedc 5将含有 150 个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为 1 ，则编号为 69 的 结点的双亲结点的编号为（ B ）。 A 33 B 34C35D 36 6如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（A ）。 A

44、哈夫曼树B 平衡二叉树 C 二叉树 D 完全二叉树 7下列有关二叉树的说法正确的是（A ）。 A二叉树中度为 0 的结点的个数等于度为 2 的结点的个数加 1 B二叉树中结点个数必大于 0 C完全二叉树中，任何一个结点的度，或者为0 或者为 2 D二叉树的度是 2 8在一棵度为 3 的树中，度为 3 的结点个数为 2，度为 2 的结点个数为 1，则度为 0 的结点个数为（ C ）。 A4B 5 C 6 D 7 9在一棵度具有 5 层的满二叉树中结点总数为（A ）。 A31B 32C 33D 16 10. 利用 n 个值作为叶结点的权生成的哈夫曼树中共包含有（ D ） 个结点。 A. nB. n

45、+1C. 2*nD. 2*n-1 11. 利用 3、6、8、12 这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的最长带权路径长度为（ A ） 。 A. 18B. 16C. 12D. 30 12在一棵树中，（ C ）没有前驱结点。 A分支结点B 叶结点 C 树根结点 D 空结点 13在一棵二叉树中，若编号为 i 的结点存在右孩子，则右孩子的顺序编号为（ C ） A 2iB 14设一棵哈夫曼树共有 C 2i+2 ）个非叶结点 2i-1 D 2i+1 n 个叶结点，则该树有（ B n-1 C n+1 D 2n 15设一棵有 n 个叶结点的二叉树，除叶结点外每个结点度数都为 2，则该树共

46、有（ B ）个结点 A 2nB 2n-1 C2n+1D 2n+2 16在一个图 G中，所有顶点的度数之和等于所有边数之和的（C ）倍。 A 1/2B1C2D 4 17在一个有像图中，所有顶点的入度之和等于所有顶点的出度之和的（B ）倍 A 邻接矩阵表示法 B 邻接表表示法 C逆邻接表表示法D 邻接表和逆邻接表 18在图的存储结构表示中，表示形式唯一的是（ A n B n 1 C n 1 D n/2 19 一个具有 n 个顶点的无向完全图包含（ A ）条边。 A n（n 1）Bn（ n 1） C n（n 1）/2 D n（n 1）/2 20 对于具有 n 个顶点的图，若采用邻接矩阵表示， 则该矩

47、阵的大小为（ B ）。 A n B n2C n 2 1 D （ n 1） 2 21对于一个具有 n 个顶点和 e 条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（ D ） A nB e C 2nD 2e 22在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（B ）邻接点。 A 入边 B 出边 C入边和出边 D 不是入边也不是出边 23邻接表是图的一种（ B ）。 A 顺序存储结构 B 链式存储结构 C索引存储结构 D 散列存储结构 24 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ B ） A 完全图 B 连通图 C 有回路 D 一棵树 25

48、下列有关图遍历的说法不正确的是（C ）。 A连通图的深度优先搜索是一个递归过程 B图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C非连通图不能用深度优先搜索法 D图的遍历要求每一顶点仅被访问一次 26 无向图的邻接矩阵是一个（ A ）。 A 对称矩阵 B 零矩阵 C 上三角矩阵 D 对角矩阵 27图的深度优先遍历算法类似于二叉树的（A ）遍历。 A先序B 中序 C 后序 D 层次 28已知下图所示的一个图，若从顶点 V1 出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（C ） 3度大于 0 的结点称作分支结点 或 非终端结点 。 4度等于 0 的结点称作叶子结点 或 终端结

49、点 。 5在一棵树中，每个结点的 子树的根 或者说每个结点的 后继结点 称为该结点的 孩子结点 ，简称为孩子。 6从根结点到该结点所经分支上的所有结点称为该结点的祖先 。 7树的深度或高度是指 树中结点的最大层数 。 8具有 n 个结点的完全二叉树的深度是log2 n 1 。 9先序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，访问二叉树的根结点 ；先序遍历 二叉树的 左子树 ，先序遍历二叉树的 右子树 。 10 中序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，中序遍历二叉树的左子树 ；访 问而叉树的 根结点 ，中序遍历二叉树的 右子树 。 1

50、1后序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，后序遍历二叉树的左子树 ；后序 遍历二叉树的 右子树 ，访问而叉树的 根结点 。 12将树中结点赋上一个有着某种意义的实数，称此实数为该结点的权 。 13树的带权路径长度为树中所有叶子结点的带权路径长度之和 。 14哈夫曼树又称为最优二叉树 ，它是 n 个带权叶子结点构成的所有二叉树中带权路径长度 WPL 最小的二叉树 。 15若以 4，5，6，7，8 作为叶子结点的权值构造哈夫曼树，则其带权路径长度是69 16具有 m 个叶子结点的哈夫曼树共有2m-1 结点。 17在图中，任何两个数据元素之间都可能存在关系，因此图的

51、数据元素之间是一种 多对多 的关系。 18图的遍历是从图的某一顶点出发，按照一定的搜索方法对图中所有顶点 各做 一次 访问的过程。 19图的深度优先搜索遍历类似于树的先序 遍历。 20图的广度优先搜索类似于树的按层次 遍历。 21具有 n 个顶点的有向图的邻接矩阵，其元素个数为n2 。 22图常用的两种存储结构是邻接矩阵 和 邻接表 。 23在有 n 个顶点的有向图中，每个顶点的度最大可达2(n-1) 。 24在一个带权图中，两顶点之间的最段路径最多经过n-1 条边。 25为了实现图的深度优先搜索遍历，其非递归的算法中需要使用的一个辅助数据结构为栈 三、综合题 (1) 先序为“根左右” ，先序

52、序列为： fdbacegihl (2) 中序为“左根右” ，中序序列为： abcdefghij (3) 后序为“左右根” ，后序序列为： acbedhjigf 2已知某二叉树的先序遍历结果是： 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) 二叉树图形表示如下： A BC DEF GHIJ L K M （ 2）该二叉树后序遍历的结果是： G、D、B、L、H、K、M、I、E、J、F、C和 A 3已知一棵完全二叉树共有 892 个结点，求 树的高度 叶子结点

53、数 单支结点数 最后一个非终端结点的序号 答 已知深度为 k 的二叉树最多有 2k-1 个结点 （K 1）， 29-1892data=X) return 1; /*根结点的层号为 1*/ /* 向子树中查找 X 结点 */ else int c1=NodeLevel(BT-left,X); if(c1=1) _(1) return c1+1; int c2=(2) NodeLevel(BT-right,X) _; if _(3)_ (c2=1) return c2+1; / 若树中不存在 X 结点则返回 0 else return 0; 2. 下面函数的功能是按照图的深度优先搜索遍历的方法，

54、输出得到该图的生成树中的各条边， 请在划有横线的地方填写合适内容。 void dfstree(adjmatrix GA, int i, int n) int j; visitedi=1; (1) for(j=0; jdata=p-data; t-lchild=CopyTree(p-lchild); t-rchild=CopyTree(p-rchild); return(t); else return(NULL); /*CopyTree*/ 2 根据下面函数声明编写出求一棵二叉树中叶子结点总数的算法，该总数值由函数返回。假定参数BT 初始指向二叉树的根结点 int BTreeLeafCount(

55、struct BTreeNode* BT); int BTreeLeafCount(struct BTreeNode* BT) if(BT=NULL) return 0; else if(BT-left=NULL else return BTreeLeafCount(BT-left)+BTreeLeafCount(BT-right); 六、完成：实验 3栈、队列、递归程序设计 实验 4图的存储方式和应用 根据实验要求(见教材 P203)认真完成本实验，并提交实验报告。 本部分作业覆盖教材第 8-9 章的内容） 数据结构（本）课程作业（ 4 ） 一、单项选择题 1. 顺序查找方法适合于存储结构为

56、（ D ）的线性表。 A散列存储B 索引存储 C散列存储或索引存储D 顺序存储或链接存储 2对线性表进行二分查找时，要求线性表必须（C ）。 A 以顺序存储方式 B以链接存储方式 C 以顺序存储方式 ，且数据元素有序 D以链接存储方式，且数据元素有序 3. 对于一个线性表， 若要求既能进行较快地插入和删除， 又要求存储结构能够反映数据元素之间的逻辑关系， 则应该 （ B ） A以顺序存储方式B 以链接存储方式 C以索引存储方式D 以散列存储方式 C ）。 4采用顺序查找方法查找长度为 n 的线性表时，每个元素的平均查找长度为（ C (n+1)/2 D (n-1)/2 An B n/2 5哈希函

57、数有一个共同的性质，即函数值应当以（D ）取其值域的每个值。 A最大概率B 最小概率 C 平均概率 D 同等概率 6有一个长度为 10 的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（ A ） A29/10B31/10 C 26/10 D 29/9 7已知一个有序表为 11,22,33,44,55,66,77,88,99 ，则顺序查找元素 55 需要比较（ C ）次。 A 3B 4C 5 D 6 8顺序查找法与二分查找法对存储结构的要求是（D ） A顺序查找与二分查找均只是适用于顺序表 B顺序查找与二分查找均既适用于顺序表，也适用于链表 C顺序查找只是适用于顺序表

58、D二分查找适用于顺序表 9有数据 53,30,37,12,45,24,96 B )。 A 45,24,53,12,37,96,30B ，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应该选择的序列是 37,24,12,30,53,45,96 C 12,24,30,37,45,53,96D 30,24,12,37,45,96,53 10对有 18 个元素的有序表作二分（折半）查找，则查找 A1、 2、3B9、5、 2、3 C9、 5、3D9、4、 2、3 A3 的比较序列的下标可能为（ D ） 11. 对于顺序存储的有序表 5，12，20，26，37，42，46，50，64，若采用

59、折半查找，则查找元素 26 的比较次数是 A.3 B. 3 C. 4 D.5 12. 在所有的排序方法中，关键字比较的次数与记录初始排列秩序无关的是（ C ）。 A. 冒泡排序 B. 希尔排序 C. 直接选择排序 D. 直接插入排序 13. 从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已排序序列的正确的位置上，此方法称为 （ A ） A. 插入排序 B. 选择排序 C. 交换排序 D. 归并排序 14. 从未排序序列中挑选元素， 并将其放入已排序序列的一端， 此方法称为（ C ） A. 插入排序 B. 交换排序 C. 选择排序 D. 归并排序 15. 依次将每两个相邻的

60、有序表合并成一个有序表的排序方法称为（ D ）。 A. 插入排序B.交换排序C.选择排序D.归并排序 16. 当两个元素出现逆序的时候就交换位置，这种排序方法称为（ B ）。 A. 插入排序B.交换排序C.选择排序D.归并排序 17. 每次把待排序的区间划分为左、右两个子区间，其中左区间中记录的关键字均小于等于基准记录的关键字，右区间中记录的关 键字均大于等于基准记录的关键字，这种排序称为（ B ）。 A. 插入排序 B. 快速排序 C. 堆排序 D. 归并排序 18. 在正常情况下，直接插入排序的时间复杂度为（ D ）。 A. O(log2n) B. O(n)C. O(n log 2n) D