数据结构习题及答案——严蔚敏课后习题答案

1、第一章 绪论 选择题 1.组成数据的基本单位是 a数据项b数据类型c数据元素d数据变量 2.数据结构是研究数据的 以及它们之间的相互关系。 a理想结构物理结构 b理想结构抽象结构 c物理结构逻辑结构 d抽象结构逻辑结构 3.在数据结构中从逻辑上可以把数据结构分成 a动态结构和静态结构 b紧凑结构和非紧凑结构 c线性结构和非线性结构d内部结构和外部结构 4.数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间的和运算等的学科。 a数据元素b计算方法c逻辑存储d数据映像 a结构 b关系 c运算 d算法 5.算法分析的目的是。 a 找出数据结构的合理性 b研究算法中的输入和输出的关系

2、c分析算法的效率以求改进d分析算法的易懂性和文档性 6.计算机算法指的是它必须具备输入、输出和等5个特性。 a计算方法b排序方法c解决问题的有限运算序列d调度方法 a可执行性、可移植性和可扩充性b可行性、确定性和有穷性 c确定性、有穷性和稳定性 d易读性、稳定性和安全性 二、判断题 1.数据的机内表示称为数据的存储结构。 2.算法就是程序。 3.数据元素是数据的最小单位。 4.算法的五个特性为有穷性、输入、输出、完成性和确定性。 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。 三、填空题 1.数据逻辑结构包括_、_、_ 和_四种类型其中树形结构和图形结构合称为_。 2.在线性结构中第

3、一个结点_前驱结点其余每个结点有且只有_个前驱结点最后一个结点_后续结点其余每个结点有且只有_个后续结点。 3.在树形结构中树根结点没有_结点其余每个结点有且只有_个前驱结点叶子结点没有_结点其余每个结点的后续结点可以_。 4.在图形结构中每个结点的前驱结点数和后续结点数可以_。 5.线性结构中元素之间存在_关系树形结构中元素之间存在_关系图形结构中元素之间存在_关系。 6.算法的五个重要特性是_、_、_、_、_。 7.数据结构的三要素是指_、_和_。 8.链式存储结构与顺序存储结构相比较主要优点是_。 9.设有一批数据元素为了最快的存储某元素数据结构宜用_结构为了方便插入一个元素数据结构宜用

4、_结构。 四、算法分析题 1.求下列算法段的语句频度及时间复杂度 参考答案 选择题1. c 2.c 3. c 4. a、b 5. c 6.c、b 二、判断题:1、 2、 3、 4、 5、 三、填空题 1、线性、树形、图形、集合 非线性网状 2、没有1没有1 3、前驱1后继任意多个 4、任意多个 5、一对一一对多多对多6、有穷性确定性可行性输入输出 7、数据元素逻辑结构存储结构 8、插入、删除、合并等操作较方便 9、顺序存储链式存储 四、算法分析题 fori1 iltn i forj 1 j lti j xx1 分析该算法为一个二重循环执行次数为内、外循环次数相乘但内循环次数不固定与外循环有关因

5、些时间频度tn123nnn1/2 有 1/4tn/n21故它的时间复杂度为n2 即n与n2 数量级相同。 2、分析下列算法段的时间频度及时间复杂度 for i1iltni for j1jltij for k1kltjk xij-k 分析算法规律可知时间频度tn112123.123n 由于有1/6 tn/ n3 1故时间复杂度为n3 第二章 线性表 一、选择题 1.一个线性表第一个元素的存储地址是100每个元素的长度为2则第5个元素的地址是 a110 b108c100 d120 2. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变平均要移动 个元素。 a64b63 c63.5 d

6、7 3.线性表采用链式存储结构时其地址 。 a 必须是连续的 b 部分地址必须是连续的 c 一定是不连续的 d 连续与否均可以 4. 在一个单链表中若p所指结点不是最后结点在p之后插入s所指结点则执行 as-gtnextpp-gtnexts b s-gtnextp-gtnextp-gtnexts cs-gtnextp-gtnextps dp-gtnextss-gtnextp 5.在一个单链表中若删除p所指结点的后续结点则执行 ap-gtnextp-gtnext-gtnext bpp-gtnext p-gtnextp-gtnext-gtnext cp-gtnextp-gtnext dp p-gt

