数据结构与算法复习题.docx

《数据结构与算法复习题.docx》由会员分享，可在线阅读，更多相关《数据结构与算法复习题.docx（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据构造与算法复习题一、 写出以下各词语对应的中文英 sequential storge structure 顺序存储构造 Abstract Data Type (ADT) 抽象数据类型 二叉排序树 Binary sort tree queue 队列 storge structure 存储构造 time complexity 时间复杂度 线性表 Linear List 二叉树 Binary Tree Depth_First Search 深度优先搜索 singly linked lists 单链表 二、 单项选择题 1、数据构造是一门研究非数值计算的程序设计问题中数据元素的 、数据信息在计算机

2、中的存储构造以及一组相关的运算等的课程。 A: 操作对象: 计算方法: 逻辑构造: 数据映象 2、某线性表最常用的运算是插入与删除,插入运算是指在表尾插入一个新元素,删除运算是指删除表头第一个元素,那么采用 存储方式最节省运算时间.。A: 仅有头指针的单向循环链表B: 仅有尾指针的单向循环链表C: 单向链表D:双向链表3、一个栈的入栈序列是a，b，c，d，e，那么栈的不可能的输出序列是_。 A: abcde B: decba C: edcba D: dceab 4、将一个递归算法改为对应的非递归算法时，通常需要使用_。 A: 栈 B: 队列 C: 循环队列 D: 优先队列 5、关于空串，以下说

3、法中正确的有_。A: 空串就是空格串 B: 空串的长度可能不为零C: 空串是零个字符的串 D: 空串的长度就是其包含的空格个数6、二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开场连续存放在存储器内，该数组按行存放时，数组元素A74的起始地址为 。A: SA+141 B: SA+144 C: SA+222 D: SA+2257、某二叉树的前序与后序序列正好相反，那么该二叉树一定是 的二叉树。A: 空或只有一个结点 B: 高度等于其结点数 C: 任一结点无左孩子 D: 任一结点无右孩子8、下述棵二叉树中，是完全二叉树的是： 。: : : :9、深度为5的

4、二叉树至多有_个结点。A: 16 B: 32 C: 31 D: 1010、在一个无向图中，所有顶点的度数之与等于所有边数的 倍。A: 1/2 B: 1 C: 2 D: 4 11、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为_.。A: (n+1)/2 B: n/2 C: (n-1)/2 D: n 12、对线性表进展折半搜索时，要求线性表必须_。 A: 以数组方式存储且结点按关键码有序排列 B: 以数组方式存储 C: 以链接方式存储且结点按关键码有序排列 D: 以链接方式存储13、下述几种排序方法中，要求内存量最大的是_。A: 插入排序 B: 选择排序 C: 快速排序 D: 归

5、并排序14、采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为_。A: On2 B: O(nlog2n) C: O(n) D: O(log2n)15、在一个单链表中，假设删除p所指结点的后续结点，那么执行_。A: p=p-next;p-next=p-next-next; B: p-next=p-next-next; C: p-next=p-next; D: p=p-next-next16、非线性构造中，每个结点_。A:无直接前趋 B:只有一个直接前驱与后继C:只有一个直接前趋与个数不受限制的直接后继D:有个数不受限制的直接前趋与后继17、设稀疏矩阵按列优先顺序存储于三元组表，那么

6、结点(3，2，-5)是三元组表中的第_项。A:2 B:3 C:4 D:118、对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，那么_。A:n0=n2+1 B:n2=n0+1 C:n0=2n2+1 D:n2=2n0+119、下面程序段的时间复杂度是_。s=0；for(i=0；in；i+) for(j=0；jn；j+) s+=Bij；sum=s；A:O(1) B:O(n) C:(n2) D:O(n3)20、以下阐述不正确的选项是_。 A: 计算机内的数值运算依靠方程式，而非数值运算如表、树等那么要依靠数据构造 B：数据构造是研究非数值计算的程序设计问题中计算机的操作对象以及它们

