发布时间 : 星期一 文章数据结构习题集1'更新完毕开始阅读116b5c72ba0d4a7303763a0c
4.语句p=p->next完成了指针负值并使p指针得到了p指针所指后继结点的数据域值。（ ） 5.要想删除p指针的后继结点，我们应该执行q=p->next ； p->next=q->next； free(q)。（ ） 三、填空题
1.已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：________。
2.顺序表中逻辑上相邻的元素物理位置( )相邻， 单链表中逻辑上相邻的元素物理位置________相邻。
3.线性表L＝（a1，a2，...，an）采用顺序存储，假定在不同的n＋1个位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是________。
4.在非空双向循环链表中，在结点q的前面插入结点p的过程如下：
p->prior=q->prior; q->prior->next=p; p->next=q; ________;
5.已知L是无表头结点的单链表，是从下列提供的答案中选择合适的语句序列，实现： 表尾插入s结点的语句序列是________。 A．p->next=s; B．p=L; C．L=s; D．p->next=s->next; E．s->next=p->next; F．s->next=L; G．s->next=null; H．while(p->next!=0) p=p->next; I．while(p->next!=null) p=p->next; 四、算法设计题
1.试编写一个求已知单链表的数据域的平均值的函数（数据域数据类型为整型）。
2.已知带有头结点的循环链表中头指针为head,试写出删除并释放数据域值为x的所有结点的c函数。
3.某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个循环链表，每个结点有价格、数量和链指针三个域。现出库（销售）m台价格为h的电视机，试编写算法修改原链表。
4.某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个循环链表，每个结点有价格、数量和链指针三个域。现新到m台价格为h的电视机，试编写算法修改原链表。
5.线性表中的元素值按递增有序排列，针对顺序表和循环链表两种不同的存储方式，分别编写C函数删除线性表中值介于a与b（a≤b）之间的元素。
6.设A=(a0,a1,a2,...,an-1),B=(b0,b1,b2,...,bm-1)是两个给定的线性表,它们的结点个数分别是n和m,且结点值均是整数。
若n=m，且 ai= bi （0≤i 若存在一个j， j 8.线性表由前后两部分性质不同的元素组成(a0,a1,...,an-1,b0,b1,...,bm-1),m和n为两部分元素的个数,若线性表分别采用数组和链表两种方式存储,编写算法将两部分元素换位成(b0,b1,...,bm-1,a0,a1,...,an-1),分析两种存储方式下算法的时间和空间复杂度。 9.用循环链表作线性表(a0,a1,...,an-1)和（b0,b1,...,bm-1）的存储结构,头指针分别为ah和bh，设计C函数，把两个线性表合并成形如（a0,b0,a1,b1,…）的线性表，要求不开辟新的动态空间,利用原来循环链表的结点完成合并操作,结构仍为循环链表,头指针为head,并分析算法的时间复杂度。 3 10.试写出将一个线性表分解为两个带有头结点的循环链表，并将两个循环链表的长度放在各自的头结点的数据域中的C函数。其中,线性表中序号为偶数的元素分解到第一个循环链表中,序号为奇数的元素分解到第二个循环链表中。 11.试写出把线性链表改为循环链表的C函数。 12.己知非空线性链表中x结点的直接前驱结点为y,试写出删除x结点的C函数。 第三章 栈和队列 一、选择题 1.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（ ）。 A．edcba B．decba C．dceab D．abcde 2.栈结构通常采用的两种存储结构是（ ）。 A．线性存储结构和链表存储结构 B．散列方式和索引方式 C．链表存储结构和数组 D．线性存储结构和非线性存储结构 3.判定一个栈ST(最多元素为m0)为空的条件是（ ）。 A．ST-〉top!=0 B．ST-〉top==0 C．ST-〉top!=m0 D．ST-〉top=m0 4.判定一个栈ST(最多元素为m0)为栈满的条件是（ ）。 A．ST->top!=0 B．ST->top==0 C．ST->top!=m0-1 D．ST->top==m0-1 5.一个队列的入列序列是1,2,3,4,则队列的输出序列是（ ）。 A．4,3,2,1 B．1,2,3,4 C．1,4,3,2 D．3,2,4,1 6.循环队列用数组A[0,m-1]存放其元素值，已知其头尾指针分别是front和rear则当前队列中的元素个数是（ ）。 A．(rear-front+m)%m B．rear-front+1 C．rear-front-1 D．rear-front 7.栈和队列的共同点是（ ） A．都是先进后出 B．都是先进先出 C．只允许在端点处插入和删除元素 D．没有共同点 8.表达式a*(b+c)-d的后缀表达式是（ ）。 A．abcd*+- B．abc+*d- C．abc*+d- D．-+*abcd 9.4个元素a1，a2，a3和a4依次通过一个栈，在a4进栈前，栈的状态，则不可能的出栈序是（ ）。 A．a4，a3，a2，a1 B．a3，a2，a4，a1 C．a3，a1，a4，a2 D．a3，a4，a2，a1 10.以数组Q[0..m－1]存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是（ ）。 A．rear－qulen B．rear－qulen＋m C．m－qulen D．1＋（rear＋m－qulen）%m 二、填空题 1.栈的特点是________，队列的特点是________。 2.线性表、栈和队列都是________结构,可以在线性表的________位置插入和删除元素，对于栈只能在________插入和删除元素，对于队列只能在________插入元素和________删除元素。 3.一个栈的输入序列是12345,则栈有输出序列12345是________。(正确/错误) 4.设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳________个元素。 三、算法设计题 4 1.假设有两个栈s1和s2共享一个数组stack[M],其中一个栈底设在stack[0]处，另一个栈底设在stack[M-1]处。试编写对任一栈作进栈和出栈运算的C函数push（x,i)和pop(i),i=l,2。其中i=1表示左边的栈，,i=2表示右边的栈。要求在整个数组元素都被占用时才产生溢出。 2．利用两个栈s1,s2模拟一个队列时,如何用栈的运算来实现该队列的运算?写出模拟队列的插入和删除的C函数。 一个栈s1用于插入元素,另一个栈s2用于删除元素。 第四章 串 一、选择题 1.下列关于串的叙述中，正确的是（ ） A．一个串的字符个数即该串的长度 B．一个串的长度至少是1 C．空串是由一个空格字符组成的串 D．两个串S1和S2若长度相同，则这两个串相等 2. 字符串满足下式,其中head和tail的定义同广义表类似,如head(?xyz?)=?x?,tail(?xyz?)= ?yz?,则s=( )。concat(head(tail(s)),head(tail(tail(s))))= ?dc?。 A．abcd B．acbd C．acdb D．adcb 3. 串是一种特殊的线性表,其特殊性表现在（ ） A．可以顺序存储 B．数据元素是字符 C．可以链式存储 D．数据元素可以是多个字符 4. 设串S1=?ABCDEFG?,s2=?PQRST?,函数CONCAT（X，Y）返回X和Y串的连接串，SUBSTR（S，I，J）返回串S从序号I开始的J个字符组成的字串，LENGTH（S）返回串S的长度，则CONCAT（SUBSTR（S1，2，LENGTH（S2）），SUBSTR（S1，LENGTH（S2），2））的结果串是（ ）。 A．BCDEF B．BCDEFG C．BCPQRST D．BCDEFEF 二、算法设计 1.分别在顺序存储和一般链接存储两种方式下,用C语言写出实现把串s1复制到串s2的串复制函数strcpy(s1,s2)。 2.在一般链接存储(一个结点存放一个字符)方式下,写出采用简单算法实现串的模式匹配的C语言函数int L_index(t,p)。 第五章 数组与广义表 一、选择题 1．常对数组进行的两种基本操作是（ ） A．建立与删除 B．索引和修改 C．查找和修改 D．查找与索引 2.二维数组M的元素是4个字符(每个字符占一个存储单元)组成的串,行下标i的范围从0到4,列下标j的范围从0到5,M按行存储时元素M[3][5]的起始地址与M按列存储时元素( )的起始地址相同。 A．M[2][4] B．M[3][4] C．M[3][5] D．M[4][4] 3.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,存放该数组至少需要的单元数是（ ）。 A．80 B．100 C．240 D．270 4.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A[7][4]的起始地址为（ ）。 A．SA+141 B．SA+144 C．SA+222 D．SA+225 5.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A[4][7]的起始地址为（ ）。 5 A．SA+141 B．SA+180 C．SA+222 D．SA+225 6.稀疏矩阵一般的压缩存储方法有两种,即（ ）。 A．二维数组和三维数组 B．三元组和散列 C．三元组和十字链表 D．散列和十字链表 7.若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算,这种观点（ ）。 A．正确 B．错误 8.设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中,对下三角部分中任一元素ai,j(i<=j),在一组数组B的下标位置k的值是（ ）。 A．i(i-1)/2+j-1 B．i(i-1)/2+j C．i(i+1)/2+j-1 D．i(i+1)/2+j 二、填空题 1.己知二维数组A[m][n]采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOC(A[0][0]),则A[i][j]的地址是________。 2.二维数组A[10][20]采用列序为主方式存储,每个元素占一个存储单元,并且A[0][0]的存储地址是200,则A[6][12]的地址是________。 3.有一个10阶对称矩阵A,采用压缩存储方式(以行序为主,且LOC(A[0][0])=1),则A[8][5]的地址是________。 4.设n行n列的下三角矩阵A已压缩到一维数组S[1..n*(n+1)/2]中,若按行序为主存储,则A[i][j]对应的S中的存储位置是________。 5.若A是按列序为主序进行存储的4×6的二维数组,其每个元素占用3个存储单元,并且A[0][0]的存储地址为1000,元素A[1][3]的存储地址为________，该数组共占用________个存储单元。 三、算法设计 1.如果矩阵A中存在这样的一个元素A[i][j]满足条件:A[i][j]是第i行中值最小的元素,且又是第j列中值最大的元素,则称之为该矩阵的一个马鞍点。编写一个函数计算出1×n的矩阵A的所有马鞍点。 算法思想：依题意,先求出每行的最小值元素,放入min[m]之中,再求出每列的最大值元素,放入max[n]之中,若某元素既在min[i]中,又在max[j]中,则该元素A[i][j]便是马鞍点,找出所有这样的元素,即找到了所有马鞍点。 2.n只猴子要选大王,选举办法如下:所有猴子按1,2,...,n编号围坐一圈,从1号开始按1、2、...、m报数,凡报m号的退出到圈外,如此循环报数,直到圈内剩下只猴子时,这只猴子就是大王。n和m由键盘输入,打印出最后剩下的猴子号。编写一程序实现上述函数。 算法思想:本题用一个含有n个元素的数组a,初始时a[i]中存放猴子的编号i,计数器似的值为0。从a[i]开始循环报数,每报一次,计数器的值加1,凡报到m时便打印出a[i]值(退出圈外的猴子的编号),同时将a[i]的值改为O(以后它不再参加报数),计数器值重新置为0。该函数一直进行到n只猴子全部退出圈外为止,最后退出的猴子就是大王。因此,现本题功能的程序如下: 3.数组和广义表的算法验证程序 编写下列程序: (1)求广义表表头和表尾的函数head()和tail()。 (2)计算广义表原子结点个数的函数count_GL()。 (3)计算广义表所有原子结点数据域(设数据域为整型〉之和的函数sum_GL()。 #include \#include \typedef struct node { int tag; union 6