赞
踩
数据结构808真题回忆,en,不是全部,可以作为一个参考看看,欢迎指正。
1.算法是 ( ) 。
为了解决某一问题而规定的一个有限长的操作序列。
2.带头结点的单链表为空的判定条件是( )
A、head== NULL
B、 head->next== NULL
C、head->next==head
D、 head!=NULL
【B】
带头结点单链表判空:head->next==NULL
不带头结点单链表判空:head==NULL
带头结点循环链表判空:head->next==head
3.设散列表中有 m 个存储单元,散列函数 H(key)= key % p,则 p 最好选择( )。
A、 小于等于 m 的最大奇数
B、 小于等于 m 的最大素数
C、 小于等于 m 的最大偶数
D、 小于等于 m 的最大合数
【B】
--想起两个相关题目--
为了能有效地应用 HASH 查找技术,必须解决的两个问题是构造一个好的HASH函数和确定解决冲突的方法
散列表中解决冲突的两种方法是开放定址法和链地址法
4.下列排序算法中,平均时间复杂度为O(n^2)的排序算法有()
A、归并排序 B、堆排序 C、冒泡排序 D、快速排序
【C】
5.若串str=“Software”,其子串的个数是( )。
A、8 B、9 C、36 D、37
【D】
s=8+7+6+5+4+3+2+1+1=37
其中空串是任何字符串的子串
6.有XYZ 三个元素依次入栈,不可能的出栈顺序是()
A、ZYX B、ZXY C、YXZ D、XYZ
【B】
栈:是限定仅在表尾进行插入或者删除操作的线性表,又称为后进先去(List In First Out,LIFO)线性表。
7.已知串S=‘aaab’,其Next数组值为( )
A、0123 B、1123 C、1231 D、1211
[A]
8.设广义表L=((a,b,c)),则L的长度和深度分别为()
A、 1和1 B、1和3 C、1和2 D、2和3
【C】
广义表长度=所含数据元素个数(这里数据元素可能是原子or广义表)
广义表深度=数左(右)边括号,括号的最大层次
9.(类似)以下关于顺序存储结构的叙述中,( )是正确的。
A、每个结点中至少包含一个指针域
B、存储密度大
C、可用于栈、队列、树等逻辑结构的存储表示
D、便于插入、删除运算操作
【B】 顺序表和链表的区别 1.存储上: 顺序表:顺序表在内存上是连续的 链表:链表在内存上是不连续的。 2.实现方式上: 顺序表:顺序表是通过数组来实现的, 链表:由于链表的内存不连续特性,我们只能借助节点来实现。 3.存储密度上: 顺序表:顺序表它开辟一块内存就实实在在的存了一个元素,要是用多少开辟多少空间的话,顺序表的存储密度就是百分之百。 链表:因为链表中有两个参数,存储元素用了一半,next引用占了一半,所以链表的存储密度只能达到百分之五十。 4.进行基本操作(增删改查)时: a)查找元素时: 顺序表:基于它的随机访问数据特性,查找元素时时间复杂度O(1)。 链表:不能随机访问数据,查找元素时的时间复杂度是O(N)。 b)删除和增加元素的时候: 顺序表:由于它原来的顺序结构不能变化,所以不管是删除还是插入元素,都要进行元素的搬运,时间复杂度是O(N)。 链表:因为有next引用,要想插入或者删除元素只需要改变引用之间的指向即可,时间复杂度是O(1).注意:链表虽然插入或者删除的时候时间复杂度是O(1),这里指的是我们在已知要插入位置的时候。倘若我们不知道要插入的位置,还是要先进行遍历,这里也是有一个O(N)的时间复杂度。
10逻辑结构包括()两大类。
线性结构和非线性结构
11.(类似)设在一棵度数为 3 的树中,度数为 3 的结点数有 2 个,度数为 2 的结点数有 1 个,度数为 1 的结点数有 2 个,那么度数为 0 的结点数有( )个。
A、 4 B、 5 C、 6 D、 7
【C】
其他4道也是普通的基础题。
1.数据类型和抽象数据类型定义,抽象数据类型的好处。
答:
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型是一般由用户定义的,表示应用问题的数据模型以及定义在这个模型上的一组操作的总称。
具体包括三个部分,数据对象、数据对象上关系的集合以及数据对象的基本操作的集合。
抽象数据类型的好处:抽象数据类型的定义仅取决于它的逻辑特性,而与其计算机内部如何表示和实现无关。
无论其内部结构如何变化,只要它的数学特性不变就不影响它的外部使用。
2.在递归计算斐波那契数列 Fn(即下列式 Fi b(n))时需对较小的 F(n-1)、F(n-2)……F(1)、F(0)分别精确计算多少次?(写出计算步骤)
Long Fib (long n )
{
If ( ( n = = 1 ) || ( n = = 0 ) ) return 1;
else return Fib (n-1) + Fib (n-2);
}
我表述的不太清楚,百度了一个答案
3.递归定义,递归的优缺点,递归需要借助什么实现?
答:一个函数在结束本函数之前,直接或间接调用函数自身,称为递归。
递归程序的优点是程序结构简单、清晰,易证明其正确性。缺点是执行中占内存空间较多,运行效率低。
递归程序执行中需要借助栈这种数据结构来实现
4.删除单链表中p直接后继结点代码。
status ListDelete(linklist &p){
if(p->nest==null) return 0;
linklist q;
q=p->nest;
p->nest=q->nest;
delete q;
return 1;
}
5.如果以行序为主序将A的非零元素存储在一维数组B[n]中,A为下三角矩阵,那么A的第i行第j列的非零元素aij(i≥j)在数组B中的下标,分析过程加答案。
6.树、森林和二叉树是三种不同的数据结构,将树,森林转化为二叉树的目的是什么?
答:树的孩子兄弟链表表示法和二叉树二叉链表表示法本质是一样的,只是解释不同。
树是森林的特例,即森林中只有一棵树的特殊情况。
树可用二叉树唯一表示,并可使用二叉树的一些算法去解决树和森林中的问题,简化问题的处理和提高效率。
7.算数表达式转二叉树,画图。
8.利用广义表 ls 取表头 head(ls)和取表尾 tail(ls)的基本运算,将原子 d 从广义表中分解出来,写每一步运算结果L = ( ( a , ( b) ) , ( ( c , d ) ) , ( e , f ) )
答:
tail(ls)=(((c,d)),(e.f))
head(tail(ls))=((c,d))
head(head(tail(ls)))=(c,d)
tail(head(head(tail(ls))))=(d)
head(tail(head(head(tail(ls)))))=d
9.有一个输入数据的序列是{46,25,78,62,12,80}
①画出从空树起,逐个输入各个数据而生成的二叉查找树(每增加一个记录画一幅画)
②计算该二叉查找树查找成功时的平均查找长度
答:
(1)
(2)ASL成功=(1+2*2+3*3)/6=7/3
答:
深度优先生成树:1-2-3-4-5
广度优先生成树:1-2-3-4-5
1.设计将序列中s到t的奇数移到所有偶数之前的算法。代码填空
void quickpass(int r[], int s, int t)
{
int i=s,j=t,x=r[s];
while(i<j)
{
while ①(i<j && r[j]%2==0) j=j-1;
if ②(i<j) {r[i]=r[j];i=i+1;}
while (i<j && r[i]%2==1) i=i+1;
if (i<j) {③r[j]=r[i];j=j-1;}
}
④r[i]=x;
}
2.递归建立二叉树(类似思路代码),代码填空。
typedef struct tree { char date; struct tree *left_leaf; ①struct tree *right_leaf; }tree,*BiTree; void creat_tree(BiTree *T)//创建树 { char val; scanf("%c",&val); //getchar(); if(val=='#') { ②*T=NULL; } else { *T=③(BiTree)malloc(sizeof(tree)); (*T)->date=val; ④ creat_tree(&(*T)->left_leaf); creat_tree(&(*T)->right_leaf); } }
3.根据给出的代码回答问题。
int searchnum(int number[],int n) { if(n>=1) { if(searchnum(number, n-1)>number[n]) return searchnum(number, n-1); else return number[n]; } else return number[0]; }int main(){ int a[9]={9,8,7,6,5,4,3,21,2}; int number=searchnum(a, 8); printf("%d\t",number); }
(1)searchnum函数实现的功能,主函数得出的结果。
(2)searchnum函数的时间复杂度,空间复杂度。
答:
(1) searchnum函数实现的功能为在给定是数组中找到最大值并返回。
主函数得出的结果为21。
(2)searchnum函数的时间复杂度为O(n),函数需调用递归n次。
间复杂度O(n),函数调用深度为n。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。