数据结构复习题二及答案Word文档格式.docx

1、 （A） 1 （B） n （C） nlog2n （D） n25设一组初始关键字记录关键字为（20，15，14，18，21，36，40，10），则以20为基准记录的一趟快速排序结束后的结果为（ ）。（A） 10，15，14，18，20，36，40，21 （B） 10，15，14，18，20，40，36，21 （C） 10，15，14，20，18，40，36，2l （D） 15，10，14，18，20，36，40，216设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（ ）。 （A） O（1） （B） O（log2n） （C） （D） O（n2）7设无向图G中有n个顶点e条边，则其对应

2、的邻接表中的表头结点和表结点的个数分别为（ ）。 （A） n，e （B） e，n （C） 2n，e （D） n，2e8. 设某强连通图中有n个顶点，则该强连通图中至少有（ ）条边。 （A） n（n-1） （B） n+1 （C） n （D） n（n+1）9设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（ ）方法可以达到此目的。 （A） 快速排序 （B） 归并排序 （C） 堆排序 （D） 插入排序10.下列四种排序中（ ）的空间复杂度最大。 （A） 插入排序 （B） 冒泡排序 （C） 堆排序 （D） 归并排序11 设一组权值集合W=2，3，4，5，6

3、，则由该权值集合构造的哈夫曼树中带权路径长度之和为（ ）。 （A） 20 （B） 30 （C） 40 （D） 4512执行一趟快速排序能够得到的序列是（ ）。 （A） 41，12，34，45，27 55 72，63 （B） 45，34，12，41 55 72，63，27 （C） 63，12，34，45，27 55 41，72 （D） 12，27，45，41 55 34，63，7213设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（ ）。（A） head=NULL （B） head-next=NULL（C） head-next=head （D） head!=NULL14时间

4、复杂度不受数据初始状态影响而恒为O（nlog2n）的是（ ）。 （A） 堆排序 （B） 冒泡排序 （C） 希尔排序 （D） 快速排序15设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（ ）。 （A） 空或只有一个结点 （B） 高度等于其结点数 （C） 任一结点无左孩子 （D） 任一结点无右孩子16一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（ ）。 （A） 堆排序 （B） 冒泡排序 （C） 快速排序 （D） 希尔排序17设某棵三叉树中有40个结点，则该三叉树的最小高度为（ ）。 （A） 3 （B） 4 （C） 5 （D） 618顺序查找不论在顺序线性表中还是在

5、链式线性表中的时间复杂度为（ ）。 （A） O（n） （B） O（n2） （C） O（n1/2） （D） O（1og2n）19二路归并排序的时间复杂度为（ ）。 （A） O（n） （B） O（n2） （C） O（nlog2n） （D） O（1og2n）20. 深度为k的完全二叉树中最少有（ ）个结点。 （A） 2k-1-1 （B） 2k-1 （C） 2k-1+1 （D） 2k-121.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（ ）。 （A） front-next=s；front=s； （B） s-

6、next=rear；rear=s； （C） rear- （D） s-next=front；22.设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（ ）。 （A） O（n+e） （B） O（n2） （C） O（ne） （D） O（n3）23.设某哈夫曼树中有199个结点，则该哈夫曼树中有（ ）个叶子结点。 （A） 98 （B） 99 （C） 100 （D） 10124.设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（ ）。25.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（ ）。 （A） 第i行非0元素的个数之和 （B） 第i列非0元素的个数

7、之和 （C） 第i行0元素的个数之和 （D） 第i列0元素的个数之和26下列程序段的时间复杂度为（ ）。for（i=0；m； i+） for（j=0； jt； j+） cij=0； j+） for（k=0； kright=s； s-left=p； p-right-left=s；right=p-right；s- （C） p-31下列各种排序算法中平均时间复杂度为O（n2）是（ ）。 （A） 快速排序 （B） 堆排序 （C） 归并排序 （D） 冒泡排序32设输入序列1、2、3、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（ ）。 （A） n-i （B） n-1-i （

