作业1
一、单项选择题
1．在数据结构中，从逻辑上可以把数据结构分为（C ）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结
构
C．线性结构和非线性结构 D．内部结构和外部机构 2．下列说法中，不正确的是（ D ）。 A．数据元素是数据的基本单位
B．数据项是数据中不可分割的最小可标识单位 C．数据可有若干个数据元素构成 D．数据项可由若干个数据元素构成 3．一个存储结点存储一个（ B ）。
A．数据项 B．数据元素 C．数据结构 D．数据类型
4．数据结构中，与所使用的计算机无关的是数据的（ C ）。 A．存储结构 B．物理结构 C．逻辑结构 D．物理和存储结构 5．下列的叙述中，不属于算法特性的是（ D ）。 A．有穷性 B．输入性 C．可行性 D．可读性 6．算法分析的目的是（ C ）。
A．找出数据结构的合理性 B．研究算法中的输入和输出的关系
C．分析算法的效率以求改进 D．分析算法的易懂性和
文档性
7．数据结构是一门研究计算机中（ B ）对象及其关系的科学。
A．数值运算 B．非数值运算 C．集合 D．非集合 8．算法的时间复杂度与（ C ）有关。
A．所使用的计算机 B．与计算机的操作系统
A．head = =NULL
B．head->next= =NULL C．head->next= =head
D．head!=NULL
16．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（ C ）。 A．p=q->next B．p->next=q C．p->next=q->next D．q->next=NULL
17．在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（C ）。
A．r=f->next; B．r=r->next;
C．f=f->next; D．f=r->next;
18．在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（ B ）。
（本部分作业覆盖教材第1-2章的内容）
C．与算法本身 D．与数据结构
9．设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），则移动元素个数为（ A ）。 A．n-i+1 B．n-i C．n-i-1 D．i
10．设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（ B ）。
A．n-i+1 B．n-i C．n-i-1 D．i
11．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（ C ）。
A．p=q->next B．p->next=q C．p->next=q?next
D．q->next=NULL
12．在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（ D ）。 A
C
．
p->next=
．s;
s?next=
p?next
B．p->next=s?next;
D．s->next=p->next; p->next=s;
13．非空的单向循环链表的尾结点满足（C ）（设头指针为head，指针p指向尾结点）。
A.．P->next= =NULL B．P= =NULL C．P->next= =head D．P= = head 14．链表不具有的特点是（ A ）。
A．可随机访问任一元素 B．插入删除不需要移动元素
C．不必事先估计存储空间 D．所需空间与线性表长度成正比
15．带头结点的链表为空的判断条件是（ B ）（设头指针为head）。
p=s->next
A．f->next=s; f=s; B．r->next=s;r=s; C．s->next=r;r=s; D．s->next=f;f=s; 19.一个顺序表第一个元素的存储地址是90，每个元素的长度为2，则第6个元素的地址是（B ）。
A．98 B．100 C．102 D．106 20．有关线性表的正确说法是（ D ）。
A．每个元素都有一个直接前驱和一个直接后继 B．线性表至少要求一个元素
C．表中的元素必须按由小到大或由大到下排序 D．除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继
二、填空题
1．在一个长度为n的顺序存储结构的线性表中，向第i(1?i?n+1)个元素之前插入新元素时，需向后移动 n-i+1 个数据元素。
2．从长度为n的采用顺序存储结构的线性表中删除第i(1?i?n+1)个元素 ，需向前移动 n-i 个元素。
3．数据结构按结点间的关系，可分为4种逻辑结构： 集合 、
线性结构 、 树形结构 、 图状结构 。
4．数据的逻辑结构在计算机中的表示称为 物理结构 或 存储结构 。
有零个或多个输出 。
7．数据结构中的数据元素存在多对多的关系称为__图状结构__结构。
8．数据结构中的数据元素存在一对多的关系称为_树形结构__结构。
9．数据结构中的数据元素存在一对一的关系称为_线性结构_结构。
10．要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为___ n-1__和 __ O(n)___ 。
应执行__ s->next=p->next ___和p->next=s;的操作。
12．设有一个头指针为head的单向循环链表，p指向链表中的结点，若
p->next= =__ head __，则p所指结点为尾结点。
13．在一个单向链表中，要删除p所指结点，已知q指向p所指结点的前驱结点。则可以用操作_ q->next=p->next __。
14．设有一个头指针为head的单向链表，p指向表中某一个结点，且有p->next= =NULL,通过操作__ p->next=head __,就可使该单向链表构造成单向循环链表。
15．每个结点只包含一个指针域的线性表叫 单链表 。 17．数据的逻辑结构是从逻辑关系上描述数据，它与数据的关系 存储结构 无关，是独立于计算机的。
18．在双向循环链表的每个结点中包含 两个 指针域，其中next指向它的 直接后继 ，prior指向它的 直接前驱 ，而
19．单向循环链表是单向链表的一种扩充，当单向链表带有头结点时，把单向链表中尾结点的指针域由空指针改为 头结点的指针 ；当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向 指向第一个结点的指针 。
20．线性链表的逻辑关系时通过每个结点指针域中的指针来表存储结构，又称为 链表 。 三、问答题
1．简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？
答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中的存储表示称为数据的存储结构。可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示。尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑
5．除了第1个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的数据结构为 线性结构 ，每个结点可有任意多个前驱和后继结点数的结构为 非线性结构 。
6．算法的5个重要特性是 有穷性 、 确定性 、 可形性 、 有零个或多个输入 、
结构的特点。采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大。
2．解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。
答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，，要求内存中存储单元的地址必须是连续的。
优点：一般情况下，存储密度大，存储空间利用率高。 缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能
链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。
优点：插入和删除元素时很方便，使用灵活。 缺点：存储密度小，存储空间利用率低。 3．什么情况下用顺序表比链表好？
答：顺序表适于做查找这样的静态操作，链表适于做插入和删除这样的动态操作。如果线性表的变化长度变化不大，且其主要操作是查找，则采用顺序表；如果线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。
头结点是在链表的开始结点之前附加的一个结点；第一个结点（或称首元结点）是链表中存储第一个数据元素的结点；头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。 5．解释带头结点的单链表和不带头结点的单链表的区别。
带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作上。
在结构上，带头结点的单链表，不管链表是否为空，均含有一个头结点，不带头结点的单链表不含头结点。
在操作上，带头结点的单链表的初始化为申请一个头结点。都相同。不带头结点的单链表，其算法步骤要分别考虑插入或删除的位置是第一个结点还是其他结点。因为两种情况的算法步骤不同。
四、程序填空题
1．下列是用尾插法建立带头结点的且有n个结点的单向链表的算法，请在空格内填上适当的语句。
NODE *create1(n)
/* 对线性表(1,2,.....,n),建立带头结点的单向链表 */ {
NODE *head,*p,*q;
11．在一个单链表中p所指结点之后插入一个s所指结点时，得到充分利用；（3）表的容量难以扩充。
16．线性表具有 顺序存储 和 链式存储 两种存储结构。 4．头指针、头结点、第一个结点（或称首元结点）的区别是什么？
头结点的prior指向 尾结点 ，尾结点的next指向 头结点 。 答：
示的。其逻辑顺序和物理存储顺序不再一致，而是一种 链式 无论插入或删除的位置是地第一个结点还是其他结点，算法步骤
int i;
p=(NODE *)malloc(sizeof(NODE)); head=p; q=p; p->next=NULL; for(i=1;i<=n;i++) {
p=(NODE *)malloc(sizeof(NODE)); （1）p->data=i ; （2）p->next=NULL ; （3）q->next=p ; （4） q=p ; }
return(head); }
2．下列是用头插法建立带头结点的且有n个结点的单向链表的算法，请在空格内填上适当的语句。
NODE *create2(n) */ {
NODE *head,*p,*q; int i;
p=(NODE *)malloc(sizeof(NODE)); （1） head=p ; p->next=NULL;
（2） q=p ; for(i=1;i<=n;i++) {
p=(NODE *)malloc(sizeof(NODE)); p->data=i; if(i==1)
（3） p->next=NULL ;
else
（4） p->next=q->next ; （5） q->next=p ; }
return(head); }
3．下列是在具有头结点单向列表中删除第i个结点，请在空格内填上适当的语句。
int delete(NODE *head,int i) {
NODE *p,*q; int j; q=head; j=0;
while((q!=NULL)&&(j } { q=q->next; j++; } if(q==NULL) return(0); （2） q->next=p->next ; free(p); return(1); 五、完成：实验1――线性表 根据实验要求（见教材P201-202）认真完成本实验，并提交实验报告。 数据结构（本）课程作业2 （本部分作业覆盖教材第3-5章的内容） 一、单项选择题 A．3，2，1 B．2，1，3 C．3，1，2 D．1，3，2 2．一个队列的入队序列是1，2，3，4。则队列的输出序列是（ B ）。 A．4，3，2，1 B．1，2，3，4 C．1，4，3，2 D．3，2，4，1 3．向顺序栈中压入新元素时，应当（ A ）。 A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针 C．先后次序无关紧要 D．同时进行 4．在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（ C ）。 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．在一个栈顶指针为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; 6．一般情况下，将递归算法转换成等价的非递归算法应该设置（ A ）。 A．栈 B．队列 C．堆栈或队列 D．数组 7．表达式a*(b+c)-d的后缀表达式是（ B ）。 A．abcd*+- B．abc+*d- C．abc*++d- D．-+*abcd 8．判断一个顺序队列sq（最多元素为m0）为空的条件是（ C ）。 A ． sq->rear-sq->front== B．sq->rear-sq->front-1= = m0 （1） p=q->next ; /*对线性表(n,n-1,.....,1),建立带头结点的线性链表 1．若让元素1，2，3依次进栈，则出栈顺序不可能为（ C ）。 m0