7、之间的关系与操作等的学科 C: 数据的逻辑构造与数据的物理构造有时可以不加区分 D：同样的数据对象，用不同的数据构造来表示，运算效率可能有明显的差异 21、计算机算法指的是，它必须具备输入、输出与_。 A: 计算方法 B: 排序方法 C: 解决问题的有限运算步骤 D: 程序设计方法22、数组与一般线性表的区别主要在_。A: 存储方面 B: 元素类型一致C: 逻辑构造方面 D: 不能进展插入、删除运算23、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个_构造。 A: 栈 B: 队列 C: 数组 D: 树24、在所有排序方法中，关键字比拟的次数与记录的初始排

8、列次序无关的是_。A: 希尔排序 B: 起泡排序 C: 插入排序 D: 选择排序25、二叉排序树中，键值最小的结点_。A: 左指针一定为空 B: 右指针一定为空C: 左、右指针均为空 D: 左、右指针均不为空三、 在一个C语言程序中，有构造类型STUDENT的定义与构造数组allstudents的声明如下：struct STUDENT char name10; int number;STUDENT allstudents1050; allstudents是一个二维数组，它的每个元素都是包含name与number的构造类型。在C语言中，二维数组使用以行序为主序的存储构造，char类型占用1字节，

9、int类型占用4字节。假定allstudents在内存中的起始存储位置是2000，请写出计算allstudentsij的存储位置的算式，并计算allstudents53的存储位置。答: (1) allstudentsij的存储位置=2000+(i*50+j)*14 (2) allstudents53的存储位置=2000(5*50+3)*14=5542四、写出以下程序段的输出结果栈的元素类型SelemType为char 输出结果是：五、 构造Huffman树，并求出带权路径的长度及给出Huffman编码假设用于通信的电文由字符集A，B，C，D，E中的字母构成，这些字母在电文中出现的概率分别为27

10、，43，19，3，12，要求：1、 构造一棵Huffman树左结点的权不大于右结点的权 2、 求出带权路径的长度2分3、 给出Huffman编码左分支为0，右分支为1 答： 1、对应的Huffman树 2、带权路径的长度 27*2+43*1+19*3+3*4+12*4=2143、Huffman编码字符ABCDEHuffman编码101六、 图的应用1、应用Prim普里姆算法求解以下连通图的最小生成树 要求按如下格式给出在构造最小生成树过程中顺序选出的各条边 ，并画出最小生成树 。始顶点号终顶点号权值 答:始顶点号终顶点号权值0313545223151432、图G(V，E)，其中V=1,2,3,

11、4,5,6，,，请画出图G，并写出其邻接矩阵与邻接表表示。答：图G如下所示，图G的邻接矩阵与邻接表表示分别如图(b)与(c)所示。对于这类问题，只要掌握了图的概念与存储构造就可以做出正确的答案。通常情况下对图的顶点排列顺序与各顶点的邻接点排列顺序并没有特定要求，因此，在写出邻接矩阵与邻接表表示时，只要按照某种排列顺序画出相应的构造图就可以了。但应该注意的是，对于邻接矩阵表示，如果顶点结点的顺序不同，那么邻接矩阵就不一样；对于邻接表表示，如果顶点结点的顺序或者邻接点的顺序不同，那么邻接表就不一样。0 1 1 1 0 00 0 0 0 1 00 1 0 0 1 10 0 0 0 0 10 0 0

12、0 0 10 0 0 0 0 0(b)图 图及其存储构造1(a)34256(c)126453223545666七、根据二叉树的遍历，恢复该二叉树并进展其他遍历操作 一棵二叉树的先序遍历为：acbrsedfmlk，中序遍历为：rbsceafdlkm ，试画出该二叉树 ，并写出它的后序遍历 。答:(1) 画出该二叉树:(2)后序遍历:rsbecfklmda八、 构造哈希表并求其成功查找时的ASL 设有一组关键字19，01，23，14，55，20，84，27，68，11，10，77，采用哈希函数：Hkey= key % 13，假设用开放定址法的线性探测法解决冲突，试在013的哈希地址空间中对该关键字

13、序列构造哈希表并求其成功查找时的ASL。1、填写对应的哈希表 哈希地址0111213关键字 比拟次数 2、求其成功查找时的ASL 答：依题意，m=13，线性探测法的下一个地址计算公式为：di = Hkeydi+1 = di+1% m ；i=1，2，1、哈希表如下：3分哈希地址0111213关键字1比拟次数1214311311322、共有12个关键字，等概率查找，那么成功查找时2分ASL=1+2+1+4+3+1+1+3+1+1+3+2/12=23/12九、建立二叉排序树并作插入与删除操作 一组关键字为28,9,32,40,34,22,25,33,7,15,要求：1、建立一棵二叉排序树 2、画出插

