37 下列查找方法中（ a ）适用于查找单链表。
A）顺序查找 B）折半查找 C）分块查找 D）hash查找
38 下列算法中（c 普利姆算法）适用于求图的最小代价生成树。（ b ）能对图作广度优先遍历。
A）DFS算法 B）BFS算法 C）Prim算法 D）Dijkstra算法
39 关键路径是指在只有一个源点和一个汇点的有向无环网中源点至汇点（ c ）的路径。 a:弧的数目最多 b:弧的数目最少 c:权值之和最大 d:权值之和最小 40 希表的查找效率取决于（ d ）。
a: 哈希函数 b:处理冲突的方法。 c:哈希表的装填因子。 d:以上都是 41 在Hash函数H(k)=k MOD m中，一般来说，m应取( c )。 A. 奇数 B. 偶数 C. 素数 D. 充分大的数
42 在顺序表查找中，为避免查找过程中每一步都检测整个表是否查找完毕， 可采用 a 方法。
A.设置监视哨 B.链表存贮 C.二分查找 D.快速查找 43 静态查找表和动态查找表的区别在于( b )。 A. 前者是顺序存储，而后者是链式存储
B. 前者只能进行查找操作，而后者可进行查找、插入和删除操作 C. 前者只能顺序查找，而后者只能折半查找 D. 前者可被排序，而后者不能被排序
44 在一个含有n个元素的有序表上进行折半查找，找到一个元素最多要进行( b )次元素 比较。
A．?log2(n)? B. ?log2(n)?+1 C. ?log2(n+1)? D. ?log2(n+1)?+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，采用线性探测再散列处理冲突指加数为1。
若依次将数据序列：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->netx = p->next ）实现。
5 已知某树的先根遍历次序为abcdefg后根遍历次序为cdebgfa。 若将该树转换为二叉树,其后序遍历次序为（ ）。层次遍历次序为（ ）。 6 已知某二叉树的先序遍历次序为afbcdeg后序遍历次序为cedbgfa。 其后序遍历次序为（ ）。层次遍历次序为（ ）。 7 在二叉树的第i层上至少有_____1____个结点, 至多有___2___个结点 , 深度为k的二叉树至多有_2__-1_______个结点.
i
i-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*(n-1)/2条边，此时即是完全图 条边。
13 对于图的存储结构有（ 数组表示法 ）、（ 邻接表法 ）( 十字链表法 ) ( 邻接多重表法 )等方法。 14 在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是____m/2________条。 15 若有序表中关键字序列为：12，22，33，44，55，66，77，88，99对其进行折半查找， 则在等概率情况下，查找成功时的平均查找长度是（ ）。查找99时需进行（ ）次比 较。
16 在哈希表中，处理冲突的方法有开放定址法， 再哈希表法 ， 链地址法 等。
17 在二叉树的第i层上至少有_____个结点, 至多有_____个结点 ,深度为k的二叉树至多有 个结点.
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个结点， 除根之外的所有非终端结点至少有（ ）棵子树， 树中每个结点至多有（ ）棵子树。
22 在哈希表中，处理冲突的方法有开放定址法， ， , 。
23 哈希表的查找效率取决于（ ① 哈希函数是否均匀； ② 处理冲突的方法；
③ 哈希表的装填因子 ）。
24高度为4 (包含不带关键字的叶子结点层)的7?阶?B?树最少有 个关键字，最多 有_________个关键字；如果其中的某结点正好有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 ; }
return -1;
} //end of BinarySearch
27 (算法填空)
下列函数为堆排序中的堆调整过程（调整H.r[s]的关键字，使H.r[s..m]成为一小顶堆）。请在“ ”处填上合适的内容,完成该算法。 Void heapadjust( heaptype @ H , int s , int m ) { rc=H.r[s];
for (j=2*s;j<=m;j*=2) {
if (j
H.R[s] = rc ; }//heapadjust
图示结构题
1 已知在电文中只出现频率为 ( 5,26,7,23,20,19 )的６个字符， 画出你建的哈夫曼树，并给出其哈夫曼编码。
2.已知某二叉树的后序遍历和中序遍历次序分别为DBFGECA和BDACFEG
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库必看!!!!!数据结构期末复习题及部分答案解析(2)在线全文阅读。
相关推荐：