第一章 绪论
1．下面是几种数据的逻辑结构S=(D，R)，分别画出对应的数据逻辑结构，并指出它们分别属于何种结构。
D={a，b，c，d，e，f} R={r}
(a) r={
(b) r={ for(j=0；j for(i=0；i for(j=0；j While(i 3．在数据结构中，与所使用的计算机无关的是 。 A．存储结构 B．物理结构 C．物理和存储结构 D．逻辑结构 4．非线性结构中每个结点 。 A．无直接前驱结点 B．只有一个直接前驱和直接后继结点 C．无直接后继结点 D．可能有多个直接前驱和多个直接后继结点5．可以把数据的逻辑结构划分成 。 A．内部结构和外部结构 B．动态结构和静态结构 C．紧凑结构和非紧凑结构 D．线性结构和非线性结构 第二章 线性表 一、单项选择题 1．下面关于线性表叙述中，错误的 是_(1)_。 (1)：A．顺序表必须占用一片地址连续的存储单元 B．链表不必占用一片地址连续的存储单元 C．顺序表可以随机存取任一元素 D．链表可以随机存取任一元素 2．在表长为n的单链表中，算法时间复杂度为O(n)的操作是 (2)。 (2)：A．查找单链表中第i个结点 B．在p结点之后插入一个结点 C．删除表中第一个结点 D．删除p结点的直接后继结点 1 3．单链表的存储密度 (3) 。 (3)：A．大于1 B．等于1 C．小于1 D．不能确定 4．在表长为n的顺序表中，算法的时间复杂度为O(1)的操作是 (4) 。 (4)：A．在第n个结点之后插入一个结点 B．在第i个结点前插入一个新结点 C．删除第i个结点 D．求表长 5．在下列链表中不能从当前结点出发访问到其余各结点的是（5）。 (5)：A．单链表 B．单循环链表 C．双向链表 D．双向循环链表 6．在设头、尾指针的单链表中，与长度n有关的操作是（6）。 (6)：A．删除第一个结点 B．删除最后一个结点 C.在第一个结点之前插入一个结点 D.在表尾结点后插入一个结点 7.设p结点是带表头结点的双循环链表中的结点，则 (1)在p结点后插入s结点的语句序列中正确的是 （7）。 （7）：A.s->next=p->next；p->next->prior=s； p->next=s；s->next=p->next； B.p—>next=s；S—>next=p—>next； p—>next—>prior=s；s—>next=p； C.p->next=s；p—>next—>prior=s； s->next=p—>next；S—>next=p； D.p->next->prior=s；p->next=s； s->next=p->next；s->next=p； (2)在p结点之前插入s结点的语句序列中正确的是(8)。 (8)：A.s->prior=p->prior；p->prior->next p->prior=s；s->next=p； B.p->prior=s；p->prior->next=s; s->prior=p->prior；s->next=p; C.p->prior->next=s；p->prior=s; s->prior=p->prior；s->next=p; D.p->prior=s；s->next=p； p->prior->next=s；s->prior=p->prior; 8．下列关于链表说法错误的是 (9) 。 (9)：A.静态链表中存取每一个元素的时间相同 B．动态链表中存取每一个元素的时间不同 C．静态链表上插入或删除一个元素不必移动其他元素 D．动态链表上插入或删除一个元素不必移动其他元素 9．在链表中最常用的操作是在最后一个数据元素之后插入一个数据元素和删除第一个数据元素，则最节省运算时间的存储方式是 (10) 。 (10)：A.仅有头指针的单链表 B．仅有头指针的单循环链表 2 C．仅有头指针的双向链表 D．仅有尾指针的单循环链表 二、填空题 1．单链表中每个结点需要两个域，一个是数据域，另一个是 (1) 。 2．链表相对于顺序表的优点是 (2) 和 (3) 操作方便。 3．表长为n的顺序表中，若在第j个数据元素(1≤i≤n+1)之前插入一个数据元素，需要向后移动 (4) 个数据元素；删除第j个数据元素需要向前移动 (5) 个数据元素；在等概率的情况下，插入一个数据元素平均需要移动 (6) 个数据元素，删除一个数据元素平均需要移动 (7) 个数据元素。 4．单链表h为空表的条件是 (8) 。 5．带表头结点的单链表h为空表的条件是 (9) 。 6．在非空的单循环链表h中，某个p结点为尾结点的条件是 (10)。 7．在非空的双循环链表中，已知p结点是表中任一结点，则 (1)在p结点后插入s结点的语句序列是： s->next=p->next；s->prior=p； (11) ； (12) (2)在p结点前插入s结点的语句序列是： s->prior=p->prior；s->next=p； (13) ； (14) (3)删除p结点的直接后继结点的语句序列是： q=p->next；p->next=q->next； (15) ；free(q)； (4)删除p结点的直接前驱结点的语句序列是： q=p->prior；p->prior=q->prior； (16) ；free(q)； (5)删除p结点的语句序列是： p->prior->next=p->next； (17) ；free(q)； 8．在带有尾指针r的单循环链表中，在尾结点后插入p结点的语句序列是 (18) ； (19)；删除第一个结点的语句序列是q=r->next； (20) ；free(q)。 三、应用题 1．简述顺序表和链表各自的优点。 2．简述头指针和头结点的作用。 ． 四、算法设计题 1．请编写一个算法，实现将x插入到已按数据域值从小到大排列的有序表中。 2．设计一个算法，计算单链表中数据域值为x的结点个数。 3．设计一个用前插法建立带表头结点的单链表的算法。 4．请编写一个建立单循环链表的算法。 5．设计一个算法，实现将带头结点的单链表进行逆置。 6．编写一个算法，实现以较高的效率从有序顺序表A中删除其值在x和y之间(x≤A[i] ≤y)的所有元素。 3 第三章 栈和队列 一、选择题 1．插入和删除只能在表的一端进行的线性表，称为 (1) 。 (1)：A．队列 B．循环队列 C．栈 D．双栈 2．队列操作应遵循的原则是 （2） 。 (2)：A.先进先出 B．后进先出 C．先进后出 D．随意进出 3．栈操作应遵循的原则是 （3） 。 (3)：A．先进先出 B．后进后出 C．后进先出 D．随意进出 4．设队长为n的队列用单循环链表表示且仅设头指针，则进队操作的时间复杂度为 （4） 。 (4)：A．O(1) B．O(log2n) C．O(n) D．O(n) 5．设栈s和队列q均为空，先将a，b，c，d依次进队列q，再将队列q中顺次出队的元素进栈s，直至队空。再将栈s中的元素逐个出栈，并将出栈元素顺次进队列q，则队列q的状态是 (5) 。 (5)：A．abcd B．dcba C．bcad D．dbca 6．若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为 (6) 。 (6)：A．5和1 B．4和2 C．2和4 D．1和5 7．一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是 （7） 。 (7)：A.edcba B.decba C.dceab D.abcde 二、填空题 1．在栈结构中，允许插入、删除的一端称为 (1) ，另一端称为 (2) 。 2．在队列结构中，允许插入的一端称为 (3) ，允许删除的一端称为 (4) 。 3．设长度为n的链队列用单循环链表表示，若只设头指针，则进队和出队操作的时间复杂度分别是 (5) 和 (6) ；若只设尾指针，则进队和出队操作的时间复杂度分别为 (7) 和 (8) 。 4．设用少用一个元素空间的数组A[m]存放循环队列，front指向实际队首，rear指向新元素应存放的位置，则判断队空的条件是 (9) ，判断队满的条件是 (10) ，当队未满时，循环队列的长度是 (11) 。 5.两个栈共享一个向量空间时，可将两个栈底分别设在 (12) 。 三、应用题 ． 1．简述线性表、栈和队列有什么异同? 2．循环队列的优点是什么?设用数组A[m]来存放循环队列，如何判断队满和队空。 3．若进栈序列为abcd，请给出全部可能的出栈序列和不可能的出栈序列。 4．设栈s和队列q初始状态为空，元素a，b，c，d，e和f，依次通过栈s，一个元素出栈后即进人队列，若6个元素出队的序列是bdcfea，则栈s的容量至少应该存多少个元素? 5．已知一个中缀算术表达式为 3 + 4 / (25- (6+15))*8 写出对应的后缀算术表达式（逆 4 2 波兰表达式）。 四、算法设计题 1.已知q是一个非空顺序队列，s是一个顺序栈，请设计一个算法，实现将队列q中所有元素逆置。 2．已知递归函数： 1 当n=0时 F(n)= n·F(n/2) 当n>0时 (1)写出求F(n)递归算法； (2)写出求F(n)的非递归算法。 3．假设以带头结点的循环链表表示队列，并且仅设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。 第四章 串、数组和广义表 一、选择题 1．串的模式匹配是指 (1) 。 (1)：A.判断两个串是否相等 B．对两个串进行大小比较 C．找某字符在主串中第一次出现的位置 D．找某子串在主串中第一次出现的第一个字符位置 2．设二维数组A[m][n]，每个数组元素占用d个存储单元，第一个数组元素的存储地址是如Loc(a[0][0])，求按行优先顺序存放的数组元素a[j][j](0≤i≤m-1，0≤j≤n-1)的存储地址 (2) 。 (2)：A．Loc(a[0][0]+[(i-1)*n+j-1]*d B．Loc(a[0][0])+[i*n+j]*d C．Loc(a[0][0]+[j*m+i]*d D．Loc(a[0][0])+[(j-1)*m+i-1]*d 3．设二维数组A[m][n]，每个数组元素占d个存储单元，第1个数组元素的存储地址是Loc(a[0][0])，求按列优先顺序存放的数组元素a[j][j](0≤i≤m-1，0≤j≤n-1)的存储地址 (3) 。 (3)：A．Loc(a[0][0]+[(i-1)*n+j-1]*d B．Loc(a[0][0])+[i*n+j]*d C．Loc(a[0][0]+[(j-1)*m+i]*d D．Loc(a[0][0])+[j*m+i]*d 4．已知二维数组A[6][10]，每个数组元素占4个存储单元，若按行优先顺序存放数组元素a[3][5]的存储地址是1000，则a[0][0]的存储地址是 (4) 。 5