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

数据结构（本）课程作业 作业1 （本部分作业覆盖教材第1-2章的内容） 一、单项选择题 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．与计算机的操作系统  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=qnext  D．q->next=NULL 12．在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（  D  ）。 A．p->next= s; snext= pnext    B．p->next=snext; C．p=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）。 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 ）。 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(1in+1)个元素之前插入新元素时，需向后移动 n-i+1 个数据元素。 2．从长度为n的采用顺序存储结构的线性表中删除第i(1in+1)个元素 ，需向前移动  n-i 个元素。 3．数据结构按结点间的关系，可分为4种逻辑结构：    集合  、 线性结构  、    树形结构  、  图状结构   。 4．数据的逻辑结构在计算机中的表示称为  物理结构  或  存储结构  。 5．除了第1个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的数据结构为  线性结构  ，每个结点可有任意多个前驱和后继结点数的结构为  非线性结构    。 6．算法的5个重要特性是  有穷性  、  确定性  、  可形性  、  有零个或多个输入  、 有零个或多个输出  。 7．数据结构中的数据元素存在多对多的关系称为__图状结构__结构。 8．数据结构中的数据元素存在一对多的关系称为_树形结构__结构。 9．数据结构中的数据元素存在一对一的关系称为_线性结构_结构。 10．要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为___ n-1__和 __ O(n)___ 。 11．在一个单链表中p所指结点之后插入一个s所指结点时，应执行__ 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．每个结点只包含一个指针域的线性表叫  单链表  。 16．线性表具有  顺序存储  和  链式存储  两种存储结构。 17．数据的逻辑结构是从逻辑关系上描述数据，它与数据的关系  存储结构  无关，是独立于计算机的。 18．在双向循环链表的每个结点中包含  两个 指针域，其中next指向它的  直接后继  ，prior指向它的  直接前驱  ，而头结点的prior指向  尾结点  ，尾结点的next指向  头结点  。 19．单向循环链表是单向链表的一种扩充，当单向链表带有头结点时，把单向链表中尾结点的指针域由空指针改为  头结点的指针  ；当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向  指向第一个结点的指针    。 20．线性链表的逻辑关系时通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种  链式  存储结构，又称为  链表  。  三、问答题 1．简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的与实现？ 答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中的存储表示称为数据的存储结构。可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示。尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大。 2．解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。 答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，，要求内存中存储单元的地址必须是连续的。 优点：一般情况下，存储密度大，存储空间利用率高。 缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。 链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。 优点：插入和删除元素时很方便，使用灵活。 缺点：存储密度小，存储空间利用率低。 3．什么情况下用顺序表比链表好？ 答：顺序表适于做查找这样的静态操作，链表适于做插入和删除这样的动态操作。如果线性表的变化长度变化不大，且其主要操作是查找，则采用顺序表；如果线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。 4．头指针、头结点、第一个结点（或称首元结点）的区别是什么？ 头结点是在链表的开始结点之前附加的一个结点；第一个结点（或称首元结点）是链表中存储第一个数据元素的结点；头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。 5．解释带头结点的单链表和不带头结点的单链表的区别。 答： 带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作上。 在结构上，带头结点的单链表，不管链表是否为空，均含有一个头结点，不带头结点的单链表不含头结点。 在操作上，带头结点的单链表的初始化为申请一个头结点。无论插入或删除的位置是地第一个结点还是其他结点，算法步骤都相同。不带头结点的单链表，其算法步骤要分别考虑插入或删除的位置是第一个结点还是其他结点。因为两种情况的算法步骤不同。 四、程序填空题 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;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) /*对线性表(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;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)&&(jnext; 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，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== m0          B．sq->rear-sq->front-1= = m0      C．sq->front==sq->rear                D．sq->front==sq->rear+1 9．判断一个循环队列Q（最多元素为m0）为空的条件是（ A  ）。 A．Q->front==Q->rear                B．Q->front!=Q->rear C．Q->front==(Q->rear+1)% m0      D．Q->front!= (Q->rear+1)%m0  10．判断栈S满（元素个数最多n个）的条件是（C  ）。 A．s->top==0                B．s->top!=0 C．s->top==n-1              D．s->top!=n-1  11．一个队列的入队顺序是a,b,c,d，则离队的顺序是（ B ）。 A．a,d,cb      B．a,b,c,d      C．d,c,b,a    D．c,b,d,a 12．如果以链表作为栈的存储结构，则退栈操作时（  C  ）。 A．必须判断栈是否满          B．判断栈元素类型  C．必须判断栈是否空          D．对栈不作任何判断 13．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（ B  ）结构。 A．堆栈      B．队列      C．数组      D．先性表 14．一个递归算法必须包括（ B ）。 A．递归部分        B．终止条件和递归部分      C．迭代部分        D．终止条件和迭代部分 15．从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则执行（ 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;      B．r->next=s;r=s;  C．s->next=r;r=s;        D．s->next=f;f=s; 18.以下陈述中正确的是（  A ）。 A．串是一种特殊的线性表        B．串的长度必须大于零 C．串中元素只能是字母        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==“English”，其子串的个数是（  D ）。 A．9      B．16        C． 36        D．28 23．串与普通的线性表相比较，它的特殊性体现在（ C ）。 A．顺序的存储结构            B．链接的存储结构  C．数据元素是一个字符        D．数据元素可以任意 24．空串与空格串（  B  ）。 A．相同        B．不相同      C．可能相同  D．无法确定 25．两个字符串相等的条件是（  D）。 A．两串的长度相等      B．两串包含的字符相同 C．两串的长度相等，并且两串包含的字符相同 D．两串的长度相等，并且对应位置上的字符相同 26．在实际应用中，要输入多个字符串，且长度无法预定。则应该采用（A ）存储比较合适（    ）。 A．链式        B． 顺序        C．堆结构    D．无法确定        27.一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的存储地址为100，则该数组的首地址是（ C  ）。 A．64            B．28 C．70            D．90 28．稀疏矩阵采用压缩存储的目的主要是（D  ）。 A．表达变得简单                B．对矩阵元素的存取变得简单    C．去掉矩阵中的多余元素        D．减少不必要的存储空间的开销 29．一个非空广义表的表头（ C  ）。 A．不可能是原子                B．只能是子表 C．只能是原子                  D．可以是子表或原子      30．常对数组进行的两种基本操作是（  C  ）。 A．建立与删除                  B．索引与、和修改 C．查找和修改                  D．查找与索引 31. 设二维数组A[5][6]按行优先顺序存储在内存中，已知A[0][0] 起始地址为1000，每个数组元素占用5个存储单元，则元素A[4][4]的地址为（  A    ）。 A．1140        B．1145      C． 1120        D．1125 32．设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a9,2在一维数组B中的下标是（  D  ）。 A．41            B．32            C．18          D．38 二、填空题 1．栈是限定在表的一端进行插入和删除操作的线性表，又称为  后进先出  。 2．循环队列队头指针在队尾指针  下一个      位置，队列是“满”状态 3．在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针  增1        ，当删除一个元素队列时，头指针  增1        。 4．循环队列的引入，目的是为了克服  假上溢  。 5．向顺序栈插入新元素分为三步：第一步进行  栈是否满  判断，判断条件是    s->top=MAXSIZE-1  ；第二步是修改      栈顶指针      ；第三步是把新元素赋给      栈顶对应的数组元素  。同样从顺序栈删除元素分为三步：第一步进行    栈是否空        判断，判断条件是    s->top=-1      。第二步是把  栈顶元素        ；第三步      修改栈顶指针          。 6．假设以S和X分别表示入栈和出栈操作，则对输入序列a,b,c,d,e一系列栈操作SSXSXSSXXX之后，得到的输出序列为    bceda          。 7．一个递归算法必须包括    终止条件      和    递归部分      。 8．判断一个循环队列LU（最多元素为m0）为空的条件是    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．在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为___ r->next=s _____和r=s; (结点的指针域为next) 13．在一个链队中，设f和r分别为队头和队尾指针，则删除一个结点的操作为__ f=f->next ______。 (结点的指针域为next) 14．串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是  字符      。 15．串的两种最基本的存储方式是    顺序存储方式            和      链式存储方式            。 16．空串的长度是    0      ；空格串的长度是    空格字符的个数          。 17．需要压缩存储的矩阵可分为      特殊        矩阵和      稀疏        矩阵两种。 18．设广义表L=（（），（）），则表头是  （）        ，表尾是    （（））          ，L的长度是    2      。 19．广义表A（（a,b,c）,(d,e,f)）的表尾为    （（d,e,f））        。 20．两个串相等的充分必要条件是_______串长度相等且对应位置的字符相等            ___。 21．设有n阶对称矩阵A，用数组s进行压缩存储，当ij时，A的数组元素aij相应于数组s的数组元素的下标为__ i(i-1)/2+j _____。（数组元素的下标从1开始） 22．对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的___行下标____、___列下标___和___非零元素值____三项信息。 三、问答题 1．简述栈和一般线性表的区别。 答：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。 2．简述队列和一般线性表的区别。 队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的删除只能在队头进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。 3．链栈中为何不设头结点？ 答：因为链栈只在链头插入和删除结点，不可能在链表中间插入和删除结点，算法实现很简单，所以一般不设置头结点。 4．利用一个栈，则： （1）如果输入序列由A，B，C组成，试给出全部可能的输出序列和不可能的输出序列。 （2）如果输入序列由A，B，C，D组成，试给出全部可能的输出序列和不可能的输出序列。 答： （1）栈的操作特点是后进先出，因此输出序列有： 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不可能由输入序列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出栈  输出序列：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最先的次序有哪几个？ 答：从题中可知，要使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，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(n>0)个元素a1 ,a2…ai… an的有限序列，其中ai或者是原子或者是一个广义表。所以，广义表是一种递归数据结构，而线性表没有这种特性，线性表可以看成广义表的特殊情况，当ai都是原子时，广义表退化成线性表。 四、程序填空题 1．在下面空格处填写适当的语句，以使下面的链式队列取出元素的算法完整。  int write(LinkQueue *q) {QueueNode *p; if (q->front==q->rear)　          /*队空*/ {printf(“underflow”); exit(0);} while (q->front->next != NULL) {p=q->front->next;