第三章栈、队列和数组 、名词解释 1.栈、栈顶、栈底、栈顶元素、空栈2.顺序栈3.链栈4.递归5.队列、队尾、队头6.顺序队 7.循环队8.队满9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上(下) 三角矩阵 、填空题 1.栈修改的原则是 或称 ,因此,栈又称为」 线性表。在栈顶 进行插入运算,被称为 或,在栈顶进行删除运算,被称为 或 2.栈的基本运算至少应包括 五 种 3.对于顺序栈,若栈顶下标值top=0,此时,如果作退栈运算,则产生 4.对于顺序栈而言,在栈满状态下,如果此时在作进栈运算,则会发生“ 5.一般地,栈和线性表类似有两种实现方法,即 实现和实现 6.top=0表示 此时作退栈运算,则产生“ top=sqstack maxsize-l 表示 ,此时作进栈运算,则产生“ 7.以下运算实现在顺序栈上的初始化,请在处用适当的句子予以填充 int InitStack(SqStackTp *sq) return(1): K 以下运算实现在顺序栈上的进栈,请在 处用适当的语句予以填充 Int Push(SqStackTp *sq, DataType x) if(sp->top=sqstack maxsize-1l ferror("tit"): return(O) return (1): 1 9.以下运算实现在顺序栈上的退栈,请在 用适当句子予以填充。 op(sqstackTp *sg, Data Type *x) {if(sp->top==0) error(下溢"); return(0) else(*x= 10.以下运算实现在顺序栈上判栈空,请在 处用适当句子予以填充。 Int EmptyStack(SqStackTp *sg) lif return(1) else return(O) 11.以下运算实现在顺序栈上取栈顶元素,请在 处用适当句子予以填 充。 Int GetTop(sqStackTp *sg, Data Type *x) return
1 第三章 栈、队列和数组 一、名词解释： 1.栈、栈顶、栈底、栈顶元素、空栈 2.顺序栈 3.链栈 4.递归 5.队列、队尾、队头 6.顺序队 7.循环队 8.队满 9.链队 10.随机存储结构 11.特殊矩阵 12.稀疏矩阵 13.对称方阵 14.上（下） 三角矩阵 二、填空题： 1. 栈修改的原则是_________或称________，因此，栈又称为________线性表。在栈顶 进行插入运算，被称为________或________，在栈顶进行删除运算，被称为________ 或________。 2. 栈的基本运算至少应包括________、________、________、________、________五 种。 3. 对于顺序栈，若栈顶下标值 top=0,此时，如果作退栈运算，则产生“________”。 4. 对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。 5. 一般地，栈和线性表类似有两种实现方法，即________实现和________实现。 6. top=0 表示________，此时作退栈运算，则产生“________”；top=sqstack_maxsize-1 表示________，此时作进栈运算，则产生“________”。 7. 以下运算实现在顺序栈上的初始化，请在________处用适当的句子予以填充。 int InitStack(SqStackTp *sq) { ________; return(1);} 8. 以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。 Int Push(SqStackTp *sq,DataType x) { if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);} else{________________: ________________=x; return(1);} } 9. 以下运算实现在顺序栈上的退栈，请在________________用适当句子予以填充。 Int Pop(SqStackTp *sq,DataType *x) {if(sp->top==0){error(“下溢”);return(0);} else{*x=________________; ________________; return(1);} } 10. 以下运算实现在顺序栈上判栈空，请在________________处用适当句子予以填充。 Int EmptyStack(SqStackTp *sq) {if(________________) return(1); else return(0); } 11.以下运算实现在顺序栈上取栈顶元素，请在________________处用适当句子予以填 充。 Int GetTop(SqStackTp *sq,DataType *x) {if(________________) return(0);
return(1): I 2.以下运算实现在链栈上的初始化,请在 处用请适当句子予以填充 Void InitStacl (LstackTp * Is 13.以下运算实现在链栈上的进栈,请在处用请适当句子予以填充 Void Push(LStackTp *ls, DataType x) I LstackTp *p; p=malloc(sizeof(LstackTp)) p->next=ls 14.以下运算实现在链栈上的退栈,请在 处用请适当句子予以填充 Int Pop(lstackTp * ls, Data Type *x) (LstackTp *p f(ls!=NULL Is=ls->next return (1) helse return(O) 15.以下运算实现在链栈上读栈顶元素,请在 处用请适当句子予以填 充。 Int Get Top (lstackTp * ls, Data Type *x) I if(ls!=NULL)( return(1): 1 else return(O) 16.必须注意,递归定义不能是“循环定义”。为此要求任何递归定义必须同时满足如下 条件: ①被定义项在定义中的应用(即作为定义项的出现)具有 ②被定义项在最小“尺度”上的定义不是 17.队列简称 。在队列中,新插入的结点只能添加到」 被删除的只能是排在 的结点 18.队列以线性表为逻辑结构,至少包括 五种基本运算 19.顺序队的出、入队操作会产生 0.以下运算实现在循环队上的初始化,请在 处用适当句子予以填充 Void InitCyc Queue(Cycqueue Tp *sg) sq->rear=0; 1 21.以下运算实现在循环队上的入队列,请在 处用请适当句子予以填 充 Int EnCycQueue(CycquereTp *sq, DataType x)
2 else{*x=________________; return(1);} } 12. 以下运算实现在链栈上的初始化，请在________________处用请适当句子予以填充。 Void InitStacl(LstackTp *ls){ ________________;} 13.` 以下运算实现在链栈上的进栈，请在处用请适当句子予以填充。 Void Push（LStackTp *ls,DataType x） { LstackTp *p;p=malloc(sizeof(LstackTp)); ________________; p->next=ls; ________________; } 14．以下运算实现在链栈上的退栈，请在________________处用请适当句子予以填充。 Int Pop(LstackTp *ls,DataType *x) {LstackTp *p; if(ls!=NULL) { p=ls; *x=________________; ls=ls->next; ________________; return(1)； }else return(0); } 15. 以下运算实现在链栈上读栈顶元素，请在________________处用请适当句子予以填 充。 Int Get Top(LstackTp *ls,DataType *x) { if(ls!=NULL){ ________________;return(1);} else return(0); } 16.必须注意，递归定义不能是“循环定义”。为此要求任何递归定义必须同时满足如下 条件： ①被定义项在定义中的应用（即作为定义项的出现）具有________________； ②被定义项在最小“尺度”上的定义不是________________的。 17．队列简称________________。在队列中，新插入的结点只能添加到________________， 被删除的只能是排在________________的结点。 18．队列以线性表为逻辑结构，至少包括________________、________________、 ________________、________________ ________________、五种基本运算。 19．顺序队的出、入队操作会产生“________________”。 20．以下运算实现在循环队上的初始化，请在________________处用适当句子予以填充。 Void InitCycQueue(CycqueueTp *sq) { ________________;sq->rear=0;} 21. 以下运算实现在循环队上的入队列，请在________________处用请适当句子予以填 充。 Int EnCycQueue(CycquereTp *sq,DataType x)
I if((sq->rear+1)%maxsize= eror(“队满”); return(0) return(1) 22.以下运算实现在循环队上的出队列,请在 用适当句子予以填充。 Int Out Queue(CycquereTp *sg, DataType * x) lif(sg>front== ){eror(“队空”); return(0) return(1) 23.以下运算实现在循环队上判队空,请在」 处用适当句子予以填充 Int Empt yCycQueue( Cycqueue Tp sg) lif( else return(O) 24.以下运算实现在循环队上取队头,请在」 处用适当句子予以填充。 Int Get Head(Cycqueue Tp sq, DataType *x) (if(sg. rear== return(0) return (1) 25链队在一定范围内不会出现 的情况。当lq. front=1q.rear试,队 中无元素,此时 26.以下运算实现在链队上的初始化,请在 处用适当句子予以填充。 void InitQueue(QueptrTp *lp) queue p=(LqueueTp *)malloc(sizeof(LqueueTp)) lg>rear=p (lq->front)->next= 27.以下运算实现在链队上的入队列,请在 处用适当句子予以填充。 Void EnQueue( QueptrTp *lg, Data Type x) p=(LqueueTp *)malloc (sizeof(LqueueTp (lg->rear)->next= 3
3 { if((sq->rear+1)%maxsize== ________________) {error(“队满”);return(0); else{ ________________; ________________ ________________; return(1); } 22. 以下运算实现在循环队上的出队列，请在________________处用适当句子予以填充。 Int OutCycQueue(CycquereTp *sq,DataType *x) {if(sq->front== ________________){error(“队空”);return(0)；} else{ ________________; ________________; return(1); } } 23. 以下运算实现在循环队上判队空，请在________________处用适当句子予以填充。 Int EmptyCycQueue(CycqueueTp sq) {if(________________) return(1); else return(0); } 24. 以下运算实现在循环队上取队头，请在________________处用适当句子予以填充。 Int GetHead(CycqueueTp sq,DataType *x) { if(sq.rear== ________________return(0); else{ *x=sq.data[________________ ]; return(1); } 25.链队在一定范围内不会出现________________的情况。当 lq.front==lq.rear 试，队 中无元素，此时________________。 26．以下运算实现在链队上的初始化，请在________________处用适当句子予以填充。 void InitQueue(QueptrTp *lp) { LqueueTp *p; p=(LqueueTp *)malloc(sizeof(LqueueTp))； ________________； lq->rear=p; (lq->front)->next=________________; } 27. 以下运算实现在链队上的入队列，请在________________处用适当句子予以填充。 Void EnQueue(QueptrTp *lq,DataType x) { LqueueTp *p; p=(LqueueTp *)malloc(sizeof(LqueueTp)); ________________=x; p->next=NULL; (lq->rear)->next=________________; ________________; }
28.以下运算实现在链队上的出队列,请在 处用适当句子予以填充。 int OutQueue(QuetrTp *lg, Data Type *x) LqueueTp *s if(1 g->front==1q-rear)eroe(“队空”); return(0);} else s=(lg->front)->next =s->data (lq->front)->next f(s->next==NULL) lg->rear=lg->front return(1) 9.以下运算实现在链队上判队空,请在 处用适当句子予以填充 int Empt yQueue(QueptrTp * lg) return(I else return(O) 30.以下运算实现在链队上读队头元素,请在 处用适当句子予以填充 Int GetHead(QueptrTp lg, DataType *x) queue if(lg. rear==lg front)return(0) p->data return(1) 31.一般地,一个n维数组可视为其数据元素为 维数组的线性表。数组通常只有 和 两种基本运算。 ,通常采用 存储结构来存放数组。对二维数组可有两种存储方法:一种是以 为主序的存储方式,另一种是以_ 为主序的存储方式。C语言数组用 的是以 序为主序的存储方法; FORTRAN语言用的是以 序为主序的存 储方法 33.需要压缩存储的矩阵可分为 矩阵和 矩阵两种。 34.对称方阵中有近半的元素重复,若为每一对元素只分配一个存储空间,则可将n2个元 素压缩存储到 个元素的存储空间中 5.假设以一维数组M(1:n(n+1)/2)作为n阶对称矩阵A的存储结构,以行序为主序存储 其下三角(包括对角线)中的元素,数组M和矩阵A间对应的关系为 6.上三角矩阵中,主对角线上的第t行(1<=t<=n)有 个元素,按行优先顺序存 放上三角矩阵中的元素a时,a之前的前i-1行共有 个元素,在第i行上,ai 是该行的第 个元素,M[k]和a的对应关系是。 当ij时,a=c,c存放在M 7.下三角矩阵的存储和对称矩阵类似。M[K]和a;的对应关系是 38.基于三元组的稀疏矩阵转置的处理方法有两种,以下运算按照矩阵A的列序来进行转置
4 28. 以下运算实现在链队上的出队列，请在________________处用适当句子予以填充。 int OutQueue(QuetrTp *lq,DataType *x) { LqueueTp *s; if(lq->front==lq->rear){erroe(“队空”)；return(0);} else { s=(lq->front)->next; ________________=s->data; (lq->front)->next=________________； if(s->next==NULL) lq->rear=lq->front; free(s); return(1); } } 29. 以下运算实现在链队上判队空，请在________________处用适当句子予以填充 int EmptyQueue(QueptrTp *lq) { if(________________) return(1)； else return(0); } 30. 以下运算实现在链队上读队头元素，请在________________处用适当句子予以填充。 Int GetHead(QueptrTp lq,DataType *x) { LqueueTp *p; if(lq.rear==lq.front) return(0); else{________________; ________________ =p->data; return(1); } } 31．一般地，一个 n 维数组可视为其数据元素为___________维数组的线性表。数组通常只有 ___________和___________两种基本运算。 32，通常采用___________存储结构来存放数组 。对二维数组可有两种存储方法：一种是以 ___________为主序的存储方式，另一种是以___________为主序的存储方式。C 语言数组用 的是以___________序为主序的存储方法；FORTRAN 语言用的是以___________序为主序的存 储方法 33．需要压缩存储的矩阵可分为___________矩阵和___________矩阵两种。 34．对称方阵中有近半的元素重复， 若为每一对元素只分配一个存储空间 ，则可将 n2 个元 素压缩存储到___________个元素的存储空间中。 35．假设以一维数组 M（1：n(n+1)/2）作为 n 阶对称矩阵 A 的存储结构，以行序为主序存储 其下三角（包括对角线）中的元素，数组 M 和矩阵 A 间对应的关系为___________。 36．上三角矩阵中，主对角线上的第 t 行(1j 时，aij=c,c 存放在 M[___________]中。 37．下三角矩阵的存储和对称矩阵类似。M[K]和 aij 的对应关系是___________。 38．基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵 A 的列序来进行转置
请在 处用适当的句子用以填充。 Trans Sparmat(SpMatrixTp a, SpMatrixTp *b) [(*b). mu=a. nu: (*b). nu=a. mu; (*b).tu=a tu for(p=l: pnext: free(p) 43.设有二为数组intM[10][20](注:m为0..10,n为0..20),每个元素(整数) 栈两个存储单元,数组的起始地址为2000,元素M[5][10]的存储位置为 M[8][19] 的存储值为 44.在具有n个单元的循环队列中,队满时共有」 个元素 可以作为实现递归函数调用的一种数据结构。 46.数组M中每个元素的长度是3个字节,行下标i从1到8,列下标j从1到0,从 首的址EA开始连续存放在存储其中。若按行方式存放,元素M[8][5]的起始地址为
5 请在___________处用适当的句子用以填充。 Trans_Sparmat(SpMatrixTp a,SpMatrixTp *b) { (*b).mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu; if(a.tu) { q=1; for(col=1; ___________;col++) for(p=1;pnext;free(p)。 43．设有二为数组 int M[10][20](注：m 为 0...10,n 为 0...20),每个元素（整数） 栈两个存储单元，数组的起始地址为 2000，元素 M[5][10]的存储位置为___________，M[8][19] 的存储值为___________。 44．在具有 n 个单元的循环队列中，队满时共有___________个元素。 45．___________可以作为实现递归函数调用的一种数据结构。 46．数组 M 中每个元素的长度是 3 个字节，行下标 i 从 1 到 8，列下标 j 从 1 到 0，从 首的址 EA 开始连续存放在存储其中。若按行方式存放，元素 M[8][5]的起始地址为
若按列优先方式存放,元素M[8][5]的地址为 47.对带有头结点的列队列1q,判定队列中只有一个数据元素的条件是 48.二维数组M的成员是6个字符(每个字符栈一个存储单元)组成的串,行下标 的范围从0到8,列下标j的范围从1到10,则存放M至少需要 个字节;M的第 列和第5行共占 个字节;若M按行方式存储,元素M[8][5]的起始地址与当M 按列优先方式存储时的_ 元素的起始地址一致 、单项选择题 1.在以下栈的基本运算中,不是加工型运算的是() ① InitStack(S)②Push(S,X)③Pop(S)④ empty(S) 2.以下说法正确的是() ①因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 ②因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 ③对于链栈而言,在栈满状态下,如果此时再作进栈运算,则会发生“上溢 ④对于顺序栈而言在栈满状态下如果此时再作迸栈运算,则会发生“下溢 3.在以下队列的基本运算中,不是加工型运算的是 ① InitQueue(Q)② EnQueue(Q,X)③ DOut Queu(Q,X)④ GetHead(Q,x) 4顺序队列的人队操作应为() ①sq.rear=sq.rear+1 sq data [sg. rear]=x 2sg data[sg. rear]=x sq rear=sg. rear+l 3sg. rear=(sg. rear+1)% maxsize ④4sq alsgrear」=x sq rear=(sg. rear+1)% maxsize 5.循环队列的人队操作应为() ①sq.rear=sq.rear+1 sq. data [sq. rear]=x ②sq.data[sq.rear]=x sq- rear=sq rear+1 3sg. rear=(sq. rear+1)% maxsize ④sq.data[sq.rear]=x sq. rear=(sq. rear+1)% maxsize 6.顺序队列的出队操作为() (sq. front=(sq front+1)% maxsize (2)sg front=sg. front+1 3sq. rear=(sq. rear+1)% maxsize ④sq.rear=sq.rear+1 7.循环队列的出队操作为() (sg. front=(sg. font+1)%maxsize 3sg. rear=(sq rear+)% maxsize ④sq.rear=sq.rear+1 8.循环队列的队满条件为() 1(sq. rear+1)% mazsize ==(sg front+1)% maxsize 2(sq rear+1 maxsize ==sq front+1 Osg. (rear+1)% maxsize =sq front ④sq.rear=sq. front 9.循环队列的队空条件为() ((sq. rear+1)% maxsize ==(sg. front+1)% maxsize 6
6 ___________；若按列优先方式存放，元素 M[8][5]的地址为___________。 47．对带有头结点的列队列 lq,判定队列中只有一个数据元素的条件是___________。 48．二维数组 M 的成员是 6 个字符（每个字符栈一个存储单元）组成的串，行下标 i 的范围从 0 到 8，列下标 j 的范围从 1 到 10，则存放 M 至少需要___________个字节；M 的第 8 列和第 5 行共占___________个字节；若 M 按行方式存储，元素 M[8][5]的起始地址与当 M 按列优先方式存储时的___________元素的起始地址一致。 三、单项选择题 1．在以下栈的基本运算中，不是加工型运算的是 （ ） ①lnitStack(S) ②Push(S,X) ③Pop(S) ④empty(S) 2.以下说法正确的是 ( ) ①因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 ②因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 ③对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢” ④对于顺序栈而言在栈满状态下如果此时再作迸栈运算，则会发生“下溢”。 3．在以下队列的基本运算中，不是加工型运算的是 （ ） ①InitQueue(Q) ②EnQueue(Q,X) ③OutQueu(Q,X) ④GetHead(Q,x) 4.顺序队列的人队操作应为 ( ) ①sq.rear=sq.rear+1 sq.data[sq.rear]=x ②sq.data[sq.rear]=x sq.rear=sq.rear+1 ③sq.rear=(sq.rear+1)% maxsize; sq.data[sq.rear]=x ④sq.data[sqrear]=x sq.rear=(sq.rear+1)% maxsize 5.循环队列的人队操作应为 ( ) ①sq.rear=sq.rear+1 sq.data[sq.rear]=x ②sq.data[sq.rear]=x sq.rear=sq.rear+1 ③sq.rear=(sq.rear+1)% maxsize sq.data[sq.rear]=x ④sq.data[sq.rear]=x sq.rear=(sq.rear+1)% maxsize 6. 顺序队列的出队操作为 ( ) ①sq.front=(sq.front+1)% maxsize ②sq.front=sq.front+1 ③sq.rear=(sq.rear+1)% maxsize ④sq.rear=sq.rear+1 7. 循环队列的出队操作为 ( ) ①sq.front=(sq.ftont+1)% maxsize ②sq.front=sq.front+1 ③sq.rear=(sq.rear+)% maxsize ④sq.rear=sq.rear+1 8.循环队列的队满条件为 ( ) ①(sq.rear+1) % mazsize ==(sq.front+1) % maxsize; ②(sq.rear+1 % maxsize ==sq.front+1 ③sq.(rear+1) % maxsize ==sq.front ④sq.rear ==sq.front 9.循环队列的队空条件为 ( ) ①(sq.rear+1) % maxsize ==(sq.front+1) % maxsize
(2(sg. rear+)% maxsize ==sq front+1 3(sp. rear+1)% maxsize ==sq front ④sq.rear 10.数组的数据元素类型 DataType可根据实际需要而定义。以下说法完全正确的是() ①数组的读运算可以读取一个数据元素整体,写运算只能修改一个数据元素的一部分 ②数组的读、写运算可以读取或修改一个数据元素的一部分或一个整体 ③数组的读、写运算只能读取或修改一个数据元素的一部分 ④数组的读、写运算只能读取或修改一个数据元素整体 11.对于以行序为主序的存储结构来说,在数组A[c1…d,c2…dl]中,c1和d1分别为 数组A的第一个下标的上、下界,c2…d2分别为第二各下标的上、下界,每个数据元素占K 个存储单元,二维数组中任一元素a[i,j的存储位置可由()式确定 ①Loc[i,j=[(d2-c2+1)(i-c1)+(j-c2)]*k Loc[i, j]=loc[c, C2]+[( d2-C2+1)(i-c1+(j-c2)]=k lOci, j=ALCl, C2]+[( d2-C2+1)(i-C1)+(j-C2)]*k ④Loc[i,j]=loc[0,0]+[(d2-c2+1)(i-c1)=(j-c2)]*k 12对于C语言的二维数组 DataType A[m[n],每个数据元素占K个存储单元,二维数组中任 意元素a[i,j的存储位置可由()式确定 LOc[i, j]=A[m, n]+[(n+1)*i+j]=*k @[i, j]=loc[0, 0]+[(m+n)*i+j]*k ③Loc[i,j=1oc[0,0]+[(n+1)*i+订*k OLoc[i, j]=[(n+1)=i+j]=*k 13.线性表的顺序存储结构是一种()的存储结构,线性表的链式存储结构是一种()的存 储结构 ①随机存取 ②顺序存储 14.如果以链表作为栈的存储结构,则退栈操作是 ①必须判别栈是否满②必须判别栈是否空 ③判别栈元素的类型④对栈不做任何操作 15对于基于三元组的稀疏矩阵转置的处埋方法以下说法正确的是 ①按照矩阵A的列序来进行转置,算法的时间复杂度为0(nu+tu) ②按照A的三元组a.data的次序进行转置,算法的时间复杂度为0(mu*tu) ③按照矩阵A的列序来进行转置的方法称快速转置 ④按照矩阵A的列序进行转置,对于tu<<mxmu才有意义。 16.稀疏矩阵的压缩存储方法是只存储 ①非零元素 ②三元祖(i,j,a;) 17.基于三元组的稀疏矩阵,对每个非零元素a,可以用一个 )唯一确定。 ①非零元素 ②三元组(i,j,an)③ 18如果以链表作为栈的存储结构,则退栈操作时 ①必须判别栈是否满 ②判别栈元素的类型 ③必须判别栈是否空 ④队栈不做任何判别 19.设C语言数组Data[m+1]作为循环队列SQ的存储空间, front为队头指针,rear为队 为指针,则执行出队操作的语句为 ① front= front+1 ② front=( front+1)%m ③rear=(rear+1)%m 4 front=(front+1)%(m+1) 20.三角矩阵可压缩存储到数组()中
7 ②(sq.rear+) % maxsize ==sq.front+1 ③(sp.rear+1) % maxsize ==sq.front ④sq.rear == sq.front 10.数组的数据元素类型 DataType 可根据实际需要而定义。以下说法完全正确的是 ( ) ①数组的读运算可以读取一个数据元素整体,写运算只能修改一个数据元素的一部分 ②数组的读、写运算可以读取或修改一个数据元素的一部分或一个整体 ③数组的读、写运算只能读取或修改一个数据元素的一部分 ④数组的读、写运算只能读取或修改一个数据元素整体 11．对于以行序为主序的存储结构来说，在数组 A[c1···d1，c2···d2]中，c1 和 d1 分别为 数组 A 的第一个下标的上、下界，c2…d2 分别为第二各下标的上、下界，每个数据元素占 K 个存储单元，二维数组中任一元素 a[i,j]的存储位置可由( )式确定. ①Loc[i,j]=[( d2-c2+1)(i- c1)+(j- c2)]*k ②Loc[i,j]=loc[c1, c2]+[( d2- c2+1)(i- c1)+(j- c2)]*k ③Loc{i,j}=A[c1, c2]+[( d2- c2+1)(i- c1)+(j- c2)]*k ④Loc[i,j]=loc[0,0]+[( d2- c2+1)(i- c1)=(j- c2)]*k 12 对于 C 语言的二维数组 DataType A[m][n],每个数据元素占 K 个存储单元，二维数组中任 意元素 a[i,j] 的存储位置可由( )式确定. ①Loc[i,j]=A[m,n]+[(n+1)*i+j]*k ②Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k ③Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k ④Loc[i,j]=[(n+1)*i+j]*k 13.线性表的顺序存储结构是一种( )的存储结构,线性表的链式存储结构是一种（ ）的存 储结构。 ① 随机存取 ② 顺序存储 14．如果以链表作为栈的存储结构，则退栈操作是 ( ) ①必须判别栈是否满 ②必须判别栈是否空 ③判别栈元素的类型 ④对栈不做任何操作 15 对于基于三元组的稀疏矩阵转置的处埋方法以下说法正确的是 ( ) ①按照矩阵 A 的列序来进行转置，算法的时间复杂度为 0(nu+tu) ②按照 A 的三元组 a.data 的次序进行转置，算法的时间复杂度为 O(nu*tu) ③按照矩阵 A 的列序来进行转置的方法称快速转置 ④按照矩阵 A 的列序进行转置,对于 tu<<mu x nu 才有意义。 16．稀疏矩阵的压缩存储方法是只存储 ( ) ①非零元素 ② 三元祖（i,j, aij） ③ aij ④ i,j 17．基于三元组的稀疏矩阵，对每个非零元素 aij,可以用一个（ ）唯一确定。 ①非零元素 ②三元组(i,j,aij) ③ aij ④ i,j 18 如果以链表作为栈的存储结构,则退栈操作时 ( ) ①必须判别栈是否满 ②判别栈元素的类型 ③必须判别栈是否空 ④ 队栈不做任何判别 19．设 C 语言数组 Data[m+1]作为循环队列 SQ 的存储空间， front 为队头指针，rear 为队 为指针，则执行出队操作的语句为 （ ） ①front=front+1 ② front=（front+1）%m ③rear=(rear+1)%m ④ front=(front+1)%(m+1) 20.三角矩阵可压缩存储到数组（ ）中
①M[:n(n+1)/2+1] ②M[:n(n+1)/2] ③M[n(n+1)/2+1] ④M[n(n+1)/2] 21.设有一顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素出线的顺序是s2,s3,s4,S6, S5,s1,则栈的容量至少应该是 ② ④6 22.设有一顺序栈已含3个元素,如下图所示,元素a4正等待进栈。那么下列4个序列 中不可能出现的出栈序列是 maxsize-l ↑te ④a4,a3,a2, 23.向一个栈顶指针为Top的链中插入一个s所指结点时,其操作步骤为 op->next=s @2 s->next=Top->next: Top->next=s ③s->next=Top;Top=s 4s->next=Top: Top=Top->next 24.从栈顶指针为Top的链栈中删除一个结点,并将被删节点的值保存到x中,其操作步骤为 (x=Top->data; Top=Top->next @Top=Top->next: x=Top->data 3x=Top: Top=Top->next ④x=Top->data 5.在一个链队中,若f,r分别为队首、队尾指针,则插入s所指结点的操作为() ①f->next=c;f=s ②r>next=s;r=s s->next=r:r=s ④s->next=f;f=s 26常对数组进行的两种基本操作是 ①建立与删除②索引与修改 ③查找与修改 ④查找与索引 27.链栈与顺序栈相比,有一个比较明显的优点即 ①插入操作更方便 ②通常不会出现栈满的情况 ③不会出现栈空的情况 ④删除操作更方便 8.若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成 了对该矩阵的转置运算,这种观点 ①正确 ②错误 9。二为数组M[i,j的元素是4个字符(每个字符占一个存储单元)组成的串,行下标i的 范围从0到4,列下标j的范围从0到5。M按行存储时元素M[3,5]的起始地址与M按列存 储时元素()的起始地址相同 ①M[2,4] ②M[3,4] ③M[3,5] ④M[4,4] 30.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是 ① d c b dec b ③ d cea b ④abcd 31.一个队列的人列序是1,2,3,4,则队列的输出系列是 ①4,3,2,1 ③1,4 ④3,2,4,1 32.设计一个判别表达式中左、右括号是否配对出线的算法,采用()数据结构最佳。 ①线性标的顺序存储结构 ②栈 ③队列 ④线性表的链式存储结构 33.若已知一个栈的输入序列为1,2,3,.,n,其输出序列为P1、P2、.P。若p=n,则 P1为 ① ③n-i+1 ④不确定
8 ①M[1:n(n+1)/2+1] ② M[1:n(n+1)/2] ③M[n(n+1)/2+1] ④M[n(n+1)/2] 21.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出线的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是 （ ） ①2 ② 3 ③ 5 ④6 22．设有一顺序栈已含 3 个元素，如下图所示，元素 a4 正等待进栈。那么下列 4 个序列 中不可能出现的出栈序列是 （ ） 0 1 2 3 maxsize-1 sq ↑top ①a3,a1,a4,a2 ②a3,a2,a4,a1 ③ a3,a4,a2,a1 ④a4,a3,a2,a1 23.向一个栈顶指针为 Top 的链中插入一个 s 所指结点时，其操作步骤为 （ ） ①Top->next=s ② s->next=Top->next;Top->next=s ③s->next=Top;Top=s ④ s->next=Top;Top=Top->next 24.从栈顶指针为 Top 的链栈中删除一个结点，并将被删节点的值保存到 x 中，其操作步骤为 （ ） ①x=Top->data;Top=Top->next ②Top=Top->next;x=Top->data ③x=Top;Top=Top->next ④ x=Top->data 25.在一个链队中，若 f,r 分别为队首、队尾指针，则插入 s 所指结点的操作为（ ） ①f->next=c;f=s ②r->next=s;r=s ③s->next=r;r=s ④ s->next=f;f=s 26 常对数组进行的两种基本操作是 （ ） ①建立与删除 ② 索引与修改 ③ 查找与修改 ④ 查找与索引 27．链栈与顺序栈相比，有一个比较明显的优点即 （ ） ①插入操作更方便 ② 通常不会出现栈满的情况 ③不会出现栈空的情况 ④ 删除操作更方便 28．若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成 了对该矩阵的转置运算，这种观点 （ ） ①正确 ②错误 29。二为数组 M[i,j]的元素是 4 个字符（每个字符占一个存储单元）组成的串，行下标 i 的 范围从 O 到 4，列下标 j 的范围从 O 到 5。M 按行存储时元素 M[3,5] 的起始地址与 M 按列存 储时元素( )的起始地址相同。 ①M [2,4] ② M[3,4] ③M[3,5] ④M[4,4] 30.一个栈的入栈序列是 a,b,c,d,e,则栈的不可能的输出序列是 （ ） ① e d c b a ②d e c b a ③d c e a b ④a b c d e 31.一个队列的人列序是 1，2，3，4，则队列的输出系列是 （ ） ① 4，3，2，1 ② 1，2，3，4， ③1，4，3，2 ④ 3，2，4，1 32．设计一个判别表达式中左、右括号是否配对出线的算法，采用（ ）数据结构最佳。 ①线性标的顺序存储结构 ②栈 ③ 队列 ④ 线性表的链式存储结构 33．若已知一个栈的输入序列为 1，2，3，...,n,其输出序列为 P1、P2、...Pn。若 p1=n,则 P1 为 ①i ②n=i ③ n-i+1 ④ 不确定 a1 a2 a3
34.以下说法正确的是 ①顺序队和循环队的队满和队空判断条件是一样的 ②栈可以作为实现过程调用的一种数据结构 ③插人和删除操作是数据结构中最基本的两种操作,所以这两种操作在数组中也经常使用 ④在循环队列中, front指向队列中第一个元素的前一位置,rear指向实际的队尾元素,队 列为满的条件 front=rear 35.以下说法正确的是 ①数组是同类型值的集合 ②数组是一组相继的内存单 ③数组是一种复杂的数据结构,数组元素之间的关系,既不是线性的,也不是树形的 ④使用三元组表表示稀疏矩阵的元素,有时并不能节省存储空间 四、简答及应用 1.简述顺序栈的类型定义 2.简述链栈的类型定义。 3.简述顺序队列、循环队列的类型定义。 4.简述链队的类型定义。 5,写出基于三元组的稀疏矩阵的类型说明。 6.对于循环队列,试写出求队列长度的算法 7.设有编号为t,2,3,4的四辆列车。顺序进入一个占世界共的展台,试写出这四两列车 开出车站的所有可能的顺序。 8设有上三角矩阵(a1)n*n,将其上三角元素逐行存于数组B(1:m)中(m充分大),使得B[k]=aj 且k=f1(i)+f2(j)+c。是推导出函数f,f2和常数c(要求f1和f2中不含常数项) 9.设有三对角矩阵(a;)n*n,将其三条对角线上的元素逐行存于数组B(1:3n-2)中,使得 B[k]=a1,求 (1)用i、j表示k的下标变换公式 (2)用k表示i、j的下标变换公式 10.阅读下列程序,写出程序的运行结果 i define sqstack maxsize typedef struct sqstack I char data[sqstack maxsize Int top SqStackTp I SqStackTp sq InitStack(&sq For(ch=A′;ch<=′A+12;ch+) I Push(&sq, ch) printf(%c", ch) printf(w\n" while(! EmptyStack(sg)) Pop( &sg, &ch) 9
9 34．以下说法正确的是 ①顺序队和循环队的队满和队空判断条件是一样的 ②栈可以作为实现过程调用的一种数据结构 ③插人和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用 ④在循环队列中，front 指向队列中第一个元素的前一位置，rear 指向实际的队尾元素，队 列为满的条件 front=rear 35. 以下说法正确的是 ①数组是同类型值的集合 ②数组是一组相继的内存单元 ③数组是一种复杂的数据结构，数组元素之间的关系，既不是线性的，也不是树形的 ④使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间 四、简答及应用 1．简述顺序栈的类型定义。 2．简述链栈的类型定义。 3．简述顺序队列、循环队列的类型定义。 4．简述链队的类型定义。 5，写出基于三元组的稀疏矩阵的类型说明。 6．对于循环队列，试写出求队列长度的算法。 7．设有编号为 t，2，3，4 的四辆列车。顺序进入一个占世界共的展台，试写出这四两列车 开出车站的所有可能的顺序。 8 设有上三角矩阵(aij)n*n,将其上三角元素逐行存于数组 B(1:m)中（m 充分大），使得 B[k]=aij, 且 k=f1(i)+f2(j)+c。是推导出函数 f1,f2 和常数 c(要求 f1和 f2中不含常数项)。 9．设有三对角矩阵（aij）n*n,将其三条对角线上的元素逐行存于数组 B(1:3n-2)中，使得 B[k]=aij,求： （1） 用 i、j 表示 k 的下标变换公式； （2） 用 k 表示 i、j 的下标变换公式. 10.阅读下列程序，写出程序的运行结果。 # define sqstack_maxsize 40 typedef struct sqstack { char data[sqstack_maxsize]; int top; } SqStackTp; main() { SqStackTp sq; int i; char ch; InitStack(&sq); For(ch=’A’;ch<=’A’+12;ch++) { Push(&sq,ch); printf(“%c”,ch); } printf(“\n”); while(!EmptyStack(sq)) { Pop(&sq,&ch);
11.阅读下列算法,写出其完整的功能 Void reverse list( LinkedListTP head) DataTy InitStack(&ls) While(p!=NULL I Pop(&1, &x): p->data=x } 12,对下列函数,按照《数据结构导论》课本的图3-5失利,画出调用f(5)是引起的工作栈 状态变化情况。 I if(n==) return(10) 五、算法设计 1.某汽车轮渡口,过江渡船每次能载10辆车过江。过江车辆分为客车类和货车类 上渡船的有如下规定:同类车先到先上船:且每上4辆客车,才允许上一辆货车;若等待客 车不足4辆,则以火车代替,若无货车等待允许客车都上船。试写一算法模拟渡口管理。 可以在一个数组中保存两个栈:一个栈以数组的第一个单元作为栈底,另一个栈以 数组的最后一个单元作为栈底(如下图所示)。设S是其中一个占,是分别编写过程 push(S,X)(元素X入栈),出栈pop(S)和取栈顶元素Top(S).题示:设其中一个栈为0,另 栈为 0 M-1 M+1 栈0底 栈0顶栈1顶 栈1底 3.假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头 指针),试编写相应的初始化队列、入队列和出队列算法。 4.假设以数组 cycque[m](假设数组范围在0..m)存放循环队列的元素,同时设变量rear和 quelen分别指示循环队列中队尾元素位置和内含元素的个数。试给出此循环队列的队满条 件,并写出相应的入队列和出队列的算法。 5.编写算法:按行优先存储顺序,将稀疏矩阵转换为三元组的表示形式 6.稀疏矩阵用三元组的表示形式,试写一算法实现两个稀疏矩阵相加,结果仍用三元组表示
10 printf(“&c”,ch); } printf(“\n”); } 11.阅读下列算法，写出其完整的功能。 Void reverse_list( LinkedListTP *head) { LstackTP ls,p; DataType x; InitStack(&ls); p=head->next; While(p!=NULL) { Push(&lsdata); p=p->next;} p=head->next; While(! EmptyStack(&ls)) { Pop(&l,&x); p->data=x; p=p-next;} } 12，对下列函数，按照《数据结构导论》课本的图 3-5 失利，画出调用 f(5)是引起的工作栈 状态变化情况。 Int f(int I) { if(n==1) return(10); else return(f(I-1)+2); } 五、算法设计 1.某汽车轮渡口，过江渡船每次能载 10 辆车过江。过江车辆分为客车类和货车类， 上渡船的有如下规定：同类车先到先上船；且每上 4 辆客车，才允许上一辆货车；若等待客 车不足 4 辆，则以火车代替，若无货车等待允许客车都上船。试写一算法模拟渡口管理。 可以在一个数组中保存两个栈：一个栈以数组的第一个单元作为栈底，另一个栈以 数组的最后一个单元作为栈底（如下图所示）。设 S 是其中一个占，是分别编写过程 push(S,X)(元素 X 入栈)， 出栈 pop(S)和取栈顶元素 Top(S).题示：设其中一个栈为 0，另 一栈为 1。 0 1 2 M-1 M M+1 栈 0 底 栈 0 顶 栈 1 顶 栈 1 底 3．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头 指针），试编写相应的初始化队列、入队列和出队列算法。 4．假设以数组 cycque[m](假设数组范围在 0..m)存放循环队列的元素，同时设变量 rear 和 quelen 分别指示循环队列中队尾元素位置和内含元素的个数。试给出此循环队列的队满条 件，并写出相应的入队列和出队列的算法。 5．编写算法:按行优先存储顺序，将稀疏矩阵转换为三元组的表示形式。 6．稀疏矩阵用三元组的表示形式，试写一算法实现两个稀疏矩阵相加，结果仍用三元组表示。 ······