8、C） n+l -i （D） 不能确定33设散列表中有m个存储单元，散列函数H（key）= key % p，则p最好选择（ ）。 （A） 小于等于m的最大奇数 （B） 小于等于m的最大素数 （C） 小于等于m的最大偶数 （D） 小于等于m的最大合数34设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（ ）个。 （A） 4 （B） 5 （C） 6 （D） 735.设完全无向图中有n个顶点，则该完全无向图中有（ ）条边。 （A） n（n-1）/2 （B） n（n-1） （C） n（n+1）/2 （D） （n-1）/236.设顺序表

9、的长度为n，则顺序查找的平均比较次数为（ ）。 （A） n （B） n/2 （C） （n+1）/2 （D） （n-1）/237.设有序表中的元素为（13，18，24，35，47，50，62），则在其中利用二分法查找值为24的元素需要经过（ ）次比较。 （A） 1 （B） 2 （C） 3 （D） 438.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（ ）。 （A） 6 （B） 11 （C） 5 （D） 6.539.设有向无环图G中的有向边集合E=2，33，41，4，则下列属于该有向图G的一种拓扑排序序列的是（ ）。 （A） 1，2，3，4 （B） 2，3

10、，4，1 （C） 1，4，2，3 （D） 1，2，4，340.设有一组初始记录关键字序列为（34，76，45，18，26，54，92），则由这组记录关键字生成的二叉排序树的深度为（ ）。二、填空殖（每空1分 共20分）1. 数据的物理结构主要包括_和_两种情况。2. 设一棵完全二叉树中有500个结点，则该二叉树的深度为_；若用二叉链表作为该完全二叉树的存储结构，则共有_个空指针域。3. 设输入序列为1、2、3，则经过栈的作用后可以得到_种不同的输出序列。4. 设有向图G用邻接矩阵Ann作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的_，第i列上所有元素之和等于顶点i的_。5. 设哈

11、夫曼树中共有n个结点，则该哈夫曼树中有_个度数为1的结点。6. 设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为_。7. _遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。8. 设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较_次就可以断定数据元素X是否在查找表中。9. 不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为_。10. 设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为_，右孩子结点的编号为_。11. 设一组初始记录关键字为（

12、72，73，71，23，94，16，5），则以记录关键字72为基准的一趟快速排序结果为_。12. 设有向图G中有向边的集合E=4，3，则该图的一种拓扑序列为_。13. 下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。struct recordint key; int others;int hashsqsearch（struct record hashtable ,int k）int i,j; j=i=k % p;while （hashtablej.key!=k&hashtablej.flag!=0）j=（_） %m; if （i=j） return（-1）; if （

13、_ ） return（j）; else return（-1）;14. 下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。typedef struct nodeint key; struct node *lchild; struct node *rchild;bitree;bitree *bstsearch（bitree *t, int k） if （t=0 ） return（0）;else while （t!=0）if （t-key=k）_; else if （t-keyk） t=t-lchild; else_;15for（i=1，t=1，s=0；ii+） t=t*i；的时间

14、复杂度为_。16设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X，则进行插入操作的语句序列为_（设结点的指针域为next）。17设有向图G的二元组形式表示为G =（D，R），D=1，2，3，4，5，R=r，r=2,44,51,33,23,5，则给出该图的一种拓扑排序序列_。18设无向图G中有n个顶点，则该无向图中每个顶点的度数最多是_。19设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有_个结点数。20设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为_。21设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针

15、变量p所指向的结点为叶子结点的条件是_。22简单选择排序和直接插入排序算法的平均时间复杂度为_。23快速排序算法的空间复杂度平均情况下为_，最坏的情况下为_。24.散列表中解决冲突的两种方法是_和_。25. 设指针p指向单链表中结点A，指针s指向被插入的结点X，则在结点A的前面插入结点X时的操作序列为：1） s-next=_；2） p-3） t=p-4） p-data=_；5） s-data=t；26. 设某棵完全二叉树中有100个结点，则该二叉树中有_个叶子结点。27. 设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最

16、多存储_队列元素。28. 对一组初始关键字序列（40，50，95，20，15，70，60，45，10）进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为_，在整个排序过程中最多需要进行_趟排序才可以完成。29.在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择_排序，如果从节省存储空间的角度来考虑则最好选择_排序。30. 设一组初始记录关键字序列为（20，12，42，31，18，14，28），则根据这些记录关键字构造的二叉排序树的平均查找长度是_。31. 设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉树的前序序列为_。32. 设用于通信的电文