7、next-gtnext 6.下列有关线性表的叙述中正确的是 a线性表中的元素之间隔是线性关系 b线性表中至少有一个元素 c线性表中任何一个元素有且仅有一个直接前趋 d线性表中任何一个元素有且仅有一个直接后继 7.线性表是具有n个 的有限序列n0 a表元素 b字符 c数据元素 d数据项 二、判断题 1.线性表的链接存储表中元素的逻辑顺序与物理顺序一定相同。 2.如果没有提供指针类型的语言就无法构造链式结构。 3.线性结构的特点是只有一个结点没有前驱只有一个结点没有后继其余的结点只有一个前驱和后继。 4.语句pp-gtnext完成了指针赋值并使p指针得到了p指针所指后继结点的数据域值。 5.要想删

8、除p指针的后继结点我们应该执行qp-gtnext p-gtnextq-gtnext freeq。 三、填空题 1.已知p为单链表中的非首尾结点在p结点后插入s结点的语句为_ 。 2.顺序表中逻辑上相邻的元素物理位置 相邻 单链表中逻辑上相邻的元素物理位置_相邻。 3.线性表la1a2.an采用顺序存储假定在不同的n1个位置上插入的概率相同则插入一个新元素平均需要移动的元素个数是_ 4.在非空双向循环链表中在结点q的前面插入结点p的过程如下 p-gtpriorq-gtprior q-gtprior-gtnextp p-gtnextq _ 5.已知l是无表头结点的单链表是从下列提供的答案中选择合适

9、的语句序列分别实现 1表尾插入s结点的语句序列是_ 2 表尾插入 s结点的语句序列是_ p-gtnexts pl ls p-gtnexts-gtnext s-gtnextp-gtnext s-gtnextl s-gtnextnull whilep-gtnext q pp-next whilep-gtnextnull pp-gtnext 四、算法设计题 1.试编写一个求已知单链表的数据域的平均值的函数数据域数据类型为整型。 2.已知带有头结点的循环链表中头指针为head试写出删除并释放数据域值为x的所有结点的c函数。 3.某百货公司仓库中有一批电视机按其价格从低到高的次序构成一个循环链表每个结点

10、有价格、数量和链指针三个域。现出库销售m台价格为h的电视机试编写算法修改原链表。 4.某百货公司仓库中有一批电视机按其价格从低到高的次序构成一个循环链表每个结点有价格、数量和链指针三个域。现新到m台价格为h的电视机试编写算法修改原链表。 5.线性表中的元素值按递增有序排列针对顺序表和循环链表两种不同的存储方式分别编写c函数删除线性表中值介于a与bab之间的元素。 6.设aa0a1a2.an-1bb0b1b2.bm-1是两个给定的线性表它们的结点个数分别是n和m且结点值均是整数。 若nm且 ai bi 0iltn 则ab 若nltm 且aibi 0iltn 则altb 若存在一个j jltm j

11、ltn 且aibi 0iltj 若ajltbj则altb否则 agtb。 试编写一个比较a和b的c函数该函数返回 -1或 0或 1分别表示 altb或 ab或 agtb。 7.试编写算法删除双向循环链表中第k个结点。 8.线性表由前后两部分性质不同的元素组成a0a1.an-1b0b1.bm-1m和n为两部分元素的个数若线性表分别采用数组和链表两种方式存储编写算法将两部分元素换位成b0b1.bm-1a0a1.an-1分析两种存储方式下算法的时间和空间复杂度。 9.用循环链表作线性表a0a1.an-1和b0b1.bm-1的存储结构头指针分别为ah和bh设计c函数把两个线性表合并成形如a0b0a1b

12、1的线性表要求不开辟新的动态空间利用原来循环链表的结点完成合并操作结构仍为循环链表头指针为head并分析算法的时间复杂度。 10.试写出将一个线性表分解为两个带有头结点的循环链表并将两个循环链表的长度放在各自的头结点的 数据域中的c函数。其中线性表中序号为偶数的元素分解到第一个循环链表中序号为奇数的元素分解到第二个循环链表中。 11.试写出把线性链表改为循环链表的c函数。 12.己知非空线性链表中x结点的直接前驱结点为y试写出删除x结点的c函数。 参考答案 一、选择题1. b 2.c 3. d 4. b 5. a 6.a 7、c 二、判断题参考答案1、2、3、4、5、 三、填空题1、s-gtn

