《数据结构》复习题.docx
数据结构复习题一、填空题.数据结构中评价算法的两个重要指标是 和。1 .数据元素之间有多种关系，其中常见的关系、02 .线性表的顺序存储是用 实现的。3 .在长度为n的顺序表中插入一个元素，等概率的情况下的平均移动元素的次数 是 o.三个结点可构成 种不同形态的二叉树。4 .对于栈只能在(位置)插入和删除元素。5 .对矩阵压缩是为了 o.深度为k的完全二叉树至少有 个结点，至多有 个结点。6 .对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为 个，其中 个用于链接孩子结点。7 .对二叉排序树进行 遍历，可得到排好序的递增结点序列。8 . N个顶点的连通图的生成树含有 条边。9 .己知有序表为(12, 18,24, 35,47, 50,62,83,90, 115, 134)当用二分法查找 90 时，需 次查找成功，47时 成功，查100时，需 次才能确定不成功。10 .算法的计算量的大小称为计算的.在线性表的顺序存储中，元素之间的逻辑关系是通过 决定的；在线性表的链接存储中，元素之间的逻辑关系是通过决定的。11 .对于一个具有N个结点的单链表，在已知的结点*P后插入一个新结点的时间复杂度为 ,在给定值为X的结点后插入一个新结点的时间复杂度为.12 .无论对于顺序存储还是链接存储的队列来说，进行插入或删除运算的时间复杂度均相同 为.13 .对于一棵具有n个结点的树，该树中所有结点的度数之和为.在一个完全二叉树的顺序存储中，若一个结点的下标为i,则它的左子女结点的下标为 ，右子女结点的下标为.14 .对于一棵具有n个结点的二叉树，对应二叉链表中指针总数为一个，其中一个用于 指向子女结点，一个指针空闲着.以折半搜索方法搜索一个线性表时，此线性表必须是存储的表15 .在一个无向图中，所有顶点的度数之和等于所有边数的一倍。16 .在一个具有n个顶点的无向完全图中，包含有条边，在一个具有n个顶点的有向完全图中，包含有一条边。17 .在一个具有n个顶点的无向图中，要连通所有顶点则至少需要一条边。18 .对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别为和条二、选择题1 .数组A0. 4,0. 3中含有元素的个数()。A. 55B. 20C. 36D. 16.下面关于线性表的叙述中，错误的是哪一个？()A.线性表采用顺序存储，必须占用一片连续的存储单元。B.线性表采用顺序存储，便于进行插入和删除操作。C.线性表采用链接存储，不必占用一片连续的存储单元。D.线性表采用链接存储，便于插入和删除操作。3 .若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复 杂度为()(l<=i<=n+l)oA. 0(0) B. 0(1)C. 0(n)D, 0(n2).对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是( )oA. head=NULL B. =NULL C. =head D. head!=NULL.一个栈的输入序列为123n,若输出序列的第一个元素是n,输出第i (l<=i<=n)个元素 是()。A.不确定B. n-i+1C. iD. n-i.已知指针p所指结点不是尾结点，若在*p之后插入结点*s,则应执行下列哪一个操作？( )A. s->link = p； p->link = s；B. s->link = p->link； p->link = s；C. s->link = p->link； p = s；D. p->link = s； s->link = p；7 .设无向图的顶点个数为n,则该图最多有()条边。A. n-1B. n(n-l)/2 C. n(n+l)/2 D. 0 E. n2.下列排序算法中()不能保证每趟排序至少能将一个元素放到其最终的位置上。A.快速排序B. shell排序C.堆排序 D.冒泡排.对线性表进行二分查找时，要求线性表必须()。A.以顺序方式存储B.以顺序方式存储,且数据元素有序C.以链接方式存储D.以链接方式存储,且数据元素有序.在下面的排序方法中，辅助空间为0 (n)的是()。A.希尔排序B.堆排序C.选择排序 D.归并排序11在下面的程序段中，对x的赋值语句的频度为()FOR i:=l TO n DOx:=x+l;A. 0(2n) B. 0(n) C. 0(n2)D. 0(log2n)12线性表是具有n个()的有限序列(n>0)oA.表元素 B.字符 C.数据元素 D.数据项13若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为()(K=i<=n+l)oA. 0(0) B. 0(1)C. 0(n)D. 0(n2)14下面哪一方法可以判断出一个有向图是否有环(回路)()A.深度优先遍历B.拓扑排序 C.求最短路径D.求关键路径15链表不具有的特点是()A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比16某堆栈的输入序列为a, b, c , d,下面的四个序列中，不可能是它的输出序列的是( )oA. a, c, b, d B. b, c, d, a C. c, d, b, a D. d, c, a, b17设计一个判别表达式中左，右括号是否配对出现的算法，采用()数据结构最佳。A.线性表的顺序存储结构B.队列 C.线性表的链式存储结构 D.栈18如果节点A有两个兄弟，B是A的双亲，则B的度为 ()A. 5B. 4C. 3D. 2)o19数组A04, 0.3中含有元素的个数（A. 55B. 20C. 36D. 1620在一个有向图中，所有顶点的入度之和等于所有边数的（）倍A. 1/2 B. 1C. 2 D. 4三、名词解释1.堆（heap） 2.完全图 3 .二叉排序4.树中节点的度和树的度5 数据结构 6稀疏矩阵7排序算法的稳定性8连通图9AOE网四、简答题 1、简述线性表的特点？2、举例说明快速排序是否为稳定排序法?3、简述线性表和队列的共同点和区别4、举例说明希尔排序是否为稳定排序法5、写出右图的拓扑排序序列第3题图6、某二叉树的后序遍历为：HDFBKGCEA,中序遍历为：HBCFAEKCG,请构造出此二叉树 7、有如下的一组数据，1,5,6, 10, 15, 16,17, 18, 19,20,30。画出其折半查找的判定树。8、写出第3题图的深度优先和广度优先遍历序列9、用序列（20, 15, 35, 30, 25, 40）建立一个二叉排序树，画出该树。10、画一棵深度为4的完全二叉树五、算法设计题1、对单链表中节点的存储结构进行定义.说明节点中为整型数据。2、对单链表中节点的存储结构进行定义（链表中节点的数据类型为整形）2、根据上题定义的 节点的结构，写出在单链表中查找值为X节点的算法，查找成功，返回X在线性表中的位置, 查找失败，返回0。函数头部如下int Search（node *head, int x）3、写出折半查找算法数据结构课程考试试题答案一、填空题(每小题0.5分，共10分)1 .数据结构中评价算法的两个重要指标是时间复杂性和空间复杂性2 .数据元素之间有多种关系，其中常见的关系有集合、线性、树、图。3 .线性表的顺序存储是用数组实现的。4 .在长度为n的顺序表中插入一个元素，等概率的情况下的平均移动元素的次数是 (n+l)/25 .三个结点可构成种不同形态的二叉树。6 .对于栈只能在 栈顶(位置)插入和删除元素。7 .对矩阵压缩是为了节省存储空间8 .深度为k的完全二叉树至少有卜个结点，至多有211个结点。9 .对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为 2n 个,其中 n-l个用于链接孩子结点。10 .对二叉排序树进行中序 遍历,可得到排好序的递增结点序列。11 . N个顶点的连通图的生成树含有上!_条边12 .己知有序表为(12, 18,24,35,47, 50,62,83,90, 115, 134)当用二分法查找 90 时，需2 次查找成功，47时 4成功，查100时，需 4 次才能确定不成功。13 .算法的计算量的大小称为计算的时间复杂性.在线性表的顺序存储中，元素之间的逻辑关系是通过元素在数组中的位置决定的;在线性表的链接存储中，元素之间的逻辑关系是通过避圈决定的。14 .对于一个具有N个结点的单链表，在已知的结点*P后插入一个新结点的时间复杂度为 ,在给定值为X的结点后插入一个新结点的时间复杂度为 0 (n).15 .无论对于顺序存储还是链接存储的队列来说，进行插入或删除运算的时间复杂度均相同 为。.16 .对于一棵具有n个结点的树，该树中所有结点的度数之和为n-l.在一个完全二叉树的顺序存储中，若一个结点的下标为i,则它的左子女结点的下标为 2*i ,右子女结点的下标为2*i+l .17 .对于一棵具有n个结点的二叉树，对应二叉链表中指针总数为2*n 个，其中n-l个用于指向子女结点，n+1个指针空闲着.以折半搜索方法搜索一个线性表时，此线性表必须是顺序存储的有序表18 .在一个无向图中，所有顶点的度数之和等于所有边数的上一倍。19 .在一个具有n个顶点的无向完全图中，包含有n*（n-l）/2 条边,在一个具有n个顶点 的有向完全图中，包含有 n*（nT）条边。20 .在一个具有n个顶点的无向图中，要连通所有顶点则至少需要n-1条边。21 .对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为 2*e和 e 条二、选择题（每小题1分，共10分）1-5 CBCBB 6-10 BCBBD 11-15 BCCBB 11-15 DDCBB三、略Ui略五、略名词解释（每题4分，共20分）简答题（每题5分，共40分）算法设计题（20分）
