数据结构复习题2

1、一、选择题（1）数据结构通常是研究数据的（ A ）及它们之间的相互联系。A. 存储结构和逻辑结构 B. 存储和抽象（2）在逻辑上可以把数据结构分成： （ C ）。A. 动态结构和静态结构C. 线性结构和非线性结构C. 联系和抽象D. 联系与逻辑B. 紧凑结构和非紧凑结构D. 内部结构和外部结构（3）数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为 （ C ）。A. 存储结构B.（4）算法分析的两个主要方面是（A. 空间复杂性和时间复杂性C. 可读性和文档性（5）下列时间复杂度中最坏的是（逻辑结构A ）。D ）。C. 顺序存储结构D. 链式存储结A. O（ 1）6）等概率情

2、况下，在有n）C ）。AnB.D.C.正确性和简明性 数据复杂性和程序复杂性O(log2n)2D. O( n2)B.n 个结点的顺序表上做插入结点运算，需平均移动结点的数目为. （n-1）/2 C. n/2D. （n+1）/23， 4的四辆列车，顺序进入一个栈结构的站台，下列不可n/2能的出站顺序为A. 1234( D )B .1243C. 1324D . 1423（8）如 果以链表作为栈的存储结构，则出栈 操作时（B )A. 必须判别栈是否满B.必须判别栈是否空C. 必须判别栈元素 类型D. 队栈可 不做任何判别（9）链 栈与顺序栈相比，有一个比较明显的 优点是（B )7）设有编号为1， 2

3、，A.插入操作更加方便B.通常不 会出现栈O满的情 况。C.不会出现栈空的情况D.删除操 作根加方A .队列B. 循环队列C .栈D.循 环栈11)若进队的序列为：A， B，C, D,则出队的序列是（C）。A.B， C， D， AB .A，C，B， DC.A，B， C， DD .C，B，D， A12)若用一个大小为6的数组来实现循环队列，且当前front和 rear 的值分别为 3和 0，当10 ）插 入和删 除只能 在一端进行的线 性表，称为 （ C）。）。从队列中删除一个元素，再加入两个元素后，front和rear的值分别为（BA . 5和 1B. 4和 2C . 2和 4D. 1和 51

4、3 ) S=morning，执行求子串函数SubStr（S,2,2）后的结果为（B ）。B . orC. inD . ngA. mo(14)S1=good ，S2=morning，执行串连接函数 ConcatStr(S1,S2) 后的结果为( A )。A . goodmorningB . good morningC . GOODMORNINGD . GOOD MORNING(15)S1=good ，S2=morning，执行函数 SubStr(S2,4,LenStr(S1) 后的 结果为( B )。A goodB ningD . mornC. go( 16) 设 串 S1=ABCDEFG ，

5、S2=PQRST ,则 ConcatStr(SubStr(S1,2,LenStr(S2),SubStr(S1,LenStr(S2),2)的结果串为( D )。A BCDEFB BCDEFGCBCPQRSTD. BCDEFEF（17） 已知二维数组 放数组元素 a35A610 ，每个数组元素占 4个存储单元， 若按行优先顺序存 的存储地址是 1000，则 a00 的存储地址是（B )。A 872B 860C 868D86418）在一棵具有五层的满二叉树中，结点的总数为（A. 16B. 3119）具有 64 个结点的完全二叉树的深度为（A . 5B. 6C32C )C. 7D33（20）具有n （

6、 n1）个结点的完全二叉树中，结点i( 2in)的左孩子结点是（D )。A . 2i B . 2i+1（若 2ip rior- n ext =p-nexto(6)A+B/C-D*E的后缀表达式是:ABC/+DE*- o解决顺序队列“假溢出”的方法是采用循环队列。循环队列的队首指针为front，队尾指针为rear，则队空的条件为front =rear 。(8)设循环队列的头指针front指向队首元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN,则队满标志为：fron t=(rear+1)%MAXLEN(9)设循环队列的容量为 40 (序号从0到39),现经过一系列的