13、extp-gtnext p-gtnexts 2、一定不一定 3、n/2 4、q-gtpriorp 5、16 3 2 2 91 7 四、算法设计题1、 include quotstdio.hquot include quotmalloc.hquot typedef struct node int data struct node link node int avernode head int i0sum0ave node p phead whilepnull pp-gtlinki sumsump-gtdata avesum/i return ave 2、 include quotstdio.hq

14、uot include quotmalloc.hquot typedef struct node int data / 假设数据域为整型 / struct node link node void del_linknode headint x / 删除数据域为x的结点/ node pqs phead qhead-gtlink whileqhead ifq-gtdatax p-gtlinkq-gtlink sq qq-gtlink frees else pq qq-gtlink 3、 void delnode headfloat priceint num node pqs pheadqhead-g

15、tnext whileq-gtpriceltpriceampampqhead pq qq-gtnext ifq-gtpriceprice q-gtnumq-gtnum-num else printfquot无此产品quot ifq-gtnum0 p-gtnextq-gtnext freeq 4、 include quotstdio.hquot include quotmalloc.hquot typedef struct node float price int num struct node next node void insnode headfloat priceint num node

16、 pqs pheadqhead-gtnext whileq-gtpriceltpriceampampqhead pq qq-gtnext ifq-gtpriceprice q-gtnumq-gtnumnum else snode mallocsizeofnode s-gtpriceprice s-gtnumnum s-gtnextp-gtnext p-gtnexts 5、顺序表 算法思想从0开始扫描线性表用k记录下元素值在a与b之间的元素个数对于不满足该条件的元素前移k个位置最后修改线性表的长度。 void delelemtype listint nelemtype aelemtype b i

17、nt i0k0 whileiltn iflistigtaampamplistiltb k else listi-klisti i nn-k / 修改线性表的长度/ 循环链表: void delnode headelemtype aelemtype b node pq p headqp-gtlink / 假设循环链表带有头结点 / whileqhead ampamp q-gtdatalta pq qq-gtlink whileqhead ampamp q-gtdataltb rq qq-gtlink freer ifpq p-gtlinkq 6、 define maxsize 100 int l

18、istamaxsizelistbmaxsize int nm int compareint aint b int i0 whileaibiampampiltnampampiltm i ifnmampampin return0 ifnltmampampin return-1 ifngtmampampim return1 ifiltnampampiltm ifailtbi return-1 else ifaigtbi return1 7、 void deldunode headint i dunode p ifi0 headhead-gtnext head-gtpriornull return0

19、else forj0jltiampamppnullj pp-gtnext ifpnulljgti return1 p-gtprior-gtnextp-gtnext p-gtnext-gtpriorp-gtproir freep return0 8. 顺序存储: void convertelemtype listint lint h / 将数组中第l个到第h个元素逆置/ int i elemtype temp forihiltlh/2i templisti listilistlh-i listlh-itemp void exchangeelemtype listint nint m conver

20、tlist0nm-1 convertlist0m-1 convertlistmnm-1 该算法的时间复杂度为onm空间复杂度为o1 链接存储:不带头结点的单链表 typedef struct node elemtype data struct node link node void convertnode headint nint m node pqr int i phead qhead fori0iltn-1i qq-gtlink /q指向an-1结点 / rq-gtlink q-gtlinknull whiler-gtlinknull rr-gtlink /r指向最后一个bm-1结点 /

21、headq r-gtlinkp 该算法的时间复杂度为onm但比顺序存储节省时间不需要移动元素只需改变指针空间复杂度为o1 9. typedef struct node elemtype data struct node link node node unionnode ahnode bh node abheadrq headah aah bbh whilea-gtlinkahampampb-gtlinkbh ra-gtlink qb-gtlink a-gtlinkb b-gtlinkr ar bq ifa-gtlinkah /a的结点个数小于等于b的结点个数 / a-gtlinkb while

22、b-gtlinkbh bb-gtlink b-gtlinkhead ifb-gtlinkbh /b的结点个数小于a的结点个数 / ra-gtlink a-gtlinkb b-gtlinkr returnhead 该算法的时间复杂度为onm其中n和m为两个循环链表的结点个数. 10. typedef struct node elemtype data struct node link node void analyzenode a node rhqhrqp int i0j0/i为序号是奇数的结点个数 j为序号是偶数的结点个数 / pa rhnode mallocsizeofnode/rh为序号是

