- 相关推荐
数据结构试题及答案
导语：数据结构考试会主要考倒什么呢。考生们不妨看看。以下是小编搜集并整理的有关内容，希望对大家有所帮助!
一、单项选择题
1、连续存储设计时，存储单元的地址( )。
A、一定连续
B、一定不连续
C、不一定连续
D、部分连续，部分不连续
2、以下属于逻辑结构的是( )。
A、顺序表
B、 哈希表
C、有序表
D、 单链表
3、 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。
A、 BA+141
B、 BA+180
C、 BA+222
D、 BA+225
4、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用( )存储方式最节省时间。
A、顺序表
B、双链表
C、带头结点的双循环链表
D、单循环链表
5、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用( )存储方式最节省运算时间。
A、单链表
B、仅有头指针的单循环链表
C、双链表
D、仅有尾指针的单循环链表
6、线性表( a1,a2,…,an)以链接方式存储时，访问第i位置元素的时间复杂性为( )。
A、O(i)
B、O(1)
C、O(n)
D、O(i-1)
7、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是( )。
A、head==NULL
B、head→next==NULL
C、head→next==head
D、head!=NULL
8、 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是( )。
A、 i
B、 n-i
C、 n-i+1
D、 不确定
9、 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列?( )。
A、 5 4 3 6 1 2
B、 4 5 3 1 2 6
C、 3 4 6 5 2 1
D、 2 3 4 1 5 6
10、 散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的( )方法是散列文件的关键。
A、 散列函数
B、 除余法中的质数
C、 冲突处理
D、 散列函数和冲突处理
二、填空题
1、数据的物理结构包括 的表示和 的表示。
2、数据结构中评价算法的两个重要指标是 。
3、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。
4、线性表L=(a1,a2,…,an)用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。
5、在一个长度为n的顺序表中第i个元素(1<=i<=n)之前插入一个元素时，需向后移动________个元素。
6、链接存储的特点是利用________来表示数据元素之间的逻辑关系。
7、 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______。
8、区分循环队列的满与空，只有两种方法，它们是______和______。
三、判断题
1、算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。( )
2、 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。( )
3、 稀疏矩阵压缩存储后，必会失去随机存取功能。( )
4、 数组是同类型值的集合。( )
5、 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。( )
6、 稀疏矩阵压缩存储后，必会失去随机存取功能。( )
7、 二维以上的数组其实是一种特殊的广义表。( )
8、 文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。( )
三、解答题
1、 数据结构是一门研究什么内容的学科?
2、数据元素之间的关系在计算机中有几种表示方法?各有什么特点?
3、 有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈(即C第一个且D第二个出栈)的次序有哪几个?
四、程序阅读题
1、请阅读以下程序，写出此程序所要完成的功能，及时间复杂度。
int compare( SqList A, SqList B )
{ j=0;
while ( j
if ( A、elem[j] < B、elem[j] ) return(-1);
else if ( A、elem[j] > B、elem[j] ) return(1);
else j++;
if ( A、length == B、length ) return (0);
else if ( A、length < B、length ) return(-1);
else return(1);
}
2、将二叉树bt中每一个结点的左右子树互换的C语言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队，出队和判别队列是否为空的函数，请填写算法中得空白处，完成其功能。
typedef struct node
{int data ; struct node *lchild, *rchild; }btnode;
void EXCHANGE(btnode *bt)
{btnode *p, *q;
if (bt){ADDQ(Q,bt);
while(!EMPTY(Q))
{p=DELQ(Q); q=(1)_; p->rchild=(2)___; (3)___=q;
if(p->lchild) (4)___; if(p->rchild) (5)___;
}
}
}
五、算法设计题
1、写出广度优先搜索遍历的遍历算法。
数据结构模拟试题1参考答案
一、选择题(20分)
1-5 A B C A C
6-10 D D C B B
二、填空题(20分)
l、(n-2)(n+3)/2
2、n0=n2+1
3、3 1 4
4、n1-1 n2+n3
5、50 4
6、直接插入排序和冒泡排序
三、判断题(10分)
1、× 2、× 3、√ 4、√ 5、×
6、√ 7、√ 8、 × 9、× 10、√
四、应用题(20分)
1、参考答案如下：
2、参考答案如下：
3、参考答案如下：
4、参考答案如下：
1)
2)带权路径长度269
5、参考答案如下：
1) A B C D E G
2) A B C E D G
6、参考答案如下：
五、算法设计题(30分)
1、算法源代码如下：
int flag=1;
int max;
void sortbitree(bitree T)
{ if(T)
{ sortbitree(T->lchild);
k++;
if(k==1) max=T->data;
else
{ if(T->data>max) max=T->data;
else flag=0; }
sortbitree(T->rchild);
}
}
2、算法源代码如下：
int pathed[MAX_VERTEX_NUM];
int top=0;
int path[MAX_VERTEX_NUM];
int ispath(algraph graph,int vi,int vj)
{ arcptr p;
int j;
pathed[vi]=1; path[++top]=vi;/*将顶点vi加入当前路径path */
if(path[top]==vj) /*存在顶点vi到顶点vj的路径*/
return 1;
else /*将顶点vi的邻接点加入当前路径*/
for(p=graph、vertices[vi]、firstarc;p;p=p->nextarc)
if(!pathed[p->adjvex]) return ispath(graph,p->adjvex,vj);
pathed[vi]=0; top--; /*将顶点vi从当前路径path中删除 */
if(top==0) return 0; /*不存在vi到vj的简单路径*/
}
3、算法源代码如下：
bithrtree insucc(bithrtree p)/*找p结点的后继*/
{ if(p->rtag==1) /*后继线索*/
return p->rchild;
else /*右子树的最左下结点*/
{ p=p->rchild;
while(p->ltag==0) p=p->lchild;
return p; }
}
【数据结构试题及答案】相关文章：
经典java笔试题及答案09-26
阅读理解试题及答案11-14
军校面试试题及答案09-25
客服面试试题及答案09-26
销售面试试题与答案09-26
外企面试的经典试题及答案09-25
逻辑学试题及答案09-26
Java经典笔试题（含答案）09-26
中考英语各类试题及答案09-25
销售行业面试试题及答案09-26