数据结构练习题11
需积分: 0 142 浏览量
2022-08-08
18:18:40
上传
评论
收藏 148KB DOCX 举报
练习题：
一、填空题
1、______是数据的最小单位，_________是讨论数据结构时涉及的最小数据单位。
2、设一棵完全二叉树具有 50 个结点，则此完全二叉树有 个度为 2 的结点。
3、在用于表示有向图的邻接矩阵中，对第 i 列的元素进行累加，可得到第 i 个顶点的______
度。
4、已知一棵度为 3 的树有 2 个度为 1 的结点，3 个度为 2 的结点，4 个度为 3 的结点，则该
树中有____________ 个叶子的结点。
5、有一个长度为 20 的有序表采用二分查找方法进行查找，共有＿＿＿＿＿＿个元素的查找
长度为 3。
6、对于双向链表，在两个结点之间插入一个新结点需要修改的指针共______个。
删除一个结点需要修改的指针共__________个。
7、已知广义表 LS=(a,(b,c,d),e)，它的深度是__________，长度是__________。
8、循环队列的引入是为了克服__________。
9、表达式 a*(b+c)-d/f 的后缀表达式是________________。
10、数据结构中评价算法的两个重要指标是 。
11、设 r 指向单链表的最后一个结点，要在最后一个结点之后插入 s 所指的结点，需执行的
三条语句是___________；r=s; r->next=null;。
12、设有一个空栈，栈顶指针为 1000H(十六进制)，现有输入序列为 a，b，c，d，e，经过
PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH 之 后 ， 输 出 序 列 是 _______ ， 而 栈 顶 指 针 值 是
_______H。设栈为顺序栈，每个元素占 4 个字节。
13、模式串 P=‘abaabcac’的 next 函数值序列为________。
14、任意连通图的连通分量只有一个，即是 。
15、栈的特性是 。
16、串的长度是 。
17、如果一个有向图中没有＿＿＿＿＿＿，则该图的全部顶点可能排成一个拓扑序列。
18、在具有 n 个叶子结点的哈夫曼树中，分支结点总数为 。
19、在线性表的散列存储中，装填因子�又称为装填系数，若用 m 表示散列表的长度，n 表
示待散列存储的元素的个数，则�等于________。
20、排序的主要目的是为了以后对已排序的数据元素进行 。
21、对于一个具有 n 个结点的单链表，在已知的结点*p 后插入一个新结点的时间复杂度为
________,在给定值为 x 的结点后插入一个新结点的时间复杂度为________。
22、线性表 L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一
个元素平均需要移动元素的个数是________。
23、两个栈共享空间时栈满的条件_______。
24、深度为 H 的完全二叉树至少有_ __个结点；至多有_ __个结点；H 和结点总数 N
之间的关系是 __。
25、在有序表 A[1…20]中，按二分查找方法进行查找，查找长度为 4 的元素的下标从小到
大依次是__________。
26、根据初始关键字序列(29，32，05，18，10)建立的二叉排序树的高度为____________。
27、设 F 是由 T1,T2,T3 三棵树组成的森林,与 F 对应的二叉树为 B,已知 T1,T2,T3 的结点数
分别为 n1,n2 和 n3 则二叉树 B 的左子树中有______个结点，右子树中有______个结点。
28、从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较，将其放入
已排序序列的正确位置上的方法，称为_______。对于关键字序列(22，13，11，18，50，
评论0