数据结构复习题2.doc

此文档收集于网络，仅供学习与交流，如有侵权请联系网站删除一、选择题（1）数据结构通常是研究数据的（ A ）及它们之间的相互联系。 A. 存储结构和逻辑结构 B. 存储和抽象 C. 联系和抽象 D. 联系与逻辑（2）在逻辑上可以把数据结构分成：（ C ）。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构（3）数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（ C ）。 A. 存储结构 B. 逻辑结构 C. 顺序存储结构 D. 链式存储结（4）算法分析的两个主要方面是（ A ）。A. 空间复杂性和时间复杂性 B. 正确性和简明性C. 可读性和文档性 D. 数据复杂性和程序复杂性（5）下列时间复杂度中最坏的是（ D ）。 A. O（1） B. O（ n） C. O（log2n） D. O（n2）（6）等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为（ C ）。An B(n-1)/2 C n/2 D(n+1)/2（7）设有编号为1，2，3，4的四辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为 ( D ) A1234 B1243 C1324 D1423（8）如果以链表作为栈的存储结构，则出栈操作时（ B ） A必须判别栈是否满 B必须判别栈是否空 C必须判别栈元素类型 D队栈可不做任何判别（9）链栈与顺序栈相比，有一个比较明显的优点是（ B ）。A插入操作更加方便 B通常不会出现栈满的情况。C不会出现栈空的情况 D删除操作根加方便（10）插入和删除只能在一端进行的线性表，称为( C )。 A队列 B循环队列 C栈 D循环栈 （11）若进队的序列为：A，B，C，D，则出队的序列是（ C ）。 AB，C，D，A BA，C，B，D CA，B，C，D DC，B，D，A（12）若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为( B )。 A5和1 B4和2 C2和4 D1和5（13）S=morning，执行求子串函数SubStr(S,2,2)后的结果为( B )。Amo Bor Cin Dng（14）S1=good，S2=morning，执行串连接函数ConcatStr(S1,S2)后的结果为( A )。 Agoodmorning Bgood morning CGOODMORNING DGOOD MORNING（15）S1=good，S2=morning，执行函数SubStr(S2,4,LenStr(S1)后的结果为( B )。 AgoodBning Cgo Dmorn（16）设串S1=ABCDEFG，S2=PQRST ,则ConcatStr(SubStr(S1,2,LenStr(S2),SubStr(S1,LenStr(S2),2)的结果串为( D )。 ABCDEF BBCDEFG CBCPQRST D. BCDEFEF(17)已知二维数组A610，每个数组元素占4个存储单元，若按行优先顺序存放数组元素a35的存储地址是1000，则a00的存储地址是（ B ）。A872 B860 C868D864（18）在一棵具有五层的满二叉树中，结点的总数为（ B ） A16 B31 C32 D33（19）具有64个结点的完全二叉树的深度为（ C ）A5B6 C7（20）具有n（n1）个结点的完全二叉树中，结点i（2in）的左孩子结点是（ D ）。A2iB2i+1C2i-1 D不存在（若2iprior-next=p-next 。（5） A+B/C-D*E的后缀表达式是： ABC/+DE*- 。（6） 解决顺序队列“假溢出”的方法是采用 循环队列 。（7） 循环队列的队首指针为front，队尾指针为rear，则队空的条件为 front = rear 。（8） 设循环队列的头指针front指向队首元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，则队满标志为： front=(rear+1)%MAXLEN 。（9） 设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有 front=11，rear=19，则循环队列中还有 8 个元素。（L= (Nrearfront)% N=（401911）% 40=8）（10） 设S=My Music，则LenStr(s)= _ 8 。（11） 两个字符串分别为：S1=Today is，S2=30 July,2005,ConcatStr(S1,S2)的结果是： Today is 30 July,2005 。（12） 求子串函数SubStr(Today is 30 July,2005,13,4)的结果是： July 。（13） 在串的运算中，EqualStr(aaa,aab)的返回值为 data= x ; p=head-next;while (p!=NULL) & ( p-data!=a )_p=p-next ;if (p=NULL)coutnext=p-next_;_ p-next=s _;(2)假定用一个循环单链表表示一个循环队列，该队列只设一个队尾指针rear，试填空完成向循环队列中插入一个元素为x的结点的函数。typedef struct queuenode / 定义队列的存储结构int data;struct queuenode *next;QueueNode;InQueue(QueueNode *rear,int x) / 向队列插入元素为x的函数 QueueNode *rear;QueueNode *head,*s; s= new QueueNode ; s-data= x ; if(rear=NULL) / 循环队列为空，则建立一个结点的循环队列 rear=s; rear-next; else head= rear-next ; / 循环队列非空，则将s插到后面rear-next= s ;rear=s;rear-next =head;（3）下面程序是把两个串r1和r2首尾相连的程序，即：r1=r1+r2，试完成程序填空。typedef Struct char vecMAXLEN; / 定义合并后串的最大长度int len; / len为串的长度St ;void ConcatStr(Str *r1,Str *r2) / 字符串连接函数int i; coutvecvec; if(r1-len+r2-len MAXLEN ) cout两个串太长，溢出！; else for(i=0;ilen ;i+) / 把r2连接到r1 r1-vec r1-len+i =r2-veci; r1-vecr1-len+i= 0 ; / 添上字符串结束标记 r1-len= r1-len+r2-len ; / 修改新串长度 (4)下面算法是判断字符串是否为回文（即正读和倒读相同），试完成程序填空。#include stdio.htypedef struct char vecMAXLEN; int len;str;void Palindrome (str s) int i=0; ing j= s.len-1 ; while ( j-i=1 ) if ( s.veci= s.vecj ) i+; j- ;continue / (或 j=j+1 ) else break; if ( j-i=1 ) coutIt is not a palindromen; else coutIt is a palindromen;(5)void BInsSort( ) /按递增序对R1R n 进行二分插入排序 int i, j, low, high, m; for( i=2;i= n ; i+) R0=Ri; / 设定R0为监视哨low=1; high= n ；while(low = high) m=(low+high)/2 ;if(R0=high+1;j-)Rj+1= R j ; / 元素后移 Rhigh=R0; / 插入四、应用题（1）已知一棵二叉树的后序遍历和中序遍历的序列分别为：ACDBGIHFE和ABCDEFGHI。请画出该二叉树，并写出它的前序遍历的序列。BCHDDFGEIA解：恢复的二叉树为： 其前序遍历的序列为：E B A D C F H G I（2） 把下列一般树转换为二叉树12435678 ABFEGHIJCD12468 8D537ABCHDDFGEIJ解： （3）把下列森林转换为二叉树ACBDEFGKIJH KABCHDDFGEIJ解：（4）把下列二叉树还原为森林ADBICHFGE解：还原后的二叉树为：ABCHDDFGEI （5）假设用于通信的电文仅由A、B、C、D、E、F、G 8个字母组成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10。试为这8个字母设计哈夫曼编码。解：以权值：2、3、6、7、10、19、21、32构造哈夫曼树：（左子为0，右子为1。）651911281740D213260D10000D023D710D00000111111 01字母编号对应编码出现频率A10107B0019C100002D10016E1132D100013E0121F101110（6）有向图如下图所示，画出邻接矩阵和邻接表解：邻接矩阵 1 2 3 4 5邻接表123524354154（7）已知一个无向图有6个结点，9条边，这9条边依次为(0,1)，(0,2)，(0,4)，(0,5)，(1,2)，(2,3)，(2,4)，(3,4)，(4,5)。试画出该无向图，并从顶点0出发，分别写出按深度优先搜索和按广度优先搜索进行遍历的结点序列。解：231D045从顶点0出发的深度优先搜索遍历的结点序列：0 1 2 3 4 5（答案不唯一）从顶点0出发的广度优先搜索遍历的结点序列：0 1 2 4 5 3（答案不唯一）（8）网G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。2543125431解： 最小生成树： 8 11 10 8 3 4 13 7 3 4 (9) 对于给定结点的关键字集合K=5，7，3，1，9，6，4，8，2，10，（1）试构造一棵二叉排序树；（2）求等概率情况下的平均查找长度ASL。解：（1）构造二叉排序树 ： （2）ASL=(1*1+2*2+3*4+4*3)/10=2.974312596108D(10) 给定结点的关键字序列为：19，14，23，1，68，20，84，27，55，11，10，79。设散列表的长度为13，散列函数为：H（K）=K % 13。试画出线性探测再散列解决冲突时所构造的散列表，并求出其平均查找长度。解：线性探测再散列解决冲突时所构造的散列表：012345678910111214168275519208479231110 平均查找长度ASL=（1*6+2*1+3*3+4*1+9*1）/12=30/3=3(11) 给定结点的关键字序列为：47，7，29，11，16，92，22，8，3，哈希表的长度为11。设散列函数为：H（K）=K % 11。试画出平方探测再散列解决冲突时所构造的散列表，并求出其平均查找长度。解：平方探测再散列解决冲突时所构造的散列表。012345678910112234792167298 平均查找长度ASL=（1*5+2*4）/9 = 13/9 = 5/3 （或1.44）（12）已知数据序列12，02，16，30，28，10，17，20，06，18，写出希尔排序每一趟排序的结果。（设d=5、2、1）解： 12 02 16 30 28 10 17 20 06 18d=5 10 02 16 06 18 12 17 20 30 28d=2 12 02 16 06 17 12 18 20 30 28d=1 02 06 10 12 16 17 18 20 28 30（13）已知数据序列10，18，4，3，6，12，9，15，写出二路归并排序的每一趟排序结果。10 18 4 3 6 12 9 15 10 18 3 4 6 12 9 15 第一趟排序结果 3 4 10 18 6 9 12 15 第二趟排序结果 3 4 6 9 10 12 15 18 第三趟排序结果（14）已知数据序列53，36，48，36，60，7，18，41，写出采用简单选择排序的每一趟排序结果。解：53 36 48 36 60 7 18 41（7） 36 48 36 60 53 18 41（7 18） 48 36 60 53 36 41（7 18 36） 48 60 53 36 41（7