23、奇数的链表头指针 / qhnode mallocsizeofnode /qh为序号是偶数的链表头指针 / rrh qqh whilepnull r-gtlinkp rp i pp-gtlink ifpnull q-gtlinkp qp j pp-gtlink rh-gtdatai r-gtlinkrh qh-gtdataj q-gtlinkqh 11. typedef struct node elemtype data struct node link node void changenode head node p phead ifheadnull whilep-gtlinknull pp-

24、gtlink p-gtlinkhead 12. typedef struct node elemtype data struct node link node void delnode xnode y node pq elemtype d1 py qx whileq-gtnextnull / 把后一个结点数据域前移到前一个结点/ p-gtdataq-gtdata qq-gtlink pq p-gtlinknull / 删除最后一个结点/ freeq 第三章 栈和队列 一、选择题 1. 一个栈的入栈序列是abcde则栈的不可能的输出序列是 。 a edcbabdecbacdceab dabcde

25、 2.栈结构通常采用的两种存储结构是 。 a 线性存储结构和链表存储结构b散列方式和索引方式 c链表存储结构和数组 d线性存储结构和非线性存储结构 3.判定一个栈st最多元素为m0为空的条件是 。 a st-top0 bst-top0 cst-topm0 dst-topm0 4.判定一个栈st最多元素为m0为栈满的条件是 。 ast-gttop0 bst-gttop0 cst-gttopm0-1dst-gttopm0-1 5.一个队列的入列序列是1234则队列的输出序列是 。 a4321b1234c1432d3241 6.循环队列用数组a0m-1存放其元素值已知其头尾指针分别是front和re

26、ar则当前队列中的元素个数是 arear-frontmm b rear-front1 crear-front-1drear-front 7.栈和队列的共同点是 a 都是先进后出 b都是先进先出 c只允许在端点处插入和删除元素d没有共同点 8.表达式abc-d的后缀表达式是 。 aabcd-babcd- cabcd-d-abcd 9.4个元素a1a2a3和a4依次通过一个栈在a4进栈前栈的状态则不可能的出栈序是 aa4a3a2a1 ba3a2a4a1 ca3a1a4a2 da3a4a2a1 10.以数组q0.m1存放循环队列中的元素变量rear和qulen分别指示循环队列中队尾元素的实际位置和当

27、前队列中元素的个数队列第一个元素的实际位置是 arearqulen brearqulenm cmqulen d1rearmqulen m 二、填空题 1.栈的特点是_队列的特点是_。 2.线性表、栈和队列都是_结构可以在线性表的_位置插入和删除元素对于栈只能在_插入和删除元素对于队列只能在_插入元素和_删除元素。 3.一个栈的输入序列是12345则栈有输出序列12345是_。正确/错误 4.设栈s和队列q的初始状态皆为空元素a1a2a3a4a5和a6依次通过一个栈一个元素出栈后即进入队列q若6个元素出队列的顺序是a3a5a4a6a2a1则栈s至少应该容纳_个元素。 三、算法设计题 1.假设有两

28、个栈s1和s2共享一个数组stackm其中一个栈底设在stack0处另一个栈底设在stackm-1处。试编写对任一栈作进栈和出栈运算的c函数pushxi和popiil2。其中i1表示左边的栈i2表示右边的栈。要求在整个数组元素都被占用时才产生溢出。 2.利用两个栈s1s2模拟一个队列时如何用栈的运算来实现该队列的运算写出模拟队列的插入和删除的c函数。 一个栈s1用于插入元素另一个栈s2用于删除元素. 参考答案 一、选择题 1. c 2.a 3. b 4. b 5. b 6.b 7、c 8、c 9、c 10、d 二、填空题1、先进先出先进后出2、线性 任何 栈顶队尾对头3、正确的 4、3 三、算法设计题 1. define m 100 elemtype stackm int top10top2m-1 int pushelemtype xint i iftop1-top21 return1 /上溢处理/ else ifi1 stacktop1x ifi2stacktop2-x return0 int popelemtype pxint i ifi1 iftop10 return1 else top1- pxstacktop1 return0 else ifi2 iftop2m-1 return1 else top2 pxstacktop2 return0 2. elemtype s1