发布时间 : 星期日 文章数据结构复习题与答案更新完毕开始阅读7a1359e459fafab069dc5022aaea998fcc2240c9
.
静态查找表只是查找特定元素或者检索特定元素的属性
最通俗的解释：动态查找表可以对查找表结构进行修改，而静态查找表只是查询
44 在一个含有n个元素的有序表上进行折半查找，找到一个元素最多要进行( b )次元素 比较。
A．?log2(n)? B. ?log2(n)?+1 C. ?log2(n+1)? D. ?log2(n+1)?+1 折半查找每次都会把范围缩小一半，因为最后剩一个元素时，也要执行查找过程，所以+1。
k
每次二分 直到最后一次才找到 就会有 2 = n / 2 得到 k = log2n + 1
45 设输入序列为20, 45, 30, 89, 70, 38, 62，19依次插入到一棵2-3树中(初始状态为空)，
该B-树为( b )。再删除38，该B-树为( f )。
（ 30 62 ） （ 45 ）
（19，20）（ 38 45 ） （ 70，89 ） （ 30 ） （ 70 ）
（19 20） （38 ）（ 62 ） （ 89 ）
a: b:
（ 45 70 ） （ 45 ）
（20） （ 62 ） （ 89 ） （ 20 ） （ 70 ）
（19）（ 30 ） （ 19 ） ( 30,38 ）（ 62 ） （ 89 ）
c: d:
（ 30 70 ） （ 45 ）
（19，20） （ 45 62） （ 89 ） （ 20 ） （ 70 ）
（19 ） （30 ）（ 62 ） （ 89 ）
e: f:
46根据插入次序(80，90，100，110，85，70，75，60，72)建立二叉排序树。
图( a )是最终变化的结果。若仍以该插入次序建立平衡二叉树。图( c )是最 终变化的结果。
80 80 .
. 70 90 75 90 60 75 85 100 60 70 85 100 72 110 72 110 a: b:
90 90 75 100 80 100 70 80 110 75 70 85 110 60 72 85 60 72
c: d:
47 若有序表中关键字序列为：14，20，25，32，34，45，57，69，77，83，92。对其进行 折半查找，则在等概率情况下，查找成功时的平均查找长度是( c )。查找32时需进 行( c )次比较。
A. 1 B. 2 C. 3 D. 4 48 已知哈希表地址空间为A[9]，哈希函数为H(k)=k mod 7，采用线性探测再散列处理冲突。 若依次将数据序列：76,45,88,21,94,77,17存入该散列表中，则元素17存储的下标为( h )；
在等概率情况下查找成功的平均查找长度为( c )。
A. 0 B. 1 C. 2 D. 3 E. 4 F. 5 G. 6 H. 7
49 若从二叉树的根结点到其它任一结点的路径上所经过的结点序列按其关键字递增有序， 则该二叉树是( c )。
A. 二叉排序树 B. 赫夫曼树 C. 堆 D. 平衡二叉树
50 当待排序序列的关键字次序为倒序时，若需为之进行正序排序，下列方案中( d )为佳。 A. 起泡排序 B. 快速排序 C. 直接插入排序 D. 简单选择排序
51 下列排序算法中，( d)算法可能会出现：初始数据有序时，花费的时间反而最多。 A. 堆排序 B. 起泡排序 C. 归并排序 D. 快速排序 52 在下列排序方法中，( c )方法平均时间复杂度为0(nlogn)，
最坏情况下时间复杂度为0(n2)；( d )方法所有情况下时间复杂度均为0(nlogn)。 a. 插入排序 b. 希尔排序 c. 快速排序 d. 堆排序
53 已知一组待排序的记录关键字初始排列如下：56,26,86,35,75,19,77,58,48,42 下列选择中( d )是快速排序一趟排序的结果。( c )是希尔排序 (初始步长为3)一趟排序的结果。( a )是初始堆(大堆顶)。 A)86,75,77,58,42,19,56,35,48,26. B)26,56,35,75,19,77,58,48,42,86.
.
.
C)35,26,19,42,58,48,56,75,86,77. D)42,26,48,35,19,56,77,58,75,86.
三．填空题
1 数据结构通常有下列4类基本结构：集合、线性结构 、树型结构、图型结构。
2 设单链表中结点形式为 data next ，若单链表长度大于等于2，指针p指向表中某个结点且p->next非空，此时若要删除指针p所指的结点，可以通过如下方法进行：将p所指结点的后继的元素值复制到该结点，然后删除其后继结点。相应的语句序列为： p->data = p->next->data；p->next = p->next->next；free(p ->next)； ； 3 线性表的顺序存储结构是以数组下标来表示数据元素之间的逻辑关系的。
4 已知P是单链表中某一结点的指针，P既不是首元结点也不是尾元结点，Q是P 的 前驱 结点指针。当删除P结点时，链表的链接可用语句(q->next = p->next)实现。 5 已知某树的先根遍历次序为abcdefg后根遍历次序为cdebgfa。
若将该树转换为二叉树,其后序遍历次序为(edcgfba)。层次遍历次序为(abcfdge)。 6 已知某二叉树的先序遍历次序为afbcdeg中序遍历次序为cedbgfa。 其后序遍历次序为(edcgbfa)。层次遍历次序为(afbcgde)。
i-1
7 在二叉树的第i层上至少有1个结点, 至多有2个结点 ,
i
深度为k的二叉树至多有2-1个结点.
8 对树的遍历有先序遍历树和后序遍历树。若以二叉链表作树的存储结构, 则树的先序遍历可借用二叉树的先序遍历算法来实现, 而树的后序遍历可借用二叉树的中序遍历算法来实现。 9 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少 是2*h-1，至多是满树。
10 对任何一棵二叉树T,若其终端结点数为n0.度为2的结点为n2,则n0与n2的关系为 (n0=n2+1)。
11 如果对完全二叉树中结点从1开始按层进行编号，设最大编号为n；那么，可以断定编 号为i (i>1)的结点的父结点编号为(i/2向下取整)；所有编号(i>n/2)的结点为叶子结点。
12 n个顶点的连通图至少有n-1条边，至多有n(n-1)/2条边。
13 对于图的存储结构有(数组表示法)、(邻接表法)、(十字链表法)、(邻接多重表法)等方法。
14 在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是m/2条。
15 若有序表中关键字序列为：12，22，33，44，55，66，77，88，99对其进行折半查找， 则在等概率情况下，查找成功时的平均查找长度是(3)。查找99时需进行(2)次比较。 16 在哈希表中，处理冲突的方法有开放定址法，再哈希法，链地址法等。
i-1k
17 在二叉树的第i层上至少有1个结点, 至多有2个结点 ,深度为k的二叉树至多有2-1个结点.
18 对于一棵高度为K的二叉排序树，结点数最少可有 个，最多可有 个。 19 用中序遍历对二叉排序树进行访问可得到有序序列。
20 已知Hash函数为 H(K)=K mod 13 ，散列地址为0 --14，用二次探测再散列 处理冲突，关键字(23，34，56，24，75，12，49, 52，36，92)
的分布如图，则平均成功的查找长度为( )、平均失败的查找长度为( )。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
.
.
52 36 92 56 34 23 24 75 12 49 21 一棵ｍ阶的Ｂ-树，第一层至少有一个结点；第二层至少有2个结点， 除根之外的所有非终端结点至少有(┌ m/2 ┐)棵子树， 树中每个结点至多有( m )棵子树。
22 在哈希表中，处理冲突的方法有开放定址法，再哈希法，链地址法，建立一个公共溢出区。
23 哈希表的查找效率取决于(哈希函数是否均匀)(处理冲突的方法)和(哈希表的装填因子)。
24高度为4 (包含不带关键字的叶子结点层)的7阶B树最少有┌ m/2 ┐-1个关键字，
最多有m-1个关键字；如果其中的某结点正好有2个儿子，那么，该结点必定是 结点。
25 对n个元素的序列进行内部排序，若用起泡排序法，最少的比较次数是n-1，最多的比较次数是n(n-1)/2。
25 (算法填空)
Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e)) { //先序非递归遍历二叉树。
Initstack ( S ); Push ( S,T ); While ( !stackempty( S ) )
{ While ( gettop( S, p )&&p)
{ if (!Visit (p->data ) ) return ERROR; push(S,p->lchild) ; }
Pop ( S , p );
if (!StackEmpty(S))
{ Pop(s,p); push( S, p->rchild ); } }
return ok; }
26 (算法填空)
下列算法试图完成在数组A中搜索有无关键字key，若有，返回数组下标,若无，返回-1。在“ ”处填上合适的内容,完成该算法。
int BinarySearch (keytype A [], int low,int high, keytype key ) {
while (low <= high)
middle = (low+high) /2; if (A[middle] == key)
return middle; if (key < A[middle]) high = middle -1; else low = middle +1;
.