数据结构常见笔试题Word文件下载.docx
《数据结构常见笔试题Word文件下载.docx》由会员分享，可在线阅读，更多相关《数据结构常见笔试题Word文件下载.docx（18页珍藏版）》请在冰点文库上搜索。
11.数据的逻辑结构是指（反映数据元素之间逻辑关系的数据结构）
12.根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为（线性结构和非线性结构）
13.下列数据结构具有记忆功能的是（C）
A．队列B．循环队列C．栈D．顺序表
14.递归算法一般需要利用（栈）实现。
15.由两个栈共享一个存储空间的好处是（节省存储空间，降低上溢发生的机率）
16.与单向链表相比，双向链表的优点之一是（更容易访问相邻结点）
17.设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为（350）说明：
完全二叉树总结点数为N，若N为奇数，则叶子结点数为（N+1）/2；
若N为偶数，则叶子结点数为N/2。
18.串的长度是（串中所含字符的个数）
19.设有两个串p和q，求q在p中首次出现位置的运算称做（模式匹配）
20.N个顶点的连通图中边的条数至少为（N-1）
21.N个顶点的强连通图的边数至少有（N）
22.对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为（n）
23.最简单的交换排序方法是（冒泡排序）
24.假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为（n（n-1）/2）
25.在待排序的元素序列基本有序的前提下，效率最高的排序方法是（冒泡排序）
26.希尔排序法属于（插入类排序）
27.堆排序法属于（选择类排序）
28.已知数据表A中每个元素距其最终位置不远，为节省时间，应采用（直接插入排序）
29.算法的基本特征是有穷性、可行性、确定性和拥有足够的情报。
第三部分
1.一个算法通常由两种基本要素组成：
一是对数据对象的运算和操作，二是算法的控制结构。
2.所谓数据处理是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。
3.数据结构是指相互有关联的数据元素的集合。
4.数据结构分为逻辑结构与存储结构，线性链表属于（存储结构）。
5.数据元素之间的任何关系都可以用前驱和后继关系来描述。
6.数据的逻辑结构有线性结构和非线性结构两大类。
7.常用的存储结构有顺序、、索引等存储结构。
8.栈的基本运算有三种：
入栈、退栈与读栈顶元素。
9.队列主要有两种基本运算：
入队运算与退队运算。
10.在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。
11.栈和队列通常采用的存储结构是链式存储和顺序存储。
12.循环队列主要有两种基本运算：
每进行一次入队运算，队尾指针就进1。
13.当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。
这种情况称为上溢。
14.当循环队列为空时，不能进行退队运算，这种情况称为下溢。
15.在一个容量为25的循环队列中，若头指针front=16，尾指针rear=9，则该循环队列中共有18个元素。
注：
当rear<
front时，元素个数＝总容量－（front－rear）；
当rear>
front时，元素个数＝rear－front。
第四部分
1、链表反转（无表头结点）
单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。
比如一个链表是这样的：
1->
2->
3->
4->
5通过反转后成为5->
1。
最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。
源代码如下：
法一：
typedefstructLNode
{
intdata;
LNode*next;
}LNode,*LinkList;
voidReverse（LinkList&
head）
if（head==NULL）
return;
}
还有一种利用递归的方法。
这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点。
不过，这个方法有一个缺点，就是在反转后的最后一个结点会形成一个环，所以必须将函数返回的节点的next域置为NULL。
因为要改变head指针，所以我用了引用。
算法的源代码如下：
法二：
LNode*Reverse（LNode*p,LinkList&
if（p==NULL||p->
next==NULL）
head=p;
returnp;
else
LNode*tmp=Reverse（p->
next,head）;
tmp->
next=p;
p->
next=NULL;
2.判断一个链表是否存在环，例如下面这个链表就存在一个环：
例如N1->
N2->
N3->
N4->
N5->
N2就是一个有环的链表，环的开始结点是N5这里有一个比较简单的解法。
设置两个指针p1，p2。
每次循环p1向前走一步，p2向前走两步。
直到p2碰到NULL指针或者两个指针相等结束循环。
如果两个指针相等则说明存在环。
求环长：
按照上面两个指针不同步长步进的方法，第一次相遇时记录当前指针，步长为1的指针继续走，计数，直到再次来到记录的指针，经过的步数即为环长。
找环入口：
根据所得环长Y，设置指针指向头部，另一指针先向前走Y。
若两指针当前指向的node相同，则为入口，否则各自向前走1再判断是否相等。
structNode
Node*next;
};
boolIsLoop（Node*head）
Node*p1=head,*p2=head;
if（head==NULL||head->
returnfalse;
do
p1=p1->
next;
p2=p2->
next->
}while（p2&
&
p2->
next&
p1!
=p2）;
if（p1==p2）
returntrue;
3.判断两个数组中是否存在相同的数字：
给定两个排好序的数组，怎样高效地判断这两个数组中存在相同的数字？
这个问题首先想到的是一个O（nlogn）的算法。
就是任意挑选一个数组，遍历这个数组的所有元素，遍历过程中，在另一个数组中对第一个数组中的每个元素进行binarysearch。
用C++实现代码如下：
boolFindCommon（inta[],intsize1,intb[],intsize2）
inti;
for（i=0;
i<
size1;
i++）
intstart=0,end=size2-1,mid;
while（start<
=end）
mid=（start+end）/2;
if（a[i]==b[mid]）
elseif（a[i]<
b[mid]）
end=mid-1;
start=mid+1;
后来发现有一个O（n）算法。
因为两个数组都是排好序的。
所以只要一次遍历就行了。
首先设两个下标，分别初始化为两个数组的起始地址，依次向前推进。
推进的规则是比较两个数组中的数字，小的那个数组的下标向前推进一步，直到任何一个数组的下标到达数组末尾时，如果这时还没碰到相同的数字，说明数组中没有相同的数字。
boolFindCommon2（inta[],intsize1,intb[],intsize2）
inti=0,j=0;
while（i<
size1&
j<
size2）
if（a[i]==b[j]）
if（a[i]>
b[j]）
j++;
if（a[i]<
i++;
4.“最大子序列”问题：
给定一整数序列A1，A2，...,An（可能有负数），求A1~An的一个子序列Ai~Aj，使得Ai到Aj的和最大。
例如：
整数序列-2,11,-4,13,-5,2,-5,-3,12,-9的最大子序列的和为21。
对于这个问题，最简单也是最容易想到的那就是穷举所有子序列的方法。
利用三重循环，依次求出所有子序列的和然后取最大的那个。
当然算法复杂度会达到O（n^3）。
显然这种方法不是最优的，下面给出一个算法复杂度为O（n）的线性算法实现，算法的来源于ProgrammingPearls一书。
在给出线性算法之前，先来看一个对穷举算法进行优化的算法，它的算法复杂度为O（n^2）。
其实这个算法只是对穷举算法稍微做了一些修改：
其实子序列的和我们并不需要每次都重新计算一遍。
假设Sum（i,j）是A[i]...A[j]的和，那么Sum（i,j+1）=Sum（i,j）+A[j+1]。
利用这一个递推，我们就可以得到下面这个算法：
intMaxSub（inta[],intsize）
inti,j,v,max=a[0];
size;
v=0;
for（j=i;
j++）
v=v+a[j];
//Sum（i,j+1）=Sum（i,j）+A[j+1]
if（v>
max）
max=v;
returnmax;
那怎样才能达到线性复杂度呢？
这里运用动态规划的思想。
先看一下源代码实现：
intMaxSub2（inta[],intsize）
inti,max=0,tempSum=0;
tempSum+=a[i];
if（tempSum>
max=tempSum;
elseif（tempSum<
0）
tempSum=0;
5.按单词反转字符串,并不是简单的字符串反转，而是按给定字符串里的单词将字符串倒转过来，就是说字符串里面的单词还是保持原来的顺序，这里的每个单词用空格分开。
Hereis
经过反转后变为：
isHere
如果只是简单的将所有字符串翻转的话，可以遍历字符串，将第一个字符和最后一个交换，第二个和倒数第二个交换，依次循环。
其实按照单词反转的话可以在第一遍遍历的基础上，再遍历一遍字符串，对每一个单词再反转一次。
这样每个单词又恢复了原来的顺序。
char*ReverseWord（constchar*str）
intlen=strlen（str）;
char*reStr=newchar[len+1];
strcpy（reStr,str）;
inti,j;
for（i=0,j=len-1;
j;
i++,j--）
chartemp=reStr[i];
reStr[i]=reStr[j];
reStr[j]=temp;
intk=0;
while（k<
len）
i=j=k;
while（reStr[j]!
='
'
&
reStr[j]!
\0'
）
k=j+1;
j--;
for（;
i<
returnreStr;
如果考虑空间和时间的优化的话，当然可以将上面代码里两个字符串交换部分改为异或实现。
例如将
改为
reStr[i]^=reStr[j];
reStr[j]^=reStr[i];
6.字符串反转。
我没有记错的话是一道MSN的笔试题，网上无意中看到的，拿来做了一下。
题目是这样的，给定一个字符串，一个这个字符串的子串，将第一个字符串反转，但保留子串的顺序不变。
输入：
第一个字符串:
"
Thisisfishsky'
sChinesesite:
子串:
fishsky"
输出：
nc/nc.moc.fishsky.//:
ptth:
etisesenihCs'
fishskysisihT"
一般的方法是先扫描一边第一个字符串，然后用stack把它反转，同时记录下子串出现的位置。
然后再扫描一遍把记录下来的子串再用stack反转。
我用的方法是用一遍扫描数组的方法。
扫描中如果发现子串，就将子串倒过来压入堆栈。
最后再将堆栈里的字符弹出，这样子串又恢复了原来的顺序。
#include<
iostream>
cassert>
stack>
usingnamespacestd;
//reversethestring'
s1'
exceptthesubstring'
token'
.
constchar*reverse（constchar*s1,constchar*token）
assert（s1&
token）;
stack<
char>
cStack;
constchar*pToken=token,*head=s1,*rear=s1;
while（*head!
while（*head!
*pToken==*head）
ptoken++;
head++;
if（*pToken=='
）//containthetoken
constchar*p;
for（p=head-1;
p>
=rear;
p--）
cStack.push（*p）;
pToken=token;
rear=head;
cStack.push（*rear）;
head=++rear;
char*pszRetValue=newchar[strlen（s1）+1];
inti=0;
while（!
cStack.empty（））
pszRetValue[i++]=cStack.top（）;
cStack.pop（）;
pszRetValue[i]='
;
returnpszRetValue;
intmain（intargc,char*argv[]）
cout<
<
reverse（"
"
）;
return0;
7.删除数组中重复的数字：
一个动态长度可变的数字序列，以数字0为结束标志，要求将重复的数字用一个数字代替，例如：
将数组1,1,1,2,2,2,2,2,7,7,1,5,5,5,0转变成1,2,7,1,5,0问题比较简单，要注意的是这个数组是动态的。
所以避免麻烦我还是用了STL的vector。
vector>
//removetheduplicatednumbersinanintgerarray,thearraywasendwith0;
//e.g.1,1,1,2,2,5,4,4,4,4,1,0--->
1,2,5,4,1,0
voidstaticremove_duplicated（inta[],vector<
int>
_st）
_st.push_back（a[0]）;
for（inti=1;
_st[_st.size（）-1]!
=0;
if（a[i-1]!
=a[i]）
_st.push_back（a[i]）;
当然如果可以改变原来的数组的话，可以不用STL，仅需要指针操作就可以了。
下面这个程序将修改原来数组的容。
voidstaticremove_duplicated2（inta[]）
if（a[0]==0||a==NULL）
intinsert=1,current=1;
while（a[current]!
=0）
if（a[current]!
=a[current-1]）
a[insert]=a[current];
insert++;
current++;
a[insert]=0;
8.判断一个二叉排序树是否是平衡二叉树。
解决方案：
根据平衡二叉树的定义，如果任意节点的左右子树的深度相差不超过1，那这棵树就是平衡二叉树。
首先编写一个计算二叉树深度的函数，利用递归实现。
template<
typenameT>
staticintDepth（BSTreeNode<
T>
*pbs）
if（pbs==NULL）
intld=Depth（pbs->
left）;
intrd=Depth（pbs->
right）;
return1+（ld>
rd?
ld:
rd）;
下面是利用递归判断左右子树的深度是否相差1来判断是否是平衡二叉树的函数：
staticboolisBalance（BSTreeNode<
intdis=Depth（pbs->
left）-Depth（pbs->
if（dis>
1||dis<
-1）
returnisBalance（pbs->
left）&
isBalance（pbs->
升级会员 