14、入结点20后的二叉排序树 3、画出再删除结点32后的二叉排序树 答：建二叉排序树 插入结点20后的二叉排序树 或 删除结点32后的二叉排序树十、排序算法操作 1、用希尔排序法，对8个数值4，19，28，29，11，21，74，87进展排序，增量序列为:5、3、1，并输出前2趟的结果。 答：第1趟排序结果： 4，19，28，29，11，21，74，87第2趟排序结果： 4，11，21，29，19，28，74，872、用快速排序法，对8个数值46，6，98，19，32，40，60，40进展排序，并输出前2趟的结果。 答：第1趟排序结果： 40，6，40，19，32，46，60，98第2趟排序结果：

15、 32，6，40，19，40，46，60，983、用冒泡排序法，对 10个数值46,74,53,14,26,38,86,65, 27,34进展排序，并输出前2趟的结果。 答：第1趟排序结果： 46 , 53, 14,26,38,74,65,27,34,86 第2趟排序结果： 46,14 ,26,38, 53,65,27,34,74,86十一、 阅读理解算法并答复以下问题与填充 1、二叉树的存储构造为二叉链表，结合以下图阅读以下算法。typedef struct node TElemType data; struct node *next;ListNode;typedef ListNode *L

16、inkList;LinkList Leafhead=NULL;void Inorder(BTree T) LinkList s; if(T) Inorder(T-lchild); if(!T-lchild) & (!T-rchild) s=(ListNode*)malloc(sizeof(ListNode); s-data=T-data; s-next=Leafheak; Lerfhead=s; Inorder(T- rchild); 对于上图所示的二叉树：1画出执行上述算法后所建立的构造 2说明该算法的功能 答：1执行上述算法后建立的构造为如下所示的链表 2该算法的功能是用中序遍历递归算法对

17、二叉树进展遍历，将二叉树中叶结点数据域的值作为单链表结点的值，并用头插法建立一个以Leafhead为头指针的逆序单链表即按二叉树中叶结点数据从右至左链接成一个链表。2、以下算法以二叉链表为存储构造，交换二叉树各结点的左右子树。请在有横线的地方填写适宜的内容。 typedef char DataType;typedef struct node DataType data; struct node *lchild, *rchild; BinTNode; typedef BinTNode *BinTree; BinTree s T) BinTree t,t1,t2; if (T=NULL) t=_(

18、1);else t=(BinTree)malloc(sizeof(BinTNode);t-data=_(2); t1=slchild); t2=srchild); t-lchild=_(3);t-rchild=_(4); return(_(5); 答：(1) NULL ;(2) T-data;(3) t2 ;(4) t1 ;(5) _ t_; 3、以下算法的功能是什么？void abct(SqList &L) for ( i=2; inext!=NULL ) p=p-next;len+; return (len);2、写一算法用头插法建立无头结点的单链表，结果返回单链表的头指针 typedef

19、 char DataType; typedef struct node DataType data; struct node *next; ListNode; typedef ListNode *LinkList;答：3、线性表的元素是无序的，且以带头结点的单链表作为存储构造；设计一个删除表中所有值小于max但大于min的元素的算法。算法描述如下：delete(LinkList *head, int max, int min)答：delete(LinkList *head, int max, int min) LinkList *p,*q; q=head; p=head-next; while

20、 (p!=NULL) if(p-datadata=max) q=p; p=p-next; else q-next=p-next; free(p); p=q-next; 4、 试写一个算法,实现单链表的就地逆置,即利用原表的存储空间将线性表(a1,a2,.an)逆置为 (an,an-1,a2, a1) 单链表结点的类型定义如下: typedef struct node /*结点类型定义*/ Datatype data; /*结点的数据域*/ struct node *next; /*结点的指针域*/ ListNode;答:void InverseList (LinkList &head) ListNode *p, *t, *h; h=head-next; p=h-next; h-next=NULL; while(p!=NULL) t=p-next; p-next=h; h=p; p=t; head-next=h;第 17 页