1)填空题：序号1-80
【1，1，2】线性结构中元素之间存在一对一关系，树形结构中元素之间存在 一对多 关系，图形结构中元素之间存在 多对多 关系。
【2，1，2】为了最快地存取数据元素，物理结构宜采用 顺序存储 结构。
【3，1，2】数据结构的三要素是 逻辑结构， 物理结构 ， 操作 。
【4，1，2】数据的逻辑结构可形式地用一个二元组B＝(K，R)来表示，其中K是 数据元素的有限集合__，R是 K上关系的有限集___。
【5，1，2】存储结构可根据数据元素在机器中的位置是否一定连续分为 顺序存储结构__， 链式存储结构___。
【6，1，4】度量算法效率可通过 时间复杂度__来进行。
【7，1，4】算法的五个重要特性是确定性、 可行性 、 有穷性 、输入和输出。
【8，1，4】设n为正整数，则下面程序段的时间复杂度是 O(n)__。
i=1；k=0； while(i k=k+10*i；i++； } 【9，1，4】设n 为正整数，下面程序段中前置以记号@的语句的频度是 n(n+1)/2 。 for (i=0; i @ a[i][j]=0; } 【10，1，4】设n 为正整数，试确定下列各程序段中前置以记号@的语句的频度: (1) i=1; k=0; while (i<=n-1){ i++; @ k+=10 * i; // 语句的频度是________n-1______________。 } (2) k=0; for (i=1;i<=n;i++){ for (j=i; j<=n;j++) @ k++; // 语句的频度是____n(n+1)/2__________________。 } 【11，1，4】按增长率由大到小排列下列函数的结果是__ n2__ n log2 n n _ n1/2__ log2 n ___ log2 (log2 n),______________________。 log2 (log2 n), n log2 n, n2, n1/2, log2 n, n 【12，2，1】当线性表的规模比较大，难以估计其存储规模时，一般以采用 动态链表 的存储结构为好。 【13，2，1】线性表(a1，a2，…，an)有两种存储结构： 顺序存储结构和链式存储结构，请就这两种存储结构完成下列填充： __顺序_ 存储密度较大；__顺序__存储利用率较高；__顺序__可以随机存取；__链式___不可以随机存取； __链式__插入和删除操作比较方便。 【14，2，2】从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动 n-i 个元素。 【15，2，3】带头结点的双链表L为空的条件是 L->next=L或L->prior=L 。 【16，2，3】带头结点的单链表Head为空的条件是____ Head->next=NULL ______。 【17，2，3】非空单循环链表L中*p是尾结点的条件是_____p->next=L ___________。 【18，2，3】在一个单链表中p所指结点(p所指不是最后结点)之后插入一个由指针s所指结点，应执行s->next=__ p->next ___;和p->next=___ s_____的操作。 【19，2，3】在一个单链表中的指针p所指结点之前插入一个由指针s所指结点，可执行以下操作序列： s->next= p->next；____; p->next=s; t=p->data; p->data=___ s->data;_____; s->data=t; 【20，2，3】在一个单链表中删除p所指结点时，应执行以下操作： q= p->next; p->data= p->next->data; p->next= p->next->next _ ; free(q); 【21，2，3】在单链表中，删除指针P所指结点的后继结点的语句是 P->next = P->next->next;___。 【22，2，3】带头结点的单循环链表Head的判空条件是__ Head->next == Head;___； 不带头结点的单循环链表的判空条件是___ Head == NULL; __。 【23，2，3】删除带头结点的单循环链表Head的第一个结点的操作是__ Head->next = Head->next->next; ___；删除不带头结点的单循环链表的第一个结点的操作是__ Head = Head ->next;___。 【24，2，3】已知L是带表头结点的非空单链表, 且P结点既然不首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。 a. 删除P结点的直接前驱结点的语句序列是______10 12 8 11 4 14 __________________________。 b. 删除结点P的语句序列是_______10 12 7 3 14______________________。 c. 删除尾元结点的语句序列是 9 11 3 14_______________________。 (1) P = P->next; (2) P->next = P; (3) P->next = P->next ->next; (4) P = P->next ->next; (5) while (P != NULL) P = P->next; (6) while (Q->next != NULL){P = Q; Q = Q->next}; (7) while (P->next != Q) P = P->next; (8) while (P->next->next != Q) P = P->next; (9) while (P->next->next != NULL) P = P->next; (10) Q = P; (11) Q = P->next; (12) P = L; (13) L = L->next; (14) free (Q); 【25，3，1】栈操作的原则是 先进后出/后进先出 。 【26，3，1】对一个栈，给定输入的顺序是A、B、C，则全部不可能的输出序列有 不可能得到的输出序列有CAB 。 【27，3，1】数据A、B、C、D依次进栈后，再从栈中取一数据，则它是 D。则本栈得到DCBA的输出序列，其理由是 根据后进先出的原则，首先得到D，在栈内的数由底到顶依次是A、B、C，而出栈的次序刚好相反，即DCBA。 。 【28，3，1】.在栈顶指针为HS的链栈中，判定栈空的条件是 head->next==NULL 。 【29，3，1】将递归算法改写成等价的非递归算法，通常应该设置 堆栈 的数据结构 【30，3，2】下列程序把十进制数转换为十六进制数，请填写合适的语句成分。（每空2分） void conversion10_16() { InitStack(&s); scanf(“%d”,&N); while(N){ ① ________Push(s, N)__________ ___ ; N = N/16; } while(!StackEmpty(s)){ ② _______Pop(s, e)______________ ; if(e<=9)printf(“%d”,e); else printf(“%c”,e-10+’A’); } } /* conversion */ 【31，3，4】若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素为n，则第i个输出元素是 n－i＋1 。 【32，3，4】若用一个大小为6个元素的数组来实现循环队列，且当前rear=0和front=3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是 2 和 4 。 【33，3，4】已知一个栈的输入序列为1，2，3，…，n,输出序列为a1,a2,a3,…,an，那么a2=n的输出序列共有 n-1 种。 【34，3，4】堆栈和队列都是线性表, 堆栈是_________后进先出___________________________的线性表, 而队列是_______先进先出_____________________________的线性表。 【35，3，4】从循环队列中删除一个元素时，其操作是 先移动队首元素,后取出元素 。 【36，3，4】若用一个大小为6个元素的数组来实现循环队列，且当前rear=0和front=3。 当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是 2 和 4 。 【37，3，4】下面是关于循环队列的操作，请在划线空白处填写合适语句成分。 Status EnQueue(SqQueue &Q, QelemType e) { if((Q.rear+1)%MAXSIZE==Q.front) ) retrun ERROR; Q.base[(Q.rear)] = e; Q.rear=(Q.rear+1)%MAXSIZE ; return OK; } // EnQueue 【38，4，1】空串是 零个字符的串 ，其长度为 零 。 【39，4，1】设串s1=”teachers and “,s2=”students”,则StrLength(s2)= 8 ；Concat(s1,s2)= ”teachers and students” 。 【40，4，1】设s = ‘I AM A TEACHER’，其长度是 14 。 【41，4，1】两个串相等的充分必要条件是 两个串的长度相等且对应位置的字符相同 。 【42，4，2】串的两种最基本的存储方式是 顺序存储方式和链接存储方式 。 【43，4，3】令有串u=”aabcaab”和v=”abcaabcaabcaaba”, (1) 求Index(v,u,5)的值：Index(v,u,5)= 8 ; (2分) (2) 求出u作为模式串时在KMP算法中的next[j]值。(2分) j u next[j] 【44，5，1】二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]的存储地址是200，则A[6][10]的地址是 332。 【45，5，1】设每个元素需要8个字节，顺序存储100个元素,若首地址是2500，那么第50个元素的地址是_____2892________。 【46，5，2】已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是 LOC (A[0][0]) + (n*i + j) k 【47，5，2】C语言采用行优先方式存放数组元素，数组下标从0开始。设维数为（5,6,7）的数组A5x6x7的起始存储地址为Loc[0][0][0]=1000，每个数组元素占用4个字节。则元素A[4][4][4]所在的地址Loc[4][4][4]= ___________1800_________________________。 【48，5，2】按行优先次序列出三维数组A[2][3][2]的所有12个元素在内存中的存储次序，它们依次是： A[0][0][0] A[0][0][1] A[0][1][0] A[0][1][1] A[0][2][0] 1 a 0 2 a 1 3 b 2 4 c 1 5 a 1 6 a 2 7 b 3