第一章绪论
一、填空题
1．数据是描述客观事物的数、字符以及所有能输入到计算机且能够被计算机程序加工处理的符号集合。
_________是数据的基本单位；___________是数据的最小单位。通常被计算机加工处理的数据不是孤立无关的，而是彼此之间存在着某种联系，将这种数据间的联系称为________。
2．数据结构进行形式化定义时，可以从逻辑上认为数据结构DS是_________的集合D和D上_________的集合R所构成的二元组：DS=（D，R）。
3．已知某数据结构的二元组形式表示为：A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}。则此数据结构属于_____________结构。
4．一个算法的时间复杂度通常用问题规模大小的函数来表示，当一个算法的时间复杂度与问题规模n大小无关时，则表示为__________；成正比关系时，则表示为___________；成对数关系时，则表示为___________；
成平方关系时，则表示为__________。
5．数据结构的逻辑结构包括_____________、树型结构和图型结构三种类型，其中树型结构和图型结构合称为_____________；数据结构的存储结构主要包括____________和____________两种类型。
6．线性结构的特点是：第一个结点_______前驱结点，其余结点有且仅有_______个前驱结点；最后一个结点_______后继结点，其余每个结点有且仅有_______个后继结点。
7．树型结构的特点是：根结点没有________结点，其余每个结点有且仅有________个前驱结点；叶子结点_________后继结点，其余结点可以有_________个后继结点。
8．图型结构的特点是：每个结点可以有_________个前驱结点和后继结点。
9．程序段for（i=1，s=0；s 10．常见的时间复杂度有常数阶O(1)、对数阶O(log2n)、线性阶O(n)、平方阶O(n2)、线性对数阶O(nlog2n)、立方阶O(n3)、指数阶O(2n)等等，这些数量阶之间的大小关系为__________________________。 二、分析下列用二元组形式表示的数据结构，指出他们分别属于何种类型的数据结构。 1.A=（K，R），其中：K={a，b，c，d，e，f，g，h}，R={r}，r={ 2.B=（K，R），其中：K={a，b，c，d，e，f，g，h}，R={r}，r={ 3.C=（K，R），其中：K={ a，b，c，d，e }，R={r}，r={ 4.D=（K，R），其中：K={48，25，64，57，82，36，75}，R={r1，r2}，r1={<25，36>，<36，48>，<48， 57>，<57，64>，<64，75>，<75，82>}；r2={<48，25>，<48，64>，<64，57>，<64，82>，<25，36>， <25，75>}。 5.E=（K，R），其中：K={1，2，3，4，5，6，7}，R={r}，r={<1，2>，<2，1>，<1，4>，<4，1>，<2， 3>，<3，2>，<3，4>，<4，3>，<1，3>，<3，1>}。 三、指出下列各函数的功能并求出其时间复杂度。 1.void prime(int n) { int i; for(i=2;i<=sqrt(n);i++) if (n %i==0) break; if (i>sqrt(n)) printf(“yes”); else printf(“no”); } 2.long sum1(int n) { long sum,w,i; for(sum=0,i=1;i<=n;i++){ w=1; for(j=1;j<=i;j++) w=w×i; sum=sum+w; } return(sum); } 3.long sum2(int n) { long sum,w,i; for(sum=0, w=1,i=1;i<=n;i++){ w=w×i; sum=sum+w;} return(sum); } 4.void sort(int r[ ],int n) { int i,j; for(i=1; i if(r[j]>r[j+1]) {temp=r[j];r[j]=r[j+1];r[j+1]=temp;} } 补充： 0.分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ 0. N^2 __。for (i=0;i for (j=0;j A[i][j]=0; 1 分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ N^3 __。 s=0; for (i=0;i for (j=0;j for (k=0;k s=s+B[i][j][k]; sum=s; 2 分析下面算法（程序段）给出最大语句频度，该算法的时间复杂度是__根号N __。i=s=0; while (s { i++; s+=i; //s=s+i } 3。分析下面算法（程序段）给出最大语句频度，该算法的时间复杂度是__ log(N)__。i=1; while (i<=n) i=i*2; 第一章参考答案 一、填空题 1． 数据元素，数据项，结构 2． 数据，关系 3． 树型 4． O(1)，O(n)，O(log 2n)，O(n 2) 5． 线性结构，非线性结构，顺序结构，链式结构 6． 无，一，无，一 7． 前驱，一，无，任意 8． 任意 9． O(n 1/2) 分析：设程序段中的循环体执行k 次，则有不等式∑∑+==≤<1 11k i k i i n i 成立，解此不等式得到不等式 2/14/122/34/12-+<≤-+n k n ，因此)()(n O k n f ==。 10． O(1) 二、分析下列用二元组形式表示的数据结构，指出他们分别属于何种类型的数据结构。 1． 线性结构 2． 树型结构 3． 图型结构 4． 图型结构 分析：数据结构D 中的关系集合R 有两个关系r1和r2。如果只考虑关系r1，则为线性结构；如果只考虑关系r2，则为树型结构；如果把关系r1和r2联合起来考虑，则为图型结构。 5． 图型结构 分析：若用图形来表示则可以看出r 是E 上的对称关系，为了简化起见，我们通常把 三、指出下列各函数的功能并求出其时间复杂度。 1． 函数的功能是判断n 是否是一个素数，其时间复杂度为O(n 1/2)。 分析：函数prime 中出现的库函数sqrt 为平方根函数，因此)(1)(n O n n f =-=。 2． 函数的计算∑=n i i 1 !的值，其时间复杂度为O(n 2 )。 3． 函数的计算∑=n i i 1 !的值，其时间复杂度为O(n)。 4． 函数的功能是对数组r 中的n 个元素进行冒泡排序，其时间复杂度为O(n 2)。 分析：)(2/)1()()(211n O n n i n n f n i =-=-=∑-=。 第二章线性表 一、填空题 1．设长度为n的顺序线性表在任何位置上插入或删除操作都是等概率的，则插入一个元素时平均需要移动_______个元素，删除一个元素时平均需要移动______个元素。 2．在顺序线性表中插入一个元素时，插入位置开始后的所有元素均需要________移动一个位置。 3．在顺序线性表中删除一个元素时，被删除元素后的所有元素均需要__________移动一个位置。 4．线性表的链式存储结构中，元素之间的线性关系是通过结点中的________来实现的。 5．线性表的顺序存储结构中逻辑上相邻的元素，物理位置__________相邻；线性表的链式存储结构中逻辑上相邻的元素，物理位置____________相邻。 6．已知单链表的长度为n，则在给定值为x的结点后插入一个新结点的时间复杂度为__________。 7．已知单链表的长度为n，则删除给定值为x的结点的时间复杂度为__________。 8．在单链表中设置头结点的作用是________________________________。 9．双向链表中每个结点含有两个指针域，其中一个指针域指向_______结点，另一个指针域指向______结点。10．在长度为n的线性表中顺序查找某个结点值为X的时间复杂度为______________。 二、选择题 1．在长度为n的顺序线性表中删除第i个元素(1<=i<=n)，则需要向前移动的元素个数为（）。 ⑴n-i ⑵n+1-i ⑶n-1-i ⑷i 2．建立一个长度为n的单链表的时间复杂度为（）。 ⑴O(n) ⑵O(1) ⑶O(n2) ⑷((log2n) 3．设指针p指向单链表中的结点A，结点A的后继结点是结点B，则删除结点B的操作为（）。 ⑴p->next=p ⑵p=p->next ⑶p=p->next->next ⑷p->next=p->next->next 4．设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B之间插入结点X的操作为（）。 ⑴s->next=p->next；p->next=s；⑵q->next=s；s->next=p； ⑶p->next=s->next；s->next=p；⑷p->next=s；s->next=q； 5．在长度为n的顺序线性表中的第i个元素(1<=i<=n+1)之前插入一个新元素时，则需要向后移动的元素个数为（）。 ⑴n-i ⑵n+1-i ⑶n-1-i ⑷i 6．在长度为n的有序线性表中插入一个元素后仍然保持有序的平均时间复杂度为（）。 ⑴O(log2n) ⑵O(1) ⑶O(n2) ⑷O(n) 7．设指针p指向双向链表中的结点A，指针s指向被插入的结点X，则在结点A之后插入结点X的操作为（）。 ⑴p->rlink=s；s->llink=p；p->rlink->llink=s；s->rlink=p->rlink； ⑵s->llink=p；s->rlink=p->rlink；p->rlink=s；p->rlink->llink=s； ⑶p->rlink=s；p->rlink->llink=s；s->llink=p；s->rlink->p->rlink； ⑷s->llink=p；s->rlink=p->rlink；p->rlink->llink=s；p->rlink=s； 8．指针p指向双向链表中的结点A，则删除结点A的操作是（）。 ⑴p->llink->rlink=p->rlink；p->rlink->llink=p->llink； ⑵p->rlink->llink=p->rlink；p->llink->llink=p->llink； ⑶p->llink->rlink=p->llink；p->rlink->llink=p->rlink； ⑷p->rlink->rlink=p->rlink；p->rlink->rlink=p->rlink； 9．线性表采用链式存储结构时，要求存储单元的地址（）。 ⑴必须是连续的⑵部分地址必须是连续的 ⑶一定是不连续的⑷连续不连续都可以 10．设head为单链表的头指针，则不带头结点的单链表为空的判定条件是（）。 ⑴head==NULL ⑵head->next==NULL ⑶head->next==head ⑷head!=NULL 11．设head为单链表的头指针，则带头结点的单链表为空的判定条件是（）。 ⑴head==NULL ⑵head->next==NULL ⑶head->next==head ⑷head!=NULL 12．设head和tail分别为单向循环链表的头指针和尾指针，则下列等式成立的是（）。 ⑴head==tail ⑵head->next==tail ⑶tail->next==head ⑷head->next==tail->next 三、算法设计题 顺序存储结构的类型定义：typedef struct {int a[m]; int n; } sqlist; 链式存储结构的类型定义：typedef struct node {int data; struct node *next;} lklist; 1.建立一个有n个结点的单链表，要求从尾部进行插入。 2.建立一个有n个结点的单链表，要求从头部进行插入。 3.用顺序存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表（a1，a2，……，a n）逆置为(a n， a n-1，……，a1)。 4.用链式存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表（a1，a2，……，a n）逆置为(a n， a n-1，……，a1)。 5.已知集合A、B，求集合C=A∩B算法，要求集合A、B和C均用采用顺序存储结构表示。 6.已知集合A、B，求集合C=A∩B算法，要求集合A、B和C均用采用链式存储结构表示。 7.设计在带有头结点的单向链表中删除值为X的结点算法。 第二章参考答案 一、填空题 1． n/2，(n-1)/2 分析：当在顺序线性表中的第i （1<=i<=n+1）个位置之前插入一个新元素时，从第i 个元素起向后的n+1-i 个元素均要向后移动一个位置。因此在等概率情况下，插入操作中元素的平均移动次数为 ∑ +==-++=112)1(11)(n i n i n n n f ；当在顺序线性表中删除第i （1<=i<=n ）个位置上的元素，从第i+1个元素起向后的n-i 个元素均要向前移动一个位置。因此在等概率情况下，删除操作中元素的平均移动次数为 ∑=-=-=n i n i n n n f 12 1)(1)(。 2． 向后 3． 向前 4． 指针域 5． 一定，不一定 6． O(n) 7． O(n) 8． 消除空表的特殊性，统一表示和处理空表和非空表的情形，从而简化插入和删除等操作的某些细节。 9． 前驱，后继 10． O(n) 二、填空题 1． (1) 2． (1) 分析：建立一个单链表的过程实际上就是在空链表的基础之上从单链表的头部或从单链表的尾部不断插入新结点的过程，因此建立单链表的时间复杂度为O(n)。 3． (4) 4． (2) 5． (2) 6． (4) 分析：在有序的线性表中插入一个元素后仍然保持有序的过程分为两步：第一步查找插入位置，第二步插入新元素。在线性表中查找插入位置的平均时间复杂度为f 1(n)=O(n)，在顺序线性表中插入新元素的平均时间复杂度为f 2(n)=O(n)，而在链式线性表中插入新元素的平均时间复杂度为f 2(n)=O(1)，因此本题中的平均时间复杂度f(n)=O(n)+O(1)=O(n) 或 f(n)=O(n)+O(n)=O(n)。 7． (4) 分析：在双向链表或双向循环链表中插入一个新结点的操作比较繁琐，通常需要修改4个指针域，根据排列公式可知共有4!=24种方案。在这24种方案中，有些方案是可行的，有些方案是不可行的。我们的通常做法是先连接哪些不破坏有用信息的指针域，然后再根据需要连接其余的指针域，在操作过程中注意修改有关结点指针域的操作顺序，以免丢失链域信息而造成链表中断的错误。 8． (1) 分析：在双向链表或双向循环链表中删除一个结点的操作比较相对插入一个新结点而言稍微简单一些，只需要修改两个指针域。首先找到指向前驱结点的指针（p->left ）和指向后继结点的指针（p->right ），然后再分别表示出前驱结点中的右指针域（p->left->right ）和后继结点的左指针域（p->right->left ），最后分别修改前驱结点中的右指针域和后继结点的左指针域。 9． (4) 10．(1) 11．(2) 12．(3) 三、算法设计题 1.建立一个有n个结点的单链表，要求从尾部进行插入。 分析：本题的算法思想是设置指针变量q始终指向当前链表中的最后一个结点，新生成的结点直接在尾部进行插入。这种设置指针变量q的方法使得操作比较简单，否则每次在尾部插入新结点时需要用一个临时指针变量从链表头部移到链表尾部。 void createlklistfromtail (lklist *&head ) { int i; lklist *p,*q; for (i=1,head=0;i<=n;i++) { p=(lklist *)malloc(sizeof(lklist)); scanf("%d",&(p->data));p->next=0; if(i==1)head=q=p;else {q->next=p;q=p;} } } 提示：以下形式参数表中出现在形式参数名前加符号“&”的现象，这种现象在我们常见的Turbo C 2.0版本中不能使用，但在Borland C 3.1及其以后版本中可以使用，它的作用是使得对形式参数的修改可以影响到对应的实在参数。以后算法设计题中经常用到。 2.建立一个有n个结点的单链表，要求从头部进行插入。 void createlklistfromhead (lklist *&head ) { int i; lklist *p,*q; for (i=1,q=head=0;i<=n;i++) { p=(lklist *)malloc(sizeof(lklist)); scanf("%d",&(p->data)); p->next=head; head=p; } } 提示：不断从头部插入新结点的方法来构造单向链表比不断从尾部插入新结点的方法来构造单向链表稍微操作简单一些。但顺序打印从尾部插入建立的单向链表所得到的序列与建立单向链表输入的序列一样，而顺序打印从头部插入建立的单向链表所得到的序列与建立单向链表输入的序列正好相反。 3.用顺序存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表（a1，a2，……，a n）逆置为(a n， a n-1，……，a1)。 void invertsqlist(sqlist &list) { int i,temp,n=list.n; for(i=1;i<=n/2;i++){temp=list.a[i-1]; list.a[i-1]=list.a[n-i]; list.a[n-i]=temp;} } 提示：本题中的循环次数只能是顺序线性表的长度一半，如果循环次数是顺序线性表的长度，则经过逆置后再逆置而还原到初始状态。 4.用链式存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表（a1，a2，……，a n）逆置为(a n， a n-1，……，a1)。 分析：本题的算法思想是依次将单链表中的结点取出来并用指针q指向它，然后再用从头部插入的方法建立一个新的单链表。 void invertlklist(lklist *&head) { lklist *p=head,*q; /*head=0;*/ q=p；p=p->next; q->next=0; while(p!=0){q=p; p=p->next; q->next=head; head=q;} } 5.已知集合A、B，求集合C=A∩B算法，要求集合A、B和C均用采用顺序存储结构表示。 分析：本题的算法思想是顺序取出集合A中的元素A[i]，然后再在集合B中从前向后进行顺序查找，如果找到等于该元素的结点则将其放入集合C中，否则什么也不做。本题算法思想同样适用于其后的第6题。 void intersectionsqlist(sqlist lista, sqlist listb,sqlist &listc) { int i,j; for(listc.n=0,i=0;i<=lista.n-1; i++) { for(j=0;j<=listb.n-1; j++) if (listb.a[j]==lista.a[i]) break; if(j<=listb.n-1) {listc.a[listc.n]=lista.a[i]; listc.n++;} } } 6.已知集合A、B，求集合C=A∩B算法，要求集合A、B和C均用采用链式存储结构表示。 void intersectionlklist(lklist *lista, lklist *listb,lklist *&listc) { lklist *p,*q,*s; for(listc=0,p=lista;p!=0; p=p->next) { for(q=listb;q!=0;q=q->next) if (p->data==q->data) break; if(q!=0) {s=(lklist *)malloc(sizeof(lklist)); s->data=p->data; s->next=listc; listc=s;} } } 7.设计在带有头结点的单向链表中删除值为X的结点算法。 分析：本题的算法思想是首先在单链表中查找值为x的结点，如果单链表为空或在单链表中找不到值为x 的结点则给出相应的提示信息，否则进行删除操作。为了便于删除操作的实现而设置指针变量p指向被删除的结点，指针变量q始终指向其前驱结点。 void deletelklist(lklist *&head, int x) { lklist *q,*p; if (head->next==0) printf(“This linklist is empty\n”); else for(q=head,p=head->next; p!=0; q=p, p=p->next) if (p->data==x) break; if (p==0) printf(“Not found %d in this linklist\n”,x); else { q->next=p->next; free(p);} } 提示：在链表中引入头结点后可以消除空表的特殊性，统一表示和处理空表和非空表的情形，从而简化插入和删除等操作的某些细节。具体涉及到本题中，如果没有引入头结点，则在找到值为x的结点后要区分该结点是第一个结点还是其它结点，而引入头结点后，则这两种情况就可以统一处理。如果本题中的单链表没有带头结点，则需要将上述黑体中的代码改为代码if (p==head) head=p->next; else q->next=p->next;。 第三章栈和队列 一、填空题 1.线性表、栈和队列从逻辑上来说都是____________结构。可以在线性表的_______位置插入和删除元素； 对于栈只能在__________插入和删除元素；对于队列只能在___________插入元素和在_________删除元素。 2.栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为__________表；队列的 插入和删除运算分别在队列的两端进行，进行插入的一端叫做__________，进行删除的一端叫做___________，先进队的元素必定先出队，所以又把队列称为____________表。 3.假设用向量S[1：m]来存储顺序栈，指针top指向当前栈顶的位置。则当栈为空时满足的条件是 ____________；当栈为满时满足的条件是_____________。 4.设有一个空栈，现有输入序列1、2、3、4、5，经过push、push、pop、push、pop、push、push、pop、pop、 pop后，输出序列为__________________。 5.在一个顺序循环队列中为了方便入队列和出队列的操作通常约定头指针front指向实际队头元素的___前一 个位置_________，尾指针rear指向当前实际队尾元素的_____所在位置_______。若该顺序循环队列有m 个存储单元，则队列满时共有__________个元素。 6.设有一个顺序循环队列如上题中的约定，则该队列满的条件是_________，队列空的条件是_________。 7.不论是顺序栈（队列）还是链式栈（队列），插入（删除）运算的时间复杂度均为________。 8.系统在函数调用前自动把调用后的____________压入堆栈；当函数调用结束后，系统又自动作退栈处理， 并将程序执行流程无条件转移到所保存的_____________处继续执行。 二、选择题 1．设栈的输入序列是1、2、3、…、n，输出序列的第一个元素是n，则第i个输出元素是（）。 ①n-i ②n-i-1 ③n-i+1 ④不确定 2．设元素进栈次序为A、B、C、D、E，则下列不可能的出栈序列是（）。 ①ABCDE ②BCDEA ③EABCD ④EDCBA 3．设用一维数组s[m]表示栈的存储空间，用top指向当前栈顶元素（其初始值为-1），则进行出栈时的操作序列是（）。 ①x=s[op]；②x=s[top]；top=0； ③x=s[top]；top=top-1；④x=s[top]；top==top+1； 4．设指针hs指向栈顶，指针s指向插入的结点A，则插入结点A时的操作为（）。 ①hs->next=s；②s->next=hs；hs=s； ③s->next=hs->next；hs->next=s；④s->next=hs；hs=hs->next； 5．设用一维数组s[m]表示栈的存储空间，用top指向当前栈顶元素（其初始值为-1），则进行入栈时的操作序列是（）。 ①s[top] =x；②top=top+1；s[top]=x； ③top==top-1；s[top]=x；④s[top]=x；top==top+1； 6．设front是链式队列的头指针，rear是链式队列的尾指针，s指向插入的结点A，则插入结点A的操作为（）。 ①front->next=s；front=s；②s->next=rear；rear=s； ③rear->next=s；rear=s；④s->next=front；front=s； 7．设front是链式队列的头指针，rear是链式队列的尾指针，则删除队头元素的操作为（）。 ①front=front->next；②rear=rear->next ； ③rear=front->next ；④front=rear->next； 8．对于一个具有m个存储单元的顺序循环队列，设front为队头指针，rear为队尾指针，则该队列中队列元素的个数计算公式为（）。 ①rear-front ②front-rear ③(rear-front)%m ④(rear-front+m)%m 9．设用一维数组q[m]作为顺序循环队列的存储空间，front指向队头元素的前一个位置，rear指向队尾元素的当前位置，则入队列的操作序列为（）。 ①q[rear] =x；rear=rear+1；②q[rear]=x；rear=rear-1； ③rear=(rear+1)%m；q[rear] =x；④rear=(rear-1)%m；q[rear]=x； 10．设用一维数组q[m]作为顺序循环队列的存储空间，front指向队头元素的前一个位置，rear指向队尾元素的当前位置，则出队列的操作序列为（）。 ①x=q[front]；front=front+1；②front=(front+1)%m；x=q[front]； ③x=q[front]；front=front-1；④front=(front-1)%m；x=q[front]； 三、算法设计题 1．设有两个顺序栈S1和S2共享一个存储区S[0：m-1]，为了尽量利用存储空间减少溢出的可能性，采用栈顶相向、迎面增长的存储方式，要求分别设计两个栈的入栈和出栈操作。 2．设计算法判断表达式中的圆括号是否配对出现。 3．设用一个单向循环链表来表示队列（也称循环队列），该队列只设一个队尾指针rear，不设队头指针front，要求设计出该队列的入队列和出队列操作。 4．假设以一个一维向量q[0：m-1]作为顺序循环队列的存储空间，同时设变量rear和len分别指示顺序循环队列中的队尾元素的位置和实际队列中的元素个数，要求设计出该队列的入队列和出队列操作。 5．将数字1、2、……、n按顺时针方向排列成环形，按顺时针方向从1开始计数，计满时则输出该位置上的数字并从环中删除该数字，然后从下一个数字开始继续计数，直到环中所有数字均被输出为止，要求设计一个算法完成此功能。 第三章参考答案 一、填空题 1． 线性，任何，栈顶，队尾，队头 2． 先进后出（FILO ），队尾，队头，先进先出（FIFO ） 3． top==0，top==m 4． 23541 5． 前一个位置，所在位置， m-1 分析：在顺序循环队列中约定头指针front 和尾指针rear 所指向的位置，是牺牲掉一个存储单元而方便表示队列空和队列满的条件，因此顺序循环队列中实际可用的存储单元只有m-1个。 6． (rear+1)%m==front ，rear==front 7． O(1) 8． 返回地址，返回地址 二、选择题 1. (3) 分析：设栈的输入序列是1、2、3、……、n ，输出序列的第一个元素是n ，则输出序列必定是n 、n-1、n-2、……、1，因此第i 个输出元素是n+1-i 。 2. (3) 3. (3) 4. (2) 5. (2) 6. (3) 7. (1) 8. (4) 分析：顺序循环队列中的元素个数=? ??<+-≥-front rear m front rear front rear front rear ，整理合并可写成(rear-front+m)%m 。 9. (3) 10. (2) 三、算法设计题 1. 设有两个顺序栈S1和S2共享一个存储区S[0：m-1]，为了尽量利用存储空间减少溢出的可能性，采用栈顶相向、迎面增长的存储方式，要求分别设计两个栈的入栈和出栈操作。 分析：本题算法思想是引入形式参数flag ，当形式参数flag 的值为1时表示对栈1进行操作，flag 的值为2时表示对栈2进行操作。 typedef struct {int s[m]; int top1; int top2;} sqstack; void push(sqstack &stack , int x,int flag) { if (stack.top1+1==stack.top2) printf(“stack is full \n”); else { if (flag==1) {stack.top1++; stack.s[stack.top1]=x;} else if(flag==2){stack.top2--; stack.s[stack.top2]=x;}else printf(“input error \n”); } } void pop(sqstack &stack , int &y, int flag) { if (flag==1) if(stack.top1<0) printf(“empty\n”); else { y=stack.s[stack.top1];stack.top1--; } else if(flag==2) if(stack.top2>=m) printf(“empty\n”); else { y=stack.s[stack.top2];stack.top2++; } else printf(“input error\n”); } 2.设计算法判断表达式中的圆括号是否配对出现。 分析：本题的算法思想是顺序扫描表达式，当扫描到左圆括号时进栈而扫描到右圆括号时出栈，如果扫描到右圆括号时不能出栈或扫描表达式结束时栈中仍有左圆括号则意味表达式中圆括号不匹配，否则表达式中圆括号匹配。 typedef struct {int s[m]; int top;} sqstack; int matchbracket() { char ch; sqstack stack; stack.top= -1; do { ch=getchar(); if (ch==‘(’) {stack.top=stack.top+1; stack.s[stack.top]=ch;} else if (ch==‘)’)if (stack.top<0) return(0); else stack.top=stack.top-1; }while(ch!= ‘#’); if (stack.top<0) return(1); else return(0); } 3.设用一个单向循环链表来表示队列（也称链式循环队列），该队列只设一个队尾指针rear，不设队头指针front，要求设计出该队列的入队列和出队列操作。 typedef struct node {int data; struct node *next;} lklist; void inlkqueue(lklist *rear, int x) { lklist *p; p=(lklist *) malloc(sizeof(lklist)); p->data=x; if (rear==0) {rear=p; rear->next=rear;}else {p->next=rear->next; rear->next=p; rear=p;} } void outlkqueue(lklist *rear, int *y) { lklist *p; if (rear==0) printf(“queue is empty\n”); else if {rear->next==rear} {y=rear->data; rear=0; } else { p=rear->next; y=p->data; rear->next=p->next; free(p);} } 4.假设以一个一维向量q[0：m-1]作为顺序循环队列的存储空间，同时设变量rear和len分别指示顺序循环队列中的队尾元素的位置和实际队列中的元素个数，要求设计出该队列的入队列和出队列操作。 分析：本题中出队列的算法思路是设置一个临时变量front指向当前队列中队头元素的实际位置，考虑到表达式queue.rear+1-queue.len的值可能为负，因此设置front的值为(queue.rear+1-queue.len+m)%m。 typedef struct{ int q[m]; int rear; int len; } sqqueue; void insqqueue(sqqueue &queue, int x) { if (queue.len==m) printf(“queue is full\n”); else {queue.rear=(queue.rear+1)%m; queue.q[queue.rear]=x;queue.len++;} } void outsqqueue(sqqueue &queue, int *y) { int front; if (queue.len==0) printf(“queue is emptyl\n”); else {front=queue.rear+1-queue.len+m}%m; y=queue.q[queue.front];queue.len--;} } 5.编写一个算法解决约瑟夫（Josephus）环问题。其问题是：设有n个人围坐在一张圆桌周围，现从第一个人开始从1报数，报到k的人出离开圆桌，接着从下一个人从1开始重新报数，……，以此类推，直到他们都离开圆桌，求出他们离开圆桌的先后顺序。 分析：本题的算法思路是设置变量sum和num，其中变量sum表示当前已经离开圆桌的人数个数，变量num表示当前的报数。 void Josephus( int n, int k) { int i,num,sum,r[100]; for(i=0;i for(sum=num=i=0; sum if (r[i]!=-1) { num++; if (num % k==0) { printf("%d\t",i); num=0;sum++; r[i]= -1; } } } 第四章 字符串和数组 一、填空题 1. 设字符串S1=“ABCDEF”，S2=“PQRS”，则运算S=CONCA T(SUB(S1，2，LEN(S2))，SUB(S1，LEN(S2)， 2)的结果为S=_________________。 2. 判断两个字符串相等的充要条件是____________________________。 3. 下列程序段实现子串t 在主串s 中位置的算法，要求在下划线处填上正确语句。 int index(char s[ ], char t[ ]) { i=j=0; while(i if(s[i]==t[j]){i=i+l; j=j+l;}else{i=_______; j=______;} if (j==strlen(t))return(i-strlen(t));else return (-1); } 4. 设二维数组A 有m 行n 列，每个数组元素占L 个字节的存储单元，按行的顺序存放在m*n 个连续的存储单元中。已知A[0][0]的地址为1000，则A[i][j]的地址为______________________________________。 5. 设三维数组A[3][4][5]中的每个元素占10个字节的存储单元，按行的顺序存放在一组连续的存储空间中。已知A[0][0][0]的首地址为1000，则数组元素A[1][2][3]的首地址为___________________________。 6. 设对称矩阵A 有n 行n 列，每个数组元素占L 个字节的存储单元，按行的顺序将下三角矩阵中的元素（包括对角线上的元素）存放在n*(n+1)/2个存储单元中，已知A[0][0]的地址为1000，则A[i][j]（i>=j ）的地址为___________________________。 7. 设有n 行n 列的三对角矩阵A ，每个数组元素占L 个字节的存储单元，按照从上到下从左到右的顺序将三条对角线上的元素存放在3n-2个连续的存储单元中，已知A[0][0]的地址为1000，则三对角线上元素A[i][j]的地址为_________________。 8. 已知稀疏矩阵A=??????????????-00005100 000302 00，则A 的三元组表为__________________。 二、算法设计题 1. 设用顺序存储结构存储字符串S1和S2，要求设计一个函数完成对两个字符串的比较。若S1>S2时则返回正数；若S1=S2时则返回0；若S1 2. 用顺序存储结构实现在字符串S 中删除所有其值等于ch 的字符的算法。 3. 设单链表中存放n 个字符，试设计算法判断字符串是否关于中心对称。 第四章参考答案 一、填空题 1. “BCDEDE ” 2. 字符串的长度相等且对应位置上的字符相等 3. i-j+1，0 分析：在查找子串位置的过程中，当发现s[i]!=t[j]时需要重新调整指针i 和j 的值后继续查找。指针j 的值肯定调整到子串的开始位置0，而指针i 的值则相应调整到i-j 的后一个位置i-j+1。 4. 1000+(i*n+j)*L 5. 1330 分析：A[1][2][3]的首地址=1000+(1*4*5+2*5+3)*10=1330。 6. 1000+(i*(i+1)/2+j)*L 分析：A[i][j]的首地址=1000+(1+2+……+i+j)*L=1000+(i*(i+1)/2+j)*L 。 7. (2*i+j)*L 分析：A[i][j]的首地址=? ??>+=+-++-=0*)*2(*))1(23*)1((0*i L j i L i j i i L j ，经合并整理可得A[i][j]的首地址=(2*i+j)*L 。 8. 4 4 4 ?????? ? ??-532122301 220 二、算法设计题 1. 设用顺序存储结构存储字符串S1和S2，要求设计一个函数完成对两个字符串的比较。若S1>S2时则返回正数；若S1=S2时则返回0；若S1 int comparestring(char s1[ ], char s2[ ]) { int i; for(i=0;s1[i]!=0;i++) if (s1[i]!=s2[i]) break; return(s1[i]-s2[i]); } 2. 用顺序存储结构实现在字符串S 中删除所有其值等于ch （假设ch=’A ’）的字符的算法。 void deletestring(char s[ ],char ch) { int i=0,j; while(s[i]!=0) if (s[i]==ch) {for(j=i+1; s[j]!=0; j++) s[j-1]=s[j]; s[j-1]=0;}else i++; } 3. 设计一个算法判断字符串S 中的字符是否关于中心对称。 typedef struct {char s[m]; int top;} sqstack; int stringsymmetry(char s[ ]) { int i; sqstack stack; stack.top= -1; for(i=0;s[i]!=0;i++) {stack.top++; stack.s[stack.top]=s[i];} for(i=0;s[i]!=0;i++) if (s[i]==stack.s[stack.top]) stack.top=stack.top-1; else return(0); return(1); } 第五章树 一、填空题 1.设一棵树的二元组形式表示为T=（D，R），其中D={A，B，C，D，E，F，G}，R={(A，B)，(A，C)，(A， D)，(B，E)，(C，F)，(C，G)}，则该树的度数为________，树的深度为________，叶子结点的个数为_________， 分支结点的个数为_________，C结点的双亲结点为__________，C结点的孩子结点为__________。 2.二叉树有_________种不同形态。 3.对于一棵具有n个结点的二叉树，当它为一棵__________二叉树时具有最小高度，其最小高度为 _______________。 4.一棵深度为k的满二叉树的结点总数为___________；一棵深度为k的完全二叉树的结点总数最少有 ___________个，最多有____________个。 5.已知一棵二叉树中度数为0的结点个数为n0，度数为1的结点数为n1，则该树中度数为2的结点数为n2， 则n0=___________。 6.一棵树中度数为1的结点数为n1，度数为2的结点数为n2，……，度数为m的结点度为n m，则该树中度 数为0的结点数为____________个。 7.已知一棵二叉树的顺序存储结构表示为ABCDE?F（其中字符?表示空结点），则其前序序列为 _____________，中序序列为___________，后序序列为_____________。 8.按照从上到下、从左到右的顺序对有n个结点的完全二叉树从1开始顺序编号，则编号为i（i!=1且2i+1<=n） 的结点其双亲结点的编号为________，其左孩子结点的编号为________，其右孩子结点的编号为________。 9.对于一棵具有n个结点的二叉树，当用二叉链表作为存储结构时，其二叉链表中的指针域的总数为______ 个，其中______个用于链接孩子结点，_______个为空指针域。 10.设某棵二叉树的前序遍历序列为ABCDEFGH，中序遍历序列为BCAEDGHF，则该二叉树的后序遍历序 列为____________________。 11.如果按中序遍历某二叉树的遍历序列为abc，问有________种不同的二叉树可以得到这一遍历序列。 12.设哈夫曼树中有n个叶子结点，则该哈夫曼树中总共有___________结点。 二、选择题 1．假设一棵二叉树中，双分支结点数为15个，单分支结点数为30个，则终端结点数为（）。 ①15 ②16 ③17 ④47 2．假设一棵三叉树的结点数为50，则它的最小高度为（）。 ①3 ②4 ③5 ④6 3．一棵二叉树上第5层的结点数最多为（）。 ①15 ②16 ③8 ④32 4．将完全二叉树中的所有结点按照从上到下、从左到右的顺序存放在n个连续的存储单元中，第一个结点存放在R[1]中。若结点R[i]有左孩子，则左孩子的结点是（）。第一个结点存放在R[0]中呢？（） ①R[2i+1] ②R[2i] ③R[i/2] ④R[2i-1] 5. 设一棵具有n个结点的满二叉树有m个叶子结点和k个分枝结点，则下列等成立的是（）。 ①n=2k+1 ②m+k=2n ③n=2m+1 ④n=2k-1 6．设森林F中有三棵树，第一、第二和第三棵树的结点树分别为m1、m2和m3，则与森林F对应的二叉树的根结点的右子树上的结点个数是（）。 ①m1②m1+m2③m3④m2+m3 7．设A、B为一棵二叉树上的两个结点，中序遍历时A在B前的条件是（）。 ①A在B的右方②A在B的左方③A是B的祖先④A是B的子孙 8．一棵具有k层的满三叉树中共有（）个结点数。 ①(3 k-1)/2 ②3 k-1 ③(3 k-1)/3 ④3 k 9．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少有（）个。 ①2h②2h-1 ③2h+1 ④h+1 10．若采用顺序存储结构存储深度为h且有n个结点的二叉树，则最多将浪费（）个存储单元。 ①0 ②2 h-1-n ③2 h+1-n ④2 h-n 11．已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，则它的前序遍历序列是（）。 ①acbed ②decab ③deabc ④cedba 12．在一棵非空二叉树的中序遍历序列中，根结点的右边（）。 ①只有右子树上的所有结点②只有右子树上的部分结点 ③只有左子树上的部分结点④只有左子树上的所有结点 三、应用题 1．设一棵树的二元组形式表示为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法表示出该树的存储结构并将该树转化为对应的二叉树。 2．根据5个叶子结点的权值集合{3、6、9、2、5}构成一棵哈夫曼树并计算这棵哈夫曼树的带权路径长度。 四、算法设计题 typedef struct node {int data; struct node *lchild; struct node *rchild;} bitree; 1.设计复制一棵二叉树的算法。 2.设计判断两个二叉树是否等价的算法。 3.设计层次遍历二叉树中所有结点的算法。 4.设计统计二叉树中叶子结点总数的算法。 5.设计交换二叉树中所有结点左右子树的算法。 6.建立一棵二叉树的链式存储结构的算法。 第五章参考答案 一、填空题 1． 3，3，4，3（分支结点即度不为0的结点），A ，F 和G 2． 5 3． 完全，??1log 2+n 4． 2k -1，2k-1，2k -1 5． n 0=1+n 2 6． n 0=1+n 2+2n 3+…+(m-1)n m 分析：设m 叉树中的结点总数为n ，则下面两个等式同时成立，经两式相减得到等式n 0=1+n 2+2n 3+…+(m-1)n m 。 n=n 0+n 1+n 2+n 3+…+n m （如果从结点数的角度考虑） n-1=n 1+2n 2+3n 3+…+mn m （如果从分支数的角度考虑） 7． ABDECF ，DBEACF ，DEBFCA 8． i/2，2i ，2i+1 9． 2n ，n-1，n+1 分析：用二叉链表作为二叉树的存储结构时，第个结点有两个指针域，则有n 个结点的二叉链表中共有2n 个指针域，其中有n-1个指针域指向非根结点，因此整个二叉链表中还有n+1个指针域。线索二叉树的线索就是利用这多余的n+1个指针域来作为线索而方便查找某个结点的前驱结点和后继结点。 10． CBEHGFDA 分析：由前序遍历序列可知，根结点最先被访问，这就可以确定A 是根结点，而又由中序遍历序列可知二叉树的根结点是其左右子树的分隔点，从而可以确定以A 为根结点的左子树上的结点为BC ，右子树上的结点为DEFGH 。以此类推，直到将这棵二叉树构造出来。实际上，只要给定某棵二叉树的前序遍历序列和中序遍历序列（或中序遍历序列和后序遍历序列）可以唯一地确定这棵二叉树。但如果给定的是某棵二叉树的前序遍历序列和后序遍历序列则不能唯一确定这棵二叉树。 11． 5 分析：三个结点的二叉树形状共有5种，如果再考虑到三个结点的排列顺序则每种情况又分为6种子情况，但中序遍历序列是abc 的只能是1种子情况。因此中序遍历序列是abc 的共有5种二叉树可以得到这一结果。 12． 2n-1 由构造哈夫曼树的过程可知，哈夫曼树中不存在度数为1的结点，只有度数为0的结点和度数为2的结点。 二、选择题 1． (2) 2． (3) 用归纳法可以证明三叉树中的第i 层上最多有3i-1个结点。本题中的三叉树的结点树为50个，因此该三叉树的最小高度为5。 3． (2) 4． (2)、（1） 5． (1) 分析：根据满二叉树的定义可知满二叉树中没有度数为1的结点，因此有等式n=m+k 和等式m=k+1成立，从而得到等式n=2k+1和等式n=2m-1成立。 6． (4) 森林转化为二叉树的规则是首先将森林中的各棵树的根结点看成是兄弟结点，然后再按照树转化为二叉树的规则进行转化。因此，本题中经转化而得到的二叉树的根结点的右子树上结点数等于第二、第三棵树上的结点数之和。 7．(2) 设结点C为结点A和B的最近的公共祖先，则根据中序遍历时A在B的之前知：如果C就是A，则B一定在A的右子树上，如果C就是B，则A一定在B的左子树上，如果C不是A也不是B，则A一定在C的左子树上而B一定在C的右子树上。 8．(1) 分析：用归纳法可以证明三叉树中的第i层上最多有3i-1个结点，因此根据等比数列求和分式可知具有k层的三叉树最多有(3k-1)/2个结点。 9．(3) 10．(2) 分析：顺序存储结构比较适合于完全二叉树，如果是一般二叉树则要将其扩充成完全二叉树以后才能够用顺序存储结构。深度为h的二叉树扩充成完全二叉树最多需要2h-1个存储单元，而实际利用的只是其中的n个存储单元，因此最多浪费2h-1-n个存储单元。 11．(4) 12．(1) 三、应用题 1．略 2．哈夫曼树略，带树路径等于55 四、算法设计题 1.设计复制一棵二叉树的算法。 void copybitree(bitree *bt1,bitree *&bt2) { if (bt1==0) {bt2=0; return;} bt2=(bitree *)malloc(sizeof(bitree)); bt2->data=bt1->data; copybitree(bt1->lchild,bt2->lchild);copybitree(bt1->rchild,bt2->rchild); } 2.设计判断两个二叉树是否等价的算法。 int judgebitree(bitree *bt1,bitree *bt2) { if (bt1==0 && bt2==0) return(1); else if (bt1==0&&bt2!=0 || bt1!=0&&bt2==0 ||bt1->data!=bt2->data) return(0); else return(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild)); } 3.设计层次遍历二叉树中所有结点的算法。 分析：本题的算法思想是设置一个顺序循环队列，队列中的单元用来存储二叉树上结点的指针。先将二叉树上的根指针入队列，在队列非空的情况下取出队头元素访问所指向的结点且将该结点中的左右指针域入队列。 void levelorder(bitree *bt) { struct {int front,rear; bitree *q[m];}queue; bitree *p=bt; queue.rear=queue.front=0; if(bt!=0) {queue.rear=(queue.rear+1)%m; queue.q[queue.rear]=p;} while (!(queue.front==queue.rear)) { queue.front=(queue.front+1)%m; p=queue.q[queue.front]; visitnode(p); if(p->lchild!=0){queue.rear=(queue.rear+1)%m; queue.q[queue.rear]=p->lchild;}; if(p->rchild!=0){queue.rear=(queue.rear+1)%m; queue.q[queue.rear]=p->rchild;}; } } 4.设计统计二叉树中叶子结点总数的算法。 void countleaf(bitree *bt,int &count) { if(bt==0) return; if(bt->lchild==0 && bt->rchild==0) count++; if(bt->lchild!=0) countleaf(bt->lchild,count); if(bt->rchild!=0) countleaf(bt->rchild,count); } 5.设计交换二叉树中所有结点左右子树的算法。 void swapbitree(bitree *bt) { bitree *p; if(bt==0) return; swapbitree(bt->lchild); swapbitree(bt->rchild); p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p; } 6.建立一棵二叉树的链式存储结构的算法。 void createbitree(threadbitree *&bt) { char ch; scanf("%c",&ch); if(ch=='#') {bt=0; return;} bt=(threadbitree*)malloc(sizeof(threadbitree)); bt->data=ch; createbitree(bt->lchild); createbitree(bt->rchild); } 提示：遍历是二叉树各种操作的基础，可在在遍历过程中对结点进行各种操作，如求已知结点的孩子结点、判定结点所在的层次、求二叉树的深度、统计二叉树中结点总数、复制二叉树等操作，也可以在遍历过程中生成结点，如建立二叉树的链式存储结构。 栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是 __________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ 2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出 8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点 数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s 数据结构模拟卷(含答案)经典习题 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( ) 数据结构考试题库 绪论 一、填空题 1.数据的逻辑结构被分为集合、(线性结构)、(树形结构)和(图状结构)四种。 2.物理结构是数据结构在计算机中的表示，又称为(存储结构)。 3.数据元素的逻辑结构包括( 线性)、(树)和图状结构3种类型，树形结构和图状结构合称为(非线性结构)。 4.(数据元素)是数据的基本单位，(数据项)是数据不可分割的最小单位。 5.线性结构中元素之间存在(一个对一个)关系，树形结构中元素之间存在(一个对多个)关系，图状结构中元素之间存在(多个对多个)关系。 ？6.数据结构是一门研究非数值计算的程序设计问题中：计算机的(数据元素)以及它们之间的(关系)和(运筹)等的学科。 7.算法的五个重要特性为有穷性、确定性、(输入)、(输出)和(可行性)。 二、选择题 1.数据的不可分割的基本单位是(D)。 A.元素 B.结点 C.数据类型 D.数据项 *2.线性表的逻辑顺序与存储顺序总是一致的，这种说法(B)。 A.正确 B.不正确 C.不确定 D.无法选择 3.线性结构是指数据元素之间存在一种(D)。 精心整理，用心做精品2 A.一对多关系 B.多对多关系 C.多对一关系 D.一对一关系 4.在数据结构中，从逻辑上可以把数据结构分成(A)。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 5.线性表若采用链式存储结构时，要求内存中可用存储单元的 地址( D)。 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续不连续都可以 三、简答题 1.算法的特性是什么。 答：有穷性确定性可行性有0或多个输入有1或多个输出线性结构 一、填空题 1.在一个长度为n的线性表中删除第i个元素（1≤i≤n）时，需向前移动(n-i)个元素。 2.从循环队列中删除一个元素时，其操作是(先移动队首指针，后取出元素)。 3.在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为(p->next)。 4.在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把(p->next)的值赋给q->next，然后(q->date)的值赋给p->next。 5.从一个栈删除元素时，首先取出(栈顶元素)，然后再使(栈顶指针)减1。 6.子串的定位操作通常称做串的(模式匹配)。 精心整理，用心做精品3 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 1 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位 10. 下列图示的顺序存储结构表示的二叉树是( ) 2 数据结构期末考试试题及答案 、选择题 评价一个算法时间性能的主要标准是()。1. A、算法易于调试 B、算法易于理解 C、算法的稳定性和正确性 D、算法的时间复杂度 )等五个特性。计算机算法具备有输入、输出、 2. A、可行性、可移植性和可扩充性 B、可行性、确定性和有穷性 C、确定性、有穷性和稳定性 D、XX、稳定性和XX 。带头结点的单链表head为空的判定条件是()3. A、h ead==NULL B、h ead->next==NULL C、head->next==head D、head！=NULL 以下关于线性表的说法不正确的是()。4. A、线性表中的数据元素可以是数字、字符、记录等不同类型。 B、线性表中包含的数据元素个数不是任意的。 C、线性表中的每个结点都有且只有一个直接前趋和直接后继。 D、存在这 样的线性表：表中各结点都没有直接前趋和直接后继。 在顺序表中，只要知道()，就可在相同时间内求出任一结点的存储地址。 5.A、基地址 B、结点大小 C、向量大小 D、基地址和结点大小 ()运算中，使用顺序表比链表好。6. A、插入 B、删除 C、根据序号查找 D、根据元素值查找一个长度为n的顺序表中，向第i个元素之前插入一个新元素时，需要向后移动()个元素7.A、n-i B、n-i+1 C、n-i-1 D、i ()适合作为经常在首尾两端操作线性表的存储结构。8. A、顺序表 B、单链表 C、循环链表 D、双向链表 栈和队列的共同点是() 9. A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 一个队列的入列序列是1234，则队列的输出序列是()。10. A 、4321 B 、12 3 4 C 、1432 D 、 3241队列与一般的线性表的区别在于()。11. A、数据元素的类型不同 B、运算是否受限制 C、数据元素的个数不同 D、逻辑结构不同 假上溢”现象会出现在()中。12. A、循环队列 B、队列 C、链队列 、顺序队列D.二、填空 2013-2014学年二学期数据结构期末考试模拟试卷(1~6卷) 一、应用题(3小题，共24分) 1已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3 次、4次和9次，对该字符串用［0,1］进行前缀编码，问该字符串的编码至少有多少位。 【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图所示。其带权路 径长度=2X 5+1X 5+3X 4+5X 3+9X 2+4X 3+4X 3+7X 2=98，所以，该字符串的编码长度至少为98位。 2.已知关键码序列为(Ja n, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec), 散列表的地址空间为0~16,设散列函数为H(x)= ［i/2」(取下整数)，其中i为关键码 中第一个字母在字母表中的序号，采用链地址法处理冲突构造散列表，并求等概率情况下查找成功的平均查找长度。 【解答】H(Ja n)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0 H(May)=13/2=6, H(Ju n)=10/25, H(Jul)=10/25, H(Aug)=1/2=0 H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2 采用链地址法处理冲突，得到的开散列表如下： 平均查找长度=(1 X 7+2X 4+3X 1)/12=18/12 3.分析下面各程序段的时间复杂度 (1)s1(int n) { int p=1,s=0; for (i=1;iv=n;i++) { p*=i;s+=p; } return(s); } ——0(n) (2)s2(int n) x=0;y=0; For (k=1;kv=n;k++) x++; For (i=1;iv=n;i++) For (j=1;jv=n;j++) y++; ——0(n) 1?下述算法的功能是什么？ ListNode *Demo l(LinkList L P ListNode *p) ("L是有头结蛊的单链表 ListNodc *q=L->rLCxt P (1) V ‘V … 」(1 )返回结点*p的直接前趋结点地址。 q=q->nest; if (q) return q, else ?ro< #*p not in L"); I ⑵ i/oid Demo2(LisINode *p ,ListNode +q) 〔//p t*q*8S 表中的 两个结点 (2)交换结点*p和结点*q (p和q的值不变)。 DataTypetemp; temp=p->data, p->data=q->data; q-x^ata^emp, 1.对给定的一组权值W=( 5, 2, 9, 11, 8, 3, 7),试构造相应的哈夫曼树，并计算它的带权路径长度。【解答】构造的哈夫曼树如图所示。 数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #include #define OVERFLOW 0 #define MAXSIZE 100 typedef int ElemType; typedef struct list {ElemType elem[MAXSIZE]; int length; }Sqlist; void Creatlist(Sqlist &L) {int i; printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。 scanf("%d",&L.length); for(i=0;i 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 第三章栈和队列 一、判断题： 1、栈和队列都是限制存取点的线性结构(易) 2、栈和队列是两种重要的线性结构。(易) 3、带头结点的单链表形式的队列，头指针F指向队列的头结点，尾指针R指向队列的最后一个结点(易) 4、在对不带头结点的链队列作出队操作时，不会改变头指针的值。(易) 答案：1-4 √√×× 二、选择题： 1、一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是C____。 A、 edcba B、 decba C、 dceab D、 abcde 2、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi 为_C___。 A、 i B、 n=i C、 n-i+1 D、不确定 3、栈结构通常采用的两种存储结构是_A___。 A、顺序存储结构和链式存储结构 B、散列方式和索引方式 C、链表存储结构和数组 D、线性存储结构和非线性存储结构 4、判定一个顺序栈ST（最多元素为m0）为空的条件是_B___。A、top !=0 B、top= =0 C、top !=m0 D、top= =m0-1 5、判定一个顺序栈ST（最多元素为m0）为栈满的条件是D。A、top！=0 B、top= =0 C、top！=m0 D、top= =m0-1 6、队列操作的原则是( A ) A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删 除 7、向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行__ _C_。(不带空的头结点) (易) A、HS—＞next=s;9 B、s—＞next= HS—＞next; HS—＞next=s; C、s—＞next= HS; HS=s; D、s—＞next= HS; HS= HS—＞next 《数据结构》课程设计题目 (程序实现采用C语言) 题目1：猴子选王（学时：3） 一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。 //链表 #include { pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 } void KickFromRing(RingNodePtr pHead, int n) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == n) { // 踢出环 printf("\n%d", pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; 数据结构考试及答案（） 作者: 日期: 2 数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为（C） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时，要求占用的存储空间地址（D） A 必须是连续的B部分地址必须是连续的 C 一定是不连续的D可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为 （D ）。 An B n/2 C （n-1）/2 D （n+1）/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（D ）o A s—link = p—link ；p—link = s； B p—link = s; s—link = q; C p—link = s—link ；s—link = p； D q—link = s; s—link = p; 5、如果想在4092个数据中只需要选择其中最小的5个，采用（C ）方法最好。 A 起泡排序 B 堆排序C锦标赛排序 D 快速 排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（B ）o A 求子串B模式匹配C 串替换 D 串连接 7、在数组A中，每一个数组元素A[i][j] 占用3个存储字，行下标i从1到8, 列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放 该数组至少需要的存储字数是（ C ）。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 A 栈B队列C循环队列D优先队列 9、一个队列的进队列顺序是1,2, 3, 4 ，则出队列顺序为（C ）。 10、在循环队列中用数组A[0.. m-1]存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。 A （ front - rear + 1） % m B （rear - front + 1） %m C （ front - rear + m） % m D （ rear - front + n） % m 11、一个数组元素a[i]与（A ）的表示等价。 A * （a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数 A指针 B 引用C值 D 变量 13、下面程序段的时间复杂度为（C) for (i nt i=0;i 2017《数据结构》期末考试试题及答案 《数据结构》期末考试试题及答案 1 ................................................................. 2..试题 1 答案............................................................ 7..《数据结构》期末考试试题及答案 2 ................................................................. 9..试题 2 答案........................................................................ 1.. 4. 《数据结构》期末考试试题及答案 3 ............................................................... 1..6试题 3 答案........................................................................ 2.. 1. 数据结构》期末考试试题及答案 1 单选题（每题 2 分，共 20 分） 1. 栈和队列的共同特点是 （ ）。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 2. 用链接方式存储的队列，在进行插入运算时 （ ）. A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D .头、尾指针可能都要修改 3. 以下数据结构中哪一个是非线性结构？ （ ） A. 队列 B. 栈 C. 线性表 D. 二叉树 4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（io ）, A[2][2]存放 若有18个元素的有序表存放在一维数组 A[19]中，第一个元素放A[1]中, 现进行二分查找，则查找 A [3]的比较序列的下标依次为（ A. 1 ， 2， 3 B. 9， 5， 2， 3 C. 9， 5， 3 D. 9， 4， 2， 3 8. 对n 个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O （1） B. O （n ） C. O （ 1 og 2n ） D. O （n2） 9. 对于线性表（ 7， 34， 55， 25， 64， 46， 20， 10）进行散列存储时，若选 用 H （K ）=K %9 作为散列函数，则散列地址为 1 的元素有（ ）个， 位置在 676（10），每个元素占一个空间， 表示用 10 进制表示。 问 A[3][3] （10）存放在什么位置？脚注 （10） 5. A ．688 B ．678 C ． 692 D ． 696 树最适合用来表示 （ ）。 A.有序数据元素 B.无序数据元素 6. C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 二叉树的第 k 层的结点数最多为 （ ）. A ．2-1 B.2K+1 C.2K-1 D. 2k-1 7. 数据结构经典例题 1.设计一个算法将L拆分成两个带头节点的单链表L1和L2。 void split(LinkList *&L,LinkList *&L1,LinkList *&L2) { LinkList *p=L->next,*q,*r1; //p指向第1个数据节点 L1=L; //L1利用原来L的头节点 r1=L1; //r1始终指向L1的尾节点 L2=(LinkList *)malloc(sizeof(LinkList));//创建L2的头节点 L2->next=NULL; //置L2的指针域为NULL while (p!=NULL) { r1->next=p; //采用尾插法将*p(data值为ai)插入L1中 r1=p; p=p->next; //p移向下一个节点(data值为bi) q=p->next; //由于头插法修改p的next域,故用q保存*p的后继节点 p->next=L2->next; //采用头插法将*p插入L2中 L2->next=p; p=q; //p重新指向ai+1的节点 } r1->next=NULL; //尾节点next置空 } 2.查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。 typedef struct LNode {int data; struct LNode *link; } *LinkList; int Searchk(LinkList list,int k) { LinkList p,q; int count=0; p=q=list->link; while (p!=NULL) { if (count 2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。 s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。 贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。 for(i=n-1；i>=0；i--) for(j=0；j 数据结构习题 习题一 一、选择题 1、算法分析的两个主要方面是：（） A．正确性和简明性B．时间复杂度和空间复杂度 C．数据复杂性和程序复杂性D．可读性和文档性 2、在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．逻辑结构和存储结构 3、计算机算法具备输入、输出和（）等5个特性： A．有穷性、确定性和稳定性B．可行性、可移植性和可扩充性 C．有穷性、确定性和可行性D．易读性、稳定性和安全性 4、算法分析的目的是（）。 A．找出算法的合理性 B．研究算法的输人与输出关系 C．分析算法的有效性以求改进 D．分析算法的易懂性 二、填空题 1、数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。 2、线性结构中元素之间存在的关系，树形结构中元素之间存在的关系， 图形结构中元素之间存在的关系。 3、________是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为________。 4、数据的________指数据元素及其关系在计算机存储器内的表示。_________是逻辑结构在计算机里的实现，也称之为映像。 5、所谓算法（Algorithm）是对特定问题求解方法和步骤的一种描述，它是指令的一组__________，其中每个指令表示一个或多个操作。 三、问答题 1、用大O形式写出下面算法的时间复杂度： i＝0； s=0； while(s＜n） ｛ i++; s+=i; ｝ 2、写出以下算法的时间复杂度： for（i＝0; i＜m; i＋＋） for（j＝0 ; j＜t; j＋＋） c[i][j]=0； for（i=0；i＜m；i＋＋） for（j=o; j 基本概念典型例题 一、单项选择题 [例6-1]数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。其中，D是( ①)的有穷集合，R是D上( ②)的有限集合。 ①A.算法B. 数据元素C. 数据操作D. 逻辑结构 ②A. 操作B. 映像C. 存储D．关系 解析：由数据结构的集合形式化定义可知，本题答案为：①B；②D。 [例6-2]数据的常用存储结构中不包括( )。 A．顺序存储结构B．线性结构C．索引存储结构D．散列存储结构 解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储 方法和散列存储方法。由此可知，本题答案为：B。 [例6-3] 算法指的是( ①)，它必须具备( ②)这三个特性。 ①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法 ②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性D．易读性、稳定性、安全性 解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。它 必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。由此可知，本 题答案为：①㈠②B。 [例6-4] 在下面的程序段中，对x的赋值语句的执行频度为( )。 for(i=0；i经典数据结构面试题(含答案)
2017年数据结构期末考试题及答案A
数据结构试题库答案
数据结构模拟卷(含答案)经典习题培训讲学
数据结构考试题库
数据结构模拟卷(含答案)经典习题
数据结构期末考试试题及答案
数据结构题库教材
经典数据结构上机题_答案解析
《数据结构》期末考试题及答案
数据结构相关题库及答案
数据结构经典题目c语言代码
数据结构考试及答案()
2017数据结构期末考试试题及答案
数据结构经典例题
2015年数据结构期末考试题及答案
数据结构期末考试试题及答案
数据结构题库汇总
数据结构典型例题
相关主题
文本预览