复习题第一章——第五章一、单选或填空题1. 下列程序段中S语句的执行频度为。

for(i＝0；i＜n；i++ ）for(j＝0；j＜i；j++ ）S；2. 下列算法的时间复杂度是（）。

for(i＝0；i＜n；i++ ）c[i]＝i；3. 算法的时间复杂度可表示为O(1)、线性阶、平方阶O(n2)、对数阶O(logn)和指数阶O(2n)等。

4 以下关于数据结构的基本概念中，叙述正确的是A) 数据元素是数据不可分割的最小单位。

B) 数据是数据对象的子集。

C) 数据元素之间的关系在计算机中可用顺序映像和非顺序映像两种不同的方法表示。

D) 数据结构在计算机中的表示又称为逻辑结构。

5. 在数据结构中，数据的逻辑结构包括（）。

A) 线性结构和非线性结构B) 逻辑结构和物理结构C) 顺序结构和链式结构D) 虚拟结构和抽象结构6. 在数据结构中，数据的存储结构包括。

A) 线性结构和非线性结构B) 逻辑结构和物理结构C) 顺序结构和链式结构D) 虚拟结构和抽象结构7. 线性结构的数据元素之间存在一种( )。

A．一对多关系B．多对多关系C．多对一关系D．一对一关系8. 在长度为n的顺序表中插入一个元素，需要平均移动个元素。

A) n/2 B)nC) n(n-1) D) n(n+1)9. 在有n个元素的顺序表中做插入、删除运算，平均时间复杂度为。

10. 顺序表中逻辑上相邻的元素物理位置相邻，单链表中逻辑上相邻的元素的物理位置相邻。

A)必然、必然B)必然、不一定C)不一定、必然D)不一定、不一定11．相对于顺序存储而言，链式存储的优点是（）。

A．随机存取B．节约空间C．增、删操作方便D．节点间关系简单12 以下关于头结点的描述中，叙述错误．．的是A) 头结点是对链表首元结点的别称B) 若链表中附设头结点，则头指针一定不为空C) 头结点中不存储链表的数据元素，而是一些诸如表长之类的辅助信息D) 在单链表中附设头结点，插入或删除首元素时不必进行特殊处理13．已知L是无表头结点的单链表，且P所指结点既不是首元结点，也不是尾元结点，则在P之后插入S所指结点，则执行（）。

A) S->next=P->next；P->next=S；B) P->next=S->next；S->next=P；C) S->next=P；P->next＝S；D) P->next=S；S->next=P；14. 已知L是带表头结点的非空单链表，且P结点是S结点的直接前驱。

则删除S结点的语句序列为。

I. P->next = S ;free(P)II. P->next = P->next->next; free(S)III. P->next = S->next; free(S)IV. P = P->next ;free(S)A) I和II正确B) II和III正确C) III和IV正确D) 全部正确15. 已知L是带表头结点的单链表，则删除首元结点的语句序列是（）。

A) L->next =L->next->next; free(L)B) P = L ;L= P->next ;free(P)C) P = L->next ; L->next= P->next ;free(P)D) P = L ;L= P->next ;free(P)16. 已知L是一带有头结点的单链表的头指针，则该单链表为空的条件是。

17. 已知P结点是某双向链表的中间结点，则删除P结点的语句序列是，，free(P);18. 设将整数1，2，3，4，5依次进栈，最后都出栈，出栈可以在任何时刻(只要栈不空)进行，则出栈序列不可能的是（）。

A) 32415 B) 45231 C) 32145 D) 4532119. 在栈中由顶向下已存放元素c, b, a 在第4个元素d入栈前，栈中元素可以出栈，则不可．．能．的出栈序列是A) dcba B) cbda C) cdba D) cadb20. 若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行，但不允许连续3次进行退栈操作，则不可能得到的出栈序列是（）。

A．dcebfa B．cbdaef C．bdcaef D．afedcb21. 设有栈S和队列Q，其初始状态为空，元素a1,a2,a3,a4,a5,a6依次入栈，出栈的元素进入队列Q。

若元素出队列的顺序是a2,a4,a3,a6,a5,a1，则栈的容量至少是。

22. 某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则abcde顺序入队，不可能的到的顺序是（）。

A．bacde B．dbace C．dbcae D．ecbad23. 设用一维数组A[n]存储一个栈，令A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。

当从栈中弹出一个元素时，变量T的变化为（）。

A) T=T+1 B) T=T-1C) T不变D) T=n-124. 循环队列是满队列的条件是。

