单选题
2-1适用于折半查找的表的存储方式及元素排列要求为(D) 。
A.链接方式存储，元素无序
B.链接方式存储，元素有序
C.顺序方式存储，元素无序
D.顺序方式存储，元素有序
2-2在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为(B)。
A.5 B.4 C.3 D.6
2-3分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是(C)。
A.（100，80， 90， 60， 120，110，130）
B.（100，120，110，130，80， 60， 90）
C.（100，60， 80， 90， 120，110，130）
D.（100，80， 60， 90， 120，130，110）
2-4设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（D）个记录。
A.1 B.2 C.3 D.4
2-5设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是(D)
A.8 B.3 C.5 D.9
2-6假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行（D）次探测。
A.(k-1)/2 B.k/2 C.k(k+1)/2 D.k(k-1)/2
2-7在散列存储中，装填因子α的值越大，则(A)。
A.存取元素时发生冲突的可能性就越大
B.存取元素时发生冲突的可能性就越小
C.存取元素时不可能发生冲突
D.毫无影响
2-8设有一组关键字{9,1,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=12,22,32,…,)解决冲突。计算查找成功的平均查找长度为（B）。
A.13/6 B.15/8 C.17/8 D.17/6
2-9选取哈希函数Ｈ（key）=key mod 7,用链地址法解决冲突。试在０-６的散列地址空间内对关键字序列｛31,23,17,27,19,11,13,91,61,41｝构造哈希表，并计算在等概率下成功查找的平均查找长度。（A）
A.15/10 B.15/8 C.17/10 D.15/6
2-10输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），按次序构造一棵二叉排序树BS为（A）。
A.
B.
C.
D.
2-11对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为
（1） 84 47 25 15 21 （2） 15 47 25 84 21
（3） 15 21 25 84 47 （4） 15 21 25 47 84
则采用的排序是 (A)。
A.选择 B.冒泡 C.快速 D.插入
2-12快速排序方法在（D）情况下最不利于发挥其长处。
A.要排序的数据量太大
B.要排序的数据中含有多个相同值
C.要排序的数据个数为奇数
D.要排序的数据已基本有序
2-13下列四个序列中，哪一个是堆（C）。
A.75,65,30,15,25,45,20,10
B.75,65,45,10,30,25,20,15
C.75,45,65,30,15,25,20,10
D.75,45,65,10,25,30,20,15
2-14有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为 （C）
A.-1，4，8，9，20，7，15，7
B.-1，7，15，7，4，8，20，9
C.-1，4，7，8，20，15，7，9
D.A，B，C均不对
2-15堆是一种(B)排序。
A.插入 B.选择 C.交换 D.归并
2-16数据表中有10000个元素,如果仅要求求出其中最大的10个元素,则采用(D)算法最节省时间。
A.冒泡排序 B.快速排序 C.简单选择排序 D.堆排序
2-17下列排序算法中, (C)排序在一趟结束后不一定能选出一个元素放在其最终位置上。
A.选择 B.冒泡 C.归并 D.堆
2-18下列排序算法中，在待排序数据已有序时，花费时间反而最多的是(B)排序。
A.冒泡 B.希尔 C.快速 D.堆
2-19若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行 （C）次比较。
A.3 B.10 C.15 D.25
2-20已知N元整型数组a存放N个学生的成绩，已按由大到小排序，以下算法是用对分（折半）查找方法统计成绩大于或等于X分的学生人数，请填空使之完善。（C）
#define N 10/*学生人数*/
int uprx(int a[],int x ) /*函数返回大于等于X分的学生人数*/
{
int head=1,mid,rear=N;
do {
mid=(head+rear)/2;
if(x==a[mid]) return mid;
if(x>a[mid]) { (1); } else{ (2) ; }
}while( (3) );
if (a[head]<x){ return head-1;}
return head;
}
A.(1)rear=mid (2)head=mid (3)head<rear
B.(1)head=mid+1 (2)rear=mid-1 (3)head==rear
C.(1)rear=mid-1 (2)head=mid+1 (3)head<rear
D.(1)rear=mid-1 (2)head=mid+1 (3)head==rear
函数题
6-1 数据结构考题 - 折半查找
建立一个递增的有序表（用顺序表作存储结构），用折半查找的方法对其实施查找。
顺序表的类型描述：
#define MAXSIZE 50 typedef int ElemType; typedef struct { ElemType *R; int length; }SSTable;函数接口定义：
下面给出了 折半查找 函数的大部分内容，但缺少了一部分（以下划线
____标识出来的部分）。请先将以下代码中画横线的部分补充完整，然后将完整的函数
Search_Bin提交系统，完成题目要求的功能。int Search_Bin(SSTable T, ElemType k) { int low,high,mid; low=1; high=T.length; while ( ____ ) { mid=____ ; if ( ____) return mid; else if (k< T.R[mid]) high=____; else low=____; } return 0 ; }该函数中的参数说明：
ElemType k要搜索的值顺序表中第一个数据元素存储在
T.R[1]测试主程序样例：
int main () { SSTable T; ElemType k; Create(T); cin>>k; int pos=Search_Bin(T,k); if(pos==0) cout<<"NOT FOUND"<<endl; else cout<<pos<<endl; return 0; }输入格式:
第一行输入一个整数n，表示顺序表的元素个数。
第二行从小到大输入n个数字，依次为表内元素值。
第三行输入一个要查找的值。文章来源：https://www.toymoban.com/news/detail-758367.html
输出格式:
输出这个值在表中的位置。如果没有找到，输出NOT FOUND。文章来源地址https://www.toymoban.com/news/detail-758367.html
输入样例:
5 2 4 6 8 10 6输出样例:
3输入样例2:
5 2 4 6 8 10 18输出样例2:
NOT FOUND参考答案：
int Search_Bin(SSTable T, ElemType k) { int low,high,mid; low=1; high=T.length; while (low<=high) { mid=(low+high)/2 ; if (T.R[mid]==k) return mid; else if (k<T.R[mid]) high=mid-1; else low=mid+1; } return 0 ; }
6-2 数据结构考题 - 顺序查找
建立一个顺序表，用顺序查找的方法对其实施查找。
顺序表的类型描述：
#define MAXSIZE 50 typedef int ElemType; typedef struct { ElemType *R; int length; } SSTable;函数接口定义：
下面给出了 顺序查找 函数的大部分内容，但缺少了一部分（以下划线
____标识出来的部分）。请先将以下代码中画横线的部分补充完整，然后将完整的函数
Search_Seq提交系统，完成题目要求的功能。int Search_Seq (SSTable T,ElemType k) { int i; T.R[0]= ____ ; for ( i=____ ; T.R[ ____ ]!= k ; ____ ); return ____ ; }该函数中的参数说明：
ElemType k要搜索的值顺序表中第一个数据元素存储在
T.R[1]测试主程序样例：
int main () { SSTable T; ElemType k; Create(T); cin>>k; int pos=Search_Seq(T,k); if(pos==0) cout<<"NOT FOUND"<<endl; else cout<<pos<<endl; return 0; }输入格式:
第一行输入一个整数n，表示顺序表的元素个数。
第二行行输入n个数字，依次为表内元素值。
第三行输入一个要查找的值。
输出格式:
输出这个值在表中的位置。如果没有找到，输出NOT FOUND。
输入样例:
5 9 5 3 7 6 7输出样例:
4输入样例2:
5 9 5 3 7 6 8输出样例2:
NOT FOUND参考答案：
int Search_Seq (SSTable T,ElemType k) { int i; T.R[0]= k; for (i=T.length;T.R[i]!=k;i--); return i ; }
到了这里，关于数据结构第7~8章练习答案（PTA）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
