您现在的位置:  网站首页工学类数据结构导论

2009年1月自考数据结构导论试题


 
试题类型:WORD文档 试题时间:2009年1月
所属省份 试卷资费免费下载
网上书店卓越网上搜索看看 试卷收藏加入收藏夹
试卷评级

        分享到:

 


     下载列表
 
          
       
          2009年1月自考数据结构导论试题
       
 
     试卷内容预览
 
  

2009年1月自考数据结构导论试题
课程代码:02142
一、单项选择题(本大题共15小题,每小题2分,共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。
1.数据的不可分割的最小标识单位是( )
A.数据项 B.数据记录
C.数据元素 D.数据变量
2. for(i=0;i<m;i++)
for(j=0;j<t;j++)
c[i][j]=0;
for(i=0;i<m;i++)
for(j=0;j<t;j++)
for(k=0;k<n;k++)
c[i][j]=c[i][j]+a[i][k]*b[k][j];
上列程序的时间复杂度为( )
A.O(m+n×t) B.O(m+n+t)
C.O(m×n×t) D.O(m×t+n)
3.若线性表最常用的操作是存取第i个元素及其前趋的值,那么最节省操作时间的存储方式是( )
A.单链表 B.双链表
C.单循环链表 D.顺序表
4.设单链表中指针p指向结点A,要删除A之后的结点(若存在),则修改指针的操作为
( )
A.p—>next=p—>next—>next B.p=p—>next
C.p=p—>next—>next D.p—>next=p
5.向一个栈顶指针为hs的链栈中插入一个*s结点时,应执行的操作为( )
A.hs—>next=s; B.s—>next=hs;hs=s;
C.s—>next=hs—>next;hs—>next=s; D.s—>next=hs;hs=hs—>next;
6.设循环队列的元素存放在一维数组Q[0‥30]中,队列非空时,front指示队头元素的前一个位置,rear指示队尾元素。如果队列中元素的个数为11,front的值为25,则rear应指向的元素是( )
A.Q[4] B.Q[5]
C.Q[14] D.Q[15]
7.定义二维数组A[1‥8,0‥10],起始地址为LOC,每个元素占2L个存储单元,在以行序为主序的存储方式下,某数据元素的地址为LOC+50L,则在以列序为主序的存储方式下,该元素的存储地址为( )
A.LOC+28L B.LOC+36L
C.LOC+50L D.LOC+52L
8.具有n个结点的二叉树,拥有指向孩子结点的分支数目是( )
A.n-1 B.n
C.n+1 D.2n
9.对一棵有100个结点的完全二叉树按层序编号,则编号为49的结点,它的左孩子的编号为( )
A.99 B.98
C.97 D.50
10.有m个叶子结点的哈夫曼树,其结点总数是( )
A.2m-1 B.2m
C.2m+1 D.2(m+1)
11.有n个结点的无向图的边数最多为( )
A.n+1 B.
C.n(n+1) D.2n(n+1)
12.设图的邻接矩阵为,则该图为( )
A.有向图 B.无向图
C.强连通图 D.完全图
13.二分查找算法的时间复杂度是( )
A.O(n2) B.O(nlog2n)
C.O(n) D.O(log2n)
14.已知8个元素(34,76,45,18,26,54,92,65),按照依次插入结点的方法生成一棵二叉排序树,则该树的深度为( )
A.4 B.5
C.6 D.7
15.采用排序算法对n个元素进行排序,其排序趟数肯定为n-1趟的排序方法是( )
A.插入和快速 B.冒泡和快速
C.选择和插入 D.选择和冒泡
二、填空题(本大题共13小题,每小题2分,共26分)
请在每小题的空格中填上正确答案。错填、不填均无分。
16.在数据结构中,数据的存储结构有顺序存储方式、链式存储方式、_________和散列存储方式等四种。
17. 作为一个算法输入的数据所含数据元素的数目,或与此数目有关的其他参数,称为_________。
18.在双链表中,存储一个结点有三个域,一个是数据域,另两个是指针域,分别指向 _________和 _________。
19.在有n个元素的链队列中,入队和出队操作的时间复杂度分别为_________和_________。
20.在栈结构中,允许插入的一端称为 _________;在队列结构中,允许插入的一端称为 _________。
21.在循环队列中,存储空间为0~n-1。设队头指针front指向队头元素前一个空闲元素,队尾指针指向队尾元素,那么其队空标志为rear=front,队满标志为 _________。
22.深度为k的二叉树至多有 _________个结点,最少有 _________个结点。
23.设有一稠密图G,则G采用 _________存储结构较省空间。设有一稀疏图G,则G采用 _________存储结构较省空间。
24.在一个具有n个结点的单链表中查找其值等于x的结点时,在查找成功的情况下,需平均比较_________个元素结点。
25.假定对线性表R[0…59]进行分块检索,共分为10块,每块长度等于6。若检索索引表和块均用顺序检索的方法,则检索每一个元素的平均检索长度为_________。
26.文件在外存储器上的组织结构主要有三种:顺序文件、散列文件和索引文件,其中 _________特别适应磁带存储器,也适应磁盘存储器。
27.在插入排序、冒泡排序、快速排序、归并排序等排序算法中,占用辅助空间最多的是 _________。
28.冒泡排序最好的时间复杂度为 _________,平均时间复杂度为 _________,是一种稳定的排序算法。
三、应用题(本大题共5小题,每小题6分,共30分)
29.已知一棵二叉树的前序序列是ABCDEFG,中序序列是CBDAEGF。请构造出该二叉树,并给出该二叉树的后序序列。
30.将题30图所示的由三棵树组成的森林转化为一棵二叉树。

题30图
31.已知某图的邻接表存储结构如题31图所示:

题31图
(1)画出该图。
(2)根据该邻接表从顶点A出发,分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。
32.假定采用H(k)=k mod 7计算散列地址,引用线性探测的开放定址法解决冲突,试在0~6的散列地址空间中,对关键字序列(38,25,74,63,52,48)构造散列表,并求出等概率情况下查找成功的平均查找长度。
33.用快速排序法对数据序列(49,38,65,97,16,53,134,27,39)进行排序,写出其第一趟排序的全过程。
四、算法设计题(本大题共2小题,每小题7分,共14分)
34.完善下列折半插入排序算法。
Void binasort(struct node r[MAXSIZE],int n)
{for(i=2;i<=n;i++){
r[0]=r[i];low=1;high=i-1;
while(low<=high){
mid=(1)_________;
if(r[0].key<r[mid].key)
high=(2)_________;
else low=(3)_________;
}
for(j=i-1;j>=low;j- -)
(4)_________;
r[low]=r[0] ;
}
}
35.下列算法的功能是求出指定结点在给定的二叉排序树中所在的层次。请完善该算法。
Void level(BSTree root,p)
{ int level=0;
if(!root)
(1)_________;
else{
level++;
while(root—>key!=p—>key){
if(root—>key<p—>key)
(2)_________ ;
else
(3)_________ ;
level++;
}
(4)_________;
}
}


......
......
 
    更多其他年份试题
    2010年10月自考数据结构导论参考答案  (WORD)
    全国2010年10月自学考试数据结构导论试题  (WORD)
    全国2010年1月自学考试数据结构导论试题  (WORD)
    全国2009年10月自学考试数据结构导论试题  (WORD)
    2009年1月自考数据结构导论试题  (WORD)
    全国2008年10月自学考试数据结构导论试题  (WORD)
    2008年1月全国自学考试试题数据结构导论试卷  (WORD)
    2007年10月自考试题数据结构导论试卷  (WORD)
 
     相关课程
        色彩学       色彩与构成
        森林保护学       森林防火
        森林资源经营管理       商法
        商法(二)       商法原理与实务
        伤寒论
 
     本站声明
自己也曾经是自考生,当初考的是计算机专业的专科,花了我四年半年时间。许多朋友跟我说自考太难了,他们快要坚持不下去了。我自己的经验是,其实自考不难,难的是坚持。 我不相信人天生下来会有谁比谁更聪明的脑袋瓜,只相信谁比谁更努力。努力看书,多做题,多花时间在学习上面,一定能够成功。加油吧!

考一场试下来,需要花费很多精力,也需要花去不少钱。在此我向大家保证,我的网站一定会奉行免费的政策,无论如何,我都不会使网站变成收费模式。

如果本站收集的内容侵犯了你的权利,也请告诉我,我会进行核实后并立即予以删除。

如果认为此网站还可以,告诉你的朋友们吧,我会一如继往,努力拼命的,哈哈!