A）Q.rear＝Q.front B）(Q.rear+1) % maxsize＝Q.frontC）Q.rear＝0 D）Q.front＝025. 在具有m个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队满的条件是（）A. front== (rear＋1) % mB. front＋1== rearC. front== rearD. rear== m26. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是（）A)front== (rear＋1) % n B)front＋1==rearC)front==rear D)front==027. 循环队列用数组A[0‥m-1]存放其数据元素。

设front指向其实际的队头，rear指向其实际队尾的下一个位置，则当前队列中的数据元素有个。

28 在串的运算中，StrLength(Concat (’aa’，’bb’))的返回值为A) 0B) 8C) 6D) 429．设s1＝”I have_”，s2＝”a dream”，则strcat(s1, s2)的值是I have_ a dream，SubString(s1,4,3)的值是ave。

30. 设s1＝”I am a student”，s2＝”a student”，则Index(s1,s2)的值是。

31. 假设有二维数组A5×6，每个元素用相邻的4个字节存储，存储器按字节编址。

已知A的基地址为1000，则数组A的最后一个元素a45的第一个字节的地址是；按行存储时，元素a14的第一个字节的地址是。

32. 已知二维数组A[1..7，1..7]按列存放，其起始存储位置为100，每个元素占用4个字节，则元素A[4,6]的第一个字节的地址为。

A）204 B）252C）208 D）25633. 一个非空广义表的表头（）。

A．一定是子表B．一定是原子C．不能是子表D．可以是原子，也可以是子表34. 设广义表L＝（(a,b),c,()），则head(L)＝，tail(L)＝。

二、算法填空：请在空白横线处填写语句，完成如下功能的算法：在无表头结点单链表L的第一个值为x的结点之前插入值为y的结点。

#define OK 1#define ERROR 0typedef struct LNode{int data;struct LNode *next;}LNode,*LinkList;Status Insert(LinkList &L,int x, int y){s=(LinkList*)malloc(sizeof(LNode)); s->data=y;if( ①){ s->next=L; L=s; }else{q=L; p = q->next；while( p!=NULL&& ②) { ③; p=p->next; }if (p==NULL) return ERROR;else{ ④; ⑤; return OK; }}}//Insert第六章一、单选或填空题1. 已知完全二叉树的第7层上有10个叶子结点，则整个二叉树的结点数最多是A) 73 B) 63 C) 235 D) 2452. 300个结点的完全二叉树的叶结点有个。

3．一个具有1025个结点的二叉树的高h为____。

A）11 B）10 C）11至1025之间D）10至1024之间4. m叉树的第i层至多有个结点5. 将一棵有100个节点的完全二叉树从上到下，从左到右依次对节点进行编号，根节点的编号为1，则编号为49的节点的右孩子编号为（）。

6．把如右图所示的树转换成二叉树时，C是（）A. A的左子女B. A的右子女C. B的左子女D. B的右子女7. 设森林F中有3棵树，其结点个数分别是n1、n2和n3，则与森林对应的二叉树根结点的右子树上的结点个数是。

A) n1-1 B)n1+n2 C) 0 D) n2+n38.在一颗度为4的树T中，若有20个度为4的结点，10个度为3的结点，5个度为2的结点，10个度为1的结点，则树T的叶结点个数有个。

9. 一棵二叉树中序遍历结果为DCBAEFG，后序遍历结果为DCBGFEA。

则此二叉树先序遍历的结果应为A) ABCDEFG B)ABECFDG C)AEBFCGD D)不能确定10. 将一棵树t 转换为孩子—兄弟链表表示的二叉树h，则t 的后根遍历是h 的A）先序遍历B）中序遍历C）后序遍历C）层序遍历11.现有一段电文共100个字符，其中A出现50次，B出现20次，C出现5次，D出现10次，E出现15次。

现对这5个字符进行哈夫曼编码，则其平均码长为。

二、解答题1. 某二叉树层序序列为abcdefghij，中序序列为bgdhjaecif。

（1）画出该二叉树；（2）画出该二叉树的后序后继线索树；（3）画出该二叉树对应的树或森林。

2. 一棵二叉树的先序、中序和后序序列分别如下，其中有部分未给出。

先序：__B__EHI__FG__K中序：D__HEIA__CJG__后序：__H__EBF__KG__A（1）试求出空格处的结点字符；（2）画出该二叉树；（3）画出与该二叉树对应的树或森林。

3. 已知某通讯用电文仅有A、B、C、D、E、F六个字符构成，其出现的频率分别为23，5，14，8，25，7，请首先建立哈夫曼树，然后给出六个字符的哈夫曼编码（注：建立哈夫曼树时权值小的为左子树，权值大的为右子树）。

第七章一．单选或填空题1. 若某有向图的邻接矩阵A只有0和1两种元素，其中aij＝1表示有向图中存在弧<i,j>，则编号为i顶点的入度可用表示。