严蔚敏 数据结构课后习题及答案解析.docx

严蔚敏 数据结构课后习题及答案解析 第一章 绪论 一、选择题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〕探究算法中的输入和输出的关系 〔C〕分析算法的效率以求改良〔D〕分析算法的易懂性和文档性6.计算机算法指的是〔①〕,它必需具备输入、输出和〔②〕等5个特性 ① 〔A〕计算方法〔B〕排序方法〔C〕解决问题的有限运算序列〔D〕调度方法 ② 〔A〕可执行性、可移植性和可扩大性〔B〕可行性、确定性和有穷性 〔C〕确定性、有穷性和稳定性 〔D〕易读性、稳定性和平安性 二、判定题1.数据的机内表示称为数据的存储构造。

〔 〕 2.算法就是程序〔 〕3.数据元素是数据的最小单位〔 〕4.算法的五个特性为：有穷性、输入、输出、完成性和确定性〔 〕 5.算法的时间困难度取决于问题的规模和待处理数据的初态〔 〕 三、填空题1.数据逻辑构造包括________、________、_________ 和_________四种类型,其中树形构造和图形构造合称为_____ 2.性构造中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最终一个结点______后续结点,其余每个结点有且只有_______个后续结点3.在树形构造中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________ 4.在图形构造中,每个结点的前驱结点数和后续结点数可以_________5.线性构造中元素之间存在________关系,树形构造中元素之间存在______关系,图形构造中元素之间存在_______关系6.算法的五个重要特性是_______、_______、______、_______、_______。

7.数据构造的三要素是指______、_______和________8.链式存储构造与依次存储构造相比拟,主要优点是________________________________ 9.设有一批数据元素,为了最快的存储某元素,数据构造宜用_________构造,为了便利插入一个元素,数据构造宜用____________构造四、算法分析题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、依次存储；链式存储四、算法分析题 for(i=1; inext=p;p->next=s; 〔B〕 s->next=p->next;p->next=s; 〔C〕s->next=p->next;p=s; 〔D〕p->next=s;s->next=p;5.在一个单链表中，假设删除p所指结点的后续结点，那么执行〔 〕〔A〕p->next=p->next->next; 〔B〕p=p->next; p->next=p->next->next; 〔C〕p->next=p->next; 〔D〕p =p->next->next; 6.以下有关线性表的表达中，正确的选项是〔 〕 〔A〕线性表中的元素之间隔是线性关系 〔B〕线性表中至少有一个元素〔C〕线性表中任何一个元素有且仅有一个干脆前趋 〔D〕线性表中任何一个元素有且仅有一个干脆后继 7.线性表是具有n个〔 〕的有限序列〔n≠0)〔A〕表元素 〔B〕字符 〔C〕数据元素 〔D〕数据项 二、判定题1.线性表的链接存储，表中元素的逻辑依次与物理依次必须一样。

〔 〕 2.假如没有供应指针类型的语言，就无法构造链式构造〔 〕3.线性构造的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继〔 〕4.语句p=p->next完成了指针赋值并使p指针得到了p指针所指后继结点的数据域值〔 〕 5.要想删除p指针的后继结点，我们应当执行q=p->next ； p->next=q->next； free(q)〔 〕 三、填空题1.确定P为单链表中的非首尾结点，在P结点后插入S结点的语句为：_______________________ 2.依次表中逻辑上相邻的元素物理位置( )相邻， 单链表中逻辑上相邻的元素物理位置_________相邻3.线性表L＝〔a1，a2，...，an〕采纳依次存储，假定在不同的n＋1个位置上插入的概率一样，那么插入一个新元素平均须要移动的元素个数是________________________ 4.在非空双向循环链表中，在结点q的前面插入结点p的过程如下： p->prior=q->prior; q->prior->next=p; p->next=q;______________________;5.确定L是无表头结点的单链表，是从以下供应的答案中选择适宜的语句序列，分别实现： 〔1〕表尾插入s结点的语句序列是_______________________________ (2) 表尾插入 s结点的语句序列是_______________________________1. p->next=s; 2. p=L; 3. L=s;4. p->next=s->next; 5. s->next=p->next; 6. s->next=L; 7. s->next=null;8. while(p->next!= Q)? p=p-next; 9. while(p->next!=null) p=p->next;四、算法设计题1.试编写一个求确定单链表的数据域的平均值的函数〔数据域数据类型为整型〕。

