数据结构题库
单选题
略
函数题
- 顺序表的查找操作
int LocateElem(SqList L,ElemType e){
int sign = 0;
for(int i = 0; i < L.length; i++){
if(L.elem[i] == e){
sign = i + 1;
}
}
return sign;
}
- 顺序表的插入操作
6-4 顺序表的有序插入操作int ListInsert(SqList &L,int i,ElemType e){
if(i > L.length + 1 || i < 1 || L.length == MAXSIZE){
return 0;
}
for(int index = L.length; index >= i; index--){
L.elem[index] = L.elem[index - 1];
}
L.elem[i-1] = e;
L.length++;
return 1;
}
- 顺序表的删除操作
int ListDelete(SqList &L,int i){
if(i < 1 || i > L.length){
return 0;
}
for(int index = i-1; index < L.length; index++){
L.elem[index] = L.elem[index+1];
}
L.length--;
return 1;
}
- 顺序表的有序插入操作
int SqInsert(SqList &L,ElemType e){
if(L.length == MAXSIZE){
return 0;
}
int temp = 0;
for(int index = 0; index < L.length; index++){
if(e <= L.elem[index]){
temp = index;
break;
}
temp = L.length;
}
for(int index = L.length; index > temp; index--){
L.elem[index] = L.elem[index-1];
}
L.elem[temp] = e;
L.length++;
return 1;
}
- 求顺序表最大值
int GetMax(SqList L){
if(L.length == 0){
return 0;
}
int max = L.elem[0];
for(int i = 1; i < L.length; i++){
if(max < L.elem[i]){
max = L.elem[i];
}
}
return max;
}
- 求顺序表最小值
int GetMin(SqList L){
if(L.length == 0){
return 0;
}
int min = L.elem[0];
for(int i = 1; i < L.length; i++){
if(min > L.elem[i]){
min = L.elem[i];
}
}
return min;
}
- 顺序表统计大于指定元素值个数
int GetGreater(SqList L, ElemType e){
int count = 0;
for(int index = 0; index < L.length; index++){
if(L.elem[index] > e){
count++;
}
}
return count;
}
- 顺序表统计指定元素值个数
int GetCount(SqList L, ElemType e){
int count = 0;
for(int index = 0; index < L.length; index++){
if(L.elem[index] == e){
count++;
}
}
return count;
}
- 顺序表统计小于指定元素值个数
int GetSmaller(SqList L, ElemType e){
int count = 0;
for(int index = 0; index < L.length; index++){
if(L.elem[index] < e){
count++;
}
}
return count;
}
- 求单链表的表长
int Length ( LinkList L ){
int length = 0;
while(L->next != NULL){
L = L->next;
length++;
}
return length;
}
- 统计单链表元素出现次数
int GetCount ( LinkList L,ElemType e ){
int count = 0;
while(L->next != NULL){
L = L->next;
if(L->data == e){
count++;
}
}
return count;
}
- 单链表统计正数个数
int PositiveInt(LinkList L){
int count = 0;
while(L->next != NULL){
L = L->next;
if(L->data > 0){
count++;
}
}
return count;
}
- 单链表统计负数个数
int NegativeInt(LinkList L){
int count = 0;
while(L->next != NULL){
L = L->next;
if(L->data < 0){
count++;
}
}
return count;
}
- 单链表统计偶数个数
int EvenNumber(LinkList L){
int count = 0;
while(L->next != NULL){
L = L->next;
if(L->data % 2 == 0){
count++;
}
}
return count;
}
- 单链表统计奇数个数
int OddNumber(LinkList L){
int count = 0;
while(L->next != NULL){
L = L->next;
if(L->data % 2 != 0){
count++;
}
}
return count;
}
- 前缀表达式
void Prefix(BiTree T){
if(T == NULL){
return;
}
printf("%c ", T->data);
Prefix(T->lchild);
Prefix(T->rchild);
}
- 中缀表达式
void Infix(BiTree T){
if(T == NULL){
return;
}
Infix(T->lchild);
printf("%c ", T->data);
Infix(T->rchild);
}
- 后缀表达式
void Suffix(BiTree T){
if(T == NULL){
return;
}
Suffix(T->lchild);
Suffix(T->rchild);
printf("%c ", T->data);
}
- 单链表元素最大值以及结点数
void Count_max (LinkList L ){
int maxNum = 0, count = 0;
if(L == NULL || L->next == NULL){
printf("%d %d", maxNum, count);
return;
}
maxNum = L->next->data;
while(L->next != NULL){
L = L->next;
count++;
if(maxNum < L->data){
maxNum = L->data;
}
}
printf("%d %d", maxNum, count);
}
- 单链表元素最小值以及结点数
void Count_min (LinkList L ){
int count = 0, minNum = 0;
if(L->next == NULL){
printf("%d %d", minNum, count);
return;
}
minNum = L->next->data;
while(L->next != NULL){
L = L->next;
count++;
if(minNum > L->data){
minNum = L->data;
}
}
printf("%d %d", minNum, count);
}
- 中序输出运算式中的运算符,并返回运算符的个数
int count = 0;
int Infix_num(BiTree T){
if(T == NULL){
return;
}
Infix_num(T->lchild);
if(T->data >= 33 && T->data <= 47){
printf("%c ", T->data);
count++;
}
Infix_num(T->rchild);
return count;
}
- 统计二叉树叶子结点个数
int count = 0;
int LeafCount ( BiTree T){
if(T == NULL){
return;
}
if(T->lchild == NULL && T->rchild == NULL){
count++;
}
LeafCount(T->lchild);
LeafCount(T->rchild);
return count;
}
- 统计二叉树度为1的结点个数
int count = 0;
int NodeCount ( BiTree T){
if(T == NULL){
return;
}
if((!T->lchild && T->rchild) || (T->lchild && !T->rchild)){
count++;
}
NodeCount(T->lchild);
NodeCount(T->rchild);
return count;
}
- 统计二叉树度为2的结点个数
int count = 0;
int NodeCount ( BiTree T){
if(T == NULL){
return;
}
if(T->lchild != NULL && T->rchild != NULL){
count++;
}
NodeCount(T->lchild);
NodeCount(T->rchild);
return count;
}
主观题
- 哈夫曼树的构建
假设用于通信的电文仅由8个字母组成,字母在电文中出现的频率分别为0.09,0.16,0.02,0.06,0.32,0.03,0.21,0.11。
- 试为这8个字母设计哈夫曼编码,请写出哈夫曼树的构建详细过程和编码;(4分)
- 设计另一种由二进制表示的等长编码方案;(2分)
- 对于上述实例,分析两种方案的编码长度,分析两种方案的优缺点(3分)
wpl = 21 * 2 + 32 * 2 + 9 * 3 + 11 * 3 + 16 * 3 + 6 * 4 + 2 * 5 + 3 * 5
- 二叉排序树的构造
已知一组数据元素为(18,3,34,25,12,29,15)
- 试从空树开始画出按元素排列顺序输入而生成的一棵二叉排序树;
- 计算查找概率相同情况下,查找成功的平均查找长度。
wpl = 1 * 1 + 2 * 2 + 2 * 3 + 2 * 4
- 哈希表的构造
已知哈希函数为:H(k)=k%11,表长为11,采用线性探测再散列解决冲突,对下列关键字序列{43,88,27,11,10,23}
- 构造哈希表;
- 求出等概率下查找成功时的平均查找长度。
wpl = 1 * 3 + 2 + 3 + 4