17、仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为_。33. 设一组记录关键字序列为（80，70，33，65，24，56，48），则用筛选法建成的初始堆为_。34. 设无向图G（如右图所示），则其最小生成树上所有边的权值之和为_。三、应用题1.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。2已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为0.6，假定选用的散列函数是H（K）= K mod 7，若

18、发生冲突采用线性探查法处理，试：（1）计算出每一个元素的散列地址并在下图中填写出散列表： 0 1 2 3 4 5 6（2）求出在查找每一个元素概率相等情况下的平均查找长度。3已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。4. 在如下数组A中链接存储了一个线性表，表头指针为A 0.next，试写出该线性表。 A 0 1 2 3 4 5 6 7 data605078903440next3572415. 请画出下图的邻接矩阵和邻接表。 6. 已知一个图的顶点集V和边集E分别为：V=1,2,3,4,5,6,7; E=（1,2）3,（1,3）5,（1,4）8

19、,（2,5）10,（2,3）6,（3,4）15,（3,5）12,（3,6）9,（4,6）4,（4,7）20,（5,6）18,（6,7）25; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。7. 画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。8. 阅读算法，回答问题。LinkList mynote（LinkList L）/L是不带头结点的单链表的头指针if（L&L-next）q=L；L=Lp=L； S1：while（pnext） p=p S2：pnext=q；qnext=NULL； return L； 请回答下列问题： （1）说明语句S1的

20、功能； （2）说明语句组S2的功能； （3）设链表表示的线性表为（a1,a2, ,an）,写出算法执行后的返回值所表示的线性 表。四、算法设计题1. 设计在单链表中删除值相同的多余结点的算法。2. 设计在顺序有序表中实现二分查找的算法。3. 设计判断二叉树是否为二叉排序树的算法。4. 设计计算二叉树中所有结点值之和的算法。5. 设计将所有奇数移到所有偶数之前的算法。6. 设计判断单链表中元素是否是递增的算法。数据结构复习题二答案一、选择题1-10 BBAAA BDCCD11-20 DAAAD DBACB21-30 CACDB AAACD31-40 DCBCA CCDAA二、填空题1. 顺序存储

21、结构、链式存储结构2. 9，5013. 54. 出度，入度5. 06. e=d7. 中序8. 79. O（1）10. i/2，2i+111. （5，16，71，23，72，94，73）12. （1，4，3，2）13. j+1，hashtablej.key=k14. return（t），t=t-rchild15. O（n）16. s-next=p-next;next=s17. （1，3，2，4，5）18. n-119. 12920. F=R21. p-lchild=0&rchild=022. O（n2）23. O（nlog2n）， O（n）24. 开放定址法，链地址法25. p-next，s-2

22、6. 5027. m-128. 6，829. 快速，堆30. 19/731. CBDA32. 633. （24，65，33，80，70，56，48）34. 81. 2. H（36）=36 mod 7=1; H（22）=（1+1） mod 7=2; .冲突H（15）=15 mod 7=1;.冲突 H2（22）=（2+1） mod 7=3;H（15）=（1+1） mod 7=2;H（40）=40 mod 7=5;H（63）=63 mod 7=0;H（22）=22 mod 7=1;（1） 0 1 2 3 4 5 663361522（2）ASL=3. （8,9,4,3,6,1）,10,（12,18,1

23、8） （1,6,4,3）,8,（9）,10,12,（18,18） 1,（3,4,6）,8,9,10,12,18,（18） 1,3,（4,6）,8,9,10,12,18,18 1,3, 4,6,8,9,10,12,18,184. 线性表为：（78，50，40，60，34，90）5.邻接矩阵： 邻接表如图11所示：图116. 用克鲁斯卡尔算法得到的最小生成树为： （1,2）3, （4,6）4, （1,3）5, （1,4）8, （2,5）10, （4,7）207. 如图（7）图（7）8. （1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点 （3）返回的线性表为（a2,a3,an,a1） typedef int datatype;typedef struct node datatype data; struct node *next;lklist;void delredundant（lklist *&head） lklist *p,*q,*s; for（p=head;p!=0;p=p- for（q=p-next,s=q;q!=