数据结构习题 第一章绪论 .单项选择 数据结构是一门研究非数值计算的程序设计问题中计算机的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=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=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; inext==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; inext==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]
3.二维数组M的每个元素是4个字符(每个字符占一个存储单元)组成的串,行下标i的范围从0到4 列下标j的范围从0到5,M按行存储时元素M[3][5]的起始地址与M按列存储时元素B的起始地 址相同 A)M[2][4] )M[3][4]C)M[3][5]D)M{4}[4 4.数组A中,每个元素A的长度为3个字节,行下标i从1到8,列下标j从1到10,从首地址SA开始 连续存放在存储器内,存放数组至少需要的单元数是C A 5.数组A中,每个元素A的长度为3个字节,行下标i从1到8,列下标从1到10,从首地址SA开始连 续存放在存储器内,该数组按行存放时,元素A[8][5]的起始地址为_C A)SA+141B)SA+144C)SA+222D)SA+255 6.数组A中,每个元素A的长度为3个字节,行下标从1到8,列下标j从1到10,从首地址SA开始连 续存放在存储器内,该数组按列存放时,元素A[5][8]的起始地址为B。 A)SA+141B)SA+144C)SA+222D)SA+255 7.稀疏矩阵一般的压缩存储方法有两种,即_C A)二维数组和三维数组 B)三元组和散列 C)三元组和十字链表 D)散列和十字链表 8.若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的 转置运算,这种观点A )正确 B)错误 9.设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分(如图所示)按行序存放在一维数组 B[1..n(n-1)/2]中,对下三角部分中任一元素a,(i≥j),在一组数组B中下标k的值是B A)i(i-1)/2+j-1B)i(i-1)/2+jC)i(i+1)/2+j-1D)i(i+1)/2+j 10.广义表(a),a)的表头是C①,表尾是②C_。 B)0C)(a)D)(a)) 11.广义表(a)的表头是①B,表尾是②C A B)(a)C)0D)(( 12.广义表((a,b),C,d)的表头是①C_,表尾是②_D_。 C)(a, b) D)(c, d) 13.广义表(a,b,c,d)表头是①A_,表尾是②D。 A) B)b c)(a, b) D(b, c, d) 14.广义表((a,b,c,d)的表头是①_C_,表尾是_②B A)a B) C)(a, b, c, d) D)((a, b, c, d)) 15.一个广义表的表头总是一个广义表,这个断言是B A)正确 B)不正确 个广义表的表尾总是一个广义表,这个断言是A。 A)正确 B)不正确 二.填空题 1.已知二维数组A[m][n]采用行序为主方式存储,每个元素占k个存储单元,并且第一个的存储地址 是LOC(A[O][0]),则A[i][j的地址是。 2.二维数组A[10][20]采用列序为主方式存储,每个元素占一个存储单元,并且A[O][0]的存储地 址是200,则A[6][12]的地址是
3. 二维数组 M 的每个元素是 4 个字符（每个字符占一个存储单元）组成的串，行下标 i 的范围从 0 到 4， 列下标 j 的范围从 0 到 5，M 按行存储时元素 M[3][5]的起始地址与 M 按列存储时元素__B___的起始地 址相同。 A） M[2][4] B) M[3][4] C) M[3][5] D) M{4}[4] 4. 数组 A 中，每个元素 A 的长度为 3 个字节，行下标 i 从 1 到 8，列下标 j 从 1 到 10，从首地址 SA 开始 连续存放在存储器内，存放数组至少需要的单元数是_C____。 A) 80 B) 100 C) 240 D) 270 5. 数组 A 中，每个元素 A 的长度为 3 个字节，行下标 i 从 1 到 8，列下标从 1 到 10，从首地址 SA 开始连 续存放在存储器内，该数组按行存放时，元素 A[8][5]的起始地址为___C__。 A) SA+141 B) SA+144 C) SA+222 D) SA+255 6. 数组 A 中，每个元素 A 的长度为 3 个字节，行下标从 1 到 8，列下标 j 从 1 到 10，从首地址 SA 开始连 续存放在存储器内，该数组按列存放时，元素 A[5][8]的起始地址为_B____。 A) SA+141 B) SA+144 C) SA+222 D) SA+255 7. 稀疏矩阵一般的压缩存储方法有两种，即_C____。 A) 二维数组和三维数组 B） 三元组和散列 C） 三元组和十字链表 D） 散列和十字链表 8. 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的 转置运算，这种观点__A___ 。 A） 正确 B） 错误 9. 设矩阵 A 是一个对称矩阵，为了节省存储，将其下三角部分（如图所示）按行序存放在一维数组 B[1..n(n-1)/2]中，对下三角部分中任一元素 ai,j(i≥j)，在一组数组 B 中下标 k 的值是_B____。 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 a1,1 a2,1 a2,2 A= ... an,1 an,2 ... an,n 11． 10. 广义表（（a）,a）的表头是__C_①__，表尾是__②_C__。 12． A) a B) () C) (a) D) ((a)) 11. 广义表（（a））的表头是__①B___，表尾是__②_C__。 A) a B) (a) C) () D) ((a)) 12. 广义表((a,b),c,d)的表头是__①_C__，表尾是__②__D_。 A) a B) b C) (a,b) D) (c,d) 13. 广义表(a,b,c,d)表头是__①_A__，表尾是__②_D__。 A) a B) b C) (a,b) D) (b,c,d) 14. 广义表（（a,b,c,d））的表头是__①_C__，表尾是__②_B__。 A) a B) () C) (a,b,c,d) D) ((a,b,c,d)) 15. 一个广义表的表头总是一个广义表，这个断言是_B____。 A) 正确 B） 不正确 16. 一个广义表的表尾总是一个广义表，这个断言是__A___。 A）正确 B） 不正确 二．填空题 1． 1. 已知二维数组 A[m][n]采用行序为主方式存储，每个元素占 k 个存储单元，并且第一个的存储地址 是 LOC（A[0][0]），则 A[i][j]的地址是_____。 2． 2. 二维数组 A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且 A[0][0]的存储地 址是 200，则 A[6][12]的地址是_____
3.二维数组A[10..20][5..10]采用行序为主方式存储,每个元素占4个存储单元,并且A[10][5]的 存储地址是1000,则A[18][9]的地址是 4.有一个10阶对称矩阵A,采用压缩存储方式(以行序为主存储,且A[0][0]=1),则A[8][5]的地 址是 5.设n行n列的下三角矩阵A已压缩到一维数组S[1.n*(n+1)/2]中,若按行序为主存储,则A[i][j] 对应的S中的存储位置是 6.一个稀疏矩阵如图所示,则对应的三元组表示为 0020 3000 00 5 000 广义表((a)的表头是((a)) 表尾是0。 8.广义表(a),((b),c),((d))的表头是(a) 表尾是((b),c),((d)) 9.广义表(a),((b),c),((d))的长度是3,深度是_3 10.广义表(a,(a,b),d,e,((i,j),k))的长度是5 深度是2 11.设HAED[p为求广义表p的表头函数,TAL[p]为求广义表p的表尾函数,其中[]是函数的符号,给出下 列广义表的运算结果: HEAD[(a,b,c)]的结果是a TAIL[(a,b,c)]的结果是(b,c)。 HEAD[((a),(b))]的结果是(a) TAIL[((a),(b))]的结果是(b) HEAD[TAIL[(a,b,c)]的结果是 TAIL lHEAD((a,b),(c,d)]的结果是(b) HEAD[HEAD[((a,b),(c,d)]的结果是a TAIL[TAIL[(a,(c,d)]]的结果是O 第六章树形结构 单项选择题 1.如图所示的4棵二叉树中,c不是完全二叉树 (A) (B) (C) (D) 2.如图所示的4棵二叉树,b是平衡二叉树 (A) (B) (C)
3. 二维数组 A[10..20][5..10]采用行序为主方式存储，每个元素占 4 个存储单元，并且 A[10][5]的 存储地址是 1000，则 A[18][9]的地址是_____。 4. 有一个 10 阶对称矩阵 A，采用压缩存储方式（以行序为主存储，且 A[0][0]=1），则 A[8][5]的地 址是_____。 5. 设 n 行n 列的下三角矩阵A 已压缩到一维数组 S[1..n * (n+1)/2]中，若按行序为主存储，则 A[i][j] 对应的 S 中的存储位置是_____。 6. 一个稀疏矩阵如图所示，则对应的三元组表示为_____。 0 0 2 0 3 0 0 0 0 0 -1 5 0 0 0 0 7.广义表（（（a）））的表头是_（（a））____，表尾是_()____。 8.广义表（（a）,((b),c)，（（（d））））的表头是_（a）____，表尾是(((b),c)，（（（d）））)_____。 9.广义表（（a）,((b),c),(((d)))）的长度是__3___，深度是_3____。 10.广义表（a,(a,b),d,e,((i,j),k)）的长度是_5____，深度是_2____。 11.设 HAED[p]为求广义表 p 的表头函数，TAIL[p]为求广义表 p 的表尾函数，其中[]是函数的符号，给出下 列广义表的运算结果： HEAD[(a,b,c)]的结果是_a____。 TAIL[(a,b,c)]的结果是__(b,c)___。 HEAD[((a),(b))]的结果是_(a)____。 TAIL[（（a）,(b)）]的结果是_((b))____。 HEAD[TAIL[(a,b,c)]的结果是__b___。 TAIL[HEAD((a,b),(c,d))]的结果是_(b)____。 HEAD[HEAD[(（a,b）,(c,d))]]的结果是_a____。 TAIL[TAIL[(a,(c,d))]]的结果是_()____。 第六章 树形结构 一．单项选择题 1． 如图所示的 4 棵二叉树中，__c___不是完全二叉树。 （A） （B） （C） （D） 2．如图所示的 4 棵二叉树，__b___是平衡二叉树。 （A） （B） （C） （D）
3.在线索化二叉树中,t所指结点没有左子树的充要条件是b。 a) t->left=NULL B) t->ltag=1 C)t->1tag=1且t-left=NULD)以上都有不对 4.二叉树按某种顺序线索化后,任一结点均有指向其前驱和后继的线索,这种说法 B)错误 5.二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法a_。 A)正确 B)错误 6.由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树,这种说法b A)正确 B)错误 7.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为b。 A)2hB)2h-1C)2h+1D)h+1 8.如图所示二叉树的中序遍历序列是b。 A) abcdgef B)dfebage C) D) debag 9.已知某二叉树的后序遍历序列是 dabic,中序遍历序列是 debao, 它的前序遍历序列是 C) deabc D) cedb 7.如果T2是由有序树T转换而来的二叉树,那么T中结点的前序就是T2中结点的 A)前序B)中序C)后序D)层次序 8.如果T2是由有序树T转换而来的二叉结,那么T中结点的后序就是T2中结点的b。 A)前序 )中序C)后序D)层次序 9.某二叉树的前序遍历结点访问顺序是 abdgcefh,中序遍历的结点访问顺序是 dgbaechf,则其后序遍 历的结点访问顺序是 A) bdgcefha B)gdbecfha C)bdgaechf D) gdbehfca 10.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值 这种说法 A)正确 B)不正确 11.按照二叉树的定义,具有3个结点的二叉树有_c种。 A)3 )4C)5D)6 12.一棵二叉树如图所示,其中遍历的序列为b A) abdgcefh B)dgbaechf C)gdbehfca D)abcdefgh
3． 在线索化二叉树中，t 所指结点没有左子树的充要条件是_b____。 A） t->left=NULL B) t->ltag=1 C) t->ltag=1 且 t->left=NULL D) 以上都有不对 4． 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索，这种说法_b____。 A） 正确 B） 错误 5． 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法__a___。 A） 正确 B） 错误 6． 由于二叉树中每个结点的度最大为 2，所以二叉树是一种特殊的树，这种说法_b____。 A） 正确 B） 错误 7． 设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为_b____。 A） 2h B) 2h-1 C) 2h+1 D) h+1 8． 如图所示二叉树的中序遍历序列是__b___。 A) abcdgef B) dfebage C) dbaefcg D) defbagc 9.已知某二叉树的后序遍历序列是 dabec，中序遍历序列是 debac， 它的前序遍历序列是__d____。 A) acbed B) decab C) deabc D) cedba 7. 如果 T2 是由有序树 T 转换而来的二叉树，那么 T 中结点的前序就是 T2 中结点的_a____。 A) 前序 B） 中序 C） 后序 D） 层次序 8. 如果 T2 是由有序树 T 转换而来的二叉结，那么 T 中结点的后序就是 T2 中结点的_b____。 A) 前序 B） 中序 C） 后序 D） 层次序 9. 某二叉树的前序遍历结点访问顺序是 abdgcefh，中序遍历的结点访问顺序是 dgbaechf，则其后序遍 历的结点访问顺序是_d____。 A） bdgcefha B) gdbecfha C) bdgaechf D) gdbehfca 10. 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。 这种说法__b___。 A) 正确 B） 不正确 11. 按照二叉树的定义，具有 3 个结点的二叉树有_c____种。 A） 3 B） 4 C） 5 D） 6 12. 一棵二叉树如图所示，其中遍历的序列为_b____。 A） abdgcefh B) dgbaechf C) gdbehfca D) abcdefgh a b c g d f e a b c d e f g h
13.树的基本遍历策略可分为先根遍历和后根遍历;二叉树的基本遍历策略可分为先序遍历、中序 遍历和后序遍历。这里,我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论a 是正确的 A)树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B)树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C)树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D)以上说法都不对 14.深度为5的二叉树至多有 个结点。 A)16B)32C)31D)10 5.在一非空二叉树的中序遍历序列中,根结点的右边 A)只有右子树上的所有结点 B)只有右子树上的部分结点 C)只有左子树上的部分结点 D)只有左子树上的所有对点 16.树最适合用来表示 A)有序的数据元素 B)无序的数据元素 C)元素之间具有分支层次关系的数据D)元素之间无联系的数据 17.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序a A)不发生改变B)发生改变C)不能确定 D)以上都有不对 18.实现任意二叉树的后序遍历的非递归算法而不使用栈结构,最佳方案是二叉树采用d存储结 构 A)二叉链表B)广义表存储结构C)三叉链表 D)顺序存储结构 19.对一个满二叉树,m个树叶,n个结点,深度为h,则 A) n=h+m B) h+m-2n C)M Fh-1 D)n=2-1 20.如果某二叉树的前序为stuw,中序为 atvs,那么该二叉树的后序为c A)wits B) vwuts C)wuvts D)wutsv 21.如图所示的t2是由有序树t1转换 而来的二叉树,那么树t1有c个叶结点。 B)5 D)7 22.设n,m为一棵二叉树上的两个结点,在中序遍历时,n在m前的条件是 A)n在m的右方 B)n是m的祖先 C)n在m的左方 D)n是m的子孙 23.线索二叉树是一种c结构。 A)逻辑B)逻辑与存储C)物理D)线性 二.填空题(将正确答案填在相应的空中) 1.一棵树如图所示,回答下面的问题
13. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序 遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论_a____ 是正确的。 A） 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B） 树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C） 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D） 以上说法都不对 14. 深度为 5 的二叉树至多有_c____个结点。 A） 16 B） 32 C） 31 D） 10 15. 在一非空二叉树的中序遍历序列中，根结点的右边_a____。 A） 只有右子树上的所有结点 B） 只有右子树上的部分结点 C） 只有左子树上的部分结点 D） 只有左子树上的所有对点 16. 树最适合用来表示__c___。 A） 有序的数据元素 B） 无序的数据元素 C） 元素之间具有分支层次关系的数据 D）元素之间无联系的数据 17. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序__a___。 A） 不发生改变 B） 发生改变 C） 不能确定 D） 以上都有不对 18. 实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用_d__存储结 构。 A） 二叉链表 B） 广义表存储结构 C） 三叉链表 D） 顺序存储结构 19. 对一个满二叉树，m 个树叶，n 个结点，深度为 h，则___d__。 A） n=h+m B) h+m=2n C) m=h-1 D) n=2h -1 20. 如果某二叉树的前序为 stuwv，中序为 uwtvs，那么该二叉树的后序为_c____。 A) uwvts B) vwuts C) wuvts D) wutsv t2 21. 如图所示的 t2 是由有序树 t1 转换 而来的二叉树，那么树 t1 有_c____个叶结点。 A) 4 B) 5 C) 6 D) 7 22. 设 n, m 为一棵二叉树上的两个结点，在中序遍历时，n 在 m 前的条件是__c___。 A) n 在 m 的右方 B） n 是 m 的祖先 C）n 在 m 的左方 D） n 是 m 的子孙 23. 线索二叉树是一种__c___结构。 A） 逻辑 B） 逻辑与存储 C） 物理 D） 线性 二．填空题（将正确答案填在相应的空中） 1．一棵树如图所示，回答下面的问题： a b e c d f h g i j
(1)棵树的根结点是kL (2)这棵树的叶结点是k2,k5,k4,k7 (3)结点k3的度是2 (4)这棵树的度为 (5)这棵树的深度是_4 (6)结点k3的子女是k5,k6,k7。 (7)结点k3的父结点是k1 4.一棵二叉树的结点数据采用顺序存储结构,存储于数组t中,如图所示,则该二叉树的链接表示 形式为 23456789101112131415161718192021 t 5.深度为k的完全二叉树至少有个结点。至多有个结点,若按自上而下,从左到右次序 给结点编号(从1开始),则编号最小的叶子结点的编号是 在一棵二叉树中,度为零的结点的个数为n,度为2的结点的个数为n,则有no=.n2+1。 7.一棵二叉树的第i(i≥1)层最多有个结点:一棵有n(n>0)个结点的满二叉树共有个叶 子和个非终端结点 8.结点最少的树为空树,结点最少的二叉树为空树。 9.现有按中序遍历二叉树的结果为abc,问有_5种不同形态的二叉树可以得到这一遍历结果, 这些二叉树分别是。 10.根据二叉树的定义,具有三个结点的二叉树有5种不同的形态,它们分别是 11.由如图所示的二叉树,回答以下问题 (1)其中序遍历序列为 dgbaechif
（1） 棵树的根结点是_k1____。 （2） 这棵树的叶结点是__k2,k5,k4,k7___。 （3） 结点 k3 的度是_2____。 （4） 这棵树的度为___3__。 （5） 这棵树的深度是__4___。 （6） 结点 k3 的子女是__k5,k6,k7___。 （7） 结点 k3 的父结点是__k1___。 4. 一棵二叉树的结点数据采用顺序存储结构，存储于数组 t 中，如图所示，则该二叉树的链接表示 形式为_____。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 t: 5. 深度为 k 的完全二叉树至少有_____个结点。至多有_____个结点，若按自上而下，从左到右次序 给结点编号（从 1 开始），则编号最小的叶子结点的编号是_____。 6. 在一棵二叉树中，度为零的结点的个数为 n0，度为 2 的结点的个数为 n2，则有 n0==__n2+1___。 7. 一棵二叉树的第 i(i≥1)层最多有_____个结点；一棵有 n(n>0)个结点的满二叉树共有_____个叶 子和_____个非终端结点。 8. 结点最少的树为_空____树，结点最少的二叉树为_空____树。 9. 现有按中序遍历二叉树的结果为 abc，问有__5___种不同形态的二叉树可以得到这一遍历结果， 这些二叉树分别是_____。 10. 根据二叉树的定义，具有三个结点的二叉树有_5____种不同的形态，它们分别是_____。 11. 由如图所示的二叉树,回答以下问题: (1) 其中序遍历序列为__dgbaechif___。 K1 K2 K3 K4 K7 K5 K6 e a f d g c j l h I b a b c i d f g e h