数据结构习题集1(2)

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.字符串\的nextval值为( ) A．(0,1,01,1,0,4,1,0,1) B．(0,1,0,0,0,0,2,1,0,1) C．(0,1,0,1,0,0,0，1,1) D．(0,1,0,1,0,1,0,1,1)

3.字符串满足下式,其中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 4.串是一种特殊的线性表,其特殊性表现在（ ） A．可以顺序存储

B．数据元素是一个字符 C．可以链式存储

D．数据元素可以是多个字符 5．设串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

5.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A[4][7]的起始地址为（ ）。

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[0][0]的地址是________。

2.二维数组A[10][20]采用列序为主方式存储,每个元素占一个存储单元,并且A[0][0]的存储地址是200,则A[6][12]的地址是________。

3.有一个10阶对称矩阵A,采用压缩存储方式(以行序为主,且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

6

{ int tag; union

{struct node *sublist; char data; }dd;

struct node *link; }NODE;

NODE *creat_GL(char **s) {

NODE *h; char ch; ch=*(*s); (*s)++; if(ch!='\\0') {

h=(NODE*)malloc(sizeof(NODE)); if(ch=='(') {

h->tag=1;

h->dd.sublist=creat_GL(s); } Else {

h->tag=0;

h->dd.data=ch; } } else

h=NULL; ch=*(*s); (*s)++; if(h!=NULL) if(ch==',')

h->link =creat_GL(s); else

h->link=NULL; return(h); }

void prn_GL(NODE *p) {

if(p!=NULL) {

if(p->tag==1) {

printf(\

7

if(p->dd.sublist ==NULL) printf(\ else

prn_GL(p->dd.sublist ); } else

printf(\ if(p->tag==1) printf(\if(p->link!=NULL) {

printf(\

prn_GL(p->link); } } }

NODE *copy_GL(NODE *p) {

NODE *q;

if(p==NULL) return(NULL);

q=(NODE *)malloc(sizeof(NODE)); q->tag=p->tag; if(p->tag)

q->dd.sublist =copy_GL(p->dd.sublist ); else

q->dd.data =p->dd.data; q->link=copy_GL(p->link); return(q); }

NODE *head(NODE *p) /*求表头函数 */ {

return(p->dd.sublist); }

NODE *tail(NODE *p) /*求表尾函数 */ {

return(p->link); }

int sum(NODE *p) /*求原子结点的数据域之和函数 */ { int m,n;

if(p==NULL) return(0); else

{ if(p->tag==0) n=p->dd.data; else

n=sum(p->dd.sublist); if(p->link!=NULL)

8

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构习题集1(2)在线全文阅读。