2.确定带有头结点的循环链表中头指针为head,试写出删除并释放数据域值为x的全部结点的c函数3.某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个循环链表，每个结点有价格、数量和链指针三个域现出库〔销售〕m台价格为h的电视机，试编写算法修改原链表4.某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个循环链表，每个结点有价格、数量和链指针三个域现新到m台价格为h的电视机，试编写算法修改原链表 5.线性表中的元素值按递增有序排列，针对依次表和循环链表两种不同的存储方式，分别编写C函数删除线性表中值介于a与b〔a≤b〕之间的元素6.设A=(a0,a1,a2,...,an-1),B=(b0,b1,b2,...,bm-1)是两个给定的线性表,它们的结点个数分别是n和m,且结点值均是整数假设n=m，且 ai= bi 〔0≤inext; *head->prior=NULL; return(0); } Else{for(j=0;jnext;if(p==NULL||j>i) return(1); p->prior->next=p->next; p->next->prior=p->proir; free(p); return(0); }8. 依次存储: void convert(elemtype list[],int l,int h) /* 将数组中第l个到第h个元素逆置*/ { int i;elemtype temp;for(i=h;ilink; /*q指向an-1结点 */ r=q->link; q->link=NULL; while(r->link!=NULL)r=r->link; /*r指向最终一个bm-1结点 */ *head=q; r->link=p; }该算法的时间困难度为O(n+m),但比依次存储节约时间(不须要移动元素,只需变更指针),空间困难度为O(1) 9.typedef struct node {elemtype data; struct node *link; }NODE;NODE *union(NODE *ah,NODE *bh) {NODE *a,*b,*head,*r,*q; head=ah; a=ah; b=bh;while(a->link!=ah&&b->link!=bh) {r=a->link; q=b->link; a->link=b; b->link=r; a=r; b=q; } if(a->link==ah) /*a的结点个数小于等于b的结点个数 */ {a->link=b;while(b->link!=bh) b=b->link; b->link=head; }if(b->link==bh) /*b的结点个数小于a的结点个数 */ {r=a->link; a->link=b; b->link=r; }return(head); }该算法的时间困难度为O(n+m),其中n和m为两个循环链表的结点个数. 10.typedef struct node {elemtype data; struct node *link; }NODE;void analyze(NODE *a〕 {NODE *rh，*qh，*r,*q,*p；int i=0，j=0；/*i为序号是奇数的结点个数 j为序号是偶数的结点个数 */ p=a；rh=〔NODE *〕malloc〔sizeof〔NODE〕〕；/*rh为序号是奇数的链表头指针 */ qh=(NODE *)malloc(sizeof(NODE)); /*qh为序号是偶数的链表头指针 */ r=rh; q=qh; while(p!=NULL) {r->link=p; r=p; i++; p=p->link; if(p!=NULL) {q->link=p; q=p; j++; p=p->link; } }rh->data=i; r->link=rh; qh->data=j; q->link=qh; } 11.typedef struct node {elemtype data; struct node *link; }NODE;void change(NODE *head) {NODE *p; p=head; if(head!=NULL) { 本文来源：网络收集与整理，如有侵权，请联系作者删除，谢谢！第9页 共9页第 9 页 共 9 页第 9 页 共 9 页第 9 页 共 9 页第 9 页 共 9 页第 9 页 共 9 页第 9 页 共 9 页第 9 页 共 9 页第 9 页 共 9 页第 。