数据结构复习题2教材

1、、选择题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

2、 ）。A. O( 1)B. O(n）C.2O(log2n)D. O( n2)6）等概率情况下，在有n 个结点的顺序表上做插入结点运算，需平均移动结点的数目为C ）。A nB （n-1）/2C n/2 D （n+1）/27）设有编号为 1，2， 3， 4的四辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为( D )A 1234B1243C 1324D 1423（8）如 果以链表作为栈的存储结构，则出栈 操作时（B )A必须判别栈是否满B必 须 判别栈是否空C必须判别栈元素类型D 队栈可 不做任何判别（9）链 栈与顺序栈相比，有一个比较明显的 优点是（B )A插入 操作更 加方便B通常 不

3、 会出现栈 满的情 况。front 和 rear 的值分别为 3和 0，当C不会 出现栈 空的情 况 D 删除 操 作根加方 便10 ）插 入和删 除只能在一端进行的线性表， 称为 （C) 。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 的值分别为 （ B ）A 5和1B 4和2C2和4D1和5( 13) S=morning ，执

4、行求子串函数 SubStr(S,2,2) 后的结果为( B )。A moB orCinD ng( 14 ) S1=good ， S2=morning ， 执 行 串 连 接 函 数 ConcatStr(S1,S2) 后 的 结 果 为 ( A )。A goodmorningC GOODMORNINGB good morningD GOOD MORNING( 15) S1=good ， S2=morning ，执行 函数 SubStr(S2,4,LenStr(S1) 后的 结 果为 ( B ) 。A goodB ningC go16 ) 设 串 S1=ABCDEFGD morn， S2=PQRS

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

6、in)的左孩子结点是（D ）。A 2iB 2i+1（若 2iprior-next=p-next5) 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

7、)，现经过一系列的入队和出队运算后，有 front=11 ，rear=19 ，则循环队列中还有8个元素。(L= (N rear front)%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) 在串 的运算 中，

8、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) Qu

9、eueNode *rear;QueueNode *head,*s;s= new QueueNode ; s-data= x ; if(rear=NULL) rear=s; rear-next;else head= rear-next rear-next= s ; rear=s;rear-next =head;/ 定义队列的存储结构/ 向队列插入元素为 x 的函数/ 循环队列为空，则建立一个结点的循环队列/ 循环队列非空，则将 s 插到后面3）下面程序是把两个串 r1 和 r2 首尾相连的程序，即： r1=r1+r2 ，试完成程序填空。typedef Struct char vecMAXLEN;

10、 int len;/ 定义合并后串的最大长度/ len 为串的长度Stvoid ConcatStr(Str *r1,Str *r2) int i; coutvecvec; if(r1-len+r2-len MAXLEN ) cout 两个串太长，溢出！ / 字符串连接函数else for(i=0;ilen ;i+)/ 把 r2 连接到 r1r1-vec r1-len+i =r2-veci; r1-vecr1-len+i= 0 ; r1-len= r1-len+r2-len ;/ 添上字符串结束标记/ 修改新串长度（4） 下面算法是判断字符串是否为回文（即正读和倒读相同），试完成程序填空。#in

11、clude stdio.h typedef 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 )/ (或 j=j+1 )i+; j- ;continue elsebreak;if ( j-i=1 )coutIt is not a palindromen;elsecoutIt is a palindromen;(5)void BInsSort( )/ int i, j, low, high, m;for( i=2

12、;i= n ; i+) R0=Ri;low=1;high= n ； while(low = high) m=(low+high)/2 ; if(R0=high+1;j-)R j +1= R j ;Rhigh=R0; /按递增序对 R1R n 进行二分插入排序/ 设定 R0 为监视哨/ 元素后移 插入四、应用题ACDBGIHFE和 ABCDEFGH。I（1）已知一棵二叉树的后序遍历和中序遍历的序列分别为：请画出该二叉树，并写出它的前序遍历的序列。解：恢复的二叉树为：H其前序遍历的序列为： E B A D C F H G I2) 把下列一般树转换为二叉树解：3)K解：A解：还原后的二叉树为：5）假

13、设用于通信的电文仅由A、B、C、D、E、F、G 8 个字母组成，字母在电文中出现的频率分别为 7，19，2，6，32，3，21，10。试为这 8 个字母设计哈夫曼编码。解：左子为 0，右子为 1。）以权值： 2、3、6、7、10、19、21、32 构造哈夫曼树：10001400011010111701 0字母编号对应编码出现频率A10107B0019C100002D10016E1132D100013E01216)有向图如下图所示，画出邻接矩阵和邻接表解：邻接矩阵邻接表，(0,2)(0,4) ，(0,5) ， 分别写出按深101010001000010(1,2) ，(2,3) ，(2,4) ，(

14、3,4) ，(4,5) 。试画出该无向图，并从顶点 0 出发， 度优先搜索和按广度优先搜索进行遍历的结点序列。解：从顶点 0 出发的深度优先搜索遍历的结点序列： 0 1 2 3 4 5（答案不唯一）从顶点 0 出发的广度优先搜索遍历的结点序列： 0 1 2 4 5 3（答案不唯一） 8）网 G 的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。1）试构造一棵二叉排序树；（2）求等概率情况下的平均查找长度解：（ 1）构造二叉排序树 ：ASL 。( 2) ASL=(1*1+2*2+3*4+4*3)/10=2.90810110803013103040110407013070（10） 给定结点的关

15、键字序列为： 19，14，23，1，68，20，84，27， 55，11，10，79。 设散列表的长度为 13，散列函数为： H（K）=K % 13。试画出线性探测再散列解决冲突时 所构造的散列表，并求出其平均查找长度。解：线性探测再散列解决冲突时所构造的散列表：0 1 2 3 4 5 6 7 8 9 10 11 1214168275519208479231110 平均查找长度 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 %

16、 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 ，写出希尔排序每一趟排10 02 16 06 18 12 17 20 30 28d=212 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 1510 18 3 4 6 12 9 15 第一趟排序结果3 41018691215第二趟排序结果3 469 10121518第三趟排序结果（14）已知数据序列53，36，48，36，60，7，18，41 ，写出采用简单选择排序的每一趟排序结果。解： 53 36 4836607 18 41（7）36 483660531841（7