7、入队和出队运算后，有front=11 , rear=19 ,则循环队列中还有8个元素。(L= (N + rear front)%(10)(11)N=( 40+ 19- 11)设 S=My Music两个字符% 40=8)，贝U LenStr(s)= _8串分另U为S1=Today isS2=30Today is 30 Julv,2005July,2005,13,4) 的结果是：July,2005,Co ncatStr(S1,S2)的结果是:求子串函数 SubStr(Today is 30July o在串的运算中，EqualStr(aaa,aab) 的返回值为 data=xp=head-n ex

8、t;while (p !=NULL) & ( p-data!=a )p=p-nextif (p=NULL)coutnextp-n ext=s(2)假定用一个循环单链表表示一个循环队列，该队列只设一个队尾指针rear，试填空完成向循环队列中插入一个元素为x的结点的函数。typ edef struct queue node int data;struct queue node *n ext;QueueNode;In Queue(QueueNode *rear,i nt x) QueueNode *rear;QueueNode *head,*s;s= new QueueNode/定义队列的存储结构/

9、向队列插入元素为x的函数s-data= X : if(rear=NULL) rear=s; rear-n ext; else head=rear- nextrear- n ext=srear=s;rear- n ext=head;/循环队列为空，则建立一个结点的循环队列/循环队列非空，则将s插到后面(3)下面程序是把两个串 r1和r2首尾相连的程序，即：r1=r1+r2，试完成程序填空。typ edef Struct char vecMAXLEN;int len;St ;void Con catStr(Str *r1,Str *r2) /定义合并后串的最大长度/ len为串的长度/字符串连接函

10、数int i;coutvecvec;if(r1-le n+r2-le nMAXLEN )cout两个串太长，溢出！ elseH.for(i=0;ilen;i+)r1-vec r1-len+i =r2-veci; r1-vecr1-le n+i=0;r1-le n=r1-le n+r2-le n:/把r2连接到r1/添上字符串结束标记/修改新串长度(4)下面算法是判断字符串是否为回文(即正读和倒读相同)，试完成程序填空。#in eludestdio.htyp edefstruct charvecMAXLEN;intlen;str;voidP ali ndrome (str s) int i=0;

11、ing j=s.le n-1while(i-i=1)if ( s.veci=s.vecN)i+;j-;c ontinue11(或 j=j+1)elsebreak;if (j-i=1)coutlt is not a p ali ndromen;elsecoutIt is a p ali ndromen;(5)void Bln sSort()/按递增序对R1R n 进行二分插入排序 int i, j, low, high, m;for( i=2;i=n ; i+) R0=Ri;/设定R0为监视哨low=1;high=while(low=high)m=(low+high)/2if(R0=high+1

12、;j-)Ri+1= R j /元素后移Rhigh=R0;/插入ACDBGIHF和 ABCDEFGHI四、应用题（1）已知一棵二叉树的后序遍历和中序遍历的序列分别为:请画出该二叉树，并写出它的前序遍历的序列。解：恢复的二叉树为：其前序遍历的序列为：E B A D C F H G I(2) 把下列一般树转换为二叉树解:H解:ABGCDK解：还原后的二叉树为:（5）假设用于通信的电文仅由 的频率分别为7， 解：以权值：19, 2, 6, 32, 3, 21,B、C、D、E、F、G 8个字母组成，字母在电文中出现10）试为这8个字母设计哈夫曼编码）32构造哈夫曼树：（左子为0，右子为1。）2、3、6、

13、7、 10、 19、 21、字母编号对应编码出现频率1A10107B0019C100002D10016E1132D100013E0121(6)有向图如下图所示，画出邻接矩阵和邻接表解:邻接矩阵1(010邻接表度优先搜索和按广度优先搜索进行遍历的结点序列。解:从顶点0出发的深度优先搜索遍历的结点序列：0 1 2 3 4 5 (答案不唯一)从顶点0出发的广度优先搜索遍历的结点序列：0 1 2 4 5 3 (答案不唯一)(8)网G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。08解:10110131011L。13(9)对于给定结点的关键字集合K=5(1),7, 3,1(2)解:试构造一棵二叉

14、排序树；求等概率情况下的平均查找长度(1)构造二叉排序树ASL。(2)ASL=(1*1+2*2+3*4+4*3)/10=2.91， 68， 20， 84， 27， 55， 11， 10， 79。 设散列表的长度为 13,散列函数为：H ( K)=K % 13。试画出线性探测再散列解决冲突时 所构造的散列表，并求出其平均查找长度。解：线性探测再散列解决冲突时所构造的散列表：(10)给定结点的关键字序列为:19， 14， 23,141682755192084792311100123456789101112 平均查找长度 ASL= ( 1*6+2*1+3*3+4*1+9*1)/12=30/3=320

15、,（或 1.44）06, 18，写出希尔排序每一趟排12 02 16 30 28 10 17 20 06 18d=21002160618121720302812021606171218 2030 28d=1(13)02 06 10已知数据序列10 18 412161718 20283010 , 18, 4, 3, 6 , 12 , 9 , 15,9 15写出二路归并排序的每一趟排序结果。3 6 121018 3 4 612 915第一趟排序结果341018 691215第二趟排序结果46910121518已知数据序列53，36，48,3(14)排序结果。解：53 36 48 36 60_ 7

16、18 4136,第三趟排序结果60 , 7, 18 , 41，写出采用简单选择排序的每一趟（11）给定结点的关键字序列为：47, 7, 29, 11, 16, 92, 22, 8, 3,哈希表的长度为 11。设散列函数为：H （ K）=K % 11。试画出平方探测再散列解决冲突时所构造的散列表，并求 出其平均查找长度。解：平方探测再散列解决冲突时所构造的散列表。01234567891011223 14792167 1298平均查找长度 ASL= （ 1*5+2*4）/9 = 13/9 = 5/3 （12）已知数据序列12 , 02, 16, 30, 28, 10, 17, 序的结果。（设d=5、2、1）解： d=5(7)316483660531841(718)418