数据结构习题 第一章绪论 .单项选择 数据结构是一门研究非数值计算的程序设计问题中计算机的A①以及它们之间的A②和运算等的 学科 ①A)操作对象B)计算方法C)逻辑存储D)数据映象 ②A)结构 B)关系 C)运算 D)算法 2.数据结构被形式地定义为(K,R),其中K是B①_的有限集合,R是K上的_D②有限集合。 ①A)算法 B)数据元素C)数据操作D)逻辑结构 )操作 B)映象 C)存储 D)关系 3.在数据结构中,从逻辑上可以把数据结构分成C①_。 ①A)动态结构和静态结构 B)紧凑结构和非紧凑结构 C)线性结构和非线性结构 D)内部结构和外部结构 4.线性表的顺序存储结构是一种A①的存储结构,线性表的链式存储结构是一种②的存储结构 A)随机存取 B)顺序存取 C)索引存取 D)散列存取 5.算法分析的目的是C①,算法分析的两个主要方面是A②。 ①A)找出数据结构的合理性B)研究算法中的输入和输出关系 C)分析算法的效率以求改进D)分析算法的易懂性和文档性 ②A)空间复杂性和时间复杂性B)正确性和简明性 C)可读性和文档性 D)数据复杂性和程序复杂性 6.计算机算法指的是C①,它必具备输入、输出和_②B等五个特性。 ①A)计算方法 B)排序方法 C)解决问题的有限操作序列 D)调度方法 ②A)可行性、可移植性和可扩充性B)可行性、确定性和有穷性 C)确定性、有穷性和稳定性 D)易读性、稳定性和安全性 7.计算机执行下面程序段时,语句S的执行次数为①B for(i=1; i<n; i++) for(=n: j>=1 j--)S ①A)n(n+2)/2B)(n-l)n+2)2C)n(n+1)/2D)(n-1)(n+2) 8.线性表的逻辑顺序与存储顺序总是一致的,这种说法①B ①A)正确 B)不正确 9.线性表若采用链式存储结构时,要求内存中可用存储单元的地址①D ①A)必须是连续的 B)部分地址必须是连续的 C)一定是不连续的 D)连续或不连续都可以 10.每种数据结构都具备三个基本运算:插入、删除和查找,这种说法①B。 ①A)正确 B)不正确 二,填空题(将正确的答案填在相应的中) 数据逻辑结构包括_①线性结 ②树型结构和_③图形结构。三种类型,树形结构和图形结构合 称为④非线性结构。 2.在线性结构中,第一个结点①无前驱结点,其余每个结点有且只有②一个前驱结点;最后一个 结点③无后续结点,其余每个结点有且只有④个后续结点。 3.树形结构中,树根结点没有_①前驱结点,其余每个结点有且只有②二个前驱结点;叶子结点没有
数 据 结 构 习 题 第一章 绪论 一. 单项选择 1． 数据结构是一门研究非数值计算的程序设计问题中计算机的__A①___以及它们之间的__A②__和运算等的 学科。 ① A）操作对象 B） 计算方法 C） 逻辑存储 D） 数据映象 ② A）结构 B）关系 C）运算 D）算法 2． 数据结构被形式地定义为（K，R），其中 K 是__B①___的有限集合，R 是 K 上的 D② 有限集合。 ① A）算法 B）数据元素 C）数据操作 D）逻辑结构 ② A）操作 B）映象 C）存储 D）关系 3． 在数据结构中，从逻辑上可以把数据结构分成__C①___。 ① A）动态结构和静态结构 B）紧凑结构和非紧凑结构 C）线性结构和非线性结构 D）内部结构和外部结构 4． 线性表的顺序存储结构是一种_ A①_的存储结构，线性表的链式存储结构是一种_②_的存储结构。 A) 随机存取 B) 顺序存取 C) 索引存取 D) 散列存取 5． 算法分析的目的是__C①___，算法分析的两个主要方面是__A②___。 ① A) 找出数据结构的合理性 B) 研究算法中的输入和输出关系 C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性 ② A) 空间复杂性和时间复杂性 B) 正确性和简明性 C) 可读性和文档性 D) 数据复杂性和程序复杂性 6． 计算机算法指的是 C① ，它必具备输入、输出和 ②B 等五个特性。 ① A) 计算方法 B) 排序方法 C) 解决问题的有限操作序列 D) 调度方法 ② A) 可行性、可移植性和可扩充性 B）可行性、确定性和有穷性 C）确定性、有穷性和稳定性 D）易读性、稳定性和安全性 7． 计算机执行下面程序段时，语句 S 的执行次数为__①B__ for (i=1; i<n; i++) for(j=n;j>=i;j--) S; ① A) n(n+2)/2 B) (n-1)(n+2)/2 C) n(n+1)/2 D) (n-1)(n+2) 8． 线性表的逻辑顺序与存储顺序总是一致的，这种说法_① B _。 ① A） 正确 B） 不正确 9． 线性表若采用链式存储结构时，要求内存中可用存储单元的地址_①_D。 ① A) 必须是连续的 B) 部分地址必须是连续的 C) 一定是不连续的 D) 连续或不连续都可以 10． 每种数据结构都具备三个基本运算：插入、删除和查找，这种说法__①B___。 ① A) 正确 B) 不正确 二. 填空题(将正确的答案填在相应的中) 1. 数据逻辑结构包括__①线性结构___、__②树型结构___和__③图形结构___三种类型，树形结构和图形结构合 称为__④非线性结构___。 2． 在线性结构中，第一个结点__①无___前驱结点，其余每个结点有且只有__②一___个前驱结点；最后一个 结点__③无__后续结点，其余每个结点有且只有__④一___个后续结点。 3. 树形结构中，树根结点没有__①前驱__结点，其余每个结点有且只有 ②一 个前驱结点；叶子结点没有
③后继结点,其余每个结点的后续结点可以④多个 4.图形结构中,每个结点的前驱结点数和后续结点数可以①多个 5.线性结构中元素之间存在①1对1关系,树形结构中元素之间存在②一对多关系,图形结构中元 素之间存在③多对多关系 6.算法的五个重要特性是①输入_、②_输出、_③可行性_、④确定性、_⑤有穷性_。 7.下面程序段的时间复杂度是①O(n×n) for(i=0; i<n; 1++) for(=0,j<m;j++) A[U]=0, 8.下面程序段的时间复杂度是①O(n)。 while(s<n) i++;障*=i+1* 计=;/s=s+i*/ 9.下面程序段的时间复杂度是①O(n×n) for(=0,i<n;i++) for(=0; j<n; j++) s+=B][j] 10.下面程序段的时间复杂度是①O(n) while(i<=n) 3 第二章线性表 说明:顺序存储的线性表称为向量。 一.单项选择题 个向量第一个元素的地址是100,每个元素的长度为2,则第5个元素的地址是①B A)110B)108 D)120 2.线性结构通常采用的两种存储结构是①A A)顺序存储结构和链式存储结构 B)散列方式和索引方式 C)链表存储结构和数组 D)线性存储结构和非线性存储结构 3.不带头结点的单链表head为空的判定条件是①_A A) head==NULL B) head->next==NULL C) head->next==head D) head!=NULL 4.带头结点的单链表head为空的判定条件是①B A) head==NULL B)head->next==NULL C)head->next==head D) head!=NULL 5.非空的循环链表head的尾结点(由p所指向)满足①C_。 A)p->next==NULL B)p==NULL C)P->next==head D)p=head 6.在循环双链表的p所指结点之后插入s所指结点的操作是①C_
______③后继____结点，其余每个结点的后续结点可以___④多个__。 4. 图形结构中，每个结点的前驱结点数和后续结点数可以__①多个___。 5. 线性结构中元素之间存在__①1 对 1___关系，树形结构中元素之间存在__②一对多___关系，图形结构中元 素之间存在_③_多对多___关系。 6. 算法的五个重要特性是__①输入__、_②_输出___、__③可行性___、_④确定性____、__⑤有穷性___。 7. 下面程序段的时间复杂度是__①_O（n×n）__。 for (i=0; i<n; i++) for (j=0; j<m; j++) A[i][j]=0; 8. 下面程序段的时间复杂度是___①O（n）__。 i=s=0; while (s<n) { i++; /*i=i+1*/ s+=i; /*s=s+i*/ } 9. 下面程序段的时间复杂度是__①_ O（n×n）__。 s=0; for (i=0; i<n; i++) for (j=0; j<n; j++) s+=B[I][j]; sum=s; 10. 下面程序段的时间复杂度是__①O（n）___。 i=1; while (i<=n) i=i*3; 第二章 线性表 说明：顺序存储的线性表称为向量。 一. 单项选择题 1. 一个向量第一个元素的地址是 100，每个元素的长度为 2，则第 5 个元素的地址是__①_B__。 A) 110 B) 108 C) 100 D) 120 2. 线性结构通常采用的两种存储结构是__①A___。 A) 顺序存储结构和链式存储结构 B) 散列方式和索引方式 C) 链表存储结构和数组 D) 线性存储结构和非线性存储结构 3. 不带头结点的单链表 head 为空的判定条件是__①__A_. A) head==NULL B) head->next==NULL C) head->next==head D) head!=NULL 4. 带头结点的单链表 head 为空的判定条件是__①B___。 A) head==NULL B) head->next==NULL C) head->next==head D) head!=NULL 5. 非空的循环链表 head 的尾结点（由 p 所指向）满足__①_C__。 A) p->next==NULL B) p==NULL C) P->next==head D) p==head 6. 在循环双链表的 p 所指结点之后插入 s 所指结点的操作是___①_C_
A)p->right=s: s->left=p; p>right->left=s: s->right=p->right B)p>right=s: p-right->left=s: s->left=p: s->right=p->right C)s->left=p: s->right=p->right: p>right=s: p>right->1 D)s->left=p: s->right=p->right: p>right->left=s: p->right=s 7.在一个单链表中,已知q所指结点是p所指结点的前驱结点,若在q和p之间插入s结点, 则执行_①c A)s->next=p->next: p->next=s; B)p>next=s->next: s->next D)p->next=s next 8.在一个单链表中,若p所指结点不是最后结点,在p之后插入s所指结点,则执行_①b。 B)s->next=p->next: p->next=s C)s->next=p->next: p=s ))p->next=s: s->next=p 9.在一个单链表中,若删除p所指结点的后续结点,则执行①a A)p->next=p->next->next B)p=p->next: p->next=p->next->next C)p->next=p->next 10.假设双链表结点的类型如下: typedef struct linknode int dat. /*数据域*/ struct linknode* llink;/*1link是指向前驱结点的指针域*/ struct linknode* rlink;/* rlink是指向后续结点的指针域*/ 要把一个q所指新结点作为非空双向链表中的p所指结点的前驱结点插入到该双链表中, 其算法是_①c A)g>rlink=p; g->llink-p->llink; p->llink=g: p->llink->rlink=q: B)p->llink=g: q->llinkp: p->llink->rlink=g: q>llink=p->llink C)g->llink=p->llink: q->rlink=p: p->llink->rlink=g: p->llink=g D)以上都不对 12.从一个具有n个结点的单链表中查找其值等于x结点时,在查找成功的情况下,需平均比较 ①d个结点 B)n/2 C)(n-1)/2D)(n+1)/2 13.一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是①b A)0(1)B)0(n)C)0(n2) D) o(nlog2n) 14.给定有n个元素的向量,建立一个有序单链表的时间频度是①_d。 A)n C)(n-1)/2 D)(n+1)/2 二.填空题(将正确的答案填在相应的空中) 1.单链表是线性表的链接存储表示 2.向一个长度为n的向量中删除第i个元素(1≤i≤n)时,需向前移动_n-i个元素。 3.可以使用_二叉链表表示树形结构。 4.在双链表中,每个结点有两个指针域,一个指向_直接前驱,另一个指向_直接后继 5.在一个单链表中的p所指结点之前插入一个s所指结点时,可执行哪些操作 6.在一个单链表中删除p所指结点时,应执行的操作 7.带有一个头结点的单链表head为空的条件是head->next==NULL 8.在一个单链表中p所指结点之后插入一个s所指结点时,应执行 next=p→>next 的操作。 9.非空的循环链表head的尾结点(由p所指向),满足条件_p->next=head
A) p->right=s; s->left=p; p->right->left=s; s->right=p->right; B) p->right=s; p->right->left=s; s->left=p; s->right=p->right; C) s->left=p; s->right=p->right; p->right=s; p->right->left=s; D) s->left=p; s->right=p->right; p->right->left=s; p->right=s; 7. 在一个单链表中，已知 q 所指结点是 p 所指结点的前驱结点，若在 q 和 p 之间插入 s 结点， 则执行__①c___。 A) s->next=p->next; p->next=s; B) p->next=s->next; s->next=P; C) q->next=s; s->next=p; D) p->next=s; s->next=q; 8. 在一个单链表中，若 p 所指结点不是最后结点，在 p 之后插入 s 所指结点，则执行__①b___。 A) s->next=p; p->next=s; B) s->next=p->next; p->next=s; C) s->next=p->next; p=s; D) p->next=s; s->next=p; 9. 在一个单链表中，若删除 p 所指结点的后续结点，则执行__①_a__。 A) p->next=p->next->next; B) p=p->next; p->next=p->next->next; C) p->next=p->next; D) p=p->next->next; 10. 假设双链表结点的类型如下： typedef struct linknode { int data: /*数据域*/ struct linknode * llink; /*llink 是指向前驱结点的指针域*/ struct linknode * rlink; /*rlink 是指向后续结点的指针域*/ } bnode 要把一个 q 所指新结点作为非空双向链表中的 p 所指结点的前驱结点插入到该双链表中， 其算法是__①_c__。 A) q->rlink=p; q->llink=p->llink; p->llink=q; p->llink->rlink=q; B) p->llink=q; q->llink=p; p->llink->rlink=q; q->llink=p->llink; C) q->llink=p->llink; q->rlink=p; p->llink->rlink=q; p->llink=q; D) 以上都不对. 12． 从一个具有 n 个结点的单链表中查找其值等于 x 结点时，在查找成功的情况下，需平均比较 __①_d__个结点。 A) n B) n/2 C) (n-1)/2 D) (n+1)/2 13． 一个具有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是__①_b__。 A) O(1) B) O(n) C) O(n2 ) D) O(nlog2n) 14． 给定有 n 个元素的向量，建立一个有序单链表的时间频度是__①_d__。 A) n B) n/2 C) (n-1)/2 D) (n+1)/2 二.填空题(将正确的答案填在相应的空中) 1. 单链表是_线性表____的链接存储表示。 2. 向一个长度为 n 的向量中删除第 i 个元素（1≤i≤n）时，需向前移动__n-i___个元素。 3. 可以使用_二叉链表____表示树形结构。 4. 在双链表中，每个结点有两个指针域，一个指向__直接前驱___，另一个指向_直接后继____。 5. 在一个单链表中的 p 所指结点之前插入一个 s 所指结点时，可执行哪些操作_____。 6. 在一个单链表中删除 p 所指结点时，应执行的操作_____。 7. 带有一个头结点的单链表 head 为空的条件是 head->next==NULL_____。 8. 在一个单链 表中 p 所 指结点 之后插入 一个 s 所指结 点时， 应执行 s->next=_p->next______和 p->next=_s________的操作。 9. 非空的循环链表 head 的尾结点（由 p 所指向），满足条件__p->next=head___
0.对于一个具有n个结点的单链表,在已知p所指结点后插入一个新结点的时间复杂度是_o(1):在给定 值为x的结点后插入一个新结点的时间复杂度是o(n) 第三章栈和队列 1.个栈的入栈序列是ab,c,d,e,则栈的不可能的输出序列是c A)edcba B)dceba 2.若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为pl,p2,p3,…,pn,若pl=n,则pi为c。 n-计+1D)不确定 3.判定一个栈ST(最多元素为m0)为空的条件是b A) ST->topl=0 B) ST->top==0 C) ST->top!=m0 D) ST->top==m0 4.判定一个栈ST(最多元素为mO)为栈满的条件是d A)ST->top!=0 B) ST->top==0 C) ST->topl=m0 D) ST->top==m0 栈的特点是①b,队列的特点是② A)先进先出 B)先进后出 6.在以下的叙述中,正确的是①c A)线性表的线性存储结构优于链表存储结构B)栈的操作方式是先进先出 C)二维数组是其数据元素为线性表的线性表D)队列的操作方式是先进后出 7.一个队列的入队序列是1,2,3,4,则队列的输出序列是b A)4,3,2,1B)1,2,3,4C)1,4,3,2 D)3,2,4,1 10.判定一个循环队列QU(最多元素为m0)为空的条件是 A)QU->front==QU->rear B) QU->front!=QU->rear C)QU-front=(QU->rear+1)%m0 D)QU->front!=(QU->rear+1)%m0 11.判定一个循环队列QU(最多元素为m0)为满队列的条件是d A)QU->front==QU->rear B) QU->front!=QU->rear C) QU->front=(QU->rear+1)%m0 D)QU->front!=(QU->rear+1)%m0 12.循环队列用数组A[m]存放其元素值,已知其头尾指针分别是 front和rear,则当前队列中的元素个数是a_。 A)(rear-front+m)%m B)rear-front+1 C)rear-front-1 D)rear-front 13.栈和队列的共同点是c。 A)都是先进后出B)都是先进先出C)只允许在端点处插入和删除D)没有共同点 14.向一个栈顶指针为HS的链栈中插入一个s所指结点时,则执行c A) HS->next=s s->next=HS ->next: HS->next=s C)s->next=HS: HS==S D) s->next=HS: HS=HS->next 15.从一个栈顶指针为HS的链栈中删除一个结点时,用x保存被删结点的值,则执行d。 A)x=HS:HS=HS->next B)x=HS->data C)HS=HS->next: x=HS->data D)x=HS->data: HS=HS->next 16.在一个链队中,假设f和r分别为队首和队尾指针,则插入s所指结点的运算时b。 A)f->next=s:f=s B)r->next=s: r=s C)s->next=r: r=s D)s->next=f: f=s 17.在一个链队中,假设f和r分别为队首和队尾指针,则删除一个结点的运算时c A)rf->next; B)r=r->next; C)f=f->next; D) f-r->next 二.填空题(将正确的答案填在相应的空中) 1.向量、栈和队列都是_线性结构,可以在向量的_端点位置插入和删除元素;对于栈只能在栈 顶插入和删除元素;对于队列只能在队尾插入元素和队头删除元素。 2.向一个长度为n的向量的第i个元素之前插入一个元素时,需向后移动n-i+1个元素
10. 对于一个具有 n 个结点的单链表，在已知 p 所指结点后插入一个新结点的时间复杂度是__o(1)___； 在给定 值为 x 的结点后插入一个新结点的时间复杂度是_o(n)____。 第三章 栈和队列 1． 个栈的入栈序列是 a, b, c, d, e, 则栈的不可能的输出序列是__c___。 A) edcba B) dceba C) dceab D) abcde 2． 若已知一个栈的入栈序列是 1，2，3，…，n，其输出序列为 p1, p2, p3, …, pn, 若 p1=n，则 pi 为__c___。 A) i B) n-i C) n-i+1 D) 不确定 3． 判定一个栈 ST（最多元素为 m0）为空的条件是_b____。 A) ST->top!=0 B) ST->top==0 C) ST->top!=m0 D) ST->top==m0 4． 判定一个栈 ST（最多元素为 m0）为栈满的条件是_d____。 A) ST->top!=0 B) ST->top==0 C) ST->top!=m0 D) ST->top==m0 5． 栈的特点是__①b___，队列的特点是__②_a__。 A) 先进先出 B) 先进后出 6． 在以下的叙述中，正确的是__①_c__。 A) 线性表的线性存储结构优于链表存储结构 B) 栈的操作方式是先进先出 C) 二维数组是其数据元素为线性表的线性表 D) 队列的操作方式是先进后出 7． 一个队列的入队序列是 1，2，3，4，则队列的输出序列是__b___。 A) 4,3,2,1 B) 1,2,3,4 C) 1,4,3,2 D) 3,2,4,1 10. 判定一个循环队列 QU（最多元素为 m0）为空的条件是_a____。 A) QU->front==QU->rear B) QU->front!=QU->rear C) QU->front==(QU->rear+1)%m0 D) QU->front!=(QU->rear+1)%m0 11. 判定一个循环队列 QU（最多元素为 m0）为满队列的条件是_d____。 A) QU->front==QU->rear B) QU->front!=QU->rear C) QU->front==(QU->rear+1)%m0 D) QU->front!=(QU->rear+1)%m0 12. 循环队列用数组A[m]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是__a___。 A) (rear-front+m)%m B) rear-front+1 C) rear-front-1 D) rear-front 13. 栈和队列的共同点是__c___。 A) 都是先进后出 B) 都是先进先出 C) 只允许在端点处插入和删除 D) 没有共同点 14. 向一个栈顶指针为 HS 的链栈中插入一个 s 所指结点时，则执行_c____。 A) HS->next=s; B) s->next=HS->next; HS->next=s; C) s->next=HS; HS==s; D) s->next=HS; HS=HS->next; 15. 从一个栈顶指针为 HS 的链栈中删除一个结点时，用 x 保存被删结点的值，则执行__d___。 A) x=HS; HS=HS->next; B) x=HS->data; C) HS=HS->next; x=HS->data; D) x=HS->data; HS=HS->next; 16. 在一个链队中，假设 f 和 r 分别为队首和队尾指针，则插入 s 所指结点的运算时__b___。 A) f->next=s; f=s; B) r->next=s; r=s; C) s->next=r; r=s; D) s->next=f; f=s; 17. 在一个链队中，假设 f 和 r 分别为队首和队尾指针，则删除一个结点的运算时__c___。 A) r=f->next; B) r=r->next; C) f=f->next; D) f=r->next; 二. 填空题(将正确的答案填在相应的空中) 1. 向量、栈和队列都是_线性____结构，可以在向量的__端点___位置插入和删除元素；对于栈只能在 _栈 顶____插入和删除元素；对于队列只能在_队尾____插入元素和__队头___删除元素。 2. 向一个长度为 n 的向量的第 i 个元素之前插入一个元素时，需向后移动_n-i+1____个元素
3.向栈中压入元素的操作是置入数据,栈顶指针加1 4!.对栈进行退栈时的操作是栈顶指针减1,取出数据 5.在一个循环队列中,队尾指针指向队尾元素的直接后继_。 6.从循环队列中删除一个元素时,其操作是取出队头指针所指数据元素,队头指针加1 7.在具有n个单元的循环队列中,队满时共有n-1个元素 8.一个栈的输入序列是12345,则栈的输出序列43512是错误的 9.一个栈的输入序列是12345,则栈的输出序列12345是正确的 10.在栈顶指针为HS的链栈中,判定栈空的条件是HS=NULL。 11.在栈顶指针为HS的链栈中,计算该链栈中结点个数的函数是遍历函数 第四章串 单项选择题 1.空串与空格串是相同的,这种说法b A)正确 B)不正确 2.串是一种特殊的线性表,其特殊性体现在_b。 A)可以顺序存储 B)数据元素是一个字符 C)可以链接存储 D)数据元素可以是多个字符 3.设有两个串p和q,求q在p中首次出现的位置的运算称作b A)连接B)模式匹配C)求子串D)求串长 4.设串s1=’ ABCDEFG’,s2=’ PQRST’,函数con(x,y)返回x和y串的连接串,subs(s,i,j返回串s的 从序号i的字符开始的j个字符组成的子串,1en(s)返回串s的长度,则 con(subs(s1,2,len(s2),subs(sl,len(s2),2))的结果串是d A)BCDEF B)BCDEFG C) BDPQRST D)BCDEFEF 二.填空题 1.串的两种最基本的存储方式是顺序和链式。 2.两个串的长度相等的充分必要条件是有效字符相同 空串是“”其长度等于0 4.空格串是由空格组成的字符串,其长度等于空格的个数 5.设s=“ I AM A TEACHER”其长度是14 6.设s1=’GOOD’,s2= s3=’BYE!’,则s1、s2和s3连接后的结果是 GOOD BYE!。 第五章数组和广义表 单项填空题(其中A[i...j表示下标i到j 1.常对数组进行的两种基本操作是C A)建立与删除B)索引与修改C)查找和修改D)查找与索引 2.二维数组M的每个成员是6个字符(每个字符占一个存储单元)组成的串,行下标i的范围从0到 列下标j的范围从1到10,则存放M至少需要①_D_个字节:M的第8列和第5行共占②A_个 字节:若M按行优先方式存储,元素M[8][5]的起始地址与当M按列优先方式存储时的_③B_元素 的起始地址一致。 B)180 C)240 D)540 ②A)102 B)114 C)54 D) ③A)M[8][5]B)M[3][10]C)M[5][8]D)M[O][9]
3. 向栈中压入元素的操作是_置入数据，栈顶指针加 1____。 4. 对栈进行退栈时的操作是_栈顶指针减 1，取出数据____。 5. 在一个循环队列中，队尾指针指向队尾元素的_直接后继____。 6. 从循环队列中删除一个元素时，其操作是__取出队头指针所指数据元素，队头指针加 1___。 7. 在具有 n 个单元的循环队列中，队满时共有_n-1____个元素。 8. 一个栈的输入序列是 12345，则栈的输出序列 43512 是_错误的____。 9. 一个栈的输入序列是 12345，则栈的输出序列 12345 是_正确的____。 10. 在栈顶指针为 HS 的链栈中，判定栈空的条件是_HS==NULL____。 11. 在栈顶指针为 HS 的链栈中，计算该链栈中结点个数的函数是_遍历函数____。 第四章 串 一. 单项选择题 1． 空串与空格串是相同的，这种说法_b___。 A) 正确 B) 不正确 2． 串是一种特殊的线性表，其特殊性体现在__b___。 A) 可以顺序存储 B) 数据元素是一个字符 C) 可以链接存储 D) 数据元素可以是多个字符 3． 设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作__b___。 A) 连接 B) 模式匹配 C) 求子串 D) 求串长 4． 设串 s1=’ABCDEFG’,s2=’PQRST’,函数 con(x,y)返回 x 和 y 串的连接串，subs(s,i,j)返回串 s 的 从序号 i 的字符开始的 j 个字符组成的子串，len(s)返回串 s 的长度，则 con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是_d____。 A) BCDEF B) BCDEFG C) BDPQRST D) BCDEFEF 二. 填空题 1. 串的两种最基本的存储方式是_顺序和链式____。 2. 两个串的长度相等的充分必要条件是_有效字符相同____。 3. 空串是_“”____其长度等于_0____。 4. 空格串是_由空格组成的字符串____，其长度等于__空格的个数___。 5. 设 s=“I AM A TEACHER”其长度是 14_____。 6. 设 s1=’GOOD’,s2=’ ’,s3=’BYE!’,则 s1、s2 和 s3 连接后的结果是_GOOD BYE!____。 第五章 数组和广义表 一. 单项填空题(其中 A[i...j]表示下标 i 到 j) 1. 常对数组进行的两种基本操作是__C___。 A) 建立与删除 B) 索引与修改 C) 查找和修改 D) 查找与索引 2. 二维数组 M 的每个成员是 6 个字符（每个字符占一个存储单元）组成的串，行下标 i 的范围从 0 到 8， 列下标 j 的范围从 1 到 10，则存放 M 至少需要__①_D__个字节；M 的第 8 列和第 5 行共占__②_A__个 字节；若 M 按行优先方式存储，元素 M[8][5]的起始地址与当 M 按列优先方式存储时的__③B___元素 的起始地址一致。 ① A) 90 B) 180 C) 240 D) 540 ② A) 102 B) 114 C) 54 D) 60 ③ A) M[8][5] B) M[3][10] C) M[5][8] D) M[0][9]